《恋上数据结构与算法一》笔记（十三）集合

一 目录

• 集合介绍
• 接口设计

二 集合(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

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

---

本文参考 MJ老师的 恋上数据结构与算法

---

《恋上数据结构与算法一》笔记

---

本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏与点赞是对我最大的支持和鼓励。

---