第 9章 查找 （ 5～ 6学时）
静态查找表顺序表的查找有序表的查找索引顺序表的查找
动态查找表二叉排序树平衡二叉树
散列表第 9章 查找
基本概念查找,根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。
关键字,是记录或数据元素中某个数据项的值。
（主关键字：唯一标识；次关键字：标识若干个。）
查找成功,若表中存在这样的一个记录。
查找不成功,若表中不存在关键字等于给定值的记录。
查找表,由同一类型的数据元素构成的集合。
静态查找表,若对查找表只作查找操作，则此类查找表称为静态查找表。
动态查找表,若在查找的过程中同时进行插入或删除，则此类表称为动态查找表。
第 9章 查找平均查找长度 ASL(Average Search Length)：
为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在成功时的平均查找长度。
ASL=∑pici i=1～ n
其中,n,结点个数
pi:查找第 i个结点的概率（等概率）
ci:找到第 i个结点所需要的比较次数
(以其关键字和给定值进行过比较的记录个数的平均值作为衡量查找算法好坏的依据 )
静态查找表
顺序表的查找基本思想,从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值相比较，若当前扫描到的结点关键字与相等，则查找成功；若扫描结束后，仍未找到关键字等于的结点，则查找不成功。（该法可用于顺序存储结构或链式存储结构）
（参见,P216-算法 9.1）
查找成功的平均查找长度：
ASLss=∑pici=1/n∑(n-i+1)=(n+1)/2
顺序查找的平均查找长度：
ASL=1/(2n)(∑(n-i+1)+n(n+1))=3/4· (n+1)
静态查找表
顺序查找的特点优点：算法简单，对表的结构或关键字是否有序无任何要求。
缺点：查找效率低。
静态查找表
有序表的查找折半查找（二分查找）,先确定待查记录所在的范围，
然后逐步缩小范围直到找到或找不到该记录为止。
（条件,（ 1）表中数据的关键字有序
（ 2）表是顺序存储结构 ）
（参见,P219）
静态查找表
折半查找的算法
int Search_Bin(SSTable ST,KeyType key)
{ low=1; high=ST.length;
while (low<high)
{ mid=(low+high)/2;
if (EQ(key,ST.elem[mid].key)) return mid;
else if(LT(key,ST.elem[mid].key)) high=mid-1;
else low=mid+1;
}
}
静态查找表
折半查找的性能分析
(折半查找的过程可用二叉树来描述 )
折半查找在查找成功时和给定值进行比较的关键字个数至多为 log2n +1
折半查找在查找不成功时和给定值进行比较的关键字个数最多也不超过 log2n +1
成功平均查找长度：
ASLbs= ∑pici=1/n∑j.2j-1=(n+1)/n*log2(n+1)-1
（当 n>50时）
ASLbs=log2(n+1)-1
静态查找表
索引顺序表的查找（分块查找）
（是顺序查找的一种改进。在此查找方法中，除表本身外，尚需建立一个索引表。索引表按关键字有序。）
索引表关键字项：其值为该子表内的最大关键字。
指针项：指示该子表的第一个记录在表中位置。
（参见,P225-图 9.6）
分块查找过程,
（ 1）先确定待查记录所在的块（子表），可采用顺序查找或折半查找。
（ 2）然后在块中顺序查找。
静态查找表分块查找的算法即为折半查找或顺序查找的简单组合。
分块查找的平均查找长度为：
ASLbs=Lb+Lw
其中,Lb,为查找索引表确定所在块的平均查找长度。
Lw,为在块中查找元素的平均查找长度。
若用顺序查找确定所在块，则：
ASLbs=(b+1)/2+(s+1)/2=(n/s+s)/2+1
若用分块查找确定所在块，则：
ASLbs≈log2(n/s+1)+s/2
一般情况下,b= n/s
s=√n
静态查找表 （练习题）
设有 10000个结点的线性表，若采用顺序查找、
顺序分块查找和二分查找，问它们的成功平均查找长度 ASL各是多少？
动态查找表
二叉排序树（二叉查找树）
或者是一棵空树，或者是具有下列性质的二叉树：
（ 1）若它的左子树不空，则左子树上 所有 结点的值 均小于 它的根结点的值；
（ 2）若它的右子树不空，则右子树上 所有 结点的值 均大于 它的根结点的值；
（ 3）它的左、右子树也分别为二叉排序树。
（参见,P227-图 9.7）
重要性质：按中序遍历该树所得到的中序序列是一个递增有序序列。
动态查找表
二叉排序树的查找当二叉排序树不空时，首先将给定值和根结点的关键字比较，
若相等，则查找成功；否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续查找。
（通常，可取二叉链表作为二叉排序树的存储结构。）
查找算法：
BiTree SearchBST(BiTree T,KeyType key)
{ if ((! T) || EQ(key,T->data.key)) return(T);
else if (LT(key,T->data.key)) return(SearchBST(T->lchild,key));
else return(SearchBST(T->rchild,key));
}
动态查找表
二叉排序树的插入若二叉排序树为空，则待插入结点作为根结点插入到树中；
当二叉树非空时，将待插入结点的关键字与根结点的关键字相比较，若相等，则不插入；若小于，则将待插入结点插入到根的左子树中；否则插入到根的右子树中。而子树的插入过程与树中的插入过程相同。
（新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。）
（参见,P229-图 9.8）
动态查找表
二叉排序树的插入算法 (查找算法 )
Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p)
{ if ((! T) {p=f; return FALSE; }
else if (EQ(key,T->data.key)) {p=T; return TRUE; }
else if (LT(key,T->data.key)) return(SearchBST(T->lchild,
key,T,p));
else return(SearchBST(T->rchild,key,T,p));
}
其中,T是将要生成的二叉排序树；
f是指向 T的双亲指针，初始调用值为 NULL；
p是指向数据元素结点的指针。
动态查找表
二叉排序树的插入算法
Status Insert_BST(BiTree &T,ElemType e)
{ if ( ! SearchBST(T,e.key,NULL,p))
{ s=(BiTree) malloc (sizeof(BiTNode));
s->data=e; s->lchild=s->rchild=NULL;
if (! p) T=s;
else if (LT(e.key,p->data.key)) p->lchild=s;
else p-rchild=s;
return TRUE;
} return FALSE;
} (结合图 9.8说明二叉排序树的构造过程 )
动态查找表
二叉排序树的删除
(在二叉排序树中删除一个结点相当于删除有序序列中一个结点，
而不是删除以该结点为根的子树。 )
删除操作首先进行查找，以确定被删结点是否在二叉排序树中，若不在，则不做任何事情；否则，删除操作可按结点是否有左子树（或右子树）来处理。
（ 1） 若 p结点为叶子结点，即 pL和 pR均为空；
（ 2） 若 p结点只有左子树 pL或右子树 pR；
（ 3） 若 p结点的左子树 pL和右子树 pR均不空。
动态查找表
二叉排序树的删除算法
Status Delete_BST(BiTree &T,KeyType key)
{ if (! T) return FALSE;
else if (EQ(key,T->data.key)) Delete(T,f );
else if (LT(key,T->data.key)) Delete_BST(T->lchild,key);
else Delete_BST(T->rchild,key);
return TRUE;
}
动态查找表
二叉排序树的删除算法
Void Delete(BiTree &p,BiTree &f)
{ if (! P->rchild)
{ q=p; p=p->lchild; f->lchild=p; free(q); }
else if (! P->lchild)
{ q=p; p=p->rchild; f->lchild=p; free(q); }
else { q=p; s=p->lchild;
while (s->rchild) { q=s; s=s->rchild;}
p->data=s->data;
if (q!=p) q->rchild=s->lchild;
else q->lchild=s->lchild;
}
}
动态查找表
二叉排序树的查找分析例,（参见,P231-图 9.10）
ASL(a)=(1+2+2+3+3+3)/6=14/6
ASL(b)=(1+2+3+4+5+6)/6=21/6
结论：形态均称的二叉排序树的平均查找长度小，效率高。
动态查找表 （练习题）
设关键字集合为,{22,12,30,38,25,28}和 {38，
30,28,25,22,12},请画出它们的二叉排序树，
成功查找的平均查找长度 ASL？ 结论？
动态查找表 （练习题参考答案）
22 38
12 30 30
25 38 28
28 …
12
动态查找表
平衡二叉树（ AVL树）
它或者是一棵空树，或者是具有下列性质的二叉树：
它的左子树和右子树都是平衡二叉树，并且左子树和右子树的深度之差的绝对值不超过 1。
平衡因子,定义为该左子树的深度减去它的右子树的深度。
（参见,P233-图 91.1：平衡二叉树于不平衡二叉树）
动态查找表
平衡二叉树的构造？
Adelson,Velskii和 Landis提出了一个动态地保持二叉排序树平衡的方法：在构造二叉排序树的过程中，
每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，若是，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。
（通常将这样得到的平衡的二叉排序树简称为 AVL树）
（ 参见,P234-图 9.12：平衡二叉树的生成过程）
动态查找表
不平衡的四种情况：
LL型：在 A的左孩子（ L） 的左子树（ L） 上插入结点，使 A的平衡因子由 1变为 2而失去平衡。 （平衡处理：单向右旋）
LR型：在 A的左孩子（ L） 的右子树（ R） 上插入结点，使 A的平衡因子由 1变为 2而失去平衡。
（平衡处理：双向旋转（先左后右））
RR型：在 A的右孩子（ R） 的右子树（ R） 上插入结点，使 A的平衡因子由 -1变为 -2而失去平衡。 （平衡处理：单向左旋）
RL型：在 A的右孩子（ R） 的左子树（ L） 上插入结点，使 A的平衡因子由 -1变为 -2而去平衡。
（平衡处理：双向旋转（先右后左））
（参见,P235-图 9.13）
动态查找表
平衡二叉树的算法
(参见,P236,P237)
动态查找表 （练习题）
设关键字集合为,{10,20,30,50,40}，依次输入各结点，请画出平衡二叉树的构造过程。
动态查找表 （练习题参考答案）
10 0 10 -1 10 -2 20 0 20 -1
20 0 20 -1 10 0 30 0 10 0 30 -1
30 0 50 0
20 –2 （ RR型） 20 -1
10 0 30 –2 10 0 40 0
50 1 30 0 50 0
40 0 （ LR型）
散列表
散列（ Hashing）,是一种重要的存储方法，也是一种常见的查找方法。（关键字 —地址转换法）
基本思想,以结点的关键字 k为自变量，通过一个确定的函数关系 f,计算出对应的函数值 f(k),把这个值解释为结点的存储地址，将结点存入所指的存储位置上。
查找时，再根据要查找的关键字用同样的函数计算地址，然后到相应的地址单元里取要找的结点。
散列表,用散列法存储的线性表。
散列函数,上述的函数 f。
散列地址,函数值 f(k)。
散列表
散列函数的构造方法直接定址法数字选择法平方取中法折叠法除留余数法基数转换法随机数法散列表
直接定址法取关键字或关键字的某个线性函数值作为哈希地址。
H(k)=key 或 H(key)=a.key+b
（这种函数叫做自身函数）
例,P253-表 9.2、表 9.3
数字选择法取关键字的若干数位组成哈希地址。
散列表
平方取中法取关键字平方后的中间几位为哈希地址。
折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
移位叠加,将各段的最低位对齐，然后相加。
边界叠加,将两个相邻的段沿边界折叠，然后相加。
例,key=123456
H(key)=123+456=579
H(key)=123+654=777
散列表
除留余数法（最常用的一种方法）
取关键字被某个不大于哈希表表长 m的数 p除后所得的余数为哈希地址。
H(key)=key MOD p p≤m
（ 一般情况下，选 p为小于或等于哈希表表长 m的某个最大质数为好 。）
散列表
基数转换法将关键字看成是另一个进制上的数后，再把它转换成原来进制上的数，取此数或其中若干位作为哈希地址。
随机数法选择一个随机函数，取关键字的随机函数值为它的哈希函数。
H(key)=random(key)
散列表
采用何种哈希函数，通常应考虑的因素有：
⑴ 计算哈希函数所需时间
⑵ 关键字的长度
⑶ 哈希表的大小
⑷ 关键字的分布情况
⑸ 记录的查找频率散列表
冲突,对不同的关键字可能得到同一哈希地址，即：
key1≠key2,而 H(key1)=H(key2),这种现象称为冲突。
同义词,具有相同函数值的关键字对该函数来说称做同义词。
聚集,哈希地址不同的结点争夺同一个后继哈希地址的现象称为聚集。
解决冲突的方法,
开放地址法拉链法散列表
开放地址法 ( Hi=(H(key)+di) MOD m )
当冲突发生时，使用某种方法在哈希表中形成一个探查序列，
沿着此探查序列逐个单元查找，直到找到给定的关键字，或者碰到一个开放地址（即该地址单元为空）为止。查找时，碰到一个开放地址，则说明表中没有待查的关键字；插入时，碰到一个开放地址，则可将待插入的新结点存放在该地址单元中。
⑴ 线性探查法 di=1,2,…,m -1
⑵ 二次探查法 di=12,-12,22,-22,…
⑶ 随机探查法 di=随机数序列
⑷ 双散列函数探查法 di=iH2(key)
散列表
(参见,P259-例 9-4)
散列表
拉链法将所有关键字为同义词的结点链接在一个单链表中。
（ 参见,P258-例 9-3）
散列表
散列表的查找与分析影响平均查找长度的因素：
⑴ 哈希函数
⑵ 处理冲突的方法
⑶ 哈希表的装填因子?
=表中填入的记录数 n/哈希表的长度 m
散列表
应用举例已知一组关键字为 {26,36,41,38,44,15，
68,12,6,51,25}的数据，用线性探查法解决冲突，
构造这组关键字的散列表，并计算成功查找的平均查找长度 ASL。（ 装填因子为 0.75，散列函数为：
H(key)=key MOD 13）
表长,m=n/0.75=14.67=15
散列表,HT[0..14]
散列表散列地址,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
关键字,26 25 41 15 68 44 6 36 38 12 51
MOD 13,0 12 2 2 3 5 6 10 12 12 12
比较次数,1 5 1 2 2 1 1 1 1 2 3
成功查找的平均查找长度：
ASL=(1+5+1+2+2+1+1+1+1+2+3)/11=20/11=1.82
不成功查找的平均查找长度：
ASL=(8+7+6+5+4+3+2+1+1+1+2+1+11)/13=52/13=4
上机实习题：
产生 30个 1～ 99之间的随机整数，并将此数据存入到文件中；
从文件中读取数据，并对这批数据进行顺序查找和二分查找，查找值为 28的数，若存在，输出该数在表中的位置；
将这批数据构成二叉排序树，在此树中查找值为 28的数，若存在，则删除该数；若不存在，则插入该数。
第 10章 内部排序 （ 5～ 6学时）
基本概念
插入排序
选择排序
交换排序
归并排序
基数排序
各种排序方法比较基本概念
排序,把一组无序的记录按其关键字的某种次序排列起来，使其具有一定的顺序。
内部排序,排序过程在内存中进行，不涉及外存。
外部排序,排序过程还涉及到外存的访问。
稳定性,若待排序的记录序列中存在多个关键字相同的记录，经过排序后，这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的。反之，则是不稳定的。
插入排序直接插入排序
基本思想,每一趟将一个待排序的记录，按其关键字值的大小插入到已经有序表中，直到全部插入完成。
例,（参见,P266-图 10.1）
算法,（参见,P256-算法 10.1）
稳定性,稳定
时间复杂度,O(n2)
特点,算法简便，易实现，当 n较小时，是一种很好的排序方法。
插入排序
直接插入排序算法：
Void IsertSort(Sqlist &L)
{ for (i=2; i<=L.length; ++i)
if (LT(L.r[i].key,L.r[i-1].key))
{ L.r[0]=L.r[i];
for (j=i-1; LT(L.r[0].key,L.r[j].key); --j)
L.r[j+1]=L.r[j];
L.r[j+1]=L.r[0];
}
}
插入排序希尔排序（缩小增量排序）
基本思想,先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录,基本有序,时，再对全体记录进行一次直接插入排序。
例,（参见,P272-图 10.5）
算法,（参见,P272-算法 10.4）
稳定性,不稳定
时间复杂度,O(n3/2)
特点：效率较高
（基于两点分析：（ 1）基本有序；（ 2）记录较少。）
插入排序
希尔排序算法：
Void Shellsort(SqList &L,int dk)
{ for (i=dk+1; i<=L.length; ++i)
if (LT(L.r[i].key,L.r[i-dk].key))
{ L.r[0]= L.r[i];
for (j=i-dk; j>0 && LT(L.r[0].key,L.r[j].key); j-=dk)
L.r[j+dk]=L.r[j];
L.r[j+dk]=L.r[0];
}
}
插入排序
关于希尔排序的增量选取：
（到目前为止，尚未有人求得一种最好的增量序列）
希尔最初提出：
d1=n/2,di+1=di/2,dt=1 t=log2n
后人研究的局部结论：
dk=2t-k+1-1 1≤k≤t≤log2(n+1)
练习题
已知序列 {17,18,60,40,7,32,73,65,85}，
请给出直接插入排序和希尔排序每一趟的结果（升序）。
练习题 （参考答案）
直接插入排序
17 18 60 40 7 32 73 65 85
① 17 18 60 40 7 32 73 65 85
② 17 18 60 40 7 32 73 65 85
③ 17 18 60 40 7 32 73 65 85
④ 17 18 40 60 7 32 73 65 85
⑤ 7 17 18 40 60 32 73 65 85
⑥ 7 17 18 32 40 60 73 65 85
⑦ 7 17 18 32 40 60 73 65 85
⑧ 7 17 18 32 40 60 65 73 85
⑨ 7 17 18 32 40 60 65 73 85
练习题 （参考答案）
希尔排序
17 18 60 40 7 32 73 65 85
① 17 7 32 40 18 60 73 65 85
17 7 32 40 18 60 73 65 85
② 17 7 18 40 32 60 73 65 85
17 7 18 40 32 60 73 65 85
③ 7 17 18 32 40 60 65 73 85
(注,d1=3,d2=2,d3=1)
选择排序简单选择排序
基本思想,通过 n-i次关键字间的比较，从 n-i+1个记录中选出关键字最小的记录，并和第 i(1≤i≤n)个记录交换之。
例,{ 49,38,65,97,76,13,27,49 }
① 13 38 65 97 76 49 27 49
② 13 27 65 97 76 49 38 49
③ 13 27 38 97 76 49 65 49
④ 13 27 38 49 76 97 65 49
⑤ 13 27 38 49 49 97 65 76
⑥ 13 27 38 49 49 65 97 76
⑦ 13 27 38 49 49 65 76 97
⑧ 13 27 38 49 49 65 76 97
选择排序
简单选择排序算法：
Void SelectSort( SqList &L)
{ for (i=1; i<L.length; ++i)
{ j=SelectMinKey(L,i);
if (i!=j) L.r[i] L.r[j];
}
}
选择排序
算法,（参见,P277-算法 10.9）
稳定性：不 稳定反例,2 2 1
1 2 2
时间复杂度,O(n2)
特点,算法简便，易实现。
选择排序堆排序堆的定义,n个元素的序列 {k1,k2,…,k n}当且仅当满足下 列关系时，
ki≤k2i ki≥k2i
ki≤k2i+1 或 ki≥k2i+1
（ 参见,P280-图 10.10）
堆排序,若在输出堆顶元素之后，使得剩余 n-1个元素的序列重新又建成一个堆，如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。
堆排序需解决两个问题：
（ 1） 建初始堆（对无序序列） (参见,P282-图 10.12)
（ 2） 调整建新堆（在输出堆顶元素之后） (参见,P281-图 10.11)
选择排序
筛选,自堆顶至叶子的调整过程。
（参见,P282-图 10.12,P281-图 10.11）
堆排序算法
（参见,P281-算法 10.10）
筛选算法
（参见,P282-算法 10.11）
稳定性：不 稳定
时间复杂度,O(n logn)
特点,对较大的文件很有效。
选择排序
堆排序算法,
typedef SqList HeapType;
void HeapSort(HeapType &H)
{ for (i=H.length/2; i>0; --i)
HeapAdjust(H,i,H.length);
for (i=H.length; i>1; --i)
{ H.r[1] H.r[i];
HeapAdjust(H,1,i-1);
}
}
选择排序
筛选算法,
void HeapAdjust(HeapType &H,int s,int m)
{ rc=H.r[s];
for (j=2*s; j<=m; j*=2)
{ if (j<m && LT(H.r[j].key,H.r[j+1].key)) ++j;
if (! LT(rc.key,H.r[j].key)) break;
H.r[s]=H.r[j]; s=j;
} H.r[s]=rc;
}
练习题
已知序列 {17,18,60,40,7,32,73,65,85}，
请给出简单选择排序和堆排序每一趟的结果（升序）。
练习题 （参考答案）
简单选择排序
17 18 60 40 07 32 73 65 85
① 07 18 60 40 17 32 73 65 85
② 07 17 60 40 18 32 73 65 85
③ 07 17 18 40 60 32 73 65 85
④ 07 17 18 32 60 40 73 65 85
⑤ 07 17 18 32 40 60 73 65 85
⑥ 07 17 18 32 40 60 73 65 85
⑦ 07 17 18 32 40 60 65 73 85
⑧ 07 17 18 32 40 60 65 73 85
⑨ 07 17 18 32 40 60 65 73 85
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
17 85
18 60 65 73
40 7 32 73 40 7 32 60
65 85 18 17
（建初始堆,大根堆）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
17 73
65 73 65 60
40 7 32 60 40 7 32 17
18 85 18 85
（交换） （调整）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
18 65
65 60 40 60
40 7 32 17 18 7 32 17
73 85 73 85
（交换） （调整）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
17 60
40 60 40 32
18 7 32 65 18 7 17 65
73 85 73 85
（交换） （调整）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
17 40
40 32 18 32
18 7 60 65 17 7 60 65
73 85 73 85
（交换） （调整）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
7 32
18 32 18 7
17 40 60 65 17 40 60 65
73 85 73 85
（交换） （调整）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
17 18
18 7 17 7
32 40 60 65 32 40 60 65
73 85 73 85
（交换） （调整）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
7 17
17 18 7 18
32 40 60 65 32 40 60 65
73 85 73 85
（交换） （调整）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
7 7
17 18 17 18
32 40 60 65 32 40 60 65
73 85 73 85
（交换） （调整）
上机实习题：
产生三组 50个 1～ 99之间的随机整数，并将此数据存入到数据文件中；
从文件中读取数据，并对这批数据进行直接插入排序、
简单选择排序和堆排序，分别输出这三种方法对三组数据所需的比较次数。
（注：随机函数的头文件,<stdlib.h>
随机函数的初始化,randomize( )
随机函数,rand( m ) ）
交换排序交换排序：
基本思想,两两比较待排序记录的关键字，发现两个记 录的次序相反时，即进行交换，直到没有反序的记录为止。
正序,记录的关键字按所需次序排列的序列。
反序,记录的关键字按所需次序的逆序排列的序列。
冒泡排序基本思想,首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依次类推，直至第
n-1个记录和第 n个记录的关键字进行过比较为止。
(或反之 )
交换排序
例,（参见,P273-图 10.6）
算法,（参见,P16-1.43节）
Void bubble_sort(int a[],int n)
{ for ( i=n-1,change=TRUE; i>1 && change; --i )
{ change=FALSE;
for (j=0; j<i; ++j )
if (a[j]>a[j+1]) { a[j] a[j+1]; change=TRUE; }
}
}
稳定性,稳定
时间复杂度,O(n2)
交换排序
快速排序基本思想,通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，
则可分别对这两部分记录继续进行排序，以达到整个序列有序。
例,（参见,P275-图 10.7）
算法,（参见,P276-算法 10.8、算法 10.7和算法 10.6 ）
稳定性：不 稳定
时间复杂度,O(logn)
（就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法）
练习题
已知序列 {17,18,60,40,7,32,73,65,85}，
请给出冒泡排序和快速排序每一趟的结果（升序）。
练习题 （参考答案）
冒泡排序,（ 17 18 60 40 07 32 73 65 85）
17 07
18 17 17
60 18 18 18
40 60 32 32 32
07 40 60 40 40
32 32 40 60 60
73 65 65 65 65
65 73 73 73 73
85 85 85 85 85
① ② ③ ④
练习题 （参考答案）
快速排序
17 18 60 40 07 32 73 65 85
① 07 17 60 40 18 32 73 65 85
② 07 17 32 40 18 60 73 65 85
③ 07 17 18 32 40 60 65 73 85
④ 07 17 18 32 40 60 65 73 85
归并排序
归并,是将两个或两个以上的有序表组合成一个新的有序表。
二路归并排序基本思想,将待排序文件看成 n个长度为 1的有序子文件，把这些子文件两两归并，便得到 n/2 个长度为 2的有序子文件，然后再把这 n/2 个有序的子文件两两归并，如此反复，直到最后得到一个长度为 n的有序文件为止。
例,（参见,P283-图 10.13）
算法,（参见,P283-算法 10.12、算法 10.13和算法 10.14 ）
稳定性,稳定
时间复杂度,O(nlog2n)
练习题
已知序列 {17,18,60,40,7,32,73,65,85}，
请给出二路归并排序每一趟的结果（升序）。
练习题 （参考答案）
二路归并排序
17 18 60 40 07 32 73 65 85
17 18 40 60 07 32 65 73 85
17 18 40 60 07 32 65 73 85
07 17 18 32 40 60 65 73 85
基数排序基数排序是和前面所述各类排序方法完全不同的一种排序方法，它是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
多关键字排序 （例：整理扑克牌。关键字：花色、面值）
MSD法（最高位优先）
LSD法（最低位优先）
分配：
收集：
基数排序,从最低数位关键字起，按关键字的不同值将序列中记录“分配”到 RADIX个队列中后再“收集”之，如此重复次。
按这种方法实现排序称之为基数排序。（基：是指
RADIX的取值范围。例：十进制数它的基是 10）
基数排序
例,（ P287-图 10.14）
算法,（ P288-算法 10.17,10.15,10.16）
稳定性,稳定
时间复杂度,O(d*(rd+n))
各种排序方法比较
各种排序方法之间的比较主要从以下几个方面综合考虑：
（ 1）算法的时间复杂度
（ 2）算法的空间复杂度
（ 3）排序的稳定性
（ 4）算法结构的复杂性
（ 5）参加排序数据的规模各种排序方法比较
在平均情况下，希尔、快速、堆及归并排序方法都能达到较快的排序速度，从速度来看，快速排序最快，从空间来看，堆排序最省。当 n较小，或基本有序时，插入排序和冒泡排序也能达到较快的排序速度。
从算法结构的复杂性来看，选择排序与冒泡排序方法比较简单和直接，而希尔、快速、堆以及归并排序较为复杂。
从数据序列的规模大小来看,n越小，采用简单排序方法就越合适； n越大，采用改进的排序方法越合适。
从稳定性来看，插入、冒泡、归并和基数排序方法是稳定的；而希尔、选择、堆和快速排序方法是不稳定的。
第 12章 文件 （ 2学时）
基本概念
顺序文件
索引文件
ISAM文件和 VSAM文件
散列文件
多关键字文件基本概念
文件,是由大量性质相同的记录组成的集合。
（通常，存储在外存储器中。）
操作系统文件,仅是一维的连续的字符序列，无结构、无解释。
数据库文件,是带有结构的记录的集合，这类记录是由一个或多个数据项组成的集合。
（单关键字文件、多关键字文件）
定长记录文件,文件中每个记录含有的信息长度相同。
不定长记录文件,文件中含有信息长度不等。
记录的逻辑结构,是指记录在用户或应用程序员面前呈现的方式，
是用户对数据的表示和存取方式。（它着眼于用户使用方便）
记录的物理结构,是数据在物理存储器上的存储方式，是数据的物理表示和组织。（它着眼于存储空间的提高和存取时间的减少）
基本概念
文件的操作,检索和修改
检索
（ 1）顺序存取：存取下一个逻辑记录
（ 2）直接存取：存取第 i个记录
（ 3）按关键字存取：给定一个值，查询一个和一批关键字与给定值相关的记录。
查询：（ 1）简单查询：查询关键字等于给定值的记录。
（ 2）区域查询：查询关键字属于某个区域的记录。
（ 3）函数查询：给定关键字的某个函数。
（ 4）布尔查询：将上述三种查询用布尔运算组合起来的查询。
基本概念
修改插入删除更新
文件的物理结构文件在存储介质上的组织方式。
（ 1）顺序组织
（ 2）随机组织
（ 3）链组织顺序文件
顺序文件,是根据记录的序号或记录的相对位置来进行存取的文件组织方式。
连续文件,若次序相继的两个物理记录在存储介质上的存储位置是相邻的，则又称为连续文件。
串联文件,若物理记录之间的次序由指针相连表示，则称为串联文件。
特点,
（ 1）存取第 i个记录，必须先搜索在它之前的 i-1个记录。
（ 2）插入新的记录时只能加在文件的末尾。
（ 3）若要更新文件中的某个记录，则必须将整个文件进行复制。
索引文件
索引文件,包括文件数据区和索引表两大部分的文件。
索引表,指示逻辑记录和物理记录之间一一对应关系的表。
索引项,索引表中的每一项。（总是按关键字有序）
索引顺序文件,若数据区中的记录按关键字顺序排列。
索引非顺序文件,若数据区中的记录不按关键字顺序排列。
稠密索引,每个记录建立一个索引项，如此建立的索引表称之为稠密索引。
非稠密索引,一组记录建立一个索引项，这种索引表称之为非稠密索引。
ISAM文件和 VSAM文件
索引顺序存取方法 ISAM(Indexed Seguential Access Method)
是一种专为磁盘存取设计的文件组织方式。
磁盘是以盘组、柱面和磁道三级地址存取的设备。则磁盘上的数据文件建立盘组、柱面和磁道三级索引。
柱面索引,由关键字和指针组成。前者表示该柱面中最末一个记录的关键字（最大关键字），后者指示该柱面上磁道索引位置。当柱面索引较大时，可建立柱面索引的索引
（主索引）。
磁道索引,由基本索引项和溢出索引项组成。每一部分都包括关键字和指针两项，前者表示该磁道中最末一个记录的关键字（最大关键字），后者指示该磁道中第一个记录的位置。
（参见,P314-图 128、图 129）
ISAM文件和 VSAM文件
ISAM文件的检索主索引 柱面索引 磁道索引
ISAM文件的插入
（每个柱面的基本区是顺序存储结构，而溢出区是链表结构。）
溢出区,（ 1）集中存放：整个文件设一个大的单一的溢出区。
（ 2）分散存放：每个柱面设一个溢出区。
（ 3）集中与分散：先移至每个柱面各自的溢出区，待满后再使用公共溢出区。
ISAM文件的删除只需找到待删除的记录，在其存储位置上作删除标志即可。
ISAM文件和 VSAM文件
虚拟存储存取方法 VSAM（ Virtual Storage Access Method）
它利用了操作系统的虚拟存储器的功能，给用户提供方便。对用户来说，文件只有控制区间和控制区域等逻辑存储单位，而与外存储器中的柱面、磁道等具体存储单位没有关系。
VSAM文件结构,它由索引集、顺序集和数据集三部分组成。
（参见,P316-图 12.11）
控制区间,数据集中的一个结点称为控制区间。
（每个控制区间可视为一个逻辑磁道）
控制区域,顺序集中一个结点连同其对应的所有控制区间形成一个整体，称做控制区域。
（每个控制区域可视为一个逻辑柱面）
ISAM文件和 VSAM文件
VSAM文件的插入无溢出区，解决的办法,
（ 1）每个控制区间不填满记录，在最末一个记录和控制信息之间留有空隙。
（ 2）在每个控制区域中有一些完全空的控制区间，并在顺序集的索引中指明这些空区间。
VSAM文件的删除删除记录时，需将同一控制区间中较删除记录关键字大的记录向前移动，把空间留给以后插入的新记录。
VSAM文件的优点,动态地分配和释放存储，不需要对文件进行重组，并能较快地对插入的记录进行查找。
散列文件
散列文件,是指利用哈希法进行组织的文件。即根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。
桶,在散列文件中，将若干个记录组成一个存储单位，这个存储单位称做桶。
基桶,将 m个同义词的记录可以存放在同一地址的桶中，这个桶称为基桶。
溢出桶,将第 m+1个同义词存放到另一个桶中，此桶称为溢出桶。
（例：参见,P318-图 12.13）
特点,优点：文件随机存放，记录不需要进行排序；插入、删除方便，存取速度快，不需要索引区，节省存储空间。
缺点：不能进行顺序查询，只能按关键字随机存取。
多关键字文件
多关键字文件在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。（例：高考成绩查询）
多重表文件记录按主关键字的顺序构成一个串联文件，并建立主关键字的索引（主索引），主索引为非稠密索引；对每一个次关键字建立次关键字索引（次索引），次索引为稠密索引，所有具有同一次关键字的记录构成一个链表。
（参见,P320-图 12.15）
特点：易于编程，易于修改，插入记录容易，但删除记录繁琐。
多关键字文件
倒排文件,与多重表文件的区别在于次关键字索引的结构不同。（通常，具有相同次关键字的记录之间不设指针相连，而在次关键字索引（倒排表）的该次关键字的一项中存放这些记录的物理记录号。）
（参见,P320-图 12.16）
倒排文件的特点优点：检索记录较快。
缺点：维护困难。
B-树 (参见,P238)
B-树是一种平衡的多路查找树。
一棵 m阶的 B树，或为空树，或为满足下列特性的 m叉树,
(1)树中每个结点至多有 m棵子树；
(2)若根结点不是叶子结点，只至少有两棵子树；
(3)除根之外的所有非终端结点至少有 m/2棵子树；
(4)所有非终端结点中包含下列信息数据
（ n,A0,K1,A1,K2,A2,…,K n,An）
(5)所有的叶子结点都出现在同一层次上，相当于失败点（查找不到）。
(B-树的查找、插入和删除参见 P242)
B+树 (参见,P246)
B+树是 B-树的一种变形，其区别在于：
(1)有 m棵子树的结点中含有 m个关键字；
(2)所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小从小到大顺序连接；
(3)所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大（或最小）关键字。
（在 B+树上进行查找、插入和删除的过程基本上与 B-树类似）
练习题
如图所示的一棵 3阶 B-树，给出分别插入关键字为 2,12,16和 17
的结点之后的结果。
7
3 9,13
1 4,5 8 10,11 14,15
练习题 （参考答案）
插入 2之后：
7
3 9,13
1,2 4,5 8 10,11 14,15
练习题 （参考答案）
插入 12之后：
7,11
3 9 13
1,2 4,5 8 10 12 14,15
练习题 （参考答案）
插入 16之后：
7,11
3 9 13,15
1,2 4,5 8 10 11 14 16
练习题 （参考答案）
插入 17之后：
7,11
3 9 13,15
1,2 4,5 8 10 11 14 16,17
练习题
如图所示的一棵 3阶 B-树，给出分别删除关键字为 50和 53的结点之后的结果。
45
24 53,90
3,12 37 50 61,70 100
练习题 （参考答案）
删除 50之后
45
24 61,90
3,12 37 53 70 100
练习题 （参考答案）
删除 53之后
45
24 90
3,12 37 61,70 100
静态查找表顺序表的查找有序表的查找索引顺序表的查找
动态查找表二叉排序树平衡二叉树
散列表第 9章 查找
基本概念查找,根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。
关键字,是记录或数据元素中某个数据项的值。
（主关键字：唯一标识；次关键字：标识若干个。）
查找成功,若表中存在这样的一个记录。
查找不成功,若表中不存在关键字等于给定值的记录。
查找表,由同一类型的数据元素构成的集合。
静态查找表,若对查找表只作查找操作，则此类查找表称为静态查找表。
动态查找表,若在查找的过程中同时进行插入或删除，则此类表称为动态查找表。
第 9章 查找平均查找长度 ASL(Average Search Length)：
为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在成功时的平均查找长度。
ASL=∑pici i=1～ n
其中,n,结点个数
pi:查找第 i个结点的概率（等概率）
ci:找到第 i个结点所需要的比较次数
(以其关键字和给定值进行过比较的记录个数的平均值作为衡量查找算法好坏的依据 )
静态查找表
顺序表的查找基本思想,从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值相比较，若当前扫描到的结点关键字与相等，则查找成功；若扫描结束后，仍未找到关键字等于的结点，则查找不成功。（该法可用于顺序存储结构或链式存储结构）
（参见,P216-算法 9.1）
查找成功的平均查找长度：
ASLss=∑pici=1/n∑(n-i+1)=(n+1)/2
顺序查找的平均查找长度：
ASL=1/(2n)(∑(n-i+1)+n(n+1))=3/4· (n+1)
静态查找表
顺序查找的特点优点：算法简单，对表的结构或关键字是否有序无任何要求。
缺点：查找效率低。
静态查找表
有序表的查找折半查找（二分查找）,先确定待查记录所在的范围，
然后逐步缩小范围直到找到或找不到该记录为止。
（条件,（ 1）表中数据的关键字有序
（ 2）表是顺序存储结构 ）
（参见,P219）
静态查找表
折半查找的算法
int Search_Bin(SSTable ST,KeyType key)
{ low=1; high=ST.length;
while (low<high)
{ mid=(low+high)/2;
if (EQ(key,ST.elem[mid].key)) return mid;
else if(LT(key,ST.elem[mid].key)) high=mid-1;
else low=mid+1;
}
}
静态查找表
折半查找的性能分析
(折半查找的过程可用二叉树来描述 )
折半查找在查找成功时和给定值进行比较的关键字个数至多为 log2n +1
折半查找在查找不成功时和给定值进行比较的关键字个数最多也不超过 log2n +1
成功平均查找长度：
ASLbs= ∑pici=1/n∑j.2j-1=(n+1)/n*log2(n+1)-1
（当 n>50时）
ASLbs=log2(n+1)-1
静态查找表
索引顺序表的查找（分块查找）
（是顺序查找的一种改进。在此查找方法中，除表本身外，尚需建立一个索引表。索引表按关键字有序。）
索引表关键字项：其值为该子表内的最大关键字。
指针项：指示该子表的第一个记录在表中位置。
（参见,P225-图 9.6）
分块查找过程,
（ 1）先确定待查记录所在的块（子表），可采用顺序查找或折半查找。
（ 2）然后在块中顺序查找。
静态查找表分块查找的算法即为折半查找或顺序查找的简单组合。
分块查找的平均查找长度为：
ASLbs=Lb+Lw
其中,Lb,为查找索引表确定所在块的平均查找长度。
Lw,为在块中查找元素的平均查找长度。
若用顺序查找确定所在块，则：
ASLbs=(b+1)/2+(s+1)/2=(n/s+s)/2+1
若用分块查找确定所在块，则：
ASLbs≈log2(n/s+1)+s/2
一般情况下,b= n/s
s=√n
静态查找表 （练习题）
设有 10000个结点的线性表，若采用顺序查找、
顺序分块查找和二分查找，问它们的成功平均查找长度 ASL各是多少？
动态查找表
二叉排序树（二叉查找树）
或者是一棵空树，或者是具有下列性质的二叉树：
（ 1）若它的左子树不空，则左子树上 所有 结点的值 均小于 它的根结点的值；
（ 2）若它的右子树不空，则右子树上 所有 结点的值 均大于 它的根结点的值；
（ 3）它的左、右子树也分别为二叉排序树。
（参见,P227-图 9.7）
重要性质：按中序遍历该树所得到的中序序列是一个递增有序序列。
动态查找表
二叉排序树的查找当二叉排序树不空时，首先将给定值和根结点的关键字比较，
若相等，则查找成功；否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续查找。
（通常，可取二叉链表作为二叉排序树的存储结构。）
查找算法：
BiTree SearchBST(BiTree T,KeyType key)
{ if ((! T) || EQ(key,T->data.key)) return(T);
else if (LT(key,T->data.key)) return(SearchBST(T->lchild,key));
else return(SearchBST(T->rchild,key));
}
动态查找表
二叉排序树的插入若二叉排序树为空，则待插入结点作为根结点插入到树中；
当二叉树非空时，将待插入结点的关键字与根结点的关键字相比较，若相等，则不插入；若小于，则将待插入结点插入到根的左子树中；否则插入到根的右子树中。而子树的插入过程与树中的插入过程相同。
（新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。）
（参见,P229-图 9.8）
动态查找表
二叉排序树的插入算法 (查找算法 )
Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p)
{ if ((! T) {p=f; return FALSE; }
else if (EQ(key,T->data.key)) {p=T; return TRUE; }
else if (LT(key,T->data.key)) return(SearchBST(T->lchild,
key,T,p));
else return(SearchBST(T->rchild,key,T,p));
}
其中,T是将要生成的二叉排序树；
f是指向 T的双亲指针，初始调用值为 NULL；
p是指向数据元素结点的指针。
动态查找表
二叉排序树的插入算法
Status Insert_BST(BiTree &T,ElemType e)
{ if ( ! SearchBST(T,e.key,NULL,p))
{ s=(BiTree) malloc (sizeof(BiTNode));
s->data=e; s->lchild=s->rchild=NULL;
if (! p) T=s;
else if (LT(e.key,p->data.key)) p->lchild=s;
else p-rchild=s;
return TRUE;
} return FALSE;
} (结合图 9.8说明二叉排序树的构造过程 )
动态查找表
二叉排序树的删除
(在二叉排序树中删除一个结点相当于删除有序序列中一个结点，
而不是删除以该结点为根的子树。 )
删除操作首先进行查找，以确定被删结点是否在二叉排序树中，若不在，则不做任何事情；否则，删除操作可按结点是否有左子树（或右子树）来处理。
（ 1） 若 p结点为叶子结点，即 pL和 pR均为空；
（ 2） 若 p结点只有左子树 pL或右子树 pR；
（ 3） 若 p结点的左子树 pL和右子树 pR均不空。
动态查找表
二叉排序树的删除算法
Status Delete_BST(BiTree &T,KeyType key)
{ if (! T) return FALSE;
else if (EQ(key,T->data.key)) Delete(T,f );
else if (LT(key,T->data.key)) Delete_BST(T->lchild,key);
else Delete_BST(T->rchild,key);
return TRUE;
}
动态查找表
二叉排序树的删除算法
Void Delete(BiTree &p,BiTree &f)
{ if (! P->rchild)
{ q=p; p=p->lchild; f->lchild=p; free(q); }
else if (! P->lchild)
{ q=p; p=p->rchild; f->lchild=p; free(q); }
else { q=p; s=p->lchild;
while (s->rchild) { q=s; s=s->rchild;}
p->data=s->data;
if (q!=p) q->rchild=s->lchild;
else q->lchild=s->lchild;
}
}
动态查找表
二叉排序树的查找分析例,（参见,P231-图 9.10）
ASL(a)=(1+2+2+3+3+3)/6=14/6
ASL(b)=(1+2+3+4+5+6)/6=21/6
结论：形态均称的二叉排序树的平均查找长度小，效率高。
动态查找表 （练习题）
设关键字集合为,{22,12,30,38,25,28}和 {38，
30,28,25,22,12},请画出它们的二叉排序树，
成功查找的平均查找长度 ASL？ 结论？
动态查找表 （练习题参考答案）
22 38
12 30 30
25 38 28
28 …
12
动态查找表
平衡二叉树（ AVL树）
它或者是一棵空树，或者是具有下列性质的二叉树：
它的左子树和右子树都是平衡二叉树，并且左子树和右子树的深度之差的绝对值不超过 1。
平衡因子,定义为该左子树的深度减去它的右子树的深度。
（参见,P233-图 91.1：平衡二叉树于不平衡二叉树）
动态查找表
平衡二叉树的构造？
Adelson,Velskii和 Landis提出了一个动态地保持二叉排序树平衡的方法：在构造二叉排序树的过程中，
每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，若是，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。
（通常将这样得到的平衡的二叉排序树简称为 AVL树）
（ 参见,P234-图 9.12：平衡二叉树的生成过程）
动态查找表
不平衡的四种情况：
LL型：在 A的左孩子（ L） 的左子树（ L） 上插入结点，使 A的平衡因子由 1变为 2而失去平衡。 （平衡处理：单向右旋）
LR型：在 A的左孩子（ L） 的右子树（ R） 上插入结点，使 A的平衡因子由 1变为 2而失去平衡。
（平衡处理：双向旋转（先左后右））
RR型：在 A的右孩子（ R） 的右子树（ R） 上插入结点，使 A的平衡因子由 -1变为 -2而失去平衡。 （平衡处理：单向左旋）
RL型：在 A的右孩子（ R） 的左子树（ L） 上插入结点，使 A的平衡因子由 -1变为 -2而去平衡。
（平衡处理：双向旋转（先右后左））
（参见,P235-图 9.13）
动态查找表
平衡二叉树的算法
(参见,P236,P237)
动态查找表 （练习题）
设关键字集合为,{10,20,30,50,40}，依次输入各结点，请画出平衡二叉树的构造过程。
动态查找表 （练习题参考答案）
10 0 10 -1 10 -2 20 0 20 -1
20 0 20 -1 10 0 30 0 10 0 30 -1
30 0 50 0
20 –2 （ RR型） 20 -1
10 0 30 –2 10 0 40 0
50 1 30 0 50 0
40 0 （ LR型）
散列表
散列（ Hashing）,是一种重要的存储方法，也是一种常见的查找方法。（关键字 —地址转换法）
基本思想,以结点的关键字 k为自变量，通过一个确定的函数关系 f,计算出对应的函数值 f(k),把这个值解释为结点的存储地址，将结点存入所指的存储位置上。
查找时，再根据要查找的关键字用同样的函数计算地址，然后到相应的地址单元里取要找的结点。
散列表,用散列法存储的线性表。
散列函数,上述的函数 f。
散列地址,函数值 f(k)。
散列表
散列函数的构造方法直接定址法数字选择法平方取中法折叠法除留余数法基数转换法随机数法散列表
直接定址法取关键字或关键字的某个线性函数值作为哈希地址。
H(k)=key 或 H(key)=a.key+b
（这种函数叫做自身函数）
例,P253-表 9.2、表 9.3
数字选择法取关键字的若干数位组成哈希地址。
散列表
平方取中法取关键字平方后的中间几位为哈希地址。
折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
移位叠加,将各段的最低位对齐，然后相加。
边界叠加,将两个相邻的段沿边界折叠，然后相加。
例,key=123456
H(key)=123+456=579
H(key)=123+654=777
散列表
除留余数法（最常用的一种方法）
取关键字被某个不大于哈希表表长 m的数 p除后所得的余数为哈希地址。
H(key)=key MOD p p≤m
（ 一般情况下，选 p为小于或等于哈希表表长 m的某个最大质数为好 。）
散列表
基数转换法将关键字看成是另一个进制上的数后，再把它转换成原来进制上的数，取此数或其中若干位作为哈希地址。
随机数法选择一个随机函数，取关键字的随机函数值为它的哈希函数。
H(key)=random(key)
散列表
采用何种哈希函数，通常应考虑的因素有：
⑴ 计算哈希函数所需时间
⑵ 关键字的长度
⑶ 哈希表的大小
⑷ 关键字的分布情况
⑸ 记录的查找频率散列表
冲突,对不同的关键字可能得到同一哈希地址，即：
key1≠key2,而 H(key1)=H(key2),这种现象称为冲突。
同义词,具有相同函数值的关键字对该函数来说称做同义词。
聚集,哈希地址不同的结点争夺同一个后继哈希地址的现象称为聚集。
解决冲突的方法,
开放地址法拉链法散列表
开放地址法 ( Hi=(H(key)+di) MOD m )
当冲突发生时，使用某种方法在哈希表中形成一个探查序列，
沿着此探查序列逐个单元查找，直到找到给定的关键字，或者碰到一个开放地址（即该地址单元为空）为止。查找时，碰到一个开放地址，则说明表中没有待查的关键字；插入时，碰到一个开放地址，则可将待插入的新结点存放在该地址单元中。
⑴ 线性探查法 di=1,2,…,m -1
⑵ 二次探查法 di=12,-12,22,-22,…
⑶ 随机探查法 di=随机数序列
⑷ 双散列函数探查法 di=iH2(key)
散列表
(参见,P259-例 9-4)
散列表
拉链法将所有关键字为同义词的结点链接在一个单链表中。
（ 参见,P258-例 9-3）
散列表
散列表的查找与分析影响平均查找长度的因素：
⑴ 哈希函数
⑵ 处理冲突的方法
⑶ 哈希表的装填因子?
=表中填入的记录数 n/哈希表的长度 m
散列表
应用举例已知一组关键字为 {26,36,41,38,44,15，
68,12,6,51,25}的数据，用线性探查法解决冲突，
构造这组关键字的散列表，并计算成功查找的平均查找长度 ASL。（ 装填因子为 0.75，散列函数为：
H(key)=key MOD 13）
表长,m=n/0.75=14.67=15
散列表,HT[0..14]
散列表散列地址,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
关键字,26 25 41 15 68 44 6 36 38 12 51
MOD 13,0 12 2 2 3 5 6 10 12 12 12
比较次数,1 5 1 2 2 1 1 1 1 2 3
成功查找的平均查找长度：
ASL=(1+5+1+2+2+1+1+1+1+2+3)/11=20/11=1.82
不成功查找的平均查找长度：
ASL=(8+7+6+5+4+3+2+1+1+1+2+1+11)/13=52/13=4
上机实习题：
产生 30个 1～ 99之间的随机整数，并将此数据存入到文件中；
从文件中读取数据，并对这批数据进行顺序查找和二分查找，查找值为 28的数，若存在，输出该数在表中的位置；
将这批数据构成二叉排序树，在此树中查找值为 28的数，若存在，则删除该数；若不存在，则插入该数。
第 10章 内部排序 （ 5～ 6学时）
基本概念
插入排序
选择排序
交换排序
归并排序
基数排序
各种排序方法比较基本概念
排序,把一组无序的记录按其关键字的某种次序排列起来，使其具有一定的顺序。
内部排序,排序过程在内存中进行，不涉及外存。
外部排序,排序过程还涉及到外存的访问。
稳定性,若待排序的记录序列中存在多个关键字相同的记录，经过排序后，这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的。反之，则是不稳定的。
插入排序直接插入排序
基本思想,每一趟将一个待排序的记录，按其关键字值的大小插入到已经有序表中，直到全部插入完成。
例,（参见,P266-图 10.1）
算法,（参见,P256-算法 10.1）
稳定性,稳定
时间复杂度,O(n2)
特点,算法简便，易实现，当 n较小时，是一种很好的排序方法。
插入排序
直接插入排序算法：
Void IsertSort(Sqlist &L)
{ for (i=2; i<=L.length; ++i)
if (LT(L.r[i].key,L.r[i-1].key))
{ L.r[0]=L.r[i];
for (j=i-1; LT(L.r[0].key,L.r[j].key); --j)
L.r[j+1]=L.r[j];
L.r[j+1]=L.r[0];
}
}
插入排序希尔排序（缩小增量排序）
基本思想,先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录,基本有序,时，再对全体记录进行一次直接插入排序。
例,（参见,P272-图 10.5）
算法,（参见,P272-算法 10.4）
稳定性,不稳定
时间复杂度,O(n3/2)
特点：效率较高
（基于两点分析：（ 1）基本有序；（ 2）记录较少。）
插入排序
希尔排序算法：
Void Shellsort(SqList &L,int dk)
{ for (i=dk+1; i<=L.length; ++i)
if (LT(L.r[i].key,L.r[i-dk].key))
{ L.r[0]= L.r[i];
for (j=i-dk; j>0 && LT(L.r[0].key,L.r[j].key); j-=dk)
L.r[j+dk]=L.r[j];
L.r[j+dk]=L.r[0];
}
}
插入排序
关于希尔排序的增量选取：
（到目前为止，尚未有人求得一种最好的增量序列）
希尔最初提出：
d1=n/2,di+1=di/2,dt=1 t=log2n
后人研究的局部结论：
dk=2t-k+1-1 1≤k≤t≤log2(n+1)
练习题
已知序列 {17,18,60,40,7,32,73,65,85}，
请给出直接插入排序和希尔排序每一趟的结果（升序）。
练习题 （参考答案）
直接插入排序
17 18 60 40 7 32 73 65 85
① 17 18 60 40 7 32 73 65 85
② 17 18 60 40 7 32 73 65 85
③ 17 18 60 40 7 32 73 65 85
④ 17 18 40 60 7 32 73 65 85
⑤ 7 17 18 40 60 32 73 65 85
⑥ 7 17 18 32 40 60 73 65 85
⑦ 7 17 18 32 40 60 73 65 85
⑧ 7 17 18 32 40 60 65 73 85
⑨ 7 17 18 32 40 60 65 73 85
练习题 （参考答案）
希尔排序
17 18 60 40 7 32 73 65 85
① 17 7 32 40 18 60 73 65 85
17 7 32 40 18 60 73 65 85
② 17 7 18 40 32 60 73 65 85
17 7 18 40 32 60 73 65 85
③ 7 17 18 32 40 60 65 73 85
(注,d1=3,d2=2,d3=1)
选择排序简单选择排序
基本思想,通过 n-i次关键字间的比较，从 n-i+1个记录中选出关键字最小的记录，并和第 i(1≤i≤n)个记录交换之。
例,{ 49,38,65,97,76,13,27,49 }
① 13 38 65 97 76 49 27 49
② 13 27 65 97 76 49 38 49
③ 13 27 38 97 76 49 65 49
④ 13 27 38 49 76 97 65 49
⑤ 13 27 38 49 49 97 65 76
⑥ 13 27 38 49 49 65 97 76
⑦ 13 27 38 49 49 65 76 97
⑧ 13 27 38 49 49 65 76 97
选择排序
简单选择排序算法：
Void SelectSort( SqList &L)
{ for (i=1; i<L.length; ++i)
{ j=SelectMinKey(L,i);
if (i!=j) L.r[i] L.r[j];
}
}
选择排序
算法,（参见,P277-算法 10.9）
稳定性：不 稳定反例,2 2 1
1 2 2
时间复杂度,O(n2)
特点,算法简便，易实现。
选择排序堆排序堆的定义,n个元素的序列 {k1,k2,…,k n}当且仅当满足下 列关系时，
ki≤k2i ki≥k2i
ki≤k2i+1 或 ki≥k2i+1
（ 参见,P280-图 10.10）
堆排序,若在输出堆顶元素之后，使得剩余 n-1个元素的序列重新又建成一个堆，如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。
堆排序需解决两个问题：
（ 1） 建初始堆（对无序序列） (参见,P282-图 10.12)
（ 2） 调整建新堆（在输出堆顶元素之后） (参见,P281-图 10.11)
选择排序
筛选,自堆顶至叶子的调整过程。
（参见,P282-图 10.12,P281-图 10.11）
堆排序算法
（参见,P281-算法 10.10）
筛选算法
（参见,P282-算法 10.11）
稳定性：不 稳定
时间复杂度,O(n logn)
特点,对较大的文件很有效。
选择排序
堆排序算法,
typedef SqList HeapType;
void HeapSort(HeapType &H)
{ for (i=H.length/2; i>0; --i)
HeapAdjust(H,i,H.length);
for (i=H.length; i>1; --i)
{ H.r[1] H.r[i];
HeapAdjust(H,1,i-1);
}
}
选择排序
筛选算法,
void HeapAdjust(HeapType &H,int s,int m)
{ rc=H.r[s];
for (j=2*s; j<=m; j*=2)
{ if (j<m && LT(H.r[j].key,H.r[j+1].key)) ++j;
if (! LT(rc.key,H.r[j].key)) break;
H.r[s]=H.r[j]; s=j;
} H.r[s]=rc;
}
练习题
已知序列 {17,18,60,40,7,32,73,65,85}，
请给出简单选择排序和堆排序每一趟的结果（升序）。
练习题 （参考答案）
简单选择排序
17 18 60 40 07 32 73 65 85
① 07 18 60 40 17 32 73 65 85
② 07 17 60 40 18 32 73 65 85
③ 07 17 18 40 60 32 73 65 85
④ 07 17 18 32 60 40 73 65 85
⑤ 07 17 18 32 40 60 73 65 85
⑥ 07 17 18 32 40 60 73 65 85
⑦ 07 17 18 32 40 60 65 73 85
⑧ 07 17 18 32 40 60 65 73 85
⑨ 07 17 18 32 40 60 65 73 85
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
17 85
18 60 65 73
40 7 32 73 40 7 32 60
65 85 18 17
（建初始堆,大根堆）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
17 73
65 73 65 60
40 7 32 60 40 7 32 17
18 85 18 85
（交换） （调整）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
18 65
65 60 40 60
40 7 32 17 18 7 32 17
73 85 73 85
（交换） （调整）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
17 60
40 60 40 32
18 7 32 65 18 7 17 65
73 85 73 85
（交换） （调整）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
17 40
40 32 18 32
18 7 60 65 17 7 60 65
73 85 73 85
（交换） （调整）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
7 32
18 32 18 7
17 40 60 65 17 40 60 65
73 85 73 85
（交换） （调整）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
17 18
18 7 17 7
32 40 60 65 32 40 60 65
73 85 73 85
（交换） （调整）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
7 17
17 18 7 18
32 40 60 65 32 40 60 65
73 85 73 85
（交换） （调整）
练习题 （参考答案）
堆排序
17 18 60 40 7 32 73 65 85
7 7
17 18 17 18
32 40 60 65 32 40 60 65
73 85 73 85
（交换） （调整）
上机实习题：
产生三组 50个 1～ 99之间的随机整数，并将此数据存入到数据文件中；
从文件中读取数据，并对这批数据进行直接插入排序、
简单选择排序和堆排序，分别输出这三种方法对三组数据所需的比较次数。
（注：随机函数的头文件,<stdlib.h>
随机函数的初始化,randomize( )
随机函数,rand( m ) ）
交换排序交换排序：
基本思想,两两比较待排序记录的关键字，发现两个记 录的次序相反时，即进行交换，直到没有反序的记录为止。
正序,记录的关键字按所需次序排列的序列。
反序,记录的关键字按所需次序的逆序排列的序列。
冒泡排序基本思想,首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依次类推，直至第
n-1个记录和第 n个记录的关键字进行过比较为止。
(或反之 )
交换排序
例,（参见,P273-图 10.6）
算法,（参见,P16-1.43节）
Void bubble_sort(int a[],int n)
{ for ( i=n-1,change=TRUE; i>1 && change; --i )
{ change=FALSE;
for (j=0; j<i; ++j )
if (a[j]>a[j+1]) { a[j] a[j+1]; change=TRUE; }
}
}
稳定性,稳定
时间复杂度,O(n2)
交换排序
快速排序基本思想,通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，
则可分别对这两部分记录继续进行排序，以达到整个序列有序。
例,（参见,P275-图 10.7）
算法,（参见,P276-算法 10.8、算法 10.7和算法 10.6 ）
稳定性：不 稳定
时间复杂度,O(logn)
（就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法）
练习题
已知序列 {17,18,60,40,7,32,73,65,85}，
请给出冒泡排序和快速排序每一趟的结果（升序）。
练习题 （参考答案）
冒泡排序,（ 17 18 60 40 07 32 73 65 85）
17 07
18 17 17
60 18 18 18
40 60 32 32 32
07 40 60 40 40
32 32 40 60 60
73 65 65 65 65
65 73 73 73 73
85 85 85 85 85
① ② ③ ④
练习题 （参考答案）
快速排序
17 18 60 40 07 32 73 65 85
① 07 17 60 40 18 32 73 65 85
② 07 17 32 40 18 60 73 65 85
③ 07 17 18 32 40 60 65 73 85
④ 07 17 18 32 40 60 65 73 85
归并排序
归并,是将两个或两个以上的有序表组合成一个新的有序表。
二路归并排序基本思想,将待排序文件看成 n个长度为 1的有序子文件，把这些子文件两两归并，便得到 n/2 个长度为 2的有序子文件，然后再把这 n/2 个有序的子文件两两归并，如此反复，直到最后得到一个长度为 n的有序文件为止。
例,（参见,P283-图 10.13）
算法,（参见,P283-算法 10.12、算法 10.13和算法 10.14 ）
稳定性,稳定
时间复杂度,O(nlog2n)
练习题
已知序列 {17,18,60,40,7,32,73,65,85}，
请给出二路归并排序每一趟的结果（升序）。
练习题 （参考答案）
二路归并排序
17 18 60 40 07 32 73 65 85
17 18 40 60 07 32 65 73 85
17 18 40 60 07 32 65 73 85
07 17 18 32 40 60 65 73 85
基数排序基数排序是和前面所述各类排序方法完全不同的一种排序方法，它是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
多关键字排序 （例：整理扑克牌。关键字：花色、面值）
MSD法（最高位优先）
LSD法（最低位优先）
分配：
收集：
基数排序,从最低数位关键字起，按关键字的不同值将序列中记录“分配”到 RADIX个队列中后再“收集”之，如此重复次。
按这种方法实现排序称之为基数排序。（基：是指
RADIX的取值范围。例：十进制数它的基是 10）
基数排序
例,（ P287-图 10.14）
算法,（ P288-算法 10.17,10.15,10.16）
稳定性,稳定
时间复杂度,O(d*(rd+n))
各种排序方法比较
各种排序方法之间的比较主要从以下几个方面综合考虑：
（ 1）算法的时间复杂度
（ 2）算法的空间复杂度
（ 3）排序的稳定性
（ 4）算法结构的复杂性
（ 5）参加排序数据的规模各种排序方法比较
在平均情况下，希尔、快速、堆及归并排序方法都能达到较快的排序速度，从速度来看，快速排序最快，从空间来看，堆排序最省。当 n较小，或基本有序时，插入排序和冒泡排序也能达到较快的排序速度。
从算法结构的复杂性来看，选择排序与冒泡排序方法比较简单和直接，而希尔、快速、堆以及归并排序较为复杂。
从数据序列的规模大小来看,n越小，采用简单排序方法就越合适； n越大，采用改进的排序方法越合适。
从稳定性来看，插入、冒泡、归并和基数排序方法是稳定的；而希尔、选择、堆和快速排序方法是不稳定的。
第 12章 文件 （ 2学时）
基本概念
顺序文件
索引文件
ISAM文件和 VSAM文件
散列文件
多关键字文件基本概念
文件,是由大量性质相同的记录组成的集合。
（通常，存储在外存储器中。）
操作系统文件,仅是一维的连续的字符序列，无结构、无解释。
数据库文件,是带有结构的记录的集合，这类记录是由一个或多个数据项组成的集合。
（单关键字文件、多关键字文件）
定长记录文件,文件中每个记录含有的信息长度相同。
不定长记录文件,文件中含有信息长度不等。
记录的逻辑结构,是指记录在用户或应用程序员面前呈现的方式，
是用户对数据的表示和存取方式。（它着眼于用户使用方便）
记录的物理结构,是数据在物理存储器上的存储方式，是数据的物理表示和组织。（它着眼于存储空间的提高和存取时间的减少）
基本概念
文件的操作,检索和修改
检索
（ 1）顺序存取：存取下一个逻辑记录
（ 2）直接存取：存取第 i个记录
（ 3）按关键字存取：给定一个值，查询一个和一批关键字与给定值相关的记录。
查询：（ 1）简单查询：查询关键字等于给定值的记录。
（ 2）区域查询：查询关键字属于某个区域的记录。
（ 3）函数查询：给定关键字的某个函数。
（ 4）布尔查询：将上述三种查询用布尔运算组合起来的查询。
基本概念
修改插入删除更新
文件的物理结构文件在存储介质上的组织方式。
（ 1）顺序组织
（ 2）随机组织
（ 3）链组织顺序文件
顺序文件,是根据记录的序号或记录的相对位置来进行存取的文件组织方式。
连续文件,若次序相继的两个物理记录在存储介质上的存储位置是相邻的，则又称为连续文件。
串联文件,若物理记录之间的次序由指针相连表示，则称为串联文件。
特点,
（ 1）存取第 i个记录，必须先搜索在它之前的 i-1个记录。
（ 2）插入新的记录时只能加在文件的末尾。
（ 3）若要更新文件中的某个记录，则必须将整个文件进行复制。
索引文件
索引文件,包括文件数据区和索引表两大部分的文件。
索引表,指示逻辑记录和物理记录之间一一对应关系的表。
索引项,索引表中的每一项。（总是按关键字有序）
索引顺序文件,若数据区中的记录按关键字顺序排列。
索引非顺序文件,若数据区中的记录不按关键字顺序排列。
稠密索引,每个记录建立一个索引项，如此建立的索引表称之为稠密索引。
非稠密索引,一组记录建立一个索引项，这种索引表称之为非稠密索引。
ISAM文件和 VSAM文件
索引顺序存取方法 ISAM(Indexed Seguential Access Method)
是一种专为磁盘存取设计的文件组织方式。
磁盘是以盘组、柱面和磁道三级地址存取的设备。则磁盘上的数据文件建立盘组、柱面和磁道三级索引。
柱面索引,由关键字和指针组成。前者表示该柱面中最末一个记录的关键字（最大关键字），后者指示该柱面上磁道索引位置。当柱面索引较大时，可建立柱面索引的索引
（主索引）。
磁道索引,由基本索引项和溢出索引项组成。每一部分都包括关键字和指针两项，前者表示该磁道中最末一个记录的关键字（最大关键字），后者指示该磁道中第一个记录的位置。
（参见,P314-图 128、图 129）
ISAM文件和 VSAM文件
ISAM文件的检索主索引 柱面索引 磁道索引
ISAM文件的插入
（每个柱面的基本区是顺序存储结构，而溢出区是链表结构。）
溢出区,（ 1）集中存放：整个文件设一个大的单一的溢出区。
（ 2）分散存放：每个柱面设一个溢出区。
（ 3）集中与分散：先移至每个柱面各自的溢出区，待满后再使用公共溢出区。
ISAM文件的删除只需找到待删除的记录，在其存储位置上作删除标志即可。
ISAM文件和 VSAM文件
虚拟存储存取方法 VSAM（ Virtual Storage Access Method）
它利用了操作系统的虚拟存储器的功能，给用户提供方便。对用户来说，文件只有控制区间和控制区域等逻辑存储单位，而与外存储器中的柱面、磁道等具体存储单位没有关系。
VSAM文件结构,它由索引集、顺序集和数据集三部分组成。
（参见,P316-图 12.11）
控制区间,数据集中的一个结点称为控制区间。
（每个控制区间可视为一个逻辑磁道）
控制区域,顺序集中一个结点连同其对应的所有控制区间形成一个整体，称做控制区域。
（每个控制区域可视为一个逻辑柱面）
ISAM文件和 VSAM文件
VSAM文件的插入无溢出区，解决的办法,
（ 1）每个控制区间不填满记录，在最末一个记录和控制信息之间留有空隙。
（ 2）在每个控制区域中有一些完全空的控制区间，并在顺序集的索引中指明这些空区间。
VSAM文件的删除删除记录时，需将同一控制区间中较删除记录关键字大的记录向前移动，把空间留给以后插入的新记录。
VSAM文件的优点,动态地分配和释放存储，不需要对文件进行重组，并能较快地对插入的记录进行查找。
散列文件
散列文件,是指利用哈希法进行组织的文件。即根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。
桶,在散列文件中，将若干个记录组成一个存储单位，这个存储单位称做桶。
基桶,将 m个同义词的记录可以存放在同一地址的桶中，这个桶称为基桶。
溢出桶,将第 m+1个同义词存放到另一个桶中，此桶称为溢出桶。
（例：参见,P318-图 12.13）
特点,优点：文件随机存放，记录不需要进行排序；插入、删除方便，存取速度快，不需要索引区，节省存储空间。
缺点：不能进行顺序查询，只能按关键字随机存取。
多关键字文件
多关键字文件在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。（例：高考成绩查询）
多重表文件记录按主关键字的顺序构成一个串联文件，并建立主关键字的索引（主索引），主索引为非稠密索引；对每一个次关键字建立次关键字索引（次索引），次索引为稠密索引，所有具有同一次关键字的记录构成一个链表。
（参见,P320-图 12.15）
特点：易于编程，易于修改，插入记录容易，但删除记录繁琐。
多关键字文件
倒排文件,与多重表文件的区别在于次关键字索引的结构不同。（通常，具有相同次关键字的记录之间不设指针相连，而在次关键字索引（倒排表）的该次关键字的一项中存放这些记录的物理记录号。）
（参见,P320-图 12.16）
倒排文件的特点优点：检索记录较快。
缺点：维护困难。
B-树 (参见,P238)
B-树是一种平衡的多路查找树。
一棵 m阶的 B树，或为空树，或为满足下列特性的 m叉树,
(1)树中每个结点至多有 m棵子树；
(2)若根结点不是叶子结点，只至少有两棵子树；
(3)除根之外的所有非终端结点至少有 m/2棵子树；
(4)所有非终端结点中包含下列信息数据
（ n,A0,K1,A1,K2,A2,…,K n,An）
(5)所有的叶子结点都出现在同一层次上，相当于失败点（查找不到）。
(B-树的查找、插入和删除参见 P242)
B+树 (参见,P246)
B+树是 B-树的一种变形，其区别在于：
(1)有 m棵子树的结点中含有 m个关键字；
(2)所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小从小到大顺序连接；
(3)所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大（或最小）关键字。
（在 B+树上进行查找、插入和删除的过程基本上与 B-树类似）
练习题
如图所示的一棵 3阶 B-树，给出分别插入关键字为 2,12,16和 17
的结点之后的结果。
7
3 9,13
1 4,5 8 10,11 14,15
练习题 （参考答案）
插入 2之后：
7
3 9,13
1,2 4,5 8 10,11 14,15
练习题 （参考答案）
插入 12之后：
7,11
3 9 13
1,2 4,5 8 10 12 14,15
练习题 （参考答案）
插入 16之后：
7,11
3 9 13,15
1,2 4,5 8 10 11 14 16
练习题 （参考答案）
插入 17之后：
7,11
3 9 13,15
1,2 4,5 8 10 11 14 16,17
练习题
如图所示的一棵 3阶 B-树，给出分别删除关键字为 50和 53的结点之后的结果。
45
24 53,90
3,12 37 50 61,70 100
练习题 （参考答案）
删除 50之后
45
24 61,90
3,12 37 53 70 100
练习题 （参考答案）
删除 53之后
45
24 90
3,12 37 61,70 100
