内容概述
顺序查找，分块查找，折半查找，B-树，B+-树，散列表，算法分析。
顺序查找：
- 哨兵:不用判断表尾
- AVL成功：((1+n)n/2)n=n/2;
- AVL失败：1+n;
typedef struct
{
ElemType *data;
int len;
}SSnode;
int Serch_seq(ElemType e,SSnode* ST)
{
ST.data[0]=e;
for(i=ST.data[ST.len];i!=e;i--) ;
return i;
}
有序表顺序查找：
- 优化了AVL失败
- AVL失败=(1+2+...+n+n)/(n+1)=n/2+n/n+1;
typedef struct
{
ElemType *data;
int len;
}SSnode;
int Serch_seq(ElemType e,SSnode* ST)
{
ST.data[0]=e;
for(i=ST.data[ST.len];i!=e;i--) {if(e>ST.data[i]) return 0};
return i;
}
折半查找：
- 仅适用于有序表
- mid=left+right/2 ,向下取整。
int BinartSearch(SqList L,ElemType e)
{
int left=0,right=L.len-1,mid;
while(left<=right)
{
mid=(left+right)/2;
if(SqList[mid]==e)return mid;
if(SqList[mid]>e) right=mid-1;
else{ left=mid+1 ;}
}
return -1;
}
- 循环条件left<=right。可以取等号。
- ASL=Log(2，n+1)
-
运算流程示例：
image.png
分块查找：
- 即索引顺序查找
- 块间有序，块内无序。块间二分，块内顺序。
代码： - 数据结构:块的左右边界，块内的最大元素值。
typedef strcut IndexElem
{
int left,right,maxkey;
}IndexElem;
- 查找
int BlockIndexSearch(ElemType key)
{
int left=0,right=IndexTable.len-1;
int mid=0;
while(left<=right)
{
mid= (left+right)/2;
if(IndexTable[mid]>key){right=mid-1;}
if(IndexTable[mid]<key){right=mid+1;}
}
if((int i=IndexTable[right].right==Data.len-1)return -1;
for(int i=IndexTable[left].left;i<=IndexTable[left].right;i++)
{
if(Data[i]==key)return i;
}
return -1;
}
B-树
概念
- 平衡因子为0的多路平衡查找树；
- m阶B树，每个结点最多有m-1个关键字，m个子树；最少有m/2.ceil个子树，m/2.ceil-1个关键字。
- 树高为3，则叶节点均在4层。叶节点为null，代表查找失败。
- log(m/2.ceil,n+1/2)+1=>h>=log(m,n+1)。
- 左端：叶节点最少m/2.ceil,失败层最少有2(m/2.ceil)^(h-1)个结点。失败层的节点数=总关键字树+1。所以有n+1>=2(M/2.ceil)^(h-1)。即h-1<=log(m/2.ceil,n+1);
- 令：根节点只有两个子树，其他节点至少有m/2.ceil。所以失败层（h+1）层最少节点数为2(m/2.ceil)^h-1;即第n层最少结点树为2(m/2.ceil)^(n-2);最多：m*(n-1)，根节点最少1个关键字，最多m-1个。
基本操作：
- 查找
- 插入
- 删除
B+-树
- m阶B+树，每个结点做多m个关键字，m个子树；
- 记录存储在叶节点
- 分支结点仅包含下一级索引块的地址和最大值。
散列表：①散列构造，②冲突处理
概念：
-
散列表是一种存储结构（不是顺序也不是随机），地址是关键字的一个函数；
illustrate - 思维导图：
image.png
- 装填因子：非null结点数/总长。装填因子越大，越容易产生冲突，查找效率越低。
- 拉链法解决冲突：null指针的比较不计入比较次数，如3号链表长度为3，查找的key的H（key）为3，但链表中无key，则比较次数为3。
小专题：算法分析
哈希表的ASL:
与表长无关，查找范围是[0,H(key)]若H(key)=key mod k,则范围为[0,k-1];
-
计算思路：先找到每个结点的h(key)，根据其和实际地址的差值计算每个结点的比较次数。
image.png
image.png ASL成功=（16+2+33+4+9）/12= 2.5次
ASL失败=(1+(13+12+11+...+2))/13= 7次（注意分母是13）
空元素和空指针
- 拉链法中，空指针不计入查找次数；
- 线性探测中，空元素的比较计入查找次数。
顺序查找的ASL：
- ASL成功=Σi/n=(n+1)/2
- ASL失败=n+1(要查完所有元素直到空元素)
有序表
-
对顺序查找ASL失败优化
image.png ASL成功=Σi/n=(n+1)/2 不变
ASL失败=(Σi+n)/(n+1)=n/2+n/(n+1)
折半查找
- ASL成功<=h
- ASL失败<=h（null指针不计入ASL）
- h=log(2,n+1).ceiling
分块查找
- n个节点被分成s块，每块b个。n=sb；
索引顺序查找（块内必顺序，索引可顺序可折半）
- ASL成功 = (s+1)/2+(b+1)/2 = (s+1)/2+(n/s+1)/2 = (s^2+2s+n)/2s
- ASL失败 = s+1+b+1
索引折半查找（块内必顺序，索引可顺序可折半）
- ASL成功 <= log(2,s+1).ceil + (b+1)/2
- ASL失败 <= log(2,s+1).ceil + (b+1)
时间复杂度
- 顺序O(n）
- 折半O(log(n))
- 分块(O(n))
- 哈希(O(1))
王道习题
1.折半查找的递归算法：
int BinarySearch(SqList L,ElemType key,int low,int high)
{
int mid=(low+high)/2;
if(low>high)return -1;
if(L[mid]==key)return mid;
return L[mid]>key? BinarySearch[L,key,low,mid-1]:BinarySearch[L,key,mid+1,high];
}
调用
result=BinarySearch(L,5,1,L.len)
