线索二叉树

jyl 贡献于2012-10-29

作者 jyl  创建于2006-03-24 11:34:00   修改者番茄花园  修改于2006-03-30 01:32:00字数18444

文档摘要: 6·4线索二叉树 1、线索二叉树的结点结构二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构,使每个结点都有了唯一前驱和后继(第一个结点无前驱,最后一个结点无后继)。对于二叉树的一个结点,查找其左右子女是方便的,其前驱后继只有在遍历中得到。为了容易找到前驱和后继,有两种方法。一是在结点结构中增加向前和向后的指针fwd和bkd,这种方法增加了存储开销,不可取;二是利用二叉树的空链指针。
关键词:

 6·4 线索二叉树   1、线索二叉树的结点结构 二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构,使每个结点都有了唯一前驱和后继(第一个结点无前驱,最后一个结点无后继)。对于二叉树的一个结点,查找其左右子女是方便的,其前驱后继只有在遍历中得到。为了容易找到前驱和后继,有两种方法。一是在结点结构中增加向前和向后的指针fwd和bkd,这种方法增加了存储开销,不可取;二是利用二叉树的空链指针。现将二叉树的结点结构重新定义如下: lchild ltag data rtag rchild 其中:ltag=0 时 lchild指向左子女; ltag=1 时 lchild指向前驱; rtag=0 时 rchild指向左子女; rtag=1 时 rchild指向后继; 以这种结点结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,指向前驱和后继的指针叫线索,加上线索的二叉树叫线索二叉树,对二叉树进行某种形式遍历使其变为线索二叉树的过程叫线索化。 学习线索化时,有三点必须注意:一是何种“序”的线索化,是先序、中序还是后序;二是要“前驱”线索化、“后继”线索化还是“全”线索化(前驱后继都要);三是只有空指针处才能加线索。 2、对二叉树进行中序线索化的算法 bithptr *pre; /* 全程变量 */ void INTHREAD(bithptr *p) {if(p!=NULL) { INTHREAD(p->lchild); /* 左子树线索化 */ if(p->lchild==NULL) { p->ltag=1;p->lchild=pre;} if(p->rchild==NULL) p->rtag=1; if(pre!=NULL && pre->rtag==1) pre->rchild=p; pre=p; /* 前驱指向当前结点 */ INTHREAD(p->rchild); /* 右子树线索化 */ } 3、在线索二叉树上查找前驱和后继 (1)中序线索二叉树:若结点的ltag=1,lchild指向其前驱;否则,该结点的前驱是以该结点为根的左子树上按中序遍历的最后一个结点。若rtag=1,rchild指向其后继;否则,该结点的后驱是以该结点为根的右子树上按中序遍历的第一个结点。 求后继的算法如下: bithptr *INORDERNEXT(bithptr *p) {if (p->rtag==1) return(p->rchild); else {q=p->rchild; /* 找右子树最先访问的结点 */ while (q->ltag==0) q=q->lchild; return(q); } } 求前驱的算法如下: bithptr *INORDERNEXT(bithptr *p) {if (p->ltag==1) return(p->lchild); else {q=p->lchild;/* 找左子树最后访问的结点 */ while (q->rtag==0) q=q->rchild; return(q); } } (2) 后序线索二叉树: 在后序线索二叉树中查找结点*p的前驱:若结点*p无左子树,则p->lchild指向其前驱;否则,若结点*p有左子树,当其右子树为空时,其左子树的根(即p->lrchild)为其后序前驱。当其右子树非空时,其右子树的根(即p->rchild)为其后序前驱。 在后序线索二叉树中查找结点*p的后继:若结点*p为根,则无后继;若结点*p为其双亲的右孩子,则其后继为其双亲;若结点*p为其双亲的左孩子,且双亲无右子女,则其后继为其双亲;若结点*p为其双亲的左孩子,且双亲有右子女,则结点*p的后继是其双亲的右子树中按后序遍历的第一个结点。所以,求后序线索二叉树中结点的后继要知道其双亲的信息,要使用栈,所以说后序线索二叉树是不完善的。 (3)先序线索二叉树: 在先序线索二叉树中查找结点的后继较容易,而查找前驱要知道其双亲的信息,要使用栈,所以说先序线索二叉树也是不完善的。 4、对线索二叉树进行中序遍历的算法 void TRAVERSEINTHREAD(bithptr *p) {if (p!=NULL) { while(p->ltag==0) p=p->lchild; do { visit(p->data); p=INORDERNEXT(p); } while (p!=NULL) } } 2、          线索二叉树的插入 在线索二叉树上插入结点,不仅要修改结点的指针,还要修改线索。现仅以在中序线索二叉树的*p结点和其右孩子结点之间,插入*q(它只有右子树)结点讨论之。 void INSERTRIGHT(bithptr *p,*q) {bithptr *s; s=INORDERNEXT(p); q->ltag=1;q->lchild=p;q->rtag=p->rtag;q->rchild=p->rchild; p->rtag=0;p->rchild=q; if (s!=null && s->ltag==1) s->lchild=q; }   6·5 树和森林   6·5·1 树、森林与二叉树的相互转换 树、森林与二叉树可以相互唯一转换 1、                     树、森林转为二叉树 树(树林)转换成二叉树时结果是唯一的。其转换可以递归的描述如下:若树(树林)为空,则二叉树为空;否则,树(树林)中第一棵树的根是二叉树的根,第一棵树除去根结点后的子树林是二叉树的左子树,树林中除去第一棵树后的树林形成二叉树的右子树。 形象的说转换过程可用下面的“三步曲”来说明: 三步曲: 连线 切线 旋转 连线: 将兄弟结点连接起来 切线: 保留双亲到第一个子女的连线,将双亲到其它子女的连线切掉。 旋转:以根为轴,平面向下顺时针方向旋转450。 2、                 二叉树转为树林 二叉树转换成树(树林)时结果也是唯一的。 其转换可以递归的描述,若二叉树为空,则树(树林)为空;否则,二叉树的根是树(树林)中第一棵树的根,二叉树的左子树构成树(树林)中第一棵树除去根结点后的子树林,二叉树的右子树构成树林中除去第一棵树后的树林。 形象的说是上面三步曲的逆。 6·5·2 树的存储结构 1、          双亲链表表示法 以一组连续的存储空间存放树的结点,每个结点中附设一个指针指示其双亲结点在这连续的存储空间中的位置(下标,这种结构属静态链表) ,可形式表示如下: #define maxnode 32 typrdef struct { datatype data; int parent; }ptree; ptree T[maxnode]; 2、          孩子链表表示法 用多重链表表示。有两种方法:同构:按最大度的结点设置各结点结构,即一个数据域和d个指针域,这容易造成空间浪费;异构:结点有几棵子树设几个指针,这样操作困难。可将其子女链在一个单链表中。其形式描述如下: typrdef struct cnode /* 表结点 */ { int child; struct cnode *next; }link, typedef struct /* 头结点 */ {datatype data; link *headptr; }ctree; ctree T[maxnode]; /* 表头数组 */ 带双亲的孩子链表表示法: typedef struct /* 头结点 */ {datatype data; int parent; link headptr; }headnode1; 3、          孩子兄弟表示法 该方法又称二叉树表示法,或二叉链表表示法,即以二叉链表作存储结构,结点的两个链域分别指向该结点的第一个孩子和下一个兄弟,分别命名为fch和nsib。可形式描述如下: typedef struct treenode {datatype data; struct treenode *fch,*nsib; }treenode ,*tree; 树的这种表示本质上是二叉树的二叉链表表示。由于二叉树和树这种存储结构的一致性,从而导致树和二叉树可以相互转换。 6·5·3 树和森林的遍历 树的遍历方法也可分为“宽度优先法”和“深度优先法”两类。前者指从(根)第一层开始,由上到下,从左往右逐个结点的遍历;后者又可分为先根次序和后根次序。 (1)先根次序的遍历(相当于对其相应的二叉树的先序遍历) 若树(森林)为空,则空操作,否则: ·访问左面第一棵树的根; ·按先根次序从左到右遍历此根下的子树; ·按先根次序从左到右遍历除第一棵树外的树(森林)。 (2)后根次序的遍历(相当于对其相应的二叉树的中序遍历) 若树(森林)为空,则空操作,否则: ·按后根次序从左到右遍历最左面的树下的子树; ·访问最左面树的根; ·按后根次序从左到右遍历除第一棵树外的树(森林); 6·6 哈夫曼树及其应用   6·6·1 最优二叉树(哈夫曼树----带权路径长度最短的树) 1、          哈夫曼树的基本概念 (1) 路径 从树中一个结点(向下)到另一个结点之间的分支。 (2) 路径长度 路径上的分支数目称为路径长度。 (3) 树的路径长度 从树根到每一结点的路径长度之和,称为树的路径长度,完全二叉树是路径长度最短的二叉树。 (4) 结点的带权路径长度 从该结点到树根之间的路径长度和结点上权的乘积。 (5) 树的带权路径长度 (6) 哈夫曼树(最优二叉树) 带权路径长度之和最小的二叉树称为哈夫曼树(最优二叉树) (7) 哈夫曼编码 在哈夫曼树上,左分枝为0,右分枝为1,从根结点开始,直到叶子结点所组成的编码序列,称为叶子结点的哈夫曼编码。 2、          哈夫曼树在判定问题中的应用 将百分制转为五级记分制的例子。说明哈夫曼树是判定次数最少的树(即带权路径长度最短、最节省计算时间。各级比例 5%,15%,40%,30%,10%) 3、          如何构造哈夫曼树 (1) 根据给定的n个权值{w1,w2,…,wn},构成n棵二叉树的集合F={T1,T2,…,Tn},每棵二叉树Ti只有根结点。 (2) 在F中选两棵根结点权值最小的树作为左右子树,构造一棵二叉树,新二叉树根结点的权值等于其左右子树根结点权值之和。 (3) 在F中删除这两棵子树,同时将新得到的二叉树加入F中。 (4) 重复(2)和(3),直到F中只剩一棵树(即哈夫曼树)为止。 举例说明这一过程: 应该说明,哈夫曼树的形态不是唯一的,但对具有一组权值的各哈夫曼树的WPL是唯一的。 6·6·2 哈夫曼编码 1、          哈夫曼编码提出的背景 (1) 如何使电报编码变短,非前缀编码出现二义性。 (2) 用二叉树可以构造前缀编码。 (3) 由哈夫曼树得到最优编码。   第七章 图的概念和存储结构   图是重要的一类非线性结构,应用极为广泛。图最早的应用一般都引用16世纪东普鲁士的七桥问题。本章只介绍图的基本概念、存储结构、图的遍历和简单应用。   7·1 图的概念   1、          图的定义 图是一种数据结构,其形式化定义可写为 Graph=(V,R) 其中,V={x|xdatatype} 2、          图的术语概念 (1)         有向图、无向图 (2)         有(无)向完全图 稀疏图 稠密图 子图 无向完全图:n个顶点n(n-1)/2条边; 有向完全图:n个顶点n(n-1)条弧; (3)         权、网 和边(弧)相关的数叫权,带权的图称网。 (4)         邻接、邻接点 无向图:一条边连起来的两个顶点,互称邻接点; 有向图:若从顶点x到顶点y有一条弧,则说顶点x邻接到顶点y,而顶点y邻接自顶点x。 (5)         度、出度、入度 (6)         路径、路径长度、回路(环)、简单路径 (7)         连通、连通图、连通分量 无向图顶点v1到顶点v2有路径,则说v1和v2连通。若任意两个顶点都连通,则说该图是连通的。连通分量是无向图中的极大连通子图。 (8)         强连通图、强连通分量 (9)         生成树、有向树、生成森林 一个连通图的生成树是一个极小连通子图,它含有图的全部顶点,但只有足以构成一棵树的n-1条边。 7·2 图的存储结构 7·2·1 图的顺序存储结构----数组表示法 1、          数组表示法 用两个数组分别表示数据元素的(顶点)的信息和边(弧)的信息。 typedef struct {vextype vexs[n]; adjtype arcs[n][n]; }graph; 若顶点只有编号信息,边(弧)只是有无,则可用下面的邻接矩阵来表示。 2、          邻接矩阵的定义 3、          无向图邻接矩阵的性质 (1)     无向图的邻接矩阵是对称矩阵; (2)     顶点vi的度是邻接矩阵中第i行(或第i列)的元素(1)之和。 4、          有向图邻接矩阵的性质 (1)     有向图的邻接矩阵不一定是对称矩阵; (2)     顶点vi的出度是邻接矩阵中第i行元素之和,入度是邻接矩阵中第i列的元素之和 5、          网的邻接矩阵 将邻接矩阵中的0、1换成权值,就是网的邻接矩阵。 6、          邻接矩阵的优缺点 容易实现图的前4个操作。 容易判定顶点间有无边(弧),容易计算顶点的度(出度、入度);缺点是所占空间只和顶点个数有关,和边数无关,在边数较少时,空间浪费较大。 7、          建立邻接矩阵的算法 7·2·2 图的邻接表表示法 邻接矩阵在稀疏图时空间浪费较大,为了克服这一缺点,可采用邻接表表示法。 1、          邻接表的结点结构 (1)顶点结点结构 vertex link (2)边(弧)结点结构 adjvex info next 其中,vertex是顶点数据,link是指向该顶点第一个邻接点的指针,adjvex是邻接点在向量中的下标,info是邻接点的信息,next是指向下一邻接点的指针。 2、          邻接表是顶点的向量结构和边(弧)的单链表结构 每个顶点结点包括两个域,将n个顶点放在一个向量中(称为顺序存储的结点表);一个顶点的所有邻接点链接成单链表,该顶点在向量中有一个指针域指向其第一个邻接点。 3、          邻接表的优缺点 空间较省; 无向图容易求各顶点的度;边表中结点个数是边的两倍; 有向图容易求顶点的出度;若求顶点的入度则不容易,要遍历整个表。为了求顶点的入度,有时可设逆邻接表(指向某顶点的邻接点链接成单链表) 4、          建立邻接表的算法  7·3 图的遍历   图的遍历指,从图的某顶点出发,访问图的各顶点,使每个顶点被访问一次,且只被访问一次。访问的含义可以是输出各顶点的值,查询顶点,修改顶点等等。 本节介绍图的遍历的两种方法:深度优先遍历和宽度优先遍历,还介绍生成树的概念。为了遍历方便,设辅助数组visited,初始时,数组元素的值均为0或false,表示未被遍历,一旦遍历,就置为1或true。 6·3·1 深度优先遍历 1、          深度优先遍历的思想 在图中从任意一个顶点(设为v0)开始,进行遍历,接着找v0的第一邻接点,若该邻接点未被遍历,则遍历之,再找该邻接点的第一邻接点,若该第一邻接点已被遍历,则找其下一邻接点。若下一邻接点未被遍历,则遍历,再找它的第一邻接点,就这样递归向下进行。若遇到第一邻接点不存在,或下一邻接点也不存在时,则退回到调用的上一层。如此下去,若不能遍历完所有顶点(说明不是连通图),则再选一个未遍历的顶点,重新开始以上过程,直至所有顶点遍历完毕。 3、          深度优先遍历的算法 int visited[MAX+1] /*辅助数组,是算法中需用到的全局变量 */ void dfs(graph g[MAX+1],int v) /* 从图g的第v号顶点出发深度优先遍历 */ { edgenode *p; printf(“6d”,g[v].vertex) /* 首先访问该顶点,假设其数据为整数 */ visited[v]=1; p=g[v].link; while(p) { if(visited[p->adjvex]!=l) dfs(g,p->adjvex); /* 若该顶点末被访问过,则递归调用 */ p=p->next; /* p指向下一个与第v个顶点链接的表结点 */ } } void dfstravel(graph g[MAX+1],int n) /* 深度优先遍历顶点个数为n的图g */ { int v; for (v=1;v<=n;v++) visited[v]=0; /*初始化辅助数组,表示所有顶点均末被访问过 */ for (v=1;v<=n;v++) /*对图中所有未被访问过的顶点进行深度优先搜索*/ if (visited[v]!=1) dfs(g,v) } 4、          深度优先遍历生成树 图的所有顶点加上遍历中经过的边所构成的子图叫图的生成树。 5、          深度优先遍历算法分析 对于连通图,在dfstravel函数中只要调用一次dfs,即可遍历图中所有顶点。对于非连通图,有几个连通分量,则调用几次。由此,也知道了如何求连通分量的个数。 当用二维数组表示邻接矩阵作为图的存储结构时,查找每个顶点的邻接点所需时间为O(n2),其中n为图中顶点数。而当以邻接表作图的存储结构时,找邻接点所需时间为O(e),其中e为无向图的边数或有向图的弧数。由此,当以邻接表作存储结构时,深度优先遍历图的时间复杂度为0(n+e)。 6·3·2 宽度优先遍历          宽度优先遍历的基本思想 宽度优先遍历又称广度优先遍历,和树的层次遍历类似。从图中任意一个顶点(设为v0)开始遍历,接着依次遍历v0的所有邻接点(每个邻接点被遍历一次且只一次),再遍历这些邻接点的邻接点,……。如此下去,若不能遍历完所有顶点(说明不是连通图),则再选一个未遍历的顶点,重新开始以上过程,直至所有顶点遍历完毕。   7·4 生成树和最小生成树   1、          生成树 对于连通图,调用DFS或BFS所经过的边的集合和图的全部顶点构成了图的极小连通子图,即连通图的一棵生成树。 2、 最小生成树 (1)问题的提出 假设n个城市间建立通信联络网,连通n个城市需要n-1条线路,而n个城市间最多有n(n-1)/2条线路,如何从n(n-1)/2条中选取n-1条线路,使总的耗费最少。 (2)由无向连通图构造最小生成树的方法 ·从图中任意顶点开始,将其包括在最小生成树中; ·再选取权值最小的边,使其一个顶点已在生成树中,而另一个顶点尚不在生成树中,将该顶点加入生成树。若这样的边有多个,任选一个。 ·重复上步,直至所有顶点都包括在生成树中。这就是最小生成树。 具体说,构造最小生成树有两种方法:普里母(prim)和克鲁斯卡尔(kruskal)方法。 (3)生成最小生成树的算法  7·5 最短路径   网络中的常见问题:两点间是否有通路,哪条路径最短。本书讨论两类问题:一类是从一个顶点到其它顶点间的最短路径,另一类是任意两顶点间的最短路径。这都是有向图的应用。 单源最短路径 这里路径指两顶点间的通路,路径的长度指所有经过的边的总长。“最短路径”的问题指当两个顶点间通路多于一条时,如何找出边长总和为最短的那条。Dijkstra提出按路径长度递增的次序求最短路径的方法。 1、          Dijkstra 求最短路径的基本思想 把顶点分成两组,第一组是已确定最短路径的结点的集合,第二组是尚未确定最短路径的结点的集合。按路径长度递增的次序逐个把第二组的顶点放到第一组中。设求从v1到其它各顶点间的最短路径,则在任意时刻,从v1到第一组各顶点间的最短路径都不大于从v1到第二组各顶点间的最短路径。 2、     Dijkstra 求最短路径的步骤 7·6 拓扑排序   1、拓扑排序的基本概念 (1)AOV网 顶点表示活动,弧表示活动间的优先关系的有向图,叫顶点表示活动的网(Activity On Vertex Network)。 (2)拓扑序列 将AOV网上的所以顶点排成一个线性序列,且该序列满足若在AOV网中,顶点vi到vj有一条路径,则在该线性序列中vi必在vj的前面。这样的序列称为拓扑序列。 (3)拓扑排序 对AOV网构造拓扑序列的操作叫拓扑排序。 (4)在AOV网中不应有环,否则就会自己以自己为先决条件;若AOV网代表一个工程,则AOV网的一个拓扑序列就是一个工程顺利完成的可行方案。 2、拓扑排序的方法 (1)         从图中选择一个入度为0的顶点输出; (2)         从图中删除该顶点及源自该顶点的所有弧; (3)           重复以上两步,直至全部顶点都输出,拓扑排序顺利完成。否则,若剩有入度非0的顶点,说明图中有环,拓扑排序不能进行。 3、          拓扑排序算法 在邻接表的顶点向量中,向量的每个元素再增加一个入度域,存放各顶点的入度值。输出该顶点,删除源自该顶点的弧就是将该顶点的邻接点的入度减1。实际实现时,可设一个栈,存放入度为0的顶点,退栈就是输出顶点,当邻接点的入度域减1减到0时,就将其入栈,拓扑排序完成时,栈应为空。 Status ToplogicalSort(ALGraph G){ FindInDegree(G,indegree); InitStack(S); for(i=0;inextarc) {k=p>adjvex; if(!(--indegree[k])) Push(S,k); } } if(count,建立AOE网的存储结构。 (2)         从源点v1出发,令ve(1)=0,求 ve(j) 2<=j<=n。 (3)         从汇点vn出发,令vl(n)=ve(n),求 vl(i) 1<=i<=n-1。 (4)         根据各顶点的ve和vl值,求每条弧s(活动)的最早开始时间e(s)和最晚开始时间l(s),其中e(s)=l(s)的为关键活动。 求关键路径是在拓扑排序的前提下进行的,不能进行拓扑排序,自然也不能求关键路径。 5、          求关键路径的实例模拟 6、          求关键路径的算法分析 (1)     求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径; (2)     只有缩短关键活动的工期才有可能缩短工期; (3)     若一个关键活动不在所有的关键路径上,减少它并不能减少工期; (4)     只有在不改变关键路径的前提下,缩短关键活动才能缩短整个工期。       第八章 排序     8·1 基本概念   1、         排序的定义 在排序中结点(数据元素)称为“记录”,记录的集合称为“文件”,内存中的文件也常称为“线性表”。 设n个记录的序列为 {R1,R2,…,Rn} (8—1) 其相应的关键字序列为 {K1,K2,…,Kn} 需确定1,2,…,n的一种排列P1,P2,…,Pn,使关键字有如下关系 Kp1<=Kp2<=…<=Kpn (8—2) 即使式(3—1)的序列成为一个按关键字有序的序列 {Rp1, Rp2,…,Rpn} 这样一种操作称为排序。 2、         排序的分类 内部排序和外部排序。内部排序指待排序文件不大,一次可以在内存中完成的排序,外部排序指待排序文件较大,文件存放在外存上,不能一次调入内存的排序。 内部排序可以分为5大类:插入排序、选择排序、交换排序、分配排序和归并排序。 3、         稳定排序和不稳定排序 若待排序文件中有关键字相等的记录,排序后,其前后相对次序与排序前未发生变化,这种排序称为“稳定”排序,否则是“不稳定”排序。稳定排序与不稳定排序表示所用的排序方法,并不说明哪种方法好与差。 4、         排序中记录的存储方式 顺序存储结构 静态链表 地址排序 5、         排序算法的评价 (1)     算法执行时所需要的时间 最好情况,最差情况,平均情况 (2)   算法执行时所需要的附加空间 如无特别说明,本书排序指记录关键字按递增排序,以数组作为待排序记录文件的存储结构。为简单起见,设关键字为整数,待排序记录的类型说明如下: #define n 待排序记录的个数 typedef struct { int key; datatype other; }rectype; rectype r[n+1]; /* r为结构体数组 */   8·2 插入排序   8·2·1 直接插入排序 1、   直接插入排序的基本思想: 先假定第一个记录是有序序列,然后,从第二个记录开始,依次将记录插入到前边有序的序列中,直至全部记录序列有序。为了避免总要查询文件尾,特设“监视哨”。 2、         直接插入排序的实例模拟 3、         直接插入排序的算法 void straitsort(r,n) /* 本算法对含有n个记录的文件排序*/ int n,r[]; { int i,j; for(i=2,i<=n;i++) /* 假定第一个记录有序 */ { r[0]=r[i]; j=i-1; /* 将待排序记录放进监视哨 */ while (r[0].key=1) /* 最后一个步长取1 */ { for (i=k+1;i<=n;i++) /* 分k组进行直接插入排序 */ { x=r[i]; j=i-k; while (j>0 && x.keyK2),则交换之,然后比较K2和K3,……,直至Kn-1和Kn,这时最大关键字到了最后(第n个位置),这叫一趟起泡排序,进行了n-1次比较。 (2)     重复(1),但只比较到第n-1个元素(关键字),称第二趟比较。 (3)     共进行n-1趟比较,完成整个排序。 2、             起泡排序实例模拟 待排序记录的关键字为 7,2,5,1,9,6,8,3 第一趟起泡排序的结果为 2,5,1,7,6,8,3,[9] 第二趟起泡排序的结果为 2,1,5,6,7,3,[8,9] 第三趟起泡排序的结果为 1,2,5,6,3,[7,8,9] 第四趟起泡排序的结果为 1,2,5,3,[6,7,8,9] 第五趟起泡排序的结果为 1,2,3,[5,6,7,8,9] 第六趟起泡排序的结果为 1,2,3,[5,6,7,8,9] 第六趟起泡排序是必须的,因为第五趟发生了交换。 3、             起泡排序的算法 void bubblesort(r,n) /* r是含有n个记录的待排序文件,本算法按起泡排序方式*/ /* 对其进行排序 */ int n; rectype r[n+1] { register i=1, j, k,flag=1; while (flag && ir[j+1]; flag=1 /* 逆序时交换 */ } i++; /* 进入下一趟起泡排序 */ } } 8·3·2 快速排序 1、         快速排序的基本概念 以第一个记录为“枢轴”,查询记录序列,确定“枢轴“的位置。枢轴将待排序文件分成两部分:枢轴左面的记录的关键字都不大于它的关键字,而枢轴右面的记录的关键字都不小于它的关键字。对枢轴的左右两部分继续实施这一过程,直至全部文件有序。 2  快速排序的算法 (1)     一次划分的算法: int Patition(r,l,h) /* r是下标从l到h的待排序文件,本算法对其进行快速排序的一次划分 */ { int i=l; j=h; rp=r[i]; x=r[i].key; /* 暂存枢轴元素,并提取关键字 */ while (i=x.key ) j--; if (ir[i]; /* 第i个元素和最小元素交换 */ } } 8·4·2 堆排序 1、          堆的定义 堆是一个含有n个关键字{k1,k2,…,kn}的序列,且具有如下特性: ki<=k2i 且 ki<=k2i+1 (1<=i<=n/2) (1) 或 ki>=k2i 且 ki>=k2i+1 (1<=i<=n/2) (2) ki>=k2i 满足式(1)的称为极小化堆,或极小堆,或小堆,满足式(2)的称为极大化堆,或极大堆,或大堆。本节以极小化堆为例子进行讲解。 堆与完全二叉树的关系:堆是n个元素(关键字)的序列,满足完全二叉树顺序存储中结点间的关系(双亲与子女序号间的关系)。 2、          堆排序的基本问题 既然堆顶元素(关键字)是最小元素,所以它是排序序列的最小元素,输出后,将其它元素再调整成堆,新的堆顶元素是排序序列的第二个元素。如此下去,通过堆,可将一个无序序列变为一个有序序列。因此,堆排序的基本问题是: (1)如何建堆 (2)如何调堆 3、          如何调堆 将最后一个元素和堆顶元素交换(相当将堆顶元素输出)后,这时,从堆顶到倒数第二元素,除堆顶元素外,其余元素均符合堆的定义。下面采用筛选法,把包括堆顶元素在内的所有元素调成堆。 Sift(R,i,m) /* 假设R[i+1..m]中各元素满足堆的定义,本算法调整R[i]使序列R[i..ml中各元素满足堆的性质*/ RecTypeR[]; int i,m; { int j=2*i; RecType temp=R[i]; /* 暂存“根”记录R[i] */ while(j<=m) /* j<=m时,R[2i]是R[i]的左孩子 */ { if((jR[j].key) /* 孩子结点关键字最大 */ { R[i]=R[j]; /* 将R[j]换到双亲位置上 */ i=j; j=2*i; /* 修改当前被调整结点 */ } else break; /* 调整完毕,退出循环*/ } R[i]=temp; /* 最初被调整结点放入正确位置 */ } 4、          如何建堆 具有n个结点的完全二叉树,其叶子结点被认为符合堆的定义,其最后一个非终端结点的编号是n/2,若从该结点开始,直到根结点,依次调用上面的筛选法,则可完成堆的建立。具体算法放在下面堆排序算法中。 5、          堆排序算法 Heapsort(R) /* R[1]到R[n]为待排序记录,本算法完成堆排序 */ RecType R[]; { int i; RecType temp; for (i=n/2;i>=1;i--) Sift(R,i,n); /* 初始建堆 */ for (i=n;i>1;i--) { R[1]< -- >R[i] /* 输出堆顶元素 */ Sift(R,1,i-1); /* 调堆 */ } 8·5 归并排序   1、         归并排序的基本思想 设待排序文件有n个记录,开始首先假定这n个记录都是有序的(这是自然的,一个记录当然自己有序)。然后进行归并,将相邻的有序子文件合并成一个较大子文件,如此下去,直至整个文件有序。对于二路归并来说,第一次长1的有序子文件两两归并得到长为2的éù个有序子文件,再两两归并得到长为4的éù个有序子文件,如此下去,直至得到长为n的有序文件。 2、         二路归并排序的算法 (1)    两个有序子文件归并成一个有序子文件 merge(r,r1,low,mid,high) /*r[low]到r[mid]与r[mid+1]到r[high]是两个有序子文件* / /* 本算法将其归并成一个有序子文件从r1[low]到r1[high]*/ rectype r[],r1[]; int low,mid,high; { int i=low; j=mid+1; k=low; while ((i<=mid) && (j<=high)) if (r[i].key<=r[j].key r1[k++]=r[i++]; /*取小者复制*/ else r1[k+=]=r[j++]; while (i<=mid) r1[k++]=r[i++];/*复制第一个文件剩余记录*/ while (j<=high) r1[k++]=r[j++];/*复制第二个文件剩余记录*/ } (2)    一趟归并的算法 mergepass(r,r1,length) /*对r进行一趟归并,结果放在r1中 */ rectype r[],r1[]; int length; /* length是本趟归并的有序子文件的长度*/ {int i=0,j; /*指向第一对子文件起始点 */ while (i+2*length<=n) {merge(r,r1,i,i+length-1,i+2*length-1) i=i+2*length /*指向下一对子文件起始点 */ } if (i+leng-1方块>红心>黑桃;在面值中2<3<4<…<10k) high=mid-1); /* 在左子表查找 */ else low=mid+1; /* 在右子表查找 */ } return(-1) } 3、二分法查找的优缺点 优点:查找速度快; 但表必须有序。 缺点:频繁插入和删除不方便。 二分法查找适于表中元素很少变化而查找频繁的情况;对于查找少而表中元素频繁变化的情况,可用链表作存储结构,进行顺序查找。 9·2·3 分块查找 分块查找综合了顺序查找和二分法查找的优点,既有动态结构,又适于快速查找。          分块查找的基本思想 将待查找文件等长的分为若干个子文件(最后一个子文件长度可能小)。子文件内的元素无序,但子文件之间有序,即第一个子文件的最高关键字小于第二个子文件的最高关键字,第二个子文件的最高关键字小于第三个子文件的最高关键字,依次类推。再建立一个索引表(文件),文件中的每个元素含有各子文件的最高关键字和各子文件中第一个元素的地址(下标),索引文件按关键字有序。 查找时,对索引表可以顺序查找或二分法查找,在块内只能顺序查找。   9·3 树表的查找   适应元素结点的动态插入与删除。 9·3·1 二叉排序树 1、          什么叫二叉排序树 (1)二叉排序树的定义 二叉排序树或为一棵空树,或为具有如下性质的二叉树: · 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; · 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; · 它的左右子树也分别是二叉排序树。 (2)二叉排序树的建立实例 设关键字序列k=(k1,k2,…,km) (m>0),则建立二叉排序树的步骤如下: · 令关键字k1为二叉排序树的根; ·若k1>k2,则k2做k1左子树的根结点,否则做k1右子树的根结点;在子树中继续子树的根比较重复前面的操作; · 对序列中的其它关键字递归使用上面步骤。 例如,给定关键字序列: k=(45,12,53,3,37,100,24,61,90,78) 其建立二叉排序树的过程描述如下。 (3)中序(对称序)遍历二叉排序树所的结点序列是有序序列 对二叉排序树进行中序遍历,其遍历序列是一个有序序列,这是由二叉排序树的定义决定的。 (4)二叉排序树中结点的插入 在二叉排序树中插入结点,只要保证插入结点后的二叉排序树仍然是二叉排序树就行了,插入的结点都是叶子结点,其结果是唯一的。 BSTNode *lnsertBST(t,s) /*将新结点*s插入到t所指的二叉排序树中*/ /*返回插入*s后二叉排序树的根指针*/ BSTNode *s,*t; { BSTNode *f,*p=t; while(p!=NULL) { f=p; /*查找过程中,f指向*P的双亲*/ if(s->key==p->key)return(t); /*树中己有结点*s,无须插入*/ if(s->keykey) p=p->lchild;/*在左子树中查找插入位置*/ elsep=p->rchild; /*在右子树中查找插入位置*/ } if(t==NULL) return(s); /*原树为空,返回S作为根指针*/ if(s->keykey) f->lchild=s; /*将*s插入为*f的左孩子*/ else f->rchild=s; /*将*s插入为*f的左孩子*/ return(t) } (5)二叉排序树中结点的删除 在二叉排序树中删除结点,删除结点后的二叉排序树仍然是二叉排序树,但其结果不是唯一的。而且,当一个结点被删除后,再将其立即插入,所得二叉排序树与结点删除前得二叉排序树一般来说形态不等。 BSTNode *CreatBST() {BSTNode *s,*t==NULL; /*置二叉排序树的初态为空树*/ KeyType key,endflag=0; Datatype data; scanf(“%d”,&key); /*读入一个结点的关键字*/ while(key !=endflag) /*输入未到结束标志时,循环*/ { s=malloc(sizeof(BSTNode)) ;/* 申请新结点*/ s->lchild=s->rchild=null; s->key=key; scanf(“%d”,&data); /*读入结点的其他数据项*/ s->other=data; t=lnserBST(t,s); /*将新结点*s插入到树t中*/ scanf("%d",&key); /*读入下一个结点的关键字*/ } return(t); } 2、          最佳二叉排序树 (1)最佳二叉排序树的定义 有n个结点的二叉树,共有n!个不同的二叉排序树,其中,平均查找(检索)长度最短的那棵二叉排序树叫最佳二叉排序树。 (2)扩充的二叉排序树 将二叉树中度为1和0的结点,都补充上虚结点,使每个结点(除虚结点外)的度均为2,这样的二叉树称为扩充的二叉排序树。设所加虚结点的个数为N,原有结点(称为内部结点)个数为n,由于这时的二叉树无度为1的结点,根据二叉树的性质3,则下式成立: N=n+1 若定义外部路径长度是扩充的二叉树的根到每个外部结点的路径长度之和,用E表示。内部路径长度是指从扩充的二叉树的根到每个内部结点的路径长度之和,用I表示,则下式成立: E=I+2n (3)如何构造最佳二叉排序树。首先将关键字排序,将所得有序表构造静态查找的判定树,所得二叉树即为最佳二叉排序树。判定树是唯一的,但按着最佳二叉排序树的定义,最佳二叉排序树是不唯一的。   

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档