数据结构C语言版复习重点

1、百度文库-让每个人平等地提升自我数据结构(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=1;i<=n;+i)+x;S += x;(C) for(j=1;j<=n;+j)for(k=1;k<=n;+k)+x;

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

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

5、头指针，它指向表中第一个结点；L->next为第一个结点地址，L->next=NULL为空表。生成结点:P=(LinkList)malloc(sizeof(LNode)回收结点：free(q)图2.7带头结点的单链表22<a)非空表當(B)空表4& 3 M3-图2.8在.fi!屮插入结点Bd指针变化状况<a)插入前$(h)旅人后S > next = P > next ；P > next = s；2. 9在单链表中删除结点时指针变化状况P 一> next = P > next > next ；2) 循环链表特点：表中最后一个结点

6、的指针域指向头结点，整个链表形成一个 环。循环链表的操作与线性链表基本一致，差别仅在于算法中的循环条件不是P或P->next是否为空，而是它们是否等于头指针。E 2H2单谐环链表Ca)非空表1(b)空表(M)Cb)图2.13仅设尾指针的循环链表(a)两个S$1(b)合并后的表3)双向链表特点：有2个指针域，其一指向直接后继，另一指向直接前趋图Z 14双向错表示例(B)结点结f*(h)空的腹I旬循环毎表I CC)非空的双向循环犍表d > next 一> PnOr = d > PriOr > next = dIfJ 2 A取向懂舉巾制除姑血时描钎变化状况图2f 16在

7、戏向÷人一牛结点时?针的童牝状況第3章、栈和队列1栈：是限定仅在表尾进行插入或删除操作的线性表。表尾端称为 栈顶，表头 端称为栈底，不含有元素的空表称为 空栈；栈又称为后进先出的线性表。2. 队列：是一种先进先出的线性表，它只允许在表的一端进行插入，而另一端 删除元素。允许插入的一端叫做 队尾，允许删除的一端则称为 队头。1）链队列：用链表示的队列。一个队列需要两个分别指示队头和队尾的指针 （分 别成为头指针和尾指针）才能确定唯一。和单链表一样，也给链队列添加一个头 结点，并令头指针指向头结点。Q. IrontQ. FWQ. frontQ frontQ front Q EW（*）Cd

8、) 3.11賦列运算描针变化秋况空肌列;W元累JC人叭刊<e>元It y人臥列* （CD元ItX出队列2）循环队列：与顺序栈类似，除了用一组地址连续的存储单元依次存放从队列 头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。初始化建空队列时，令fron t = rear = 0,每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。Q. Peaf图乳12头、尾指針和队列中元累之间的关系(a)空5K; (b) JIJa和n相细人队列MZ JL和h ms除<d) Jl JS和k相堆插人臥列之后JH及J4麓剧餘

9、Q. frontQ IrtlIItQ. IrantX U 旃环臥列的头用惜针O-Iafflf况。Ck MWffi时*任)空从列第4章、串1. 串：是由零个或多个字符组成的有限序列第5章、数组和广义表1. 数组特点：与线性表一样，所有数据元素都必须属于同一数据类型。2. 数组的顺序存储结构：由于数组一般不作插入或删除操作， 一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不会发生变动，因此采用顺序存储结构表示数组。存储位置计算：假设每个数据元素需占用L个存储单元，则二维数组A中任一元 素aij的存储位置可由下式确定以行序为主序的存储结构：LOC(i,j)=LOC(0,0)+(b2*i+j

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

11、i可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。例如：(1) A=()A是一个空表，它的扶度为零。(2> R=-J)列表E只有个像子IE前长度为It(3) C=C列表C的悅度为辈两个元j分别为原子C和子表(孙"(4) D=CAtB.O列表D的长度为3 + 3<元就都是列表.显然.将子表的值代 人后则有D-CC >,3),(应，価(5) E = (SE)这是个递归的表，它的检度为典E相当于一个无限的列表 E=(df Ct (d第6章、树和二叉树1. 二叉树：是一种树型的结构，它的特点是每个结点至多只有两棵子树(即二 叉树中不存在度大于2的结点)，并且

12、，二叉树的子树有左右之分，其次序不能 任意颠倒。2. 二叉树的性质：1) 性质1:在二叉树的第i层上至多有2的i减1次方个结点(i 1)。2) 性质2:深度为k的二叉树至多有2的k次方减1个结点(k 1)。深度为k的二叉树至少有k个结点(k 1)。/深度为k的完全二叉树至少有2的k次方减2的k减1次方个结点(k 1)。/3) 性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为 n2，则 n0=n2+104) 性质4 :具有n个结点的完全二叉树的深度为Iog2n+1。5) 性质5:如果对一棵有n个结点的完全二叉树(其深度为log2n+1 )的结点 按层序编号(从第1层到第log

13、2n+1层，每层从左到右)，则对任一结点i (1 i n）有：a）如果i=1 ,则结点i是二叉树的根，无双亲；如果i>1 ,则其双亲PARENT（i） 是结点i2b）如果2i>n ,则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD（i） 是结点2i oC）如果2i+1>n ,贝U结点i无右孩子；否则其右孩子 RCHILD（i）是结点2i+1。3满二叉树：一颗深度为k且有2的k次方减1个结点的二叉树。4. 完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都 与深度为k的满二叉树中编号从1至n的结点遍历二叉树：根据二叉树写遍历结果：5.1)先序遍历（

14、先根遍历）：a)-+ a * b - C d / e fDLRb）中序遍历（中根遍历）：a + b * C - d - e / fC）后序遍历（后根遍历）：a b C d - * + e f / -CGE对应。fLDRLRD试求出空格_=B_=EHI_FG_K_D HElA CJGH EBF KG AB2）根据遍历结果画二叉树： 一棵二叉树的先序、中序和后序序列分别如下，其中有部分未给出， 处的结点字符，并画出该二叉树 先序 中序 后序 解题思路：a）由先序或后序确定根结点；如本题后 序最后一个为A,根结点为A,所以先序 第一个空就为AOb）在中序找出根结点，根结点左侧为左 子树，右侧为右子树

15、；如本题 D=HEI为 左子树，=CJG=为右子树。C）由先序确定紧跟在根结点后的左子树根； 树根，中序根结点的左子树只有一个空，所以为d）继续由中序确定左子树根的左右子树，左侧为左子树，右侧为右子树；如本 题B的左子树为D,右子树为HEl，所以先序第二个空为Doe）重复c）、d）步骤确定整棵左子树；如本题先序中紧跟在 D后的是E，E为B 的右子树，由中序中看出E左子树为H,右子树为I ,补充后序填空，前两空分 别为D和If）由后序确定右子树根的左子树，再由中序确定右子树根；如本题紧跟在B后如本题紧跟在A后的是B，B为左子B的是F, F为右子树根的左子树，已知中序=CJG=>右子树，F只

16、可能第一个空， 那第二个空为K,补全先序、中序、后序填空并可画出二叉树。6. 森林与二叉树的转换：1）树转换成二叉树：连兄弟，留长子，删孩子。a）连线，连接所有兄弟结点。b）删线，仅保留双亲与长子结点的连线，删除与其他孩子结点之间的连线。C）整理，原有的长子结点为左子树，从兄弟转换为孩子的结点为右子树。d）注意，由于树根没有兄弟结点，固树转换为二叉树后，二叉树根结点的右子 树必为空。树转化成州2）森林转换成二叉树：连树根及兄弟，留长子，删孩子。a）连线，连接每棵树的根结点及所有兄弟结点。b）删线，仅保留双亲与长子结点的连线，删除与其他孩子结点之间的连线。C）整理，第一棵树根结点为二叉树根结点，

17、原有的长子结点为左子树，从兄弟 转换为孩子的结点为右子树。3）二叉树转换成树：连左孩子的右孩子及其右孩子，删原树右孩子。a）连线，若某结点X存在左孩子XL,则将这个左孩子的右孩子结点 XLR左孩 子的右孩子的右孩子结点XLRR左孩子的右孩子的右孩子的右孩子结点 XLRR 都与X结点连线。b）删线，删除原二叉树的所有双亲与右孩子结点的连线。C）整理，原二叉树根结点为树根结点。!pair 4）二叉树转换成森林：连左孩子的右孩子及其右孩子，删原树右孩子。a）连线，若某结点X存在左孩子XL,则将这个左孩子的右孩子结点 XLR左孩 子的右孩子的右孩子结点XLRR左孩子的右孩子的右孩子的右孩子结点 XLR

18、R 都与X结点连线。b）删线，删除原二叉树的所有双亲与右孩子结点的连线。二h 寻找rar4*2t 帚分离的二C）整理，调整为多棵树的森林。7. 赫夫曼树：又称最优树，是一类带权路径长度最短的树x 7 5 6C图氐24誌夫曼树的构造过蓉a）两个最小数值组成一对，小的在前，大的在后；如上图中2与4最小，2在前，4在后。b）将两个最小数值的和算作一个数，再与其他数重复a）步骤；如上图中2与4的和为6， 5与6最小，5在前，6在后。C）最后计算WPL它等于每个数值乘以从根结点到这个数值的连线个数的积之和；如上图中 WPL=2*3+4*3+5*2+7*仁358. 赫夫曼编码：a）在赫夫曼树上，左分支代表

19、0,右分支代表1。b）由根结点到指定结点的路径（从上到下把0、1连起来），就是该结点的赫夫曼 编码；如上图（d）中a为0，b为10，C为110，d为111。第7章、图1. 图：多个结点，结点之间的关系可以是任意的，图中任意两个数据元素之间 都有可能相关。2. 无向完全图：有n（n-1）/2条边的无向图。3. 有向完全图：有n（n-1）条边的有向图。4. 入度：以顶点V为头的弧的数目称为V的入度。5. 出度：以V为尾的弧的数目称为V的出度。6. 连通图：在无向图中，任意两个顶点之间都有路径。7. 连通分量：在无向图中的极大连通子图。1(a)>图7*3无向图及其连通分董<a)无l图GA

20、 <b) G3的3个连通分麵8. 邻接矩阵：无向图的邻接矩阵关于主对角线对称，在整个矩阵中非零元素的 个数等于边个数的2倍，第i行和第i列中非零元素的个数等于该结点的度。5CX37CoOOOOOel4OaOaOo8OOOOOOCo9nrOO5rnn6图7. 9网及其邻接知阵(a)网>b (b)邻接矩阵9. 邻接表：无向图的邻接矩阵关于主对角线对称，在整个矩阵中非零元素的个 数等于边个数的2倍，第i行和第i列中非零元素的个数等于该结点的度。10. 深度优先遍历：从图中某个顶点出发，搜索与之相关联的顶点，选择一个访 问（从左到右，从上到下）；再从该顶点出发，搜索与之相关联且未访问过的顶

21、 点，选择一个访问；重复上步骤，直到没有相关联且未访问过的顶点；后退一个 顶点继续搜索访问，直到所有顶点都被访问过。a）从Vo出发，先找到Vo的关联顶点V3。b）由V3出发，找到V1 ;由V1出发，没有关联的顶点。C）回到V3,从V3出发，找到V2;由V2出发，没有关联的顶点。d）回到V3,再回至U V0,由Vo出发，找到V4。e）从V4出发，找到V1,因为V1已经被访问过了，所以不访问。所以最后顺序是V0, V3, V1, V2, V411. 广度优先遍历：从图中某个顶点出发，搜索与之相关联的顶点，逐个访问（从 左到右，从上到下）；再从这些顶点出发，搜索与之相关联且未访问过的顶点， 逐个访问

22、；重复上步骤，直到所有顶点都被访问过。a）从V0出发，先找到V0的关联顶点V3、V4。b）由V3出发，找到VI、V2;由V4出发，找到V1,因为V1已经被访问过了, 所以不访问。C）由V1出发，没有关联的顶点；由 V2出发，没有关联的顶点。所以最后顺序是V0, V3, V4, V1, V212. 最小生成树：1）普里姆算法：连相邻权值最小的。2)克鲁斯卡尔算法：先连权值最小的，再依次连<d)te)图7-18克鲁斯卡尔算法构造毘小生成树的过釋13. 拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序的操作以图7,28（a）中的有向图为例'图中，环和昭没育前胚，则可任迭一个.假设

23、先输出 恥准拥除巩及弧SeJ 仏之后，只有顶点S殺有前驱，则输出U且剧去S越弧 胡人之后孙和V4祁注有前驱。依次类推可从中枉选一个显续 进暂.整亍拓扑排序的过棵如I枣仁空所示。最后得到祓有向图的拓扑有序序列为： -Vi *v1 *v*v2 ji,哥J.S8 AWR-网挖其拓扑有痒序列产生的过程(a) A("3V- R (bj 険 J W (c> |£出伽空后 I<dJ 出班el唏出叶之医I （I） 之雋1）如图，先求各事件的最早发生时间（顺序为 V1V9）V1的最早发生时间为0，V2的最早发生时间为6， V3的最早发生时间为4, V4 的最早发生时间为5。对于V

24、5,需要V2, V3均发生，V2发生且完成的时间为 6+1=7; V3发生且完成的时间为4+仁5,因而V5的最早发生时间为7。同理可求 出各顶点的最早发生时间：V1 V2 V3 V4 V5 V6 V7 V8 V9e（i） 0645771614182）求各事件的最晚发生时间（顺序为 V9V1）V9的最晚时间为18, V8的最晚时间为18-a11=14, V7的最晚时间为18-a10=16,V6的最晚时间为14-a9=10, V5的最晚时间为 V7的最晚时间减去a7和V8的最a1a2a3a4a5a6晚时间减去 生时间：a8两者较小的，则V5的最晚时间为7,同理可得其他顶点的最晚发V1V2V3V4V

25、5V6V7V8V9l(i)0668710161418则i与ei相等的事件即为关键事件即：V1, V2, V5, V7, V8, V9可得关键路径：V1, V2, V5, V7, V9 或 V1, V2, V5, V8, V93）求各活动的最早发生时间a7a8a9a10a11e(i)00064577716144)求各活动的最晚发生时间ala2a3a4a5a6a7a8a9a10a11(i)6-6=06-4=28-5=37-1=67-1=610-2=816-9=714-7=714-4=1018-2=1618-4=14则i与ei相等的活动即为关键活动即：al, a4, a7, a8, a10, all

26、可得关键路径：V1, V2, V5, V7, V9 或 V1, V2, V5, V8, V915.最短路径：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径。1）迪杰斯特拉算法：图&34帶权有向图GJ短路径路VL兀t<1 rvt)105« . W m )500< ½ »u)30C ji¼ f¾ *)60图化翦 有向图G中从到具余各点的最短路径sU中1J入 Al Jtist S= <A> 此时最短踌径AT口 中阎静,从A开找II= <X C. D* E* F>A-&

27、AC3-XU 申的M= JAC=3值为宦短2选 1Cr 此时 S= <, c>IttBt5SK*=Q ->C=3以C为甲I司疵.A Ac=3这察案遠JS锂开 iV-D.氐 F>A->CB=5( Et上面髯一齿的兔Tb=B要短,W1 ?枳值九 C B=5*P=6ACI=TACKW申酌顶点= 笈现 *CB M>ft3i B J JHflt S= . c, b>此时摄短踣轻A -> A > A C=3 JA C "¢=5以E为中间点,UC E5違孤星短 瞬开抬找U= E> F>A>CBD =IOC 比上面第二

28、步的 ACD=S-）OTJ D枳值更改为丸TC TP省 ftCBU 中的底点=DO 變现 C TmB取價対最短4遼入 D tfll S -<JL6. D>JttHlIS A-J > -÷C<J» AC->B=S ACD=&Ia 为申间点,从 A efrs5 开胎找II= < OATfTDTE碍（比上面篥二歩HT匚TE 7） 此时1 E取值更改掏ACE =7A-tnp gy¾ ace寸枳傕为壘痣S J JtLfll S= <. C> Bs 臥 E>JtcffrSSSS A0 A C=3 A C B=S i

29、 A Tc n=&ATtTF =7以E为中询点” A C =7燧哥齢短跑轻开*找” SACEF =12(比上茴棊E3歩的 ATCTHTT =9 要圧】f取请更現为 C TD F -SEJ¾ac d f令权值K眾縊6 Fj IhttJ S= < Ck, K B, B. F> 此时盘短 A=O J C=3 , ÷C "B=5 1 A -C TD=B ACE =7, A C TD TP =9U馬督巴至歪找死毕2）弗洛伊德算法：fWDl2J-L>jj(tO+DltJ2rrF1*VlVlFflVf*：012巾rO12Vl012Vl01010*2*1

30、00R Miji112,11 IHB 7-7-L3我们先定义匹牛_维fl D313和F可【罕D代表顶点到顶成的嚴讯路楼权偵和 的距阵.P代表对应顶点的曝小路径的前躯矩阵在未分析任何頂点之前，我们将D 命名为D1,其实艺就是初始的图的邻接矩阵。捋P命塔为Pr 初冲化为图中所示的首先我化来分析，所有的顶点经过VO后到达界一顶点的最短路住，因为只有三个 顶点，因此需要查看v1vtv2,得到D】1Q+D（02=2÷l=3, D 丁忆表示的 是VI-Va的权值为5,我们发现EH 12> D-I lO÷D i 0p1通俗的话许就是叭 vvz比宜接vva距战还要近。所以我们就让Do

31、 1Pl= V tLO+Dl 02=3t ASD'i 2）Lb3,于魁就有了 D口的拒耳 因为有变化，所以P矩阵对 府的P ilIlI2|和H2l也修改为当前中转的顶点也的下标讥 于是就育了叭 也就 是说DoMW= EiT DrI vwt D'1 vC+D1 PIIWfi接下來、其贺也就星在Do和网的城础±if处珅所有顶点经过Vl和v3fUS 一顶点的最煮跻得到M和PJ D2和严完咸祈有锁点到所有顶点的SI短路径计算方法：两条线，从左上角开始计算一直到右下角如下所示：给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所 必须经过的点。百度文库-让

32、每个人平等地提升自我XX23百度文库-让每个人平等地提升自我最后A3即为所求结果。第9章、查找1. 查找表：是由同一类型的数据元素（或记录）构成的集合。2. 关键字：是数据元素（或记录）中某个数据项的值，用它可以标识（识别） 一个数据元素（或记录）。3. 静态查找表：查询某个特定的数据元素是否在查找表中，检索某个特定的数 据元素的各种属性。1）顺序查找法：从表中最后一个记录开始，逐个进行记录的关键字和给定值比 较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之 若直至第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查记录， 查找不成功。其存储结构要求：以顺序表或线

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

34、度：将长度为n的表均匀地分成b块，每块含有S个记录，即 b=ns;又假设表中每个记录的查找概率相等，则每块查找概率为1/b ,块中每个记录的查找概率为1s ,若用顺序查找确定所在块，则分块查找的平均查找 长度为，ASL=（ns+s）2+1 ;若用折半查找确定所在块，则分块查找的平均查找 长度为，ASL log2（ns+1）+s2。4. 动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查 找表中删除已存在的某个数据元素。1）二叉排序树：或者是一棵空树；或者是具有下列性质的二叉树：1、若它的左 子树不空，则左子树上所有结点的值均小于它的根结点的值； 2、若它的右子树 不空，则右子树

35、上所有结点的值均大于它的根结点的值； 3、它的左、右子树也 分别为二叉排序树。2）平衡二叉树（AVL树）：它或者是一棵空树；或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不 超过1。若将二叉树上结点的平衡因子 BF定义为该结点的左子树的深度减去它 的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。图平衡树的生成过程M 空树匚Cb）插人1乱 A 2+;柑插人即：Ce）向左逆时-ffi转平抵F（0相堆堀人M 53s 或第一次胸右頂时tt转丰W第一欢向左迎时常

36、Ife转平衛之下面即四种情况分别为：左左、右右、左右、右左，每种情况又有两个图、, 是该情况的最简单的图形，是该情况的一般的图形。设X为最小不平衡子树的根结点，y为刚插入的点左左：即在X的左孩子a的左孩子C上插入一个结点y（该结点也可以是c,如图 ），即y可以是c,也可以是C的左孩子（如图），也可以是C的右孩子（不 在画出）。CJ图就不用说了，结点X和结点a变换，则树平衡了；那么图就是树中的一般 情况了 a结点有右孩子d,那要进行X和a变换，那么a的右孩子放哪啊？很简 单，如图放在X的左孩子上；分析：x>d,d>a,所以d可作为X的左孩子，且可作 为a的右孩子中的孩子。下边这样的类

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

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

39、定要注意这个交换操作， 比如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）数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大

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

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

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

43、地址为i的记录都插入到头指针为 ChainHashi的链表中。在链表中的插入位置可以在表头 或表尾；也可以在中间，以保持同义词在同一线性链表中按关键字有序。d)建立一个公共溢出区：假设哈希函数的值域为0,m-1，则设向量 HaShTable0.m-1为基本表，每个分量存放一个记录，另设立向量 OVerTable0.v为溢出表。所有关键字和基本表中关键字为同义词的记录，不 管它们有哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。例9-4已倒9-3中所示的一R字按希诵数H(ey)=j M0D13和绘性 探删暑理冲突就遷府縛哈拮丟NEbnok . 1工如U S.27所示.Ol 23456?

44、 ESIQllI£ 13 4 LS H叫10So143'10图 9* 27 clem! O * 15<X<ft*Kt Hafyf-kty MODl3p½M>S 为级 tt 幌测再散PP皓定值K=的查找过程为*首先求4地址H<84)=6,因a,MEin6不空且 den63. key84,则找第一次冲覺处理后的地址Hr=<5 + 1) MOD而N elem打不空且a.dem71key84,则找第二次冲靈处理后的地址Hz = t6+2) MOD 16 = 8丄elemLl不空卫a÷ elem81 key = 84*!N査找成功回记聂

45、牡衰申序号8.给定值K = 38的査找过稈为t先求哈希地址H = I2,a. rkm12空且a elem 12. MyH靄.閘投下一地LH1 = C12÷1) MoD 16=13.由于 a,dem13是空记星.则 養明袤中不荷在关键字等于滤的记录扌从哈希表妁杳找过程可见Im 虽燃哈希表在关t宁与记最的仔睛位迴之间建立了苴搖映躱.但曲于“冲克H的 产主屏吏得哈希衣的査找过程仍然是一牛给定值和关逊宇进行比较的过程.囚此，仍需以 平均査找歩度作为>的査找效率的蜀度。辭)查找过桎中襦和给定值进打比较的关谨字的牛数取按于下列三T固索i哈培函 数,灶理冲究的方箍和若希表的装填因于.哈希函数

46、的“好坏”首先影咆出现冲突的频繁程变。但是，对于"均匀的”哈希函数可 匕惧定*不同的哈希匣敷对同一组Bl机的关键字;产生冲宪的可能性相同因为一股傭况 下设定的哈需函数是均匀的、则可不考恵它对平均杳找长度的影响对同样一组关键字*设定相同的哈輸函数、则不同的处壓冲突的方法得到的哈希4(不 同.它们的平均査找长度也不同.如例43和MM中的两个瞼希表，在记录的査找槪率相尊的½T,9者(链地址法)的平均査找长度先ASL< 12) = A * £ + 2 4 + $-4) = L75后者(统性探测再敬列的平均査找长度为/ViL<12)=吉 d *6÷23

47、3÷49) - 2t 5容易看出，线性擾测再諛列在处理冲樂的过穫中易产生记最的二r既使得呛 需地址K相同的记录又产生新的冲突而密抱址法处理冲究不会发生类個情况*因为哈需 地址不同的记最在木同的梃表中#在一般情况下处理冲究方旌相冋的喑希表，技平均査找悅度依軸于哈希表的装 填因子<.哈兼我的装填因于龙文为C_表中填人的记录数哈希表的云度疗标志哈椎表的裝惓程度.直观地小,发生冲突的可能性就越小卡反之Eje大表 中巳填人的记录越多，再填记录时发生伸突的可能性就越大上1査拢时1&定值術月之逬 行比较的关键字的于数也就越參可以证«InliI性探测再歆列的P希表査找脱功时的

48、平均查找长度为s(1 + )I#机探测再敲列、二Ifc探厠再敞列和再哈希的哙希表査拢成功时的平均SftK«»Sw Ilnd-a)(9-2)O II链地址法b理冲突的哈希表査找戒功时的平均査找长度为由于哈無表在査找不成功时所用比较按数也和给定值有关，则可类似地定义 住黛費不成功时的平均代找悅度为：蟹找不虺功时需U½值进仃比牧的芙瑋爭T数旳 期壇值°同样可证明，不同的赴理冲夹方法脚虜的唱甬衷査找不欣期空的平均査找艮度 分別为T J .lX】(&-30)LFil *7r + <->l)一线姓探利再散列UB= 7<-31)1 *一的開机

49、探测再散列等UBC T + t一锭地址(9-32)第10章、内部排序1. 排序：是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或 记录)的任意序列，重新排列成一个按关键字有序的序列。2. 直接插入排序：将一个记录插入到已排好序的有序表中，从而得到一个新的、 记录数增1的有序表。VOid InBertSOrt ( SqLiSt Il对JS序衰L作直接描人排序.fqr ( X* 21 K- L. Iengthf + i )if <LT<L. ri.key L. ri*lAey) <"L,<i人有序子表L-r(0 - L,ri," St制为哺

50、兵L. ri = LK ri-叮ffor ( j w i - 21 LT<Lr r0, key, L. rj.key) - j j+叮 L. rjr"记录后移L,<1 - UrfO1U插人到正确拉宜 IneetHtSort初始关字(49)38_ t65977613274&<38)<3fi49)659776132749#-3>«5)(364965)9776*132749*4«7)(38496597)76132749I=»5(7)(3S4965f7697)132749=61(13)(1338496576972749(27

51、)<13384»65 J7697)49i 8(C49)(13273S49-J-49657S97)t 监««fL r0图10"直接!入排序示例3. 希尔排序（缩小增量排序）:先将整个待排记录序列分割成若干子序列分别进 行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次 直接插入排序。VOid ShCl IInSert C SqLlAt &匚,in dk ) "对呱序験1柞 咆希尔插人提序，本½和 凰直按捕人徘睛相比作丁以下修咗, / J就J记载位置的增皐是CUU财#是X"2.刘0只建r存单元，

52、不是哨兵.1<= 0时插人位蜀已找到。for ( i - + 1 i i= L. Iengtht + i >if CLTCL.ri.key, L- r£ dfcc>) fit LHrEi人有厚増捱子最LrOJ = Lri,/ 暂存 L. for (j = i- dk j>0 && ICL. r0.key, L. rj.key)t j -= die)L. r1 + dk L,rfl1记录后移，？E找牺人位JSL. r j + dk2 = U i# 插人/ ShellInfiert算法10.4Void SballSort (SqLiSt &匚* iat lta J , Lnt t) /序弭diuOT. t-l对顺序表L尔排序。for (k* Dt k<t + - k)ShellInsextCL, dltak>:/ ffl'为小tac的插人排库I / Shl ISbrt初始关犍字：493