经贸大学2016年数据结构总复习

1、数据结构 总复习总复习 第一章 绪论 n重点内容重点内容 p 逻辑结构和物理结构逻辑结构和物理结构 p 顺序存储和链式存储顺序存储和链式存储 p 算法的五个特性算法的五个特性 p 算法的时间复杂度算法的时间复杂度 p 逻辑结构：数据元素之间的逻辑关系。逻辑结构：数据元素之间的逻辑关系。 p 物理结构（存储结构）：数据结构在计算机中的表物理结构（存储结构）：数据结构在计算机中的表 示，包括数据元素的表示和关系的表示。示，包括数据元素的表示和关系的表示。 3 顺序存储结构顺序存储结构：用数据元素在存储器中用数据元素在存储器中 的的相对位置相对位置来表示数据元素之间的逻辑来表示数据元素之间的逻辑 结

2、构结构( (关系关系) )。数据元素存放的地址是连数据元素存放的地址是连 续的续的 链式存储结构：借助指示元素存储地址链式存储结构：借助指示元素存储地址 得指针表示数据之间的逻辑关系。得指针表示数据之间的逻辑关系。数据数据 元素存放的地址是否连续没有要求元素存放的地址是否连续没有要求 4 5 顺序存储顺序存储以存储位置的相邻表示后继关系y 的存储位置和x的存储位置之间差一个常量C 链式存储链式存储以附加信息(指针)表示后记关系， 需要用一个和x在一起的附加信息指示y的存储 位置 x y yx p算法是为了解决某类问题而给出的一个有限长的算法是为了解决某类问题而给出的一个有限长的指指 令序列令序

3、列。 p 算法有以下算法有以下5个特性：个特性： n有穷性：有穷步骤，每步都有有穷的时间有穷性：有穷步骤，每步都有有穷的时间 n确定性：每条指令有确定的含义确定性：每条指令有确定的含义 n可行性：是能行的，基本运算的有限次运算完成可行性：是能行的，基本运算的有限次运算完成 n输入：输入：0 0个或多个输入，取自某个特定对象集合个或多个输入，取自某个特定对象集合 n输出：一个或多个输出，同输入有某些特定关系输出：一个或多个输出，同输入有某些特定关系 6 一个一个“好好”的算法需满足：的算法需满足： 7 程序程序中不含语法错误；中不含语法错误； 程序对于几组给定的输入可得到满足要求的结果程序对于几

4、组给定的输入可得到满足要求的结果 程序对于精心挑选的、典型的输入也可得到满足程序对于精心挑选的、典型的输入也可得到满足 要求的结果要求的结果 程序对于一切合法的输入均可以得出满足要求的程序对于一切合法的输入均可以得出满足要求的 结果结果 8 算法主要是为算法主要是为了人的阅读与交流了人的阅读与交流， 其次才是为计算机执其次才是为计算机执行行。 因此算法应该易于人的因此算法应该易于人的理解理解； 另另一方面，晦涩难读的程序易于隐藏较多错误而一方面，晦涩难读的程序易于隐藏较多错误而 难以调试和修改。难以调试和修改。 9 当当输入输入的数据非法的数据非法时，算法应当给予时，算法应当给予恰当的反应恰当

5、的反应 或进行相应的处理或进行相应的处理，而不是产生系统错误或莫名，而不是产生系统错误或莫名 其妙的结果其妙的结果。 处理出错处理出错的方法不应是中断程序的执行，的方法不应是中断程序的执行，而应而应 该返回错误提示该返回错误提示，以便在更高抽象层次上进行处，以便在更高抽象层次上进行处 理理。 10 假设，随着问题规模假设，随着问题规模n的增长，算法执行时的增长，算法执行时 间的增长率和间的增长率和f(n)的增长率相同，则可记作：的增长率相同，则可记作： T(n)=O(f(n) 称称T(n)为算为算法的（渐进）时间复杂度法的（渐进）时间复杂度 11 原操作原操作：固有数据类型的操作。固有数据类型

6、的操作。（如：（如：+，-， /，next n 因此，因此，链表不是随机存取结构链表不是随机存取结构 n 设单链表的长度为设单链表的长度为n，要查找表中第，要查找表中第i个结点，个结点， 仅当仅当1in时，时，i的值是合法的的值是合法的 单链表的插入 实现步骤实现步骤： n 首先，找到首先，找到ai-1所在所在的结点的结点p n 然后，生成一个数据域为然后，生成一个数据域为e的新结点的新结点s， n s结点作为结点作为p的直接后继结点，作为的直接后继结点，作为ai结点的直结点的直 接前驱结点。接前驱结点。 b p a b p a e s s-data=e;s-next=p-next; p-ne

7、xt=s; 单链表的删除 实现步骤实现步骤： n 首先找到首先找到ai-1的位置的位置p； n 然后令然后令pnext指向指向ai的直接后继结点，即把的直接后继结点，即把ai 从链上摘下从链上摘下 n 最后释放结点最后释放结点ai的空间的空间 ai p ai-1 ai+1 q=p-next;p-next=q-next; e=q-data; free(q); 静态链表 01 1ZHAO2 2QIAN3 3SUN4 4LI5 5ZHOU6 6WU7 7ZHENG8 8WANG0 9 1 0 01 1ZHAO2 2QIAN3 3SUN4 4LI9 5ZHOU6 6WU7 7ZHENG8 8WANG0

8、 9SHI5 1 0 01 1ZHAO2 2QIAN3 3SUN4 4LI9 5ZHOU6 6WU8 7ZHENG8 8WANG0 9SHI5 1 0 修改前修改前 在第在第5个位置个位置 插入插入SHI 删除删除ZHENG 循环链表 n 循环链表循环链表(Circular Linked List)：是一种头尾相：是一种头尾相 接的链表。其特点是最后一个结点的指针域指向接的链表。其特点是最后一个结点的指针域指向 链表的头结点，链表的头结点，整个链表的指针域链接成一个环整个链表的指针域链接成一个环。 n 从循环链表的从循环链表的任意一个结点出发任意一个结点出发都可以找到链表都可以找到链表 中的其

9、它结点，使得表处理更加方便灵活。中的其它结点，使得表处理更加方便灵活。 空表空表非空表非空表 a1 a2 an head head 双向链表的插入 S e p ab S e p ab 双向链表的插入双向链表的插入 n 算法主要语句算法主要语句 S=(DulNode *)malloc(sizeof(DulNode); S-data=e; S-prior=p-prior; p-prior-next=S; S-next=p; p-prior=S; n 设要删除设要删除的结点为的结点为p ，删除时直接先断链，删除时直接先断链，再，再 释放结点。部分语句组如下：释放结点。部分语句组如下： p-prior

10、-next=p-next; p-next-prior=p-prior; free(p); 与单链与单链表的插入和删除操作不同的是，在表的插入和删除操作不同的是，在 双向链表中双向链表中插入插入和和删除删除必须同时必须同时修改两个方向上修改两个方向上 的指针域的指向的指针域的指向。 双向链表的删除 a1a2a3 p 优点优点：易于查询，索引快：易于查询，索引快 缺点缺点：扩展性弱，不易删除、添加。：扩展性弱，不易删除、添加。 优点优点：扩展性强，易于删除、添加：扩展性强，易于删除、添加 缺点缺点：不易于查询，索引慢：不易于查询，索引慢 二者优缺点正好是互补关系，根据实际情况选择使二者优缺点正好是

11、互补关系，根据实际情况选择使 用用 顺序存储与链式存储的对比 第三章 栈和队列 n重点内容重点内容 p 栈和队列逻辑结构的特点栈和队列逻辑结构的特点 p 顺序栈的栈满、栈空判断顺序栈的栈满、栈空判断 p 循环队列的满与空的判断循环队列的满与空的判断 p 压栈、出栈算法压栈、出栈算法 p 进队列、出队列算法进队列、出队列算法 n 栈栈(Stack)：限制在表尾进行插入：限制在表尾进行插入 和删除操作的线性表。又称为后和删除操作的线性表。又称为后 进先出进先出LIFO (Last In First Out) n 栈顶栈顶(Top)：允许进行插入、删：允许进行插入、删 除操作的一端除操作的一端 n

12、栈底栈底(Bottom)：是固定端，又称：是固定端，又称 为表头。为表头。 n 空栈空栈：top=base n 满栈满栈: topmaxsize+1 a1 a2 an 栈顶栈顶 栈底栈底 进栈进栈 (Push) 出栈出栈 (Pop) 采用一组地址连续的存储单元依次存放自栈底到采用一组地址连续的存储单元依次存放自栈底到 栈顶的数据元素：栈顶的数据元素： n 用base表示栈底指针，栈底固定不变的；栈顶则随着 进栈和退栈操作而变化。 n 用top(称为栈顶指针)指示当前栈顶位置。 n 用top=base作为栈空的标记，每次top指向栈顶数组中 的下一个存储位置。 n 结点进栈：首先将数据元素保存到

13、栈顶(top所指的当 前位置)，然后执行top加1，使top指向栈顶的下一个 存储位置; n 结点出栈：首先执行top减1，使top指向栈顶元素的存 储位置，然后将栈顶元素取出。 空栈空栈 bottom top 元素元素a进栈进栈 bottom top a 元素元素b，c进栈进栈 bottom top a b c 元素元素c退栈退栈 bottom top a b bottom top a b d e f 元素元素d，e，f进栈进栈 3 元素进栈元素进栈 Status push(SqStack S , ElemType e) /* 使数据元素使数据元素e进栈成为新的栈顶进栈成为新的栈顶 */ i

14、f (S.top - S.base = S.stacksize) /栈满栈满 S.base=(SElemType *) realloc (S.base, (S.stacksize+STACKINCREMENT) * sizeof(SElemType); if (!S.base) exit (OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e ; /* 栈顶指针加栈顶指针加1 */ return OK; /* 压栈成功压栈成功 */ 4 弹栈弹栈( (元素元素出栈出栈) ) Status pop(

15、 SqStack /* 栈空，返回错误标志栈空，返回错误标志 */ e=*-S.top; return OK ; n 队列队列 (Queue)：也是运算受限的线性表。是：也是运算受限的线性表。是一种先一种先 进先出进先出(First In First Out ，简称，简称FIFO)的线性表。的线性表。 n 只允许在表的一端进行插入，而在另一端进行删只允许在表的一端进行插入，而在另一端进行删 除除 n 队头队头 (front) ：允许进行删除的一端称为队头。：允许进行删除的一端称为队头。 n 队尾队尾 (rear) ：允许进行插入的一端称为队尾。：允许进行插入的一端称为队尾。 a1 , a2 ,

16、 , an出队出队 入队入队 队尾队尾队头队头 n 队列的链式存储结构简称为链队列队列的链式存储结构简称为链队列 n 它是限制仅在表头进行删除操作和表尾进行它是限制仅在表头进行删除操作和表尾进行 插入操作的单链表。插入操作的单链表。 n 需要两类不同的结点：需要两类不同的结点：数据元素数据元素结点，队列结点，队列 的的队首指针和队尾指针队首指针和队尾指针的结点的结点 data front rear (a) 空队列空队列 front rear (b) x入队入队 x front rear (c) y再入队再入队 y front rear x (d) x出队出队 y x front rear 设立

17、一个队首指针设立一个队首指针front ，一个队尾指针，一个队尾指针rear ，分，分 别指向队首和队尾元素别指向队首和队尾元素。 初始化初始化：front=rear=0。 入队入队：将新元素插入将新元素插入rear所指的位置，然后所指的位置，然后rear加加1。 出队出队：删去删去front所指的元素，然后加所指的元素，然后加1并返回被删元并返回被删元 素。素。 队列为空队列为空：front=rear。 队满队满：rear=MAX_QUEUE_SIZE-1 (a) 空队列空队列 Q.front Q.rear (b) 入队入队3个元素个元素 a3 a2 a1 Q.front Q.rear (c

18、) 出队出队3个元素个元素 Q.front Q.rear (d) 入队入队2个元素个元素 a5 a4 Q.front Q.rear front=rear=0 将新元素插将新元素插 入入rear所指的所指的 位置，然后位置，然后 rear加加1 删去删去front所指所指 的元素，然后的元素，然后 加加1并返回被删并返回被删 元素元素 队列已满，队列已满， 但仍有存储但仍有存储 空间空间 n 充分利用向量空间充分利用向量空间，克服上述，克服上述“假溢出假溢出”现象现象 n 将为队列分配的向量空间看成为一个首尾相接将为队列分配的向量空间看成为一个首尾相接 的圆环，并称这种队列为的圆环，并称这种队列

19、为循环队列循环队列 1 2 34 5 0 循环循环队列队列 front rear 1 2 3 4 5 0 (a) 空队列空队列 front rear (b) d, e, b, g入入队队 front d e b g rear (c) d, e出队出队 b g front rear (d) i, j, k入入队队 b g front i j k rear (e) b, g出队出队 i j k rear front (f) r, p, s, t入队入队 i j k front r p rear Status EnQueue(SqQueue Q , ElemType e) /* 将数据元素e插入到循

20、环队列Q的队尾 */ if (Q.rear+1)%MAXSIZE= Q.front) return ERROR; /* 队满，返回错误标志 */ Q.baseQ. rear=e ; /* 元素e入队 */ Q.rear = (Q.rear+1) % MAXSIZE ; /* 队尾指针向前移动 */ return OK; /* 入队成功 */ Status DeQueue(SqQueue Q, ElemType /* 队空，返回错误标志 */ e = Q.baseQ.front ; /* 取队首元素 */ Q.front = (Q.front+1)% MAXSIZE ; /* 队首指针向前移动

21、*/ return OK ; 第四章 串 n重点内容重点内容 p 串的基本概念串的基本概念 n 串串( (字符串字符串) )：是零个或多个字符组成的有限序列：是零个或多个字符组成的有限序列。记作。记作： S=a1a2a3 n 其其中中S是串名，是串名，ai(1in)是单个，是单个，可以是字母、数字或可以是字母、数字或 其它字符。其它字符。 n 串值串值：双引号括起来的字符序列是串值。：双引号括起来的字符序列是串值。 n 串长串长：串中所包含的字符个数称为该串的长度。：串中所包含的字符个数称为该串的长度。 n 空串空串( (空的字符串空的字符串) )：长度为零长度为零的串称为空串，它不包含任的串

22、称为空串，它不包含任 何字符。何字符。 n 空空格串格串( (空白串空白串) )：构成串的所有：构成串的所有字符都是空格字符都是空格的串称为空的串称为空 白串。白串。 注意注意：空串和空白串的不同，例如：空串和空白串的不同，例如 和和分分 别表示长度为别表示长度为1 1的空白串和长度为的空白串和长度为0的空串。的空串。 第五章 数组和广义表 n重点内容重点内容 p 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 p 广义表的基本概念、求表头、表尾操作广义表的基本概念、求表头、表尾操作 两种顺序存储方式两种顺序存储方式 n 行优先顺序行优先顺序(Row Major Order) ：将数组元素按行排列，第将

23、数组元素按行排列，第 i+1个行向量紧接在第个行向量紧接在第i个行向量后面。对二维数组，按行优个行向量后面。对二维数组，按行优 先顺序存储的线性序列为：先顺序存储的线性序列为： a11,a12,a1n, a21,a22,a2n , am1,am2,amn PASCAL、C是按行优先顺序存储的是按行优先顺序存储的 n 列优先顺序列优先顺序(Column Major Order) ：将数组元素按列向量将数组元素按列向量 排列，第排列，第j+1个列向量紧接在第个列向量紧接在第j个列向量之后，对二维数组，个列向量之后，对二维数组， 按列优先顺序存储的线性序列为：按列优先顺序存储的线性序列为： a11,

24、a21,am1, a12,a22,am2, , an1,an2,anm FORTRAN是按列优先顺序存储的是按列优先顺序存储的 a11 a12 a1n a21 a22 a2n am1 am2 amn A= (a) 二维数组的表示形式二维数组的表示形式 (b) 行优先顺序存储行优先顺序存储(c) 列列优先顺序存储优先顺序存储 a11 a12 a1n 第第 1 行行 a21 a22 a2n 第第 2 行行 am1 am2 Amn 第第 m 行行 a11 a21 am1 第第 1 列列 a12 a22 am2 第第 2 列列 a1m a2m amn 第第 n 列列 给每一对对称给每一对对称元素元素a

25、ij和和aji(ij)分配分配1 1个存储空间个存储空间，则，则 n2个元素压缩存储到个元素压缩存储到n(n+1)/2个存储空间个存储空间 假设按假设按“行优先顺序行优先顺序”存储下三角形中的元素。存储下三角形中的元素。 设用一维数组设用一维数组( (向量向量) )sa0n(n+1)/2存储存储n阶对称阶对称 矩阵，矩阵， 为便于访问，找出矩阵为便于访问，找出矩阵A中的元素的下标值中的元素的下标值（i,j）和和 向量向量sak的的下标值下标值k之间的对应关系。之间的对应关系。 sa a00 a10 a11 an-1,0 an-1,1 an-1,n-1 K 1 2 3 4 n(n-1)/2 n(

26、n+1)/2 对称矩阵的对称矩阵的压缩存储示例压缩存储示例 n 广义表广义表(Lists，又称为列表，又称为列表 )：是由：是由n(n 0)个个 元素组成的有穷序列：元素组成的有穷序列： LS=(a1，a2，an) a1(表中第一个元素表中第一个元素)称为称为表头表头； 其余元素组成的子表称为其余元素组成的子表称为表尾表尾；(a2，a3， an) 广义表中所包含的元素广义表中所包含的元素(包括原子和子表包括原子和子表)的的 个数称为个数称为表的长度表的长度。 广义表中括号的最大层数称为表深广义表中括号的最大层数称为表深 (度度)。 第六章 树和二叉树 n重点内容重点内容 p 树和二叉树的定义及

27、相关概念树和二叉树的定义及相关概念 p 二叉树的二叉树的5 5个性质个性质 p 二叉树的各种存储结构二叉树的各种存储结构 p 树的各种存储结构树的各种存储结构 p 二叉树的各种遍历方法、中序遍历算法二叉树的各种遍历方法、中序遍历算法 p 线索二叉树的画法线索二叉树的画法 p 树的两种遍历方法树的两种遍历方法 p 哈夫曼树的构造、哈夫曼编码方法哈夫曼树的构造、哈夫曼编码方法 树树的的基本术语基本术语 n 结点结点(node)：数据元素：数据元素若干指向其子树的分支若干指向其子树的分支 n 结点的度结点的度(degree) ：结点所拥有的子树的个数称为：结点所拥有的子树的个数称为 结点的度结点的度

28、。 n 树树的度：的度：树中结点度的树中结点度的最大值最大值。 A A BDC EGFHI M J NKL 只有根结点只有根结点 树的基本术语树的基本术语 n叶子结点叶子结点：即度为即度为0 0的结点的结点 n分支结点分支结点：除叶子结点之外的其它结点除叶子结点之外的其它结点 n孩子孩子(Child)(Child)：若结点若结点x x有子树，则子树的根结有子树，则子树的根结 点是点是x x的孩子。的孩子。 n双亲(Parent)：若x有孩子结点，则该x结点称 为其孩子结点的双亲结点。 58 A BDC EGFHI M J NKL 树的基本术语树的基本术语 n兄弟结点：同一个双亲的孩子结点 n祖

29、先结点：从根结点到该结点所经路径上的所 有结点。 n子孙结点：以某个结点为根的子树以某个结点为根的子树中的任何一 个结点都称为该结点的子孙结点 n结点的层次：从根开始定义，根为第1层，根 的孩子为第2层 n堂兄弟：双亲结点在同一层上双亲结点在同一层上 59 A BDC EGFHI J 树的基本术语树的基本术语 n 有序树有序树：树中各个节点的子树树中各个节点的子树T1， T2，T3，之间是之间是有次序的有次序的，即，即 为有序树。即各个子树之间的左为有序树。即各个子树之间的左 右次序不能互换右次序不能互换 n 无序树无序树：树中各个节点的子树树中各个节点的子树T1， T2，T3，之间之间没有次

30、序关系没有次序关系的，的， 即为无序树。即为无序树。 60 A BCD E A CBD E 树的基本术语树的基本术语 n 树的深度树的深度：树中节点的树中节点的最大层次，最大层次，也称为树的也称为树的 高度或深度。高度或深度。 61 A BCD DEFHIJ KLM 第第1层层 第第2层层 第第3层层 第第4层层 62 二叉树的定义二叉树的定义 n 二叉树或者为空树二叉树或者为空树 n 或是由一个根结点加上两棵分别称为或是由一个根结点加上两棵分别称为左子树左子树 和和右子树右子树的、的、互不相交互不相交的二叉树组成。的二叉树组成。 E G B EF A A A AA (a)(b) (c) (d

31、)(e) 二叉树有二叉树有5种基本形态：种基本形态： 二叉树的特点：二叉树的特点： 1）每个结点的度）每个结点的度1，则其，则其 双亲结点双亲结点parent(i) 的编号是的编号是 i/2 。 如果如果2in，则编号为，则编号为 i 的结点无左孩子（编号为的结点无左孩子（编号为 i 的结点为叶子结的结点为叶子结 点）；否则其左孩子结点点）；否则其左孩子结点LChild(i)的编号是的编号是2i 。 如果如果2i+1n，则编号为，则编号为 i 的结点无右孩子；否则其右孩子结点的结点无右孩子；否则其右孩子结点 RChild(i) 的编号是结点的编号是结点2i+1。 i i+1 2i2i+1 2i

32、+22i+3 i/2 (a) i和和i+1结点在同一层结点在同一层 i+1 2i+22i+3 i 2i2i+1 (b) i和和i+1结点不在同一层结点不在同一层 顺序存储结构顺序存储结构 二叉树存储结构的类型定义：二叉树存储结构的类型定义： # define MAX_SIZE 100 typedef telemtype sqbitreeMAX_SIZE; SqBiTree bt; n 用一组地址连续的存储单元依次用一组地址连续的存储单元依次“自上而下自上而下、自左自左 至右至右”存储完全二叉树存储完全二叉树的数据元素的数据元素。 n 对于完全二叉树上对于完全二叉树上编号为编号为i的结点元素存储

33、在一维的结点元素存储在一维 数组的下标值为数组的下标值为i-1的分量中的分量中 n 对于一般的二叉树，对于一般的二叉树，将其每个结点与完全二叉树上将其每个结点与完全二叉树上 的结点相对照的结点相对照，存储在一维数组中存储在一维数组中 a bc d hi e jk l fg (a) 完全二叉树完全二叉树 (b) 非完全二叉树非完全二叉树 a bc de fg h0 00 0 1 2 3 4 5 6 7 8 9 10 11 a b c d e f g h i j k l (c) 完全二叉树的顺序存储形式完全二叉树的顺序存储形式 0 1 2 3 4 5 6 7 8 9 10 a b c d e 0

34、h 0 0 f g (d) 非完全二叉树的顺序存储形式非完全二叉树的顺序存储形式 最坏的情况下，一个深度为最坏的情况下，一个深度为k且且 只有只有k个结点的单支树需要长度个结点的单支树需要长度 为为2k-1的一维数组的一维数组。 链式存储结构链式存储结构 二叉链表二叉链表。 结点有三个域：结点有三个域：一个数据域一个数据域，两个分别指向左右子结，两个分别指向左右子结 点的点的指针域指针域 typedef struct BTNode ElemType data ; struct BTNode *Lchild , *Rchild ; BTNode ; Lchild data Rchild (a)

35、二叉链表结点二叉链表结点 三三叉链表叉链表 除二叉链表的三个域外，再增加一个指针域，除二叉链表的三个域外，再增加一个指针域，用来用来 指向指向结点的父结点结点的父结点 typedef struct BTNode_3 ElemType data ; struct BTNode_3 *Lchild , *Rchild , *parent ; BTNode_3 ; Lchild data parent Rchild 三三叉链表结点叉链表结点 (2) 二叉树的链式存储形式二叉树的链式存储形式 (a) 二叉树二叉树 a fe dc b g (c) 三三叉链表叉链表 a b c d e f g T (b)

36、 二二叉链表叉链表 a b c d e g f T 1 双亲表示法双亲表示法 typedef struct PTNode NodesMAX_SIZE ; int r，n; / 根结点位置，结根结点位置，结点数点数 Ptree ; F GHI R ABC DE 树的双亲存储结构树的双亲存储结构 R -10 A 01 B 02 C 03 D 14 E 15 F 36 G 67 H 68 I 69 r=0 n=10n 这种存储结构利用了任一结点的这种存储结构利用了任一结点的 双亲结点唯一的性质。双亲结点唯一的性质。可以方便可以方便 地直接找到任一结点的双亲地直接找到任一结点的双亲 n 但求结点的孩子

37、结点时需要扫描但求结点的孩子结点时需要扫描 整个数组。整个数组。 nodes 789 35 012 6 0 1 2 3 4 5 6 7 8 9 MAX_NODE-1 r n A B C D E F G H I R 4 10 孩子链表存储结构孩子链表存储结构 孩子链表表示法孩子链表表示法 F GHI R ABC DE (b) 树树 FG R ABC DE (c) 孩子兄弟存储结构孩子兄弟存储结构 R A D C G B F E 孩子结点孩子结点兄弟结点兄弟结点 firstchild data nextsibing (a) 结点结构结点结构 3 孩子兄弟孩子兄弟表示法表示法 先左先左后右的遍历算法

38、后右的遍历算法 n 先先(根根)序序的遍历的遍历算法算法DLR n 中中(根根)序序的遍历的遍历算法算法LDR n 后后(根根)序序的遍历的遍历算法算法LRD 77 根 左左 子树子树 右右 子树子树 78 n 遍历序列可否唯一确定一棵二叉树？遍历序列可否唯一确定一棵二叉树？ 先序序列：先序序列：ABIDEFGCHJ 中序序列：中序序列：IBFEDGAJHC A BC I D E F G H J n 遍历二叉树遍历二叉树的结果是求得结点的一个线性序列的结果是求得结点的一个线性序列。 n 指向该线指向该线性序列中的性序列中的“前驱前驱”和和“后继后继”的指针，称作的指针，称作 “线索线索”。 n

39、 包含包含“线索线索”的的存储结构存储结构称作称作“线索链表线索链表”；与其相应的；与其相应的 二叉树，称为二叉树，称为“线索二叉树线索二叉树”。 79 A F HI E G B D C A F HI E G B D C NIL 前序遍历结点序列：前序遍历结点序列：ABDCEGFHI A F HI E G B D C (a) 二叉树二叉树 (b) 先序线索树的逻辑形式先序线索树的逻辑形式 结点序列：结点序列：ABDCEGFHI A F HI E G B D C NIL (d) 后序线索树的逻辑形式后序线索树的逻辑形式 结点序列：结点序列：DBGEHIFCA (c) 中序线索树的逻辑形式中序线索

40、树的逻辑形式 结点序列：结点序列：DBAGECHFI A F HI E G B D C NIL NIL A F HI E G B D C NIL n 线索二叉树的指针信息存储在哪里？线索二叉树的指针信息存储在哪里？ p 设一棵二叉树有设一棵二叉树有n个结点，则有个结点，则有n-1条边条边 (指针指针 连线连线) ， 而而n个结点共有个结点共有2n个指针域个指针域 (Lchild 和和 Rchild) ，显然，显然有有n+1个空闲指针域个空闲指针域未用。未用。 p 可以利用这些空闲的指针域来存放结点的可以利用这些空闲的指针域来存放结点的直直 接前驱接前驱和和直接后继直接后继信息。信息。 81 对

41、结点的指针域做如下规定：对结点的指针域做如下规定： n 若结点有左子树，则若结点有左子树，则Lchild指向其左子树，指向其左子树，Ltag0；否否 则，指向其直接前驱，则，指向其直接前驱，Ltag1； n 若结点有右子树，则若结点有右子树，则Rchild指向其右子树，指向其右子树，Rtag0；否否 则，指向其直接后继，则，指向其直接后继，Rtag1； Lchild Ltag data Rchild Rtag 线索二叉树的结点结构线索二叉树的结点结构 0：Lchild域指示结点的左孩子域指示结点的左孩子 1 1：Lchild域指示结点的前驱域指示结点的前驱 Ltag= 0 0：Rchild域指

42、示结点的右孩子域指示结点的右孩子 1 1：Rchild域指示结点的后继域指示结点的后继 Rtag= 6.4.3 树和森林的遍历树和森林的遍历 1 树的遍历树的遍历 由树结构的定义可知，树的遍历有二种方法。由树结构的定义可知，树的遍历有二种方法。 (1) 先根序遍历先根序遍历：先访问根结点，然后：先访问根结点，然后先序遍历完先序遍历完每棵子树。每棵子树。 (2) 后根序遍历后根序遍历：先：先依次后序遍历完依次后序遍历完每棵子树，然后访问根结每棵子树，然后访问根结 点。点。 A B DC K G JI FH E 先序遍历：先序遍历：ABCDEFGIJHK 后序遍历：后序遍历：CDBFIJGHEKA

43、 基本概念基本概念 结点路径结点路径：从树中一个结点到另一个结点的之间的分支：从树中一个结点到另一个结点的之间的分支 构成这两个结点之间的路径。构成这两个结点之间的路径。 路径长度路径长度：结点路径上的分支数目称为路径长度：结点路径上的分支数目称为路径长度。 树的路径长度树的路径长度：从树根到每一个结点的路径长度之和：从树根到每一个结点的路径长度之和。 A B DC K G JI FH E A到到F ：结点路径：结点路径 AEF ； 路径长度路径长度( (即边的数目即边的数目) )：2 ； 树的路径长度树的路径长度： 31+52+23=19 结点的带权路径长度结点的带权路径长度：从该结点的到树

44、的根结点之间的路：从该结点的到树的根结点之间的路 径长度与结点的权径长度与结点的权( (值值) )的乘积的乘积。 权权( (值值) )：各种：各种开销开销、代价代价、频度频度等的抽象称呼等的抽象称呼。 树的带权路径长度树的带权路径长度：树中：树中所有叶子结点所有叶子结点的带权路径长度之的带权路径长度之 和，记做：和，记做： WPL=w1 l1+w2 l2+ +wn ln=wi li (i=1,2, ,n) 其中：其中：n为叶子结点的个数为叶子结点的个数；wi为第为第i个结点的权值个结点的权值； li为第为第i个结点的路个结点的路 径长度。径长度。 Huffman树树：具有：具有n个叶子结点个叶

45、子结点(每个结点的权值为每个结点的权值为wi) 的的 二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵 WPL值最小的树值最小的树，称这棵树为，称这棵树为Huffman树树(或称最优树或称最优树) 。 基本概念基本概念 Huffman树的构造树的构造 根据根据n个权值个权值w1, w2, ,wn，构造成，构造成n棵二叉树的集合棵二叉树的集合 F=T1, T2, ,Tn，其中每棵二叉树只有一个权值为，其中每棵二叉树只有一个权值为wi的的 根结点，没有左、右子树；根结点，没有左、右子树； 在在F中中选取两棵根结点权值最小选取两棵根结点权值最小

46、的树作为左的树作为左、右子树构造右子树构造 一棵新的二叉树，且新的二叉树根结点权值为其左一棵新的二叉树，且新的二叉树根结点权值为其左、右子右子 树根结点的权值之和；树根结点的权值之和； 在在F中删除这两棵树，同时将新得到的树加入中删除这两棵树，同时将新得到的树加入F中；中； 重复、，直到重复、，直到F只含一颗树为止。只含一颗树为止。 规定规定F=T1,T2, ,Tn中中权值小权值小的二叉树作为新构造的二叉的二叉树作为新构造的二叉 树的树的左子树左子树，权值大的二叉树作为新构造的二叉树的右子权值大的二叉树作为新构造的二叉树的右子 树树； 在取值相等时，在取值相等时，深度小深度小的二叉树作为新构造

47、的二叉树的的二叉树作为新构造的二叉树的左左 子树子树，深度大的二叉树作为新构造的二叉树的右子树深度大的二叉树作为新构造的二叉树的右子树。 权值集合权值集合W=8, 3, 4, 6, 5, 5构造构造Huffman树的过树的过 程程。所构造的所构造的Huffman树的树的WPL是是： WPL=6 2+3 3+4 3+8 2+5 3+5 3 =79 345568 第一步 5568 第二步 34 7 68 第三步 34 7 55 10 8 第四步 55 10 6 34 7 13 第六步 1 1 1 1 1 0 0 0 0 0 8 55 10 18 6 34 7 13 31 第五步 8 55 10 1

48、8 6 34 7 13 例子例子 Huffman编码编码 p在电报收发等数据通讯中在电报收发等数据通讯中，常需要将传送的文字常需要将传送的文字 转换成由二进制字符转换成由二进制字符0、1组成的字符串来传输组成的字符串来传输。 n 为了使收发的速度提高为了使收发的速度提高，要求电文要求电文编码要尽可编码要尽可 能短能短。 n 要设计要设计长短不等长短不等的编码，还必须保证的编码，还必须保证任意字符任意字符 的编码都不是另一个字符编码的前缀的编码都不是另一个字符编码的前缀，称为，称为前前 缀编码缀编码。 pHuffman树可以用来构造编码长度不等且译码不树可以用来构造编码长度不等且译码不 产生二义

49、性的编码产生二义性的编码。 Huffman编码方法编码方法 设电文中的字符集设电文中的字符集C=c1,c2, ,ci, ,cn，各个字符，各个字符 出现的次数或频度集出现的次数或频度集W=w1,w2, ,wi, ,wn。 以以字符集字符集C作为叶子结点作为叶子结点，次数或频度集次数或频度集W作为结作为结点点 的权值的权值来构造来构造Huffman树树。 规规定定Huffman树中左分支代表树中左分支代表“0”，右分支代表，右分支代表 “1” 。 从根结点到每个叶子结点所经历从根结点到每个叶子结点所经历的路径分支上的的路径分支上的“0” 或或“1”所组成的字符串所组成的字符串，为该结点所对应的编

50、码为该结点所对应的编码，称称 之为之为Huffman编码编码。 * *由于每个字符都是叶子结点由于每个字符都是叶子结点，不可能出现在根结点到其它字符，不可能出现在根结点到其它字符 结点的路径上，所以一个字符的结点的路径上，所以一个字符的Huffman编码不可能是另一个字编码不可能是另一个字 符的符的Huffman编码的前缀编码的前缀。 第七章 图 n重点内容重点内容 p 图的定义及相关术语图的定义及相关术语 p 图的各种存储结构图的各种存储结构 p 图的深度优先遍历和广度优先遍历法图的深度优先遍历和广度优先遍历法 p 图的最小生成树的概念图的最小生成树的概念 p 克鲁斯卡尔算法、普里姆算法生成

51、最小生成树克鲁斯卡尔算法、普里姆算法生成最小生成树 p 图的拓扑排序、关键路径的求法图的拓扑排序、关键路径的求法 91 7.2 图的存储结构图的存储结构 图的数组存储表示法 基本思想基本思想： n 对于对于有有n个顶点的图，用一维数组个顶点的图，用一维数组vexsn存存 储顶点信储顶点信息息 n 用二维数组用二维数组Ann存储顶点之间关系的信存储顶点之间关系的信息息 n 该二维数组称为该二维数组称为邻接矩阵邻接矩阵 n 在邻接矩阵中在邻接矩阵中： p 以顶点在vexs数组中的下标代表顶点 p 邻接矩阵中的元素Aij存放的是顶点i到顶 点j之间关系的信息 92 1 无向图的数组表示无向图的数组表

52、示 (1) 无权图的邻接矩阵无权图的邻接矩阵 无向无权图无向无权图G=(V，E)有有n(n1)个顶点，其邻接矩阵是个顶点，其邻接矩阵是 n阶对称方阵阶对称方阵，其元素的定义如下：，其元素的定义如下： 1 若若(vi , vj) E，即，即vi , vj邻接邻接 0 若若(vi , vj) E，即，即vi , vj不邻接不邻接 Aij= (a) 无向图无向图 a bc d (b) 顶点矩阵顶点矩阵 vexs a b c d 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 (c) 邻接矩阵邻接矩阵 (2) 带权图（网）的邻接矩阵带权图（网）的邻接矩阵 无向带权图无向带权图G=(V，

53、E) 的邻接矩阵元素的定义如下：的邻接矩阵元素的定义如下： 带权无向图带权无向图 邻接矩阵邻接矩阵 3 5 4 1 2 6 ab cd e 3 vexs a b c d e 6 2 6 3 4 3 2 3 1 4 3 5 3 5 Wij 若若(vi , vj) E，即，即vi , vj邻接，权值为邻接，权值为wij 若若(vi , vj) E，即，即vi , vj不邻接时不邻接时 Aij= 特点：特点： 1、无向图的邻接矩阵是、无向图的邻接矩阵是对称方阵对称方阵； 2、顶点、顶点vi的度数的度数是第是第i行的行的非非0元素的个数元素的个数； 3 3、无向图的边数是上无向图的边数是上(或下或下)

54、三角形矩阵中三角形矩阵中非非0元元 素个数素个数。 95 2 有向图的数组表示有向图的数组表示 (1) 无权图的邻接矩阵无权图的邻接矩阵 有向无权图有向无权图G=(V，E)有有n(n1)个顶点，则其邻接矩个顶点，则其邻接矩 阵是阵是n阶对称方阵阶对称方阵元素定义如下：元素定义如下： 1 若若 E，从，从vi到到vj有弧有弧 Aij= 0 若若 E 从从vi到到vj 没有弧没有弧 (a) 有向图有向图 a c b d e (b) 顶点矩阵顶点矩阵 a b c d e (c) 邻接矩阵邻接矩阵 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 (2

55、) 带权图的邻接矩阵带权图的邻接矩阵 有向带权图有向带权图G=(V，E)的邻接矩阵元素的定义如下：的邻接矩阵元素的定义如下： wij 若若 E，即，即vi , vj邻接，权值为邻接，权值为wij 若若 E，即，即vi , vj不邻接时不邻接时 Aij= (b) 顶点矩阵顶点矩阵 a b c d e (c) 邻接矩阵邻接矩阵 6 2 3 3 1 4 5 (a) 带权有向图带权有向图 3 5 4 1 2 6 ab cd e 3 特点：特点： 1 1、对于顶点对于顶点vi，第第i行行的非的非0元素的个数是其出度元素的个数是其出度 OD(vi)；第第i列列的非的非0元素的个数是其入度元素的个数是其入度

56、ID(vi) 。 2、邻接矩阵中、邻接矩阵中非非0元素的个数就是图的元素的个数就是图的弧的数目弧的数目。 7.2.2 邻接链表法邻接链表法 基本基本思想思想： n 对图对图的的每个顶点每个顶点建立一个建立一个单链表单链表，存储该顶点所有，存储该顶点所有 邻接顶点及其相关信息邻接顶点及其相关信息。 n 每一个单链表设一个每一个单链表设一个表头结点表头结点。 n 第第i个单链表个单链表: 表示依附于顶点表示依附于顶点Vi的边的边 (对有向图是以对有向图是以 顶点顶点Vi为尾的为尾的弧弧)。 1 结点结构与邻接链表示例结点结构与邻接链表示例 n 链表中的结点称为链表中的结点称为表结点表结点，表结点由

57、三个域组，表结点由三个域组成：成： p 邻邻接点域：指示与顶点接点域：指示与顶点Vi邻接的顶点在图邻接的顶点在图中的位置中的位置 p 链域：指向下一个与顶点链域：指向下一个与顶点Vi邻接的表结点，邻接的表结点， p 数据域：存储和边或弧相关数据域：存储和边或弧相关的信息，如权值等。的信息，如权值等。 n表头结点表头结点(称为称为顶点结点顶点结点)，由两个域组成：，由两个域组成： p 链域：指向链表链域：指向链表中的第一个结点中的第一个结点 p 数据域数据域： 存储顶点名或其他信息。存储顶点名或其他信息。 adjvex info nextarc 表结点表结点： data firstarc 表头结

58、点表头结点： n 所有所有顶点结点顶点结点用一个向量以顺序结构形式存储，可用一个向量以顺序结构形式存储，可 以随机访问任意顶点的链表，该向量称为以随机访问任意顶点的链表，该向量称为表头向量表头向量 n 向向量的下标指示量的下标指示顶点的位置顶点的位置？ v1 v2v3 v4 v5 0 1 2 3 4 v1 v2 v3 v4 v5 213 02 0314 204 23 无向图邻接表无向图邻接表 有向图有向图 v1 v2v3 v4 v5 13 014 2 3 0 1 2 3 4 v1 v2 v3 v4 v5 正邻接链表正邻接链表 出度直观出度直观 2 02 2 0 1 2 3 4 MAX_VEX-

59、1 v1 v2 v3 v4 v5 3 04 逆邻接链表逆邻接链表 入度直观入度直观 有向图邻接表有向图邻接表 n 有向图的邻接表有两有向图的邻接表有两 种：种：正邻接表正邻接表和和逆邻逆邻 接表接表 n 正邻接表正邻接表是以顶点是以顶点Vi为出为出 度而度而建立的邻接表建立的邻接表； n 逆邻接表逆邻接表是以顶点是以顶点Vi为入为入 度而度而建立的邻接表；建立的邻接表； 2 邻接表法的特点邻接表法的特点 n 表头向量中每个分量就是一个单链表的头结点，表头向量中每个分量就是一个单链表的头结点，分量个数分量个数 就是图中的顶点数目就是图中的顶点数目； n 在在边或弧稀疏边或弧稀疏的情况下的情况下，

60、用邻接表表示比用邻接矩阵表示，用邻接表表示比用邻接矩阵表示 节省存储空间；节省存储空间； n 在无向图，在无向图，顶点顶点Vi的度是第的度是第i个链表的结点数个链表的结点数； n 在有向图中在有向图中，第，第i个链表中的结点数是顶点个链表中的结点数是顶点Vi的出的出 (或入或入)度；度； 求入求入 (或出或出)度，须遍历整个邻接表；度，须遍历整个邻接表； n 在邻接表上容易找出任一顶点的第一个邻接点和下一个邻在邻接表上容易找出任一顶点的第一个邻接点和下一个邻 接点接点； n 要判定两个顶点要判定两个顶点Vi和和Vj之间是否有边，需要搜索第之间是否有边，需要搜索第i个或第个或第 j个链表个链表