数据结构习题解析与实训 第二章.doc

第2章 线性表线性表是一种最简单、也是最基本的数据结构,用向量存储结构实现的线性表称为顺序表。它的主要基本操作有插入、删除和查找。本章给出一些常见的顺序表应用例题,习题中顺序表的数据结构如下所示。#defineDATATYPE1int#defineMAXSIZE100typedefstructDATATYPE1datasMAXSIZE;intlast;SEQUENLIST;说明:设元素的数据类型为整数,表长不超过100个元素。元素长度存放在last变量中,元素在数组datas中,从下标为1的单元开始存放。2.1习题解析【习题1】将顺序表中元素逆置。题目要求:按用户输入的数据建立一个顺序表,利用最少的辅助空间实现表中元素逆置存放。测试数据:s=100,90,80,70,60,50,40运行结果:s=40,50,60,70,80,90,100下面给出实现顺序表中元素逆置的两个源程序,源程序中黑体部分体现了两种不同的算法。【解答1】#includedatastru.h#include第2章线性表l11main()EQUENLISTa;inti,j,k,temp;printf(请输入顺序表元素,元素为整型量,用空格分开,-99为结束标志:);j=0;k=1;i=0;scanf(%d,&i);while(i!=-99)j+;a.datask=i;k+;scanf(%d,&i);/输入顺序表元素/a.last=j;printf(n逆置前顺序表元素列表:);for(i=1;i=a.last;i+)/逆置前顺序表元素显示/printf(%3d,a.datasi);printf(n);for(i=1;i=a.last/2;i+)/逆置顺序表元素/emp=a.datasi;a.datasi=a.datasa.last-i+1;a.datasa.last-i+1=temp;printf(n逆置后顺序表元素列表:);/逆置后顺序表元素显示/for(i=1;i=a.last;i+)printf(%3d,a.datasi);printf(n);【解答2】#includedatastru.h#includemain()EQUENLISTa;inti,j,k,temp;printf(请输入顺序表元素,元素为整型量,用空格分开,-99为结束标志:);j=0;k=1;i=0;scanf(%d,&i);while(i!=-99)j+;a.datask=i;k+;scanf(%d,&i);/输入顺序表元素/a.last=j;printf(n逆置前顺序表元素列表:);for(i=1;i=a.last;i+)/逆置前顺序表元素显示/printf(%3d,a.datasi);printf(n);for(i=1;i=a.last/2;i+)/逆置顺序表元素/emp=a.datasi;a.datasi=a.datasa.last-i+1;a.datasa.last-i+1=temp;printf(n逆置后顺序表元素列表:);/逆置后顺序表元素显示/for(i=1;i=a.last;i+)l12数据结构习题解析与实训printf(%3d,a.datasi);printf(n);【习题2】求顺序表中最大值元素和次大值元素。题目要求:按用户输入的数据建立一个顺序表,表中元素值不可以重复。输出表中最大值元素和次大值元素。注意:程序要求输入元素个数在2个以上。测试数据:s=10,23,34,5,61,72,29,20运行结果:最大值元素是72次大值元素是61【解答】#includedatastru.h#includemain()EQUENLISTa;inti,j,k,max,submax;printf(请输入顺序表元素,元素为整型量,用空格分开,-99为结束标志:);j=0;k=1;i=0;scanf(%d,&i);while(i!=-99)j+;a.datask=i;k+;scanf(%d,&i);a.last=j;printf(n顺序表元素列表:);for(i=1;ia.datas2)max=a.datas1;submax=a.datas2;/初始最大值元素max和次大值元素submax/elsemax=a.datas2;submax=a.datas1;for(i=3;imax)submax=max;max=a.datasi;elseif(a.datasisubmax)submax=a.datasi;printf(n最大值元素=%3d,次大值元素=%3d,max,submax);printf(n);【习题3】在有序表中插入一个元素并保持该表仍然有序。题目要求:按用户输入的数据建立一个有序表(表中元素递增有序)。将指定元素插第2章线性表l13到表中适当的位置,并保持该有序表的有序性。测试数据:s=10,23,34,5,61,72,29,20运行结果:=5,10,20,23,29,34,61,72插入值:25插入后:s=5,10,20,23,25,29,34,61,72【解答】#includedatastru.h#includemain()EQUENLISTa;inti,k,m,x;printf(请输入顺序表元素,元素为整型量,用空格分开,-99为结束标志:);a.last=0;i=0;scanf(%d,&i);whilei!=-99)/输入顺序表元素,建立有序表/k=a.last;while(k=1)&(i=k+1;m-)a.datasm+1=a.datasm;a.datask+1=i;a.last+;scanf(%d,&i);printf(输入要插入的元素值(整型):);scanf(%d,&x);printf(n插入前有序表元素列表:);for(i=1;i=1)&(x=i+1;m-)a.datasm+1=a.datasm;/移动元素/a.datasi+1=x;/新元素插入/a.last+;/表长加1/printf(n插入后有序表元素列表:);for(i=1;i=a.last;i+)printf(%4d,a.datasi);printf(n);l14数据结构习题解析与实训【习题4】两个有序表合并题目要求:按用户输入的数据建立两个有序表la和lb(元素值递增有序),合并成一个新的递增有序的顺序表lc。在lc中值相同的元素均保留,即lc表长=la表长+lb表长。测试数据:la=10,23,34,5,61,72,29,20,lb=1,3,34,61,56,21,11。运行结果:lc=1,3,5,10,11,20,21,23,29,34,34,56,61,61,72。输入的la和lb表中数据可以是无序的,但程序中对应建立的是有序表,合并后新的顺序表lc中元素也递增有序。程序运行过程如图21所示。图2.1两个有序表合并运行过程【解答】#includedatastru.h#includevoidmerge_sqlist(SEQUENLISTla,SEQUENLISTlb,SEQUENLISTlc)/两有序表合并/inti,j,k;i=j=k=1;whilei=la.last&j=lb.last)if(la.datasidatask=la.datasi;k+;i+;elselc-datask=lb.datasj;k+;j+;while(idatask=la.datasi;k+;i+;while(jdatask=lb.datasj;k+;j+;lc-last=k-1;return;main()SEQUENLISTla,lb,lc;inti,k,m;printf(请输入la顺序表元素,元素为整型量,用空格分开,-99为结束标志:);la.last=0;i=0;scanf(%d,&i);while(i!=-99)/输入la顺序表元素,建立有序表/k=la.last;while(k=1)&(i=k+1;m-)la.datasm+1=la.datasm;la.datask+1=i;la.last+;scanf(%d,&i);printf(nn请输入lb顺序表元素,元素为整型量,用空格分开,-99为结束标志:);lb.last=0;i=0;scanf(%d,&i);while(i!=-99)/输入lb顺序表元素,建立有序表/k=lb.last;while(k=1)&(i=k+1;m-)lb.datasm+1=lb.datasm;lb.datask+1=i;lb.last+;scanf(%d,&i);printf(nla有序表元素列表:);for(i=1;i=la.last;i+)printf(%4d,la.datasi);printf(n);printf(nlb有序表元素列表:);for(i=1;i=lb.last;i+)printf(%4d,lb.datasi);printf(n);merge_sqlist(la,lb,&lc);printf(n合并后lc有序表元素列表:);for(i=1;i=lc.last;i+)printf(%d,lc.datasi);printf(n);l16数据结构习题解析与实训【习题5】删除有序表中的重复元素题目要求:按用户输入的数据建立一个有序表,删除值相同的多余元素(即重复元素只保留一个)。要求删除后表仍保持有序。测试数据:s=10,12,23,34,10,10,5,61,5,10,29,20,61运行结果:建立的有序表为s=5,5,10,10,10,10,12,20,23,29,34,61,61删除后的有序表为s=5,10,12,20,23,29,34,61【解答】#includedatastru.h#includemain()EQUENLISTa;inti,k,m;printf(请输入顺序表元素,元素为整型量,用空格分开,以-99为结束标志:);a.last=0;i=0;scanf(%d,&i);while(i!=-99)/输入顺序表元素,建成有序表/k=a.last;while(k=1)&(i=k+1;m-)a.datasm+1=a.datasm;a.datask+1=i;a.last+;scanf(%d,&i);printf(n删除前有序表元素列表:);for(i=1;i=a.last;i+)printf(%3d,a.datasi);printf(n);i=1;while(ia.last)/删除有序表中重复元素,保留一个/while(ia.last)&(a.datasi=a.datasi+1)or(m=i;ma.last;m+)a.datasm=a.datasm+1;a.last-;i+;printf(n删除后有序表元素列表:);for(i=1;i=a.last;i+)printf(%3d,a.datasi);printf(n);第2章线性表l17【习题6】删除无序表中的重复元素题目要求:按用户输入的数据建立一个顺序表,表中元素不要求有序,删除值相同的多余元素(即重复元素只保留一个)。希望读者能清楚理解在有序表上删除重复元素的算法和在无序表上删除重复元素算法的不同。测试数据:s=10,23,10,10,34,5,61,23,72,29,20,10,23运行结果:s=10,23,34,5,61,72,29,20【解答】#includedatastru.h#includemain()EQUENLISTa;inti,j,k;printf(请输入顺序表元素,元素为整型量,用空格分开,以-99为结束标志:);j=0;k=1;i=0;scanf(%d,&i);while(i!=-99)j+;a.datask=i;k+;scanf(%d,&i);/输入顺序表元素/a.last=j;printf(n删除前顺序表元素列表:);for(i=1;i=a.last;i+)printf(%3d,a.datasi);printf(n);for(i=1;i=a.last;i+)/删除无序表中重复元素,本来、保留一个/j=i+1;while(j=a.last)if(a.datasi=a.datasj)&(j=a.last)or(k=j;ka.last;k+)a.datask=a.datask+1;a.last-;j+;printf(n删除后顺序表元素列表:);for(i=1;i=a.last;i+)printf(%3d,a.datasi);printf(n);【习题7】顺序表并集运算集合上最基本的操作是求集合的并集、交集、差集运算。例如A,B是两个集合,A=a,b,c,B=b,d则并集AB=a,b,c,d交集AB=b差集A-B=a,c,对应集l18数据结构习题解析与实训合的文氏(Venn)图如图22所示。在集合运算中,集合的存储形式可采用顺序表,集合中元素的类型为整型量。题目要求:按用户输入的数据建立两个集合la和lb,同一集合中无重复元素,用顺序表存放。对两集合进行并集运算,结果放在la表中。算法的思路如下:将lb表中的每一个元素作为给定值在la表中查找,若给定值在la表中存在,则不作任何运算处理;否则将此元素加入la表中(追加在la表的最后即可)。图2.2集合的文氏(Venn)图测试数据:la=10,23,34,5,61,72,29,20,lb=5,4,76,61,29运行结果:la=10,23,34,5,61,72,29,20,4,76顺序表存放的两个集合la和lb进行并集运算的过程如图23所示。图2.3集合la和lb进行并集运算的过程【解答】#includedatastru.h#includeintinsert(SEQUENLISTa,DATATYPE1x,inti)/将x元素插在a表指定的i位置上/intk;第2章线性表l19if(ia-last+1|a-last=MAXSIZE)return0;elsefor(k=a-last;k=i;k-)a-datask+1=a-datask;a-datasi=x;a-last+;return1;intlocate(SEQUENLISTa,DATATYPE1x)/x元素在a表中,返回x元素所在位置k;否则返回0)/intk;k=1;while(klast&a-datask!=x)k+;if(klast)returnk;elsereturn0;voidunite(SEQUENLISTla,SEQUENLISTlb)inti;for(i=1;ilast+1);/则将lb表中的该元素插到la表的最后/main()SEQUENLISTa,b;inti,j,k;printf(请输入la顺序表元素,元素为整型量,用空格分开,“-99”为结束标志:);j=0;k=1;i=0;scanf(%d,&i);while(i!=-99)j+;a.datask=i;k+;scanf(%d,&i);/输入la顺序表元素/a.last=j;printf(nla顺序表元素列表:);for(i=1;i=a.last;i+)printf(%3d,a.datasi);printf(n);l20数据结构习题解析与实训printf(n请输入lb顺序表元素,元素为整型量,用空格分开,“-99”为