数据结构复习汇编课件.ppt

1、数据结构数据结构韩萍n数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。n数据结构分为逻辑结构和存储结构（物理结构）n顺序存储：n链式存储 a1 a2 a3a2 a1一一算法概念算法概念 对特定问题求解步骤的一种描述，是指令的有限序列，对特定问题求解步骤的一种描述，是指令的有限序列，每条指令表示一个或多个操作。每条指令表示一个或多个操作。：确定性：有穷性：可行性：输入：输出：可读性：健壮性：效率与低存储量需求正确性：算法的时间效率主要由两个因素决定：l所需处理问题的数据量大小，数据量大，所花费的时间就多；l在解决问题的过程中，基本操作的执行次数 时间复

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

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

4、1)/检查检查i值是否合理值是否合理 return ERROR;if(L.length=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;这里的问题规模是表的长度，设它的值为这里的问题规模是表的长度，设它的值为n。该算。该算法的时间主要花费在循环的元素后移语句上，所需移法的时间主要花费在循环的元素后移语句上，所需移动元素的次数不仅依赖于表的长度，而且还

5、与插入位动元素的次数不仅依赖于表的长度，而且还与插入位置有关。置有关。i位置位置移动次数移动次数 1n 2n-1 in-i+1 n+10平均移动次数：平均移动次数：时间复杂度：时间复杂度：O（n）22)1(111111)1(nnnnninin(a1,ai-1,ai,ai+1,an)改变为 (a1,ai-1,ai+1,an)ai+1 an表的长度减1a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 2.2.在线性表中删除第在线性表中删除第i i（1 i n1 i n）个元素，使）个元素，使status delete_sq(Sqlist&L,int i,elemtype&e)if(i

6、L.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;该算法的时间分析与插入算法相似，结点的移动次数也是由表该算法的时间分析与插入算法相似，结点的移动次数也是由表长长n和位置和位置i决定。决定。i位置位置移动次数移动次数 1n-1 2n-2 in-i n0平均移动次数：平均移动次数：时间复杂度：时间复杂度：O（n）212)1(111)(nnnnninin第三章 栈和队列栈和队列也可以被称作为操作栈和队列也可以被

7、称作为操作受限的线性表。受限的线性表。思考：假设有思考：假设有A,B,CA,B,C三个元素进三个元素进S S栈的顺序是栈的顺序是A,B,CA,B,C，写出所有可能的出栈序列。写出所有可能的出栈序列。CBAACBABCCABBACBCA1.栈属于加了限制条件的线性结构；栈属于加了限制条件的线性结构；2.栈是后进先出的线性表；栈是后进先出的线性表；3.进栈和出栈只能从栈顶进行；进栈和出栈只能从栈顶进行；4.栈中的元素个数可以是栈中的元素个数可以是0（空栈）；（空栈）；5.栈的元素的个数不能是无穷多个；栈的元素的个数不能是无穷多个；6.每个栈中的元素的类型相同每个栈中的元素的类型相同.栈的特性栈的特

8、性队列（队列（queuequeue）是一种只允许）是一种只允许在一端进行插入，而在另一端进行在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限删除的线性表，它是一种操作受限的线性表。的线性表。3.2.1 3.2.1 队列的定义及其运算队列的定义及其运算a0 a1 a2 an-1frontrear依次 1 2 3 4 5 6 删除两个元素之后的头元素是？第四章第四章 串串 零个或多个字符组成的有限序列。一般记S=a1a2.an 其中，S是串名串名，单引号括起的字符序列是串值串值；2 2、串长、串长 串中所包含的字符个数3 3、空串、空串长度为零的串，它不包含任何字符。1 1、串、串4

9、4、空格串、空格串由一个或多个空格组成的串，其长度为串中空格字符的个数。第五章5.3 广义表的定义广义表的定义一、广义表一、广义表（General List）1.广义表中的元素即可以是单个元素（称为原子）广义表中的元素即可以是单个元素（称为原子）也可以是广义表（称为子表）。也可以是广义表（称为子表）。2.一般表示：一般表示：LS=(a1,a2,an)3.习惯上广义表名用大写字母，原子用小写字母习惯上广义表名用大写字母，原子用小写字母4.当当LS非空时，非空时，a1称为称为LS 的表头（的表头（head），其余），其余元素组成的表（元素组成的表（a2,an）称为表尾（）称为表尾（tail）。）。

10、例：例：A=()B=(e)C=(a,(b,c,d)D=(A,B,C)E=(a,E)F=(a,b,(c,(d)广义表特点：广义表特点：允许递归，可共享子表允许递归，可共享子表元素不仅有先后次序，而且有层次关系元素不仅有先后次序，而且有层次关系元素的层次：是包括该元素的括号对数元素的层次：是包括该元素的括号对数表深：广义表中元素的最大层次表深：广义表中元素的最大层次二二广义表的存储结构（通常用链式）广义表的存储结构（通常用链式）广义表的扩展线性链表存储typedef struct glnodeint tag;/0 原子结点；1 子表结点union atomtype atom;/原子结点的值域 st

11、ruct glnode*hp;/子表表头指针struct glnode*next;/下一元素指针*glist;例：例：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作业练习作业练习求下列广义表操作的结果：求下列广义表操作的结果：GetHead【(p,h,w)】；GetTail【(b,k,p,h)】；GetHead【(a,b),(c,d)】；GetTail【(a,b),(c,d)】；GetHead【GetTail【(a,b),(c,d)】GetTail【

12、GetHead【(a,b),(c,d)】GetHead【GetTail【GetHead【(a,b),(c,d)】GetTail【GetHead【GetTail【(a,b),(c,d)】第六章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 K5.3.2根据二叉树的遍历构造二叉树3 3结点的结点的5 5棵二叉树的棵二叉树的3 3种遍历序种遍历序列如表所示。存在情况列如表所示。存在情况:表 5.

13、1 5 棵二叉树的 3 种遍历序列 二叉树 遍历序列 图 5.7（a）图 5.7（b）图 5.7（c）图 5.7（d）图 5.7（e）先序遍历序列 ABC ABC ABC ABC ABC 中序遍历序列 BAC BCA ACB CBA ABC 后序遍历序列 BCA CBA CBA CBA CBA ABCABCABCABCCAB因此，对因此，对3 3种遍序序列有结论：种遍序序列有结论：（1 1）由先序遍历序列和中序遍历）由先序遍历序列和中序遍历序列能够唯一确定一棵二叉树。序列能够唯一确定一棵二叉树。（2 2）由后序遍历序列和中序遍历）由后序遍历序列和中序遍历序列能够唯一确定一棵二叉树。序列能够唯一

14、确定一棵二叉树。（3 3）由先序遍历序列和后序遍历）由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。序列不能唯一确定一棵二叉树。例如：已知二叉树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由中序遍历序列和后序遍历序列构造二叉树的过程示意由中序遍历序列和后序遍历序列构造二叉树的过程示意平衡二叉树或者是一棵空树，

15、或者是具有下列性质的二叉排序树：(1)左、右子树都是平衡二叉树；(2)左、右子树高度差的绝对值=1。若把左子树与右子树高度之差称为结点x的平衡因子(balance factor)，用bf(x)表示。则由平衡二叉树定义知:Bf(x)=x左子树深度-x右子树深度1.平衡二叉树的定义91000065504741853060727842-330-202141853060727842-1110010a.非平衡二叉树非平衡二叉树 b.平衡二叉树平衡二叉树 所有结点的平衡因子只能所有结点的平衡因子只能取取-1-1，0 0，1 1三个值之一。三个值之一。6.2 堆排序堆是一棵顺序存储的完全二叉树，堆是一棵顺序

16、存储的完全二叉树，若每个结点的关键字都不小（大）于其若每个结点的关键字都不小（大）于其孩子结点的关键字，则称为大（小）根孩子结点的关键字，则称为大（小）根堆。堆。968338112791236854724305391堆排序的基本思想是：首先，按堆排序的基本思想是：首先，按堆的定义将堆的定义将R1.nR1.n调整为堆（这个过调整为堆（这个过程称为初始建堆），交换程称为初始建堆），交换R1R1和和RnRn；然后，将然后，将R1.n-1R1.n-1调整为堆，交换调整为堆，交换R1R1和和Rn-1Rn-1；如此反复进行，直到；如此反复进行，直到交换了交换了R1R1和和R2R2为止。为止。6.3.1 哈

17、夫曼树的定义哈夫曼树的定义设二叉树具有设二叉树具有n n个带权值的叶子结个带权值的叶子结点，那么从根结点到各个叶子结点的点，那么从根结点到各个叶子结点的路径长度路径长度l li i与相应结点权值与相应结点权值w wi i的乘积的乘积的和，称为二叉树的带权路径长度，的和，称为二叉树的带权路径长度，记作：记作：WPL=1WPL=13+33+33+23+22+42+41=201=20。n1iiilwWPL 4 2 1 3 6.3.2 哈夫曼树的构造哈夫曼树的构造（1 1）由给定的）由给定的n n个权值个权值WW1 1,W,W2 2,W,Wn n 构造构造n n棵只有一个叶子结棵只有一个叶子结点的二叉

18、树，从而得到一个二叉树的集点的二叉树，从而得到一个二叉树的集合合F=TF=T1 1,T,T2 2,T,Tn n。（2 2）在）在F F中选取根结点的权值最小中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，新二叉树根结点的造一棵新的二叉树，新二叉树根结点的权值为其左、右子树根结点权值之和。权值为其左、右子树根结点权值之和。（3 3）在集合）在集合F F中删除作为左、右子中删除作为左、右子树的两棵二叉树，并将新建立的二叉树树的两棵二叉树，并将新建立的二叉树加入到集合加入到集合F F中。中。（4 4）重复（）重复（2 2）、（）、（3 3）

19、两步，当）两步，当F F中只剩下一棵二叉树时，这棵二叉树便中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。是所要建立的哈夫曼树。注：如此建造的二叉树，没有度为注：如此建造的二叉树，没有度为1 1的结点。如有的结点。如有n n个叶子，必有个叶子，必有m=2n-1m=2n-1个结点。个结点。9例如:已知权值 W=5,6,2,9,7 56275276976713952767139527952716671329WPL=(6+7+9)*2+(5+2)*3=22*2+7*3=44+21=65注意：1.只算叶子2.分层计算3.路径长为层数减1 快速远距传输电文时，为使电文尽量短，采用不等长编码，且使

20、用频高的字符用较短的码。并且使任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。利用赫夫曼树可以构造出一种最优前缀编码使所传电文的总长度最短,这种编码就是赫夫曼编码。6.3.3 赫夫曼编码例：已知某通信息流只用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.3511237142911111110000000823 00 29 1011 01014 1105 0113 01117 11108 1111哈夫曼树和编码的代码实现序号权重父号左子右子17

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

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

23、无向图无向图-对称矩阵，半对称矩阵，半存即可，节省空间。每行存即可，节省空间。每行(列列)数字和即是顶点的度数字和即是顶点的度有向图的邻接矩有向图的邻接矩阵为非对称矩阵阵为非对称矩阵ABECD0 1 0 0 10 0 1 0 00 0 0 1 01 1 0 0 00 0 1 0 0ABCDEABCDE行和为出度行和为出度列和为入度列和为入度有向网的邻接矩有向网的邻接矩阵为非对称矩阵阵为非对称矩阵ABECDABCDEABCDE121731 57.3.2 深度优先搜索深度优先搜索深度优先搜索的基本思想是：深度优先搜索的基本思想是：从图从图G G中某个顶点中某个顶点vivi出发，访出发，访问问viv

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

25、点，然后依次从依次从V0的的各个未被访问各个未被访问的的邻接点出发深度优先搜索遍历图邻接点出发深度优先搜索遍历图，直至图中所有都被访问到。为确定每一个结点是否被访问，必须设置访问标志。一、连通图的深度优先搜索遍历一、连通图的深度优先搜索遍历achdekf8234570F F F F F F F F F0 1 2 3 4 5 6 7 8TTTT TT Tach d kfe achkfed访问标志访问标志:访问次序访问次序:例如例如:achdkfe7.4 最小生成树在一个无向连通图在一个无向连通图G G中，如果取它中，如果取它的全部顶点和一部分边构成一个子图的全部顶点和一部分边构成一个子图GG，即

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

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

28、,vj)(vi,vj)，其中，其中 viUviU，vjV-UvjV-U，并把该边，并把该边(vi,vj)(vi,vj)和顶点和顶点vjvj分别并入分别并入T T的边集的边集TETE和顶点集和顶点集U U。V0V3V5V2V1V46453821756V01V2closedge i12345AdjvexLowcostV0V1V2V3V4V5V0V1V2V3V4V5v06v01v070v25v26v2440V5v55v5220V350V1v1330V41+4+2+5+3=15例如：UV-U7.7 AOE网与关键路径若在带权的有向图中，以顶点若在带权的有向图中，以顶点表示事件，有向边表示活动，边上表示

29、事件，有向边表示活动，边上的权值表示完成该活动的开销（如的权值表示完成该活动的开销（如该活动所需的时间），则称此带权该活动所需的时间），则称此带权的有向图为用边表示活动的网络，的有向图为用边表示活动的网络，简称简称AOEAOE网（网（Activity On Edge Activity On Edge networknetwork）。）。在一个表示工程的在一个表示工程的AOEAOE网中，网中，应该不存在回路，网中仅存在一应该不存在回路，网中仅存在一个入度为个入度为0 0的顶点（事件），称为的顶点（事件），称为开始顶点（源点），它表示了整开始顶点（源点），它表示了整个工程的开始；个工程的开始；网中

30、也仅存在一个出度为网中也仅存在一个出度为0 0的的顶点（事件），称为结束顶点顶点（事件），称为结束顶点（汇点），它表示整个工程的结（汇点），它表示整个工程的结束。束。在寻找关键活动时所用到的几个在寻找关键活动时所用到的几个参量的定义：参量的定义：（1 1）事件）事件vkvk的最早发生时间的最早发生时间（2 2）事件）事件vkvk的最迟发生时间的最迟发生时间（3 3）活动）活动aiai的最早开始时间的最早开始时间（4 4）活动）活动aiai的最迟开始时间的最迟开始时间因AOV网中的活动可以并行，故工程完成的最短时间为从源点源点到汇点汇点的最长路径(关键路径关键路径)。abcdefghk64521

31、187244例如例如:“关键活动”是：关键路径上的活动，权值增关键路径上的活动，权值增加加 将使有向图上的最长路径的长度增加。最长路径的长度增加。源点汇点6174关键路径a-b-e-h-k把从源点到顶点j的最长路径长度叫做事件(顶点)的 最早发生时间ve(j);它是可能发生的最早时间。把从顶点k到汇点的最短路径长度叫做事件(顶点)的 最迟发生时间 vl(k).它是在不推迟工期的前提下最迟必须开始的时间。事件发生时间的计算公式:ve(源点)=0;ve(k)=Maxve(j)+dut()例如：ve(k)=18,ve(h)=14,ve(f)=7;vl(汇点)=ve(汇点);vl(j)=Minvl(k

32、)dut()例如:vl(k)=18,vl(h)=14,vl(f)=10。设第 i 条弧为 则 对第 i 项活动言,“活动(弧)”的 最早开始时间 e(i)e(i)=ve(j);e()=14;e()=7;“活动(弧)”的 最迟开始时间 l(i)l(i)=vl(k)dut();l()=14;e()=10。jkdut 什么是“关键活动关键活动”？该活动的该活动的最早最早开始时间开始时间 =该活动的该活动的最迟最迟开始时间开始时间在关键路径上,e(h,k)=l(h,k),不在关键路径上e(f,h)=7,l(f,h)=10，推迟开始或延迟3天均不影响工期。abcdefghk64521187244a b

33、c d efg h kvevl0000000006457115 715 14 1818181818181818181816 1486610807拓扑有序序列拓扑有序序列:a-d-f-c-b-e-h-g-ka b c d efg h kvevl06457715 14 181814161078660ab ac ad be ce df eg eh fh gk hk权权6 4 5 1 1 2 8 7 4 2 4el000645777 15 14141602366887 10 算法的实现要点算法的实现要点:显然，求ve的顺序应该是按拓扑有序拓扑有序的次序;而 求vl的顺序应该是按拓扑逆序拓扑逆序的次序;

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

35、查找的范围缩小一半。如此递推,直到查找成功或把要查找的范围缩小为空（查找失败）。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，则判定，则判定树如下。可看出中序遍历判定树与表序相同，树如下。可看出中序遍历判定树与表序相同，其查找次数恰好等于层数。其查找次

36、数恰好等于层数。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）例: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 6 7 8 9 10 2.指针：L=6 H=10 M=(L+H)/2=8M3.指针：L=9 H=10 M

37、=(L+H)/2=9L4.指针：L=9 H=8 HL失败LM不难看出：如果把建造的描述折半查找的不难看出：如果把建造的描述折半查找的判定树中所有结点的空指针域上加一个指向称判定树中所有结点的空指针域上加一个指向称为外部结点的方形结点的指针。则失败时必指为外部结点的方形结点的指针。则失败时必指向外部指针，所以比较次数也不会超过层数。向外部指针，所以比较次数也不会超过层数。52803691471010 折半查找算法折半查找算法int BinSearch(LineList R,int n,KeyType k)int low=0,hight=n-1,mid;while(low=hight)mid=(l

38、ow+hight)/2;if(k=Rmid.key)return mid;else if(kRmid.key)hight=mid-1;else low=mid+1;return-1;/Search_Bin 算法分析：在二分查找过程中，关键算法分析：在二分查找过程中，关键字与字与k每比较一次查找范围就缩小一半。每比较一次查找范围就缩小一半。因为比较次数等于元素所在层数因为比较次数等于元素所在层数 h，而而h层最多有层最多有2h-1个元素，设有序表中元素个元素，设有序表中元素个数为个数为n，则有，则有h1kh1k122nnnh22log)1(log则二分查找的最大查找长度为：则二分查找的最大查找长

39、度为：二分查找的平均查找长度为二分查找的平均查找长度为O(log2n)，比顺序查找速度快。比顺序查找速度快。n)(nnninCphiiniii22111log11log121ASL1h2h102*h2*1)-h(2*22*1S设h1h212*h2*1)-h(2*22*12S则)222(2*hS2SS1h10h12222nh1-h10因)1(log2nh故nnn)1(log)1(S2n)(nnninCphiiniii22111log11log121ASL课本错误，请照课本错误，请照此修改此修改p168中中7.5 哈希表查找 7.5.1 哈希表查找的基本概念哈希表查找的思想，它通过哈希表查找的思想

40、，它通过对元素的关键字值进行某种运算，对元素的关键字值进行某种运算，直接求出元素的地址，即使用关直接求出元素的地址，即使用关键字到地址的直接转换方法，而键字到地址的直接转换方法，而不需要反复比较。不需要反复比较。因此，哈希表查找法又叫杂因此，哈希表查找法又叫杂凑法或散列法。凑法或散列法。用一个函数用一个函数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)是表与元素关键

41、字之间是表与元素关键字之间映射关系的函数，称为哈希函数。映射关系的函数，称为哈希函数。构造哈希函数和建立解决冲突构造哈希函数和建立解决冲突的方法是两个主要任务。的方法是两个主要任务。假定某教室有假定某教室有3535个座位，哈希个座位，哈希法则要限定学生所坐的位置应与其法则要限定学生所坐的位置应与其学号的末两位相同，则学号为学号的末两位相同，则学号为06016050601605的学生应坐编号为的学生应坐编号为5 5的座位。的座位。这样我们要找某个学生时只需根据这样我们要找某个学生时只需根据其学号的末两位到相应座位上去找其学号的末两位到相应座位上去找即可，不必一一比较了。即可，不必一一比较了。在这

42、个例子里，学生好比记录，在这个例子里，学生好比记录，学号则为关键字，对关键字进行的学号则为关键字，对关键字进行的操作操作-哈希函数则是取其末两位，哈希函数则是取其末两位，用以确定记录的位置。用以确定记录的位置。n不同的关键字可能得到同一哈希不同的关键字可能得到同一哈希地址，这种现象称冲突。具有同一地地址，这种现象称冲突。具有同一地址的关键字称作同义词。应该尽可能址的关键字称作同义词。应该尽可能地避免冲突的发生。地避免冲突的发生。n总之，哈希表就是根据设定的哈总之，哈希表就是根据设定的哈希函数和处理冲突的方法将一组关键希函数和处理冲突的方法将一组关键字映像到一个有限的连续地址上，并字映像到一个有

43、限的连续地址上，并以此地址作为存储地址的表。这一映以此地址作为存储地址的表。这一映像过程称为哈希造表或散列，所得存像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。储位置称哈希地址或散列地址。7.5.2 7.5.2 哈希函数的构造方法哈希函数的构造方法一个好的哈希函数能将给定的数一个好的哈希函数能将给定的数据集均匀地映射到给定的地址区间中。据集均匀地映射到给定的地址区间中。构造哈希函数的常用方法：构造哈希函数的常用方法：1.1.直接定值法直接定值法 H(kH(ki i)=a)=a*k ki i+b,+b,例如按序号的若干例如按序号的若干倍加上一个常数存储。倍加上一个常数存储。2.2.

44、数字分析法数字分析法取关键字中某些取值较分散的数取关键字中某些取值较分散的数字位作为散列地址。字位作为散列地址。再如取下列各元素的第再如取下列各元素的第6 6位和第位和第7 7位：位：100011211100011211，100011322100011322，100011413100011413，100011556100011556，100011613100011613，100011756100011756，100011823100011823的散列地址的散列地址分别是：分别是：1212，1313，1414，1515，1616，1717，1818。3.3.除留余数法除留余数法 H H（k k）

45、=k mod m,=k mod m,如学号后两位。如学号后两位。4.4.平方取中法平方取中法取关键字平方的中间几位。取关键字平方的中间几位。5.5.折叠法折叠法把关键字分割成位数相同的几段，把关键字分割成位数相同的几段，求叠加和，舍去进位。例如书号求叠加和，舍去进位。例如书号0-0-442-20586-4442-20586-4折叠折叠5864+0224+04=60925864+0224+04=60927.5.3 哈希冲突的解决方法在哈希表中，虽然冲突很难避免，但在哈希表中，虽然冲突很难避免，但发生冲突的可能性却有大有小。发生冲突的可能性却有大有小。这主要与三个因素有关：这主要与三个因素有关：（

46、1 1）与装填因子）与装填因子 有关。有关。（2 2）与所采用的哈希函数有关。）与所采用的哈希函数有关。（3 3）与哈希冲突函数有关。）与哈希冲突函数有关。mn n-已填，已填，m-空间空间几种常用的解决哈希冲突的方法：几种常用的解决哈希冲突的方法：1开放地址法开放地址法（1）线性探测再散列）线性探测再散列（2）二次探测再散列）二次探测再散列（3）随机探测再散列）随机探测再散列2链地址法链地址法3.性能分析性能分析查找成功时的平均查找长度是指查找到表中已有表项的平均探查次数，查找成功时的平均查找长度是指查找到表中已有表项的平均探查次数，它是找到表中各个已有表项的探查次数的平均值。而查找不成功的

47、平均它是找到表中各个已有表项的探查次数的平均值。而查找不成功的平均查找长度是指在表中查找不到待查的表项，但找到插入位置的平均探查查找长度是指在表中查找不到待查的表项，但找到插入位置的平均探查次数，它是表中所有可能散列的位置上要插入新元素时为找到空位置的次数，它是表中所有可能散列的位置上要插入新元素时为找到空位置的探查次数的平均值。探查次数的平均值。表表7.2列出了用几种不同的方法解决冲突时哈希表的平均查找长度。列出了用几种不同的方法解决冲突时哈希表的平均查找长度。从中可以看到，哈希表的平均查找长度不是对象个数从中可以看到，哈希表的平均查找长度不是对象个数n的函数，而是装填的函数，而是装填因子因

48、子 的函数。因此，在设计哈希表时可选择的函数。因此，在设计哈希表时可选择 控制哈希表的平均查找长度。控制哈希表的平均查找长度。表 7.2 用几种不同的方法解决冲突时哈希表的平均查找长度 平均查找长度 解决冲突的方法 成功的查找 不成功的查找 线性探查法 2111 21(112)平方探查法 1ln 11 链地址法 21 e 8.4.2 快速排序快速排序是由冒泡排序改进而得的，快速排序是由冒泡排序改进而得的，它的基本思想是：在待排序的它的基本思想是：在待排序的n n个记录个记录中任取一个记录（通常取第一个记录），中任取一个记录（通常取第一个记录），把该记录放入最终位置后，整个数据区把该记录放入最终

49、位置后，整个数据区间被此记录分割成两子区间。所有关键间被此记录分割成两子区间。所有关键字比该记录关键字小的放置在前子区间字比该记录关键字小的放置在前子区间中，所有比它大的放置在后子区间中，中，所有比它大的放置在后子区间中，并把该记录排在这两个子区间的中间，并把该记录排在这两个子区间的中间，这个过程称为一趟快速排序。这个过程称为一趟快速排序。之后对所有的两个子区间分别重复之后对所有的两个子区间分别重复上述过程，直至每个子区间内只有一个上述过程，直至每个子区间内只有一个记录为止。简而言之，每趟排序使表的记录为止。简而言之，每趟排序使表的第一个元素入终位，将数据区间一分为第一个元素入终位，将数据区间

50、一分为二，对于子区间按递归方式继续这种划二，对于子区间按递归方式继续这种划分，直至划分的子区间长为分，直至划分的子区间长为1 1。快速排序算法的时间复杂度是快速排序算法的时间复杂度是O(nlogO(nlog2 2n),n),而且快速排序是不稳定的。而且快速排序是不稳定的。n 27 38 13 49 76 97 65 49图示一次划分过程。方括号表示无序区，方框表示基准，它未参加真正的交换，只是在划分完成时才将它放入正确的位置上。初始关键字 49 38 65 97 76 13 27 49 ijj向左扫描j第一次交换后27 38 65 97 76 13 49iji向右扫描i第二次交换后 27 38