集合的库实现

xiaoxiao2021-03-01  15

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

 

 

转载请注明原文地址: https://www.6miu.com/read-4050196.html

最新回复(0)