返回首页
计算机考研：数据结构常用算法精析（8）
查字典公务员网
第九章 查找
查找分成静态查找和动态查找，静态查找只是找，返回查找位置。而动态查找则不同，若查找成功，返回位置，若查找不成功，则要返回新记录的插入位置。也就是说，静态查找不改变查找表，而动态查找则会有插入操作，会改变查找表的。
不同的查找所采用的存储结构也不同，静态查找采用顺序表，而动态查找由于经常变动，所以用二叉排序树，二叉平衡树、B-和B+。
静态查找有，顺序查找，折半查找，分块查找(索引顺序查找)
顺序查找(Sequential Search)是最简单的一种查找方法。
算法思路
设给定值为k，在表(R1 R2Rn)中，从Rn即最后一个元素开始，查找key=k的记录。若存在一个记录Ri(ln)的key为k，则查找成功，返回记录序号i;否则，查找失败，返回0。
算法描述
int sqsearch(sqlist r,keytype k) //对表r顺序查找的算法//
{ int i;
r.data[0].key=k; //k存入监视哨//
i=r.len; //取表长//
while(r.data[i].key!=k)
i--; //顺序查找//
return(i);
}
算法用了一点技巧：先将k存入监视哨，若对某个i(0)有r.data[i].key=k，则查找成功，返回i;若i从n递减到1都无记录的key为k，i再减1为0时，必有r.data[0].key=k，说明查找失败，返回i=0。
平均查找成功长度ASL= ，而查找失败时，查找次数等于n+l。
折半查找算法及分析
当记录的key按关系有序时，不管是递增的还是递减的，只要有序且采用顺序存储。
算法描述
int Binsearch(sqlist r,keytype k) //对有序表r折半查找的算法//
{ int low,high,mid;
low=1;high=r.len; //上下界初值//
while(low=high) //表空间存在时//
{ mid=(low+high)/2; //求当前mid//
if (k==r.data[mid].key)
return(mid); //查找成功，返回mid//
if (k
high=mid-1; //调整上界，向左部查找//
else
low=mid+1; //调整下界，向右部查找//
}
return(0); //lowhigh，查找失败//
}
判定树：用来描述二分查找过程的二叉树。n个结点的判定树的深度和n个结点的完全二叉树深度相同= 。但判断树不一定是完全二叉树，但他的叶子结点所在层次之差不超过1。所以，折半查找在查找成功时和给定值进行比较的关键字个数至多为
ASL=
分块查找算法及分析
分块查找(Blocking Search)，又称索引顺序查找(Indexed Sequential Search)，是顺序查找方法的一种改进，目的也是为了提高查找效率。
1.分块
设记录表长为n，将表的n个记录分成b= 个块，每块s个记录(最后一块记录数可以少于s个)，即：
且表分块有序，即第i(1b-1)块所有记录的key小于第i+1块中记录的key，但块内记录可以无序。
2.建立索引
每块对应一索引项：
KeymaxLink
其中Keymax为该块内记录的最大key;link为该块第一记录的序号(或指针)。
3.算法思路 分块索引查找分两步进行：
(1)由索引表确定待查找记录所在的块;(可以折半查找也可顺序因为索引表有序)
(2)在块内顺序查找。(只能用顺序查找，块内是无序的)
5.算法分析
分块查找算法的时间复杂度为：
二叉排序树：对二叉排序树中序遍历，得到的肯定是递增的有序序列。所以插入和删除都要保证二叉排序树这一性质。
1.二叉排序树的建立
typedef struct Bsnode; //二叉排序树结点//
{ Retype data; //结点数据//
struct Bsnode *Lchild,*Rchild;
}BSN,*BSP; //结点及指针说明符//
BSP createBst( ) //从键盘文件读入记录，建立二叉排序树的算法//
{ BSP T,S; keytype key;
T=NULL; //置空树，T为二叉排序树根结点指针//
scanf(%dkey); //读入第一个记录的key//
while(key!=0) //设key以0为结束符//
{ S=(BSP)malloc(sizeof(BSN)); //申请结点//
S-data.key=key; //存入key//
S-Lchild=S-Rchild=NULL; //置S结点左、右子树为空//
T=BSTinsert(T,S); //将S结点插入到当前的二叉排序树T中//
scanf(%dkey); //读下一记录的key//
}
return(T); //返回根指针//
}
2.二叉排序树的插入新结点
BSP BSTinsert(BSP T,BSP S)
//二叉排序树的插入算法，T、S分别为根结点和待插入结点的指针//
{ BSP q, p;
if (T==NULL)
return(S); //树为空时，以S为根//
p=T; q=NULL; //q为p的父结点指针//
while(p) //寻找插入位置//
{ q=p;
if(S-data.key==p-data.key)
{ free(S);
return(T);
} //S结点已存在，返回//
if(S-data.keydata.key)
p=p- //向左找//
else
p=p- //向右找//
}
if(S-data.keydata.key)
q-Lchild=S; //S为q的左子插入//
else
q-Rchild=S; //S为q的右子插入//
return(T);
}
3.二叉排序树的删除结点
(1)算法思路：设指针p指向待删除结点，q为p的父结点指针，分两种情况讨论如下：
①当p结点无左子树时，如图
PR
q
P
p=q-Lchild
PR
q
P
p=q-Rchild
其中PR为p结点的右子树(PR=空时，P为叶结点)。此时删除操作只要令：
q-Lchild=p- 或 q-Rchild=p-
②当p结点的左子树PL存在时,有两种删除方法。
删除前：
其一是 直接删除P，再将P的右子树接到新子树的最后下脚
另一种：将P被最右下的元素替换而不用删除结点(用中序前驱替换)需要掌握的
(2)算法描述
Status BSTdelete(BSP t,keytype k)
//在根指针为t的二叉排序树中，删除key=k的结点的算法//
{ BSP p,q,f,h;
p=t;q=NULL; //q为p的父结点指针//
while(p) //寻找被删除结点//
{ if(p-data.key==k)
break; //找到被删p结点，退出//
q=p;
if(kdata.key)
p=p- //向左找//
else
p=p- //向右找//
}
if(p==NULL)
return(t); //若k不在树中，返回//
if(p-Lchild==NULL) //p无左子树时//
{ if(q==NULL)
t=p- //p为根,删除后,其右子为根//
else if(q-Lchild==p) //p为q之左子时//
q-Lchild=p-
else
q-Rchild=p- //p为q之右子时//
free(p);
}
else //p的左子树存在//
{ f=p;h=p- //寻找p在中序下的直接前驱h//
while(h-Rchild)
{ f=h;
h=h-
}
p-data=h- //以h结点代替p结点，即删除p结点//
if(f!=p)
f-Rchild=h-
else
f-Lchild=h-
free(h);
}
return(t);
}
二叉排序树查找算法描述
BSP BSTSearch(BSP t,keytype k) //在二叉排序树t中，查找key=k的结点//
{ BSP p=t;
while(p)
{ if(p-data.key==k)
break; //查找成功，退出循环//
if(kdata.key)
p=p- //向左找//
else
p=p- //向右找//
}
return(p);
} //查找成功时返回的是对应的位置，不成功时是插入位置。
平衡二叉树(AVL)
平衡因子BF(Balance Factor)：BF=HL-HR
Lchild BFdataRchild
树的结点形式：
平衡二叉排序树 :若在构造二叉排序树的同时，使其始终保持为AVL树，则此时的二叉排序树为平衡的二叉排序树。
4中调整方法：设指针a是失去平衡的最小子树根。
1 B
BL
h-1
1
BR
h-1
AR
h-1
LL型调整
0 B
0 A
BL
h-1
1
BR
h-1
AR
h-1
2 A
(1)单向右旋平衡处理：由于在a的左子树根结点的左子树插入结点，a的平衡因子由1增至2，致使以a为根的子树失去平衡，则需要进行一次向右的顺时针旋转操作。(LL)
-1 B
BR
h-1
1
BL
h-1
AL
h-1
RR型调整
0 B
0 A
AL
h-1
BL
h-1
BR
h-1
1
-2 A
(2)单向左旋平衡处理：由于在a的右子树根结点的右子树插入结点，a的平衡因子由-1变成-2，致使以a为根结点的子树失去平衡，则需要一次向左的逆时针旋转操作。(RR)
(3)先左后右平衡处理：由于在a的左子树根结点的右子树上插入结点，a的平衡因子由1增至2，致使以a为根结点的子树失去平衡，需要进行两次旋转(先左旋后右旋)操作(LR)
-1 B
BL
h-1
CL
h-2
1
AR
h-1
LR型调整
0 C
-1 A
BL
h-1
CR
h-2
AR
h-1
2 A
1 C
CR
h-2
0 B
CL
h-2
1
1 B
CL
h-2
1
BR
h-1
AL
h-1
RL型调整
0 C
0 A
AL
h-1
CL
h-2
1
BR
h-1
-2 A
1 C
CR
h-2
-1 B
CR
h-2
(4)先向右后向左平衡处理：由于在a的右子树根结点的左子树上插入结点，a的平衡因子由-1变成-2，致使以a为根结点的子树失去平衡，则需要进行两次旋转(先向右再向左)操作。
B-树：是一种平衡的多路查找树。一棵M阶的B-树，或者为空树，或满足
(1)树中的每个结点至多有M棵子树;
(2)若根结点不是叶子结点，则至少有两颗子树
(3)除根之外的所有非终端结点至少有 棵子树。
(4)所有结点的关键字的个数比他的子树个数少1
一棵3阶B-树(又称2-3树)。
掌握B-树的插入与删除
哈希表：处理冲突的方法
1.开放地址法
(1)di=1，2，3，(m-1)称为线性探查法;
(2)di= ， ， ， 称为二次探查法。
2.链地址法
发生冲突时，将各冲突记录链在一起，即同义词的记录存于同一链表。
装填因子定义：= ，
一般，设Hash表的装填因子为，采用线性、二次探查法及链地址法解决冲突时，查找成功的平均查找长度分别用公式表示如下：
线性探查法：
二次探查法：
链地址法：
第9章节有关数据结构算法，上文中为大家作了分析，希望考生对于这些算法能够熟记于心，方便考试的应用和日后的实际操作，预祝大家都能够取得好成绩，加油!
