《数据结构与算法》总结（三）集合

一 目录

• 集合介绍
• 接口设计

二 集合(Set)

集合的特点

• 不存放重复的元素
• 常用于去重
  • 存放新增 IP，统计新增 IP 量
  • 存放词汇，统计词汇量
  • ......

三 接口设计

@interface Set : NSObject

- (int)size;

- (BOOL)isEmpty;

- (void)clear;

- (BOOL)contains:(id)element;

- (void)add:(id)element;

- (void)remove:(id)element;

- (void)traversal;

@end

作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

以下资料在群文件可自行下载！

3.1 使用链表实现

• 使用链表实现

@interface ListSet()
/** list*/
@property(nonatomic,strong)LinkedList *list;
@end

@implementation ListSet

- (instancetype)init {
    self = [super init];
    if (self) {
        self.list = [[LinkedList alloc] init];
    }
    return self;
}

#pragma mark - override

- (int)size {
    return (int)self.list.size;
}

- (BOOL)isEmpty {
    return self.list.isEmpty;
}

- (void)clear {
    [self.list clear];
}

- (BOOL)contains:(id)element {
    return [self.list contains:element];
}

- (void)add:(id)element {
    NSUInteger index = [self.list indexOf:element];

    if (index == NSNotFound) {  // 不存在就添加
        [self.list add:element];
    } else {
        [self.list set:index element:element];
    }
}

- (void)remove:(id)element {
    NSInteger index = [self.list indexOf:element];

    if (index != NSNotFound) {  // 存在
        [self.list remove:index];
    }
}

- (void)traversal {
    for (int i = 0; i < self.list.size; i++) {
        NSLog(@"%@",[self.list get:i]);
    }
}

@end

• 测试代码如下

- (void)listSetTest {
    ListSet *set = [[ListSet alloc] init];
    [set add:@10];
    [set add:@11];
    [set add:@11];
    [set add:@12];
    [set add:@10];

    [set traversal];
}

• 运行结果如下

2020-02-29 16:48:50.085402+0800 13_Set[83620:4504418] 10
2020-02-29 16:48:50.085568+0800 13_Set[83620:4504418] 11
2020-02-29 16:48:50.085673+0800 13_Set[83620:4504418] 12

3.2 二叉树实现

• TreeSet

@interface TreeSet()
/** tree */
@property(nonatomic,strong)RBTree *tree;
@end

@implementation TreeSet

- (instancetype)init {
    self = [super init];
    if (self) {
        self.tree = [[RBTree alloc] init];
    }
    return self;
}

#pragma mark - override

- (int)size {
    return self.tree.size;
}

- (BOOL)isEmpty {
    return self.tree.isEmpty;
}

- (void)clear {
    [self.tree clear];
}

- (BOOL)contains:(id)element {
    return [self.tree contains:element];
}

- (void)add:(id)element {
    [self.tree add:element];
}

- (void)remove:(id)element {
    [self.tree remove:element];
}

- (void)traversal {
    [self.tree preordr];
}

@end

• 测试代码

- (void)treeSetTest {
    TreeSet *treeSet = [[TreeSet alloc] init];
    [treeSet add:@12];
    [treeSet add:@10];
    [treeSet add:@7];
    [treeSet add:@11];
    [treeSet add:@10];
    [treeSet add:@11];
//    [treeSet add:@9];

    [treeSet traversal];
}

• 运行结果如下

2020-02-29 16:50:53.745750+0800 13_Set[83665:4507822] 12
2020-02-29 16:50:53.745908+0800 13_Set[83665:4507822] 10
2020-02-29 16:50:53.746010+0800 13_Set[83665:4507822] 7
2020-02-29 16:50:53.746182+0800 13_Set[83665:4507822] 11

---

项目链接地址 - 13_Set

---

作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

推荐阅读

iOS开发——最新 BAT面试题合集（持续更新中）

作者：路飞_Luck
链接：https://www.jianshu.com/p/26fbca3e5f6b
来源：简书