数据结构期末重点复习题

1作业：1、简述逻辑结构和存储结构的联系？2、数据结构和数据类型有什么区别？3、分析以下算法的时间复杂度

voidfunc(intn){inti=0,s=0;while(s<n){i++;s=s+i;}}22023/10/1顺序表算法设计练习：

已知一个顺序表L，其中的元素递增有序排列，设计一个算法插入一个元素x后保持该顺序表仍递增有序排列。32023/10/1参考算法：Voidinsert(Sqlist&L,ElemTypex){inti=0,j;if(L.length+1>L.listsize)p24while(i<L.length&&x>=L.elem[i])i++;for(j=L.length-1;j>=i;j--)L.elem[j+1]=L.elem[j];L.elem[i]=x;L.length++;}42023/10/1顺序表算法设计练习：试写一个算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表。（a1,a2,…,an）逆置为（an,an-1,…,a1）。52023/10/1参考算法：Voidreverse(Sqlist&L){inti=0,j=L.length-1;while(i<j){L.elem[i]<->L.elem[j];i++;j--;}}62023/10/1顺序表算法设计练习：试设计一个高效的算法，删除线性表L中所有值为x的元素。72023/10/1参考算法：Voiddeletelist(Sqlist&L,ElemTypex){intcount=0;for(i=0;i<=L.length-1;i++)if(L.elem[i]==x)count++;elseL.elem[i-count]=L.elem[i];}82023/10/1链表算法设计练习：设计一个算法删除带头结点的单链表L中值为x的结点的直接前驱结点。92023/10/1参考算法：Intdelx(Linklist&L,ElemTypex){LinkListp=L,q=p->next,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;}102023/10/1链表算法设计练习：设计一个算法，在带头结点的单链表head中删除一个data域值最小的结点，假设该结点唯一。112023/10/1参考算法：VoidDelMinNode(Linklisthead){Linklistp=head->next,pre=head;Linklistminp,minpre;Elemtypemin=p->data;minp=p;minpre=pre;While(p!=NULL){If(p->data<minp->data){min=p->data;minp=p;minpre=pre;}pre=p;p=p->next;}minpre->next=minp->next;Free(minp);}122023/10/11、假设表达式中允许包含3种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈判断表达式中的括号是否正确配对。Intmatch(charexp[],intn){charst[Maxsize];inttop=-1;inti=0,tag=1;while(i<n&&tag==1){if(exp[i]==‘(’||exp[i]==‘[‘||exp[i]==‘{’){top++;st[top]=exp[i];}if(exp[i]==‘)’)if(st[top]==‘(’top--;elsetag=0;if(exp[i]==‘]’)if(st[top]==‘[’top--;elsetag=0;if(exp[i]==‘}’)if(st[top]==‘{’top--;elsetag=0;132023/10/12、假设用一个循环单链表表示队列，并且只设一个指针rear指向队尾结点，但不设头指针，设计出相应的队初始化、入队算法。VoidinitQu(Qnode*&rear){rear=NULL;}VoldEnQu(Qnode*&rear,ElemTypex){Qnode*s;s=(Qnode*)mallaoc(sizeof(Qnode));s->data=x;if(rear==NULL){s->next=s;rear=s;}else{s->next=rear->next;rear->next=s;rear=s}}142023/10/1作业：1、设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部分，将所有的偶数放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。2、设计一个算法，计算一个三元组表表示的稀疏矩阵的对角线元素之和。15例：设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．8提示：因为每个结点都有一条枝指向它，分支数为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的结点个数是（）A．9B．11C．15D．不确定提示：

n0=n2+116例3：已知某二叉树先序序列{ABHFDECKG}和中序序列{HBDFAEKCG},画出该二叉树。HBDFEKCGAEKCGABHDFEKCGABHFDEABHFDCKGAKCGEBHFDA17例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;}18例2：求二叉树的深度intDepth(BiTreeT){if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+max(depthLeft,depthRight);}returndepthval;}19例3：按先序序列建立二叉树的二叉链表已知先序序列：ABC00DE0G00F000（其中0表示空格字符,空指针）建立相应的二叉链表ABCDEFG20例：对于前序遍历与中序遍历结果相同的二叉树（）;对于前序遍历和后序遍历结果相同的二叉树为（）。A．一般二叉树B．只有根结点的二叉树C．根结点无左孩子的二叉树D．根结点无右孩子的二叉树E．所有结点只有左子数的二叉树F．所有结点只有右子树的二叉树例：某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A．空或只有一个结点B．任一结点无左子树C．高度等于其结点数D．任一结点无右子树FB√21例：一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：()A．不确定B.0C.1D.2例：一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：()。A.0B.1C.2D.不确定√左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域√只有最后一个叶结点没有后继22例：线索二叉树是一种（）结构。A．逻辑B．逻辑和存储C．物理D．线性例：n个结点的线索二叉树上含有的线索数为（）A．2nB．n－1C．n＋1D．n√√N个结点共有2n个指针域，二叉链表用了n-1个，剩下n+1个23练习：写出下图所示树的先序和后序遍历序列并将之转换成一棵二叉树ABCDEFHGI先根遍历：ABDEGHICF后根遍历：DGHIEBFCAABGDCFHEI246.4.2森林和二叉树的转换－规则设森林F={T1,T2,……Tm}，二叉树B=（root，LB，RB）(1)森林转化成二叉树的规则

若F为空(m=0)，B为空;

若F不空(m≠0)，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转换而来。25森林转换成二叉树步骤1：转换－将各棵树分别转换成二叉树步骤2：加线－将每棵树的根结点用线相连步骤3：旋转－以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树ABCDEFGHIJ森林FABCDEFGHIJF中每棵树对应的二叉树26森林转换成二叉树步骤1：转换－将各棵树分别转换成二叉树步骤2：加线－将每棵树的根结点用线相连步骤3：旋转－以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树ABCDEFGHIJABCDEFGHIJ森林F27森林转换成二叉树步骤1：转换－将各棵树分别转换成二叉树步骤2：加线－将每棵树的根结点用线相连步骤3：旋转－以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树ABCDEFGHIJABCDEFGHIJ森林FF转换的二叉树BABCDEFGHIJ28二叉树转换成森林步骤1：抹线－将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原－将孤立的二叉树还原成树二叉树BABCDEFGHIJ29二叉树转换成森林步骤1：抹线－将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原－将孤立的二叉树还原成树二叉树BABCDEFGHIJABCDEFGHIJ30二叉树转换成森林步骤1：抹线－将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原－将孤立的二叉树还原成树ABCDEFGHIJ二叉树BABCDEFGHIJABCDEFGHIJ31二叉树转换成森林步骤1：抹线－将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原－将孤立的二叉树还原成树B转换成的森林F二叉树BABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ32练习：写出下图所示森林的先序和中序遍历序列并将之转换成一棵二叉树EABCDFIJHGK先序遍历：中序遍历：ABCDEFIKJGHBEFDCIAJGHK33例：设F是一个森林，B是由F变换得的二叉树。若中有n个非终端结点，则B中右指针域为空的结点有（）个。A．n-1B．nC．n+1D．n+2每一个非终端结点的孩子中都会贡献出一个空的右指针√例：设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有

个结点，右子树中有

个结点。n1-1n2+n334构造最优二叉树的说明1在选取两棵根结点权值为最小和次小的二叉树时，如果出现权值相同的情况，可以在相同权值的二叉树中任选一棵。2当两棵根结点权值为最小和次小的二叉树组成新的二叉树的左右子树时，谁是左子树谁是右子树没有特殊规定。3在最优二叉树中没有度为1的结点，根据二叉树的性质3可知有n个叶子结点的二叉树有n-1个非终端结点共有2*n-1个结点。a7b5c2d461118a7b5d4c26111835如何得到最短的二进制前缀码（赫夫曼编码）？为了设计电文总长最短的二进制前缀编码，以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)360231411529378000000111111110058428291519编码：3（0111）5（0110）7（1110）

8（1111）11（010）14（110）

23（00）29（10）37练习：用于通信的电文由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试设计不等长Huffman编码,并给出该电文的总码数。00000001001010001010111011电文总码数=4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=257382023/10/1练习（1）设无向图的顶点个数为n，则该图最多有（）条边。（2）一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。（3）在一个无向图中，所有顶点的度数之和等于所有边数的____倍。（4）要连通具有n个顶点的有向图，至少需要（）条边。（5）若无向图G=（V，E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（）。392023/10/1无向图邻接表表示V1V2

V4

V5

V3

顶点的度：该顶点所在单链表中表结点个数V1V2V3V4V50123413∧04∧202∧12∧14∧3与顶点V1相邻接的顶点在数组中的下标402023/10/1V1V2

V4

V5

V3

254311邻接表表示V1V2V3V4V501234123∧4024∧521114∧133042∧3152∧1权值无向网412023/10/1V1V2

V3

V4

邻接表表示12∧V1V2∧V3V401233∧0∧以顶点V1为始点的弧的终点顶点在数组中的下标顶点的出度该顶点所在单链表中表结点个数顶点的入度查询整个邻接表中的表结点，与该顶点的序号（数组下标）一致的表结点个数有向图422023/10/1图的邻接表表示问题：具有n个顶点e条边的无向图的邻接表中有多少个表头结点？有多个表结点（边结点）？

有向图呢？432023/10/1练习:

请画出下图的邻接矩阵和邻接表442023/10/17.3.1深度优先搜索-举例1234V1V3V4V2datafirstarc2783^^^adjvexnextarc5V5641^51282^V6V7V8678736354^^^V1V2V4V5V3V7V6V8深度遍历：V1

V3V7V6V2V5V8V4给定存储结构，图的遍历序列唯一452023/10/17.3.2广度优先搜索-举例广度遍历：V1V3V2V7V6V5V4V81234V1V3V4V2datafirstarc2783^^^adjvexnextarc5V5641^51282^V6V7V8678736354^^^V1V2V4V5V3V7V6V8给定存储结构，图的遍历序列唯一462023/10/1下列有关图遍历的说法中不正确的是（）A．连通图的深度优先搜索是一个递归过程B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C.图的遍历要求每一顶点仅被访问一次D．对图进行一次深度优先遍历可以访问图中所有顶点472023/10/1给定有向图如下：

给出其邻接表存储结构基于邻接表，给出DFS序列和BFS序列482023/10/1练习：已知一个图的顶点集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)20492023/10/1练习：设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。

【答】E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}502023/10/17.5.1拓扑排序-实现步骤C1C3C2C7C5C6C4编号课程名称C1数学C2程序设计C3离散数学C4汇编程序设计C5数据结构C6结构程序设计C7编译原理C1C3C2C7C5C6C4拓扑有序序列：C1=>C3=>C2=>C4=>C6=>C5=>C7逻辑结构上：拓扑序列不唯一512023/10/17.5.2关键路径AOE-网(ActiveOnEdge)：在带权的有向无环图中，顶点表示事件，弧表示工程的一个活动，弧上权值表示活动持续的时间。用来估算工程完成时间。源点：入度为0的顶点。汇点：出度为0的顶点。路径长度：AOE网中路径上各活动持续时间之和。关键路径：路径长度最长的路径。V1V3V4V6V5V8V2V7V9a1=6a7=9a5=1a2=4a4=1a10=2a3=5a6=2a9=4a11=4a8=7说明：（1）完成工程的最短时间是从开始点到完成点的最长路径的长度。（2）关键路径的改变会影响整个工期。522023/10/1设活动ai在有向无环图G的有向边<j,k>上：事件vj的最早发生时间ve(j):从源点v0到vj的最长路径长度。ve(0)=0;ve(j)=从源点到顶点j的最长的路径长度。ve(k)=Max{ve(j)+dut(<j,k>)}事件vj的最迟开始时间vl(j)：保证汇点vn-1在ve(n-1)时刻完成的前提下，事件vj最迟允许开始的时间。vl(n-1)=ve(n-1)＝从源点到汇点的最长路径长度;vl(k)=从汇点到顶点k的最短的路径长度。vl(j)=Min{vl(k)-dut(<j,k>)}kjdut(<j,k>)ai7.5.2关键路径—定义和术语532023/10/17.5.2关键路径—定义和术语设活动ai在有向边<j,k>上,有：活动ai的最早开始时间e(i)：从源点v0到vj的最长路径长度。e(i)=ve(j);活动ai的最迟开始时间l(i)：是不推迟工程完成的前提下，该活动允许的最迟开始时间。l(i)=vl(k)-dut(<j,k>)活动ai时间余量：l(i)-e(i)关键活动：满足l(i)=e(i)的活动。关键路径上的活动都是关键活动。kjdut(<j,k>)ai542023/10/17.5.2关键路径—求关键活动关键活动e(i)=l(i)e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)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)=Max{ve(j)+dut(<j,k>)}vl(j)=Min{vl(k)-dut(<i,j>)}在拓扑有序的前提下进行在逆拓扑有序前提下进行552023/10/1由汇点至源点由源点至汇点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)=Max{ve(j)+dut(<j,k>)}vl(j)=Min{vl(k)-dut(<j,k>)}e(i)=ve(j);l(i)=vl(k)–dut(<j,k>)14161077866320l(i)000000差1416777546000e(i)a11a10a9a8a7a6a5a4a3a2a1注意：关键路径可有多条。缩短工期必须缩短关键活动所需的时间562023/10/1如何求关键路径？(算法思想)（1）输入e条弧<j,k>，建立AOE网的存储结构；（2）从源点v0出发，令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间ve[i](1

i

n-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止，否则执行步骤（3）；（3）从汇点vn出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求余各顶点的最迟发生时间vl[i](n-2

i

2)（4）根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s).若某条弧满足条件e(s)=l(s),则为关键活动。572023/10/1下列关于AOE网的叙述中，不正确的是（）

A.关键活动不按期完成就会影响整个工程的完成时间

B.某些关键活动提前完成，那么整个工程将会提前完成

C.所有的关键活动提前完成，那么整个工程将会提前完成

D.任何一个关键活动提前完成，那么整个工程将会提前完成582023/10/19.2.1二叉排序树二叉排序树(二叉查找树）(BinarySortTree,BST)：空树或具有下列性质的二叉树:根的左子树若非空，则左子树上的所有结点的关键字值均小于根结点的值。根的右子树若非空，则右子树上的所有结点的关键字值均大于根结点的值。它的左右子树同样是二叉排序树。中序遍历二叉排序树可得到一个关键字的有序序列592023/10/19.2.1二叉排序树的插入例：序列45、24、53、12、90构成一棵二叉排序树建BST树过程：一个无序序列可以构造二叉排序树前提：查找失败插入的结点是一个叶子结点，且是查找失败时查找路径上访问的最后一个结点的左孩子或右孩子。插入算法：二叉排序树的存储结构使用链表首先执行查找算法，找出被插入结点的父亲结点。若二叉树为空。则首先单独生成根结点。判断被插结点是其父亲结点的左、右孩子。将结点插入4553902412602023/10/19.2.1二叉排序树-删除设二叉排序树上被删除结点是p，PL是p的左子树，PR是p的右子树，p的双亲结点是f，不失一般性，设p是f的左孩子。有三种情况：被删除的结点p是叶子结点；被删除的结点p只有左子树或者只有右子树；被删除的结点既有左子树，也有右子树。对二叉排序树，删去一个结点相当于删去有序序列中的一个记录。612023/10/19.2.1二叉排序树-删除1）被删除的结点p是叶子结点：修改双亲结点的指针，令

f->lchild=NULL4553902412pf45539024f例：删除叶子结点12622023/10/19.2.1二叉排序树-删除2）被删除的结点p只有左子树或者只有右子树：令PL或PR直接为其双亲结点f的左子树即可，f->lchild=p->lchild||p->rchild。4553902412pf45539012f例：删除结点24632023/10/19.2.1二叉排序树-删除3）被删除的结点既有左子树，也有右子树。在删去p结点前，中序遍历该二叉树得到的序列为{…CLC…QLQSLSPPRF…}，即S是中序遍历序列中被删结点p的直接前驱结点。方法一：令P的左子树为F的左子树，P的右子树为S的右子树FPPLPRFPCQSPRCLQLSLFCQSPRCLQLSL642023/10/19.2.1二叉排序树-删除3）被删除的结点既有左子树，也有右子树。在删去p结点前，中序遍历该二叉树得到的序列为{…CLC…QLQSLSPPRF…}，即S是中序遍历序列中被删结点p的直接前驱结点。方法二：令p的直接前驱S替代p，再从二叉排序树中删去S。FPPLPRFPCQSPRCLQLSLFSCQPRCLQLSL652023/10/19.2.1二叉排序树-删除举例删除454553123732410061907845123732453100619078662023/10/19.2.1二叉排序树-删除举例删除45451233724531006190783745531237324100619078672023/10/1练习：假定一棵二叉排序树采用二叉链表存储结构，其根结点指针为T,设计一个算法输出该二叉排序树中最大的键值和最小的键值。682023/10/1statusmaxmindata(){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);}692023/10/19.3哈希表查找表的特点：记录的关键字和在结构中的位置之间无确定关系查找过程是给定值依次和关键字集合中各个关键字的比较查找效率取决于和给定值进行比较的关键字个数。希望不经比较，直接可以找到所查记录哈希函数：在记录的关键字和其在表中位置之间建立一种函数关系，即以f(key)作为关键字为key的记录在表中的位置。702023/10/19.3哈希表定义和术语冲突：不同关键字得到同一哈希地址，key1

key2，f(key1)=f(key2)同义词：在一个哈希函数中具有相同函数值的不同关键字。

哈希表：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这种表被称为哈希表。哈希造表或散列：映象过程。哈希地址或散列地址：所得的存储位置。构造哈希表要注意的问题：考虑选择一个“好”的哈希函数;

选择一种处理冲突的方法。712023/10/19.3.3处理冲突的方法1开放定址法：Hi=(H(key)+di)MODmi=1,2,…,k(k≤m-1)，H(key)为哈希函数；m：哈希表长，di是增量序列，有三种取法di=1,2,…m-1，称为线性探测再散列di=12,-12,22,-22,…,±k2(k≤m/2)称为二次探测再散列di=伪随机数列，称为随机探测再散列722023/10/1处理冲突方法举例例：一组关键字19,14,23,01,68,20,84,27,55,11,10,79；按H(key)=keymod13和线性探测再散列方法处理冲突构造表长为16的哈希表。0123456789101112131415311931134121比较次数200820023010冲突次数ASLss=1/12（1*6+2+3*3+4+9）=2.5

14

0168275519208479231110732023/10/19.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.75742023/10/1练习：已知关键字序列为：（75,33,52,41,12,88,66,27），哈希表长为10，哈希函数为：H(k)＝k%9，解决冲突用线性探测法，请：（1）构造出哈希表；（2）计算等概率下查找成功的平均查找长度。752023/10/1TypedefstructLNode{ElemTypedata;//数据域

structLnode*next;//指针域

}LNode,*LinkList;二、结点和单链表的C语言描述LinkListL；//L为单链表的头指针762023/10/1TypedefstructLNode{ElemTypedata;//数据域

structLnode*next;//指针域

}LNode,*LinkList;二、结点和单链表的C语言描述LinkListL；//L为单链表的头指针772023/10/1三、单链表操作的实现GetElem(L,i,&e)//取第i个数据元素ListInsert(&L,i,e)//插入数据元素ListDelete(&L,i,e)//删除数据元素ClearList(&L)//重置线性表为空表CreateList(&L,n)//生成含n个数据元素的链表782023/10/1L

线性表的操作

GetElem(L,i,&e)

在单链表中的实现:211830754256∧pppj123792023/10/1

因此，查找第i个数据元素的基本操作为：移动指针，比较j和i。

单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。

令指针p始终指向线性表中第j个数据元素。802023/10/1StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的链表的头指针，以e返回第i个元素}//GetElem_L算法时间复杂度为:O(ListLength(L))p=L->next;j=1;//p指向第一个结点，j为计数器while(p&&j<i){p=p->next;++j;}//

顺指针向后查找，直到p指向第i个元素

//

或p为空if(!p||j>i)

returnERROR;//第i个元素不存在e=p->data;//取得第i个元素returnOK;812023/10/1ai-1

线性表的操作ListInsert(&L,i,e)

在单链表中的实现：

有序对<ai-1,ai>

改变为<ai-1,e>和<e,ai>eaiai-1822023/10/1

因此，在单链表中第i个结点之前进行插入的基本操作为:

找到线性表中第i-1个结点，然后修改其指向后继的指针。

可见，在链表中插入结点只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。832023/10/1StatusListInsert_L(LinkListL,inti,ElemTypee){

//L为带头结点的单链表的头指针，本算法

//在链表中第i个结点之前插入新的元素e

}//LinstInsert_L算法的时间复杂度为:O(ListLength(L))……p=L;j=0;while(p&&j<i-1)

{p=p->next;++j;}

//

寻找第i-1个结点if(!p||j>i-1)

returnERROR;//

i大于表长或者小于1842023/10/1s=(LinkList)malloc(sizeof(LNode));

//生成新结点s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sp852023/10/1线性表的操作ListDelete(&L,i,&e)在链表中的实现:有序对<ai-1,ai>和<ai,ai+1>

改变为<ai-1,ai+1>ai-1aiai+1ai-1862023/10/1

在单链表中删除第

i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;free(q);pq872023/10/1StatusListDelete_L(LinkListL,inti,ElemType&e){

//删除以L为头指针(带头结点)的单链表中第i个结点

}//ListDelete_L算法的时间复杂度为:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//寻找第i个结点，并令p指向其前趋if(!(p->next)||j>i-1)

returnERROR;//删除位置不合理q=p->next;p->next=q->next;//删除并释放结点e=q->data;free(q);returnOK;882023/10/1操作ClearList(&L)在链表中的实现:voidClearList(&L){//将单链表重新置为一个空表

while(L->next){

p=L->next;L->next=p->next;

}}//ClearListfree(p);算法时间复杂度：O(ListLength(L))892023/10/1逆位序输入n个数据元素的值，建立带头结点的单链表。操作步骤：一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三、输入数据元素an-1，建立结点并插入；ananan-1四、依次类推，直至输入a1为止。902023/10/1voidCreateList_L(LinkList&L,intn){//逆序输入n个数据元素，建立带头结点的单链表}//CreateList_L算法的时间复杂度为:O(Listlength(L))L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一个带头结点的单链表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);//输入元素值

p->next=L->next;L->next=p;//插入}912023/10/1时间复杂度为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->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next;} else{pc->next=pb;pc=pb;pb=pb->next;} } pc->next=pa?pa:pb; free(Lb);}922023/10/15.3.2稀疏矩阵稀疏矩阵：设m行n列的矩阵含t个非零元素，则δ=t/(m*n)称为稀疏因子，通常认为

0.05的矩阵为稀疏矩阵。抽象数据类型稀疏矩阵的定义：书96页稀疏矩阵的压缩存储稀疏矩阵中非零元素位置无规律记住非零元素的行i，列j，值aij稀疏矩阵中存在多个非零元素三元组的C语言描述

typedefstruct{inti,j;ElemTypee;}Triple三元组顺序表的C语言描述#defineMAXSIZE125000typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix932023/10/1三元组表表示的稀疏矩阵的转置设M和T分别是MM和TT的三元组表，如何由M得到T？将矩阵行列值(即m和n)相互交换将每个三元组中的i和j对换重排三元组的次序942023/10/1StatusTransposeSMatrix(TSMatrixM,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.data[p].j==col)

{T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;

T.data[q].e=M.data[p].e;++q;}}returnOK;}//TransposeSMatrix三元组表表示的稀疏矩阵转置算法1评价：O(nu*tu)，优点:节省空间，tu<<mu*nu适用对MM的每一列扫描一遍所有非零元952023/10/1三元组表表示的稀疏矩阵转置方法2思想：按M.data的三元组次序转置，再将三元组置入T中适当的位置。问题：转置前需知MM的每列中非零元素个数及第一个非零元素在T.data中的位置。解决方案：设num和cpot两个向量，num[col]：矩阵MM的第col列中非零元素的个数，cpot[col]:矩阵MM第col列第一个非零元在T.data中的位置cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1](2<=col<=M.nu)StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;++t)++num[M.data[t].j];cpot[1]=1;for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p){col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];}}returnOK;}//TransposeSMatrix

时间复杂度为O(nu+tu),若tu~mu*nu则为O(mu*nu)，与经典算法相同，多用了两个辅助向量。三元组表表示的稀疏矩阵转置方法2统计M中每一列的非零元个数初始化M中每一列第一个非零元应该在T中的位置M中col列下一个非零元应该在T中的位置972023/10/1稀疏矩阵的压缩存储—行逻辑链接顺序表需求：随机存取任一行的非0元方法：记住矩阵每一行第一个非0元在三元组表中的位置设数组rpos[1..n]:矩阵中的每行第一个非零元素的起始位置。

rpos[1]=1;rpos[row]=rpos[row-1]+第row-1行的非零元素个数行逻辑链接顺序表:在稀疏矩阵存储结构中固定指示行信息的辅助数组rpos行逻辑链接表存储结构的Ｃ语言描述：typedefstruct{Tripledata[MAXSIZE+1];

intrpos[MAXRC+1];//各行第一个非零元素位置表

intmu,nu,tu;}RLSMatrix

982023/10/1

0210-2400N=ijv22111-2324行逻辑链接表举例row1234rpos[row]1235N的三元组表

N的rpos向量992023/10/1基于行逻辑链接表表示的稀疏矩阵相乘（1）对于每个元素M.data[p](p=1,2……,M.tu)，找到N中满足条件的N.data[q]，在查找过程中，用到rpos数组，rpos数组的含义是稀疏矩阵中每行第一个非零元素在三元组当中位置的数组，rpos[row]：第row行第一个非零元素在N.data中的序号，rpos[row+1]-1：第row行最后一个非零元素在N.data中的序号，最后一个非零元素在N.data中的位置序号是N.tu。求乘积M.data[p].v

N.data[q].v，然后累加。为操作方便，应对每个元素设一个乘积和的变量数组c