数据结构复习汇编.pptx

《数据结构复习汇编.pptx》由会员分享，可在线阅读，更多相关《数据结构复习汇编.pptx（93页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据结构分为逻辑结构和存储结构（物理结构）第1页/共93页数据的逻辑结构：数据的逻辑结构：数据元素之间的逻辑关系，分：数据元素之间的逻辑关系，分：集合集合数据元素间除数据元素间除“同属于一个集合同属于一个集合”外，外，无其它关系无其它关系 线性结构线性结构一个对一个，如线性表、栈、队列一个对一个，如线性表、栈、队列 树形结构树形结构一个对多个，如树一个对多个，如树 图状结构图状结构多个对多个，如图或网多个对多个，如图或网概念及术语概念及术语第2页/共93页数据的存储结构数据的存储结构数据的逻辑结构在计算

2、机存储设备中的映射，分：顺数据的逻辑结构在计算机存储设备中的映射，分：顺序存储结构、链式存储结构。序存储结构、链式存储结构。n顺序存储：以相对的存储位置表示逻辑关系以相对的存储位置表示逻辑关系 n链式存储以以附加指针表示后继关系以以附加指针表示后继关系 a1 a2 a3a2 a1概念及术语概念及术语第3页/共93页2算法和算法分析1算法概念 对特定问题求解步骤的一种描述，是指令的有限序列，每条指令表示一个或多个操作。算法应具备的特性算法应具备的特性：（2 2）确定性：指令具有确切的含义，相同的输入有相同指令具有确切的含义，相同的输入有相同的输出。的输出。（1 1）有穷性：对合法的输入值在执行有

3、穷步之后结束。对合法的输入值在执行有穷步之后结束。（3 3）可行性：所有操作可经已实现的基本运算执行有限所有操作可经已实现的基本运算执行有限次来实现次来实现（4 4）输入：0 0个或多个个或多个（5 5）输出：一个或多个一个或多个第4页/共93页（2 2）可读性：便于阅读和交流便于阅读和交流（3 3）健壮性：能够对输入的非法数据作出反应和处理能够对输入的非法数据作出反应和处理（4 4）效率与低存储量需求：效率指算法的执行时间；存：效率指算法的执行时间；存储量需储量需 求指算法执行过程中所需要的最大存储空间。求指算法执行过程中所需要的最大存储空间。2算法设计的要求（1 1）正确性：算法应满足具体

4、问题的需求。算法应满足具体问题的需求。a.a.程序不含语法错误程序不含语法错误b.b.对于几组输入可得满足要求的结果对于几组输入可得满足要求的结果c.c.对于精心选择的几组典型、苛刻、带有刁难性的输对于精心选择的几组典型、苛刻、带有刁难性的输入数据可得满足要求的结果入数据可得满足要求的结果 d.d.对一切合法的输入数据都能得出产生要求的结果对一切合法的输入数据都能得出产生要求的结果 第5页/共93页3 3算法效率的度量算法效率的度量算法的时间效率主要由两个因素决定：l所需处理问题的数据量大小，数据量大，所花费的时间就多；l在解决问题的过程中，基本操作的执行次数 时间复杂度：算法中基本操作重复执

5、行的次数是问题规模n的某个函数，T(n)=O(f(n)好的算法应该能够在数据量n增长的同时，函数T(n)的增长速度比较缓慢。第6页/共93页 常见函数的增长率第7页/共93页一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。总时间由一个常数(即零次多项式)来限界。一个时间为O(n2)的算法由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。关系为:O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为：O(2n)O(n!)O(nn)第8页/共93页 第二章第9页/共93页1线性表：是n0个性质相同的数据元素的有限序列。线性表可记作（a1,a2

6、,an）n 0基本操作：建立、存取、插入、删除、检索、分解、排序等。第10页/共93页(a1,ai-1,ai,an)改变为(a1,ai-1,e,ai,an)a1a2ai-1ai ana1a2ai-1ai ean表的长度加12基本运算1.在线性表第i（1i n+1）个位置上插入元素e第11页/共93页注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是l.elemi-1。status insert_sq(Sqlist&L，elemtype e，int i)if(iL.length+1)/检查i值是否合理 return ERROR;if(L.length=

7、ListSize)/判断是否溢出 exit(overflow);for(j=L.length-1;j=i-1;j-)L.elemj+1=L.elemj;/腾出第i个位置 L.elemi-1=e;/插入 L.length+;/当前表长加1 return OK;第12页/共93页 这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的元素后移语句上，所需移动元素的次数不仅依赖于表的长度，而且还与插入位置有关。i位置移动次数 1n 2n-1 in-i+1 n+10平均移动次数：时间复杂度：O（n）第13页/共93页(a1,ai-1,ai,ai+1,an)改变为(a1,ai-1,ai+1

8、,an)ai+1 an表的长度减1a1a2ai-1aiai+1 ana1a2ai-12.2.在线性表中删除第i i（1 i n1 i n）个元素，使第14页/共93页status delete_sq(Sqlist&L,int i,elemtype&e)if(iL.length)/检查i值是否合理return ERROR;e=L.elemi-1;/C下标从0开始 for(j=i;j=L.length-1;j+)L.elem j-1=L.elem j;/删除 L.length-;return OK;第15页/共93页该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。i位置移动

9、次数 1n-1 2n-2 in-i n0平均移动次数：时间复杂度：O（n）第16页/共93页第三章第三章 栈和队列栈和队列栈和队列也可以被称作为操栈和队列也可以被称作为操作受限的线性表。作受限的线性表。第17页/共93页思考：假设有思考：假设有A,B,CA,B,C三个元素进三个元素进S S栈的顺序是栈的顺序是A,B,CA,B,C，写出所有可能的出栈序列。写出所有可能的出栈序列。CBAACBABCCABBACBCA第18页/共93页1.栈属于加了限制条件的线性结构；栈属于加了限制条件的线性结构；2.栈是后进先出的线性表；栈是后进先出的线性表；3.进栈和出栈只能从栈顶进行；进栈和出栈只能从栈顶进行

10、；4.栈中的元素个数可以是栈中的元素个数可以是0（空栈）；（空栈）；5.栈的元素的个数不能是无穷多个；栈的元素的个数不能是无穷多个；6.每个栈中的元素的类型相同每个栈中的元素的类型相同.栈的特性第19页/共93页队列（队列（queuequeue）是一种只允许）是一种只允许在一端进行插入，而在另一端进行在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限删除的线性表，它是一种操作受限的线性表。的线性表。3.2 3.2 队列队列 (Queue)Queue)队列的定义及其运算队列的定义及其运算第20页/共93页n n定义u u允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(re

11、ar)。n n特性u u先进先出(FIFO,First In First Out)a0 a1 a2 an-1frontrear第21页/共93页依次 1 2 3 4 5 6 删除两个元素之后的头元素是？第22页/共93页第四章 串 零个或多个字符组成的有限序列。一般记S=a1a2.an 其中，S是串名，单引号括起的字符序列是串值；2 2、串长 串中所包含的字符个数3 3、空串长度为零的串，它不包含任何字符。1 1、串4 4、空格串由一个或多个空格组成的串，其长度为串中空格字符的个数。第23页/共93页第五章第24页/共93页5.3 广义表的定义一、广义表（General List）1.广义表中

12、的元素即可以是单个元素（称为原子）也可以是广义表（称为子表）。2.一般表示：LS=(a1,a2,an)3.习惯上广义表名用大写字母，原子用小写字母4.当LS非空时，a1称为LS 的表头（head），其余元素组成的表（a2,an）称为表尾（tail）。第25页/共93页例：A=()B=(e)C=(a,(b,c,d)D=(A,B,C)E=(a,E)F=(a,b,(c,(d)广义表特点：允许递归，可共享子表元素不仅有先后次序，而且有层次关系元素的层次：是包括该元素的括号对数表深：广义表中元素的最大层次第26页/共93页2广义表的存储结构（通常用链式）广义表的扩展线性链表存储typedef struc

13、t glnodeint tag;/0 原子结点；1 子表结点union atomtype atom;/原子结点的值域 struct glnode*hp;/子表表头指针struct glnode*next;/下一元素指针*glist;第27页/共93页例：A=();B=(e);C=(a,(b,c,d);D=(A,B,C);E=(a,E)都设一附加表头结点1 A1B0 e 1C0a10 b0 c0 d 11 11D10 a1E第28页/共93页作业练习求下列广义表操作的结果：GetHead【(p,h,w)】；GetTail【(b,k,p,h)】；GetHead【(a,b),(c,d)】；GetTa

14、il【(a,b),(c,d)】；GetHead【GetTail【(a,b),(c,d)】GetTail【GetHead【(a,b),(c,d)】GetHead【GetTail【GetHead【(a,b),(c,d)】GetTail【GetHead【GetTail【(a,b),(c,d)】第29页/共93页第六章第30页/共93页ABCDEFGHK例如：例如：先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A二叉树的遍历层次序列：层次序列：A B E C F D G H K第31页/共

15、93页根据二叉树的遍历构造二叉树3 3结点的结点的5 5棵二叉树的棵二叉树的3 3种遍历序种遍历序列如表所示。存在情况列如表所示。存在情况:ABCABCABCABCCAB第32页/共93页因此，对因此，对3 3种遍序序列有结论：种遍序序列有结论：（1 1）由先序遍历序列和中序遍历）由先序遍历序列和中序遍历序列能够唯一确定一棵二叉树。序列能够唯一确定一棵二叉树。（2 2）由后序遍历序列和中序遍历）由后序遍历序列和中序遍历序列能够唯一确定一棵二叉树。序列能够唯一确定一棵二叉树。（3 3）由先序遍历序列和后序遍历）由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。序列不能唯一确定一棵二叉树。第33

16、页/共93页例如：已知二叉树BT的后序遍历序列为：CBEHGIFDA，中序遍历序列为：BCAEDGHFI，请构造这棵二叉树T。A ABCBCDEFDEFGHIGHIA ADEFDEFGHIGHIB BC CFGHFGHI IA AB BC CD DE EGHGHA AB BC CD DE EF FI IA AB BC CD DE EF FH HG GI I由中序遍历序列和后序遍历序列构造二叉树的过程示意由中序遍历序列和后序遍历序列构造二叉树的过程示意第34页/共93页平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：(1)左、右子树都是平衡二叉树；(2)左、右子树高度差的绝对值=1。若

17、把左子树与右子树高度之差称为结点x的平衡因子(balance factor)，用bf(x)表示。则由平衡二叉树定义知:Bf(x)=x左子树深度-x右子树深度1.平衡二叉树的定义第35页/共93页91000065504741853060727842-330-202141853060727842-1110010a.非平衡二叉树 b.平衡二叉树 所有结点的平衡因子只能所有结点的平衡因子只能取取-1-1，0 0，1 1三个值之一。三个值之一。第36页/共93页6.2 堆排序堆是一棵顺序存储的完全二叉树，堆是一棵顺序存储的完全二叉树，若每个结点的关键字都不小（大）于其若每个结点的关键字都不小（大）于其孩

18、子结点的关键字，则称为大（小）根孩子结点的关键字，则称为大（小）根堆。堆。968338112791236854724305391第37页/共93页堆排序的基本思想是：首先，按堆排序的基本思想是：首先，按堆的定义将堆的定义将R1.nR1.n调整为堆（这个过调整为堆（这个过程称为初始建堆），交换程称为初始建堆），交换R1R1和和RnRn；然后，将；然后，将R1.n-1R1.n-1调整为堆，交换调整为堆，交换R1R1和和Rn-1Rn-1；如此反复进行，直到；如此反复进行，直到交换了交换了R1R1和和R2R2为止。为止。第38页/共93页6.3.1 哈夫曼树的定义设二叉树具有设二叉树具有n n个带权值

19、的叶子结个带权值的叶子结点，那么从根结点到各个叶子结点的点，那么从根结点到各个叶子结点的路径长度路径长度l li i与相应结点权值与相应结点权值w wi i的乘积的的乘积的和，称为二叉树的带权路径长度，记和，称为二叉树的带权路径长度，记作：作：WPL=13+33+22+41=20WPL=13+33+22+41=20。第39页/共93页6.3.2 哈夫曼树的构造（1 1）由给定的）由给定的n n个权值个权值WW1 1,W,W2 2,W,Wn n 构造构造n n棵只有一个叶子结棵只有一个叶子结点的二叉树，从而得到一个二叉树的集点的二叉树，从而得到一个二叉树的集合合F=TF=T1 1,T,T2 2,

20、T,Tn n。（2 2）在）在F F中选取根结点的权值最小中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，新二叉树根结点的造一棵新的二叉树，新二叉树根结点的权值为其左、右子树根结点权值之和。权值为其左、右子树根结点权值之和。第40页/共93页（3 3）在集合）在集合F F中删除作为左、右子中删除作为左、右子树的两棵二叉树，并将新建立的二叉树树的两棵二叉树，并将新建立的二叉树加入到集合加入到集合F F中。中。（4 4）重复（）重复（2 2）、（）、（3 3）两步，当）两步，当F F中只剩下一棵二叉树时，这棵二叉树便中只剩下一棵二叉树时，

21、这棵二叉树便是所要建立的哈夫曼树。是所要建立的哈夫曼树。注：如此建造的二叉树，没有度为注：如此建造的二叉树，没有度为1 1的结点。如有的结点。如有n n个叶子，必有个叶子，必有m=2n-1m=2n-1个个结点。结点。第41页/共93页9例如:已知权值 W=5,6,2,9,7562752769767139527第42页/共93页67139527952716671329WPL=(6+7+9)*2+(5+2)*3=22*2+7*3=44+21=65注意：1.只算叶子2.分层计算3.路径长为层数减1第43页/共93页快速远距传输电文时，为使电文尽量短，采用不等长编码，且使用频高的字符用较短的码。并且使

22、任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。利用赫夫曼树可以构造出一种最优前缀编码使所传电文的总长度最短,这种编码就是赫夫曼编码。6.3.3 赫夫曼编码第44页/共93页例：已知某通信息流只用8种字符，出现频率为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计赫夫曼编码。设W=(5,29,7,8,14,23,3,11),n=8,则m=15.351123714291111111000000082300291011010141105011301117111081111第45页/共93页哈夫曼树和编码的代码实现序号权重父号左子右子17219324

23、6532637218109101112131415W=7,19,2,6,32,3,21,10N=8 m=2*8-1=159953610101194111117181212281011131340271414601251515100131410010210300000400015016000017118001112345678第46页/共93页第7章 图 7.1 图的基本概念 7.1.1 图的定义图是一种非线性结构图是一种非线性结构,它比树形结它比树形结构更复杂构更复杂.图中的数据元素之间是多对图中的数据元素之间是多对多关系多关系,每一个元素都可能与其他元素每一个元素都可能与其他元素有关有关.图

24、是由一个非空的顶点集合和一个图是由一个非空的顶点集合和一个描述顶点之间关系即边（或者弧）的集描述顶点之间关系即边（或者弧）的集合组成合组成.第47页/共93页7.2 图的存储结构 7.2.1 邻接矩阵邻接矩阵是表示顶点之间相邻关系的邻接矩阵是表示顶点之间相邻关系的矩阵。设矩阵。设G=(V,E)G=(V,E)是具有是具有n n个顶点的图，则个顶点的图，则G G的邻接矩阵是的邻接矩阵是n n阶方阵定义阶方阵定义A A：若若G G是网，则邻接矩阵可定义为：是网，则邻接矩阵可定义为：第48页/共93页Aij=0(i,j)VR1(i,j)VRBACDFE例如例如:矩阵的元素为矩阵的元素为ABCDEFAB

25、CDEF无向图无向图-对称矩阵，半对称矩阵，半存即可，节省空间。每行存即可，节省空间。每行(列列)数字和即是顶点的度数字和即是顶点的度第49页/共93页有向图的邻接矩有向图的邻接矩阵为非对称矩阵阵为非对称矩阵ABECDABCDEABCDE行和为出度行和为出度列和为入度列和为入度第50页/共93页有向网的邻接矩有向网的邻接矩阵为非对称矩阵阵为非对称矩阵ABECDABCDEABCDE121731 5第51页/共93页7.3.2 深度优先搜索深度优先搜索的基本思想是：深度优先搜索的基本思想是：从图从图G G中某个顶点中某个顶点vivi出发，访出发，访问问vivi，然后选择一个与，然后选择一个与viv

26、i相邻且没相邻且没被访问过的顶点被访问过的顶点v v访问，再从访问，再从v v出发出发选择一个与选择一个与v v相邻且未被访问的顶相邻且未被访问的顶点点vjvj访问，依次继续。访问，依次继续。第52页/共93页如果当前已访问过的顶点的如果当前已访问过的顶点的所有邻接顶点都已被访问，则回所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点一个拥有未被访问的相邻顶点w w，从从w w出发按同样方法向前遍历。直出发按同样方法向前遍历。直到图中所有顶点都被访问。到图中所有顶点都被访问。第53页/共93页从图中某个顶点顶点V0出发，访问此顶点，然

27、后依次从依次从V0的的各个未被访问各个未被访问的的邻接点出发深度优先搜索遍历图邻接点出发深度优先搜索遍历图，直至图中所有都被访问到。为确定每一个结点是否被访问，必须设置访问标志。一、连通图的深度优先搜索遍历一、连通图的深度优先搜索遍历第54页/共93页achdekf8234570F F F F F F F F F012345678TTTT TT Tach d kfe achkfed访问标志访问标志:访问次序访问次序:例如例如:achdkfe第55页/共93页7.4 最小生成树在一个无向连通图在一个无向连通图G G中，如果取它中，如果取它的全部顶点和一部分边构成一个子图的全部顶点和一部分边构成一

28、个子图GG，即：，即：V(G)=V(G)V(G)=V(G)和和 E(G)E(G)E(G)E(G)若边集若边集E(GE(G)中的边，既将图中的边，既将图G G中中的所有顶点连通，又不形成回路，则称的所有顶点连通，又不形成回路，则称子图子图GG是原图是原图G G的一棵生成树。的一棵生成树。产生最小生成树主要有两个算法，产生最小生成树主要有两个算法，即普里姆算法和克鲁斯卡尔算法。即普里姆算法和克鲁斯卡尔算法。第56页/共93页7.4.2 普里姆算法普里姆普里姆(PrimPrim)算法的思路是：算法的思路是：假设假设G=(V,E)G=(V,E)是一个具有是一个具有n n个顶点的个顶点的连通网，连通网，

29、T=(U,TE)T=(U,TE)是是G G的最小生成树，的最小生成树，其中其中U U是是T T的顶点集，的顶点集，TETE是是T T的边集，的边集，U U和和TETE的初值均为空。的初值均为空。第57页/共93页算法开始时，首先从算法开始时，首先从V V中任取一个中任取一个顶点（假定取顶点（假定取v0v0），将它并入），将它并入U U中，中，此时此时U=v0U=v0，然后只要，然后只要U U是是V V的真子集的真子集（即（即U U V V），就从那些其一个端点已），就从那些其一个端点已在在T T中，另一个端点仍在中，另一个端点仍在T T外的所有边外的所有边中，找一条最短（即权值最小）边，中，找

30、一条最短（即权值最小）边，假定为假定为(vi,vj)(vi,vj)，其中，其中 viUviU，vjV-UvjV-U，并把该边，并把该边(vi,vj)(vi,vj)和顶点和顶点vjvj分别并入分别并入T T的边集的边集TETE和顶点集和顶点集U U。第58页/共93页V0V3V5V2V1V46453821756V01V2closedge i12345AdjvexLowcostV0V1V2V3V4V5V0V1V2V3V4V5v06v01v070v25v26v2440V5v55v5220V350V1v1330V41+4+2+5+3=15例如：UV-U第59页/共93页7.7 AOE网与关键路径若在带

31、权的有向图中，以顶点若在带权的有向图中，以顶点表示事件，有向边表示活动，边上表示事件，有向边表示活动，边上的权值表示完成该活动的开销（如的权值表示完成该活动的开销（如该活动所需的时间），则称此带权该活动所需的时间），则称此带权的有向图为用边表示活动的网络，的有向图为用边表示活动的网络，简称简称AOEAOE网（网（Activity On Edge Activity On Edge networknetwork）。）。第60页/共93页在一个表示工程的在一个表示工程的AOEAOE网中，网中，应该不存在回路，网中仅存在一应该不存在回路，网中仅存在一个入度为个入度为0 0的顶点（事件），称为的顶点（事

32、件），称为开始顶点（源点），它表示了整开始顶点（源点），它表示了整个工程的开始；个工程的开始；网中也仅存在一个出度为网中也仅存在一个出度为0 0的的顶点（事件），称为结束顶点顶点（事件），称为结束顶点（汇点），它表示整个工程的结（汇点），它表示整个工程的结束。束。第61页/共93页在寻找关键活动时所用到的几个在寻找关键活动时所用到的几个参量的定义：参量的定义：（1 1）事件）事件vkvk的最早发生时间的最早发生时间（2 2）事件）事件vkvk的最迟发生时间的最迟发生时间（3 3）活动）活动aiai的最早开始时间的最早开始时间（4 4）活动）活动aiai的最迟开始时间的最迟开始时间第62页/共9

33、3页因AOV网中的活动可以并行，故工程完成的最短时间为从源点源点到汇点汇点的最长路径(关键路径关键路径)。abcdefghk64521187244例如例如:“关键活动”是：关键路径上的活动，权值增关键路径上的活动，权值增加加将使有向图上的最长路径的长度增加。最长路径的长度增加。源点汇点6174关键路径a-b-e-h-k第63页/共93页把从源点到顶点j的最长路径长度叫做事件(顶点)的最早发生时间ve(j);它是可能发生的最早时间。把从顶点k到汇点的最短路径长度叫做事件(顶点)的最迟发生时间vl(k).它是在不推迟工期的前提下最迟必须开始的时间。第64页/共93页事件发生时间的计算公式:ve(源

34、点)=0;ve(k)=Maxve(j)+dut()例如：ve(k)=18,ve(h)=14,ve(f)=7;vl(汇点)=ve(汇点);vl(j)=Minvl(k)dut()例如:vl(k)=18,vl(h)=14,vl(f)=10。第65页/共93页设第i条弧为则对第i项活动言,“活动(弧)”的最早开始时间e(i)e(i)=ve(j);e()=14;e()=7;“活动(弧)”的最迟开始时间l(i)l(i)=vl(k)dut();l()=14;e()=10。jkdut第66页/共93页什么是“关键活动关键活动”？该活动的该活动的最早最早开始时间开始时间 =该活动的该活动的最迟最迟开始时间开始时

35、间在关键路径上,e(h,k)=l(h,k),不在关键路径上e(f,h)=7,l(f,h)=10，推迟开始或延迟3天均不影响工期。第67页/共93页abcdefghk645211872440000000006457115 715 14 1818181818181818181816 1486610807拓扑有序序列拓扑有序序列:a-d-f-c-b-e-h-g-k第68页/共93页06457715 14 181814161078660000645777 15 14141602366887 10第69页/共93页 算法的实现要点算法的实现要点:显然，求ve的顺序应该是按拓扑有序拓扑有序的次序;而求vl

36、的顺序应该是按拓扑逆序拓扑逆序的次序;因为拓扑逆序序列即为拓扑有序序列的 逆序列逆序列，因此应该在拓扑排序的过程中，另设一个“栈栈”记下拓扑有序序列。第70页/共93页8.2 二 分 查 找n所谓有序表有序表,即表中的各元素按关键字的值升序(或降序)存放。n折半查找又称二分查找,是查找有序表的简单、有效的常用方法。n基本思想：设低高端指针为L、H,则选取中间记录M=(L+H)/2,将其关键字与给定关键字k进行比较,若相等,则查找成功；第71页/共93页n否则,若k值比表中关键字值大,则令L=M+1,H不变,在表的后半部分继续对右子表进行折半查找；若k值比表中关键字值小,则令H=M-1,L不变,

37、继续对左子表进行折半查找。每进行一次比较,要么找到要查找的元素,要么将查找的范围缩小一半。如此递推,直到查找成功或把要查找的范围缩小为空（查找失败）。第72页/共93页LHMK=210 1 2 3 4 5 6 7 8 9 10 2.指针：L=0 H=4 M=(L+H)/2=2HM3.指针：L=3 H=4 M=(L+H)/2=3LM查找过程构成描述折半查找的判定树，当查找过程构成描述折半查找的判定树，当前的前的M M作根，左子表的作根，左子表的M M作为左子树的根，右子作为左子树的根，右子表的表的M M作为右子树的根，作为右子树的根，若，若n=11n=11，则判定树，则判定树如下。可看出中序遍历

38、判定树与表序相同，其如下。可看出中序遍历判定树与表序相同，其查找次数恰好等于层数。查找次数恰好等于层数。528036914710L=0,H=10M=5L=6,H=10M=8L=0,H=4M=2L=0,H=1M=0L=9,H=10M=9L=3,H=4M=3L=6,H=7M=6L=1,H=1M=1L=4,H=4M=4L=7,H=7M=7L=10,H=10M=10例:5,13,19,21,37,56,64,75,80,88,92）第73页/共93页例:5,13,19,21,37,56,64,75,80,88,92）1.指针：L=0 H=10 M=(L+H)/2=5LHMK=850 1 2 3 4 5

39、 6 7 8 9 10 2.指针：L=6 H=10 M=(L+H)/2=8M3.指针：L=9 H=10 M=(L+H)/2=9L4.指针：L=9 H=8 HL失败LM不难看出：如果把建造的描述折半查找的不难看出：如果把建造的描述折半查找的判定树中所有结点的空指针域上加一个指向称判定树中所有结点的空指针域上加一个指向称为外部结点的方形结点的指针。则失败时必指为外部结点的方形结点的指针。则失败时必指向外部指针，所以比较次数也不会超过层数。向外部指针，所以比较次数也不会超过层数。52803691471010第74页/共93页 折半查找算法折半查找算法int BinSearch(LineList R,

40、int n,KeyType k)int low=0,hight=n-1,mid;while(low=hight)mid=(low+hight)/2;if(k=Rmid.key)return mid;else if(kRmid.key)hight=mid-1;else low=mid+1;return-1;/Search_Bin 第75页/共93页算法分析：在二分查找过程中，关键算法分析：在二分查找过程中，关键字与字与k每比较一次查找范围就缩小一半。每比较一次查找范围就缩小一半。因为比较次数等于元素所在层数因为比较次数等于元素所在层数 h，而而h层最多有层最多有2h-1个元素，设有序表中元素个元

41、素，设有序表中元素个数为个数为n，则有，则有则二分查找的最大查找长度为：第76页/共93页二分查找的平均查找长度为二分查找的平均查找长度为O(log2n)，比顺序查找速度快。比顺序查找速度快。因故课本错误，请照课本错误，请照此修改此修改p168中中第77页/共93页7.5 7.5 哈希表查找哈希表查找 哈希表查找的思想，它通过哈希表查找的思想，它通过对元素的关键字值进行某种运算，对元素的关键字值进行某种运算，直接求出元素的地址，即使用关直接求出元素的地址，即使用关键字到地址的直接转换方法，而键字到地址的直接转换方法，而不需要反复比较。不需要反复比较。因此，哈希表查找法又叫杂因此，哈希表查找法又

42、叫杂凑法或散列法。凑法或散列法。第78页/共93页用一个函数用一个函数H H把数据集中的把数据集中的n n个个结点的关键字唯一地转换成结点的关键字唯一地转换成0.m-10.m-1范围内的数值，即对任意结点的关范围内的数值，即对任意结点的关键字键字kiki，有：，有：0H(ki)m-1 0H(ki)m-1（0in-10in-1）H(ki)H(ki)是表与元素关键字之间是表与元素关键字之间映射关系的函数，称为哈希函数。映射关系的函数，称为哈希函数。构造哈希函数和建立解决冲突构造哈希函数和建立解决冲突的方法是两个主要任务。的方法是两个主要任务。第79页/共93页假定某教室有假定某教室有3535个座位

43、，哈希个座位，哈希法则要限定学生所坐的位置应与其法则要限定学生所坐的位置应与其学号的末两位相同，则学号为学号的末两位相同，则学号为06016050601605的学生应坐编号为的学生应坐编号为5 5的座位。的座位。这样我们要找某个学生时只需根据这样我们要找某个学生时只需根据其学号的末两位到相应座位上去找其学号的末两位到相应座位上去找即可，不必一一比较了。即可，不必一一比较了。在这个例子里，学生好比记录，在这个例子里，学生好比记录，学号则为关键字，对关键字进行的学号则为关键字，对关键字进行的操作操作-哈希函数则是取其末两位，哈希函数则是取其末两位，用以确定记录的位置。用以确定记录的位置。第80页/

44、共93页不同的关键字可能得到同一哈不同的关键字可能得到同一哈希地址，这种现象称冲突。具有同希地址，这种现象称冲突。具有同一地址的关键字称作同义词。应该一地址的关键字称作同义词。应该尽可能地避免冲突的发生。尽可能地避免冲突的发生。总之，哈希表就是根据设定的总之，哈希表就是根据设定的哈希函数和处理冲突的方法将一组哈希函数和处理冲突的方法将一组关键字映像到一个有限的连续地址关键字映像到一个有限的连续地址上，并以此地址作为存储地址的表。上，并以此地址作为存储地址的表。这一映像过程称为哈希造表或散列，这一映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地所得存储位置称哈希地址或散列地址。址。第8

45、1页/共93页哈希函数的构造方法哈希函数的构造方法一个好的哈希函数能将给定的一个好的哈希函数能将给定的数据集均匀地映射到给定的地址区数据集均匀地映射到给定的地址区间中。间中。构造哈希函数的常用方法：构造哈希函数的常用方法：1.1.直接定值法直接定值法 H(kH(ki i)=a*k)=a*ki i+b,+b,例如按序号的若例如按序号的若干倍加上一个常数存储。干倍加上一个常数存储。第82页/共93页2.2.数字分析法数字分析法取关键字中某些取值较分散的取关键字中某些取值较分散的数字位作为散列地址。数字位作为散列地址。再如取下列各元素的第再如取下列各元素的第6 6位和第位和第7 7位：位：10001

46、1211100011211，100011322100011322，100011413100011413，100011556100011556，100011613100011613，100011756100011756，100011823100011823的散列地址分别是：的散列地址分别是：1212，1313，1414，1515，1616，1717，1818。第83页/共93页3.3.除留余数法除留余数法 H H（k k）=k mod m,=k mod m,如学号后两位。如学号后两位。4.4.平方取中法平方取中法取关键字平方的中间几位。取关键字平方的中间几位。5.5.折叠法折叠法把关键字分割成位

47、数相同的几段，把关键字分割成位数相同的几段，求叠加和，舍去进位。例如书号求叠加和，舍去进位。例如书号0-0-442-20586-4442-20586-4折叠折叠5864+0224+04=60925864+0224+04=6092第84页/共93页在哈希表中，虽然冲突很难避免，但在哈希表中，虽然冲突很难避免，但发生冲突的可能性却有大有小。发生冲突的可能性却有大有小。这主要与三个因素有关：这主要与三个因素有关：（1 1）与装填因子）与装填因子 有关。有关。（2 2）与所采用的哈希函数有关。）与所采用的哈希函数有关。（3 3）与哈希冲突函数有关。）与哈希冲突函数有关。n-已填，已填，m-空间空间第8

48、5页/共93页几种常用的解决哈希冲突的方法：几种常用的解决哈希冲突的方法：1开放地址法开放地址法（1）线性探测再散列）线性探测再散列（2）二次探测再散列）二次探测再散列（3）随机探测再散列）随机探测再散列2链地址法链地址法第86页/共93页3.性能分析性能分析查找成功时的平均查找长度是指查找到表中已有表项的平均探查次数，查找成功时的平均查找长度是指查找到表中已有表项的平均探查次数，它是找到表中各个已有表项的探查次数的平均值。而查找不成功的平均它是找到表中各个已有表项的探查次数的平均值。而查找不成功的平均查找长度是指在表中查找不到待查的表项，但找到插入位置的平均探查查找长度是指在表中查找不到待查

49、的表项，但找到插入位置的平均探查次数，它是表中所有可能散列的位置上要插入新元素时为找到空位置的次数，它是表中所有可能散列的位置上要插入新元素时为找到空位置的探查次数的平均值。探查次数的平均值。第87页/共93页表表7.2列出了用几种不同的方法解决冲突时哈希表的平均查找长度。列出了用几种不同的方法解决冲突时哈希表的平均查找长度。从中可以看到，哈希表的平均查找长度不是对象个数从中可以看到，哈希表的平均查找长度不是对象个数n的函数，而是装填的函数，而是装填因子因子 的函数。因此，在设计哈希表时可选择的函数。因此，在设计哈希表时可选择 控制哈希表的平均查找长度。控制哈希表的平均查找长度。第88页/共9

50、3页快速排序是由冒泡排序改进而得的，快速排序是由冒泡排序改进而得的，它的基本思想是：在待排序的它的基本思想是：在待排序的n n个记录中个记录中任取一个记录（通常取第一个记录），任取一个记录（通常取第一个记录），把该记录放入最终位置后，整个数据区把该记录放入最终位置后，整个数据区间被此记录分割成两子区间。所有关键间被此记录分割成两子区间。所有关键字比该记录关键字小的放置在前子区间字比该记录关键字小的放置在前子区间中，所有比它大的放置在后子区间中，中，所有比它大的放置在后子区间中，并把该记录排在这两个子区间的中间，并把该记录排在这两个子区间的中间，这个过程称为一趟快速排序。这个过程称为一趟快速排序