数据结构基础复习.ppt

数据结构数据结构考研辅导考研辅导 基础复习基础复习浙江大学计算机学院浙江大学计算机学院内容提纲内容提纲考研概述考研概述1基础内容复习基础内容复习2线性表、堆栈、队列、数组线性表、堆栈、队列、数组A树与图树与图B查找与排序查找与排序C考研概述考研概述v考察目标考察目标理解数据结构的基本概念：掌握数据结构理解数据结构的基本概念：掌握数据结构的逻辑结构、存储结构及其差异，以及各的逻辑结构、存储结构及其差异，以及各种基本操作的实现。种基本操作的实现。在掌握基本的数据处理原理和方法的基础在掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。上，能够对算法进行设计与分析。能够选择合适的数据结构和方法进行问题能够选择合适的数据结构和方法进行问题求解。求解。考研概述考研概述v考试形式考试形式整卷满分为整卷满分为150分，考试时间为分，考试时间为180分钟分钟数据结构占数据结构占45分，估计用时分，估计用时4550分钟分钟单选题：单选题：40题题 2分分/题，估计占题，估计占10题题20分左分左右，建议用时不超过右，建议用时不超过2分钟分钟/题题综合题：综合题：70分，估计占分，估计占2题共题共2025分，建分，建议用时不超过议用时不超过10分钟分钟/题题考研概述考研概述v复习计划复习计划基础理论复习基础理论复习例题详解例题详解题目范围：真题题目范围：真题1套套+模拟题模拟题9套套+补充题补充题模拟题第模拟题第10套将用于最后一天模拟考试套将用于最后一天模拟考试基础内容复习基础内容复习数据结构（数据结构（C语言版）语言版），严蔚敏、吴伟民，清华大学出版社，严蔚敏、吴伟民，清华大学出版社v线性表、堆栈、队列、数组线性表、堆栈、队列、数组v树与图树与图v查找与排序查找与排序6线性表、堆栈、队列、数组线性表、堆栈、队列、数组v 线性表线性表定义：定义：n个数据元素的有限序列个数据元素的有限序列基本操作：随机访问、插入、删除、前驱、后基本操作：随机访问、插入、删除、前驱、后继、倒序等继、倒序等实现方式：实现方式：顺序存储：数组顺序存储：数组aiai+1Loc(ai)Loc(ai+1)=Loc(ai)+llLoc(ai)=Loc(a1)+?(i-1)*lv线性表线性表实现方式：实现方式：顺序存储：数组顺序存储：数组线性表、堆栈、队列、数组线性表、堆栈、队列、数组 是一种随机存取的存储结构，方便随机存是一种随机存取的存储结构，方便随机存取第取第i个数据元素个数据元素 插入、删除复杂度为插入、删除复杂度为O(n)，需要移动大量，需要移动大量元素元素v自测题自测题在在n个结点的顺序表中，算法的时间复杂度是个结点的顺序表中，算法的时间复杂度是O(1)的操作是：的操作是：A.访问第访问第i个结点个结点(1in)和求第和求第i个结点的直接前驱个结点的直接前驱(2in)B.在第在第i个结点后插入一个新结点（个结点后插入一个新结点（1in）C.删除第删除第i个结点（个结点（1in）D.将将n个结点从小到大排序个结点从小到大排序线性表、堆栈、队列、数组线性表、堆栈、队列、数组线性表、堆栈、队列、数组线性表、堆栈、队列、数组v线性表线性表实现方式：实现方式：链式存储：链表链式存储：链表 线性链表线性链表存储地存储地址址数据域数据域指针域指针域1LiNULL7Qian1313Sun119Zhao7头指针头指针H=19HZhaoQianSunLi 若若 p-data=ai 则则 p-next-data=ai+1typedef struct LNode ElemType data;struct LNode *next;LNode,*LinkList;有时附加有时附加头结点头结点v自测题自测题线线性性表表若若采采用用链链式式存存储储结结构构时时，要要求求内内存存中中可可用用存储单元的地址存储单元的地址:A.必须是连续的必须是连续的B.部分地址必须是连续的部分地址必须是连续的C.一定是不连续的一定是不连续的D.连续或不连续都可以连续或不连续都可以线性表、堆栈、队列、数组线性表、堆栈、队列、数组线性表、堆栈、队列、数组线性表、堆栈、队列、数组v线性表线性表实现方式：实现方式：链式存储：链表链式存储：链表 线性链表线性链表 插入、删除复杂度为插入、删除复杂度为O(1)，仅需修改指针，仅需修改指针而而不不需要移动元素需要移动元素 是一种是一种非非随机存取的存储结构，随机存取的存储结构，不不方便随方便随机存取第机存取第i个数据元素个数据元素*静态链表静态链表（p.31-35）v自测题自测题下面的叙述不正确的是（下面的叙述不正确的是（）A.线性表在链式存储时，查找第线性表在链式存储时，查找第i个元素的时间个元素的时间同同i的值成正比的值成正比B.线性表在链式存储时，查找第线性表在链式存储时，查找第i个元素的时间个元素的时间同同i的值无关的值无关C.线性表在顺序存储时，查找第线性表在顺序存储时，查找第i个元素的时间个元素的时间同同i 的值成正比的值成正比D.线性表在顺序存储时，查找第线性表在顺序存储时，查找第i个元素的时间个元素的时间同同i的值无关的值无关线性表、堆栈、队列、数组线性表、堆栈、队列、数组v自测题自测题在一个单链表中，若在一个单链表中，若p所指的结点不是最后结点，所指的结点不是最后结点，在在p之后插入之后插入s所指结点，则执行：所指结点，则执行：A.s-next=p;p-next=s;B.s-next=p-next;p-next=s;C.s-next=p-next;p=s;D.p-next=s;s-next=p;线性表、堆栈、队列、数组线性表、堆栈、队列、数组psv自测题自测题在单链表中，指针在单链表中，指针p指向元素为指向元素为x的结点，实现的结点，实现“删除删除x的后继的后继”的语句是：的语句是：A.p=p-next;B.p-next=p-next-next;C.p-next=p;D.p=p-next-next;线性表、堆栈、队列、数组线性表、堆栈、队列、数组xp线性表、堆栈、队列、数组线性表、堆栈、队列、数组v线性表线性表实现方式：实现方式：链式存储：链表链式存储：链表 循环链表循环链表 双向链表双向链表HHHH有时设有时设尾指尾指针针可简化某可简化某些操作，如些操作，如两表合并。两表合并。v自测题自测题设一个链表最常用的操作是在末尾插入结点和删设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用除尾结点，则选用()最节省时间。最节省时间。A.单链表单链表 B.单循环链表单循环链表 C.带尾指针的单循环链表带尾指针的单循环链表 D.带头结点的双循环链表带头结点的双循环链表线性表、堆栈、队列、数组线性表、堆栈、队列、数组v自测题自测题将线性表将线性表La和和Lb头尾连接，要求时间复杂度为头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结，且占用辅助空间尽量小。应该使用哪种结构？构？A.单链表单链表 B.单循环链表单循环链表 C.带尾指针的单循环链表带尾指针的单循环链表 D.带头结点的双循环链表带头结点的双循环链表线性表、堆栈、队列、数组线性表、堆栈、队列、数组tmp=La-next;La-next=Lb-next;Lb-next=tmp;LaLb线性表、堆栈、队列、数组线性表、堆栈、队列、数组v线性表线性表练习练习1：分别实现数组、单链表、循环链表、双向链分别实现数组、单链表、循环链表、双向链表的插入和删除操作。表的插入和删除操作。练习练习2：实现单链表的原地逆转。实现单链表的原地逆转。练习练习3：分别用一元多项式的两种表示实现多项式加分别用一元多项式的两种表示实现多项式加法。法。32-51-2 3000 -1103200P19v自测题自测题给定给定2个带有表头结点的单链表的头指针个带有表头结点的单链表的头指针L1和和L2，结点结构为结点结构为 。假设这。假设这2个链表的结点个链表的结点已经按已经按Data域递增有序，请设计算法把它们合并成域递增有序，请设计算法把它们合并成一个按一个按Data域递增有序的链表。注意：算法不能使域递增有序的链表。注意：算法不能使用额外的结点空间。用额外的结点空间。线性表、堆栈、队列、数组线性表、堆栈、队列、数组DataNext 算法思路为顺序比较算法思路为顺序比较L1和和L2当前所指的两结点的当前所指的两结点的Data域，将小的那个结点从原链表摘除，贴到合并链表域，将小的那个结点从原链表摘除，贴到合并链表的尾部。如此进行到至少其中一个链表为空。若此时另的尾部。如此进行到至少其中一个链表为空。若此时另一个链表不为空，则将另一个链表整个贴到合并链表的一个链表不为空，则将另一个链表整个贴到合并链表的尾部。注意原始尾部。注意原始2个链表有个链表有2个头结点，合并后只保留一个头结点，合并后只保留一个，需要释放另一个的空间。个，需要释放另一个的空间。List MergeSortedLists(List L1,List L2)List L=L1;List Tail=L2;L1=L1-Next;L2=L2-Next;free(Tail);Tail=L;/释放第二个链表的表头，并将新链表的表尾指针释放第二个链表的表头，并将新链表的表尾指针Tail初始化初始化while(L1&L2)if(L1-Data L2-Data)Tail-Next=L2;L2=L2-Next;/第二个链表的第一结点值小，将其插入新链表尾第二个链表的第一结点值小，将其插入新链表尾 else Tail-Next=L1;L1=L1-Next;/第一个链表的第一结点值小，将其插入新链表尾第一个链表的第一结点值小，将其插入新链表尾 Tail=Tail-Next;if(L1)Tail-Next=L1;/将剩余的第一个链表接到新链表表尾将剩余的第一个链表接到新链表表尾else if(L2)Tail-Next=L2;/将剩余的第二个链表接到新链表表尾将剩余的第二个链表接到新链表表尾return L;v自测题自测题给定给定2个带有表头结点的单链表的头指针个带有表头结点的单链表的头指针L1和和L2，结点结构为结点结构为 。假设这。假设这2个链表的结点个链表的结点已经按已经按Data域递增有序，请设计算法把它们合并成域递增有序，请设计算法把它们合并成一个按一个按Data域域递减递减有序的链表。注意：算法不能使有序的链表。注意：算法不能使用额外的结点空间。用额外的结点空间。线性表、堆栈、队列、数组线性表、堆栈、队列、数组DataNext 解题的基本思路不变，只要将原来的表尾插入改为表解题的基本思路不变，只要将原来的表尾插入改为表头插入即可。当然，当其中一个链表为空而另一个链表头插入即可。当然，当其中一个链表为空而另一个链表不为空时，不能直接将剩余链表贴到表尾，而必须将剩不为空时，不能直接将剩余链表贴到表尾，而必须将剩余结点一个一个插入表头。余结点一个一个插入表头。v自测题自测题若若L1和和L2是有序是有序数组数组，其结点已经按，其结点已经按Data域递增域递增有序，请设计算法把它们合并成一个按有序，请设计算法把它们合并成一个按Data域递增域递增有序的数组。注意：要求将有序的数组。注意：要求将L2并入并入L1，并且要求移，并且要求移动元素的次数尽可能少。动元素的次数尽可能少。线性表、堆栈、队列、数组线性表、堆栈、队列、数组 必须事先算好合并后必须事先算好合并后L1的长度，然后从的长度，然后从L1的最终尾的最终尾部向前插入元素。插入过程与前面算法类似，但是是部向前插入元素。插入过程与前面算法类似，但是是从从尾部开始尾部开始比较比较L1和和L2相应元素大小，将较大的元素先插相应元素大小，将较大的元素先插入到后面的位置。入到后面的位置。void MergeSortedArrays(ElementType L1,int N1,ElementType L2,int N2)int p1,p2,cur;p1=N1-1;/p1指向指向L1当前处理的元素位置当前处理的元素位置p2=N2-1;/p2指向指向L2当前处理的元素位置当前处理的元素位置cur=N1+N2-1;/cur指向下一个要插入的元素在指向下一个要插入的元素在L1中的最终位置中的最终位置while(p1=0)&(p2=0)if(L1p1 L2p2)L1cur=L1p1;p1-;else L1cur=L2p2;p2-;cur-;while(p2=0)/将将p2的剩余元素插入到的剩余元素插入到L1中中L1p2=L2p2;p2-;v堆栈堆栈概念：后进先出，限定仅在表尾进行插入删除概念：后进先出，限定仅在表尾进行插入删除的线性表。的线性表。表示与实现：表示与实现：顺序栈：数组，顺序栈：数组，top+，top-链栈：链表，链栈：链表，top即为头指针即为头指针应用：括号匹配检验、表达式求值、应用：括号匹配检验、表达式求值、n阶阶Hanoi塔问题（典型递归）、迷宫问题塔问题（典型递归）、迷宫问题线性表、堆栈、队列、数组线性表、堆栈、队列、数组v自测题自测题判定一个栈判定一个栈ST(最多元素为最多元素为m0)为空的条件是：为空的条件是：A.ST-top!=0B.ST-top=0C.ST-top!=m0D.ST-top=m0线性表、堆栈、队列、数组线性表、堆栈、队列、数组v自测题自测题有六个元素以有六个元素以6，5，4，3，2，1 的顺序进栈，的顺序进栈，问下列哪一个不是合法的出栈序列？问下列哪一个不是合法的出栈序列？A.5 4 3 6 1 2 B.4 5 3 1 2 6 C.3 4 6 5 2 1 D.2 3 4 1 5 6线性表、堆栈、队列、数组线性表、堆栈、队列、数组v自测题自测题若一个栈的输入序列为若一个栈的输入序列为1，2，3，n，输出，输出序列的第一个元素是序列的第一个元素是i，则第，则第j个输出元素是：个输出元素是：A.i j 1 B.i j C.j i 1 D.不确定的不确定的线性表、堆栈、队列、数组线性表、堆栈、队列、数组v队列队列概念：先进先出，限定仅在队尾进行插入、仅概念：先进先出，限定仅在队尾进行插入、仅在队头进行删除的线性表。在队头进行删除的线性表。表示与实现：表示与实现：顺序队列：循环数组，顺序队列：循环数组，(rear+1)%N,(front+1)%N链栈：链表，链栈：链表，front为头指针，为头指针，rear为尾指针为尾指针应用：离散事件模拟应用：离散事件模拟线性表、堆栈、队列、数组线性表、堆栈、队列、数组v自测题自测题循环队列用数组循环队列用数组A0,N1存放其元素值，已知存放其元素值，已知其头尾指针分别是其头尾指针分别是front和和rear，则当前队列中的，则当前队列中的元素个数是：元素个数是：A.(rear-front+N)%NB.rear-front+1C.rear-front-1D.rear-front线性表、堆栈、队列、数组线性表、堆栈、队列、数组01.N-1frontrearv自测题自测题栈和队列的共同特点是：栈和队列的共同特点是：A.都是先进后出都是先进后出 B.都是先进先出都是先进先出 C.只允许在同一端点处插入和删除只允许在同一端点处插入和删除 D.没有共同点没有共同点 线性表、堆栈、队列、数组线性表、堆栈、队列、数组v数组数组 特殊矩阵的压缩存储特殊矩阵的压缩存储对称矩阵：对称矩阵：线性表、堆栈、队列、数组线性表、堆栈、队列、数组an,1a11a21a22a31an,nSAk0123*上（下）三角矩阵同理存储，或许多存储一个常数（若另一上（下）三角矩阵同理存储，或许多存储一个常数（若另一半矩阵元素是非零常数）。半矩阵元素是非零常数）。线性表、堆栈、队列、数组线性表、堆栈、队列、数组v数组数组 特殊矩阵的压缩存储特殊矩阵的压缩存储m对角矩阵：对角矩阵：或者或者 稀疏矩阵：稀疏矩阵：nrow=3,ncol=5,ntotal=6(1,3,4),(2,1,7),(2,3,1),(2,5,-3),(3,2,-2),(3,5,5),线性表、堆栈、队列、数组线性表、堆栈、队列、数组v数组数组 特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵：稀疏矩阵：三元组顺序表：以行序为主序，顺序排列为三元三元组顺序表：以行序为主序，顺序排列为三元组的组的1维数组，并存行数、列数、非维数组，并存行数、列数、非0元个数。元个数。typedef struct inti,j;ElemTypev;Triple;typedef union Triple dataMAXSIZE+1;intnrow,ncol,ntotal;Sparse_Matrix;ijv13421723125-3553-223线性表、堆栈、队列、数组线性表、堆栈、队列、数组v数组数组 特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵：稀疏矩阵：三元组顺序表：三元组顺序表：快速转置快速转置ijv12723-2314321535-325ijv13421723125-3553-223对每列扫描整个数组：对每列扫描整个数组：O(ncol ntotal)如何一步到位，放入正确位置？如何一步到位，放入正确位置？numcol 第col列中非0元个数；cpotcol 第col列中第1个非0元在转置矩阵中的位置；cpot1=1;cpotcol=cpotcol-1+numcol-1;1 2 3 4 5col1 1 2 0 2num1 2 3 5 5cpot42O(ncol+ntotal)线性表、堆栈、队列、数组线性表、堆栈、队列、数组v数组数组 特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵：稀疏矩阵：行逻辑链接的顺序表：行逻辑链接的顺序表：矩阵相乘矩阵相乘typedef struct Triple dataMAXSIZE+1;intrposMAXRC+1;intnrow,ncol,ntotal;Sparse_Matrix;各行第1个非0元在数组中的位置设设 M=A B，则有，则有关键：关键：对每个对每个A.datap，找所有，找所有B.dataq，满足，满足(A.datap.j=B.dataq.i)，将将(A.datap.v B.dataq.v)累加到相应的临时行向量，最后压缩到累加到相应的临时行向量，最后压缩到M中。中。O(Arow Bcol+Atotal Btotal/Brow)线性表、堆栈、队列、数组线性表、堆栈、队列、数组v数组数组 特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵：稀疏矩阵：十字链表：十字链表：矩阵相加矩阵相加41 372 112 3-32 5-23 253 5123M.rhead12345M.chead计算计算 A+B 的复杂度为的复杂度为 O(Atotal+Btotal)v自测题自测题设稀疏矩阵设稀疏矩阵A有有t个非零元素，用二维数组存储时个非零元素，用二维数组存储时占用占用m*n个单元。问稀疏矩阵的三元组表示法在个单元。问稀疏矩阵的三元组表示法在什么情况下比二维数组存储节省空间？什么情况下比二维数组存储节省空间？A.t m*nB.t m*n/3 C.t m*n/3 1D.t m*n 1线性表、堆栈、队列、数组线性表、堆栈、队列、数组树与图树与图v树与二叉树的概念树与二叉树的概念树的概念：树的概念：度度(degree)；层；层(level)注意：根为第注意：根为第1层；深度层；深度(depth)结点的最大层次。结点的最大层次。二叉树的概念：左右有序二叉树的概念：左右有序性质性质1：第：第i层最多有层最多有2i-1个结点。个结点。性质性质2：深度为：深度为k的二叉树最多有的二叉树最多有2k-1个结点。个结点。性质性质3：若：若n0为叶子数，为叶子数，n2为度为为度为2的结点数，则的结点数，则有有 n0=n2+1。性质性质4：具有：具有n个结点的个结点的完全二叉树完全二叉树的深度为的深度为 log2n+1。v树与二叉树的概念树与二叉树的概念二叉树的概念：二叉树的概念：性质性质5：对有：对有n个结点且顺序编号的完全二叉树，个结点且顺序编号的完全二叉树，其任一结点其任一结点 i 有有树与图树与图v二叉树的存储结构二叉树的存储结构顺序存储结构：数组顺序存储结构：数组 仅适用于完全二叉树仅适用于完全二叉树链式存储结构：链式存储结构：在含有在含有n个结点的二叉链表中有个结点的二叉链表中有 个空链域。个空链域。v二叉树的遍历二叉树的遍历先序、先序、中序、中序、后序、后序、层次层次树与图树与图LchildDataRchild Parent1234 5 6 7n+1v自测题自测题一棵完全二叉树共有一棵完全二叉树共有2435个结点，则其个结点，则其中度为中度为0的结点数为？的结点数为？A.1218B.1217 C.不确定不确定D.812树与图树与图前前11层共有层共有211-1=2047个结点个结点第第12层共有层共有2435-2047=388个结点个结点388+210 388/2 =1218v自测题自测题在一棵高度为在一棵高度为h(假定树根结点的层号为假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于的完全二叉树中，所含结点个数不小于 A.2h 1B.2h+1C.2h 1 D.2h树与图树与图v自测题自测题结点中序遍历为结点中序遍历为xyz的不同二叉树，它有的不同二叉树，它有几种不同状态？几种不同状态？A.3 B.4 C.5 D.6 树与图树与图yxzzxyzyxxzyxyzv自测题自测题前序遍历和中序遍历结果相同的二叉树为前序遍历和中序遍历结果相同的二叉树为 A.一般二叉树一般二叉树 B.只有根结点的二叉树只有根结点的二叉树 C.所有结点只有左子树的二叉树所有结点只有左子树的二叉树 D.所有结点只有右子树的二叉树所有结点只有右子树的二叉树 树与图树与图v自测题自测题前序遍历和后序遍历结果相同的二叉树为前序遍历和后序遍历结果相同的二叉树为 A.一般二叉树一般二叉树 B.只有根结点的二叉树只有根结点的二叉树 C.所有结点只有左子树的二叉树所有结点只有左子树的二叉树 D.所有结点只有右子树的二叉树所有结点只有右子树的二叉树 树与图树与图v自测题自测题已知中序遍历和前序遍历结果，给出算法已知中序遍历和前序遍历结果，给出算法求后序遍历结果。求后序遍历结果。树与图树与图（1）从前序遍历结果推断该树的树根。）从前序遍历结果推断该树的树根。（2）找出左子树和右子树的中序和前序遍历结果。）找出左子树和右子树的中序和前序遍历结果。（3）重复上述过程，找出左、右子树的根结点，并）重复上述过程，找出左、右子树的根结点，并逐步往下扩展，直到生成一颗完整的二叉树。逐步往下扩展，直到生成一颗完整的二叉树。中序中序前序前序左左左左右右右右OutPostOrder(PreOrder,InOrder)/已知前序序列已知前序序列PreOrder、中序序列、中序序列InOrder，求后序序列，求后序序列 1）应用前述方法，从序列）应用前述方法，从序列PreOrder和和InOrder中推断出：中推断出：树的根树的根r;左子树的前序遍历序列左子树的前序遍历序列PreOrderLeft和中序遍历序列和中序遍历序列InOrderLeft;右子树的前序遍历序列右子树的前序遍历序列PreOrderRight和中序遍历序列和中序遍历序列InOrderRight;2）递归）递归OutPostOrder(PreOrderLeft,InOrderLeft);3）递归）递归OutPostOrder(PreOrderRight,InOrderRight);4）输出）输出 r;v自测题自测题下面是某二叉树三种遍历的部分结果，请画出相下面是某二叉树三种遍历的部分结果，请画出相应的二叉树。应的二叉树。前序前序:_B_F_ICEH_G 中序中序:D_KFIA_EJC_ 后序后序:_K_FBHJ_G_A 树与图树与图A AB BC CD DF FK KI IE EH HJ JGGABD KDIHJGE Cv自测题自测题在任意一颗二叉树中，任何两个叶结点在在任意一颗二叉树中，任何两个叶结点在先序、中序、后序中的相对次序怎样？先序、中序、后序中的相对次序怎样？A.不变不变 B.不一样不一样 C.不能确定不能确定 D.以上都不是以上都不是 树与图树与图v线索二叉树线索二叉树概念：概念：树与图树与图LchildDataRchildLtagRtag0:Lchild指向左孩子指向左孩子1:Lchild指向前驱指向前驱0:Rchild指向右孩子指向右孩子1:Rchild指向后继指向后继+A DBC中序遍历：中序遍历：A+B C D000+01A10 00 01D11B11C1头结点头结点中中序序线线索索二二叉叉树树树与图树与图v线索二叉树线索二叉树构造：构造：中序：增加中序：增加pre指针，指向刚访问过的结点指针，指向刚访问过的结点后序：须增加后序：须增加Parent指针域指针域优点：优点：遍历不需要堆栈。若经常需要遍历二叉树或查遍历不需要堆栈。若经常需要遍历二叉树或查找结点在遍历序列中的前驱和后继，则应采用线索链找结点在遍历序列中的前驱和后继，则应采用线索链表作为存储结构。表作为存储结构。v二叉排序树二叉排序树定义：左定义：左 根根 二叉树二叉树B=(R,LB,RB)二叉树二叉树B=(R,LB,RB)-森林森林F=T1 T2.Tm 树与图树与图if(!F)B=NULL;else R=root(T1);LB=T11 T12.T1m1;RB=T2.Tm;if(!B)F=NULL;else root(T1)=R;T11 T12.T1m1 =LB;T2.Tm =RB;v树和森林树和森林树和森林的遍历树和森林的遍历树的遍历：树的遍历：先根（次序）遍历先根（次序）遍历=二叉树的先序遍历二叉树的先序遍历后根（次序）遍历后根（次序）遍历=二叉树的二叉树的中序中序遍历遍历森林的遍历：森林的遍历：先序遍历先序遍历=二叉树的先序遍历二叉树的先序遍历中序遍历中序遍历=二叉树的中序遍历二叉树的中序遍历树与图树与图v自测题自测题设森林设森林F对应的二叉树为对应的二叉树为B，它有，它有m个结个结点。点。B的根为的根为p，p的右子树结点个数为的右子树结点个数为n，森林，森林F中第一棵树的结点个数是中第一棵树的结点个数是？A.m-nB.m-n-1C.n+1 D.无法确定无法确定 树与图树与图mnv自测题自测题树最适合用来表示树最适合用来表示A.有序数据元素有序数据元素 B.无序数据元素无序数据元素 C.元素之间无联系的数据元素之间无联系的数据 D.元素之间有分支层次关系元素之间有分支层次关系 树与图树与图v树的应用树的应用等价类问题：等价类问题：给定集合给定集合S的的n个元素，以及个元素，以及m个形如个形如(x,y)的等价偶对，求的等价偶对，求S的等价类划分。的等价类划分。树与图树与图 初始化初始化n个只包含个只包含1个元素的子集个元素的子集;while(读入读入x,y)if(!(Find(x)=Find(y)Union 两集合两集合;10687419235142010094810710610524032Sv树的应用树的应用等价类问题等价类问题Union by size 根记录根记录(-结点数结点数)，小树并入大树，小树并入大树Find+压缩路径压缩路径 将将Find路径上的结点都变成根的路径上的结点都变成根的孩子孩子树与图树与图10687419235142-310-794810710610524832SUnion(2,10)-1010Find(9)106874192351010*等价划分等价划分n元集合的复杂度为元集合的复杂度为 O(n(n),(n)4对通常见到的对通常见到的n成立。成立。v哈夫曼哈夫曼(Huffman)树和哈夫曼编码树和哈夫曼编码哈夫曼树：带权路径长度最小的二叉树哈夫曼树：带权路径长度最小的二叉树树与图树与图75247524路径长度路径长度=7 2 +5 2 +2 2 +4 2 =367524路径长度路径长度=7 3 +5 3 +2 1 +4 2 =46路径长度路径长度=7 1 +5 2 +2 3 +4 3 =35 v哈夫曼哈夫曼(Huffman)树和哈夫曼编码树和哈夫曼编码哈夫曼树的构造哈夫曼树的构造1.将将n个带权结点作为个带权结点作为n棵只有根的二叉树的森林；棵只有根的二叉树的森林；2.选选2棵根权值最小的树，作为左右子树构造新树，棵根权值最小的树，作为左右子树构造新树，新根的权值新根的权值=左右子树根权值的和；左右子树根权值的和；3.将上述将上述2棵树删除，将新树加入森林；棵树删除，将新树加入森林；4.重复第重复第2、3步，直到只剩步，直到只剩1棵树，即是哈夫曼树。棵树，即是哈夫曼树。树与图树与图v哈夫曼哈夫曼(Huffman)树和哈夫曼编码树和哈夫曼编码哈夫曼编码哈夫曼编码例：例：aaaxuaxz 一般被存为一般被存为8个字符，占个字符，占64字节。但因只字节。但因只有有4个不同字符，故可编码为个不同字符，故可编码为 a=00,u=01,x=10,z =11，只需要占，只需要占16个字节。若采用哈夫曼编码个字节。若采用哈夫曼编码 a=0,u=110,x=10,z =111，则得到，则得到 00010110010111，只，只需要占需要占14个字节。个字节。注意：任一字符的编码都不是另一字符编码的前缀注意：任一字符的编码都不是另一字符编码的前缀 前缀编码前缀编码。树与图树与图v哈夫曼哈夫曼(Huffman)树和哈夫曼编码树和哈夫曼编码哈夫曼编码的构造：哈夫曼编码的构造：将字符出现频率作为权重，构将字符出现频率作为权重，构造哈夫曼树，并按左造哈夫曼树，并按左0右右1编码。编码。例：例：aaaxuaxz树与图树与图a:4x:2u:1z:1a:4x:2u:1z:1248000111a=0 x=10u=110z =111思考：给定编码，思考：给定编码，如何判断是否哈如何判断是否哈夫曼编码？夫曼编码？v自测题自测题哈夫曼树有哈夫曼树有n个叶结点，则该树共有多个叶结点，则该树共有多少个结点？少个结点？A.2nB.2n-1C.2n+1 D.不能确定不能确定 树与图树与图N0=nN1=02*N2=N 1 N=N0+N1+N2N=?v图的概念（图的概念（p.156-160）v图的存储及基本操作图的存储及基本操作邻接矩阵法邻接矩阵法无向图顶点的度无向图顶点的度有向图顶点的度有向图顶点的度网网树与图树与图v图的存储及基本操作图的存储及基本操作邻接表法邻接表法树与图树与图V1V2V3V4V1V2V3V40123iV1dataV2V3V421300123iV1dataV2V3V4312003020123iV1dataV2V3V43020逆邻接表逆邻接表*边稀疏时节省空间，但判断任意两顶点是否有弧相连时，则不如邻边稀疏时节省空间，但判断任意两顶点是否有弧相连时，则不如邻接矩阵方便。接矩阵方便。v自测题自测题具有具有n个顶点的无向图最多有几条边？个顶点的无向图最多有几条边？A.n(n-1)/2B.n(n+1)/2C.n2/2 D.2n 树与图树与图v自测题自测题在一个图中，所有点的度数之和等于所在一个图中，所有点的度数之和等于所有边的数目的有边的数目的多少倍？多少倍？A.1/2B.1C.2D.4树与图树与图v自测题自测题一个无向图采用邻接矩阵存储，该邻接一个无向图采用邻接矩阵存储，该邻接矩阵一定是一个矩阵一定是一个_A.对称矩阵对称矩阵B.对角矩阵对角矩阵C.三角矩阵三角矩阵D.稀疏矩阵稀疏矩阵树与图树与图树与图树与图v自测题自测题从邻接矩阵从邻接矩阵 可以看出，该图可以看出，该图共有（共有（）个顶点；如果是有向图该图）个顶点；如果是有向图该图共有（共有（）条弧；如果是无向图，则共条弧；如果是无向图，则共有（有（）条边）条边 A.9,5,5B.3,4,2C.6,3,3D.1,2,2v图的遍历图的遍历深度优先深度优先(DFS)：类似于树的先序遍历。递：类似于树的先序遍历。递归，需要堆栈。邻接矩阵归，需要堆栈。邻接矩阵 O(n2)；邻接表；邻接表 O(n+e)。广度优先广度优先(BFS)：类似于树的层次遍历。需：类似于树的层次遍历。需要队列。时间复杂度与要队列。时间复杂度与DFS相同。相同。树与图树与图v自测题自测题已已知知无无向向图图为为G=(V,E)，其其中中，顶顶点点集集合合为为V=v1,v2,v3,v4,v5,v6,v7，边边的的集集合合为为E=(v1,v2),(v1,v3),(v2,v4),(v2,v6),(v4,v5),(v4,v7),(v5,v6)，请请分分别别给给出出根根据据该该邻邻接接表表从从顶顶点点v1出出发发进进行行深深度度优优先先搜搜索索与与广广度度优优先先搜搜索索后后的的顶顶点序列。当有多种选择时，按序号先后访问。点序列。当有多种选择时，按序号先后访问。深度优先搜索序列：深度优先搜索序列：v1,v2,v4,v5,v6,v7,v3广度优先搜索序列：广度优先搜索序列：v1,v2,v3,v4,v6,v5,v7树与图树与图1234567v图的基本应用及其复杂度分析图的基本应用及其复杂度分析最小（代价）生成树最小（代价）生成树普里姆普里姆(Prim)算法：一棵树的生长算法：一棵树的生长树与图树与图v1v2v6v7v3v4v52421310758461*复杂度为复杂度为 O(n2)，与边数无关，适合与边数无关，适合于求边稠密的网的于求边稠密的网的最小生成树。最小生成树。v图的基本应用及其复杂度分析图的基本应用及其复杂度分析最小（代价）生成树最小（代价）生成树克鲁斯卡尔克鲁斯卡尔(Kruskal)算法：森林的生长算法：森林的生长树与图树与图v1v2v6v7v3v4v52421310758461*适合于求边稀适合于求边稀疏的网的最小生疏的网的最小生成树，成树，复杂度为复杂度为 O(e log e)。v自测题自测题已知一个带权连通图已知一个带权连通图G=(V,E)，其中顶点，其中顶点集合为集合为V=1,2,3,4,5，其邻接矩阵如，其邻接矩阵如图，求出其所有可能的最小生成树。图，求出其所有可能的最小生成树。树与图树与图 7 6 9 7 8 4 46 8 6 9 4 6 2 4 2 v图的基本应用及其复杂度分析图的基本应用及其复杂度分析最短路径最短路径单源（带权）最短路：迪杰斯特拉单源（带权）最短路：迪杰斯特拉(Dijkstra)算法算法 贪心，按长度递增生成，当新顶点使路径更短时，更新路径，贪心，按长度递增生成，当新顶点使路径更短时，更新路径，O(n2)。多源（带权）最短路：弗洛伊德多源（带权）最短路：弗洛伊德(Floyd)算法算法 O(n3)，但比重复，但比重复Dijkstra算法简单。算法简单。树与图树与图v图的基本应用及其复杂度分析图的基本应用及其复杂度分析拓扑排序：拓扑排序：有向无环图有向无环图(DAG)的应用之一的应用之一1.选一个无前驱顶点输出；选一个无前驱顶点输出；2.删除该顶点以及所有以之为尾的弧；删除该顶点以及所有以之为尾的弧；3.重复第重复第1、2步，直到全部顶点输出，或不存在无前驱顶点步，直到全部顶点输出，或不存在无前驱顶点(说说明有环明有环)。注意：注意：拓扑排序可方便检查有向图中是否存在环；拓扑排序可方便检查有向图中是否存在环；确定无环时，也可用确定无环时，也可用DFS进行拓扑排序，退出进行拓扑排序，退出DFS的顺序即的顺序即为逆向的拓扑序；为逆向的拓扑序；DFS可方便检查无向图中是否存在环可方便检查无向图中是否存在环(若遇到回边即有环若遇到回边即有环)。树与图树与图v图的基本应用及其复杂度分析图的基本应用及其复杂度分析关键路径：关键路径：AOE网网 带权带权DAG树与图树与图012345678startfinisha0=6a1=4a2=5a3=1a4=1a5=2a6=9a7=7a8=4a9=2a10=406457716141818161471056602323v自测题自测题判断有向图是否存在回路，除了可以利判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用用拓扑排序方法外，还可以利用_A.求关键路径的方法求关键路径的方法 B.求最短路径