蒙城网站建设,温州公司网站建设,成都高速公路网站建设招标,建立网站商城建议集合
1、集合中的数据元素除了属于同一集合外,没有任何的逻辑关系 2、在集合中,每个数据元素都有一个区别于其他元素的唯一标识(键值或者关键字值) 3、集合的运算#xff1a;
1 查找某一元素是否存在(内部查找、外部查找)
2 将集合中的元素按照它的唯一标识进行排序4、集合的…集合
1、集合中的数据元素除了属于同一集合外,没有任何的逻辑关系 2、在集合中,每个数据元素都有一个区别于其他元素的唯一标识(键值或者关键字值) 3、集合的运算
1 查找某一元素是否存在(内部查找、外部查找)
2 将集合中的元素按照它的唯一标识进行排序4、集合的存储
1 任何容器都可以存储集合
2 常用的表示形式是借鉴于线性表或树5、唯一 一个仅适合于存储和处理集合的数据结构是散列表
注意
散列表不但是一种存储方法也是一种查找方法查找
1、查找表用于查找的集合称为查找表 2、查找表的分类
1 静态查找表其中的元素是静态的(不会动态变化)
2 动态查找表其中的元素经常进行插入和删除操作(会动态变化)3、平均查找长度是指查找过程中对关键码的平均比较次数 注意顺序查找从左到右
顺序查找(无序表)
毫无选择只能做线性的顺序查找
注意监视哨在data[0]的位置核心步骤(一定是可以找到该元素的)
int i;
data[0] k;
//从后往前查找
for(idata.size()-1;k!data[i];--i)
return i;
//查找成功返回该元素的对应下标
//查找失败返回0(在下标为0的位置找到该元素)顺序查找(有序表)
和无序表的顺序查找是类似的,只是当被查找元素在表中不存在的时候,不需要遍历到表尾 例如在0 2 4 6 8 中查找5的时候,从后往前遍历,走到4的时候就可以结束遍历 核心步骤
int i;
data[0] k;
//从后往前查找
for(idata.size()-1;kdata[i];--i)
if(k data[i]) return i;
return 0;无序表的顺序查找的平均查找长度(ASL)
注意从后往前进行比较
推导
1 查找第一个元素需要比较n次
2 查找第二个元素需要比较n-1次
3 ...
4 查找第n个元素需要比较1次
5 那么总共需要比较n*(n1)/2
6 假设每个关键码都是等概率的p 1/n
7 那么n*(n1)/2 * 1/n (n1)/2
8 也就是说在查找成功的情况下平均需要比较(n1)/2个元素注意n*(n1)*(1/n) (n1)
1 查找每个元素都需要从末尾比较到0该算法的时间复杂度为O(n)
折半查找(二分查找) 查找成功 查找失败 非递归折半查找
int low 1;
int high data.size()-1;
int mid;while(lowhigh)
{mid (lowhigh)/2;if(k data[mid]) return mid;if(kdata[mid]) high mid-1;else low mid1;
}return 0;递归折半查找
折半查找(判定树) 注意 对判定树进行中序遍历得到的序列和有序表一样
外部结点和内部结点 注意
1 外部结点数目 内部结点数目 1
2 外部结点都是叶子结点
3 内部结点都是度为2的结点
4 n0 n2 1计算平均查找长度
1 查找成功(内部结点)(1*12*23*44*2)/9 25/9
2 查找失败(外部结点)(3*64*4)/10 34/100折半查找的性能
分块查找(索引顺序块的查找) 注意
1 块之间是有序的(第一块所有值小于第二块的所有值...)
2 在块内的元素之间可能有序也可能无序索引表
注意
1 先在索引表内查找
2 在对应块内的查找典型题目解析 解释 1 左边是小于 2 右边是大于 3 判断是否为一条直线 注意 左分支高度大于等于右分支(向上取整)
易错题 注意折半查找判定树的高度和完全二叉树的高度是一致的
1 向下取整**右分支的长度大于等于左分支的长度**答案为 1 3 6 8 11 13 16 19
