2022年数据结构复习要点 .pdf

《2022年数据结构复习要点 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构复习要点 .pdf（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习好资料欢迎下载第一章 绪论1.数据 (Data):是对客观事物的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。包括数值，字符，图象，声音等。2.数据元素 (Data Element): 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。3.数据对象 (Data Object) ：是性质相同的数据元素的集合。是数据的一个子集。4.数据结构 (Data Structure) ：是相互之间存在一种或多种特定关系的数据元素的集合。S = (D, R)其中 D 为数据元素的有限集，

2、R为 D 上关系的有限集。例 复数的数据结构定义如下：Complex=(C,R)其中： C 是含两个实数的集合C1,C2，分别表示复数的实部和虚部。 R=P ， P是定义在集合上的一种关系C1,C2 。5.基本数据结构类型(根据数据元素之间的不同联系划分):A.集合B.线性结构C.树形结构D.图（网）状结构6.逻辑结构 / 数据结构： 数据元素及其关系的数学特性。7.物理结构 / 存储结构： 逻辑结构在计算机中的具体实现。8.数据类型 :指一个值的集合以及在这些值上定义的一组操作的总称。包括基本数据类型、结构数据类型。在 C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类

3、型：数组、结构、联合、指针、枚举型9.抽象数据类型（Abstract Data Type 简称 ADT）:指抽象数据组织和与之相关的操作。每一个操作由它的输入和输出定义。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内的表示和实现无关。ADT可以定义为： （D，S，P） 其中 D 表示数据对象，S是 D 上的关系集，P是对 D 的基本操作集。ADT使用伪码描述为：ADT抽象数据类型名数据对象： 数据关系： 基本操作： ADT抽象数据类型名10.数据结构的研究内容：数据的逻辑结构（Logical structure ） 数据的存储结构（Storage structure 物理结构）数据

4、结构上的操作或处理（算法）数据的逻辑结构（简称数据结构）：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 40 页学习好资料欢迎下载线性结构： 有且仅有一个开始结点和终端结点，且所有结点最多只有一个直接前趋和直接后继。如：线性表，栈，队列非线性结构：一个结点可能有多个直接前趋和直接后继。如：树，图数据的存储结构： 顺序存储方法(Sequential Storage Structure): 数组 链接存储方法(Linked Storage Structure)：指针 索引存储方法：索引表 散列存储方法：由关键字直接计算存储地址数据运算：定

5、义在逻辑结构上，而在物理结构上实现如：插入，删除，更新，查找，排序11.算法和算法分析程序= 算法+ 数据结构算法：是对特定问题求解步骤的一种描述, 算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：1) 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。2) 确定性 : 算法中每一条指令必须有确切的含义。不存在二义性。相同输入只能得到相同输出。3) 可行性 :一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。4) 输入 :一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。5) 输出 :一个算法有一

6、个或多个输出，这些输出是同输入有着某些特定关系的量。12.几种基本的算法设计方法1)枚举法 :从问题的所有可能答案中找出满足条件的解。e.g 买鸡问题：公鸡每只5 元，母鸡每只3 元，小鸡3 只一元， 100 元买 100 只鸡，有多少种买法？（算法见图一）图一图二2)归纳法： 找出问题的规律A. 递推：逐次推求中间结果和最后结果e.g 计算 Fibonacci 数列：数列第1 项为 1，第 2 项为 1，从第三项开始，每一项等于前两项之和。f = (1,1,2,3,5,8,13,21,34, )B. 递归：自己调用自己e.g 计算阶乘 : F(n)=F(n-1)*n, F(1)=1 （算法见

7、图二）C. 回溯法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 40 页学习好资料欢迎下载通过 “ 试” 找到问题的解。如在一些游戏中，找出一个解决问题的途径，然后选出一条“ 试走 ” ，若此路不通，退回换路线重走。D. 数字模拟法：数字仿真问题很难建立数学模型，用随机数模拟随机现象。13.算法设计的要求评价一个好的算法有以下几个标准:(1)正确性 (Correctness )：算法应满足具体问题的需求。(2)可读性 (Readability)：算法应该好读。以有利于阅读者对程序的理解。(3)健状性 (Robustness)：算法应具

8、有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。(4)效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。定理：若A(n)=a m n m +a m-1 n m-1 + +a1n+a0是一个 m 次多项式，则A(n)=O(n m)频度：是指该语句重复执行的次数例 for(i=2;i=n;+I)for(j=2;j=i -1;+j)+x;ai， j=x;语句频度为：1+2+3+ +n-2=(1+n-2)(n -2)/2=(n -1)(n-2)/2=n2-3n+2时间复杂度为O(n2)以下六种计算算

9、法时间的多项式是最常用的。其关系为： O(1)O(logn)O(n)O(nlogn) O(n2)O(n3)指数时间的关系为：O(2n)O(n!)data; p-next6.链表分类：?单链表：每个结点指针域中只有一个指向其后继结点的指针；?循环链表：将链表的最后一个结点与第一个结点连接起来，可从任意结点出发访问其它结点；?双向链表： 每个结点中有两个指针，一个指向其后继结点，另一个指向其前趋结点；7.单链表的基本运算1)建立单链表 : 设成员数据域为字符型A.头插法建表：依次插入新结点，并置于表头规律：新增加的结点指针域指向原head 指向的结点，然后将原head 指向新结点步骤：? 产生新结

10、点：产生一个指向新结点的指针变量，其数据域内容等于要插入的结点数据? 修改新结点指针域：令其指针域指向原来的第一个结点（由head 指向）? 修改头指针：将头指针head 指向插入的结点B.尾插法建表：插入的新结点置于表尾?产生一个新结点；?新结点的数据域为插入字符；?原尾指针指向新结点；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 40 页学习好资料欢迎下载?新结点的指针域为空2)插入及删除运算3)查找运算4)8.头结点好处a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，

11、无需进行特殊处理；b、无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），头指针始终不为空，因此空表和非空表的处理也就统一了9.循环链表循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。单循环链表： 在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样， 空循环链表仅有一个自成循环的头结点表示。如下图所示：精选学习资料 - - - - - - - - - 名师归纳总结 - - - -

12、 - - -第 6 页，共 40 页学习好资料欢迎下载在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear 来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rear next) next和 rear，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p 或 pnext

13、 是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。10.双链表双向链表 (Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域 prior 。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：和单链表类似，双链表一般也是由头指针唯一确定的，增加头结点也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。设指针 p 指向某一结点，则双向链表结构的对称性可用下式描述：(p prior) next = p =(p next) prior即结点 *p 的存储位置既存放在其前趋结点*(p pr

14、ior) 的直接后继指针域中，也存放在它的后继结点 *(p next)的直接前趋指针域中。11.顺序表与链表的比较与选择线性表的长度是否固定：表长固定时用顺序表，表长不固定时用链表线性表的主要操作是什么：主要是查找时用顺序表，有较多插入、删除时用链表根据采用的算法语言：必须有指针类型时才能用链表第三章 栈与队列1. 栈定义：栈是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶 (Top)，另一端为栈底(Bottom) 。当表中没有元素时称为空栈。特性：后进先出（LIFO:Last In First Out ） ，先进后出（FILO: First In Last Out）

15、2. 顺序栈定义：用一维数组存储的栈。栈底固定不变，栈顶动态变化。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 40 页学习好资料欢迎下载typedef int datatype;#define StackSize 100struct Stack datatype elementsStackSize;int Top; /Top 表示顺序栈中栈顶之上的位置，/ 该位置将存放新的栈顶元素，当Top=0 表示空栈； / 注： Top 相当于栈内元素的个数当栈满时再做进栈运算必定产生空间溢出，简称“ 上溢 ”;当栈空时再做退栈运算也将产生溢出

16、，简称“ 下溢 ” 。基本操作：3. 链栈4. 栈的应用举例1)数制转换十进制数 N 和 d 进制数之间转换的算法原理：N=( N / d ) * d + N % d精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 40 页学习好资料欢迎下载即2)表达式求值算术四则运算规则：（1）先乘除，后加减；（2）从左算到右；（3）括号优先。四则运算由操作数（operand）和运算符 (operator) 构成。任意两个顺序出现的运算符1、 2的优先关系：1 2：1的优先级高于2。过程描述：（1）栈顶算符待比较算符，弹出栈顶算符，同时连续弹出数据栈内

17、的两个栈顶数据，进行计算，结果放回数据栈。待比较算符不变；（3）栈顶算符=待比较算符，弹出栈顶算符。（4）如果栈顶算符为#，计算结束。3)递归调用4)地图染色问题（回溯问题）用不多于四种的颜色对地图着色，使相邻的行政区域不重色基本思想： 行政区与颜色分别编号，从（1）号行政区开始，每个区域依次用颜色进行试探，若当前颜色与周围区域不重色，则用栈记下该区域的颜色序号，否则用下一颜色进行试探；若用四种颜色试探均重色，则需退栈回溯，修改栈顶颜色序号，再进行试探。直到满足要求。5)背包问题已知 n 件物品各自的体积，背包容积为T，要求从 n 件中找出若干物物品，其体积之和恰好等于背包容积，看是否有解。解

18、决思路： 顺序栈 S用来存放放入背包内的物品序号（最多有n 个元素）；参数 T 动态计算背包还可装入的重量；依次装入试验，不满足时从后往前回溯。5. 栈和队列的区别栈：只能在一端进行插入与删除操作，栈顶队列：插入在一端进行，删除在另一端进行6. 队列定义： 只允许在表的一端进行插入，而在另一端进行删除操作的线性表。队头（ Front） ：允许删除的一端（出队）；队尾（ Rear） ：允许插入的一端（入队）；1210121.nnNaadadad)1()2()1()1(1)0(0)(nnFibnFibnnnFib精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - -

19、 -第 9 页，共 40 页学习好资料欢迎下载特性： 先进先出（ First In First Out, FIFO ）7. 队列的存储结构1)顺序队列用数组存放队列中的元素，设置两个指针分别指示当前队头元素和队尾元素在数组中的位置。头指针 front 指向队头元素；尾指针 rear 指向队尾元素后一个位置。下溢： 队列为空时再做出队操作。上溢： 队列满时再做入队操作。假上溢： 尾指针等于数组上界时，即使队列不满，再进行入队也会产生上溢。解决方法：1. 每次出队时将整个队列的元素向前移动一个位置；2. 发生假上溢时将整个队列中的元素向前移动直到头指针为0;2)循环队列： 令数组 datamaxs

20、ize是一个首尾相接的圆环3)顺序队列的运算4)链队列仅在表头删除并仅在表尾插入的单链表，一个链队由一个头指针和一个尾指针惟一确定。建立在单链表定义的基础上， 在队头结点前附加一个头结点，头指针指向头结点。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 40 页学习好资料欢迎下载第四章 串1. 定义串，又称为字符串， 是不同于数值的一种数据类型，需要不同于一般数值的数据处理与存储形式。串(String)是由零个或多个字符组成的有限序列，一般记为：s = a1a2a3an (n 0)其中，单引号内的字符序列为串的值，ai（1in）可以是

21、字母、数字或其他字符；2. 基本概念长度： 串的字符数量n： str= abc123 长度 n=strlen(str)=6空串 ：长度为0 的串；str= 为空串 ; Not ?，后者称为 空格串子串 ：串中任意个连续的字符组成的子序列；str= abcdefg123456str1= cde ,str2= fg1234 ,str1、 str2 都是 str 的子串str1= fg 123 ,str2= bcdc ,str1、str2 都非 str 的子串主串： 包含子串的串；位置 ：字符在串中的序号。对于子串，位置是指其第一个字符在主串中的序号；Str= abcdef123456 , str1

22、= e ,str2= 23，str3= f123 Str1 在 str 中的位置为5，str2 在 str 中的位置为8, str3 在 str 中的位置为6，str2 在 str3 中的位置为3相等串： 长度相同，同时各位置上的字符都相等的两个串称为相等串。3. 串的特点串的逻辑结构同于线性表。串的数据对象为字符集。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 40 页学习好资料欢迎下载线性表中处理对象为“ 单个元素 ” ，而串往往以“ 串的整体 ” 为对象。4. 串与字符的区别字符是单个元素，串是一个字符集序列；字符是串的基本构

23、成元素字符没有长度的概念，串有长度即使长度为0字符与串的定义一般不同5. 串的表示方法三种方法：6. 定长顺序存储表示： 与线性表的顺序存储结构基本相同，但增加了一个单元存储串长度。另一种方式， 不存储串长度， 而是在串的结尾加一个特定字符。缺点： 串长度隐性表示，无法直观得到 (c 采用这种方法，最后是0 )。7.堆分配存储表示：这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在C语言中，利用动态存储管理函数malloc， 来根据实际需要动态分配和释放字符数组空间。这样定义的顺序串类型也有两种形

24、式。8.块链存储表示单链串 : 和线性表的链式存储相同。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 40 页学习好资料欢迎下载块链 :和线性表的链式存储相同。每个结点存放多个字符，结点又称为块。9.串模式匹配设有两个串t 和 p : t = t0t1tn-1，p = p0p1p m-1其中1m=n(通常mn)模式匹配的目的是在t 中找出和p 相同的子串。此时， t 称为“目标” ，而 p 称为“模式” 。模式匹配的结果有两种：匹配成功： t 中存在等于p 的子串，返回子串在t 中的位置匹配失败：返回一个特定的标志（如-1） 。朴素

25、的模式匹配p 中字符依次与t 中字符一一比较：如果对于所有的i( 0=i=m-1), 皆有 tj+i = pi，则匹配成功，返回位置j；否则，此趟匹配失败，这时将p 右移一个字符，进行下一趟匹配：直到匹配成功或p 移动到无法与t 继续比较为止（匹配失败）。时间复杂度朴素模式匹配算法一旦比较不等，p 右移一个字符并且下次从p0开始重新进行比较，对于目标t，存在回溯现象。匹配失败的最坏情况：每趟匹配皆在最后一个字符不等，且有n-m+1 趟匹配 (每趟比较 m 个字符）， 共比较 m*(n -m+1)次，由于 mn， 因此最坏时间复杂度O(n*m) 。匹配失败的最好情况：n-m+1 次比较 每趟只比

26、较第一个字符。匹配成功的最好情况：m 次比较。匹配成功的最坏情况：与匹配失败的最坏情况相同。综上讨论：朴素模式匹配算法的平均时间复杂度是O(n+m)最坏时间复杂度为O(m*n) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 40 页学习好资料欢迎下载第五章 数组与广义表1.数组的定义数组是由下标与值组成的数偶的有序结合，即其每一个元素是由一个值与一组下标所确定。说明：数组元素的值都是属于同一类型；下标决定了元素的位置；每个元素下标的个数决定数组的维数；数组是一个由相同类型数据元素组成的有序序列。2.数据结构三维数组的表示按行排放：三

27、维数组的表示按列排放：3.数组的存储结构1)顺序结构C语言、 Pascal 、COBOL ：行序为主序Fortran：列序为主序2)矩阵的压缩存储矩阵：二维表结构，通常采用二维数组表示。矩阵的运算：如转置、求逆、变换等矩阵的压缩存储：为多个具有相同值的元素分配一个存储空间；对零元不分配空间。A. 特殊矩阵 ：值相同元素或零元素在矩阵中的分布具有一定规律，如对称矩阵，对角矩阵；压缩方式： 对称矩阵： 若 n 阶矩阵 A 中的元素满足aij=aji,1=i,j=n 则称为 n 阶对称矩阵。矩阵压缩方式：为每一对对称元素分配一个存储空间。假设用一维数组Sn*(n+1)/2 作为对称矩阵A 的存储结构

28、，则两者间的元素间位置关系为：k=i*(i -1)/2+j -1 当 i j k=j*(j -1)/2+i -1 当 i1 时，其余结点可分为m（m0）个互不相交的有限集，其中每一个集合本身又是一棵树，称为根的子树。（注：可以理解成“ 除根以外的其它结点都有且仅有一个双亲结点” 。 ）递归定义。2.树的基本用语树的结点 ：包含一个数据元素及若干指向其子树的分支。结点的度 ：结点拥有的子树数。叶子或终端结点：度为 0 的结点。非终端结点或分支结点：度不为 0 的结点。树的度 ：树内各结点的度的最大值。结点的孩子 ：结点的子树的根称为该结点的孩子。结点的双亲 ：一个分支结点称为其孩子的双亲。兄弟

29、：同一个双亲的孩子之间互称兄弟结点；堂兄弟 ：其双亲在同一层的结点互称堂兄弟。结点的祖先：从根到该结点所经分支上的所有结点。结点的子孙 ：以某结点为根的子树中的任一结点都称为该结点的子孙。树的深度 ：树中结点的最大层次。下图中树的深度为4。有序树与无序树：将树中结点的各子树看成从左至右是有顺序的，即称为有序树；否则为无序树。森林 ：是 m(m 0) 棵互不相交的树的集合。就逻辑结构而言，任何一棵树是一个二元组Tree = ( root , F )其中 root是数据元素，根结点；F 是m(m 0) 棵树的森林， F=(T1,T2, ,Tm)，其中 Ti=(ri , Fi)称作根 root 的第

30、 i 棵子树 ;当 m 不为 0 时，在树根和其子树森林之间具有下列关系：RF= |i=1,2, ,m, m0精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 40 页学习好资料欢迎下载3.二叉树?定义：二叉树是另一种树结构，其每个结点最多只有两颗子树，并且子树有左右之分。二叉树的5 种基本形态：度为 2 的树和二叉树相同吗？性质：1)在二叉树的第i 层上至多有2i-1个结点。（i 1 ）2)深度为 k 的二叉树至多有2k-1 个结点。（ k 1）3)对任何一棵二叉树， 如果其终端结点为n0， 度为 2的结点树为n2， 则 n0=n2+

31、1。4)具有 n 个结点的完全二叉树的深度为1log2n(证明见上图 )5)如果对一棵有n 个结点的完全二叉树的结点按层序编号（从上到下， 从左到右），则对任一结点i(1 i n)，有：如果 i=1， 则结点 i 为根，无双亲； 如果 i1，则结点 i 的双亲结点是节点i/2如果 2*in ，则结点i 无左孩子，为叶子结点；否则其左孩子为结点2*i ；如果 2*i+1n ，则结点 i 无右孩子；否则其右孩子为结点2*i+1；满二叉树 ：一个深度为k 且有 2k-1 个结点的二叉树为满二叉树。完全二叉树 ：深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编

32、号从1 到 n 的结点一一对应时，称之为完全二叉树。存储结构 :1)顺序存储结构按照从上到下，从左到右的顺序存放完全二叉树上的结点信息。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 40 页学习好资料欢迎下载2)链式存储结构4.二叉树的遍历层次遍历（广度优先）层次遍历是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。对一棵非空的二叉树进行层次遍历，可按照如下步骤进行：1)初始化一个队列；2)二叉树的根结点放入队列；3)重复步骤 47 直至队列为空；4)从队列中取出一个结点x；5)访问

33、结点x；6)如果 x 存在左子结点，将左子结点放入队列；7)如果 x 存在右子结点，将右子结点放入队列。5.线索二叉树说明：遍历二叉树是将非线性结构的树转化为线性序列的形式。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 40 页学习好资料欢迎下载基本概念：线索链表： 以表示前驱与后继的结点构成的二叉链表作为二叉树的存储结构。线索： 线索链表中指向结点前驱和后继的指针。线索二叉树：加上线索的二叉树。线索化： 对二叉树，以某种次序遍历使其变为线索二叉树的过程。对同一棵二叉树遍历的方式不同，所得到的线索树也不同，二叉树有前序、 中序和后序

34、三种遍历方式，所以线索树也有前序线索二叉树、中序线索二叉树和后序线索二叉树 三种?如何保存由遍历二叉树得到的序列中结点的前驱与后继结点信息？一种方法：另一种方法：利用二叉树中的空链域（n 个结点有n+1 个空链域）。Ltag: 0, lchild 指示结点的左孩子。1, lchild 指示结点的前驱。Rtag: 0, rchild 指示结点的右孩子。1, rchild 指示结点的后继。通常在二叉树中增加一个与树中结点相同类型的头结点，令头结点的信息域为空，其lchild 域指向二叉树的根结点；其rchild 域指向以某种方式遍历二叉树时最后访问的结点，第一个被访问结点的左指针域和最后一个被访问

35、结点的右指针域的值如果是线索，也指向该头结点。遍历线索二叉树1)先找要遍历的第一个结点2)然后依次找结点的后继3)重复 2 直到其后继成为头结点问题的关键归结为如何在线索二叉树中找结点的后继例：中序线索二叉树中，找结点后继算法算法思想：对任意结点p，（1）若 rtag = 1，则 rchild 指向该结点的后继（2）若 rtag =0 ，则 rchild 指向该结点的右孩子。此时，按中序遍历的方法，从右孩子开始，沿左指针前进，直到找到没有左孩子的结点s(ltag=1)，则 s 就是 p 的后继。6.树和森林树的存储结构（1）双亲表示法用一组连续存储空间来存放结点，每个结点有两个域：data 域

36、-存放结点信息parent 域-存放双亲的位置特点 1：双亲表示法是顺序存储结构特点 2：求双亲很容易，但求孩子需要遍历整个数组（2）孩子表示法：多重链表每一个结点的孩子用单链表存储，成为孩子链表n 个结点可以有n 个孩子链表n 个孩子链表的头指针用一个数组表示特点：求孩子易，求双亲难精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 40 页学习好资料欢迎下载（3）双亲孩子表示法：在孩子表示法的头指针向量中，增加一项， 用来表示孩子的双亲。特点：结合了双亲表示法和孩子表示法的优点，求孩子和双亲都容易（4）孩子兄弟表示法用二叉链表作为存储

37、结构，结点左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。特点 1：双亲只管长子，长子连接兄弟特点 2：求孩子易，求双亲难特点 3：树和二叉树相互转换的媒介树与二叉树的转换（ 1）在兄弟之间增加一条连线；（ 2）对每个结点，除了保留与其左孩子的连线外，除去与其他孩子之间的连线；（ 3）以树的根结点为轴心，将整个树顺时针旋转45 度，使之结构层次分明。特点：根无右子树。森林与二叉树的转换把组成森林的所有树的根结点看成兄弟，就可以利用树与二叉树的转换规则实现森林和二叉树的转换森林 -二叉树：（1）将森林的第一棵树转换成二叉树，其根的右子树为空；（2）将第二棵树转换为新的二叉树，并将其作为前

38、一个二叉树的根的右子树；（3）以此循环，直到森林中所有树都被加入到二叉树中。二叉树 -森林：（1）将二叉树的根及其左子树转换为独立的二叉树；（2）将根的右子树，作为一个新的二叉树。（3）重复（ 1） （2） ，直到二叉树的右子树为空。7.哈夫曼树基本术语?路径长度：从树中一个结点到另一个结点所经过的分支构成这两个结点之间的路径，路径的分支数目称作这两个结点之间的路径长度。?树的路径长度：是从树根到树中每个结点之间路径长度之和。完全二叉树就是路径长度最短的二叉树。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 40 页学习好资料欢迎下载

39、?结点的带权路径长度：从根结点到某结点之间的路径长度与该结点所带权值的乘积，称为该结点的带权路径长度。其值为WkLk，其中 Lk为路径长度， Wk为权值。nkkkLWWPL1?树的带权路径长度：树的带权路径是树中所有叶子结点的带权路径长度之和。?哈夫曼树： 带权路径长度最小的树，称为哈夫曼树。又称为最优二叉树。哈夫曼树的特点是：权值最大的结点离根结点最近。哈夫曼算法：（1）根据给定的n 个权值 W1,W2,Wn，构造 n 棵二叉树的森林F=T1,T2, ,Tn，其中每棵二叉树Ti 中只有一个权值为Wi 的根结点，其左右孩子均为空树。（2）在 F 中选取二棵根结点权值最小的树作为左、右子树构造一

40、棵新二叉树，且置新二叉树根结点的权值为其左右子树上根结点权值之和。（3）在 F中删除这二棵树，同时将新得到的二叉树加入到F中。（4）重复 (2)和(3)，直到 F中只含有一棵树为止。这棵树就是哈夫曼树。特点 1：构造新树时，左右孩子未作规定特点 2：当有 n 权值相同的树作为候选树时，选择谁未作规定哈夫曼树没有度为1 的结点哈夫曼编码等长编码 A(00)、B(01)、C(10)、D(11) 长度最短：电文的编码总长最短的编码方案不等长编码 A(0)、B(1)、C(10)、D(11)0101 解码可能是ACB，也可能是ABAB原因： B的编码是C、 D编码的前缀，导致二义性前缀编码：若要设计长短

41、不等的编码，则必须是任一个字符的编码都不是另一个字符编码的前缀，这种编码方式称为前缀编码。A(0)、 B(10)、C(110)、D(111)：前缀编码具体作法如下：1）字符集合为d1，d2， ， dn，权值为它们在电文中出现的次数或频率集合w1，w2， ，wn 2）以 d1，d2， ，dn作为叶结点，w1，w2， ， wn作为它们的权值构造一棵哈夫曼树3）规定哈夫曼树中的左分支代表“ 0”，右分支代表 “ 1”，则从根结点到每个叶结点所经过的路径分支组成的0 或 1 序列便称之为该结点对应字符的编码，称之为哈夫曼编码。例，已知某系统在通讯联系中只出现8 种字符（a,b,c,d,e,f,g,h）

42、 ，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23, 0.03,0.11 ，试设计哈夫曼编码。0.05 0.29 0.07 0.08 0.14 0.23 0.03 0.110.08 0.29 0.07 0.08 0.14 0.23 0.110.15 0.29 0.08 0.14 0.23 0.110.15 0.29 0.19 0.14 0.23 0.29 0.29 0.19 0.230.29 0.29 0.420.58 0.421精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 40 页学习好资料欢迎下载第七章

43、图1. 基本概念图： 是一种比线性表和树更复杂的结构。GIS使用图来组织各种网络要素进行网络分析或路径分析。图是由顶点集V 和关系集 VR 构成的非线性数据结构，G=(V, VR) 。其中，V 是顶点的有穷非空集合，VR 是两个顶点之间的关系的集合（边集）。分为： 有向图： Directed graph 无向图： Undirected graph 弧： 如VR，则 表示从 a 到 b 的一条弧。 a 表示弧的起始顶点，称为弧尾 ；b表示弧的终止顶点，称为弧头 。有向图： 顶点之间有向联系(弧)的图。G1=V1, VR1其中， V1=A,B,CVR1=,边： 如VR 必有 VR，则以无序对(a,

44、b)代替这两个有序对，称为a 和 b 之间的一条边注：两个顶点之间最多只存在一条边，记为（顶点1，顶点 2） 。无向图： 顶点之间均通过边联接的图。G2=V2, VR2其中， V2=A,B,CVR2=(A,B),(B,C),(C,A)= (B,A),(C,B),(A,C)完全图： 每两个顶点之间都有边连接的无向图。对于具有 n个顶点的无向图， e的取值范围在0到 n(n-1)/2 之间。 完全图的 e为 n(n-1)/2 。证明一：每个顶点至多有n-1 条边与其他顶点相连，则n 个顶点至多有n(n-1)条边，但每条边连接两个顶点，所以最多n(n-1)/2 条边。证明二：组合理论有向完全图： 对

45、于有向图， e 的范围为0 到 n(n-1)，当 e 为 n(n-1)的有向图称为有向完全图。稀疏图与稠密图：有很少条边或弧 （如 enlogn）的图称为稀疏图，反之称为稠密图。子图： 两个同类型的图G1=(V1, E1)和 G2=(V2, E2)，存在关系V1属于或等于V2, E1属于或等于 E2，则称 G1是 G2的子图。无向图顶点的度：无向图中关联于某一顶点vi的边的数目。有向图顶点的度：顶点的入度和出度之和。入度： 以顶点 vi为终点（弧头）的弧的数目ID(vi) 出度： 以顶点 vi为起点（弧尾）的弧的数目OD(vi) 若图有 n 个顶点， e 条边或弧，每个顶点vi的度为 D(vi

46、)，则有 ：边的权： 与图的边或弧相关的数。网络： 每条边或弧都有权的带权图。路径： 从图中的顶点v1出发，沿着一些边或弧经过v1, v2, ,vn-1到达顶点vn的顶点序列( v1, v2, , vn-1, vn )niivDe12/)(精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 40 页学习好资料欢迎下载路径的长度：无权图中为路径经过的边或弧数，有权图中为沿路径各边或弧的权之和。回路： 第一个顶点与最后一个顶点相同的路径称为回路或环。简单路径： 路径序列中顶点不重复出现的路径。简单回路： 除了第一个顶点和最后一个顶点之外，其余

47、顶点不重复出现的回路。顶点连通： 无向图中两个顶点之间有路径相通，则称两个顶点是连通的。连通图： 顶点集合中任意两个顶点都连通的图。又分为：无向连通图和有向连通图无向图连通分量：无向图中的极大连通子图顶点强连通：在有向图中，若从vi到 vj、从 vj到 vi都存在路径，则称vi和 vj是强连通的。强连通图： 任意两个顶点都是强连通的有向图。有向图的强连通分量：有向图中的极大连通子图生成树： 一个连通图的生成树是一个极小连通子图（为什么？），它含有图中全部顶点，但只有足以构成一棵树的n-1 条边。三个必要条件：n 个顶点、 n-1 条边、连通树是最小的连通图2. 存储方法数组表示法（又称为“邻接

48、矩阵存储法”）使用一个一维数组来存放图中每个结点的数据信息，使用一个二维数组 （又称为邻接矩阵）来表示各顶点之间的关系。有 n 个顶点的图G 使用一个nn 的矩阵表示顶点间的关系，矩阵元素adj_mat i,j可按以下规则取值：邻接矩阵作用： （1）判断两个顶点之间是否相连；（ 2）计算顶点的度或出度和入度无向图： 顶点 i 的度是第i 行或第 i 列元素和有向图： 顶点 i 的出度是第i 行元素和，顶点i 的入度是第i 列元素和，顶点i 的度是第i 行元素和 +第 i 列元素和对网而言精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共

49、40 页学习好资料欢迎下载邻接表存储方法顺序存储与链式存储相结合。由两部分组成：（1）顶点表：使用一个具有两个域的结构体数组来存储每个顶点vi;其中一个域称为顶点域 (vertex), 存放顶点本身的数据信息，另一个域成为指针域(link)，存放依附于该顶点的边所组成的单链表的表头结点的存储位置。（2）邻接链表：邻接于vi 的顶点 vj 链接成的单链表称为vi 的邻接链表。其中每个结点由两个域构成， 一个是邻接点域(adjvex)， 用来存放邻接点序号；另一个是链域(next)，将邻接链表中的结点链接在一起。邻接表性质 : 对无向图 ,若顶点数n,边数 e（有向图为弧数）1.则头结点数n,表结

50、点数为2e2.对有向图，则头结点数n,表结点数为e精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 24 页，共 40 页学习好资料欢迎下载建立无向图邻接表的算法步骤：1 逐点依次输入结点信息，建立顶点表， 包括结点数值初始化与邻接链表头指针初始化；2 逐边依次输入邻接点对，对每次输入的结点对i 与 j, 分别建立其邻接链表（按单链表的头插法建表） ，即在 i 的邻接链表中增加j,在 j 的邻接链表中增加i.a)1 依次输入1、2、3、4 四个顶点的数据信息，并初始化单链表的头指针为NULL；b)2 输入（1，2） ，则 1 的邻接链表产生第一个结点