admin 管理员组文章数量: 1087139
2024年3月14日发(作者：dedecms模版怎么删除导航)
《数据结构》教案 2022-3-22
if(discrim!=level){
//Min value could be on either side
temp2= Kdfindmin(rtright,discrim,(level+1)%k,k);
if((temp1==Null)||((temp2!=Null)&&
(dkey(temp2->val,discrim)< dkey(temp1->val,discrim))))temp1=temp2;
}//Now,temp1 has the smallest value in children (if any)
if((temp1==Null)||(dkey(rt->val,discrim)
else return(temp1);
}
A(40,45)
x
B(15,70)
y
删除A，取代它的节点应该是识别器输出同为x
的右子树中最小的点D，它不在A的右子树最左边
C(70,10)
D(50,50)
x
G(90,8)
y
E(45,80)
F(80,20)
图1.77 k-d树删除
有关k-d树删除的程序比较复杂，可以在上机实验中讨论。
1.4非线性数据结构--图
在数据结构二元组K=(D,R)定义中，D是有限元素集合，R是定义在D上的有限个关系。
通过限制一个关系r的前趋和后继元素的个数，我们分别得到了线性表和树形结构。如果
不限制r的前趋和后继节点个数，所得结果就是图。图形数据结构是现实世界中广泛存在
的一种非线性数据结构，本节不讨论图论中的内容，主要是研究图形数据结构的计算机描
述（存储）方式，为此，首先叙述它的一些基本概念和术语。
1.4.1图的基本概念
如果V(G)是数据元素的有限集合，E(G)是它的笛卡尔积V×V：
VV{(v,u)v,uV且vu}
的子集，则称图G=(V,E)是一个图。其中，V(G)中的元素称为图G的顶点，E(G)中的元素称
为图G的边。例如图G1的关系如下：
V(G1)={v1,v2,v3,v4}
E(G1)={(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)}
100
《数据结构》教案 2022-3-22
其数据结构如图1.78（a）所示。而图1.78（b）的G2、（c）G3关系分别是：
V(G2)={v1,v2,v3,v4,v5,v6,v7}
E(G2)={(v1,v2),(v1,v3),(v2,v4),(v2,v5),(v3,v6),(v3,v7)}
V(G3)={v1,v2,v3}
E(G4)={
v1
v1
(v1,v3)
v3
v1
(v1,v2)
v2
(v1,v2)
v2
(v1,v3)
v3
(v3,v7)
v7
v2
(v2,v3)
(v2,v4)
v4
(a)G1的结构
(v2,v4)
(v1,v4)
v4
(v2,v5)
(v3,v6)
v5v6
(b)G2的结构
v3
(c)G3的结构
图1.78 若干图形结构
如果图中一条边的节点偶对是无序的，则称此图是无向图，在无向图中，(v1,v2)和
(v2,v1)代表同一条边。
如果图中一条边的节点偶对是有序的，则称此图是有向图，在有向图中，
一条边，v1是始点，v2是终点。而
定我们不考虑节点到其自身的边，即如果(v1,v2)或者
允许一条边在图中重复出现。
现在讨论完全有向图和完全无向图。假定一个无向图G中，边的集合E包含了V的笛
卡尔积V×V所有分项，则称此图是完全无向图。即图G中任何两个顶点之间都有一条边相
连。显然，图1.78（a）是4个节点的完全无向图。在一个有n个顶点的无向图中，因为任
何一顶点到其余n-1个顶点之间都有n-1条边相连，容易知道，第一个顶点v1有n-1条边
与其余n-1个顶点相连，第二个顶点v2有n-2条边和其余n-2个顶点相连，因为v1已经
连接了v2，它们之间无需连接（因为(v1,v2)和(v2,v1)代表同一条边）。依此类推，最后一
个顶点需要连接其它顶点的边数是零。即：
(ni)
2
n(n1)
i1
n
1
所以，一个具有n个顶点的无向图其边数小于等于
时，它是完全无向图。
11
n(n1)
，当边数等于
n(n1)
22
假定一个有向图G中，任何两个顶点之间都有方向相反的两条边相连，则称此图是完
全有向图。显然，完全有向图的边数等于
n(n1)
。
若(v1,v2)∈E，我们说v1和v2相邻，而边(v1,v2)则是与顶点v1和v2相关联的边。
若
101
《数据结构》教案 2022-3-22
是与顶点v1和v2相关联的。
与树的度的概念类似，一个顶点的度就是与该顶点相关联的边的数目。若是一个有向
图，则把以顶点v为终点的边的数目称之为v的入度，把以顶点v为始点的边的数目称之
为v的出度。
图1.78（c）v2的出度为2，入度为1，所以v2的度为3。有向图中出度为0的顶点称
为叶子。入度为0的顶点称为根。
若无向图G有n个顶点，t条边，设d
i
为顶点v
i
的度数，因为一条边连接两个顶点，
则：
1
n
t
d
i
2
i1
图G=（V,E），G’=（V’,E’），若V’∈V，E’∈E，并且E’中的边所关联的顶点全部在V’中，
则称图G’是图G的子图。图1.79是图1.78（a）的几个子图。
v1
v1
v1
(v1,v2)
v2
(a)(b)
(v1,v3)
v3
v2
(v2,v3)
v4
(c)
v3
(v1,v4)
图1.79 图G1的几个子图
图G=（V,E）中，如果存在顶点序列v
p
，v
i1
，v
i2
，…，v
in
，v
g
，使得（v
p
,v
i1
），（v
i1
,v
i2
），…，
（v
in
,v
g
）都在E中（若是有向图，则使得 p ,v i1 >， i1 ,v i2 >，…， in ,v g >都在E中），则 称从顶点v p 到v g 之间存在一条路经，路径长度是这条路径上的边数。如果一条路径上的顶 点除v p 和v g 可以相同之外，其余顶点均不相同，则称此路径是一条简单路径。 一般把路径（v 1 ,v 2 ），（v 2 ,v 3 ），（v 3 ,v 4 ）简单写成v 1 ，v 2 ，v 3 ，v 4 。图1.78（a）的G1中， v1，v2，v3和v1，v3，v4，v1，v3是两条路经，前者是简单路径，后者不是。图1.78（c） 的G3中，v1，v2，v3是一条简单的有向路径，而v1，v2，v3，v2不是路径（没有< v3,v2> 连接边）。 v p =v g 的简单路径称为环。一个有向图中，若存在一个顶点v 0 ，从它出发有路径可以达 到图中任何一个顶点，则称此有向图有根，根为v 0 。 现在讨论有向图和无向图的连通概念。对无向图G=(V,E)来说，如果从顶点v i 到v j 有 一条路经，我们称v j 和v j 是连通的。若G中任意两个顶点v i 和v j 都是连通的（i≠j），则 称无向图G是连通的。 图1.78的（a）和（b）是连通的。不连通的图如图1.80的G4所示。一个无向图的连 通分支定义为该图的最大连通子图。 102 《数据结构》教案 2022-3-22 v1v5 (v1,v2) v2 (v1,v3) v3v6 (v5,v6) (v6,v7) v7 (v2,v4) v4 (v1,v4) v8 图G4的结构 (v7,v8) 图1.80 不连通的无向图G4存在两个连通分支 对有向图G=(V,E)来说，若G中任意两个顶点v i 和v j （i≠j）都有一条从v i 到v j 的有 向路径，且也存在从v j 和v i 的有向路径，则称有向图G是强连通的。图1.78（c）的G3不 是强连通的，因为从v1到v3不存在一条路经。 一个有向图的强连通分支定义为此图的强连通最大子图。图1.81给出了图1.78（c） G3的两个强连通分支。 v1 v3 v1 8 3v2 11 4 6 v3 2 带权的图G5 v4 10 v5 v2 G3的强连通分支 5 图1.81 G3的强连通分支 图1.82网络 如果给图的每一条边增加一个数值作为权，我们称为带权的图，带权的连通图称为网 络，如图1.82所示。 1.4.2图形结构的物理存储方式 图形结构的物理存储方式有三种，我们分别叙述。 1.4.2.1相邻矩阵 图G的相邻矩阵是表示G中顶点i和顶点j之间相邻关系的矩阵。若顶点i和顶点j 相邻，则矩阵元素a ij =1，否则为0。具体地说，设G有n个顶点，则相邻矩阵是如下定义 的n×n矩阵。 1,若（v,v）或v,v是图G的边 ijij A[i,j] 0,若（v,v）或v,v不是图G的边 ijij 图1.78的G1和G3的相邻矩阵A1和A3分别表示在下面。容易知道，带权图（网络） 的相邻矩阵仅需将矩阵中的1代换为权值。图1.82所示网络的相邻矩阵A5也在下面给出。 103 《数据结构》教案 2022-3-22 0 1 A1 1 1 0 111 3 010 011 ， A3101 ， A5 5 101 000 8 110 0 3 0 6 4 11 5 6 0 2 0 0 411 20 010 100 8 设图G有n个顶点，我们用相邻矩阵存储图型结构的边的关系，用长度为n的顺序表 存储图的n个顶点数据，或者是指向顶点数据的指针。对于有向图，相邻矩阵需要n个单 元，对于无向图，因为相邻矩阵是对称的，只需要存储它的下三角部分。 显然，无向图的相邻矩阵第i行元素值之和就是第i个顶点的度（和顶点i相连的边 2 数）。对于有向图，相邻矩阵第i行元素值之和是第i个顶点的出度（以顶点i为始点的边 数），第i列元素值之和就是第i个顶点的入度（到顶点i的边数）。 此外，G中顶点i和顶点j之间如果存在一条长度为m的路径，则相邻矩阵A的A的 m 第i行第j列元素为0。 1.4.2.2图的邻接表示 在十字链表中我们学习过稀疏矩阵的链式存储方法，图的邻接表示与其类似。对于图G 中的某一个顶点v i ，用一个链表来记录与其相邻的所有顶点，也就是所有的边，我们称之 为边表。然后用一个顺序表存储顶点v i （i=1，2，…，n）的数据以及指向v i 的边表的指针。 比如，图1.83是图1.82的G5的邻接表示（没有考虑权）。 v1 v2 v3 v4 v5 2 1 1 1 2 3 3 2 2 4Null 4 4 4 3 Null 5Null Null 5Null 图1.83 G5的邻接表示 顶点v i 的边表的每个节点对应一个与v i 相连的边，节点数据域是与v i 相邻顶点的序号， 指针域则指向下一个与v i 相邻的顶点。用邻接法表示无向图，则每条边在它两个端点的边 表中各占一个节点。程序1.29给出了邻接法图数据输入的实例。 对于有向图，出边表和入边表分开保存，比如图1.84是图1.78（c）G3的邻接表示。 v1 v2 v3 Null G3的出边表结构 2 1 Null 3 Null v1 v2 v3 2 1 3 G3的入边表结构 Null Null Null 图1.84 有向图G3的邻接表示 数据结构定义如下： struct node{ 104 《数据结构》教案 2022-3-22 bool mark; char letter; //访问标志 //顶点数据域 //指向边表的指针 struct edge *out; }; struct edge{ bool mark; int no; //访问标志 //顶点编号 struct edge *link; //指向边表的后继 }; 程序1.29 图的邻接表示 void graphinput(struct node *nodelist,int n) { int i,j,m; struct edge *q,*p; for(i=0;i //以下输入顶点数据 printf("输入顶点%d编号n",i+1); cin>>nodelist[i].letter; nodelist[i].mark=false; //设置访问标志初始为false nodelist[i].out=Null; } //边表初始置空 for(i=0;i //以下设置顶点的边表 cout<<"输入第"< cin>>m; if(m){ nodelist[i].out=(struct edge *)malloc(sizeof(struct edge)); cout<<"输入第"< scanf("%d",&(nodelist[i].out->no)); //与第i个顶点相邻的图顶点编号 nodelist[i].out->link=Null; nodelist[i].out->mark=false; p=nodelist[i].out; for(j=1;j q=(struct edge *)malloc(sizeof(struct edge)); cout<<"输入第"< scanf("%d",&(q->no)); 105 《数据结构》教案 2022-3-22 } } } q->link=Null; q->mark=false; p->link=q; p=q; } 1.4.2.3图的多重邻接表示 图的邻接表用数组存储顶点信息，因而每条边会分别出现在其相邻两个顶点的边表中。 如果我们把图的所有顶点信息用一个链表来描述（图节点），每个图节点指向一个边表（表 节点），表节点存储的不是顶点的序号，而是指向边（或者说弧）另一端相邻顶点的指针， 我们称之为图的多重链表表示。我们分别为图和其边表设计了动态的数据结构如下： struct node{ bool mark; char letter; //访问标志 //顶点数据域 struct node *nextnode; //指向图顶点集合中下一个元素的指针 struct arc *out; }; //指向该顶点边表的指针 struct arc{ bool mark; //访问标志 //指向该弧（边）的另一端顶点的指针 struct node *link; struct arc *nextarc; // 指向与该顶点连接的其余弧（边）的指针 }; 图节点结构由顶点数据域、指向顶点集合中下一个元素的指针、以及指向顶点边表节 点的指针构成。 设顶点v i 有k条边与顶点v j1 ，v j2 ，…，v jk 相连，顶点v i 的边表节点结构由指向顶点 v jn （n=1，2，…，k）的指针、以及指向边表后继节点的指针构成。图1.85（a）G6是一个 有向图，图1.85（b）是它的多重链表节点结构。图1.86是图1.85（a）G6的多重链表表 示。 106 《数据结构》教案 2022-3-22 a b de f out info nextnode 图节点 c (a)有向图G6 g (b)节点结构 图1.85 有向图G6及其多重链表节点结构 nextarclink 边表（弧）节点 g a b cde f 图1.85 有向图G6的多重链表表示 1.4.3图形结构的遍历 给出一个图G和其中任意一个顶点v 0 ，由v 0 开始访问G中的每一个顶点一次且仅一次 的操作称之为图的遍历。由于子图中可能存在循环回路，所以树的遍历算法不能简单的应 用于图。为防止程序进入死循环，我们必须对每一个访问过的顶点做标记，避免重复访问。 图的遍历方式有深度优先和广度优先两种方式，分别对应着栈和队两种数据结构运用。 深度优先(depth-first search:DFS)：访问顶点v 0 ，然后选择一个v 0 邻接到的，且未 被访问的顶点v i ，再从v i 出发按深度优先访问其余邻接。当遇见一个所有邻接顶点都被访 问过的顶点U的时候，回到已访问序列中最后一个有未被访问过的邻接的顶点W，再从W 出发按深度优先遍历图。当图中任何一个已被访问过的顶点都没有未被访问的邻接顶点时， 遍历结束。 宽度优先(breadth-first search:BFS)：访问顶点v 0 ，然后访问v 0 邻接到的所有未被 访问的顶点v 1 ，v 2 ，v 3 ，…，v t 。然后在依次访问v 1 ，v 2 ，v 3 ，…，v t 。所邻接的、未被访问 的顶点，继续这一过程，直至访问全部顶点。宽度遍历非常类似于树的层次遍历，使用的 是队列这种数据结构。 按深度优先遍历图1.85（a）所得顶点序列是：a，b，c，f，d，e，g。 按宽度优先遍历图1.85（a）所得顶点序列是：a，b，d，e，f，c，g。 若图是连通的无向图或者是强连通的有向图，则从任何一个顶点出发都能遍历图的所 有的顶点，所得结果如图1.87的（a）和（b），结构像一棵树。若图是有根的有向图，则 107 《数据结构》教案 2022-3-22 从根出发，可以系统的遍历所有顶点。图的所有顶点、加上遍历过程中访问的边所构成的 子图，我们称之为图的生成树。比如图1.87的（a）和（b）。显然，根据访问起点的不同， 生成树不同。 a a b de f b de f c (a)深度遍历生成树 g c g (b)宽度遍历生成树 图1.87有向图G6的遍历 对于非连通无向图和非强连通有向图，从任意顶点出发不一定能遍历图的所有顶点。 而只能得到以该顶点为根的连通分支的生成树。因此，继续图的遍历过程需要从一个没有 访问过的顶点开始，所得的也是那个顶点的连通分支的生成树，于是，图的遍历结果就是 一个生成树的森林。 程序1.30是采用邻接存储方式的图深度优先遍历c语言函数示例。程序使用了一个辅 助数组next[]存储每一个顶点的下一个要检查的边。每达到一条未检查过的边，程序沿着 边节点指示的顶点序号，按深度优先搜寻边下降路径上的顶点，并将沿途顶点的序号入栈。 此时有两种情况： ① next[]空，深度方向上没有后继，则弹出栈顶，将搜索路径上最近入栈的顶点序 号取出，检查它是否有尚未搜索的边，有则沿该边进行深度优先搜寻，否则更换 边。 ② 该顶点已经被标记，也需要更换新的边。 程序1.30 图的深度优先遍历（邻接表存储结构） void DFS(struct node *nodelist,int n) { int i,k,top=-1,p; bool notfinished; int stack[size]; struct edge *next[size]; //next[i]是每个顶点边表要检查的下一条边 for(i=0;i //next[i]初始化指向各顶点边表第一条边 for(k=0;k //搜索顶点集合中未被访问的顶点k，并从此出发遍历该顶点生成子树 if(nodelist[k].mark==false){ //此顶点未访问 i=k; printf("%c,",nodelist[i].letter); //访问此顶点 nodelist[i].mark=true; //该顶点已访问标记 108 《数据结构》教案 2022-3-22 } } notfinished=true; while(notfinished){ } //从此出发遍历该顶点的生成子树 while(next[i]==Null){ //如果边表空则可以回朔顶点 if(top==-1){ //若栈空则该顶点生成子树遍历结束跳出循环 notfinished=false; printf("n"); break; } top=pop(stack,&i,top); //否则深度搜索路径上的一个顶点出栈 } if(notfinished){ //检查与第i个顶点关联的一条尚未搜索的 边 } p=next[i]->no; //指向边的另一端邻接顶点p p-=1; //因为顶点编号从1开始而数组下标从0开始 if(nodelist[p].mark==false){ //顺此顶点的深度方向遍历 top=push(stack,i,top); //当前顶点的前趋进栈 next[i]->mark=true; //前趋边访问过标记 printf("%c,",nodelist[p].letter); //访问此顶点 nodelist[p].mark=true; //访问过标记 next[i]=next[i]->link; //指向顶点i边表的下一节点（边） i=p; } //更换到邻接顶点p的边表 else next[i]=next[i]->link; //此顶点已经标记过，更换边 } 图1.85（a）G6的邻接存储结构如图1.88所示，其深度遍历生成树如图1.87（a）所 示，程序1.30的输出是： a,b,c,f,d,e,g, 对下面图1.89（a）有向图G7从顶点a出发做深度优先遍历的结果是： a, b,e, c,d, 109 《数据结构》教案 2022-3-22 1 2 3 4 5 6 7 a b c d e f g Null 2 3 6 3 7 3 Null Null Null Null 456Null 36Null 图1.88 有向图G6的邻接存储结构 ab c 1 2 3 a b c d e a Null 1 2 1 Null 5 4 5 Null Null Null e b c e d (a)有向图G7 4 5 d (b)图G7的邻接表示 图1.89有向图G7从a点出发做深度优先遍历得到的生成树森林 2 3 4 5 Null Null ab c (c)从a出发深度优先 遍历的生成树森林 1 2 3 4 5 c b a d e Null Null 35Null e d (a)以图G7的c为起点的邻接表示 (b)从c出发深度优先遍历的生成树森林 图1.90有向图G7从c点出发做深度优先遍历得到的生成树 图1.90（a）和（b）是对有向图G7从顶点c出发做深度优先遍历的结果，程序1.30 输出是： c,b,a,e,d, 程序1.30对每条边访问一次，对于顶点表从头到尾检查一次，所以花费时间数量级是 O(n+m)。这里的n是顶点数目，m是边数。 1.4.4无向连通图的最小生成树（minimum-cost spanning tree:MST） 既然从不同的顶点出发会有不同的生成树，而n个顶点的生成树有n-1条边，那么， 当边带权的时候（网络），如何寻找一个（网络中）的最小生成树（即树中各边权值之和最 小）？ 图1.91（a）显示了一个城市之间公路网络的例子。各边权值是距离，要把6个城市联 结起来至少需要构筑5条道路，所谓最小生成树就是求距离总和为最短的网络连接。 给定一个无向连通图G，构造最小生成树的prim算法得到的MST是一个包括G的所有 顶点、及其边的子集的图，而这个边的子集满足： 110 《数据结构》教案 2022-3-22 （1） 该子集的所有边的权值之和是图G所有边子集之中最小的； （2） 子集的边能够保证图是连通的。 a 10 21 19 33 e 18 (a)网络图 f 6 14 d 6 e 18 11 b 5 c f 6 e d 6 18 d a 10 11 b 5 cf a 10 11 b 5 c (b)最小生成树1(c)最小生成树2 图1.91城际公路网络与最小生成树 显然，MST的边集中没有回路，否则可以通过去掉回路中某条边而得到更小权值的边集。 因此，n个顶点的MST有n-1条边。 Prim算法很简单：从任意顶点n开始，首先把这个顶点包括进MST中（初始化MST为 n），在与n相关联的边中选出权值为最小的边及其与n相邻的顶点m。把m和边（n,m）加 入到MST中。然后，选出与n或m相关联的边中权值最小的边及相邻顶点k，同样，把k 也加入到MST中。继续这一过程，每一步都通过选出连接当前已经在MST中的某个顶点、 以及另一尚未在MST中顶点的权值为最小的边而扩展MST。直至把所有顶点包括进MST。 若有两个权值相等的边，可以任选其一加入到MST中，因此，MST不唯一。图1.91（b） 和（c）显示了这种情况。 MST的生成过程可以这样理解，反复在图G中选择具有最小权值的边及相邻顶点加入到 MST中，直至所有顶点进入到MST。比如图1.91（b）的生成过程如图1.92所示。 显然，prim算法也是典型的贪心算法步骤，有定理证明prim算法产生的就是最小生成 [1] 树，详细证明过程可以参考文献。 程序1.31是prim算法的c语言实现。程序假设权值始终大于零，图用相邻矩阵表示。 若（v i ,v j ）是边，则矩阵A[i,j]是它的权值。若（v i ,v j ）不是边（即顶点v i 与v j 不相邻）， 则矩阵A[i,j]的值是一个比任何权值都大得多的正数（INFINITY ）。因为是无向图的相邻 矩阵关于对角线对称，且对角线元素为零，所以我们只存储下三角矩阵。 b 5 c 6 b 5 c 6 a 10 b 5 c f 6 d (d) e 18 (e) a 10 11 b 5 c f 6 d a 10 11 b 5 c d (a) (b) d (c) 图1.92 MST的生成过程 用一维数组array存储相邻矩阵的下三角矩阵，显然，下三角矩阵的元素总数是： total i1 n i n(n1) 2 111 《数据结构》教案 2022-3-22 k k1 i1 i(i1) 2 j a i-1,i-1 a i1 a ij a nn a 11 a 21 a 22 a 31 a 32 图1.92 元素下标计算 图1.92给出了矩阵元素下标计算方法。边A[i,j]在array中的位置下标l就是前i-1 行元素的个数加上j： lj k1 i1 k i(i1) j 2 程序在构造MST过程中，如果顶点v i 已经在MST中，则置A[i,i]=1。若边（v i ,v j ）在 MST中，则置A[i,j]=- A[i,j]。也就是说，程序调用结束的时候，相邻矩阵中为负的元素 是MST中的边。 程序1.31 无向连通图的MST void MSTtree(int *array,int n) //数据存储在相邻矩阵array[1]～array[n] { int i,j,k,m,p=0,q=0,min; array[n*(n+1)/2]=1; for(k=2;k<=n;k++){ min=INFINITY; //每次选择新加入MST的边都重新设置权值门限为+∞ //选择符合条件的最小权的边 //从顶点n开始构造MST for(i=1;i<=n;i++){ if(array[i*(i+1)/2]==1){ //如果顶点i已在MST中 for(j=1;j<=n;j++){ if(array[j*(j+1)/2]==0){ //如果顶点j尚未在MST中 if(j //j //直接取边（i,j）的位置 else m=j*(j-1)/2+i; //j>i则边在对角线右侧的上三角中， //对应下三角中是（j,i）的位置 } } } if(array[m] } min=array[m]; p=m;q=j; } 112 《数据结构》教案 2022-3-22 } array[q*(q+1)/2]=1; //将选中的边加入到MST array[p]=-array[p]; //将选中的顶点加入到MST } 图1.91（a）无向连通图的相邻矩阵是下面的矩阵A，程序1.31输出的MST相邻矩阵 是下面的矩阵A’（假设权值均小于INFINITY :99）。 0 1 100 101 9950 9951 ' A , A 9966099661 199999180 19 9999181 21119914331 1.4.5有向图的最短路径 城际公路网络有距离标定。如果两城市之间有路连通，且经中间城市可以有多条道路 到达，那么，距离最短的连通路径是我们的首选。注意，距离最短是指路径上的边带权总 和最小，而不是路径上的边数最少。比如图1.93(a)，顶点a和顶点c之间的最短路径是 abc。 a ab 45 5 20 35 30 3 e 2 b 8 3 (a)最短路经 c 10 20 c 50 15 15 图1.93 d f (b)带权有向图 1.4.5.1单源最短路径（single-source shortest paths） 图1.93（b）的相邻矩阵A（顶点a，b，c，d，e，f对应序号1，2，3，4，5，6）如 下所示。单源最短路径就是从某一顶点v 0 出发，到达图中其它各顶点的最短路径。 501045 0 0155 20015 A 35 200 300 3 0 求最短路径的Dijkstra算法基本思想是：把图中所有顶点分成两组，第一组是相对于 顶点v 0 的路径已经确定为最短路径的那些顶点，第二组中的顶点是尚未确定最短路径的顶 113 《数据结构》教案 2022-3-22 点，每次从第二组中挑选出路径最小的那个顶点，加入到第一组中，直至从顶点v 0 出发可 以达到的所有顶点都包括进第一组内。 算法进行过程中，总是保持从v 0 到第一组各顶点的最短路径长度均不大于从v 0 到第二 组的任何顶点的最短路径长度。因为每个顶点对应一个距离值，第一组内各顶点的距离值 是相对v 0 到该顶点的最短路径长度值，第二组内各顶点的距离值是从v 0 到该顶点的、只允 许经第一组内顶点中间转接的最短路径长度值。算法步骤： ① 初始第一组内只有出发点顶点v 0 ，它的最短路径值相对于自己就是0，第二组内 包括图内其它所有顶点。第二组内各顶点的距离值如下确定：若图中有边 0 ,v k >， 则v k 的距离值就是此边的权值A[i 0 ,j k ]，否则v k 的距离值的初值就是+∞； ② ③ 从第二组中挑选出路径（距离值）最小的那个顶点v m 放入第一组中； 第一组每增加一个顶点v m ，从v 0 经该顶点中间转接达到第二组各顶点的最短路径 就可能发生变化，因此各顶点距离长度值都需要修正。方法是：如果经v m 做中间 转接，使得v 0 到v k 的最短路径比不经过v m 转接，直接到达v k 的距离短，则修改 v k 的距离值为A[i 0 ,j m ]+ A[i m ,j k ]。 ④ 重复步骤，直至图中所有顶点或者都进入第一组，或者仅剩余那些与v 0 没有路经 可达的顶点。 Dijkstra算法仍然是贪心算法的基本思想。要证明算法的正确性，只需证明第二组内 距离值最小的点v m ，就是从第一组的v 0 到第二组v m 的最短路径长度： ① 若v m 到距离值不是从v 0 到v m 的最短路径长度，那么，必有一条从v 0 到经过第二 组内其它顶点到达v m 的路径，其长度比v m 的距离值小。假设该路径经过第二组的 顶点v s ，则： v s 的距离值<从v 0 到v m 的最短路径长度 m 的距离值 这与v m 是第二组内距离值最小的点矛盾，所以，v m 到的距离值就是从v 0 到v m 的最 短路径长度。 ② 假设v x 是第二组中的任意一顶点，若v 0 到v x 的最短路径只包含第一组内的顶点中 转（无需经过v m ），则由距离定义可知其路经长度必然不小于v 0 到v m 的最短路径 长度，若v 0 到v x 的最短路径不仅包含第一组内顶点，而且也经过了第二组的顶点 v y ，因为，v 0 到v y 的路径就是v y 的距离值，它一定大于或等于从v 0 到v m 的最短路 径长度，再考虑到v y 到v x 的路径长度，那么，从v 0 到v x 的最短路径长度必定大 于从v 0 到v m 的最短路径长度，因此，第二组内距离值最小的顶点v m 到，就是从 v 0 到第二组内的最短路径点。 Dijkstra算法的程序实现对有向图采用了相邻矩阵存储。若 i ,v j >是边，则A[i,j]的 值等于边的权。否则设置A[i,j]=INFINITY。初始A的对角线元素为0，处理中用A[i,j]=1 表示第i个顶点进入第一组。辅助数组dist[]的每个元素包括两个字段，length字段的值 114 [2] 《数据结构》教案 2022-3-22 是顶点相对v 0 的距离，pre字段则指示从v 0 到该顶点v k 的路径上前趋顶点的序号。程序结 束时，沿着前趋序号可以回朔到v 0 ，从而确定从v 0 到v k 的最短路径，最短路径长度值存储 在v k 的length字段。程序1.32是单源最短路径算法的C语言实现，而变量k指明了出发 点v 0 。 程序1.32单源最短路径 void shortestPaths(struct node *dist,int *array,int n,int k) { //权值存储在相邻矩阵array[1]～array[n*n]中 } int i,u,temp,min; for(i=1;i<=n;i++){ dist[i].length=array[n*(k-1)+i]; //相邻矩阵第k行元素值就是与k关联的边 if(dist[i].length!=INFINITY)dist[i].pre=k; //(k,i)之间有弧存在，前趋是k else dist[i].pre=0; //(k,i)之间没有弧存在 } //顶点k进入第一组 array[n*(k-1)+k]=1; while(1){ min=INFINITY; u=0; for(i=1;i<=n;i++){ //在第二组中寻找最小距离点 if((array[n*(i-1)+i]==0)&&(dist[i].length } //若v k 和其它点均不相邻程序结束 u=i;min=dist[i].length; } if(u==0)break; array[n*(u-1)+u]=1; //v i 放进第一组 for(i=1;i<=n;i++){ //修改第二组中各点距离 } temp=dist[u].length+array[n*(u-1)+i]; if((array[n*(i-1)+i]==0)&&(dist[i].length>temp)){ } dist[i].length=temp; dist[i].pre=u; } 输入图1.93（b）的相邻矩阵A，指定k=1(即从v 1 开始），程序1.32的disp[]输出是： 115 《数据结构》教案 2022-3-22 (0,1),(45,4),(10,1),(25,3),(45,1),(99,0) 返回的dist[]各元素pri字段值指示我们从v 1 到各顶点的最短路径。比如，想求v 1 至v 4 的最短路径，从disp[4].pre=3可知，最短路径上的v 4 前趋是v 3 ，而disp[3].pri=1 说明v 3 的前趋就是v 1 ，即v 1 至v 4 的最短路径是v 1 ，v 3 ，v 4 ，最短路径值是disp[4].length=25。 Dijkstra算法有两重循环。主循环中处理顶点v k 到图中其余n-1个顶点的最短距离， 2 内循环中寻找第二组内具有最小距离的点，也是扫描n个顶点，因此，其计算效率是n数 量级的。 1.4.5.2每对顶点间最短路经（all-pairs shortest paths） 实际运用中，我们不但要知道从某一顶点到网络内其余顶点的最短路径，往往还需要知 道网络内每两个顶点之间的最短路径。一种方法是通过反复n次调用程序1.32可以简单的 解决这个问题。另一种方法是如下所述，概念上更为清晰。 设有向图用相邻矩阵描述。我们这样定义相邻矩阵的阶k：k阶相邻矩阵A[i,j]的元素 值等于从顶点i到顶点j之间的最短路径上，允许经过中间顶点数目（边数）不大于k的 最短路径长度。而n阶相邻矩阵A[i,j]的元素值，等于从顶点i到顶点j之间的最短路径 上经过中间顶点数目不大于n的最短路径长度，即从顶点v i 开始，允许经过图中所有n个 顶点达到v j 的最短路径。 我们定义A[i,j]=A[i,j]，由A[i,j]递推求得A[i,j]的过程，就是允许越来越多的 顶点作为v i 到v j 路径上的中间顶点的过程，直至包括图内所有的顶点都可以作为中间顶点， 从而求得v i 到v j 的最短路径。 如果A[i,j]已知，递推求A[i,j]就是在A[i,j]上增加顶点v k 作为中间点，这有两 种情况： ① v i 到v j 的最短路径上经过v k ，即A[i,j] k 的必要）， A[i,j]由两段构成，一段是从v i 开始经过k-1个顶点达到v k 的最短路径A[i,k]， 另一段是从v k 开始经过k-1个顶点达到v j 的最短路径A[k,j]，因此，A[i,j] 是它们之和： A k [i,j]A k1 [i,k]A k1 [k,j] 。 ② 第二种情况是v i 到v j 的最短路径上没有经过v k ，即A[i,j]=A[i,j]。 0n kk-1 k-1k kk-1 kk-1 k-1kk-1 0k-1k n k 程序1.33是算法的c语言实现。初值A[i,j]就是相邻矩阵，结束时A[i,j]是每对顶 点之间的最短路径长度。辅助矩阵path[i,j]是从v i 开始经过k-1个顶点达到v j 的最短路 径上v j 的前趋顶点序号。我们可以由path[i,j] 的元素值回朔最短路径。 程序1.33每对顶点间最短路经 void AllshortestPaths(int *path,int *array,int n) { int i,j,k,temp; 116 《数据结构》教案 2022-3-22 } for(i=1;i<=n;i++) for(j=1;j<=n;j++){ if(array[n*(i-1)+j]!=INFINITY)path[n*(i-1)+j]=i; //初始前趋 else path[n*(i-1)+j]=0; //没有前趋 } //递推更新最短路径矩阵 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++){ temp=array[n*(i-1)+k]+array[n*(k-1)+j]; //两段最短路径之和 if(temp } array[n*(i-1)+j]=temp; //取新的最短路径 path[n*(i-1)+j]=path[n*(k-1)+j]; //(i,j)的前驱是(k,j) } v1 6 11 3 v3 (a)带权有向图 4 v2 2 0411 A 602 30 (b)相邻矩阵 图1.94 图1.94（a）和（b）分别给出了一个带权有向图和其相邻矩阵。由程序1.33得到的每 对顶点间最短路径矩阵A和辅助矩阵path如下： n 046 112 , path 322 A 502 370 313 由path[i,j] 的元素值可以回朔最短路径，比如，由A[2,1]可知v 2 到v 1 的最短路径 n 长度是5，由path[2,1]=3可知v 2 到v 1 最短路径上，v 1 的前趋是v 3 ，由path[2,3]=2可知 v 3 的前驱是v 2 。 显然，程序1.33的求解效率是n数量级的。 3 1.4.6拓扑排序 拓扑排序是对一个拓扑结构上存在部分有序的元素进行分类的过程。 比如如下情形是 部分有序： （1） 在字典中，单词是用别的单词来定义的。如果单词u用单词w来定义，记为 wu ， 117 《数据结构》教案 2022-3-22 在字典中对单词进行拓扑分类是说把词汇排列得没有前项引用； （2） 一项工程项目由多个任务子项组成。某些子项必须在其它子任务实施之前完成， 如果子任务w必须在u之前完成，记为 wu ，项目的拓扑分类是说把所有任务子项排列得 在每一个子任务开始的时刻，其前项准备工作已经完成； （3） 在大学课程中，因为课程要依赖它的预备知识，所以某些课程必须在其它课程之 前先修。如果课程w是课程u的先修，记为 wu ，教学计划的拓扑分类是这样排列课程， 使其任何课程不会安排在先修课程之前。 一般说，集合V上的一个部分有序是V的元素之间存在一种关系，记为符号 ，称之 为“先于”。并且，符合先于关系的V中的任何元素必须具有如下性质： （1） （2） （3） 若x y且y z，则x z（传递性质）； 若x y，则不能有y x（反对称性质）； x x不成立（非自反性质）。 [3] 可以用一个有向图描述部分序关系，比如图1.95（a）。从图形结构上看，拓扑排序就 是将存在部分有序的元素排列成线性有序。即将图的顶点排列成一排，使得所有的有向边 箭头都指向右边，如图1.95（b）所示。 前述的性质（1）和性质（2）保证了拓扑图中不会出现回路，这是插入成线性有序的 先决条件。我们如下进行拓扑排序的算法：①寻找一个这样的顶点，它没有先于的元素存 在（拓扑图中至少存在一个满足条件的顶点，否则图中就会存在回路）。②把该顶点放到拓 扑排序结果表的首部，并从集合V中删除该顶点。③剩余的集合中仍然是部分有序的，因 此，重复上述过程，直至集合为空。 b a c e fd j h i g gi a bdfc e hj （a）部分有序的拓扑结构图 （ b）拓扑排序之后的部分线性序 图1.95 图结构选择多重链表形式，节点定义如下： struct leader{ char letter; int count; //顶点标识 //前趋顶点个数 struct leader *next; //指向图顶点集合中下一个元素的指针 struct trail *trail; //指向该顶点边表的指针 }; struct trailer{ 118 《数据结构》教案 2022-3-22 struct node *id; //指向该弧（边）的另一端顶点的指针 struct leader *next; //指向与该顶点连接的其余弧（边）的指针 }; 集合元素（图的顶点）以及次序关系的输入方式是按相邻顶点对的形式输入，比如， 图1.95（a）中的元素及边的关系输入形式是： head letter count next trail a 0 b 1 d 2 f 1 j 2 null h 2 null c 2 e 2 g 0 i 1 null tail id next id next null null nullnull nullnull 图1.96拓扑结构的多重链表存储形式 nullnull 程序1.34是多重表数据输入程序，对于输入的w，如果表中有此顶点，则它返回指向 标识为w的图节点的指针，否则，新增一个图节点t，标识为w并返回指向顶点t的指针。 程序1.35是根据部分序建立多重表的程序。每次输入顶点对 i ,v j >，若拓扑图中已有顶点 v i ，则为它增加一条边，否则新增一个图节点v i 。若拓扑图中已有顶点v j ，让v i 指向v j ， 修改v j 的前趋个数，否则新增一个图节点v j ，让v i 指向v j ，并且设置v j 的前趋个数为一。 程序1.34数据输入 struct leader *insert(struct leader *head,struct leader *tail,char w,int &z) { struct leader *h,*p; h=head; tail->key=w; //监视哨 while(h->key!=w){p=h;h=h->next;} if(h==tail){ //表中无w的元素，插入w h=new(leader); //申请图节点 z++; //图节点总数加一 //标识为w //初始的前趋节点数为0 h->key=w; h->count=0; h->trail=Null; p->next=h; //插入到多重表末端 119 《数据结构》教案 2022-3-22 } h->next=tail; } //返回指向标识为w的顶点的指针 return(h); 程序1.35建立多重表 void link(struct leader *head,struct leader *tail,int &z) { } 建立了部分序的多重链表之后，可以开始拓扑分类。在一个拓扑结构上对部分有序的 char x,&rx=x,y,&ry=y; struct leader *p,*q; struct trail *t; read(rx,ry); while(x!='0'){ //x=0则节点对输入终止 printf("<%c,%c>n",x,y); p=insert(head,tail,x,z); //插入x，返回指向x的指针 q=insert(head,tail,y,z); //插入y，返回指向y的指针 t=new(trail); t->id=q; //申请边节点 //x指向y t->next=p->trail; p->trail=t; (q->count)+=1; read(rx,ry); } //把新边节点插入到x的边表 //y的前趋个数增加一 //继续输入 元素进行分类的过程如下： （1） 在图节点链上寻找前趋为零的节点q，并建立新链leader； （2） 从新链头部开始输出q，并从主链上删除，节点总数减一； （3） 沿q点边表搜索，并将q所有后继的前趋计数值减1(因它们的前趋q被删除)； （4） 若某一点的前趋计数值为变为0，则把它插入新链； （5） 若新链非空，回到步骤②循环，继续输出有部分序的节点。 head null a 0 g 0 tail 图1.97初始的无前趋节点链 120 《数据结构》教案 2022-3-22 图1.97是无前趋节点的新链，因为主链表达节点输入序列关系已经不需要，所以新链 实际上使用了主链来连接无前趋节点，注意它们的边表关系没有改变。程序1.36是多重表 结构的拓扑排序函数。程序首先寻找所有count=0的起点，并将它们插入到主链。然后从 头开始输出主链的节点，每输出一个就将节点总数减一，并沿指向q的后继节点的指针， 搜索q的后继关系。将q每一个后继节点的前趋数减一之后，前趋计数值为变为0，则该后 继节点只有q为前趋，程序也把它插入到主链，应该紧接着q之后输出。 当程序结束时拓扑图中已经没有无前趋的元素，如果还有剩余节点，表明该拓扑结构 不是部分有序的。 程序1.36拓扑排序 void topsort(struct leader *head,struct leader *tail,int &z) { struct trail *t; struct leader *p,*q; p=head;head=Null; while(p!=tail){ q=p; p=p->next; if(q->count==0){ } q->next=head; head=q; } //插入到主链 //寻找表内所有count=0的起点 q=head; while(q){ printf("%c,",q->key); // 输出主链节点 z--; //节点总数减一 //指向取q的后继节点 //指向主链下一个部分序的起点 t=q->trail; q=q->next; while(t){ p=t->id; (p->count)-=1; //q后继节点的前趋数减一 if(p->count==0){ //如果该后继节点只有q为前趋则将其插入主链准备输出 p->next=q; q=p; 121 《数据结构》教案 2022-3-22 } } } //搜索q的其余后继 t=t->next; } //程序结束时拓扑图中已经没有无前趋的元素，如果还有剩余节点，表明该拓扑结构不是部分有序 if(z!=0)cout<<"This set is not partially ordered"< 122 《数据结构》教案 2022-3-22 第二章 检索 检索又叫查找。它是对某一同类型元素集合构成的检索表做某种操作，因此它不是数 据结构，而是与数据结构相关的运算问题。检索的一般含意有： 1·查询特定的元素是否在检索表中。 2·检索一个元素的各种信息（属性）。 3·如果特定的元素不在检索表中则插入此元素到表内。 4·检索到特定的元素后从表中删除此元素。 一般我们把前两种操作的检索称为静态检索，因为它不改变检索表的结构，而把包含后 两种操作的检索称为动态检索，它有可能改变检索表中的元素。检索需要元素具有特定的 标识，即所谓的关键字。 定义：关键字是数据元素中某个数据项的值，如果用它能唯一标识一个元素，则称为 主关键字，若几个元素具有相同的关键字，则称此数据项为次关键字。 检索有成功，也有失败的可能。我们定义它的过程是：检索是根据一个给定值在检索表 中确定一个关键字值等于该值的数据元素的过程。如果检索成功，其给出的结果是元素在 检索表中位置的指针（或元素某些数据项信息），如果检索失败，即表中不存在关键字值等 于给定值的元素，应返回空指针。 2.1 顺序检索 顺序检索的特点：从表头开始对检索表元素逐一比较，用给定值检索关键字。它适应的 存储结构是链式或顺序存储结均可，对表中元素无排序要求。因为顺序检索的思想很简单， 我们直接给出它C语言程序如下： 算法 程序2.1 顺序检索 int search(struct node *p,int n,int key) { } 程序表达了一个重要的技巧，即在数组的第n+1个位置设置了一个监视哨，返回时根据 int i=0; //返回时 i 为n则检索失败，否则为元素在表中地址偏移 *(p+n).key=key; //设置监视哨 while(*(p+i).key !=key)i++; return(i); 123 《数据结构》教案 2022-3-22 i值做检索成功与否的判别。 检索性能分析 定义：为确定元素在检索表中的位置，需和给定值进行比较的 次数 的期望值是检索算 法在检索成功时的平均检索长度ASL。设表长为n，则顺序检索的ASL是： ASL P i C i i1 n 这里，P i 是检索表中第i个元素的概率，且 P1 。上式意为检索表中必有欲检索 i i1 n 的元素存在，实际上检索有成功也有失败，二者必居其一，因此有p+q=1。在考虑检索失败 情况下，我们定义此时的平均检索长度是检索成功时的平均检索长度与检索失败时的平均 检索长度之和。 设C i 是找到表中其关键字与给定值相等的第i个记录时和给定值已进行过比较的关键 字个数。在顺序表中检索到第1个元素需比较1次，检索到第2个元素时需比较2次，即 检索到第i个元素时已比较过的次数是i，并设检索每一元素的概率相等，则有： 1 n ASL i n i1 n1 2 可以直接理解为检索时最好的情况是欲检索元素在表中第一个位置上，一次比较后检 索成功，最坏情况是元素在表的末尾，需n次比较后才确定，两种情况的平均即是我们说 的平均检索长度。当元素不在表中时，我们总是需要比较n＋1次才可以确定，设检索成功 的概率是p，则检索失败的概率是1-p，在设有监视哨的程序算法中，检索失败的时候是比 较了n+1次，所以有： p(n1) (1p)(n1) 2 p (n1)(1) 2 ASL 2.2 对半检索 2.2.1 对半检索与二叉平衡树 对半检索的特点是仅适用于已排好序的检索表，且要求是顺序存储结构。这种方法也 叫二分检索，是在已排好序的检索表中每次取它的中点关键字值比较，形成两个前后子表， 如检索成功则退出，否则根据结果判别下一次检索在哪个子表中进行，重复分割该子表直 124 《数据结构》教案 2022-3-22 至找到要检索的元素或子表长度为零。 算法：设表长为n,表头指针为low,表尾指针为high，key为关键字。 1·若low ≤ high 则： mid=int[(low+high)/2] if(key==*(p+mid).key)检索成功 else if(key<*(p+mid).key)high=mid-1；重复步骤1。 else if(key>*(p+mid).key)low=mid+1；重复步骤1。 这个算法比较简单，读者要注意其中一些判别条件的设置，本教材不直接给出程序。 例2.1已知一有序表T中元素是{5，13，19，21，37，56，64，75，80，88，92}， 图2.1 给出了检索21 的情况。 图2.1对半检索表及关键字为21的检索过程 现在我们分析检索失败的情况。比如检索85，它处于检索表外，3次对半检索之后有 high=8，而low=9，因为high 图2.2检索关键字为85的检索过程 关于性能分析，从判定树来看上面两种情况是如图2.3所示。一旦有序检索表确定， 则判定树确定，不同的给定值的检索过程是判定树上不同的路径表达。检索表中每一元素 125 《数据结构》教案 2022-3-22 都是判定树上不同层次的节点，有着不同的检索长度，最大检索长度是深度h。 h 图2.3对半检索树 如果表内节点数n=2-1，则判定树是满二叉树，显然，层次为1检索长度为1的节点有 1个，层次为2检索长度为2的节点有2个，层次为3检索长度为3的节点有4个，···，层 次为h检索长度为h的节点有2个，设检索任一节点的概率相等，则平均检索长度是： h-1 1 h ASL i2 i1 n i1 不考虑系数 1 ，直接展开上式有： n 012 3 h-2h-1 ASL=1×2+2×2+3×2+4×2+....+(h-1)×2+h×2 用2×<1>式两边有： （1） 2ASL=1×2+2×2+3×2+4×2+....+(h-1)×2+h×2 （2） 用（1）式－（2）式有： －ASL=(1+2 +2+2+2+......+2 再用系数 1 2 3 4 h-1 123 4 h-1h )－h×2 h 1 同乘等式两边得平均检索长度为： n ASLh2 h 2 h 1 1 h h1 21 n 因为n=2-1，所以 h=log 2 (n+1)： h ASL 1 (log 2 n1 1)(n1)1 n n1 log 2 (n1) 1 n h 实际上，表内节点数一般不满足n=2-1条件，则判定树不是满二叉树，因为： 2-1 < n ≤2-1 h-1h 则判定树具有和完全二叉树一样的深度 h log 2 n 1 (注：符号 是取运算结果 的上限整数)，即最大检索长度不超过此值。在检索失败情况下，判定树是一个扩充二叉树 (扩充树的叶子节点是内部节点数加一：n 0 =n 2 +1,则2n 0 +n 1 =n 0 +n 2 +1+n 1 =n 内 +1)，检索失败的 126 《数据结构》教案 2022-3-22 过程就是从根走到了外部节点，其最大检索长度也不超过 h log 2 n 1 。 在非等概率情况下，对半检索的判定树效率未必是最佳的。在只考虑检索成功时，我们 是求以检索概率带权的内部路径长度之和为最小的判定树，称为静态最优检索树，在此不 再讨论。 例2.2链表检索。设单链表有n个节点a 1 ，a 2 ，…，a n ，递增有序，只有检索而无插入与删 除操作，为提高访问第i个元素的效率，对链表每个节点增加一附加指针，使之检索成功 的平均检索次数达到O（log n），要求头指针仍指向a 1 。 问1：如何设置各节点指针。 问2：设n=11，请画出该逻辑结构。 解1：没有插入与删除操作说明不用考虑检索表维护问题，因此本题意是问什么链式存储结 构在一个有序节点序列检索中可以达到相当于对半检索的O（log n）平均检索效率。显然， 我们可以用节点附加的指针做成一个对半检索树，各节点指针分别指向其前后子序列中点 的元素，而头节点a 1 的左指针指向序列中点。 解2：n=11，画出对半检索树逻辑结构如图2.4所示。 a 6 a 1 ->left a 1 head a 2 a 3 a 4 a 7 a 9 a 10 a 5 a 8 a 11 图2.4 n=11的对半检索树 例2.3对半查找。设用顺序存储结构构成的一有序表是{a 1 ，a 2 ，a 3 ，a 4 ，a 5 }，已知各元素 的查找概率相应是{0.1， 0.2， 0.1， 0.4， 0.2}，现用对半查找法，求在查找成功时的 平均查找长度ASL。 解：本题考查对半检索树的概念，是访问节点的概率与寻找该节点所需的比较次数乘积和。 ASL C i P i 20.130.210.120.430.22.3 2.2.2对半检索思想在链式存储结构中的应用---跳跃表 设计跳跃表的目的是为了解决线性表的检索效率与表的长度成线性关系的问题，跳跃表 是基于概率数据结构（probabilistic data structure）确定其节点级数，因而其插入操 作不需要刻意维持平衡，比平衡二叉树和2-3树更容易维护。 我们知道，如果检索表有序并且是顺序存储结构的，采用对半检索则平均检索时间（或 称为时间复杂度）可以达到 O(log 2 n) ，在线性表的链式存储结构中，无论元素是否有序， 其检索效率都是O（n），实际应用中，线性表很多情况下使用链式存储结构。那么，我们如 何在链表中构造出具有对半检索效率的结构形式？ 这就是跳跃表要回答的问题。 127 《数据结构》教案 2022-3-22 跳跃表概念 之所以链表的检索效率为O（n），是因为遍历一个链表的过程需要沿着头节点指针域一 次一个地逐点比较，搜索其后继节点。如图2.5（a）。如果链表有序，那么我们假想给链表 添加一个指针如图2.5（b）所示，于是搜索过程可以跳跃进行，我们称之为一级跳跃表。 搜索时，首先沿着一级指针跳跃，一直到有一个节点的关键码大于检索关键码值，然后 回到该节点前驱的零级指针，再多走一个节点就可以确定检索结果（相等是检索成功，不 等是检索失败），这样可以把检索效率提高一半。 如果我们继续以这种方式增加节点的指针域，如图2.5（c）所示。这是一个有n=8个 节点的跳跃表，其第一个节点和中间节点有 log 2 83 个指针域，分别称之为0级，1级和 2级。第一次检索时候从跳跃表的最高一级指针开始，直接比较跳跃表位于 n 处的 中间节 2 点。也就是说，好象是顺序表的对半检索那样。如果中间节点的关键码大于检索关键码值， 退回到前一个节点，并降低一级指针级数，检索位于 n 的节点，如此，根据比较结果使得 4 跳跃步伐逐级减少，最终可以确定检索结果（相等是检索成功，不等是检索失败），因为跳 跃表的检索过程完全类似于顺序表的对半检索，所以其平均检索时间有可能也是 O(log 2 n) 。 跳跃表节点数据结构中定义了一个指针数组，存储可能的最大级数指针，如图2.5（c） 的节点定义如下： struct node{ int key; struct node *forward[level]; //图2.5（c）的level=2 } 其中，forward[0]存储0级指针，forward[1]存储1级指针，依此类推。在表内按关键 字检索一个节点的过程如下： 程序2.2 跳跃表检索 struct node *search(struct node *head,int key,int level) { int i; struct node *p; p=head; for(i=level;i>=0;i--) while((p->forward[i]!=0)&&(p->forward[i]->key p=p->forward[0]; //回到0级链，当前p或者空或者指向比搜索关键字小的前一个节点 128 《数据结构》教案 2022-3-22 if(p->key==key)return(p); else return(0); } head 0 （a）0级8节点的跳跃表 head a1 5 0 1 （b）1级8节点的跳跃表 head 0 1 2 检索关键码为62的搜索路径 （c）2级8节点的跳跃表 图2.5跳跃表 a1 5 a2 25 a3 30 a4 31 a5 42 a6 58 a7 62 a8 69 Nul a2 25 a3 30 a4 31 a5 42 a6 58 a7 62 a8 69 Nul Nul a1 5 a2 25 a3 30 a4 31 a5 42 a6 58 a7 62 a8 69 Nul Nul Nul updata[i] 比如，在图2.5中检索关键码为62的节点。检索从头节点最高一级（level=2）指针开 始，因为head->forward[2]指向节点a4，所以条件表达式为(p->forward[2]->key 它首先比较a4，因为a4key=31，小于62，while()语句条件成立。表明检索需要继续向 后搜索。 p=p->forward[i]让当前指针p指向a4，而a4forward[2]指向a8，则条件表达式 (p->forward[2]->key 条件不成立，当前指针p在for语句循环中级数减一，是a4->forward[1]，指向a6。whlie() 语句条件表达式（p->forward[1]->key 语句条件，p=p->forward[1]让当前指针p指向a6。 因a6forward[1]=a8，而a8key=69>62，于是退出whlie()语句，当前指针p在for 语句循环中级数继续减一，是a6->forward[0]，指向a7。因为a7key=62，于是while() 中因（p->forward[0]->key 此时，p或者空或者指向比搜索关键字小的前一个节点，我们只需要检验p在0级链上的后 继是否与检索关键字相等（检索成功），否则就是检索失败。即语句： p=p->forward[0]; if(p->key==key)return（p）; 两语句中用a7key=62和62进行比较，检索成功并返回指向a7的指针。我们可以画 129 《数据结构》教案 2022-3-22 出图2.5检索表的二叉检索判定树如图2.6所示。在图2.5中用关键字值62进行检索，检 索过程中走过的节点及对应的级数i序列分别是a4、i=2，a6、i=1，a7、i=0。 a4 a2 a1 a3a5 a6 a7 a8 图2.6 对应图2.5跳跃表的检索判定树 跳跃表性能 图2.5给出的是完全平衡的理想跳跃表情况，其距离是平均划分的，和平衡二叉树一样， 要在表的插入与删除过程维护完全平衡所花费的代价太大，而所谓基于概率数据结构的方 法是说，每插入一个节点为其分配的级别（指针数）是随机的，用随机分布函数给定，其 得到一个指针的概率是50%，有两个指针的概率是25%，以此类推。程序2.3可以得到一个 随机级数分配数： 程序2.3 随机级数产生函数 int randomlevel() { return(rand()%RANGE); } 在函数调用前应该使用初始化随机数发生器函数srand()： srand((unsigned int)time(0)); srand()的头部函数是stdlib.h，而时间函数time()的头部函数是time.h。取模操作 将随机数范围限制在RANGE以内。下面是RANGE=7，一个循环内连续100次调用randomlevel() 所返回的随机函数值在0～7之间的分布关系（由左至右分别是指针的级数0,1,…9），共有 五次循环过程。 16,15,9,14,17,15,14,0,0,0 9,18,17,12,16,16,12,0,0,0 20,12,10,19,20,8,11,0,0,0 17,13,9,9,18,18,16,0,0,0 18,15,11,15,14,10,17,0,0,0 即，获得0级指针的节点占总数的16%，获得1级指针的节点占总数的14%，获得2级 指针的节点占总数的11%，获得3级指针的节点占总数的13%，…，获得7级指针的节点占 总数的14%。这样的随机分布如果是模拟掷骰子倒是不错，因为是分布平均。但显然并不符 合我们的需求。看来我们应该寻找一种更合适的随机函数。 在具有n个节点的平衡跳跃表结构中，其0级链上有 nn 个节点元素，在1级链上有 2 0 2 1 130 《数据结构》教案 2022-3-22 个节点元素，…，其i级链上有 n 个节点元素。所以，构建跳跃表的时候应该尽量逼近这 i 2 1 产生新的指针级数 j 2 种结构。关键是如何确定随机函数分布关系。程序2.4给出了以概率 的方法。其中，RAND_MAX是随机函数所能返回的最大值，MAXlevel是我们为跳跃表设定的 级数上限，它与表节点数n是 log 2 n 的关系。 程序2.4 按指数分布的随机级数产生函数 int randX(int &level) { int i,j,t; t=rand(); for(i=0,j=2;i if(i>level)level=i; //level是跳跃表当前最大级数，每插入一个新节点都应更新 return(i); } 下面是MAXlevel=7，一个循环内连续100次调用randX()所返回的随机函数值在0～7 //返回随机分配给新节点的级数i 之间的分布关系（由左至右分别是指针的级数0,1,…9），也是共有五次循环过程。 44,27,16,5,5,1,1,1,0,0, 53,26,11,3,6,0,0,1,0,0, 54,20,13,6,3,2,0,2,0,0, 47,28,13,6,2,2,1,1,0,0, 48,23,19,6,1,1,1,1,0,0, 显然，它基本满足我们的要求。一旦确定了一个新节点的级别，下一步就是找到其插入 的位置，链接到跳跃表中。我们很关心的事情是有没有这种可能出现，就是level连续返 回多个级别很高的值，比如5或者6，造成跳跃表中许多节点都有多个指针，因为没有跳过 足够多的节点，于是插入和检索性能都比较差，类似于线性表关系。反之，很多级别低的 节点也不好，极端情况是都为零级节点，跳跃表退化成一个链表，其效率也成为O（n）。我 们说，极端性能的跳跃表有可能出现，但是其概率非常低，比如，连续插入10个节点其都 为0级节点的可能性是千分之一左右。 跳跃表优于二叉排序树的另一点是其性能与节点插入顺序无关，随着跳跃表节点数的增 加，其出现最差效率的可能性会以指数方式减少，而达到平均情况 O(log 2 n) 的可能性则迅 速增加。 跳跃表插入过程 插入步骤和检索函数中根据给定的关键字搜索表中节点过程非常类似。假设跳跃表按递 增有序。程序首先从最高级数链对跳跃表进行插入位置的搜索，并在搜索过程中用一辅助 131 《数据结构》教案 2022-3-22 指针数组updata[]纪录在每一级链的搜索路径上所走过的最远一个节点位置，见图2.5(c) 所示，它也就是要插入的新节点在每一级链上的前趋节点。因为每插入一个新节点都有可 能增加跳跃表的指针级数，从而影响到搜索的起点指针级数设置。因此，必须在随机分配 新节点指针级数的同时，更新当前跳跃表的最大级数level。程序2.4是跳跃表插入函数。 程序2.4 跳跃表插入 void insert(struct node *head,int key,int &level) { struct node *p,*updata[MAXlevel]; int i,newlevel; p=head; newlevel=randX(level); for(i=level;i>=0;i--){ while((p->forward[i]!=0)&&(p->forward[i]->key updata[i]=p; } p=new(struct node); p->key=key; //设置新节点 //随机取得新节点的级数同时更新level //updata[i]记录了搜索过程中在各级走过的最大节点位置 for(i=0;i for(i=0;i<=newlevel;i++){ //插入是从最高的newlevel层链直至0层链 p->forward[i]=updata[i]->forward[i]; //插入到分配到的级数链 updata[i]->forward[i]=p; } } 我们为跳跃表设置一个独立头节点，初始化设置函数如程序2.5。对于较小的跳跃表， 最大级数限制MAXlevel取10就足够了。注意，主程序中要对随机函数作初始化设置： srand((unsigned int)time(0)); //随机函数种子 程序2.5 跳跃表初始化设置 struct node *initialization(int &level,int &total) { int i; struct node *head; head=new(struct node); for(i=0;i //head节点的初始设置 head->key=0; 132 《数据结构》教案 2022-3-22 level=0; total=0; //设置跳跃表当前的级数为0 //节点总数为0 return(head); } 2.3 分块检索 分块检索是存储器索引上经常采用的一种方法，效率介于顺序检索与对半检索之间。它 要求检索表分块有序。若以关键码检索，则要求每一块内的关键码是此块内最大或最小的。 因此，块内的关键码排列可以无序，但块与块之间的关键码是有序的。假设按递增有序， 则第一块内所有关键码均小于第二块内的关键码，第二块内所有关键码又均小于第三块内 的关键码，…，等等。 图2.7分块检索 分块检索首先建立一个索引表，把每块中最大的一个关键码按组顺序存放，显然此数组 也是递增有序的。检索时，先用对半或顺序检索方法检索此索引表，确定满足条件的节点 在哪一块中，然后，根据块地址索引找到块首所在的存储位置，再对该检索块内的元素做 顺序检索。 比如图2.7分块检索示意。索引表元素包含了每块中节点的上边界（最大关键码）与块 起始地址对，假设检索关键码是24，首先检索索引表A[1].key<24，继续是A[2].key>24， 确定24在第二块内，按A[2].link=7找到第二块起始地址，逐次比较到B2[5].key=24，检 索成功。分块检索效率取决于分块长度及块数： E(n)E a E b E a 是索引表中确定搜索节点所在块位置的平均检索长度， E b 是在块内检索节点的平均 检索长度。设有n个节点平均分成b块，每块有 s 虑检索成功，则： n 个节点，再设检索概率相等且只考 b 1 b b1 E a i b i1 2 显然 E b s1 ，所以：分块检索的平均检索长度是： 2 133 《数据结构》教案 2022-3-22 bsns 2 E(n)11 22s 当 sn 时分块检索的平均检索长度： E(n)n1n 为最小，当索引表很大的时候可以用对半检索，或者二级索引表结构进一步提高检索效率。 2.4 哈希检索 哈希检索（散列检索）是一类完全不同的检索方法，它的思想是用关键码构造一个散 列函数来生成与确定要插入或待查节点的地址，因此，可以认为它检索时间与表长无关， 只是一个函数的运算过程。 设F是一个包含n个节点的文件空间，R i 是其中一个节点，i=1，2，...，n；K i 是其关 键码，如果关键码K i 与节点地址之间有一种函数关系存在，则可以通过该函数唯一确定的 把关键码值转换为相应节点在文件中的地址： ADDR_R i =H(K i ) 这里，ADDR_R i 是R i 的地址，H(K i )是地址散列函数，也叫哈希函数。所以，一旦选定了 哈希函数，就可以由关键码确定任一节点在文件中的位置，例如一文件有节点{R 1 ，R 2 ，R 3 }， 其关键码是： ABCD，BCDE，CDEF 选关键码第一个字符的ASCII值加上一常数1000，0000H为散列函数： H（K）＝ASCII（K的首字符）＋1000，0000H H（1）＝ASCII（A）＋1000，0000H = 1100，0001H H（2）＝ASCII（B）＋1000，0000H = 1100，0010H H（3）＝ASCII（C）＋1000，0000H = 1100，0011H 把节点按地址存放在内存空间中相应位置就形成了哈希表，用哈希函数构造表的过程， 即通过哈希函数实现由关键码到存储地址的转换过程叫哈希造表或地址散列。以同样的函 数用关键码对哈希表进行节点检索，称为哈希检索。显然，元素的散列存储是一种新的存 储结构，完全不同于链表或者是顺序存储结构。 哈希检索的实质是构造哈希函数，哈希函数的实质是实现关键码到地址的转换，即把关 键码空间映射成地址空间。因为关键码空间远大于哈希表地址空间，所以会产生不同的关 键码映射到同一哈希地址上的现象，我们称为‘地址冲突’。比如上例文件中另有一些节点 R 4 ，R 5 ，R 6 关键码是A1，B1，C1，则用该哈希函数散列后生成的地址如表2.1所示。关键码 ABCD 不等于A1，但经过地址散列后它们具有相同的哈希地址，即‘地址冲突’。我们定义， 具有相同函数值的关键码对该哈希函数来说是同义词，因此我们要求运用哈希检索时有： 134 《数据结构》教案 2022-3-22 由给定关键码集合构造计算简便、且地址散列均匀的哈希函数以减少冲突。 拟定处理冲突的办法。 关键码 ABCD BCDE CDEF A1 B1 C1 表2.1 哈希函数 ASCII(首字符)+常数 ASCII(首字符)+常数 ASCII(首字符)+常数 ASCII(首字符)+常数 ASCII(首字符)+常数 ASCII(首字符)+常数 哈希地址 1100，0001H 1100，0010H 1100，0011H 1100，0001H 1100，0010H 1100，0011H 所谓地址散列均匀是指构造的哈希函数应尽可能的与关键码的所有部分都产生相关，因 而可以最大程度的反映不同关键码的差异，比如前例中的A1、B1、C1，如果我们不仅考虑 只取首位字符的ASCII码，而是取关键码各字母的ASCIIA值的平方和作为哈希函数，就可 以减少冲突。至于设定处理冲突的办法，是因为一般说冲突是不可避免的，我们需要寻求 一种有效处理它的手段。 2.4.1哈希函数 一般说关键码分布于一个相对大的范围而哈希表的大小却是有限的，既是如此，我们也 不能保证根据哈希函数得到的散列地址可以均匀的填满哈希表的每一个位置（槽），一个好 的哈希函数应该让大部分的元素记录可以存储在根据散列地址组织的（存储结构）槽位中， 或者说至少表的一半是满的，而产生的地址冲突可以由处理冲突的方法解决。 哈希函数的选择取决于具体应用条件下的关键码分布状况，如果预先知道其分布概率就 可以设计比较好的哈希函数，否则比较困难。 例2.3 下面这个函数把一个整数散列到表长为16的哈希表中。 int hx(int x){ return(x % 16);} 对于2字节二进制串来说，函数返回值仅由其最低四个比特位决定，分布应该很差，如 二进制串1000 0000 0000 1111（32783），对16取模运算，就是将其右移4位（空出的高 位填零补进）：0000 1000 0000 0000（2048），余数是1111，而二进制串0000 0000 1111 1111 （255）对16取模运算结果是0000 0000 0000 1111，余数也是1111。 例2.4 下面是用于长度限制在10个大写英文字母的字符串哈希函数 int hx(ch x[10]) { } int i,sum; for(sum=0;i=0;i<10;i++)sum+=(int)x[i]; return(sum % M); 该函数用输入字符串10个字符的ASCIIM之和，再取M的模，因为字母的ASCII码值分 135 《数据结构》教案 2022-3-22 布65～90之间，所以10个字符之和在650～900之间，显然，如果表长M在100以内其散 列地址分布的比较好（因为（650%100）=65，（900%100）=0，大致填满表的一半左右），如 果M在1000左右其散列地址会相当的差。下面列出几种常用的哈希函数方法。 直接定址法。 直接取关键码或关键码的某个线性函数值为哈希地址： H i akeyb(a,bconst) 除留余数法。 取关键码被某个不大于哈希表长m的数p除后所得的余数为哈希地址。 H i keymodpp是质数且小于表长M 平方取中法。 取关键码平方后的中间几位为哈希地址。 随机数法。选择一个随机函数，取关键码的随机函数值为它的哈希地址。 实际工作中我们主要考虑如下因素为选择哈希函数的条件： 1·哈希函数的计算复杂性 2·哈希表大小 3·关键码分布情况 4·检索概率 2.4.2闭地址散列 设哈希地址集为0～M-1，冲突是在由关键码得到哈希地址为i，而此地址上已存放有其 它节点元素时发生，处理冲突就是为该关键码的节点寻找另一个空槽（哈希地址），称之为 再探测，探测方法有多种，在再探测过程中仍然可能会遇见槽位不空的情况，于是在探测 处理冲突可能会得到一个哈希地址序列，即多次冲突处理后才有可能找到空地址。 2.4.2.1线性探测法和基本聚集问题 这是基本的地址冲突处理方法，思想很简单，如果通过哈希函数得到基地址i，发现该 槽位不空，那么就由紧邻的地址开始，线性遍历哈希表内所有的地址，并将元素放到所发 现的第一个空槽内，线性探测函数是： H i (H(key)i)modMi1,2,...,M1(2.1) 这里H i 是由线性探测产生的哈希地址序列，H(key)是哈希函数，M是表长，i是增量序 列，称为线性探测再散列。即当哈希函数计算得地址i时如果位置i上已有节点存在，则 继续探测i+1地址是否为空，并且在不空时持续探测下去。 设H(r)是哈希函数，哈希表 Table[M]初始化为NULL，关键码r不能为NULL，基于线性探测再散列方法的插入程序如下： 程序2.6 void hashlnsert(int r) { int i,h0; 136 《数据结构》教案 2022-3-22 int pos=h0=H(r); for(i=1;Table[pos] !=NULL;i++ ){ if(Table[pos])==r)return（-1）; //如果和后一条语句交换顺序则可能在基位置重复插入r； pos=(h0+i) %M; } Table[pos]=r; } 该程序假定在插入或检索过程中，哈希表至少有一个槽位为空，否则会出现无限循环过 程。从哈希表中检索一个元素是否在表内的过程，和插入元素的过程所使用的方法必须一 样，从而可以准确的找到不在基位置上的元素，返回其在哈希表内的位置。若返回值为空 则表示检索失败。 程序2.7 void hashlnsert(int r) { int i,h0; int pos=h0=H(r); for(i=1;(Table[pos] !=key)&&( Table[pos] !=NULL);i++ )pos=(h0+i) %M; if(Table[pos]==key)return(pos); else return(NULL); } 例2.6 线性探测产生的基本聚集问题。哈希表长M=11，哈希函数采用除模取余，且p=M。 处理冲突的策略是线性探测，再探测函数 H i (H(key)i)mod11 , i=1,2,..,M-1，输入 元素序列是{9874，2009，1001，9537，3016，9875}，得到哈希表如下图2.8（a）所示。 0 10010 1001 0 1001 1 1 9537 1 9537 9537 2 3016 2 3016 2 3016 3 4/11 3 3 8/11 41/11 4 41/11 5 1/11 5 5 1/11 6 1/11 6 6 1/11 7 9874 7 9874 7 9874 8 2009 8 2009 8 2009 99875 99875 99875 10 4/11 10 10 1052 （a）初始 （b）每一空槽接收下一 （c）输入1052后每一空槽接 记录的概率分布 收下一记录的概率分布 图2.8 线性探测产生的聚集现象 问（1）表中剩余的每一空槽接收下一个记录的概率； 问（2）继续输入关键字值1052后，表中剩余的每一空槽接收下一个记录的概率； 137 《数据结构》教案 2022-3-22 问（3）根据以上计算，说明随着输入记录的增加，线性探测法处理冲突所产生的问题。 解（1）：理想情况下表中剩余的每一空槽接收下一个记录的概率应该是等分的，但是如图 2.8（a）的初始分布之后，假设新一个输入元素基地址是0，则它经过线性再探测一定会被 分配到空槽3的位置，同样，如果新元素基地址是1或者2，也会被分配到空槽3的位置， 考虑到新元素基地址也可能就是3，所以，空槽3接收新元素的可能性是 4 ，空槽4，5， 11 6因为在其前的槽位是空，所以接收下一个新元素的时候不会产生线性探测问题，其接收概 率为 1 ，而槽位10的情况与槽位3完全相同，它有可能接收前面非空槽位7，8，9的线 11 4 ，因此，表中剩余的每一空槽接收下一个记 11 性探测结果，所以接收新元素的可能性也是 录的概率分布如图2.8（b）所示。 解（2）：继续输入1052，哈希地址是（1052 % 11）=7，经过线性再探测它被放置到槽位 10，此时，由于槽位3前面连续7个槽位全部非空，所有基地址散列到这7个地址上的元 素都有可能被放置到槽位3，于是，经过元素1052的进入及线性再探测过程，槽位3现在 接收下一个新元素的概率已经变成 如图2.8（c）所示。 解（3）：随着输入记录的增加，线性探测法处理冲突所产生的问题是记录在表内的分布出 现聚集倾向，称为基本聚集。随着聚集程度的增加，它将导致新元素进入或者检索过程中 出现很长的探测序列，严重的降低哈希表使用效率。 2.4.2.2删除操作造成检索链的中断问题 如果假设哈希表至少有一个槽位是空的（实际应用中一般不会占满整个哈系表空间）， 8 ，现在表中剩余每一空槽接收下一个记录的概率分布 11 则程序2.7的线性再探测过程是以或者找到一个匹配检索关键码的节点，或者找到一个空 槽为结束标志，这会带来所谓的删除操作造成检索链中断问题。 设已输入节点关键码序列是{K 1 ，K 2 ，…，K i ，K i+1 ，…}，通过哈希函数散列得到哈希表 如图2.9（a）所示。我们进行如下操作： ① 现在输入关键码K j ，设它的基地址H（K j ）=i，因非空而产生冲突，线性再探 测序列从i+1开始遍历哈希表寻找一个空槽，假定地址为i至j-1之间的槽位 均非空，但槽位j空，于是K i 被放到表中的空槽j，如图2.9（b）所示； ② 现在将K i+1 节点关键码删除，并重新设置槽位i+1为空； ③ 对哈希表检索K j 节点关键码，程序首先比较基地址i槽位，非空，再探测地址 j，空槽，于是检索结果是关键码为K j 的节点不在哈希表中。 造成这种情况的原因是由于删除操作造成了检索链中断，程序发现一个空槽后就会判别 138 《数据结构》教案 2022-3-22 已经达到检索链末端。解决的办法是设置一个标记，表明该位置曾经有元素插入过，这个 标记我们称之为墓碑，它的设置使得删除操作既不会影响该单元的继续使用，因为插入操 作的时候，如果是墓碑标记就可以直接覆盖，不会使槽位浪费；同时，墓碑也避免了因删 除操作中断了再探测的检索过程问题，因此，程序2.7的for语句中需要增加一个墓碑判 断条件。 0 K 1 1 K 2 i K i （a） i+1 K i+1 j Null 0 K 1 1 K 2 i K i （b） i+1 K i+1 j K j 探测序列终点 0 K 1 1 K 2 i K i （c） i+1 Null j K j 删除K i+1 后置为空 图2.9删除操作造成检索链中断 删除操作带来的检索链中断问题无论对哪种再探测方法都是同样的。 2.4.2.3随机探测法 解决线性探测造成的基本聚集问题的原则，是让表中每一空槽接收下一记录的概率应尽 可能的相等，方法之一是采用随机探测序列，产生的再探测地址是从哈希表剩余的空槽中 随机选取的，其在探测函数定义如下： H i (H(key)d i )modMi1,2,...,k(2.2) d i 为一组随机数序列。 例2.7 随机探测 顺序输入一组关键字（K 1 ，K 2 ，K 3 ，K 4 ，K 5 ，K 6 ，K 7 ）得到的哈希地址是（2， 25，4，2，1，1，2），假设哈希表长29（表长是一个素数对提高哈希表性能很重要），哈希 函数是除模取余，模长p=M,用随机探测方法确定冲突后地址的函数是： H i (H(key)d i )mod29i1,2,...,k 随机步长序列d i 是23，2，19，14，…，求： （1）画出该组输入下的哈希表，并写出产生冲突后地址探测函数的求值过程。 （2）指出对该哈希表进行哪类操作可能产生问题，说明原因并提出解决办法。 解（1） K 1 =2，K 2 =25，K 3 =4，均为空槽，基地址一次散列成功； K 4 ：a 1 =((2+23)%29)=25，a 2 =((2+2)%29)=4，a 3 =（(2+19)%29）=21，3次探测成功； K 5 =1，空槽，基地址一次散列成功； K 6 ：a 1 =((1+23)%29)=24； K 7 ：a 1 =((2+23)% 29)=25，a 2 =((2+2)%29)=4，a 3 =((2+19)%29)=21，a 4 =((2+14)%29)=16； 139 《数据结构》教案 2022-3-22 所得哈希表是： 1 2 K 5 解（2） K 1 3 4 K 3 …… …… 16 K 7 …… …… 21 K 4 22 23 24 25 K 6 K 2 … 29 如果对哈希表进行删除操作有可能会产生检索链中断问题，因为删除后该单元位置为 空，使在该冲突序列链上的后续记录探查不能进行，比如删除关键字K 4 后，位置21为空， 如果要检索K 7 就不可能，因为在插入K 7 的探测序列中达到过槽位21，由于槽位21不空继 续探测到槽位16（注意，检索时使用的随机探测序列就是插入过程使用的随机序列），当 K 4 删除后由于槽位21变为空，用关键码K 7 检索并用探测序列达到槽位21时，由于其为空 程序会判别是K 7 不在哈希表内，检索失败，因此，删除造成了K 7 检索链中断。 2.4.2.4平方探测法 设哈希函数是 H(key) ， 再探测函数可以写成 P(H,i)f ， 基于平方探测再散列的 f 描述 就 是 P(H,i)i 2 ，即： H i (H(key)i 2 )modMi1,2,...,k(2.3) 显然，可以把线性再探测和随机再探测函数统一描述如下： P(H,i)i ， P(H,i)array[i] 其中数组array[]长度为M-1，存储的是1～M-1的随机序列。 例2.8 平方探测 设哈希表长M=101，输入关键码K 1 ，K 2 的哈希地址是H(K 1 )=30，H(K 2 )=29， 根据式（2.3）分别写出它们探测序列的前4个地址是： K 1 探测序列={30，31，34，39，…} K 2 探测序列={29，30，33，38，…} 显然，具有不同基位置的两个关键码在散列过程中，使用平方探测可以很快分开它们的 探测序列。但是，对于再探测序列来说，我们希望尽可能多的探测到哈希表的每一个槽位， 比如线性探测，它能遍历整个哈希表去搜寻每一个槽位是否为空，但是容易产生聚集，平 方探测显然会遗漏一些槽位，因为它是以跳跃方式进行再探测过程，不过我们可以证明， 它至少能探查到哈希表一半以上的地址。 例2.9 设2次探测序列是 H i (H(key)i 2 )modM,i1,2,...,k ，M是哈希表长（M为质数）， 请证明，2次探测序列至少可以访问到表中的一半地址。 解： 只需证明当探测序列产生地址冲突时，序列下标大于等于 设 ij而d i d j ，根据同余的定义有： M 。 2 i 2 (modM)j 2 (modM) ∴ (ij)modM0 ，或： ij0(modM) 即 (ij) 能被M除尽，因式分解后有： 140 22 2222 《数据结构》教案 2022-3-22 (ij)(ij)0(modM) 因为M为质数且 i，jM ，所以 (ij)0(modM) ，因而： (ij)0(modM) ijcM c为整数，所以 i或j M ，证毕。 2 这里，使用了数论中同余概念与同余定理，描述如下： 同余定义：若a和b为整数，而m为正整数，如果m整除a-b，就说a与b模m同余， 记为： ab(modm) 可以证明 ab(modm) ，当且仅当 a(modm)b(modm) 时成立。根据定义，如果整 数a和b模m同余，则a-b被m整除，显然，a-b-0也被m整除，所以，如果 ab(modm) 成立，则必有 ab0(modm) 成立。 同余定理：令m为正整数，整数a和b模m同余的充分必要条件是存在整数k使得： abkm 2.4.2.5二次聚集问题与双散列探测方法 我们注意到，虽然随机探测和平方探测能解决基本聚集问题，但是它们产生的探测序列 是基位置的函数，如果构造的哈希函数让不同的关键码具有相同的基地址，那么它们就有 相同的探测序列而无法分开。由于哈希函数散列到一个特定基位置导致的地址聚集，我们 称之为二次聚集。 为避免二次聚集我们需要让探测序列是原来关键码值的函数，而不是基位置的函数，一 种简单的处理方法是仍然采用线性探测方法，但是我们设计有两个哈希函数H 1 (key)和 H 2 (key)，它们都以关键码为自变量散列地址，其中，H 1 (key)产生一个0到M-1之间的散列 地址，而H 2 (key) 产生一个1到M-1之间、并且是和M互素的数做为地址补偿，双散列探 测序列是： H i (H 1 (key)iH 2 (key))modMi1,2,...,k(2.4) 例2.10 双散列方法 仍设哈希表长M=101，输入关键码K 1 ，K 2 和K 3 ，它们的哈希地址分别 是H 1 (K 1 )=30，H 1 (K 2 )=28，H 1 (K 3 )=30，H 2 (K 1 )=2，H 2 (K 2 )=5，H 2 (K 3 )=5，根据式（2.4）分别写 出它们探测序列的前4个地址是： K 1 探测序列={30，32，34，36，…} K 2 探测序列={28，33，38，43，…} K 3 探测序列={30，35，40，45，…} 实际上，H 1 (key)和H 2 (key)仍有可能产生相同的探测序列，比如H 1 (K 4 )=28，H 2 (K 4 )=2， 其探测序列与K 1 相同（注意，所有探测序列都是从基位置以后开始的）： 141 《数据结构》教案 2022-3-22 K 4 探测序列={28，30，32，34，36，…} 我们可以进一步的考虑让随机探测与双散列方法结合，让i成为一个随机序列中选取的 随机数。 2.4.3开地址散列 设哈希函数产生的地址集在0～M-1区间，则可以设立指针向量组ARRAY[M]，其每个分 量初值为空，我们将具有哈希地址j上的同义词所包含的关键码节点存储在以向量组第j 个分量为头指针的同一个线性链表内，存储按关键码有序。即，所有产生冲突的元素都被 放到一个链表内，于是，哈希散列过程转换为对链表的操作过程。 例2.11：设输入关键码为（19，14，23，1，68，20，84，27，55，11，10，79），其表长 为13，选择哈希函数是 H i keymod13 。则链地址法解决冲突后得到的哈希表如图2.10 所示。 图2.10链地址法散列得到的哈希表 2.4.4哈希表检索效率 散列存储结构是通过哈希函数运算得到元素散列地址的，但由于冲突的存在使得在检索 过程中它仍然是一个给定值和关键码的比较过程，因此平均检索长度仍是哈希检索的效率 量度，而检索过程中给定值和关键码的比较个数取决于哈希函数质量、处理冲突的方法以 及哈希表的装填因子。 当散列表为空的时候，第一条纪录直接插入到其基位置上，随着存储纪录的不断增加， 把记录插入到基位置上的可能性也越来越小，如果纪录被散列到一个基位置而该槽位已经 不空，则探测序列必须在表内搜索到另一空槽才行，换句话说散列过程增加了比较环节， 142 《数据结构》教案 2022-3-22 可以预计，随着纪录数的增加，越来越多的新纪录有可能被放到远离基位置的空槽内，即 探测序列越来越长而比较次数越来越多，因此，哈希检索效率预期是表填充程度的一个函 数，设表长为M，已存储记录数为N，定义装填因子是 节点个数/哈希表长度。 可以认为，新纪录插入的时候基位置被占用的可能性就是 ，假定可以不考虑任何聚 N ，即，装填因子＝表中填入 M 集问题，而发现基位置和探测序列下一个位置均非空的可能性是： N(N1) M(M1) 此时探测序列长度为2，档探测序列达到i+1时，表明在第i次探测仍然发生冲突，其 可能性是： N(N1)...(Ni1) M(M1)...(Mi1) 当N和M都很大时近似有 ( N i ) ，所以，预期探测次数的期望值是1加上第i次探测产 M 生冲突的概率之和，约为： 1 ( i1 N i 1 ) M1 即一次检索成功的代价与哈希表为空时相同，随着纪录数目的增加，平均检索长度（或 者说插入代价的均值）是装填因子从零到当前 的累积： 1 0 111 dxln() 1x 1 无论从哪方面看，哈希检索效率远高于O（log n），随着 的增加效率会降低，当 足 够小的时候，效率仍然可以小于2，当 接近50%的时候，效率接近2，因此，我们要求哈 希表工作的时候应该在半满状态，太小则表的空间浪费，太大则检索效率降低过多。 例2.12：设输入关键码为（13，29，1，23，44，55，20，84，27，68，11，10，79，14）， 选择装填因子 =0.75，哈希表长M=19，哈希函数采用除模余数法，取模p=17，求： （1） 线性探测产生的哈希表； （2） 随机探测产生的哈希表，随机序列是{3，16，55，44，…}； （3） 平方探测产生的哈希表； 解1：线性探测法，注意线性探测中a j =(H(Key)+i)%M，使用的模是表长度M，而哈希散列 使用的模是p=17。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 68 1 20 55 23 44 27 29 13 11 10 84 79 14 27：a 1 =27%17=10，a 2 =（H(27)+1）%19=11； 143 《数据结构》教案 2022-3-22 11：a 1 =11%17=11，a 2 =（11+1）%19=12，a 3 =（11+2）%19=13，a 4 =(11+3)%19=14； 10：a 1 =10%17=10，a 2 =（10+1）%19=11，a 3 =（10+2）%19=12，a 4 =(10+3)%19=13， a 5 =（10+4）%19=14，a 6 =（10+5）%19=15； 79：a 1 =79%17=11，a 2 =（79+1）%19=12，a 3 =（79+2）%19=13，a 4 =(79+3)%19=14， a 5 =（79+4）%19=15，a 6 =（79+5）%19=16，a 7 =（79+6）%19=17； 14：a 1 =14%17=14，a 2 =（14+1）%19=15，a 3 =（14+2）%19=16，a 4 =(14+3)%19=17， a 5 =（14+4）%19=18； 解2：随机探测法：已知a j =(H(K)+d j )%19，随机步长序列d j 是{3，16，55，44，…}，则： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 68 1 20 55 27 23 10 79 44 29 13 11 84 14 27：a 1 =27%17=10，a 2 =（27+3）%19=13，a 3 =（27+16）%19=5； 11：a 1 =11%17=11； 10：a 1 =10%17=10，a 2 =（10+3）%19=13，a 3 =（10+16）%19=7； 79：a 1 =79%17=11，a 2 =（79+3）%19=6，a 3 =（79+16）%19=0，a 4 =(79+55)%19=1， a 5 =（79+44）%19=9； 14：a 1 =14%17=14，a 2 =（14+3）%19=17； 解3：平方探测法，已知H i =(H(key)+i)%19： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 68 1 20 55 23 79 27 44 11 29 13 10 14 84 2 27：a 1 =27%17=10，a 2 =（27+1）%19=9； 11：a 1 =11%17=11； 10：a 1 =10%17=10，a 2 =（10+1）%19=11，a 3 =（10+4）%19=14； 79：a 1 =79%17=11，a 2 =（79+1）%19=6，a 3 =（79+4）%19=7； 14：a 1 =14%17=14，a 2 =（14+1）%19=15； 例2.13 求成功检索图2.10哈希表的平均检索长度。 解：比较次数为1的节点有6，比较次数为2的节点有4，比较次数为3和4的节点分别只 有1个，所以，平均比较次数是： ASL 16243421 1212 144 《数据结构》教案 2022-3-22 第三章 排序 排序是程序设计中的重要内容，它的功能是按元素的关键码把元素集合排成一个关键 码有序序列。排序有内部排序与外部排序之分，内部指计算机内部存储器，内部排序是元 素待排序列在内存中，当内存不足以容下所有元素集合时，我们把它存储在外部存储器上 进行排序运算，称为外部排序。我们首先给出排序定义，进而再讨论内部排序问题。 设 有n个元素序列{R 1 ，R 2 ，...，R n }，其相应的关键码序列是{K 1 ，K 2 ，...，K n }，需确定1，2，···， n的一种排列P 1 ，P 2 ，···，P n ，使其相应的关键码满足如下非递减（或非递增）关系： K p1 ≤K p2 ≤K p3 ≤，...，≤K pn 即序列按{R p1 ，R p2 ，R p3 ，...，R pn }成关键码有序序列，这种操作的过程称为排序。 当K 1 ，K 2 ，...，K n 是元素主关键码时，即任何不同的元素有不同的关键码，此排序结 果是唯一的，上面的等号不成立。当K 1 ，K 2 ，...，K n 是元素次主关键码时，排序结果不唯 一，此时涉及到排序稳定性问题，我们定义： 设K i =K j ， 1≤i ,j≤n, 且i 不等于j 若排序前R i 在 R j 之前（i pi pj ，即具有相同关键码的元素其在序列中 的相对顺序在排序前后不发生变化，则称此排序方法是稳定的。反之，若排序改变了R pi ， R pj 的相对顺序，则称此排序方法是不稳定的。 在排序过程中主要有两种运算，即关键码的比较运算和元素位置的交换运算，我们以此 衡量排序算法的效率。对于简单的排序算法，其时间复杂度大约是O(n)，对于快速排序算 法其时间复杂度是O(nlog 2 n)数量级的。我们要求必须掌握几种基本方法是线性插入排序， 快速排序，堆排序，归并排序等。下面从最基本的直接插入排序方法开始，进而再研究快 速排序方法的程序设计问题。 2 3.1 交换排序方法 3.1.1直接插入排序 直接插入排序是在插入第i个元素时，假设序列的前i-1个元素R 1 ，R 2 ，...，R i-1 是已 排好序的，我们用K i 与K 1 ，K 2 ，...，K i-1 依次相比较，找出K i 应插入的位置将其插入。原 位置上的元素顺序向后推移一位，存储结构采用顺序存储形式。为了在检索插入位置过程 中避免数组下界溢出，设置了一个监视哨在R[0]处。 算法3.1 1·待排序的n个元素在数组ARRAY[n+1]中，按递增排序。 145 《数据结构》教案 2022-3-22 2·for(i=2；i<=n；i++){ /*第一个元素已经有序*/ array[0]=array[i]； j=i-1； while(array[0].key array[j+1]=array[j]； /*顺序向后移动一位*/ j--； } /*循环中止时j+1指向第i个元素应插入的位置*/ /*监视哨*/ array[j+1]=array[0]； } 程序本身并不复杂，要注意监视哨的作用，当R i 1 时程序也能正常中止循环，把R i 插 入到R 1 位置。一个具体的线性排序例子过程见图3.1所示。 设待排序列是：1，9，4，7，6 j [0]i 9 1 9 4 7 6 9 1 9 4 7 6 [0] j i 4 1 9 4 7 6 4 1 9 9 7 6 i j 4 1 4 9 7 6 [0] j i 7 1 4 9 7 6 7 1 4 9 9 6 j 7 1 4 7 9 6 [0] j i 6 1 4 7 9 6 6 1 4 7 9 9 j 6 1 4 7 7 9 j 6 1 4 6 7 9 [0].key<[4].key，后移：[j+1]=[j]；j--, [0].key<[3].key, 后移：[j+1]=[j]；j--, [0].key<[2].key,不成立,跳出内循环： [j+1]=[0]； [0].key<[3].key，后移：[j+1]=[j]；j--, [0].key<[2].key不成立,跳出内循环： [j+1]=[0]； [0].key<[2].key，后移：[j+1]=[j]；j--, [0].key<[1].key不成立,跳出内循环： [j+1]=[0]； 初始 [0].key<[j].key不成立， 跳出内循环：[j+1]=[0]； i>n，退出 图 3.1线性排序过程 效率分析 直观上看，其两重循环最大都是n，因此其时间复杂度是O(n)。而在一个元素i排序 过程中，要在已排好序的i-1个元素中插入第i个元素其比较次数C i 最多是i次，此时R i 1 被插到第一个元素位置。比较次数最少是1次，此时R i ≥R i-1 ，位置没有移动。因此n次循 146 2 《数据结构》教案 2022-3-22 环的最小比较次数： C min =n-1 最大比较次数： C max i i2 n (n2)(n1) 2 而一次插入搜索过程中，为插入元素i所需移动次数其最大是C i+1 ，最小是2次（包括 array[0]的1次移动）。那么，n个元素排序时，其n-1个元素需2(n-1)次，所以最小移动 次数： M min =2×(n-1) 最大移动次数： M max (i1) i2 n (n1) (n2)(n1) 2 直接插入排序也可以考虑用链表来实现，此时没有元素移动问题，但最大、最小比较 次数一样，另外，直接插入排序的一种改进是二分法插入排序，即检索插入位置时用二分 法进行，其检索效率有所提高，但不能改变元素的移动次数，所以其平均时间复杂度不变， 且只适用于顺序存储结构。 算法判别条件while(array[0].key 素array[0]关键码，则序列顺序后移，找到有序的位置后交换元素；若等于或大于就不发 生交换，因此，具有相同关键码的元素在排序前、后的相对位置不会发生变化，所以它是 一个稳定的排序方法。 3.1.2冒泡排序 冒泡（bubble sort）的意思是每一趟排序将数组内一个具有最小关键码的元素排出到 数组顶部，算法有一个双重循环，其中内循环从数组底部开始比较相邻元素关键码大小， 位居小者向上交换，并在内循环中通过两两交换将最小元素者直接排出到顶部，此时外循 环减一指向数组顶部减一位置，继续内循环过程，将数组内具有次最小关键码的元素排出 至数组顶部减一位置，如此直至循环结束，每次循环长度比前次减一，最终结果是一个递 增排序的数组。图3.2是冒泡排序示意，算法直接见程序3.1。 程序3.1 冒泡排序 void bubsort(struct node *p,int n) 147 《数据结构》教案 2022-3-22 { struct node s; for(int i=0;i int flag=0; fot(int j=n-1;j>i;j--)if(*（p+j）.key<*（p+j-1）.key){ s=*（p+j）; *（p+j）=*（p+j-1）; *（p+j-1）=s; flag=1; } } 42 20 if(flag==0)retrun; } 13 42 20 13 14 42 20 13 14 15 42 20 13 14 15 17 42 20 13 14 15 17 20 13 14 15 17 20 13 14 15 17 20 17 13 28 14 23 15 17 14 28 15 23 17 15 28 23 17 23 28 42 23 28 23 42 28 23 28 42 23 28 图3.2 冒泡排序过程 程序3.1如果没有flag这个标志位，那么即使数组已经有序，程序也会继续双重循环 直至结束为止。另外，我们注意到，如果*（p+j）.key>=*（p+j）.key，相邻元素不发生 交换，所以冒泡排序是一个稳定的排序方法。 冒泡排序是一个双重循环过程，所以其比较次数是： iO(n i1 n 2 ) 其最佳、平均和最差情况基本是相同的。 3.1.3 选择排序 选择排序（selection sort）每次寻找待排序元素中最小的排序码，并与其最终排序 位置上的元素一次交换到位，避免冒泡排序算法有元素在交换过程中不断变位的问题，比 148 《数据结构》教案 2022-3-22 如，首先选择n个元素的最小排序码，将其与排序数组[0]位置的元素交换，然后是选择剩 余n-1个元素的最小排序码，将其与排序数组[1]位置上的元素交换，即，第i次排序过程 是选择剩余n-i个元素的最小排序码，并与排序数组[i]位置的元素交换，它的特点是n个 元素排序最多只有n-1次交换。图3.3是选择排序过程示意，程序3.2是选择排序函数。 程序3.2选择排序 void selsort(struct node *p,int n) { struct node s; for(int i=0;i } 42 20 int lowindex=i; for(int j=n-1;j>i;j--)if(p[j].key s=p[i]; p[i]=p[lowindex]; p[lowindex]=s; } 13 20 13 14 17 42 28 20 13 14 15 42 28 20 13 14 15 17 28 20 13 14 15 17 20 13 14 15 17 20 13 14 15 17 20 17 13 28 14 23 15 17 42 28 14 23 15 28 23 42 23 28 42 23 28 42 23 15 23 17 23 42 图3.3 选择排序过程 选择排序实际上仍然是冒泡排序，程序记住最小排序元素的位置，并一次交换到位， 它的比较次数仍然是 O(n 2 ) 量级，但交换次数最多只有n-1次。如果*（p+j）.key>=* （lowindex）.key，不发生交换，所以选择排序是一个稳定的排序方法。 3.1.4 树型选择排序 直接插入排序的问题在于为了从n个排序码中找出最小的排序码，需要比较n-1次， 然后又从剩下的n-1个排序码中比较n-2次，而事实上，这n-2次比较中有多个排序码已 经在前面比较过大小，只是没有保留结果而已，以至有多次比较重复进行，造成效率下降。 149 《数据结构》教案 2022-3-22 如果我们这样考虑，设n个排序元素为叶子，第一步是将相邻的叶子两两比较，取出较小 n n 排序码者作为子树的根，共有 棵子树，然后将这 棵子树的根再次按相邻顺序两两 2 2 n 比较，取出较小排序码者作为生长一层后的子树根，共有 棵，循环反复直至排出最小 4 排序码成为排序树的树根为止，我们将树根移至另一个数组，并且将叶子数组中最小排序 码标记为无穷大，然后继续从剩余的n-1个叶子中选择次最小排序码，重复上述步骤的过 程，实际上只需要修改从树根到刚刚标记为无穷大的叶子节点这一条路径上的各节点的值， 而不用比较其它的节点，除去第一次以外，等于每次寻找排序码的过程是走过深度为 log 2 n 的二叉树，即只需要比较 log 2 n 次，我们称之为树型选择排序。图3.4是树型排序的过程 前三次循环示意，排序数组为{72，73，71，23，94，16，5，68}，图3.4（a）是构造选择 排序二叉树，图3.4（b）是标记最小排序码后调整得到的次最小排序码，图3.4（c）是又 一次循环过程。 05 23 7223 16 05 05 72 16 23 7223 73 71 16 23 94 (a) 16 23 0568 23 68 1668 7223 94 68 72 73 71 23 (b) 9416 ∞68 72 73 71 23 94 (c) ∞ ∞68 图3.4树型选择排序过程 因为第一次构造这棵二叉树需要比较n-1次才能找到最小的排序码，以后每次在这棵 树上检索最小排序码需要比较 log 2 n ，共有n-1次检索，所以，树型选择排序总的比较次 数为： (n1)(n1)log 2 n 时间复杂度是 O(nlog 2 n) 。 3.2 Shell排序 shell排序也称之为缩小增量法（diminishing increment sort）。它不是根据相邻元 150 《数据结构》教案 2022-3-22 素的大小进行比较和交换，而是把总长度为n的待排序序列以步长 d i n 2 i 进行分割，间隔 为d i 的元素构成一组，组内用直接插入、或者是选择插入法排序。下标i是第i次分组的 间隔，i=1，2，…。随着间隔d i 的不断缩小，组内元素逐步地增多，但因为是在d i-1 的有序 组内基础上新增待排元素，所以比较容易排序。 若n不是2的整数冥，不妨对排序数组长度补零到整数冥的长度为止。 图3.5显示了排序数组长度为8的排序过程。程序3.3是shell排序实现。 7273 712316 94 (a)分隔d i =4 2373 94 (b)组内排序 23 94 (c)分隔d i =2 23 72 (d)组内排序 73 05 68 7216 0571 68 7216 0571 68 0516 716894 73 0516 71236894 72 (e)分隔d i =1，合并成一个组 6872 71 (f)整个数组排序 图3.5 shell排序过程 73 0516 2373 94 程序3.3 Shell排序 void shellsort(struct node *p,int n) { } void inssort2(struct node *p,int n,int incr) { } for(int i=incr;i for(int j=i;(j>=incr)&&(p[j].key swap((p+j),(p+j-incr)); for(int i=n/2;i>2;i/=2) for(int j=0;j inssort2(p,n,1); 151 《数据结构》教案 2022-3-22 3.3 快速排序 对已知的元素序列排序，在一般的排序方法中，一直到最后一个元素排好序之前，所 有元素在文件中（排序表）中的位置都有可能移动。所以，一个元素在文件中的位置是随 着排序过程而不断移动的，造成了不必要的时间浪费。快速排序基于这样一种思想，第i 次排序不是确定排序表中前i-1个元素的相对顺序，而是只确定第i个元素在排序表中的 最终位置。方法是每次排序后形成前后两个子序列，关键码小于或等于该元素关键码的所 有元素均处于它左侧，构成前子序列；关键码大于该元素关键码的所有元素均处于它右侧， 形成后子序列。我们称此元素所处的位置为枢轴，元素为枢轴元素。这样，可以对每一子 序列重复同样的处理过程，形成递归形式，直到每一元素子序列只剩一个元素为止。 此方法关键在于确定序列或子序列的哪一个元素作为枢轴元素，一般选取待排序列的 第一个元素作为枢轴元素，首先给出算法。 算法3.2 设有序列{R[s]，R[s+1]，...，R[t]} 1·设置指针i=s，j=t，R[s].key为待排元素关键码k 1 ，指针p=&R[s]； 2·执行循环： while(i while((i //递增排序*(p+j)>枢轴k则顺序不变继续搜索 *(p+i)<==>*(p+j) //由尾部起找到一小于枢轴的元素*(p+j),把它交换到前子序列i的位置 while((i //递增排序*(p+i)<枢轴k则顺序不变继续搜索 *(p+i)<==>*(p+j)； //自头部起找到一大于枢轴的元素*(p+i)把它交换到后子序列j的位置 } 3·当i=j时一个元素被排好序，可以递归调用此过程直到全部排序结束。 图3.6给出了一个元素的排序过程示意，如果枢轴元素K 1 选择合适，则每次平分前后 子序列可以得到较高的效率，程序3.3是C语言快速排序的完整程序。 程序3.3 快速排序 void qksort(struct node *p,int l,int t) { int i,j; struct node x; i=l;j=t;x=p[i]; //取序列第一个元素作为枢轴 do{ while((p[j].key>)&&(j>i))j--; //从尾部开始只要没找到小于X的元素就递减循环 if(j>i){ 152 《数据结构》教案 2022-3-22 } p[i]=p[j]; //向前单向交换，j位置空出会在后续循环中被另外元素补上 i++; } //准备开始从头部向尾部搜寻 while((p[i].key<)&&(j>i))i++; if(j>i){ p[j]=p[i]; //向后单向交换，i位置空出会在后续循环中被另外元素补上 j--; } //只要i不等于j一趟排序尚未完成 }while(i!=j); p[i]=x; //找到枢轴，把X放到其在序列的最终位置上，一趟排序完成 i++; j--; if(l //对前子序列0～j元素递归排序 if(i //对后子序列i～n-1元素递归排序 函数在主程序中调用形式为： qksort(p，0，n-1)； k=42 i 42 i 顺序j递减 42 23 23 23 i++ 23 23 23 23 23 23 23 前子序列 74 74 74 74 i 42 i 42 i 42 i 42 i 11 11 j 11 11 11 11 11 11 11 11 j 42 i j 42 65 65 65 65 65 65 65 j-- 65 65 65 i 58 58 58 58 58 58 j-- 58 58 58 58 94 94 94 94 94 j-- 94 94 94 94 94 后子序列 36 36 j 42 j 42 j 74 74 74 74 74 74 99 j-- 99 99 99 99 99 99 99 99 99 j 87 87 87 87 87 87 87 87 87 87 n-1 i 逆序交换 36 换搜索方向 36 逆序交换 36 换搜索方向 36 顺序j递减 36 顺序j递减 36 逆序交换 36 i=j确定枢 36 轴位置 0 图3.6快速排序的一个元素排序过程图解 153 《数据结构》教案 2022-3-22 效率 快速算法的效率分析与枢轴元素选取密切相关，最差的情况是每趟排序选取的枢轴元素 在排序后处于将长度为n i 的待排序列分割成一个子序列没有元素而另一个子序列有n i -1个 元素的位置上，于是，下次排序需要比较和交换的次数都是n i -1，如果在总长为n的排序 数组中每次都发生这种情况，则其时间花费是 iO(n i1 n 2 ) ，所以，最差情况下快速排序效 率与冒泡排序相当，如果枢轴是随机选取的，发生这种情况的可能性不大。 快速排序最好的情况是每趟排序选取的枢轴元素在排序后处于将长度为n i 的待排序列 分割成两个长度相等的子序列位置上，下次排序需要比较和交换的次数都是 n i ，如果每趟 2 排序都发生这种情况，则总长为n的排序数组会被分割 log 2 n 次，每次的交换和比较次数 log 2 n 是 i0 n ，这里假设n是2的整数幂，其时间花费是 O(nlog 2 n) 。 2 i 快速排序的平均效率在最好与最差情况之间，假定选取的枢轴元素位置将第i趟排序数 组的长度分割成0，1，2，…，n i -2，n i -1情况的可能性相等，概率为 1 ，则平均效率是： n i 1 T(n)cn n (T(i)T(n1i)) i0 n1 T(0)c,T(1)c 它仍然为 O(nlog 2 n) 数量级。快速排序算法中，我们要注意待排元素K 1 的选取方法不是唯 一的，它对排序效率有很大影响。 3.4 堆排序 快速排序在其枢轴元素每次都选到位于其前后子序列的中点时，相当于每次递归找到一 棵平衡二叉树的根，这时其效率最高。显然，如果我们能找到总是在一棵平衡二叉树进行 排序的方法，就有可能得到比快速排序更高的效率。堆是一棵完全二叉树，堆的特点又是 根为最大值，那么基于最大值堆排序的思想就很简单，将待排序的n个元素组建一个最大 值堆，把根取出放到排序数组的位置[n-1]处，重新对剩下的n-1个元素建堆，再次取出其 根并放置到排序数组的[n-2]位置处，循环直至堆空，堆排序完成。 实际上，排序数组就是堆数组，每次取出的根直接和堆数组的[n-1]位置元素交换，根 被放到堆数组的[n-1]位置，而原来[n-1]位置的元素成为树根，于是，堆数组[0～n-2]的 那些剩余元素在逻辑上仍然保持了完全二叉树的形状，可以继续对这些n-1个剩余元素建 堆，图3.7显示了一个堆排序过程的前四步情况，程序3.3是堆排序程序。 154 《数据结构》教案 2022-3-22 存储位置 逻辑结构 6 73 57 60 42 83 73 6 57886 72 88 48 85 （a）初始 85 88 83 73 42 57 88858372734257 6 4860 6 72 48 73 （b）建堆 60 85 83 42 83 8573 8372 60 4257 6 48 88 6 72 48 73 60 57 （c）尾部n-1节点60和树根88交换后建堆 57 60 42 73 48 83735772 60 42 48 6 85 88 6 72 （d）n-2节点48和树根85交换后建堆 72 737257 6 57 60 42 48 60 42 488385 88 （e）n-3节点6和树根83交换后建堆 6 图3.7{73,6,57,88,60,42,83,72,48,85}堆排序的前四步过程 程序3.3 堆排序 void heapsort(struct node *heap,int n) //heap指向heaparray[0]，n是堆数组长度 { } 堆排序效率 因为建堆效率是O（n），而将位置i上的元素与堆顶元素交换需要n-1次，并重建n-1 int i; buildMAXheap(heap,n); //在堆数组[0～n-1]建立堆 swap((heap+0),(heap+n-1)); //将当前堆数组的最后一个节点与堆顶节点交换 n--; //堆元素减一 //排序过程直至堆剩余一个元素为止 while(n){ buildMAXheap(heap,n); swap((heap+0),(heap+n-1)); n=n-1; } 次堆，在最坏情况下，每次恢复堆的需要移动 log 2 i 次，那么， 155 log i1 n1 2 i 次移动需要时间开 《数据结构》教案 2022-3-22 销是O（ nlog 2 n ），即堆排序最坏情况下的效率是 O(nlog 2 n) 。 3.5 归并排序 两路归并排序思想 将两个有序的数组合并为一个有序的数组称之为归并（Mergesort）。设待排序数组有n 个元素{R 1 ，R 2 ，...，R n }，在前面讨论的直接插入排序方法中，我们对第i个元素排序时假 定前i-1个元素是已经排好序的，初始i从2开始。与此类似，归并排序初始时将n个元 素的数组看成是含有n个长度为1的有序子数组，然后将相邻子数组两两归并，归并后的 子数组的长度倍增为2，而个数减少一半为 n ，反复归并子数组，直至最后归并到一个长 2 度为n的数组为止。归并排序不同于快速排序，它的运行效率与元素在数组中的排列方式 无关，因此避免了快速排序中最差的情形。 归并排序和增量排序有些类似，它们的区别在于，shell是把长度为n的待排序序列以 步长 d i n 2 i 进行分割，以间隔为d i 的元素构成一组。而归并排序是相邻的元素为一组，继 而以相邻组归并。 对包含n个元素的数组应用归并排序方法，需要一个长度为n的辅助数组暂存两路归 并的中间结果，空间开销的增加是归并排序的一个弱点，但是，任何试图通过程序技巧来 取消辅助数组的代价是程序变得极其复杂，这并不可取。 图3.8是两路归并排序示意。图中显示，一次归并结束时，序列尾部可能有1个子数 组及元素不能归并，需要进行尾部处理。因为，一次归并过程中子数组能两两归并的条件 是当前归并元素位置i≤n-2L+1，否则，余下的待排序元素一定不足两个子数组的长度，需 要进行尾部处理，方法有2：①当前归并位置i 们看成是一个归并序列直接进行归并处理，并放入到归并结果序列的尾部；②i>n-L+1，余 下元素个数少于一个子数组长度，我们将这些元素直接移入到归并结果序列的尾部。 两路归算法 包含n个元素的数组两两归并排序的算法包含有两个函数，分别是①两组归并函数： merge(归并起点,子数组1终点位置,子数组2终点位置,待排序数组，中间数组); ②一趟归并函数： mergepass(待排序数组长度，子数组长度，待排序数组，中间数组); 156 《数据结构》教案 2022-3-22 [36]，[20]，[17]，[13]，[28]，[14]，[23]，[15]，[6]，[12]，[43]，[51]，[5] （a）初始将数组看成是由n个长度为1的子数组构成 归并跨度+=2L i=1 j=1 [20，36]，[13，17]，[14，28]，[15，23]，[6，12]，[43，51]，[5] 子数组长度=2L （b）相邻子数组一次归并后，子数组长度倍增，子数组的个数减少一半 归并跨度>(n-2L+1)是一次归并循环过程结束条件 i=1 子数组长度=4L 看成一个归并序列 （c）一次归并结束时，尾部可能有子数组或元素不能归并，需要进行尾部处理 归并跨度>(n-2L+1)，不能归并，直接进行尾部处理 j=1 [13，17，20，36]，[14，15，23，28]，[6，12，43，51]，[5] [13，14，15，17，20，23，28，36]，[5，6，12，43，51] 子数组长度=8L 尾部子数组 （d）归并跨度大于n-2L+1，无需两两归并，直接进行尾部处理 [5，6，12，13，14，15，17，20，23，28，36，43，51] （e）直接两两归并 图3.8 归并排序过程 我们先看子数组归并排序算法： 算法3.3 两组归并 void merge(int L,int m,int m1,struct node *array,struct node *temp) { int i=L,k=L,j=m+1; while((i<=m)&&(j<=m1)){ if(array[i].key<=array[j].key){ temp[k]=array[i]; i++; } else{ temp[k]=array[j]; j++; } k++; } if(i>m)for(i=j;i<=m1;i++){ temp[k]=array[i]; k++; } 157 《数据结构》教案 2022-3-22 } else for(j=i;j<=m;j++){ temp[k]=array[j]; k++; } 一趟归并排序算法如下： 算法3.4 一趟归并排序 void mergepass(int n,int L,struct node *array,struct node *temp) { } 最后，我们得到两路归并排序算法如下： 算法3.5 两路归并排序算法 for(int i=1;i<=n-2*L+1;i+=2*L)merge(i,i+L-1,i+2*L-1,array,temp); if(i else for(int j=i;j<=n;j++)temp[j]=array[j]; int mergesort(int n,struct node *array) { } 当2＜n≤2时，mergepass()调用了i次（i≈log 2 n），每次调用mergepass()的时间 开销是O(n)数量级，在mergesort()中，最后有可能需要从temp[]向array[]移动n次， 所以，两路归并排序的时间花费是O(n log 2 n)数量级，相当于快速排序方法。 i-1i int L=1; struct node temp[N+1]; //排序元素个数是N while(L mergepass(n,L,array,temp); L*=2; if(L>=n){ for(int i=1;i<=n;i++) array[i]=temp[i]; return(0); } mergepass(n,L,temp,array); L*=2; } 158 《数据结构》教案 2022-3-22 3.6 数据结构小结 有关数据结构的内容就讨论到此，我们希望通过这一部份的学习使读者掌握基本的数 据结构内容以及程序设计初步。希望通过教学、习题、上机试验几个环节为读者建立分析 和设计数据结构的基本概念，包括理解数据逻辑结构、存储结构、排序与检索等内容，为 大家将来的学习提供良好的基础。现在重新回顾已经学过的内容。 3.6.1 数据结构的基本概念 一、什么是数据结构 这个问题涉及到两个基本概念。 1. 数据类型：程序设计语言中各个变量所具有的数据种类。比如FORTRON的基本数 据类型是整型、实数型、逻辑型、复数型。C语言中除整型、字符型、实数型等基 本数据类型外还有结构、共用体、枚举、位域等用户定义的数据类型。 2.数据集合：指某种数据类型的元素集合。 在此基础上我们说数据结构是数据元素及其相互关系的集合。数据结构不仅描述数据元 素，而且要描述它们之间相互关系所表达的元素之间存在的某种联系，称为结构，我们定 义过二元组： S＝（D，R） 就是表达了这个意义。 程序设计中需要将数据结构存储在计算机内存中，即数据结构的物理映象，我们说数据 的逻辑结构与物理结构是不可分割的两个内容，这里再次列出数据结构划分类型如图3.9 所示。 顺序存储结构（数组、队列、栈、完全二叉树） 物理结构 数据结构 线性表 逻辑结构树 图 图3.9 数据结构类型划分 链式存储结构（链表、树） 索引存储结构（倒排表，B+树） 散列存储结构（哈希表） 3.6.2 数据结构分类 我们有三种基本的数据结构类型，即表、树、图。 159 《数据结构》教案 2022-3-22 3.6.2.1数据结构中的指针问题 表结构中我们重点学习了链表设计，包括它的生长，删除等基本操作。在这里我们强调 了C语言中指针的运用问题，对指针的理解一直是困扰我们学习C语言和数据结构的一个 主要问题，我们应该清楚，指针首先是一个变量，它也有地址，其次，才是这个变量存储 的是一个指向其它变量的地址，最后，这个指针必须和它所指向的那个变量的数据类型相 同，因为在数组元素序列中，我们知道每个元素占用的存储空间大小由其数据类型决定， 指针与其同类型，表明当对指针变量（内容）进行加一操作的时候，我们可以正确的指向 数组内下一个元素的起始地址。 注意，指针只是指向变量所占存储空间起始地址，它是一个存储单元的地址，不是一段 存储区域的空间，请看如下问题： struct node { int key; …… struct node next; }*hash[40]，*p,a1; 程序定义了一个node结构类型的指针数组hash[40]和指针p，操作如下： &a1=malloc(sizeof(node)); hash[i]=a1; p=hash[i]; 问，p = hash [i]操作是把元素hash[i]指向的a1的地址赋给了p，还是把hash[i]->next 赋给了p 呢？是否可以写成p=hash[i]->next 呢？ 问题出在我们对指针的理解上。 （1）首先，定义是一个node节点类型的指针数组，所以，hash[i]就是指针，它指向一个 地址a1，比如是某一个链表的第一个数据节点。 （2）注意，指针是指向某数据类型变量的地址，它和该数据类型的内部结构无关。hash[i] 只是一个node类型的指针变量，是地址的概念，它没有实际占有空间，不是node节点， 当然也就没有node节点变量的指针域，比如： struct node a; 变量a是有指针域next的，你可以用： a-->next=a2； 语句让a指向a2，但是，hash[i]指针没有next指针域这一说，所以： p=hash[i]-->next； 是错误的，实际上，hash[i]指向了链表头节点a1的地址，所以，p=hash[i]就可以了。 160 《数据结构》教案 2022-3-22 3.6.2.2线性表的效率问题 顺序表、栈、队列等是基本要掌握的内容，特别在某一条件下的效率分析问题，比如， 删除操作时顺序表平均移动次数是表长n的函数： ASL n1 ，当n很大时它的效率明显 2 低于链表结构，但在随机读写效率上顺序表优于链表。我们特别注重顺序表与链表在概念 上的区别。此外，递归也是同学必须掌握的内容之一。 3.6.2.3二叉树 在树结构中我们重点讨论了二叉排序树。包括二叉树的基本概念、几种特殊的二叉树结 构如满二叉树，完全二叉树，平衡二叉树等是同学必须了解的基本内容。二叉树程序设计 是我们学习的重点，它比链表设计增加了递归设计内容的难度，读者必须通过实际编程， 才能熟练掌握和很好的理解二叉树设计与应用问题。 我们指出二叉树的存储结构是多种形式的，有顺序存储、链式存储方式等，一般我们采 用链式存储结构，它含有两个指针域一个数据域，对于哈夫曼树还增加了父指针域。我认 为，在二叉树程序设计中最基本的思想是递归程序设计的运用。用递归实现它的动态生长， 删除，检索，遍历操作，原则上要求读者设计二叉树相关操作时应是递归结构实现的。 我们还指出，从概念上讲数据结构另一种分类方式是静态与动态数据结构的区别。所谓 静态和动态是指数据结构特性在该数据结构存在期间的变动情况。顺序表是静态的，因其 结构特性在它存在期间是不变的，只有长度的变化。树是动态的，因为它的结构特性依赖 于它的生长过程。应该说链表也是静态的数据结构，至少不能说它是动态的。因为链表插 入与删除不改变它本身特性，只是表长的变化，这点与教材看法不同，大家可以商椎。 无论是表结构还是树结构，简洁明快的结构化程序设计风格是我们所追求的，数据结构 内容本身读者可以在将来的学习中不断加深理解，但良好的C语言程序设计能力与风格则 是你们整个软件技术学习中的基础。 3.6.3排序与检索 在数据结构内容之内，属于数据结构操作的一类问题是检索与排序。在检索方面，顺序 检索、对半检索都是基本内容，我们重点讨论了它们的检索效率。 在描述数据结构的物理结构时我们知道有顺序、链表、散列和索引四种基本结构，其中 散列存储结构就是通过哈希函数实现关键码值到存储地址的转换，即哈希造表或地址散列。 这是一个重要的概念，它通过计算函数表达式求解元素地址，它所注意的是由于关键码集 合空间大于内存可分配地址空间而造成的地址冲突问题。构造哈希函数的标准是它与关键 码的相关性，以期达到地址均匀散列。解决地址冲突的办法是线性探测与链地址法。 在排序方面，对于基本概念我们主要考虑了稳定性和排序效率问题，此外还讨论了直接 161 《数据结构》教案 2022-3-22 插入排序与快速排序方法，我们特别注意的是快速排序中枢轴元素的选取问题，如果每次 选取到序列的中值则可以平分前后子序列，使效率最佳。 3.7算法分析的基本概念 算法的内容是数据结构设计中经常遇到的术语与概念。我们说程序设计是算法与数据结 构在计算机上的实现，算法也就是解决问题的步骤。衡量各种数据结构优劣时，就需要用 到算法分析内容。 3.7.1基本概念 算法分析是程序执行时间的定性估算，也就是运行时间的上、下限范围。为此，我们需 要明确一些基本概念。首先，算法分析有时间复杂度与空间复杂度两个方面，目前一般的 计算机内存已足够大，在简单程序设计情况下，我们可以做到用程序的内存工作长度空间 来换取时间上的处理速度，因此，有时候我们说对于算法分析来说更看重的是时间复杂度。 实际上不能这样简单处理。计算机内存资源是我们程序运行时间的基本条件，在当前普 遍应用的多任务操作系统中，每一个进程分配的内存资源是有限的，当你程序算法占用的 空间超过操作系统分配给你的资源时候，操作系统会在硬盘物理空间上给你开设缓存区域， 或者在你的数据文件太大（它总是保存在硬盘物理空间上），运行中需要分阶段从内存调进 的情况下，程序执行过程中会出现频繁的内外存数据交换，也就是I/O操作，常识告诉我 们，任何一种I/O操作耗时远远大于CPU与内存之间的数据交换时间，差异大于一个到两 个数量级。因此，算法设计中空间复杂度依然是一个重要因素。 衡量算法优略的一个基本标准是说，处理一定规模（Size）的输入时该算法所执行的基 本操作（basic operation）的数量。 这里，规模的概念依赖于具体算法，比如，检索和排序算法中的输入元素数量。基本操 作的概念依据计算机硬件资源不同而有所不同，比如，一般的计算机CPU都支持两个变量 之间的加减乘除的整数操作、浮点数操作，但是不支持n个整数之间的累加操作，我们定 义基本操作的性质是完成该操作所需的时间与操作数具体值无关，所以，两个变量之间的 加减乘除的整数操作可以看成是基本操作，但是n个数累加所花的时间就要n来决定，比 如for语句的循环次数。 程序3.4是在一维数组中检索最大值，它依次遍历数组每一个元素，比较每一元素值并 保存当前最大元素。 程序3.4求数组最大值 int iargest(int *array,int n) { 162 《数据结构》教案 2022-3-22 int currlarge=0; for(int i=0;i renturn(currlarge); } 这里，n是任务规模，基本操作是比较运算、赋值操作，它们所需的时间与其在数组中 的位置i无关，也与元素数值的大小无关。影响程序运行时间的因素是规模n，设基本操作 时间是c，则程序3.4的运行时间为t=cn，定性的说，程序3.4算法时间代价是T(n),它与 输入规模呈线性关系增长。现在看程序3.5描述的情况。 程序3.5变量累加 long add(int n) { long sum=0; for(int i=1;i<=n;i++)for(j=1;j<=n;j++)sum++; renturn(sum); } 程序3.5的输入规模是n，基本操作是加法，设基本操作时间为c，其运行时间是cn， 2 22 我们估计它的运行时间代价是T(n)，这里的c包含了程序变量初始设置等因素。当规模为 平方项的时候，时间代价的增长率就很可观了。 时间函数的增长率是衡量算法性能的关键指标。时间复杂度是定性分析，要定量确定某 一算法所用时间是很困难的，我们只要确定它随规模n的增长率在某一数量级，确切的说 是确定那些具有最大执行频度（规模）的语句。所谓频度可以从下列程序语句中看到它的 概念。即频度就是某一语句（基本操作）的循环执行次数，程序的频度是程序中具有最大 频度的语句所具有的频度。下例中，因为程序1只是单一命令语句，所以它的频度为1；程 序2有一个n次循环语句，它的频度是n；程序3是双循环语句，当然它的频度就是n×m。 程序1 ... 程序2 .... 程序3 ... x++； for(i=0；i ... for(i=0；i for(j=0；j } ... } 频度为1 频度为n 频度为n×m 据此，我们估计程序1算法时间复杂度是O(1)，程序2是O(n)，程序3是O(n×m)数 量级的。 163 《数据结构》教案 2022-3-22 表3.1几种时间复杂度随规模n的增长率比较 n 1 2 4 8 16 32 log 2 n 0 1 2 3 4 5 nlog 2 n 0 2 8 24 64 160 n 1 4 16 64 256 1024 2 n 1 8 64 512 4096 32768 3 2 2 4 16 256 65536 483648 n 3.7.2上限分析 一个算法的运行时间上限用来描述该算法可能有的时间花销的最高增长率，它与输入规 模n有关，我们知道，一个算法的具体时间花费与输入元素的分布特性有关，比如快速排 序过程中的最差、最佳和平均时间代价的不同。因此，时间估计的上限也分成该算法平均 条件下的增长率上限、最佳条件下的增长率上限或最差条件下的增长率上限。 现在我们给出算法时间复杂度的上限定义：如果存在两个常数C≥0，n0≥0，当n≥n0 时有|f(n)|≤C|g(n)|，则称函数f(n)是O(g(n))的时间复杂度。 这里，大O表示时间估计上限，|f(n)|是某算法的运算时间，定义表明，如果说一个算 法的时间复杂度是O(g(n))数量级，则表明该算法实际所耗时间只是O(g(n))的某个常数倍， n是算法规模参数。因此，当我们写O(1)时间复杂度时，意味着算法执行时间是一个常数， 而O(n)是n的线性函数，O(log 2 n)是对数函数。我们知道当n充分大时log 2 n远小于n，nlog 2 n 是远小于n的，一些常见的关系已经在表3.1给出。 例3.1 设有一算法，分析其每一语句的频数为C k n，则它们的和是： p(n)= C k n+ C k-1 n+ C k-2 n+···+ C 1 n+ C 0 这里C i 为常数，C k 不为零，n是程序执行规模，因为： k k-1k-21 k 2 c k n k c k-1 n k1 ...c 0 c k n k c k -1 n k ...c 0 n k (c k c k -1 ...c 0 )n k 由定义我们可知，该算法的时间复杂度是P(n)=O(n)，即程序的算法时间复杂度只考虑具 有最大频度的语句。 例3.2 顺序检索的时间复杂度上限估计。我们知道，线性检索表的检索成功的平均比较次 数与规模n的关系是 k n1n ，或者说它的平均检索时间估计是 c ，对于n〉1，我们有关系 22 c n cn 成立，所以它的平均时间复杂度上限是O(n)。 2 3.7.3下限分析 上限估计告诉我们一个算法时间的增长率极限情况，有时候我们想知道一个算法至少它 需要多少运行时间，也就是它执行时间的下限程度，我们用符号Ω表示。定义: 如果存在 164 《数据结构》教案 2022-3-22 两个常数C≥0，n0≥0，当n≥n0时有|f(n)|≧C|g(n)|，则称函数f(n)的时间复杂度下限 是Ω(g(n))。 例3.3 设一算法时间花费是T(n)= C k n+ C k-1 n ，因为 c k n k c 1 nc k n k c k n k ，根 k k-1 据定义，它的时间估计下限是Ω(n)。 对于线性检索，在数组中要找到关键码为k的元素，最差的情况下，我们可能需要检索 k 完整个数组长度才能确定，最好的情况下是1次，平均是数组长度的一半，因此，在平均 和最差检索情况下，至少需要检索cn次（c是基本操作），所以它的下限估计在这两种情况 下也是Ω（n）。 当一个算法的时间估计上下限相等，都是g(n)的时候，我们说该算法它的时间估计是 (g(n)) 的，即g(n)既在O()中，也在Ω（）中。 3.7.4空间代价与时间代价转换 算法的空间开销与时间开销是一对矛盾体。比如，计算sin、cos函数值是用级数求和 的过程，如果在算法中多次使用sin、cos函数值，可以假定一个合理的精度将sin、cos 函数值制作成一个表，比如以每分为一个步长，于是，计算sin、cos函数值的过程就转换 为查找表的过程，给出表的基地址和偏移量，我们可以很快查找到相应的函数值，而这一 过程的代价是查找表所占用的内存空间。 另外一个例子是布尔变量的问题，它取值只有两种状态，真或假，假定一个算法使用了 32个布尔变量，一种方法是每个布尔变量用以字符类型量表示，需要占用32字节。我们也 可以用一个long类型变量表示，它的每一比特（bit）位代表一个布尔变量，只需要4个 字节，显然，程序上前者简单后者繁琐，但是空间开销正好相反。 再看一个实际例子，假定一个算法中需要多次使用阶乘，最大是12的阶乘，当然可以 很容易的用递归函数计算阶乘，它需要一个长整型量和多次递归调用。而从查找表概念理 解，预先计算12！如表3.2所示。 表3.2 阶乘查找表 12！ 479001600 11！ 39916800 10！ 3628800 9！ 362880 8！ 7！ 40320 5040 6！ 720 5！ 4！ 3！ 2！ 1！ 120 24 6 2 1 表3.2是一个数组，计算12以内的阶乘就是将给定值作为偏移量访问查找表的过程， 它非常简单，是空间换时间的典型例子。 我们应该清楚，存储空间和时间代价互换的基本原则是，避免程序执行过程中出现不必 要的内外存数据交换，即，外存硬盘空间开销越小，程序执行越快，我们在前面说过，I/O 数据交换是计算机运行的瓶颈。 有关算法的详细内容同学可以参考其它教科书，算法与数据结构是密切相关的，选择一 种数据结构也就确定了元素之间的关系，它对应不同的算法，我们当然希望有一种好的数 165 《数据结构》教案 2022-3-22 据结构得到高效率的算法表达，使时间复杂度最小，所以有 算法＋数据结构＝程序 这一说法，有关数据结构的基本内容就讨论到此。 166 《数据结构》教案 2022-3-22 第6章 高级数据结构内容--索引技术 6.1 基本概念 索引文件用于组织磁盘中大量数据纪录检索的排列方式，主要是为提高关系数据库的 操作效率而设计的。一个应用关系数据库设计时，从逻辑结构上看每一客观实体（关系） 至少有一个能唯一的标识其所有属性或该关系的主属性，称为主关键字。若一个属性不能 唯一的标识一个关系，或者说它对应多个关系实体，则称其为该关系的次关键字。在关系 数据库设计时，我们总是按照主关键字组织数据字典的全局逻辑结构及联接关系的，在物 理实现上，也是用主关键字与纪录的物理地址相关联的。 当大量的数据纪录在内存时，为了提高检索效率就必须按检索的形式进行排序，显然， 主关键字检索是检索关系实体的基本操作之一，比如，一个学生数据库用学号唯一标识学 生这个客观实体的所有属性，要检索特定学生的情况时，输入该学生的学号可以检索到该 生所有属性值（如姓名、年龄、性别、籍贯、家庭所在地、系别等），于是，我们自然会以 主关键字对学生记录排序。 现在的问题是，检索是多角度、综合性进行的，比如，我们需要查看自动化系、来自 浙江杭州的学生情况，查找符合这一检索条件所要求的记录的方法可以有多种，比如，将 记录按‘系别’进行排序，在检索到‘系别’等于‘自动化系’的记录中，筛选出‘家庭 所在地’的属性值等于‘杭州’的记录。然而，要对‘系别’这一属性进行排序，就得把 内存物理地址与该属性相关联，换句话说，就是所有记录需要按‘系别’属性重排。此外， 同一关系数据库还有可能遇到查询‘年龄’等于20岁的女生记录的情况，或者是‘姓名’ 等于‘xxx’的检索要求等。显然，我们不可能每次都按检索条件重排硬盘中关系数据库的 所有记录。 避免重排数据库记录的另一种选择是索引技术（index file）。我们称之为索引技术或 文件的是，其文件内每个关键码与标识该记录在数据库的物理位置的指针相关联（一起存 储）。因此，索引文件为记录提供了一种按索引关键字排列的顺序，而不需要改变记录的物 理位置。一个数据库系统允许有多个索引文件，每个索引文件都通过一个不同的关键字段 支持对记录有效率的访问，即，索引文件提供了用多个关键字访问数据记录的功能，也避 免了数据库记录的重排操作。简而言之，索引技术的应用使记录的检索与其物理顺序无关。 显然，我们不可能让每个关键码都与记录的物理指针相关联，这样，记录的物理位置 变化会造成所有索引文件的修改。次关键码索引文件实际上是把一个次关键码与具有这个 次关键码的每一个记录的主关键码相关联起来，而主关键码索引再与一个指向记录物理位 167 《数据结构》教案 2022-3-22 置的指针相关联，即，其访问顺序是次关键码-主关键码-记录物理位置。 可以说，索引技术是组织大型数据库的关键技术，其中，线性表索引主要用于数据库 记录的检索操作，对于记录的插入与删除操作我们广泛使用的是树形索引，即B树。 + 6.2 线性索引 6.2.1 线性索引 线性索引是一个按关键码-指针对顺序组织的索引文件，该文件按关键码的顺序排序， 指针指向记录的物理位置，见图6.1所示。线性索引文件本身的记录是定长的，其检索效 率是O(n)，随数据库记录增大而降低，即使索引文件是顺序存储的能使用二分检索，但是 当数据库记录数目很大时，索引文件本身也无法在内存中一次装入，运用二分检索过程中 会多次访问硬盘，效率可能还不如线性检索。 37425273 硬盘数据记录 52 734237 图6.1线性索引可以实现变长数据库记录检索 磁盘中一个物理页大小是1024字节，即可以存储128个索引记录，设，数据库记录的线性 索引文件长度为100磁盘页（100kB），每页内记录（关键码值）按递增有序，则在内存中 建立一个二级索引文件，其每个记录是每个磁盘页的第一个关键码值，该二级索引文件长 度只有100项，数据库检索时，首先根据检索关键码值在这个顺序表文件中用二分检索找 到小于或等于它的最大值，就可以找到包含该关键码的索引文件磁盘页，将该磁盘页调入 内存只需继续在128个记录中查找即可完成，见图6.2所示。 我们熟知的多级索引结构是一种解决方案，比如，一个关键字/指针对需要8个字节， 12 二级索引文件 索引文件磁盘页 12 4700 图6.2二级线性索引 95 168 《数据结构》教案 2022-3-22 6.2.2 倒排表 二级索引存在的一个问题是，当我们向数据库插入或删除一条记录时，必须同时修改 磁盘与内存中的一、二级索引文件，当索引文件很大时，这种更改涉及到所有磁盘页数据 （索引记录）的移动，代价很大。特别是当索引文件所有纪录均与物理纪录相关联的情况 下，随着一个实体纪录的插入或者删除，数据库的所有索引文件都需要修改。另外，当次 关键码取值范围很窄时，数据库记录中有大量的记录取值相同，造成索引文件中大量的重 复引用。比如一个极端的例子是学生记录中的性别属性，非男即女，于是，索引文件中有 一半记录是重复的。 属性m索引纪录1属性m索引纪录2 属性m索引纪录n 属性2索引纪录1属性2索引纪录2 属性2索引纪录n 属性1索引纪录1属性1索引纪录2 属性1索引纪录n 主键码索引纪录1主键码索引纪录2 主键码索引纪录n 属性m属性m 属性m 属性2 属性1 主键码 实体纪录1 主键码 属性2 属性1 主键码 属性2 属性1 实体纪录2实体纪录n 数据库物理纪录 如果所有索引文件指针均和物理记录关联，则实体纪录数目变更时将影响所有索引文件 一种改进的方法是二维数组形式，其每一行对一个次关键码值，每一列包含了具有该 次关键码值的所有记录的主关键码值，于是，首先通过次关键码检索索引表找到它所对应 的所有主关键码值，下一步可以通过主关键码检索数据库记录，从而得到满足检索条件的 所有记录列表，见图6.3所示。二维索引表不但可以减少空间，而且数据库更新操作对索 引文件的影响也被限制在索引文件的一行之内，极限情况是次关键码取值范围变化，比如 新添一个次关键码值时候，需要移动二维数组，但这种情况实际中很少见。 它不足之处是数组必须有一个固定的长度，则有①与次关键码相关联的主关键码记录 数受限（限定了数据库具有相同次关键码值的最大允许记录数）；②当次关键码取值对应的 数据库记录数目变化很大时，二维数组长度无法兼顾，从而造成一个次关键码值对应很少 记录数（比如只有一个主关键码相关联）的话，存储空间浪费很大。 169 《数据结构》教案 2022-3-22 次码 女 男 男 女 男 主码 文静 郭名 王东 李雯 庄全 主码 男 次码女 郭名 文静 王东 李雯 庄全 二维索引表 图6.3 二维索引文件 主关键码数组 A01 A02 A03 主关键码数组 B01 主关键码数组 C01 C02 图6.4 倒排表 物理位置 A B C 既然二维数组也是一个线性表，显然链表是一种解决办法。我们定义的倒排表是：每 一次关键码值有一指针指向它所对应的所有主关键码形成的数组，数组中的每一主关键码 与磁盘中的数据库记录位置有唯一的指针相关联，即，检索记录顺序是由次关键码到主关 键码，再到数据库记录，见图6.4所示。 6.3 2-3树 基于线性索引技术的关系数据库存储方式存在的最大问题是，当大量的记录频繁更新 的时候，其操作效率非常低，原因是每更新一条纪录就要修改一个索引文件内的所有的指 针内容，当你有多个索引文件，以及海量的记录数目时，线性索引效率很低， 而且，修改 指针的操作效率与线性索引结构无关，多级索引结构虽然能提高检索效率，但是记录物理 地址变更引起的指针修改是全索引文件范围内的，既线性索引文件其所有指针信息都是相 关的，如果我们有一种方法，记录的插入与删除只是影响索引文件局部区域，那么它作为 170 《数据结构》教案 2022-3-22 主关键码的索引就会完成得很好。树形索引是一种很好的索引文件组织方式，它本身是非 线性结构，磁盘页之间指针相关性很低，它可以提供有效的插入与删除操作，从以前的二 叉检索树讨论中知道，其效率是树深度的对数关系。 二叉树当然不适合作为索引文件结构，第一，它只有两个子树，不符合磁盘页划分； 第二，它会因为更新节点操作变得不平衡，尤其检索树存储在磁盘中时，不平衡情况对检 索效率影响更为重要，当一个节点深度跨越了多个磁盘页时，对节点的访问就是从第一个 磁盘页（根节点）开始达到这个节点所在磁盘页为止的所有节点路径之和，随着磁盘页在 内外存中的调进调出，它涉及到多次内外存交换，效率变得非常低下。因此，要采用树形 索引结构，必须寻找一种新的树结构，它能解决插入与删除操作带来的不平衡问题。这种 树形结构经过多次更新操作之后能自动保持平衡，并且适合按页存储，既，我们要求它的 算法具有下列特性: (1) (2) (3) 以一个磁盘页为单位； 插入与删除操作之后能自动保持高度平衡； 平均访问效率最佳。 基于磁盘页的树形索引结构 5 3 246 7 1 2 3 4 6 5 7 向完全二叉树插入一个关键码值为1的节点之后，需要调整所有节点重新维持平衡 首先，我们讨论2-3树概念，在此基础上引伸出B树。 + 171 《数据结构》教案 2022-3-22 6.3.1 2-3树定义 一棵2-3树具有下例性质： 1. 一个节点包含一个或者两个关键码； 2. 每个内部节点有2个子女（如果它包含一个关键码），或者3个子女（包含2个关键码）； 3. 所有叶子节点在树的同一层，因此树总是高度平衡的。 类似于二叉排序树，2-3树每一个节点的左子树中所有后继节点的值都小于其父节点第 一个关键码的值，而中间子树所有后继节点的值都大于或等于其父节点第一个关键码的值 而小于第二个关键码的值，如果有右子树，则右子树所有后继节点都大于或等于其父节点 第二个关键码的值。见图6.5所示。 root 18 12 10152021 23 33 30 2431 4547 48 5052 图6.5 2-3树[因自文献] 一个在2-3树中检索特定关键码值的函数类似于二叉排序树检索过程，见例6.1所示。 例6.1 2-3树检索函数实现 struct node *findnode(struct node *root,int key) { if(root==Null)return Null; if(key==rootlkey)return root; if((rootNumkeys==2)&&(key==rootrkey))return root; if(key else{ if(rootNumkeys==1)return findnode(rootcenter,key); else{ if(key else return findnode(rootright,key); } } } 显然，2-3树节点定义为： struct node { 172 《数据结构》教案 2022-3-22 int lkey,rkey,Numkeys; struct node *left,*center,*right; }; 6.3.2 2-3树节点插入 向2-3树插入记录（不是节点）与二叉排序树相同的是新纪录始终是被插入到叶子节 点；不同的是2-3树不向下生长叶子，而是向上提升分列出来的记录。分以下几种情况： （1） 被插入到的叶子节点只有一个关键码（代表一个记录），则新记录按左小右大原则 被放置到空位置上。见图6.6所示。 root 18 12 1015 14 152021 23 33 30 2431 4547 48 5052 图6.6 在图6.5中插入关键码值为14的记录 （2） 被插入的叶子节点已经有2个关键码，但其父节点只有1个关键码。当被插入叶子 节点内部已经没有空位置时，我们要创建一个节点容纳新增记录和原先2个记录。 设原叶子节点为L，首先将L分裂为2个节点L和L’，L取3个节点中值为最小者， L’取值为最大者，居中的关键码和指向L’的指针被传回L的父节点，即，所谓提 升一次的过程。被提升到父节点的关键码按左小右大排序，并插入到父节点空位置 中。见图6.7所示。 root 18 12 10152021 23 33 被提升的记录 30 2431 4547 48 50 L 52 55 L' 图6.7 在图6.5中插入关键码值为55的记录产生1次提升 （3） 被插入的叶子节点已经有2个关键码，而且其父节点内部亦满。此时，我们用从叶 子节点提升上来的关键码对父节点重复一次分裂--提升过程，将一个关键码从父节 点中向更上一层提升，直至根结点，如果根节点被分裂，则继续提升的关键码形成 新的根节点，此时，2-3树新增一层。见图6.8所示。 173 《数据结构》教案 2022-3-22 root 18 12 10152021 23 33 30 24 初始 root 18 12 20 101519 21 24314547 5052 23 33 30 48 31 4547 48 5052 (a)插入19产生叶子分裂与提升 root 18 20 1519 21 24 33 23 12 10 30 3145 48 47 5052 (b)父节点产生分裂与提升 root 23 18 12 1015 19 20 2124 (c)根节点提升 图6.8 30 3145 33 48 47 5052 例6.2 2-3树插入函数 struct node *insert(struct node *root,int key, struct node *retptr,int retkey) { int myretv; struct node *myretp=Null; if(root==Null){ root=(struct node*)malloc(sizeof(struct node)); rootlkey=key; rootNumkeys=1; } else{ if(rootleft==Null){//叶子节点 174 《数据结构》教案 2022-3-22 if(rootNumkeys==1){//只有一个关键码 rootNumkeys=2; if(key>=rootlkey)rootrkey=key; else{ rootrkey=rootlkey; rootlkey=key; } } else {//关键码满，分裂提升 retptr=(struct node*)malloc(sizeof(struct node));//申请L’节点 且返回指针指向L’ if(key>rootrkey){// L’节点取最大值的关键码 retptrlkey=key; retkey=rootrkey;//提升中间值的关键码 } else{// rootrkey是最大值的关键码 retptrlkey=rootrkey; if(key retkey=rootlkey; rootlkey=key; } else retkey=key; } rootNumkeys=retptrNumkeys=1;//置L和L’关键码数为1 } } else {//非叶子节点小于左关键码值搜寻左子树*/ if（key else {/*子树为2叉或小于右关键码搜寻中间子树*/ if(（rootNumkeys==1）||(key insert(rootcenter,key,myretp,myr etv); else{//搜寻右子树 insert(rootright,key, myretp,myretv); 175 《数据结构》教案 2022-3-22 } } if(myretp!=Null){// 有孩子节点分裂而形成提升 if（rootNumkeys==2）{//分裂并提升父节点 retptr=(struct node*)malloc(sizeof(struct node)); rootNumkeys=retptrNumkeys=1; if(myretv retkey=rootlkey;//*返回值 rootlkey=myretv;//*原root为L retptrlkey=rootrkey;//L’关键码 retptrleft=rootcenter; retptrcenter=rootright; rootcenter=myrept; //指向L’ } else{ if(myretv retkey=myretv; retptrlkey=rootrkey;//L’键 retptrleft=myrept; retptrcenter=rootright; } else{//提升右关键码 retkey=rootrkey; retptrlkey=myretv; retptrleft=rootright; retptrcenter=myrept; } } } else{//root节点内只有一个键，可增加一个 rootNumkeys=2; if(myretv rootrkey=rootlkey; rootlkey=meretv; 176 《数据结构》教案 2022-3-22 rootright=rootcenter; rootcenter=myretp; } else{ rootrkey=myretv; rootright=myretp; } } } } } } 调用例6.2返回的是提升关键码的值（如有则为新的根节点键）与指向（如有则为新的根 节点指向）L’的指针。其中要注意的是分裂父节点几种处理情况：①提升左关键码值，此 时一定是从左子树中分裂提升，见图6.9所示；②提升中间关键码值是从中间子树中分裂 提升上来的，见图6.10所示；③提升右关键码情况见图6.11所示。 root 18 插入17 12162330 （a） 4853 33 myretp myretv=16 12 L myretv=18 L=root 16 左指针未变 12 center myretp 17 33 left 2330 myretp 17 L' root 1833 2330 （b） 4853 L'=retptr retptr->left=root->center center retptr->center=root->right 4853 （c） 图6.9父节点分裂提升左关键码 177 《数据结构》教案 2022-3-22 root 18 插入20 33 root 18 L 33 myretv 23 L' 30 （b） myretp 4853312 1620 （a） L=root 18 myretv=23 myretp L'=retptr 33 center未变center left repptr->left=myretp 左指针未变 myretpretptr->center=root->right 12 16 20304853 （c） 图6.10父节点分裂提升中间关键码 root 1833 插入43 root 1833 myretv=48 L myretp L' 53 312 16203043 （a） myretv=33 L=root 18 myretp （b） L'=retptr 48 retptr->left=root->right center center未变left 左指针未变 retptr->center=myretp root->rightmyretp 43 12 16 203053 （c） 图6.11父节点分裂提升右关键码 关于2-3树的删除操作，需要考虑三种情况：①从包含两个关键码的叶节点中删除一 个关键码时只需要简单清除即可，不会影响其它节点；②唯一个关键码从叶节点中删除； ③从一个内部节点删除一个关键码。后两种情况特别复杂，我们留待B+树时讨论。 6.4 B+树 6.4.1 B+树定义 定义：一个m阶的B树具有以下特性： （1） 根是一个叶节点或者至少有两个子女； （2） 除了根节点和叶节点以外，每个节点有m/2到m个子女，存储m-1个关键码； （3） 所有叶节点在树的同一层，因此树总是高度平衡的； （4） 记录只存储在叶节点，内部节点关键码值只是用于引导检索路径的占位符； 178 + 《数据结构》教案 2022-3-22 （5） 叶节点用指针联接成一个链表。 （6） 类比于二叉排序树的检索特性。 B树的叶节点与内部节点不同的是，叶节点存储实际记录，当作为索引树应用时，就是记录 的关键码值与指向记录位置的指针，叶节点存储的信息可能多于或少于m个记录。见图6.12 所示。 33 18 10 12 15 23 23 30 31 图6.12 4阶B + 树 48 33 45 47 48 50 52 + 18 19 20 21 22 B树节点结构定义为： Struct Bpnode｛ Struct PAIR recarray[MAXSIZE];//关键码/指针对数组 int numrec; Bpnode *left,*right; ｝ 其中，PAIR结构定义为： Struct PAIR｛ int key; Struct BPnode *point; ｝ 因为point同时也是指向文件记录的指针，我们需要注意同构问题，这里假设文件记 录与节点结构相同，当然，实际是不可能的。此外，这里定义的叶子节点只是存储了指向 记录位置的指针与关键码key，实际上应该是记录的关键码与数据信息（文件名等）。 一个B树的检索函数如例6.3所示, 子函数binaryle()调用后返回数组recarray[]内 等于或小于检索关键码值key的那个最大关键码的位置偏移。 currec recarray[i].key <= key recarray[0].keyrecarray[1].keyrecarray[i].keyrecarray[m-1].key + + 具有m个子女的B+树节点k的关键码-指针对数组 例6.3 B树检索函数 struct BPnode *find(struct BPnode *root,int key) { int currec; currec=binaryle(root->recarray,root->numrec,key); 179 + 《数据结构》教案 2022-3-22 if(root->left==Null){//叶子节点 if(root->recarray[currec].key==key) return root->recarray[currec].point; else return Null; } } 我们注意到，一个节点的左指针为空时表明到达了叶子节点，从节点结构定义可知，内部 节点的左指针应该指向其左子树的根节点，而叶子节点链上的每个节点左指针为空，只有 右指针指向其兄弟节点，且链尾右指针亦为空。 else find(root->recarray[currec].point,key); 6.4.2 B+树插入与删除 插入操作过程 + 一棵B的生长过程见图6.13所示，首先找到包含记录的叶子节点，如果叶子未满，则 只需简单将关键码（与指向其物理位置的指针）放置到数组中，记录数加一；如果叶子已 经满了，则分裂叶子节点为两个，记录在两个节点之间平均分配，然后提升右边节点关键 码值最小（数组第一个位置上的记录关键码）的一份拷贝，提升处理过程与2-3树一样， 可能会形成父节点直至根节点的分裂过程，最终可能让B树增加一层。 + 180 《数据结构》教案 2022-3-22 50 10 12 23 33 48 (a) 10 12 23 33 33 48 50 (b) 3348 10 12 15 18 2333 45 4748 50 52 (d)47插入之后 183348 33 10 12 15 18 2333 45 48 50 52 (c)15,18,52,45插入之后 10 12 15 18 21 23 33 45 47 (e)21插入之后 183348 48 50 52 18 20 21 23 31 33 45 47 (e)20,31插入之后 内部节点关键码数达到m分裂时， 33 提升排序位置上的m-1关键码 18 23 10 12 15 18 20 2123 30 31 48 33 45 47 10 12 15 48 50 52 48 50 52 (f)继续插入30引起分裂提升过程 图6.13 删除操作过程 + 在B树中删除一个记录要首先找到包含记录的叶子节点，如果该叶子内的记录数超过 m/2，我们只需简单的清除该记录，因为剩下的记录数至少仍是m/2。 如果一个叶子节点内的记录删除后其余数小于m/2则称为下溢，于是我们需要采取如 下处理： （1） 如果它的兄弟节点记录数超过m/2，可以从兄弟节点中移入，移入数量应让兄弟节 点能平分记录数，以避免短时间内再次发生下溢。同时，因为移动后兄弟节点的第 一个记录关键码值产生变化，所以需要相应的修改其父节点中的占位符关键码值， 以保证占位符指向的节点其第一个关键码值一定是大于或等于该占位符； （2） 如果没有左右兄弟节点能移入记录（均小于或等于m/2），则将当前叶节点的记录移 出到兄弟节点，且其和一定小于等于m，然后将本节点删除。把一个父节点下的两 棵子树合并之后，因为要删除父节点中的一个占位符就可能会造成父节点下溢，产 生节点合并，并继续引发直至根节点的合并过程，从而树减少一层。 （3） 一对叶节点合并的时候应清除右边节点。 对一棵B树的删除操作过程见图6.14所示。 + 181 《数据结构》教案 2022-3-22 33 18 10 12 15 18 23 18 19 20 2123 30 31 32 48 33 45 4748 50 52 (a)设下限为3，删除关键码值18的记录不影响占位符18 33 18 30 10 12 15 20 21 2330 31 32 48 33 45 4748 50 52 (b)再删除关键码值19的记录之后从兄弟节点移入23并修改符节点占位符为30 33 18 30 10 12 15 20 21 2330 31 32 48 只剩一个子树 45 47 48 50 52 (c)删除关键码值33的记录合并兄弟叶节点 30 18 10 12 15 20 21 23 30 1831 10 12 15 20 21 23 1830 10 12 15 20 21 23 (f)根节点合并 图6.14 31 32 45 47 52 33 30 31 32 45 47 48 50 52 (d)传递叶节点到右子树并调整占位符 31 32 45 47 52 (e)删除右子树的48，50，30之后叶节点合并引起父节点合并 6.4.3 B+树实验设计 (1) 设计一个4阶B树，要求： 记录应该包括4字节（long）关键码值和60字节的数据字段(存储文件名等)，设 每个叶子可以存储5条记录，而内部节点应该是关键码值/指针对。此外，每个节 点还应该有指向同层下一个节点的指针、本节点存储的关键码数等； (2) + 此4阶B树应该支持插入、删除以及根据给定关键码值进行精确检索与关键码范围 182 + 《数据结构》教案 2022-3-22 检索； (3) (4) 显示（打印）此4阶B树的生长(含删除节点)过程实例； 有能力的同学增加4阶B树的存/取（从硬盘文件）功能。 + + 程序设计时建议注意以下几点： 节点结构定义，即内部节点与外部节点同构问题； 初始化设置； B 树输入（文件名与关键码）/输出（显示）功能； + 183
版权声明：本文标题：《数据结构》教程c语言版 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1710383597a570628.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论