Set 定义为 : 不含重复元素的集合 ,它有多种实现方式
1 .线性结构 :
1.1 数组,可以设置有序数组 , 插入元素时 运行 插入排序算法
1.2 链表 , 内存分散 ,元素之间用指针相连 ,同样 插入元素时 运行 插入排序算法
2.二分搜索树
建立一个二叉树 , 可以二分插入
3.桶 (箱)(hash)算法
建立几个桶 ,每个桶中是元素的列表 , 首先将不同的元素分配到不同的桶中,然后 本桶内的元素插入排序
4.位向量方法
当元素是整数时,并已知元素的上界,用一个整数数组表示一个位集合,当插入整数n时,将第n位置1
效率比较: 当 元素上界为n,插入m个数时
集合表示初始化插入遍历总时间空间有序数组1mmO(m^2)m有序链表1mmO(m^2)2m二叉树1logmmO(mlogm)3m箱m1mO(m)3m位向量n1nO(n)n/b