《数据结构(C语言版)》复习重点

1、数据结构(c语言版)复习重点数据结构(C语言版)复习重点重点在二、三、六、七、九、十章，考试内容两大类：概念，算法第1章、绪论1. 数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。2. 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。3. 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。其4类基本结构：集合、线性结构.树形结构.图状结构或网状结构4. 逻辑结构：是数据元素之间的逻辑关系的描述。5. 物理结构(存储结构人是数据结构在计算机中的表示(又称映像)。其4种存储结构：顺序存数结构、链式存数结构、索引

2、存数结构、散列存数结构6. 算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。其5个重要特性：有穷性.确定性.可行性.输入、输出7. 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作，T(n)=O(f(n)；他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。例如：(a)+x;s=0;(b) for(i=l;i<=n;+i)+x;s+=x;(c) for(j=l;j<=n;+j)for(k=l;k<=n;+k)+x;s+=x;含基本操

3、作“赠1”的语句的频度分别为XnW,则这3个程序段的时间复杂度分别为0(1).0(n)和0(n2),分别称为常量阶.线性阶和平方阶。还可呈现对数阶0(logn)>指数阶0(2的n次方)等。&空间复杂度：算法所需存储空间的度量记作，S(n)=0(f(n)o第2章、线性表1. 线性表：是最常用最简单的一种数据结构，一个线性表是n个数据元素的有限序列。2. 线性表的顺序存储结构八是用一组地址连续的存储单元依次存储线性表的数据元素。其特点为逻辑关系上相邻的两个元素在物理位置上也相邻，可以随机存取表中任一元素。存储位置计算：假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储

4、地址作为数据元素的存储位置，线性表的第i个数据元素ai的存储位置为L0C(ai尸L0C(al)+(i-l)*L式中LOC(al)是线性表第一个元素al的存储位置，通常称做线性表的起始位置或基地址。3. 线性表的链式存储结构：是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。数据元素ai的存储映像称为结点，包括2个域：存数据的数据域、存后继存储位置的指针域。1) 线性链表(单链表)特点：每个结点只包含1个指针域。在单链表的第一个结点之前附设的一个结点，称之为头结点。假设L是LinkList型变量，则L为单链表的头指针，它指向表中第一个结点：L->ne

5、xt为第一个结点地址，L->next=NULL为空表。生成结点:p=(LinkList)malloc(sizeof(LNode)回收结点：free(q)图2.7带头结点的单链表<a)非空表；(b)空表(a)(b)图2.8在单链表中描入结点时指针变化状况<a)插人前j(b)桶入后abcs>next=p>next;p>next=s;图2.9在单链表中删除结点时指针变化状况P>next=p>nextnext;2)循环链表特点：表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的操作与线性链表基本一致，差别仅在于算法中的循环条件不是P或P-

6、>next是否为空，而是它们是否等于头指针。图2.12单循环链表（a）非空表！（b）空表(b)图2.13仅设尾指针的循环链表（R两个琏表；（b）合并后的表3）双向链表特点：有2个指针域，其一指向直接后继，另一指向直接前趋（b）图2.14双向链表示例（a）结点结构；（b）空的双向循环链表；（c）非空的双向循环链表d>next>prior=d>prior>next=dp图2.15衣双向链表中俱1|除结 点时指针变化状况W? ?il?图2.16在双向链表中插入一个结点时省针的变化状况第3章、栈和队列L栈：是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶，表头端称

7、为栈底，不含有元素的空表称为空栈；栈又称为后进先出的线性表。2-队列：是一种先进先出的线性表，它只允许在表的一端进行插入，而另一端删除元素。允许插入的一端叫做队尾，允许删除的一端则称为队头。dau nextrear队用<a)QfrontQ.rear(b)Q.front(J31一八Q.rw”Q«arq1-1Mp_IfiB图3.10链队列示意图图3.11队列运算指针变化状况（a）空队列&（b）元素x入队列）元累y入队列）（d）元素x出队列1）链队列：用链表示的队列。一个队列需要两个分别指示队头和队尾的指针（分别成为头指针和尾指针）才能确定唯一。和单链表一样，也给链队列添加一

8、个头结点，并令头指针指向头结点。2）循环队列：与顺序栈类似，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。初始化建空队列时，令front二rear=0每当插入新的队列尾元素时，“尾指针增1"；每当删除队列头元素时，“头指针增1”。5Q.rearQ.front21Q.rear0Q,rearQ-frontQ-frontQ.frcntJ5()(b)图3.12头、尾指针和队列中元素之间的关系<a)空队列；(b)Jxh和J3相继入队列；(c)Ji和J2相继被删除s(d)J4Js和k相继插人队列之后

9、Ja及h被制除图3.14循坏队列的头尾指针(“一冢悄况？Cb;队列时3(G)空队列第4章、串1.串：是由零个或多个字符组成的有限序列。第5章、数组和广义1. 数组特点：与线性表一样，所有数据元素都必须属于同一数据类型。2. 数组的顺序存储结构：由于数组一般不作插入或删除操作，一旦建立了数组,则结构中的数据元素个数和元素之间的关系就不会发生变动，因此采用顺序存储结构表示数组。存储位置计算：假设每个数据元素需占用L个存储单元，则二维数组A中任一元素aij的存储位置可由下式确定以行序为主序的存储结构：LOC(i,j)=LOC(0,0)+(b2*i+j)*L以列序为主序的存储结构：LOC(i,j)=L

10、0C(0,0)+(b2*j+i)*L式中LOC(i,j)是aij的存储位置；LOC(0,0)是aOO的存储位置，即二维数组A的起始存储位置，也称基地址或基址；b2在以行序为主序的存储结构时为每行存储元素的个数(列数)，在以列序为主序的存储结构时为每列存储元素的个数(行数)。3. 广义表：是线性表的推广，也有人称其为列表(lists,用复数形式以示与统称的表list的区别)。记作LS=(al,边an),其中LS是广义表(al,a2,-an)的名称，n是它的长度。在线性表的定义中，”(IWiWn只限于是单个元素。而在广义表的定义中，ai可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表

11、。例如：(1) A=()A是一个空表，它的长度为零。(2) B=(e)一列表B只有一个原子e的长度为1。(3) C=(a,(b,c,dR列表C的长度为2,两个元索分别为原子a和子表(b.c,d)o(4) D=(A,B,C)列表D的长度为3,3个元索都是列表。显然，将子表的值代入后，则有D=(),(e),(a,(b,c,d)。(5) E=(a,E)这是一个递归的表，它的长度为2。E相当于一个无限的列表第6章、树和二叉树1. 二叉树：是一种树型的结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。2. 二叉树的性质：1)性质

12、1:在二叉树的第i层上至多有2的i减1次方个结点(iAl)o2)性质2：深度为k的二叉树至多有2的k次方减1个结点(k>l)o深度为k的二叉树至少有k个结点(kNl)o深度为k的完全二叉树至少有2的k次方减2的k减1次方个结点(kNl)o3)性质3:对任何一棵二叉树T,如果其终端结点数为n0度为2的结点数为n2>则n0=n2+lo4) 性质4：具有n个结点的完全二叉树的深度为log2n+l05) 性质5：如果对一棵有n个结点的完全二叉树(其深度为log2n+l)的结点按层序编号(从第1层到第log2n+l层，每层从左到右)，则对任一结点i(1WiWn）有：a）如果i=l,则结点i是

13、二叉树的根，无双亲；如果i>l,贝康双亲PARENT是结点i/2ob）如果2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILDc）如果2i+l>n,则结点i无右孩子;否则其右孩子RCHILD是结点2i+l。3-满二叉树：一颗深度为k且有2的k次方减1个结点的二叉树。4 .完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。5 .遍历二叉树：1）根据二叉树写遍历结果：一a）先序遍历（先根遍历）：DLR+a*b"cd/ef八+./Jb）中序遍历（中根遍历）：LDRa+b*c-d-e/f/

14、（a）（*）（，）f）c）后序遍历（后根遍历）：LRDabcd-*+ef/-2）根据遍历结果画二叉树：""一棵二叉树的先序.中序和后序序列分别如下，其/中有部分未给出，试求出空Ii；格处的结点字符，并画出该二叉树。A先序_B_EHI_FG_m序：BicD_HEIA_CJ由序0（eJg_H_EBF_KG_A/人、”二、解题思路：上】JKa）由先序或后序确定根结点；如本题后序最后一个为A,根结点为A,所以先序第一个空就为Aob）在中序找出根结点，根结点左侧为左子树，右侧为右子树；如本题D_HEI为左子树,_86_为右子树。c）由先序确定紧跟在根结点后的左子树根；如本题紧跟在A后

15、的是B,B为左子树根，中序根结点的左子树只有一个空，所以为Bod）继续由中序确定左子树根的左右子树,左侧为左子树,右侧为右子树；如本题B的左子树为D,右子树为HEI,所以先序第二个空为Doe）重复c）、d）步骤确定整棵左子树；如本题先序中紧跟在D后的是E,E为B的右子树,由中序中看出E左子树为H,右子树为I,补充后序填空,前两空分别为D和Iof）由后序确定右子树根的左子树,再由中序确定右子树根；如本题紧跟在B后的是F,F为右子树根的左子树，已知中序_CJG_右子树，F只可能第一个空，那第二个空为K,补全先序.中序.后序填空其可画出二叉树。6 .森林与二叉树的转换：1）树转换成二叉树：连兄弟，留

16、长子，删孩子。a）连线，连接所有兄弟结点。b）删线，仅保留双亲与长子结点的连线，删除与其他孩子结点之间的连线。c）整理，原有的长子结点为左子树，从兄弟转换为孩子的结点为右子树。d）注意，由于树根没有兄弟结点，固树转换为二叉树后，二叉树根结点的右子树必为空。（n）（b）（c）I树转化成二叉树I2）森林转换成二叉树：连树根及兄弟，留长子，删孩子。a）连线，连接每棵树的根结点及所有兄弟结点。b）删线，仅保留双亲与长子结点的连线，删除与其他孩子结点之间的连线。c）整理，第一棵树根结点为二叉树根结点，原有的长子结点为左子树，从兄弟转换为孩子的结点为右子树。3）二叉树转换成树：连左孩子的右孩子及其右孩子一

17、，删原树右孩子。a）连线，若某结点X存在左孩子XL,则将这个左孩子的右孩子结点XLR.左孩子的右孩子的右孩子结点XLRR.左孩子的右孩子的右孩子的右孩子结点XLRRR都与X结点连线。b）删线，删除原二叉树的所有双亲与右孩子结点的连线。步舞2,去线步骤3.层次调整c）整理，原二叉树根结点为树根结点。4）二叉树转换成森林：连左孩子的右孩子及其右孩子一，删原树右孩子。a）连线，若某结点X存在左孩子XL,则将这个左孩子的右孩子结点XLR、左孩子的右孩子的右孩子结点XLRR.左孩子的右孩子的右孩子的右孩子结点XLRRR都与X结点连线。b) 删线，删除原二叉树的所有双亲与右孩子结点的连线。c) 整理，调整

18、为多棵树的森林。工树步骤h寻找右孩子去拔步耐将分离的二叉树转换成树1.赫夫曼树：又称最优树，是一类带权路径长度最短的树。cbd)d)?图6.24赫夫曼树的构造过程2在前,a）两个最小数值组成一对，小的在前，大的在后；如上图中2与4最小4在后。2与 4Ab）将两个最小数值的和算作一个数，再与其他数重复£步骤；如上图中的和为6,5与6最小，5在前，6在后。c)最后计算WPL,它等于每个数值乘以从根结点到这个数值的连线个数的积之和；如上图中WPL=2*3+4*3+5*2+7*l=35口&赫夫曼编码：a)在赫夫曼树上，左分支代表0,右分支代表1。b)由根结点到指定结点的路径(从上到下

19、把0、1连起来)，就是该结点的赫夫曼编码;如上图(d)中a为0,b为10,c为110,d为111。第7章、图1 .图：多个结点，结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。2 .无向完全图：有n(n-l)/2条边的无向图。3有向完全图：有n(n-l)条边的有向图。4 .入度：以顶点V为头的弧的数目称为V的入度。5 .出度：以V为尾的弧的数目称为V的出度。6 .连通图在无向图中，任意两个顶点之间都有路径。7 .连通分量：在无向图中的极大连通子图。图7.3无向图及其连通分M(a)无向图G和(b)G的3个连通分&邻接矩阵：无向图的邻接矩阵关于主对角线对称，在整个矩阵中非

20、零元素的数等于边个数的2倍，第i行和第i列中非零元素的个数等于该结点的度。5bo5oo7OQo oOOoo4ooOOo o8o ooooo89nooo5oono6coooO O5coOO.3o ooo(b)OO18图7.9网及其邻接矩阵(。网N;(b)邻接矩阵9.邻接表：无向图的邻接矩阵关于主对角线对称，在整个矩阵中非零元素的个数图7.1图的示例(a)有向图Gz (b)无向图G之相关联的顶点，选择一个 索与之相关联且未访问过的 联且未访问过的顶点；后退等于边个数的2倍，第i行和第i列中非零元素的个数等于该结点的度。(a)Gi的邻按表9(b)Gz的邻接表？(OGi的逆邻接表210.深里优先遍历：

21、从图中某个顶点出发，搜索与访问(从左到右，从上到下)；再从该顶点出发，搜顶点，选择一个访问；重复上步骤，直到没有相关一个顶点继续搜索访问，直到所有顶点都被访问过。VO工ff/jf、VIV2f/AvjT/3in£.IV31Ja）从VO出发，先找到VO的关联顶点V3ob）由V3出发，找到Vh由VI出发,没有关联的顶点。c）回到V3,从V3出发，找到V2;由V2出发,没有关联的顶点d）回到V3,再回到VO,由V0出发，找到V4。e）从V4出发，找到VI,因为VI已经被访问过了，所以不访问。所以最后顺序是VO,V3,VI,V2,V4o11-广度优先遍历从图中某个顶点出发，搜索与之相关联的顶点

22、，逐个访问（从左到右，从上到下）；再从这些顶点出发，搜索与之相关联且未访问过的顶点，逐个访问；重复上步骤，直到所有顶点都被访问过。a）从V0出发，先找到Y0的关联顶点V3.V4ob）由V3出发,找到VI、V2;由V4出发,找到VI,因为VI已经被访问过了,所以不访问。c)由VI出发，没有关联的顶点；由V2出发，没有关联的顶点。所以最后顺序是VO,V3,V4,VI,V2o12 .最小生成树：1)普里姆算法八连相邻权值最小的。(b)(e>(f)(a>(b)(c)图7.16普里姆算法构造最小生成树的过程2）克鲁斯卡尔算法图九连8琥愀蟀你算拗给画小生成树的过程13 .拓扑排序：由某个集合上

23、的一个偏序得到该集合上的一个全序的操作以图1.28(a)中的有向图为例，图中和s没有前驱，则可任选一个。假设先输出眺在删除矶及弧3，眺？“之后？只有顶点没有前驱。则输出3且测去3及弧5?盹Ms.s和之后5和S都没有前驱。依次类推？可从中任选一个继续进行.整个拓扑排序的过程如图7?28所示。O ?关键路径：路径长度最长的路径。最后得到该有向图的拓扑有序序列为：1)如图，先求各事件的最早发生时间(顺序为vrv9)VI的最早发生时间为0,V2的最早发生时间为6,V3的最早发生时间为4,V4的最早发生时间为5o对于V5,需要V2,V3均发生，V2发生且完成的时间为6+1=7;V3发生且完成的时间为4+

24、1=5，因而V5的最早发生时间为7。同理可求出各顶点的最早发生时间：VIV2V3V4V5V6V7V8V9e(i)0645771637.28AR-网及其懈卜有序序列产生的过理2)求各事件的最晚发生网期aoV-J腐扁b)feVWVMe溜出切之后)V9的最晚时间为18,V8iW晚时岫输削8-初=14网血皴更晚时间为18-al0=16,V6渊晚时间为14P9=10,V5的最晚时间为V7的最晚时间减去a7和V8的最晚时间减去a8两者较小的，则V5的最晚时间为7,同理可得其他顶点的最晚发生时问：VIV2V3V4V5V6V7V8V9l(i)0668710161418则li与ei相等的事件即为关键事件即：Vb

25、V2,V5,V7,V8,V9可得关键路径：VbV2,V5,V7,V9或VI,V2,V5,V8,V93)求各活动的最早发生时间a5a6ala2a3a4a7a8ae(i) 0007774)求各活动的最晚发生时间ala2aa7a83aalO616a4 alOall414a5alla61 (i)6-6=06-4=2 98-5=37-1=67-1 =10-2=816-9=714-7=714-4=1018-2=16则li与ei相等的活动即为关键活动即：al>a4>a7>a8>al0>all可得关键路径：VI,V2,V5,V7,V9或VI,V2,V5,V8,V915.最短路径：

26、从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上始点？终点最短路径路径长度%无S（u>。1050（箱）30图7.35有向图G中从到其余各点的最短路径5（3s化）60B/一一f匕一2/L/7X7Z/4E权值之和最小的一条路径1）迪杰斯特拉算法：S素台中U%台中1选入从此时S=<A>止匕时杲短路径A->A=O以人为中间点，从A开始找U=O、GDsE、F>ATB=6ATC=3AT艾他U中的顶？点=8发现A->C=3权值为杲短2选入C?止匕时S=<A,C>此时摄短跻径AAA=OJATC=3以C为中间点，从ATC=3这条S!短路径开始找U=<

27、B>D、EsF>ATCTB一5（比上面第一步的Af一6要短）此时到B权值为ATCTB巧ATCTD=6ATCTE二7ATCT其他U中的顶点二00发现ATCTB二5?权值为晁3选入B>此时S=<A、C、B>此时杲短路径ATA=0JA-?C=3>ATCTB=5以B为中间点。从ATCTB=5这条星短路轻开始找U=6E>F>ATCTBTD二10（比上面第二步的ATCTX6要长）此时到D权值更改为ATC>D=6ATCTBT苴他U中的顶点二03发现ATCTM权值为最短4选入D?此时S=<A、C、BsD>止阿#fe路径A-AA-OJATC=3,

28、ATCTB?A?C-ad=6以D为中间武从ATCTb逮条最短瑶径开轴找U=v£、F>ATCTDTE对（比上面第二步的ATCTE司要长）此时到E权值更改为ATCTE二7ATCTDTF为发现ATCTE寸权值为最短5选入E>此时S=<A、C、BsD.E>止匕时呈短赂径ATA=Q小TC=3>ATC->B?一D二6A>C>E=7以E为中间烂从ATCT£=7遗条燧短路开始找U=<F>ATCTETF=12（比上面第四步的ATCTDTF=9要长）此时到F权值更改为ATCTDTF-9发现ATCTDTF=9权值为最短6选入F>止

29、匕时S=<A、C、B、IkE、F>止匕时星短路径ATA二0从TC=3/ATCTB=5,TinA>CTE=7>ATCTDTF=9U|g合巴仝，查找完毕？2）弗洛伊德算法:：Lfi>jDd(l2pDl(lO+D021所以 D,IJ2-D- ,l|0+D- ,0J2r>VO VI V 2012V0V|/2所以叩l2=r>io-图7-7-12我们先定义两个一维数组D3和P33,D代表顶点到顶点的最短路左权值和的矩阵。P代表对应顶点的最小路径的前驱矩阵。在未分析任何顶点之前，我们将D命名为DJ其实它就是初始的图的邻接矩阵。将P命名为PJ初始化为图中所示的矩阵。首

30、先我们来分析，所有的顶点经过Vo后到达穷一顶点的最短路径。因为只有三个顶点，因此需要查看VLVLV2沿到Di11O-D102=2*1=3?D2表示的是VLV2的权值为5,我们发现Di12>DilOfDi02,通俗的话讲就是vl-*V0->V2比直接v)-*v2距离还要近。所以我们就让"12=DiLOfD?02卜3,同样的D721=3,于是就有了Do的矩阵。因为有变化，所以P矩专对应的PU1U2和PH21也修改为当前中转的顶点V。的下标0,于是就有了Poo也就是说D°vjwl=minD'1vw?D'1v0+D-10w接下来，其实也就是在Do和P0的

31、基础上继绫处理所有顶点经过V!和V2后到达另一顶点的最知路径，得到D1和pi、D2和P2完成祈有顶点到所有顶点的最短路径计算工作。方法：两条线，从左上角开始计算一直到右下角如下所示：给出矩阵，其中矩'05 00 7'X 04 23 3 0 2x oo 10Path =阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点。1-1-1-f-1-1-1-1-1?1?1-1-1-1不在三条线上的元素所在的把A4划去第0行第0列和对角线来计算分00004>073205330732c§0a/07080012阶矩阵为:很容易就可趴看出不在三条线上的6个元素都

32、不发生改变，因此公二Pat%=Path.把凡划去第1行第1列和对角线来计算川严按上面所述的刘断不在三条线上的元素是否需要发生改变，发上变化的元素用括号掳起来059000433000X172 Fathi20 1 1 -1-1 -1 -1-1 -1 -1 1-1 -1(3)把冕划去第2行第2列和对角线来计算K严所以有A=最后A3即为所求结果(4)把公划去第3行第3列和对角线来计算是一2 2-1-1-1 -1-1106381 0-1 -13 -1-1 -12 23 -13 -1-1 -1-1 -1-1 -12 -1-1 -1059732 Path2441030Fath034022所以有a =x (4

33、)取4) 1所以有儿二第9章、查找1-查找表：是由同一类型的数据元素（或记录）构成的集合。2 .关键字：是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录3 .静态查找表：查询某入特定的数据元素是否在查找表中，检索某个特定的数据元素的各种属性。1）顺序查找法：从表中最后一个记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之若直至第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查记录，查找不成功。其存储结构要求：以顺序表或线性链表表示的静态查找表。其平均查找长度：假设每个记录的查找概率相等，即Pi=

34、l/n,则在等概率情况下顺序查找的平均查找长度为，ASL=（n+l）/2o2）折半查找法（二分查找法）：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。其存储结构要求：以有序表表示的静态查找表。其平均查找长度：假设表中每个记录的查找概率相等（Pi=l/n）,则查找成功时折半查找的平均查找长度为，ASL二（n+l）/n*log2（n+1）-1。3）索引顺序表查找法（分块查找法）：先确定待查记录所在的块（子表），然后在块中顺序查找。其存储结构要求：以索引顺序表表示的静态查找表。其平均查找长度：将长度为n的表均匀地分成b块，每块含有s个记录，即b=n/s;又假设表中每个

35、记录的查找概率相等，则每块查找概率为1/b,块中每个记录的查找概率为1/s,若用顺序查找确定所在块，则分块查找的平均查找长度为，ASL=（n/s+s）/2+l;若用折半查找确定所在块，则分块查找的平均查找长度为，ASLAlog2（n/s+l）+s/2o4.动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除己存在的某个数据元素。1） 二叉判卡序树：或者是一棵空树；或者是具有下列性质的二叉树：1、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；2若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；3.它的左.右子树也分别为二叉排序树。2） 平衡二叉

36、树（AVL树）：它或者是一棵空树；或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1.0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。,、(90J小(g)xLz(h)图9.12平衡树的生成过程(小空树，<b)插入13;(c)插入24;(小插入37;(e)向左逆时针右旋转平衡；相继插入90和53,(g)笫一次向右顺时针旋转八h)第二次向左逆时针旋转平衡之下面即四种情况分别为：左左、右

37、右、左右、右左，每种情况又有两个图、,是该情况的最简单的图形，是该情况的一般的图形。设X为最小不平衡子树的根结点，y为刚插入的点左左：即在x的左孩子a的左孩子c上插入一个结点y(该结点也可以是c,如图)，即y可以是c,也可以是c的左孩子(如图)，也可以是c的右孩子(不在画出)。XXfJFIL?3zaa->/ab/yx/cxYcd/vdb图就不用说了，结点x和结点a变换，则树平衡了；那么图就是树中的一般情况了a结点有右孩子d,那要进行x和a变换，那么a的右孩子放哪啊？很简单，如图放在x的左孩子上；分析：x>d,d>?所以d可作为x的左孩子，且可作为a的右孩子中的孩子。下边这样的

38、类似情况不再一一分析，自己分析分析实现：找到根结点X,与它的左孩子a进行交换即可使二叉树树再次平衡；右右:即在x的右孩子a的右孩子c上插入一个结点y（该结点也可以是c,如图），即y可以是c,也可以是c的右孩子（如图），也可以是c的左孩子（不在画出）y实现：找到根结点X,与它的右孩子a进行交换即可使二叉树树再次平衡；左右:即在x的左孩子a的右孩子c上插入一个结点y（该结点也可以是c,如图），即y可以是c,也可以是c的右孩子（如图），也可以是c的左孩子（不在画出）:XXXXbdy/jy/c日y/曰bch/再右画用这个左右和下边的右左，稍微复杂了点，需要进行两次交换，才能达到平衡，注意这时y是c的右

39、孩子，最终y作为x的左孩子；若y是c的左孩子，最终y作为a的右孩子，画图分析一下下边类似，不再敖述。实现：找到根结点x,让x的左孩子a与x的左孩子a的右孩子c进行交换，然后x与x此时的左孩子c进行交换，最终达到平衡；:即在x的右孩子a的左孩子c上插入一个结点y（该结点也可以是c,如图,即y可以是c,也可以是c的右孩子（如图），也可以是c的左孩子（不在实现：找到根结点X,让x的右孩子a与x的右孩子a的左孩子c进行交换，然后再让x与x此时的右孩子c进行交换，最终达到平衡；上边的四种情况包含了所有插入时导致不平衡的情况，上面给出的仅仅是一棵大树中的最小不平衡子树，一定要想清楚，别迷了！另外一定要注意

40、这个交换操作，比如a与b交换(a在上，b在下)，b一定要占据a的位置！什么意思？就是b要放在(覆盖)储存a的那块内存上，再通俗点说，若a是x的左孩子,则交换后b要做x的左孩子；这就是所谓的b占据a的位置！5.哈希表：1) 构造方法：a) 直接定址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key)=a?key+b其中a和b为常数(这种散列函数叫做自身函数)。若其中H(key)中已经有值了，就往下一个找，直到H(key)中没有值了，就放进去。b) 数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几

41、率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。c) 平方取中法：当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。d) 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和(去除进位)作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将

42、分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。e) 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即H(key)=keyMODp,p<=mo不仅可以对关键字直接取模，也可在折叠.平方取中等运算之后取模。对P的选择很重要，一般取素数或叫若p选的不好，容易产生同义词。2) 处理冲突方法：a) 开放定址法:Hi=(H(key)+di)MODm,i=l,2,k(k<=mT),其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：LLdi=l,2,3,m-1,称线性探测再散列；1.2. di

43、二2厂2,22-2232±k*2,(k<=m/2)称二次探测再散列；1.3. di二伪随机数序列，称伪随机探测再散列。b) 再哈希法:Hi=RHi(key),i=l,2,kRHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。C)链地址法(拉链法)：将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址在区间0,m-l±,则设立一个指针型向量ChainChainHashtm；其每个分量的初始状态都是空指针。凡哈希地址为i的记录都插入到头指针为ChainHashti的

44、链表中。在链表中的插入位置可以在表头或表尾；也可以在中间，以保持同义词在同一线性链表中按关键字有序。d)建立一个公共溢出区：假设哈希函数的值域为0,nrl,则设向量HashTableO.m-l为基本表，每个分量存放一个记录，另设立向量OverTableO.v为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们有哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。例9-4已知例9-3中所示的一组关键字按哈希函数HCkey尸keyMOD13和线性探测处理冲突构造所得哈希表a.elem0?15如图9.27所示.012345678910111213141514|0168叵|即19|20|

45、3厂792|1110图9.27哈希表a.elem0?15体给希屈败为H<keyAAyMOD13,处理冲突为级性抿浏再散列）给定值K=84的查找过程为：首先求得哈希地址H(84)=6,因a.elem6不空且a.elem6.keyH84,则找第一次冲突处理后的地址H1=(6+l)MOD16=7,而a.elem7不空且a.elem7.keyH84,则找第二次冲突处理后的地址H2=(6+2)MOD16=8,a.elemZ8不空且a.elemCfil.key=84,则杳找成功，返回记录在表中序号8.给定值K=38的查找过程为：先求哈希地址H(38)=12,a.elem12不空旦a.elem12.k

46、eyH38,则找下一地址H=12+l)MOD16=13,由于a.elem13j是空记录，则表明表中不存在关键字等于38的记录，从哈希袈的查找过程可见：(1)虽然呛希表在关键宇与记录的存储位遇之问建立了直按映像，但由于“冲突”的产生，使得哈希表的查找过程仍热是一个给定值和关键字进行比较的过程。囚此，仍需以平均查找长度作为衡登哈希表的查找效率的虽度。(2)查找过程中需和给定值进行比较的关锂字的个数取决于下列三个因索：哈希曲数，处理冲突的方法和哈希表的装填因子。哈希函数的“好坏”首先影响出现冲突的频繁程度。但是，对于“均匀的”哈希函数可以假定：不同的哈希函数对同一组随机的关键字，产生冲突的可能性相同

47、，因为一般情况下设定的哈希函数是均匀的，则可不考虑它对平均查找长度的影响。对同样一组关键字，设定相同的哈希函数，则不同的处理冲突的方法得到的哈希表不同，它们的平均查找长度也不同。如例9-3和洌9-4中的两个哈希表，在记录的查找概率相等的前提下，前者(链地址法)的平均查找长度为ASL(12)=吉(1?6+2?4+3+4>=1.75后者(线性探测再散列)的平均查找长度为ASL(12)=召(1?6+2+3?344+9)=2?5容易看出，线性探测再散列在处理冲突的过程中易产生记录的二次聚隼，如既使得哈希地址不相同的记录又产生新的冲突；而链地址法处理冲突不会发生类似情况，因为哈希地址不同的记录在不

48、同的链表中。在一般情况下，处理冲突方法相同的哈希？表，其平均查找长度依赖于哈需？表的装填因子。哈希表的装填因子定义为“表中入的记录数哈希表的长度a标志哈希表的绫满程度。直观地看，a越小，发生冲突的可能性就越小；反之，a越大，表中巳填人的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也就越多。可以证明J呦线性探测再散列的呛希表查找成功时的平均查找长度为随机探测再散列、二次探测再散列和再哈希的哈希表查找成功时的平均查找长度为Sw一，ln(l-a)(9-28)Ct.链地址法处理冲突的哈希表查找成功时的平均查找长度为S严1十号(9-29)由于哈希表在查找不成

49、功时所用比较次数也和给定值有关，则可类似地定义哈希表在盒找不成功时的平均查找长：度为：盘找不成功时需和给定值进行比牧的关键字个数的期望值。同样可证明，不同的处理冲突方法构成的哈希表查找不成功时的平均查找长度分别为JJf11/a一5.(】十(1-*J<y-o-线性探灌再散列u2u(9-31-伪随机探测再散列等)九a+厂(9-32一链地址)第10章、内部排序1 .排序：是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列。2直接插入排序：将一个记录插入到己排好序的有序表中，从而得到一个新的.记录数增1的有序表。voidInsertS

50、ort(SqList&L)对顾序表L作直接插入排序.for(i?2?iOL.lengthj+i)if(LT(L.ri.key,L.ri-.key)/气”？隔将L.ri插入有序子表L.r0=L.rij/复制为哨兵L.ri-L.ri-ljfor(j=i-2iLT(L.r0.key,L.rj.key)fj)L?弓j+叮=巾口/记录后移1L.r0?/插入到正确位置/InsertSort初始关键(49)381659776132749了11=2：(38)(3849659776132749(65)(3849*65)97J*76?132749<97)(38496597)76.132749i=51

51、(76)(3849657697)132749t=6i(13)厂(13384965769727i49a(27)<13r273849呛5?7697)49t=8i(49)(132738494965769t监视帆T010?1直接插入排序示例3.希尔排序（缩小增量排序）：先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。voidShellInsert(SqList&L,intdk)II对X序表L作一起希尔捆入排序。本真法是和一起直接播入排序相比？作了以下修改;/1.前后记录位置的增肚是dk?而不是“/2.上0只是暂存单元？不是哨兵？当jVO时，插入位蜀已找到。for(dk+1；i<=L.length；+i)if(LT(L?ri?key,L.ri-dkj.key)/需将L.r：i插入有序增值子表L.rLO=/!暂存在L.r0for(j=i-dk；j>0&&LT(L.r0.key.L.rj.key)ij-=dk)L.rj+dk=/记录后移，查找描入位登L.rj+dk=L?r0$/ffiA?Shelllnsert算法10?4voidShellSort(