数据结构期末重点复习题课件

作业：1、简述逻辑结构和存储结构的联系？2、数据结构和数据类型有什么区别？3、分析以下算法的时间复杂度voidfunc(intn)inti=0,s=0;while(sL.listsize)p24while(i=L.elemi)i+;for(j=L.length-1;j=i;j-)L.elemj+1=L.elemj;L.elemi=x;L.length+;8/3/20243顺序表算法设计练习：顺序表算法设计练习：n试写一个算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表。（a1,a2,an）逆置为（an,an-1,a1）。8/3/20244参考算法：参考算法：Voidreverse(Sqlist&L)inti=0,j=L.length-1;while(ij)L.elemiL.elemj;i+;j-;8/3/20245顺序表算法设计练习：顺序表算法设计练习：n试设计一个高效的算法，删除线性表L中所有值为x的元素。8/3/20246参考算法：参考算法：Voiddeletelist(Sqlist&L,ElemTypex)intcount=0;for(i=0;inext,r;If(q!=Null)r=q-next;Elsereturn0;While(r!=Null&r-data!=x)p=q;q=r;r=r-next;if(r!=Null)p-next=q-next;free(q);elsereturn0;return1;8/3/20249链表算法设计练习：链表算法设计练习：n设计一个算法，在带头结点的单链表head中删除一个data域值最小的结点，假设该结点唯一。8/3/202410参考算法：参考算法：VoidDelMinNode(Linklisthead)Linklistp=head-next,pre=head;Linklistminp,minpre;Elemtypemin=p-data;minp=p;minpre=pre;While(p!=NULL)If(p-datadata)min=p-data;minp=p;minpre=pre;pre=p;p=p-next;minpre-next=minp-next;Free(minp);8/3/2024111、假设表达式中允许包含3种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈判断表达式中的括号是否正确配对。Int match(char exp,int n)char stMaxsize;int top=-1;int i=0,tag=1;while(idata=x;if(rear=NULL)s-next=s;rear=s;elses-next=rear-next;rear-next=s;rear=s8/3/202413作业：作业：1、设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部分，将所有的偶数放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。2、设计一个算法，计算一个三元组表表示的稀疏矩阵的对角线元素之和。8/3/202414例：例：设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A5B6C7D8提示：提示：因为每个结点都有一条枝指向它，分支数为1*4+2*2+3*1+4*1所有结点数为分支数+1，所以1*4+2*2+3*1+4*1=4+2+1+1+xx=8例：例：若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A9B11C15D不确定提示：提示：n0=n2+115例例3：已知某二叉树先序序列：已知某二叉树先序序列 ABHFDECKG 和中序序列和中序序列 HBDFAEKCG,画出该二叉树。画出该二叉树。HBDFEKCGAEKCGABHDFEKCGABHFDEABHFDCKGAKCGEBHFDA16例1：统计二叉树中叶子结点的个数StatusCountLeaf(BiTreeT,int&count)if(T)if(T-lchild=NULL)&(T-rchild=NULL)count+;returnOK;CountLeaf(T-lchild,count);/统计左子树中叶子结点个数CountLeaf(T-rchild,count);/统计右子树中叶子结点个数elsereturnERROR;17例2：求二叉树的深度intDepth(BiTreeT)if(!T)depthval=0;elsedepthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+max(depthLeft,depthRight);returndepthval;18例3：按先序序列建立二叉树的二叉链表已知先序序列：ABC00DE0G00F000（其中0表示空格字符,空指针）建立相应的二叉链表ABCDEFG19例：例：对于前序遍历与中序遍历结果相同的二叉树（）;对于前序遍历和后序遍历结果相同的二叉树为（）。A一般二叉树 B只有根结点的二叉树 C根结点无左孩子的二叉树 D根结点无右孩子的二叉树 E所有结点只有左子数的二叉树 F所有结点只有右子树的二叉树例：例：某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A空或只有一个结点B任一结点无左子树C高度等于其结点数D任一结点无右子树FB20例：一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：()A不确定 B.0 C.1 D.2 例：一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：()。A.0 B.1 C.2 D.不确定 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域只有最后一个叶结点没有后继21例：线索二叉树是一种（）结构。A逻辑B逻辑和存储C物理D线性例：n个结点的线索二叉树上含有的线索数为（）A2nBn1Cn1DnN个结点共有2n个指针域，二叉链表用了n-1个，剩下n+1个22练习：写出下图所示树的先序和后序遍历序列并将之转换成一棵二叉树ABCDEFHGI先根遍历：先根遍历：ABDEGHICF后根遍历：后根遍历：DGHIEBFCAABGDCFHEI236.4.2 森林和二叉树的转换规则设森林F=T1,T2,Tm，二叉树B=（root，LB，RB）(1)森林转化成二叉树的规则若F为空(m=0)，B为空;若F不空(m0)，B的根root(B)是F中第一棵树T1的根root(T1)；左子树LB从T1根结点的子树森林(T11,T12,T1m)转换来；右子树RB是从森林F=T2,T3,Tm转换而来。(2)二叉树转换为森林的规则若B为空，F为空；若B非空，则F中第一棵树T1的根为二叉树的根root(B)；T1根的子树森林F1由B的左子树LB转换而来；F中除T1外其余树组成的森林F=T2,T3,Tn由B的右子树RB转换而来。24森林转换成二叉树步骤1：转换将各棵树分别转换成二叉树步骤2：加线将每棵树的根结点用线相连步骤3：旋转以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树ABCDEFGHIJ森林森林F FABCDEFGHIJF F中每棵树对应的二叉树中每棵树对应的二叉树25森林转换成二叉树步骤1：转换将各棵树分别转换成二叉树步骤2：加线将每棵树的根结点用线相连步骤3：旋转以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树ABCDEFGHIJABCDEFGHIJ森林森林F F26森林转换成二叉树步骤1：转换将各棵树分别转换成二叉树步骤2：加线将每棵树的根结点用线相连步骤3：旋转以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树ABCDEFGHIJABCDEFGHIJ森林森林F FF F转换的二叉树转换的二叉树B BABCDEFGHIJ27二叉树转换成森林步骤1：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原将孤立的二叉树还原成树二叉树二叉树B BABCDEFGHIJ28二叉树转换成森林步骤1：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原将孤立的二叉树还原成树二叉树二叉树B BABCDEFGHIJABCDEFGHIJ29二叉树转换成森林步骤1：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原将孤立的二叉树还原成树ABCDEFGHIJ二叉树二叉树B BABCDEFGHIJABCDEFGHIJ30二叉树转换成森林步骤1：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原将孤立的二叉树还原成树B B转换成的森林转换成的森林F F二叉树二叉树B BABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ31练习：写出下图所示森林的先序和中序遍历序列并将之转换成一棵二叉树EABCDFIJHGK先序遍历：先序遍历：中序遍历：中序遍历：ABCDEFIKJGHBEFDCIAJGHK32例：设F是一个森林，B是由F变换得的二叉树。若中有n个非终端结点，则B中右指针域为空的结点有（）个。An-1BnCn+1Dn+2每一个非终端结点的孩子中都会贡献出一个空的右指针例：设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有个结点，右子树中有个结点。n1-1n2+n333构造最优二叉树的说明1 在选取两棵根结点权值为最小和次小的二叉树时，如果出现权值相同的情况，可以在相同权值的二叉树中任选一棵。2 当两棵根结点权值为最小和次小的二叉树组成新的二叉树的左右子树时，谁是左子树谁是右子树没有特殊规定。3在最优二叉树中没有度为1的结点，根据二叉树的性质3可知有n个叶子结点的二叉树有n-1个非终端结点共有2*n-1个结点。a7b5c2d461118a7b5d4c26111834如何得到最短的二进制前缀码（赫夫曼编码）？如何得到最短的二进制前缀码（赫夫曼编码）？为了设计电文总长最短的二进制前缀编码，以n种字符出现的频率作权，设计一棵赫夫曼树，从根节点至即所有叶子节点，按左分支为0，右分支为1的原则即可得到最短二进制前缀编码即赫夫曼编码。例：已知某系统在通信联络中只可能出现例：已知某系统在通信联络中只可能出现8种字符，其概率为种字符，其概率为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,设计赫夫曼编码。设计赫夫曼编码。解：设权解：设权w=(5，29，7，8，14，23，3，11)350231411529378000000111111110058428291519编码：编码：3（0111）5（0110）7（1110）8（1111）11（010）14（110）23（00）29（10）36练习：练习：用于通信的电文由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试设计不等长Huffman编码,并给出该电文的总码数。0000000100101000101000000010010100010101110110111011电文总码数电文总码数=4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=25737练习练习（1）设无向图的顶点个数为n，则该图最多有（）条边。（2）一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。（3）在一个无向图中，所有顶点的度数之和等于所有边数的_倍。（4）要连通具有n个顶点的有向图，至少需要（）条边。（5）若无向图G=（V，E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（）。8/3/202438无向图邻接表表示V1V2V4V5V3顶点的度：该顶点所在单链表中表结点个数V1V2V3V4V501234130420212143与顶点V1相邻接的顶点在数组中的下标8/3/202439V1V2V4V5V3254311邻接表表示V1V2V3V4V501234123402452111413304231521权值无向网8/3/202440V1V2 V3 V4 邻接表表示12V1V2V3V4012330以顶点V1为始点的弧的终点顶点在数组中的下标顶点的出度该顶点所在单链表中表结点个数顶点的入度查询整个邻接表中的表结点，与该顶点的序号（数组下标）一致的表结点个数有向图8/3/202441图的邻接表表示问题：具有n个顶点e条边的无向图的邻接表中有多少个表头结点？有多个表结点（边结点）？有向图呢？8/3/202442练习练习:请画出下图的邻接矩阵和邻接表8/3/2024437.3.1 深度优先搜索-举例1234V1V3V4V2data firstarc2783adjvexnextarc5V564151282V6V7V8678736354V1V2V4V5V3V7V6V8深度遍历：深度遍历：V1V3 V7 V6 V2 V5 V8 V4给定存储结构，图的遍历序列唯一给定存储结构，图的遍历序列唯一8/3/2024447.3.2 广度优先搜索-举例广度遍历：广度遍历：V1 V3 V2 V7 V6 V5 V4 V81234V1V3V4V2data firstarc2783adjvexnextarc5V564151282V6V7V8678736354V1V2V4V5V3V7V6V8给定存储结构，图的遍历序列唯一给定存储结构，图的遍历序列唯一8/3/202445下列有关图遍历的说法中不正确的是（）A连通图的深度优先搜索是一个递归过程B图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C.图的遍历要求每一顶点仅被访问一次D对图进行一次深度优先遍历可以访问图中所有顶点8/3/202446给定有向图如下：给出其邻接表存储结构基于邻接表，给出DFS序列和BFS序列8/3/202447练习：已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。【答】用克鲁斯卡尔算法得到的最小生成树为：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)208/3/202448练习：设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。【答】E=(1，3)，(1，2)，(3，5)，(5，6)，(6，4)2024/8/3497.5.1 拓扑排序-实现步骤C1C3C2C7C5C6C4编号课程名称C1数学C2程序设计C3离散数学C4汇编程序设计C5数据结构C6结构程序设计C7编译原理C1C3C2C7C5C6C4拓扑有序序列：拓扑有序序列：C1=C3=C2=C4=C6=C5=C7逻辑结构上：拓扑序列不唯一8/3/2024507.5.2 关键路径AOE-网(ActiveOnEdge)：在带权的有向无环图中，顶点表示事件，弧表示工程的一个活动，弧上权值表示活动持续的时间。用来估算工程完成时间。源点：入度为0的顶点。汇点：出度为0的顶点。路径长度：AOE网中路径上各活动持续时间之和。关键路径：路径长度最长的路径。V1V3V4V6V5V8V2V7V9a1=6a7=9a5=1a2=4a4=1a10=2a3=5a6=2a9=4a11=4a8=7说明：（1）完成工程的最短时间是从开始点到完成点的最长路径的长度。（2）关键路径的改变会影响整个工期。8/3/202451设活动ai在有向无环图G的有向边上：n事件vj的最早发生时间ve(j):从源点v0到vj的最长路径长度。ve(0)=0;ve(j)=从源点到顶点j的最长的路径长度。ve(k)=Maxve(j)+dut()n事件vj的最迟开始时间vl(j)：保证汇点vn-1在ve(n-1)时刻完成的前提下，事件vj最迟允许开始的时间。vl(n-1)=ve(n-1)从源点到汇点的最长路径长度;vl(k)=从汇点到顶点k的最短的路径长度。vl(j)=Minvl(k)-dut()kj dut()ai7.5.2 关键路径定义和术语8/3/2024527.5.2 关键路径定义和术语设活动ai在有向边上,有：n活动ai的最早开始时间e(i)：从源点v0到vj的最长路径长度。e(i)=ve(j);n活动ai的最迟开始时间l(i)：是不推迟工程完成的前提下，该活动允许的最迟开始时间。l(i)=vl(k)-dut()n活动ai时间余量：l(i)-e(i)n关键活动：满足l(i)=e(i)的活动。关键路径上的活动都是关键活动。kj dut()ai8/3/2024537.5.2 关键路径求关键活动关键活动关键活动e(i)=l(i)e(i)=ve(j)l(i)=vl(k)-dut()ve(j)、vl(j)求顶点（事件）vk的最早开始时间：从ve(0)=0向汇点方向递推求顶点（事件）vj的最迟开始时间：从vl(n-1)=ve(n-1)向源点递推V1V3V4V6V5V8V2V7V9a1=6a7=9a5=1a2=4a4=1a10=2a3=5a6=2a9=4a11=4a8=7ve(k)=Maxve(j)+dut()vl(j)=Minvl(k)-dut()在拓扑有序的前提下进行在拓扑有序的前提下进行在逆拓扑有序前提下进行在逆拓扑有序前提下进行8/3/202454由汇点至源点由汇点至源点由源点至汇点由源点至汇点1814161078660vl(i)181416775460ve(i)V9V8V7V6V5V4V3V2V1iV1V3V4V6V5V8V2V7V9a1=6a7=9a5=1a2=4a4=1a10=2a3=5a6=2a9=4a11=4a8=7关键路径是关键路径是V1,V2,V5,V7,V9和和V1,V2,V5,V8,V9ve(k)=Maxve(j)+dut()vl(j)=Minvl(k)-dut()e(i)=ve(j);l(i)=vl(k)dut()14161077866320l(i)000000差1416777546000e(i)a11a10a9a8a7a6a5a4a3a2a1注意：关键路径可有多条。缩短工期必须缩短关键活动所需的时间8/3/202455如何求关键路径？(算法思想)（1）输入e条弧，建立AOE网的存储结构；（2）从源点v0出发，令ve0=0，按拓扑有序求其余各顶点的最早发生时间vei(1in-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止，否则执行步骤（3）；（3）从汇点vn出发，令vln-1=ven-1，按逆拓扑有序求余各顶点的最迟发生时间vli(n-2i2)（4）根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s).若某条弧满足条件e(s)=l(s),则为关键活动。8/3/202456下列关于AOE网的叙述中，不正确的是（）A.关键活动不按期完成就会影响整个工程的完成时间B.某些关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.任何一个关键活动提前完成，那么整个工程将会提前完成8/3/2024579.2.1 二叉排序树二叉排序树(二叉查找树）(BinarySortTree,BST)：空树或具有下列性质的二叉树:根的左子树若非空，则左子树上的所有结点的关键字值均小于根结点的值。根的右子树若非空，则右子树上的所有结点的关键字值均大于根结点的值。它的左右子树同样是二叉排序树。中序遍历二叉排序树可得到一个关键字的有序序列8/3/2024589.2.1 二叉排序树的插入例：序列45、24、53、12、90构成一棵二叉排序树建BST树过程：一个无序序列可以构造二叉排序树前提：查找失败插入的结点是一个叶子结点，且是查找失败时查找路径上访问的最后一个结点的左孩子或右孩子。插入算法：二叉排序树的存储结构使用链表首先执行查找算法，找出被插入结点的父亲结点。若二叉树为空。则首先单独生成根结点。判断被插结点是其父亲结点的左、右孩子。将结点插入45539024128/3/2024599.2.1 二叉排序树-删除设二叉排序树上被删除结点是p，PL是p的左子树，PR是p的右子树，p的双亲结点是f，不失一般性，设p是f的左孩子。有三种情况：1)被删除的结点p是叶子结点；2)被删除的结点p只有左子树或者只有右子树；3)被删除的结点既有左子树，也有右子树。对二叉排序树，删去一个结点相当于删去有序序列中的一个记录。8/3/2024609.2.1 二叉排序树-删除1）被删除的结点p是叶子结点：修改双亲结点的指针，令f-lchild=NULL4553902412pf45539024f例：删除叶子结点128/3/2024619.2.1 二叉排序树-删除2）被删除的结点p只有左子树或者只有右子树：令PL或PR直接为其双亲结点f的左子树即可，f-lchild=p-lchild|p-rchild。4553902412pf45539012f例：删除结点248/3/2024629.2.1 二叉排序树-删除3）被删除的结点既有左子树，也有右子树。在删去p结点前，中序遍历该二叉树得到的序列为CLCQLQSLSPPRF，即S是中序遍历序列中被删结点p的直接前驱结点。方法一：令P的左子树为F的左子树，P的右子树为S的右子树FPPLPRFPCQSPRCLQLSLFCQSPRCLQLSL8/3/2024639.2.1 二叉排序树-删除3）被删除的结点既有左子树，也有右子树。在删去p结点前，中序遍历该二叉树得到的序列为CLCQLQSLSPPRF，即S是中序遍历序列中被删结点p的直接前驱结点。方法二：令p的直接前驱S替代p，再从二叉排序树中删去S。FPPLPRFPCQSPRCLQLSLFSCQPRCLQLSL8/3/2024649.2.1 二叉排序树-删除举例删除4545531237324100619078451237324531006190788/3/2024659.2.1 二叉排序树-删除举例删除454512337245310061907837455312373241006190788/3/202466练习：假定一棵二叉排序树采用二叉链表存储结构，其根结点指针为T,设计一个算法输出该二叉排序树中最大的键值和最小的键值。8/3/202467statusmaxmindata()if(!T)returnerror;p=q=T;while(p-lchild!=NULL)p=p-lchild;printf(“Theminimumdatais:%d”,p-data);while(q-rchild!=NULL)q=q-rchild;printf(“Theminimumdatais:%d”,q-data);8/3/2024689.3 哈希表查找表的特点：记录的关键字和在结构中的位置之间无确定关系查找过程是给定值依次和关键字集合中各个关键字的比较查找效率取决于和给定值进行比较的关键字个数。希望不经比较，直接可以找到所查记录哈希函数：在记录的关键字和其在表中位置之间建立一种函数关系，即以f(key)作为关键字为key的记录在表中的位置。8/3/2024699.3 哈希表定义和术语冲突：不同关键字得到同一哈希地址，key1key2，f(key1)=f(key2)同义词：在一个哈希函数中具有相同函数值的不同关键字。哈希表：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这种表被称为哈希表。哈希造表或散列：映象过程。哈希地址或散列地址：所得的存储位置。构造哈希表要注意的问题：考虑选择一个“好”的哈希函数;选择一种处理冲突的方法。8/3/2024709.3.3 处理冲突的方法1开放定址法：Hi=(H(key)+di)MODmi=1,2,k(km-1)，H(key)为哈希函数；m：哈希表长，di是增量序列，有三种取法di=1,2,m-1，称为线性探测再散列di=12,-12,22,-22,k2(km/2)称为二次探测再散列di=伪随机数列，称为随机探测再散列8/3/202471处理冲突方法举例例：一组关键字19,14,23,01,68,20,84,27,55,11,10,79；按H(key)=keymod13和线性探测再散列方法处理冲突构造表长为16的哈希表。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15311931134121比较次数200820023010冲突次数ASLss=1/12（1*6+2+3*3+4+9）=2.5 14 0168 27 55 19 20 847923 11 108/3/2024729.3.3 处理冲突的方法例：用哈希函数H(key)=keyMOD13和链地址法处理冲突求一组关键字19,14,23,01,68,20,84,27,55,11,10,79的哈希表：0123456789101112 01142779 5568 1984 1023 11 20 ASLss=1/12(1*6+2*4+3+4)=1.758/3/202473练习：已知关键字序列为：（75,33,52,41,12,88,66,27），哈希表长为10，哈希函数为：H(k)k%9，解决冲突用线性探测法，请：（1）构造出哈希表；（2）计算等概率下查找成功的平均查找长度。8/3/202474 Typedef struct LNode ElemTypedata;/数据域structLnode*next;/指针域 LNode,*LinkList;二、结点和单链表的二、结点和单链表的 C C 语言描述语言描述LinkList L；/L 为单链表的头指针为单链表的头指针8/3/202475 Typedef struct LNode ElemTypedata;/数据域structLnode*next;/指针域 LNode,*LinkList;二、结点和单链表的二、结点和单链表的 C C 语言描述语言描述LinkList L；/L 为单链表的头指针为单链表的头指针8/3/202476三、单链表操作的实现三、单链表操作的实现GetElem(L,i,&e)/取第i个数据元素ListInsert(&L,i,e)/插入数据元素ListDelete(&L,i,e)/删除数据元素ClearList(&L)/重置线性表为空表CreateList(&L,n)/生成含n 个数据元素的链表8/3/202477L线性表的操作GetElem(L,i,&e)在单链表中的实现:211830754256pppj1 2 38/3/202478 因此，查找第因此，查找第 i 个数据元素的基本操作为：个数据元素的基本操作为：移动指移动指针，比较针，比较 j 和和 i。单链表是一种顺序存取的结构，为找第单链表是一种顺序存取的结构，为找第 i 个数据元个数据元素，必须先找到第素，必须先找到第 i-1 个数据元素。个数据元素。令指针令指针 p 始终指向线性表中第始终指向线性表中第 j 个数据元素。个数据元素。8/3/202479 StatusGetElem_L(LinkListL,inti,ElemType&e)/L是带头结点的链表的头指针，以是带头结点的链表的头指针，以 e 返回第返回第 i 个元素个元素/GetElem_L算法算法时间复杂度时间复杂度为为:O(ListLength(L)p=L-next;j=1;/p p指向第一个结点，指向第一个结点，j j为计数器为计数器while(p&jnext;+j;/顺指针向后查找，直到顺指针向后查找，直到 p p 指向第指向第 i i 个元素个元素 /或或 p p 为空为空if(!p|ji)returnERROR;/第第 i 个元素不存在个元素不存在e=p-data;/取得第取得第 i 个元素个元素returnOK;8/3/202480ai-1线性表的操作 ListInsert(&L,i,e)在单链表中的实现：有序对有序对 改变为改变为 和和 eaiai-18/3/202481 因此，在单链表中第因此，在单链表中第 i 个结点之前进行插入的基个结点之前进行插入的基本操作为本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。可见，在链表中插入结点只需要修改指针。但同可见，在链表中插入结点只需要修改指针。但同时，若要在第时，若要在第 i 个结点之前插入元素，修改的是第个结点之前插入元素，修改的是第 i-1 个结点的指针。个结点的指针。8/3/202482 StatusListInsert_L(LinkListL,inti,ElemTypee)/L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法/在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e /LinstInsert_L算法的算法的时间复杂度时间复杂度为:O(ListLength(L)p=L;j=0;while(p&jnext;+j;/寻找第寻找第 i-1 个结点个结点if(!p|ji-1)returnERROR;/i 大于表长或者小于大于表长或者小于1 8/3/202483s=(LinkList)malloc(sizeof(LNode);/生成新结点s-data=e;s-next=p-next;p-next=s;/插入returnOK;eai-1aiai-1sp8/3/202484线性表的操作ListDelete(&L,i,&e)在链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-18/3/202485 在单链表中删除第删除第 i i 个结点个结点的基本操作基本操作为:找到找到线性表中第线性表中第i-1i-1个结点，修改其指向后继的指针。个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p-next;p-next=q-next;e=q-data;free(q);pq8/3/202486 StatusListDelete_L(LinkListL,inti,ElemType&e)/删除以L为头指针(带头结点)的单链表中第i个结点/ListDelete_L算法的算法的时间复杂度时间复杂度为:O(ListLength(L)p=L;j=0;while(p-next&jnext;+j;/寻找第i个结点，并令p指向其前趋if(!(p-next)|ji-1)return ERROR;/删除位置不合理q=p-next;p-next=q-next;/删除并释放结点e=q-data;free(q);returnOK;8/3/202487操作ClearList(&L)在链表中的实现:voidClearList(&L)/将单链表重新置为一个空表while(L-next)p=L-next;L-next=p-next;/ClearListfree(p);算法时间复杂度：O(ListLength(L)8/3/202488逆位序输入逆位序输入 n 个数据元素的值，建立带头结点的单链表。个数据元素的值，建立带头结点的单链表。操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素an，建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素an-1，建立结点并插入；建立结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a1为止。为止。8/3/202489voidCreateList_L(LinkList&L,intn)/逆序输入 n 个数据元素，建立带头结点的单链表/CreateList_L算法的算法的时间复杂度时间复杂度为:O(Listlength(L)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(&p-data);/输入元素值p-next=L-next;L-next=p;/插入8/3/202490时间复杂度为O（La.length+Lb.length）。两个有序线性表合并为一个有序线性表的算法：两个有序线性表合并为一个有序线性表的算法：voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)pa=La-next;pb=Lb-next;Lc=pc=La;while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);8/3/2024915.3.2 稀疏矩阵n稀稀疏疏矩矩阵阵：设设m行行n列列的的矩矩阵阵含含t个个非非零零元元素素，则则=t/(m*n)称称为为稀疏因子稀疏因子，通常认为，通常认为 0.05 的矩阵为稀疏矩阵。的矩阵为稀疏矩阵。n抽象数据类型稀疏矩阵的定义：书抽象数据类型稀疏矩阵的定义：书96页页n稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵中非零元素位置无规律稀疏矩阵中非零元素位置无规律n记住非零元素的行记住非零元素的行i，列，列j，值，值aij稀疏矩阵中存在多个非零元素稀疏矩阵中存在多个非零元素l三元组的三元组的C语言描述语言描述 typedef struct int i,j;ElemType e;Triplel三元组顺序表的三元组顺序表的C语言描述语言描述#define MAXSIZE 125000 typedef struct Triple dataMAXSIZE+1;int mu,nu,tu;TSMatrix8/3/202492三元组表表示的稀疏矩阵的转置n设M和T分别是MM和TT的三元组表，如何由M得到T？将矩阵行列值(即m和n)相互交换将每个三元组中的i和j对换重排三元组的次序8/3/202493Status TransposeSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1;for(col=1;col=M.nu;+col)for(p=1;p=M.tu;+p)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+q;return OK;/TransposeSMatrix三元组表表示的稀疏矩阵转置算法1评价：评价：O(nu*tu)，优点优点:节省空间，节省空间，tumu*nu适用适用对对MM的的每一列扫每一列扫描一遍所有非零元描一遍所有非零元8/3/202494三元组表表示的稀疏矩阵转置方法2n思思想想：按按M.data的的三三元元组组次次序序转转置置，再再将将三三元元组组置置入入T中中适当的位置。适当的位置。n问问题题：转转置置前前需需知知MM的的每每列列中中非非零零元元素素个个数数及及第第一一个个非零元素在非零元素在T.data中的中的位置位置。n解决方案：设解决方案：设num和和cpot两个向量，两个向量，nnumcol：矩阵：矩阵MM的第的第col列中非零元素的个数，列中非零元素的个数，ncpotcol:矩矩阵阵MM第第col列列第第一一个个非非零零元元在在T.data中中的的位位置置cpot1=1;cpotcol=cpotcol-1+numcol-1(2=col=M.nu)8/3/202495Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol;return OK;/TransposeSMatrix时间复杂度为时间复杂度为O(nu+tu),若若tumu*nu则为则为O(mu*nu)，与经典算法相同，多用了两个辅助向量。，与经典算法相同，多用了两个辅助向量。三元组表表示的稀疏矩阵转置方法2统计统计M中每一列中每一列的非零元个数的非零元个数初始化初始化M中每一列第一个中每一列第一个非零元应该在非零元应该在T中的位置中的位置M中中colcol列下一个非零列下一个非零元应该在元应该在T中的位置中的位置稀疏矩阵的压缩存储行逻辑链接顺序表需求：随机存取任一行的非需求：随机存取任一行的非0元元方法：记住矩阵每一行第一个非方法：记住矩阵每一行第一个非0元在三元组表中的位置元在三元组表中的位置设数组设数组rpos1.n:矩阵中的每行第一个非零元素的起始位置。矩阵中的每行第一个非零元素的起始位置。rpos1=1;rposrow=rposrow-1+第第row-1行的非零元素个数行的非零元素个数行逻辑链接顺序表行逻辑链接顺序表:在稀疏矩阵存储结构中固定指示行信息的辅在稀疏矩阵存储结构中固定指示行信息的辅助数组助数组rpos行逻辑链接表存储结构的语言描述：行逻辑链接表存储结构的语言描述：typedef struct Triple dataMAXSIZE+1;int rposMAXRC+1;/各行第一个非零元素位置表各行第一个非零元素位置表 int mu,nu,tu;RLSMatrix 8/3/202497 0 2 1 0-2 4 0 0N=i j v12 221 131 -23 2 4行逻辑链接表举例行逻辑链接表举例row1234rposrow1235N的三元组表N的的rpos向量向量8/3/202498基于行逻辑链接表表示的稀疏矩阵相乘基于行逻辑链接表表示的稀疏矩阵相乘（1）对于每个元素M.datap(p=1,2,M.tu)，找到N中满足条件的N.dataq，在查找过程中，用到rpos数组，rpos数组的含义是稀疏矩阵中每行第一个非零元素在三元组当中位置的数组，rposrow：第row行第一个非零元素在N.data中的序号，rposrow+1-1：第row行最后一个非零元素在N.data中的序号，最后一个非零元素在N.data中的位置序号是N.tu。求乘积M.datap.vN.dataq.v，然后累加。为操作方便，应对每个元素设一个乘积和的变量数组ctemp，初值为0。（2）两个稀疏矩阵相乘的乘积不一定是稀疏矩阵，反之，Mik和Njk均不为零，但其乘积和也可能为0，因此Q中的该元素是否为0需计算得知。先求得Qij，再压缩到Q.data中去。8/3/202499Status MultSMarix(RLSMatrix&M,RLSMatrix&N,RLSMatrix&Q)if(M.nu!=N.mu)return ERROR;Q.mu=M.mu;Q.NU=N.nu;Q.tu=0;/Q初始化初始化 if(M.tu*N.tu!=0)/Q是非零矩阵是非零矩阵 for(arow=1;arow=M.mu;+arow)/处理处理M的每一行的每一行 ctemp=0;/当前行各元素累加器清零当前行各元素累加器清零 Q.rposarow=Q.tu+1;/设当前行第一个非零元在三元组表中的位序设当前行第一个非零元在三元组表中的位序 if(arrowM.mu)tp=M.rposarrow+1;else tp=M.tu+1;for(p=M.rposarow;ptp;+p)/对当前行中每一个非零元对当前行中每一个非零元 brow=M.datap.j;/找到对应元在找到对应元在N中的行号中的行号 if(brow N.mu)t=N.rposbrow+1;else t=N.tu+1/t指示该行中最后一个非零元的位置指示该行中最后一个非零元的位置 for(q=N.rposbrow;q t;+q)ccol=N.dataq.j;/乘积元素在乘积元素在Q中列号中列号 ctempccol+=M.datap.e*N.dataq.e;/for q /求得求得Q中第中第crow(=arow)行的非零元行的非零元 for(ccol=1;ccol MAXSIZE)return ERROR;);Q.dataQ.tu=arow,ccol,ctempccol;/if /for arow /if return OK;/MultSMatrix求矩阵乘积Q=MN，采用行逻辑链接存储表示。8/3/20241006.2.3二叉树的存储结构n链式存储结构二叉链表lchild data rchild二叉树的二叉链表C语言描述 typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;101二叉树的二叉链表存储示例：ABCDEFGABCDEFG问题：含有n个结点的二叉链表中有多少个空链域？102先序遍历二叉树的递归算法6.3 遍历二叉树和线索二叉树StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/二叉链表存储结构，visit是对数据元素操作的应用函数/先序遍历二叉树T的递归算法，对每个数据元素调用visitif(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverser(T-rchild,Visit)returnOK;returnERROR;elsereturnOK;PreOrderTraverse103例1：统计二叉树中叶子结点的个数StatusCountLeaf(BiTreeT,int&count)if(T)if(T-lchild=NULL)&(T-rchild=NULL)count+;returnOK;CountLeaf(T-lchild,count);/统计左子树中叶子结点个数CountLeaf(T-rchild,count);/统计右子树中叶子结点个数elsereturnERROR;104例2：求二叉树的深度intDepth(BiTreeT)if(!T)depthval=0;elsedepthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+max(depthLeft,depthRight);returndepthval;105