数据结构期末重点复习题.ppt

1、1,作业： 1、简述逻辑结构和存储结构的联系？ 2、数据结构和数据类型有什么区别？ 3、分析以下算法的时间复杂度 void func(int n) int i=0,s=0; while (sn) i+; s=s+i; ,2,2020/8/7,顺序表算法设计练习：,已知一个顺序表L，其中的元素递增有序排列，设计一个算法插入一个元素x后保持该顺序表仍递增有序排列。,3,2020/8/7,参考算法：,Void insert (Sqlist ,4,2020/8/7,顺序表算法设计练习：,试写一个算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表。（a1,a2,an）逆置为（an,an-1,a1）

2、。,5,2020/8/7,参考算法：,Void reverse (Sqlist ,6,2020/8/7,顺序表算法设计练习：,试设计一个高效的算法，删除线性表L中所有值为x的元素。,7,2020/8/7,参考算法：,Void deletelist (Sqlist ,8,2020/8/7,链表算法设计练习：,设计一个算法删除带头结点的单链表L中值为x的结点的直接前驱结点。,9,2020/8/7,参考算法：,Int delx(Linklist ,10,2020/8/7,链表算法设计练习：,设计一个算法，在带头结点的单链表head中删除一个data域值最小的结点，假设该结点唯一。,11,2020/8

3、/7,参考算法：,Void DelMinNode (Linklist head) Linklist p=head-next, pre=head; Linklist minp, minpre; Elemtype min=p-data; minp=p;minpre=pre; While (p!=NULL) I f (p-datadata) min=p-data; minp=p; minpre=pre; pre=p; p=p-next; minpre-next=minp-next; Free(minp); ,12,2020/8/7,1、假设表达式中允许包含3种括号：圆括号、方括号和大括号。设计一个算

4、法采用顺序栈判断表达式中的括号是否正确配对。 Int match (char exp, int n) char stMaxsize; int top=-1; int i=0,tag=1; while (in ,13,2020/8/7,2、假设用一个循环单链表表示队列，并且只设一个指针rear指向队尾结点，但不设头指针，设计出相应的队初始化、入队算法。 Void initQu(Qnode * rear=s ,14,2020/8/7,作业： 1、设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部分，将所有的偶数放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。 2、

5、设计一个算法，计算一个三元组表表示的稀疏矩阵的对角线元素之和。,15,例：设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ） A5 B6 C7 D8 提示：因为每个结点都有一条枝指向它，分支数为1*4+2*2+3*1+4*1所有结点数为分支数+1，所以1*4+2*2+3*1+4*1=4+2+1+1+x x=8 例：若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A9 B11 C15 D不确定 提示： n0=n2+1,16,例3：已知某二叉树先序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 画出该二叉树。

6、,17,例1：统计二叉树中叶子结点的个数,Status CountLeaf (BiTree T, int ,18,例2：求二叉树的深度,int Depth (BiTree T ) if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + max(depthLeft,depthRight); return depthval; ,19,例3：按先序序列建立二叉树的二叉链表,已知先序序列：A B C 0 0 D E 0 G 0 0 F 0 0 0

7、（其中0表示空格字符, 空指针）建立相应的二叉链表,A,B,C,D,E,F,G,20,例：对于前序遍历与中序遍历结果相同的二叉树（ ）; 对于前序遍历和后序遍历结果相同的二叉树为（ ）。 A一般二叉树 B只有根结点的二叉树 C根结点无左孩子的二叉树 D根结点无右孩子的二叉树 E所有结点只有左子数的二叉树 F所有结点只有右子树的二叉树 例：某二叉树的前序序列和后序序列正好相反，则该二叉树 一定是（）的二叉树。 A空或只有一个结点 B任一结点无左子树 C高度等于其结点数 D任一结点无右子树,F,B,21,例： 一棵左子树为空的二叉树在先序线索化后，其中空的链 域的个数是：( ) A不确定 B. 0

8、 C. 1 D. 2 例： 一棵左右子树均不空的二叉树在先序线索化后，其中空 的链域的个数是：( )。 A. 0 B. 1 C. 2 D. 不确定,左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域,只有最后一个叶结点没有后继,22,例： 线索二叉树是一种（ ）结构。 A 逻辑 B 逻辑和存储 C 物理 D线性 例：n个结点的线索二叉树上含有的线索数为（ ） A2n Bn1 Cn1 Dn,N个结点共有2n个指针域，二叉链表用了n-1个，剩下n+1个,23,练习：写出下图所示树的先序和后序遍历序列并将之转换成一棵二叉树,先根遍历：ABDEGH

9、ICF,后根遍历：DGHIEBFCA,24,6.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 中

10、除 T1 外其余树组成的森林F= T2, T3, , Tn 由B 的右子树 RB 转换而来。,25,森林转换成二叉树,步骤1：转换将各棵树分别转换成二叉树 步骤2：加线将每棵树的根结点用线相连 步骤3：旋转以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树,森林F,26,森林转换成二叉树,步骤1：转换将各棵树分别转换成二叉树 步骤2：加线将每棵树的根结点用线相连 步骤3：旋转以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树,E,F,G,H,I,J,森林F,27,森林转换成二叉树,步骤1：转换将各棵树分别转换成二叉树 步骤2：加线将每棵树的根结点用线相连

11、 步骤3：旋转以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树,E,F,G,H,I,J,森林F,F转换的二叉树B,28,二叉树转换成森林,步骤1：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树 步骤2：还原将孤立的二叉树还原成树,二叉树B,29,二叉树转换成森林,步骤1：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树 步骤2：还原将孤立的二叉树还原成树,二叉树B,30,二叉树转换成森林,步骤1：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成

12、多棵二叉树 步骤2：还原将孤立的二叉树还原成树,A,B,C,D,E,F,G,H,I,J,二叉树B,31,二叉树转换成森林,步骤1：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树 步骤2：还原将孤立的二叉树还原成树,B转换成的森林F,二叉树B,A,B,C,D,E,F,G,H,I,J,32,练习：写出下图所示森林的先序和中序遍历序列并将之转换成一棵二叉树,先序遍历：,中序遍历：,ABCDEFIKJGH,BEFDCIAJGHK,33,例：设F是一个森林，B是由F变换得的二叉树。若 中有n个非终端结点，则B中右指针域为空的结点有 （ ）个。 A n-1

13、Bn C n+1 D n+2,每一个非终端结点的孩子中都会贡献出一个空的右指针,例：设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有 个结点，右子树中有 个结点。,n1-1,n2+n3,34,构造最优二叉树的说明,1 在选取两棵根结点权值为最小和次小的二叉树时，如果出现权值相同的情况，可以在相同权值的二叉树中任选一棵。 2 当两棵根结点权值为最小和次小的二叉树组成新的二叉树的左右子树时，谁是左子树谁是右子树没有特殊规定。 3 在最优二叉树中没有度为1的结点，根据二叉树的性质3可知有n个叶子结点的二叉树 有n

14、-1个非终端结点共有2*n-1个结点。,35,如何得到最短的二进制前缀码（赫夫曼编码）？ 为了设计电文总长最短的二进制前缀编码，以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),36,编码：3（0111） 5（0110） 7（1110） 8（1111） 11（010） 14（110） 23（00）

15、29（10）,37,练习： 用于通信的电文由 8 个字母 c1, c2, c3, c4, c5, c6, c7, c8 组成, 各字母在电文中出现的频率分别为 5, 25, 3, 6, 10, 11, 36, 4。试 设计不等长 Huffman 编码, 并给出该电文的总码数。,0000 0001 001 0100 0101,011 10 11,电文总码数=4*5+2*25+4*3+4*6+ 3*10+3*11+2*36+4*4= 257,38,2020/8/7,练习 （1）设无向图的顶点个数为n，则该图最多有（ ）条边。 （2）一个有n个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量

16、。 （3）在一个无向图中，所有顶点的度数之和等于所有边数的_倍。 （4）要连通具有n个顶点的有向图，至少需要（ ）条边。 （5）若无向图G=（V，E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（ ）。,39,2020/8/7,无向图,顶点的度：该顶点所在单链表中表结点个数,与顶点V1相邻接的顶点在数组中的下标,40,2020/8/7,权值,无向网,41,2020/8/7,以顶点V1为始点的弧的终点顶点在数组中的下标,顶点的出度 该顶点所在单链表中表结点个数 顶点的入度 查询整个邻接表中的表结点，与该顶点的序号（数组 下标）一致的表结点个数,有向图,42,2020/8/7

17、,图的邻接表表示,问题：具有n个顶点e条边的无向图的邻接表中有多少个表头结点？有多个表结点（边结点）？,有向图呢？,43,2020/8/7,练习: 请画出下图的邻接矩阵和邻接表,44,2020/8/7,7.3.1 深度优先搜索-举例,深度遍历：V1,V3 ,V7 ,V6 ,V2 ,V5 ,V8 ,V4,给定存储结构，图的遍历序列唯一,45,2020/8/7,7.3.2 广度优先搜索-举例,广度遍历：V1 V3 V2 V7 V6 V5 V4 V8,给定存储结构，图的遍历序列唯一,46,2020/8/7,下列有关图遍历的说法中不正确的是（） A连通图的深度优先搜索是一个递归过程 B图的广度优先搜索

18、中邻接点的寻找具有“先进先出”的特征 C. 图的遍历要求每一顶点仅被访问一次 D对图进行一次深度优先遍历可以访问图中所有顶点,47,2020/8/7,给定有向图如下：,给出其邻接表存储结构 基于邻接表，给出DFS序列和BFS序列,48,2020/8/7,练习：,已知一个图的顶点集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; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。,【答】用克

19、鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20,49,2020/8/7,练习：,设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。,【答】E=(1，3)，(1，2)，(3，5)，(5，6)，(6，4),50,2020/8/7,7.5.1 拓扑排序-实现步骤,C1,C3,C2,C7,C5,C6,C4,拓扑有序序列：,逻辑结构上：拓扑序列不唯一,51,2020/8/7,7.5.2 关键路径,AOE-网(Active On Edge)：在带权的有向无环图中，顶点表示事件，弧表示工程的一个活动，弧上权值

20、表示活动持续的时间。用来估算工程完成时间。 源点：入度为0的顶点。汇点：出度为0的顶点。 路径长度：AOE网中路径上各活动持续时间之和。 关键路径：路径长度最长的路径。,说明： （1）完成工程的最短时间是从开始点到完成点的最长路径的长度。 （2）关键路径的改变会影响整个工期。,52,2020/8/7,设活动ai在有向无环图G的有向边上： 事件vj的最早发生时间ve(j):从源点v0到vj的最长路径长度。 ve(0)=0; ve(j)=从源点到顶点j的最长的路径长度。 ve(k)=Maxve(j)+dut() 事件vj的最迟开始时间vl(j)：保证汇点vn-1在ve(n-1)时刻完成的前提下，事

21、件vj最迟允许开始的时间。 vl(n-1) = ve(n-1)从源点到汇点的最长路径长度; vl(k)=从汇点到顶点k的最短的路径长度。 vl(j)=Minvl(k)-dut(),7.5.2 关键路径定义和术语,53,2020/8/7,7.5.2 关键路径定义和术语,设活动ai在有向边上,有： 活动ai的最早开始时间e(i)：从源点v0到vj的最长路径长度。 e(i)= ve(j); 活动ai的最迟开始时间l(i)：是不推迟工程完成的前提下，该活动允许的最迟开始时间。 l(i)=vl(k)-dut() 活动ai时间余量：l(i)-e(i) 关键活动：满足l(i)=e(i)的活动。关键路径上的活

22、动都是关键活动。,54,2020/8/7,7.5.2 关键路径求关键活动,求顶点（事件）vk的最早开始时间：从ve(0)=0向汇点方向递推 求顶点（事件）vj的最迟开始时间：从vl(n-1)=ve(n-1)向源点递推,ve(k)=Maxve(j)+dut(),vl(j)=Minvl(k)-dut(),在拓扑有序的前提下进行,在逆拓扑有序前提下进行,55,2020/8/7,18,14,16,10,7,8,6,6,0,vl(i),18,14,16,7,7,5,4,6,0,ve(i),V9,V8,V7,V6,V5,V4,V3,V2,V1,i,关键路径是V1 ,V2, V5, V7, V9和V1 ,V

23、2 ,V5 ,V8 ,V9,ve(k) = Maxve(j)+dut() vl(j)=Minvl(k)-dut(),e(i) = ve(j); l(i) = vl(k) dut(),14,16,10,7,7,8,6,6,3,2,0,l(i),0,0,0,0,0,0,差,14,16,7,7,7,5,4,6,0,0,0,e(i),a11,a10,a9,a8,a7,a6,a5,a4,a3,a2,a1,注意：关键路径可有多条。 缩短工期必须缩短关键活动所需的时间,56,2020/8/7,如何求关键路径？(算法思想) （1）输入e条弧，建立AOE网的存储结构； （2）从源点v0出发，令ve0=0，按拓扑

24、有序求其余各顶点的最早发生时间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),则为关键活动。,57,2020/8/7,下列关于AOE网的叙述中，不正确的是（ ） A.关键活动不按期完成就会影响整个工程的完 成时间 B.某些关键活动提前完成，那么整个工程将会 提前完成 C.所有的

25、关键活动提前完成，那么整个工程将 会提前完成 D.任何一个关键活动提前完成，那么整个工程 将会提前完成,58,2020/8/7,9.2.1 二叉排序树,二叉排序树(二叉查找树）(Binary Sort Tree, BST)：空树或具 有下列性质的二叉树: 根的左子树若非空，则左子树上的所有结点的关键字值均小于根结点的值。 根的右子树若非空，则右子树上的所有结点的关键字值均大于根结点的值。 它的左右子树同样是二叉排序树。 中序遍历二叉排序树可得到一个关键字的有序序列,59,2020/8/7,9.2.1 二叉排序树的插入,例：序列45、24、53、12、90构成一棵二叉排序树 建BST树过程： 一

26、个无序序列可以构造二叉排序树 前提：查找失败 插入的结点是一个叶子结点， 且是查找失败时查找路径上访问的 最后一个结点的左孩子或右孩子。 插入算法： 二叉排序树的存储结构使用链表 首先执行查找算法，找出被插入结点的父亲结点。 若二叉树为空。则首先单独生成根结点。 判断被插结点是其父亲结点的左、右孩子。将结点插入,45,53,90,24,12,60,2020/8/7,9.2.1 二叉排序树-删除,设二叉排序树上被删除结点是p ，PL是p的左子树，PR是p的右子树，p的双亲结点是f，不失一般性，设p是f的左孩子。有三种情况： 被删除的结点p是叶子结点； 被删除的结点p只有左子树或者只有右子树； 被

27、删除的结点既有左子树，也有右子树。 对二叉排序树，删去一个结点相当于删去有序序列中的一个记录。,61,2020/8/7,9.2.1 二叉排序树-删除,1） 被删除的结点p是叶子结点：修改双亲结点的指针，令 f-lchild=NULL,例：删除叶子结点12,62,2020/8/7,9.2.1 二叉排序树-删除,2） 被删除的结点p只有左子树或者只有右子树：令PL或PR直接为其双亲结点f的左子树即可，f-lchild=p-lchild|p-rchild。,例：删除结点24,63,2020/8/7,9.2.1 二叉排序树-删除,3）被删除的结点既有左子树，也有右子树。在删去p结点前，中序遍历该二叉树

28、得到的序列为CLCQLQSLSPPRF，即S是中序遍历序列中被删结点p的直接前驱结点。 方法一：令P的左子树为F的左子树，P的右子树为S的右子树,64,2020/8/7,9.2.1 二叉排序树-删除,3）被删除的结点既有左子树，也有右子树。在删去p结点前，中序遍历该二叉树得到的序列为CLCQLQSLSPPRF，即S是中序遍历序列中被删结点p的直接前驱结点。 方法二：令p的直接前驱S替代p，再从二叉排序树中删去S。,65,2020/8/7,9.2.1 二叉排序树-删除举例,删除45,45,12,37,3,24,66,2020/8/7,9.2.1 二叉排序树-删除举例,删除45,45,12,3,2

29、4,53,100,61,90,78,37,67,2020/8/7,练习： 假定一棵二叉排序树采用二叉链表存储结构，其根结点指针为T,设计一个算法输出该二叉排序树中最大的键值和最小的键值。,68,2020/8/7,status maxmindata() if (!T ) return error; p=q=T; while (p-lchild!=NULL) p=p-lchild; printf(“The minimum data is:%d”, p-data); while (q-rchild!=NULL) q=q-rchild; printf(“The minimum data is:%d”,

30、 q-data); ,69,2020/8/7,9.3 哈希表,查找表的特点： 记录的关键字和在结构中的位置之间无确定关系 查找过程是给定值依次和关键字集合中各个关键字的比较 查找效率取决于和给定值进行比较的关键字个数。 希望不经比较，直接可以找到所查记录 哈希函数：在记录的关键字和其在表中位置之间建立一种 函数关系，即以f(key)作为关键字为key的记录在表中的位 置。,70,2020/8/7,9.3 哈希表定义和术语,冲突：不同关键字得到同一哈希地址，key1key2， f(key1)=f(key2) 同义词：在一个哈希函数中具有相同函数值的不同关键字。 哈希表：根据设定的哈希函数H(ke

31、y)和所选中的处理冲突的方 法，将一组关键字映象到一个有限的、地址连续的地址集(区 间)上，并以关键字在地址集中的“象”作为相应记录在表中的存 储位置，这种表被称为哈希表。 哈希造表或散列：映象过程。 哈希地址或散列地址：所得的存储位置。 构造哈希表要注意的问题： 考虑选择一个“好”的哈希函数; 选择一种处理冲突的方法。,71,2020/8/7,9.3.3 处理冲突的方法,1 开放定址法：Hi=(H(key)+di) MOD m i=1,2,k (km-1)，H(key)为哈希函数；m：哈希表长，di是增量序列， 有三种取法 di=1,2,m-1，称为线性探测再散列 di=12,-12,22,

32、-22,k2 (km/2)称为二次探测再散列 di=伪随机数列，称为随机探测再散列,72,2020/8/7,处理冲突方法举例,例：一组关键字19,14,23,01,68,20,84,27,55,11,10,79；按 H(key)=key mod 13和线性探测再散列方法处理冲突构造表长 为16的哈希表。,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,3,1,1,9,3,1,1,3,4,1,2,1,比较次数,2,0,0,8,2,0,0,2,3,0,1,0,冲突次数,ASLss=1/12（1*6+2+3*3+4+9）=2.5,14,01,68,27,55,19,20,

33、84,79,23,11,10,73,2020/8/7,9.3.3 处理冲突的方法,例：用哈希函数H(key)=key MOD 13和链地址法处理冲突求一组关键字19,14,23,01,68,20,84,27,55,11,10,79的哈希表：,ASLss=1/12(1*6+2*4+3+4)=1.75,74,2020/8/7,练习：,已知关键字序列为：（75,33,52,41,12,88,66,27），哈希表长为10，哈希函数为：H(k)k%9，解决冲突用线性探测法，请： （1）构造出哈希表； （2）计算等概率下查找成功的平均查找长度。,75,2020/8/7,Typedef struct LNo

34、de ElemType data; / 数据域 struct Lnode *next; / 指针域 LNode, *LinkList;,二、结点和单链表的 C 语言描述,LinkList L； / L 为单链表的头指针,76,2020/8/7,Typedef struct LNode ElemType data; / 数据域 struct Lnode *next; / 指针域 LNode, *LinkList;,二、结点和单链表的 C 语言描述,LinkList L； / L 为单链表的头指针,77,2020/8/7,三、单链表操作的实现,GetElem(L, i, j = 1; / p指向第

35、一个结点，j为计数器,while (p / 顺指针向后查找，直到 p 指向第 i 个元素 / 或 p 为空,if ( !p | ji ) return ERROR; / 第 i 个元素不存在 e = p-data; / 取得第 i 个元素 return OK;,81,2020/8/7,线性表的操作 ListInsert( j = 0; while (p / i 大于表长或者小于1,84,2020/8/7,s = (LinkList) malloc ( sizeof (LNode); / 生成新结点 s-data = e; s-next = p-next; p-next = s; / 插入 re

36、turn OK;,s,p,85,2020/8/7,线性表的操作ListDelete ( p-next = q-next; e = q-data; free(q);,p,q,87,2020/8/7,Status ListDelete_L(LinkList L, int i, ElemType j = 0; while (p-next / 删除位置不合理,q = p-next; p-next = q-next; / 删除并释放结点 e = q-data; free(q); return OK;,88,2020/8/7,操作 ClearList(,算法时间复杂度：,O(ListLength(L),8

37、9,2020/8/7,逆位序输入 n 个数据元素的值，建立带头结点的单链表。,操作步骤：,一、建立一个“空表”；,二、输入数据元素an， 建立结点并插入；,三、输入数据元素an-1， 建立结点并插入；,an,an,an-1,四、依次类推，直至输入a1为止。,90,2020/8/7,void CreateList_L(LinkList L-next = NULL; / 先建立一个带头结点的单链表,for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf( / 插入 ,91,2020/8/7,时间复杂度为O（La.lengt

38、h+Lb.length）。,两个有序线性表合并为一个有序线性表的算法：,void MergeList_L(LinkList ,92,2020/8/7,5.3.2 稀疏矩阵,稀疏矩阵：设m行n列的矩阵含t个非零元素，则=t/(m*n)称为稀疏因子，通常认为 0.05 的矩阵为稀疏矩阵。 抽象数据类型稀疏矩阵的定义：书96页 稀疏矩阵的压缩存储 稀疏矩阵中非零元素位置无规律 记住非零元素的行i，列j，值aij 稀疏矩阵中存在多个非零元素,三元组的C语言描述 typedef struct int i,j; ElemType e; Triple,三元组顺序表的C语言描述 #define MAXSIZE

39、 125000 typedef struct Triple dataMAXSIZE+1; int mu,nu,tu;TSMatrix,93,2020/8/7,三元组表表示的稀疏矩阵的转置,设M和T分别是MM和TT的三元组表，如何由M得到T？ 将矩阵行列值(即m和n)相互交换 将每个三元组中的i和j对换 重排三元组的次序,94,2020/8/7,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,三元组表表示的稀疏矩阵转置算法1,评价：O(nu*tu)， 优点:节省空间， tumu*nu适用,95,2020/8/7,三元组表

40、表示的稀疏矩阵转置方法2,思想：按M.data的三元组次序转置，再将三元组置入T中适当的位置。 问题：转置前需知MM的每列中非零元素个数及第一个非零元素在T.data中的位置。 解决方案：设num和cpot两个向量， numcol：矩阵MM的第col列中非零元素的个数， cpotcol: 矩阵MM第col列第一个非零元在T.data中的位置,cpot1=1;,cpotcol=cpotcol-1+numcol-1 (2=col=M.nu),Status FastTransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix时间复杂度为O(nu+tu),若tumu*nu 则为O(mu*nu)，与经典算法相同，多用了两个辅助向量。,三元组表表示的稀疏矩阵转置方法2,97,2020/8/7,稀疏矩阵的压缩存储行逻辑链接顺序表,需求：随机存取任一行的非0元 方法：记住矩阵每一行第一个非0元在三元组表中的位置 设数组rpos1.n:矩阵中的每行第一个非零元素的起始位置。 rpos1=1; rposrow=rposrow-1+第row-1行的非零元素个数 行逻辑链接顺序表:在稀疏矩阵存储结构中固定指示行信息的辅助数