严蔚敏数据结构题集(c语言版)史上最全答案（一题可有多解）

第1章绪论1.1解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位,在计算机程序中通常作为•个整体进行考虑和处理。数据对象是性质相同的数据元素的集合,是数据的ー个子集。数据结构是相互之间存在ー种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是ー个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指ー个数学模型以及定义在该模型上的ー组操作。是对一般数据类型的扩展。2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解:抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现，这样抽象层次更高,更能为其他用户提供良好的使用接口。1.3解:(dT)—— »(d4)4解：ADTComplex{数据对象：D={r,i|r,i为实数}数据关系：R={<r,i»基本操作：InitComplex(&C,re,im)操作结果：构造ー个复数C,其实部和虚部分别为re和imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e返回复数C的第k元的值Put(&C,k,e)操作结果：改变复数C的第k元的值为eIsAscending(C)操作结果:如果复数C的两个元素按升序排列，则返回1,否则返回〇IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1,否则返回。Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的ー个Min(C,&e)操作结果:用e返回复数C的两个元素中值较小的ー个}ADTComplexADTRationalNumber{数据对象：D={s,m|s,m为自然数，且m不为〇}数据关系：R={〈s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R,其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果:销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果:改变有理数R的第k元的值为eIsAscending(R)操作结果:若有理数R的两个元素按升序排列，则返回1,否则返回〇IsDescending(R)操作结果:若有理数R的两个元素按降序排列,则返回1,否则返回〇Max(R,&e)

操作结果:用e返回有理数R的两个元素中值较大的ー个Min(R,&e)操作结果:用e返回有理数R的两个元素中值较小的一个}ADTRationalNumber试画出与下列程序段等价的框图。product=l;i=l;while(i<=n){product*=i;i++；)i=0;do{i++；}while((i!=n)&&(a[i]!=x));switch{casex<y:z=y-x;break;casex=y:z=abs(x*y);break;default:z=(x-y)/abs(x)*abs(y);)解:(Dexit常用于异常错误处理,它可以强行中断程序的执行,返回操作系统。(2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。(3)用整型函数进行错误处理的优点是可以给出错误类型,便于迅速确定错误。解:(1)用scanf和printf直接进行输入输出的好处是形象、直观,但缺点是需要对其进行格式控制,较为烦琐,如果出现错误,则会引起整个系统的崩溃。(2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽,减少出错的可能。(3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。解:⑴n-1n-1n-1n+(n-l)+(n-2)+...+l="(〃+D2l+(l+2)+(l+2+3)+...+(1+2+3+.l+(l+2)+(l+2+3)+...+(1+2+3+...+nバi(i+1)26立(i+D=空(r+り=人这，1.9解:=丄〃(〃+1)(2〃+1)+;〃(〃+1)=—n(n+1)(2〃+3)1.9解:[v〃J向下取整1100o(log2〃)countslog2n—2n=40n=16解:2"=10n=40n=161ハ12n=10则对于同样的循环次数n,在这个规模下,第二种算法所花费的代价要大得多。故在这个规模下,第•种算法更适宜。解:(1)对⑵错⑶错(4)对⑸错试设定若干n值,比较两函数〃2和50〃log2〃的增长趋势,并确定n在什么范围内,函数〃ユ的值大于50〃logユ〃的值。解：ガ的增长趋势快。但在n较小的时候,50〃log2〃的值较大。当n>438时，n~>50/7log2n解:(l)g(n)快(2)g(n)快(3)f(n)快(4)f(n)快15试用数学归纳法证明：>/2=.(〃+*2〃+1)/6{n>0)z=i=(xrt+,-l)/(x-l)(xl,n>0)i=0(3)右2"=2"-1 (/7>1)1=1(4)豆⑵-1)=〃2 (n>l)试写ー算法,自大至小依次输出顺序读入的三个整数X,丫和Z的值解:intmax3(intx,inty,intz){if(x>y)if(x>z)returnx;elsereturnz;elseif(y>z)returny;elsereturnz;解2：voidprint_descending(intx,inty,intz)〃按从大到小顺序输出三个数{scanf(H%d,%d,%dn,&x,&y,&z);if(x<y)x<->y;〃0为表示交换的双目运算符,以下同if(y<z)y<->z;if(xvy)xv->y;〃冒泡排序printf(M%d%d%dM,x,y,z);}//print_descending解3:(上机已实现)要求实现下列函数:voidDescend(int&x,int&y,int&z);/・按从大到小顺序返回x,y和z的值・/voidDescend(int&x,int&y,int&z)/・按从大到小顺序返回x,y和z的值・/(inttemp;if(x<y){temp=x;x=y;y=temp;}if(y<z){temp=z;z=y;if(x>=temp)y=temp;else{y=x;x=temp;}解:k〉0为阶数,n为数列的第n项intFibonacci(intk,intn)(if(k<l)exit(OVERFLOW);int*p,x;p=newint[k+1];if(!p)exit(OVERFLOW);inti,j;for(i=0;iくk+1;i++){if(i<k-l)p[i]=0;elsep[i]=l;for(i=k+l;i<n+l;i++){x二p[〇];for(j=0;j<k;j++)p[j]=p[j+l];p[k]=2*p[k-l]-x;}returnp[k];解2：Statusfib(intk,intm,int&f)〃求k阶斐波那契序列的第m项的值f{inttempd;if(k<2llm<0)returnERROR;if(m<k-l)f=0;elseif(m==k-1)f=l;else(for(i=0;i<=k-2;i++)temp[i]=0;temp[k-l]=l;〃初始化for(i=k;i<=m;i++)//求Hl序列第k至第m个元素的值(sum=0;for(j=i-k;j<i;j++)sum+=temp[j];temp[i]=sum;)f=temp[m];)returnOK;}//fib分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m9).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(kAm).解3:(上机已实现)要求实现下列函数:StatusFibonacci(intk,intm,int&f);/・如果能求得k阶斐波那契序列的第m项的值f(则返回0K；*//・否则(比如,参数k和m不合理)返回ERROR */StatusFibonacci(intk,intm,int&f)/・求k阶斐波那契序列的第m项的值f*/(inttemp[200],i,j,sum;if(k<2||m<0)returnERROR;if(m<k-l)f=0;elseif(m==kT)f=l;else(for(i=0;i〈=k-2;i++)temp[i]=0;temp[k-l]=l; //初始化for(i=k;i<=m;i++) //求出序列第k至第m个元素的值(sum=0;for(j=i-k;j<=i-l;j++)sum+=temp[j];temp[i]=sum;}f=temp[m];)returnOK;1.18解:typedefenum{A,B,C,D,E}SchoolName;typedefenum{Female,Male}SexType;typedefstruct(charevent[3];〃项目SexTypesex;SchoolNameschool;intscore;}Component;typedefstruct{intMaleSum; 〃男团总分intFemaleSum; 〃女团总分intTotalSum; 〃团体总分}Sum;SumSumScore(SchoolNamesn,Componenta[],intn){Sumtemp;temp.MaleSumニ〇;temp.FernaleSum=0;temp.TotalSum=0;inti;for(i=0;i<n;i++){if(a[i].school==sn){if(a[i].sex==Male)temp.MaleSum+=a[i].score;if(a[i].sex==Female)temp.Fema1eSum+=a[i].score;})temp.TotalSum=temp.MaleSum+temp.FemaleSum;returntemp;)解二:typedefstruct{char*sport;enum{male,female}gender;charschoolname;〃校名为或‘E'char*result;intscore;}resulttype;typedefstruct{intmalescore;intfemalescore;inttotalscore;}scoretype;voidsummary(resulttyperesultロ)〃求各校的男女总分和团体总分,假设结果已经储存在result口数组中scoretypescore;i=0;while(result[i].sport!=NULL)(switch(result[i].schoolname)(case'A':score[0].totalscore+=resu11[i].score;if(result[i].gender==0)score[0].malescore+=result[i].score;elsescore[0].femalescore+=result[i].score;break;case,B':score.totalscore+=result[i].score;if(result[i].gender==O)score.malescore+=result[i].score;elsescore.femalescore+=result[i].score;break;i++:1for(i=0;i<5;i++)(printf(HSchool%d:\nn,i);printf("Totalscoreofmale:%d\nn,score[i].malescore);printf(MTotalscoreoffemale:%d\n",score[i].femalescore);printf("Totalscoreofall:%d\n\nu,score[i].totalscore);){//summary解3:(上机已实现)要求实现下列函数:voidScores(ResultType*result,ScoreType*score);/・求各校的男、女总分和团体总分,并依次存入数组score*//*假设比赛结果已经储存在result"数组中, *//・并以特殊记录「’,male,0}(域scorce=0)*//*表示结束 */相关数据类型定义如下:typedefenum{female,male}Sex;typedefstruct{char*sport;〃项目名称Sexgender;//性别(女:female:男:male)charschoolname;//校名为或Echar*result;/Z成绩intscore;//得分(7,5,4,3,2或1)}ResultType;typedefstruct{intmalescore;/Z男子总分intfemalescore;/Z女子总分inttotalscore;/Z男女团体总分}ScoreType;voidScores(ResuItType*result,ScoreType*score)/・求各校的男、女点分和团体总分,穽依次存入数组score*//・假设比赛结果已经储存在result]]数组中, *//・并以特殊记录male,二"",〇}(域scorce=0)*//・表示结束 ・/(inti=0;while(result[i].sport!=NULL)(switch(result[i].schoolname)(case*A':score[0].totalscore+=result[i].score;if(result[i].gender=O)scorefO].femalescore+=result[i].score;elsescore[0].malescore+=result[i].score;break;caseB:score[1].totalscore+=resultli].score;if(result[i].gender==O)score[1].femalescore+=result[i].score;elsescore[1].malescore+=result[i].score;break;caseC:score[2].totalscore+=result[i].score;if(result[i].gender==O)score[2].femalescore+=result[i].score;elsescore[2].malescore+=result[i].score;break;caseD':score[3].totalscore+=resultfi].score;if(result[i].gender==O)score[3].femalescore+=result[i].score;elsescore[3].malescore+=result[i].score;break;caseE:score[4].totalscore+=result[i].score;if(result[i].gender==O)score[4].femalescore+=result[i].score;elsescore[4J.malescore+=result[i].score;break;}i++;)for(i=0;i<5;i++)(printf(MSchool%d:\nn,i);printf("Totalscoreofmale:%d\n",score[ij.malescore);printf(nTotalscoreoffemale:%d\n",score[i].femalescore);printf("Totalscoreofall:%d\n\n",score[i].totalscore);)}1.19解:#include<iostream.h>#include<stdlib.h>#defineMAXINT65535#defineArrSize100intfun(inti);intmainO(inti,k;inta[ArrSize];coutくく‘Enterk:";cin»k;if(k>ArrSize'l)exit(0);for(i=0;i<=k;i++){if(i==0)a[i]=l;else{if(2*i*a[i-l]>MAXINT)exit(0);elsea[i]=2*i*a[i-l];)}for(i=0;i<=k;i++){if(a[i]>MAXINT)exit(0);elsecout«a[i]<<*}return0;)解二:Statusalgoll9(inta[ARRSIZE])〃求i!*2べ序列的值且不超过maxint(last=1;for(i=l;i<=ARRSIZE;i++)(a[i-l]=last*2*i;if((a[i-l]/last)!=(2*i))reumOVERFLOW;last=a[i-l];returnOK;1}Z/algoll9分析:当某ー项的结果超过了maxint时,它除以前面一项的商会发生异常.1.20voidpolyvalue()floatad;float*p=a;printf("Inputnumberofterms:");scanf("%d",&n);printf("lnputthe%dcoefficientsfromaOtoa%d:\n",n,n);for(i=0;i<=n;i++)scanf("%f',p++);printf("Inputvalueofx:");scanf(H%r,&x);p=a;xp=1;sum=0;//xp用于存放x的i次方for(i=0;i<=n;i++)(sum+=xp*(*p++);xp*=x;)printf("Valueis:%f\sum);}//polyvalue解3:(上机已实现)要求实现下列函数:StatusSeries(intARRSIZE,intaロ);/・求i!*2T序列的值并依次存入长度为ARRSIZE的数组a； *//・若所有值均不超过MAXINT,则返回0K,否则返回OVERFLOW*/StatusSeries(intARRSIZE,inta[])/・求i!*2」序列的值并依次存入长度为ARRSIZE的数组a； *//・若所有值均不超过MAXINT,则返回0K,否则返回OVERFLOW*/(ints=l,i,t;for(i=l;i<=ARRSIZE;i++)(a[i-l]=s*2*i;t=MAXINT/(i+l);if(a[i-l]>t)returnOVERFLOW;s=a[i-l];}returnOK;1.20解:#include<iostream.h>#include<stdlib.h>#defineN10doublepolynomai1(inta[],inti,doublex,intn);intmain()(doublex;intn,i;inta[N];coutくく〃输入变量的值X」;cin»x;coutくく”输入多项式的阶次n:";cin»n;if(n>N-l)exit(0);coutくく”输入多项式的系数a[0]—a[n]:";for(i=0;i<=n;i++)cin»a[i];cout«"Thepolynomailvalueis”くくpolynomai1(a,n,x,n)くくendl;return0;)doublepolynomai1(inta[],inti,doublex,intn)if(i>0)returna[n-i]+polynomail(a,i-l,x,n)*x;

elsereturna[n];本算法的时间复杂度为o(n)。解3:(上机已实现)要求实现下列函数:floatPolynomial(intn,intaロ,floatxO);/・求一元多项式的值P(xO)。 *//・数组a的元素a[i]为i次项的系数,i=0,l,.・・,n♦/floatPolynomial(intn,inta[],floatx)/・求一元多项式的值P(x)° *//・数组a的元素a[i]为i次项的系数,i=0,...,n*/(inti;floatt=l,s,p=0; //t存放x的i次方for(i=0;i<=n;i++)(if(i!=0)t*二x;s=a[i]*t;P+=s;}returnp;第2章线性表描述以下三个概念的区别:头指针,头结点,首元结点(第一个元素结点).解:头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的ー个结点,该结点不存储数据元素,其指针域指向首元结点,其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统ー处理。填空题。解:(1)在顺序表中插入或删除一个元素，需要平均移动表中ー表元素,具体移动的元素个数与元素在差声除生量有关。(2)顺序表中逻辑上相邻的元素的物理位置还紧邻。单链表中逻辑上相邻的元素的物理位置至二定紧邻。(3)在单链表中,除了首元结点外,任一结点的存储位置由除燧绮点的整城物期斤示。(4)在冷犧表中、设‘置も”点的ヤN\辻插入和删除首元结点时不用进行特殊处理,在什么情况下用顺序表比链表好?解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。解:

6-1RRT—Q?!p_♦1p6TISp2.6解:2.?解:2.8解:6-1RRT—Q?!p_♦1p6TISp2.6解:2.?解:2.8解:2.9解:(4)(1)(7)(11)(8)(4)(1)(5)(12)(9)(1)(6)(11)(3)(14)(10)(12)(8)(3)(14)(10)(12)(7)(3)(14)(12)(11)(3)(14)(9) (11) (3) (14)(7)(3)(6)(12)(8)(4)(5)(13)(15) (1) (11) (18)(16) (2) (10) (18)(14) (9) (17)(1)如果L的长度不小于2,将L的首元结点变成尾元结点。(2)将单循环链表拆成两个单循环链表。2.10解:StatusDeleteK(SqList&a,inti,intk)(〃从顺序存储结构的线性表a中删除第i个元素起的k个元素〃注意i的编号从0开始intj;if(i<0i>a.length-1I|k<01|k>a.length-i)returnINFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.Iength=a.length-k;returnOK;}解二:StatusDeleteK(SqList&a,inti,intk)〃删除线性表a中第i个元素起的k个元素if(i<l||k<0||i+k-l>a.length)returnINFEASIBLE;for(count=l;i+count-K=a.length-k;count++)〃注意循环结束的条件e1em[i+count-1]=a.elem[i+count+k-l];a.length一二k;returnOK;}//DeleteK设顺序表va中的数据元素递增有序。试写ー算法,将x插入到顺序表的适当位置上,以保持该表的有序性。解:StatusInsertOrderList(SqList&va,ElemTypex)(〃在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法inti;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x<va.elem[i-l];i-)va.elem[i]=va.elem[i-l];va.elem[i]=x;va.length++;returnOK;)解二:StatusInsert_SqList(SqList&va,intx)〃把x插入递增有序表va中{if(va.length+l>va.listsize)returnERROR;va.length++;for(i=va.length-1;va.elem[i]>x&&i>=0;i—)va.elem[i+l]=va.elem[i];va.elem[i+l]=x;returnOK;}//Insert_SqList解3:(上机已实现)要求实现下列函数:voidInsertOrderList(SqList&L,ElemTypex)/・在有序的顺序表L中保序插入数据元素x*/顺序表类型定义如下:typedefstruct{ElemType*elem;int length;int listsize;}SqList;voidInsertOrderList(SqList&L,ElemTypex)//在有序的顺序表L中保序插入数据元素x(inti,j;i=L.length-1;while(i>=0&&x<=L.elem[i])i—;for(j=L.length-1;j>=i+l;j")L.elem[j+l]=L.elem[j];L.elem[i+l]=x;L.length++;)解:StatusCompareOrderList(SqList&A,SqList&B)(inti,k,j;k=A.length>B.length?A.length:B.length;for(i=0;i<k;i++){if(A.elem[i]>B.elem[i])j=l;if(A.elem[i]<B.elem[i])j=-l;if(A.length>k)j=l;if(B.length>k)j=-l;if(A.length==B.length)j=0;returnj;解二:intListComp(SqListA,SqListB)〃比较字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示AくB;值为零,表示A二B(for(i=l;A.elem[i]||B.elem[i];i++)if(A.elem[i]!=B.elem[i])returnA.elem[i]-B.elem[i];return0;}//ListComp解3:(上机已实现)要求实现下列函数:charCompare(SqListA,SqListB);TOC\o"1-5"\h\z/・比较顺序表A和B, *//・ 返回’ぐ,若AくB; *//* '=',若A=B; *//* 若A〉B */顺序表类型定义如下:typedefstruct{ElemType*elem;int length;int listsize;}SqList;charCompare(SqListA,SqListB)/Z比较顺序表A和B,// 返回’ぐ,若AくB;// '=',若A=B;// '>',若A>B{inti;for(i=0;A.elem[i]iB.elem[i];i++)if(A.elem[i]!=B.elem[i]){if(A.elem[i]-B.elem[i]>0)return' ;elsereturn'く'；}return'二’；)2.13试写ー算法在带头结点的单链表结构上实现线性表操作Located,x);解：intLocateElem_L(LinkList&L,ElemTypex)(inti=0;LinkListp二L;while(p&&p->data!=x){p=p->next;i++；}if(!p)return0;elsereturni;)解二:LNode*Locate(LinkListL,intx)〃链表上的元素查找,返回指针(for(p=l->next;p&&pー〉data!=x;p=p->next);returnp;}//Locate解3:(上机已实现)实现下列函数:LinkListLocate(LinkListL,ElemTypex);//Itx'inthelinkedlistwhoseheadnodeispointed〃by'l,thenreturnpointerpointingnode'x',//otherwisereturn'NULL'单链表类型定义如下:typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListLocate(LinkList&L,ElemTypex)//If'x'inthelinkedlistwhoseheadnodeispointed//by'L',thenreturnpointerhapointingnode'x',//otherwisereturn'NULL'(LinkListp;for(p二L-)next;p&&p-)data!二x;p=pー〉next);returnp;)2.14试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。解:〃返回单链表的长度intListLength_L(LinkList&L){inti=0;LinkListp=L;if(p)p=p-next;while(p){p=p->next;i++；)returni;}解二:intLength(LinkListL)〃求链表的长度(for(k二〇,p=L;p->next;p=p->next,k++);returnk;}//Length解3:(上机已实现)实现下列函数:intLength(LinkListL);//Returnthelengthofthelinkedlist//whoseheadnodeispointedby'L'单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;intLength(LinkListL)//Returnthelengthofthelinkedlist//whoseheadnodeispointedby'L'LinkListp;intk;for(k=0,p=L;p->next;p=p->next,k++);returnk;)2.15解:voidMergeList_L(LinkList&ha,LinkList&hb,LinkList&hc)(LinkListpa,pb;pa=ha;pb=hb;while(pa->next&&pb->next){pa二pa->next;pb=pb-〉next;)if(!pa->next){hc=hb;while(pb->next)pb=pb-〉next;pbー〉next=ha-〉next;}else{hc=ha;while(pa->next)pa二paー〉next;pa-〉next二hbー〉next;}}解二:voidListConcat(LinkListha,LinkListhb,LinkList&hc)〃把链表hb接在ha后面形成链表he(hc=ha;p=ha;while(p->next)p=pー〉next;p->next=hb;}//ListConcat2.16解:StatusDeleteAndlnsertSub(LinkList&la,LinkList&lb,inti,intj,intlen)(LinkListp,q,s,prev=NULL;intk=l;if(i<0；Ij<0||len<0)returnINFEASIBLE;//在la表中查找第i个结点P=la;while(p&&k<i){prev=p;p=p->next;k++;}if(!p)returnINFEASIBLE;//在la表中查找第i+Ien-1个结点q=p;k=l;while(q&&k<len){q=p->next;k++;}if(!q)returnINFEASIBLE;//完成删除,注意,i=l的情况需要特殊处理if(!prev)la=q->next;elseprev->next=q->next;//将从la中删除的结点插入到1b中if(j=l){q->next=lb;lb=p;)else{s=lb;k=l;while(s&&k<j-l){s=s->next;k++;}if(!s)returnINFEASIBLE;q->next=s->next;s->next=p;〃完成插入)returnOK;)解3:(上机已实现)实现下列函数:StatusDeleteAndlnsertSub(LinkList&la,LinkList&lb,inti,intj,intlen);//la和lb分别指向两个单链表中第一个结点, *//・本算法是从la表中删去自第i个元素起共len个元素,*//・并将它们插入到1b表中第j个元素之前, *//・若!b表中只有j-1个元素,则插在表尾。单链表类型定义如下:*/typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;StatusDeleteAndlnsertSub(LinkList&la,LinkList&lb,inti,intj,intlen)TOC\o"1-5"\h\z//la和lb分别指向两个单链表中第一个结点, *//・本算法是从la表中删去自第i个元素起共len个元素,*//・并将它们插入到1b表中第j个元素之前, *//・若1b表中只有j-1个元素,则插在表尾。 */(LinkListp,q,s,prev;intk;if(i<=0|Ij<=0|Ilen<=0)returnINFEASIBLE;p=la;k=l;while(p&&k<i)(prev=p;p=p->next;k++;)if(!p)returnINFEASIBLE;q=P；k=l;while(q&&k<len)(q=q->next;k++;)if(!q)returnINFEASIBLE;if(i==l)Ia=qー〉next;elseprev->next=q->next;if(j==l){q->next=lb;lb=p;}else{s=lb;k=l;while(s&&k<j-l){s=s->next;k++;}if(!s)returnINFEASIBLE;q->next=s->next;sー〉next二p;)returnOK;)2.1?解:StatusInsert(LinkList&L,inti,intb)〃在无头结点链表L的第i个元素之前插入元素b(p=L;q=(LinkList*)malloc(sizeof(LNode));q.data=b;if(i=l)(q.next=p;L=q;〃插入在链表头部)else|while(--i>l)p=p-〉next;qー〉next二pー〉next;p-〉next=q;〃插入在第i个元素的位置}}//Insert2.18试写ー算法,实现线性表操作Delete。,i),并和在带头结点的动态单链表上实现相同操作的算法进行比较。解:StatusDelete(LinkList&L,inti)〃在无头结点链表L中删除第i个元素(if(i==l)L=Lー〉next;〃删除第一个元素else{P=L;while(--i>l)p=p->next;pー〉next二p-〉nextー〉next;〃删除第i个元素}}//Delete2.19解：StatusListDelete_L(LinkList&L,ElemTypemink,ElemTypemaxk){LinkListp,q,prev=NULL;if(mink>maxk)returnERROR;P=L;prev=p;p=p->next;while(p&&p->data<maxk){if(pー〉dataく二mink){prev=p;p=p->next;)else{prev-〉next=p-〉next;q=P；p=p->next;free(q);returnOK;解二:StatusDelete_Between(Linklist&L,intmink,intmaxk)〃删除元素递增排列的链表L中值大于mink且小于maxk的所有元素(P=L;while(p->next->data<=mink)p=p->next:〃p是最后ー・个不大于mink的元素if(p->next) 〃如果还有比mink更大的元素(q二p->next;while(q->data<maxk)q=q->next;〃q是第一个不小于maxk的元素p->next=q;)}//Delete_Between解3:(上机已实现)实现下列函数:voidDeleteSome(LinkList&L,ElemTypemink,ElemTypemaxk);/*Deletealltheelementswhichvalueisbetweenminkand*//*maxkfromthesinglesortedLinkListwithheadpointerL.*/单链表类型定义如下:typedefstructLNode{ElemTypedata;structLNode*next;}LNode,"LinkList;voidDeleteSome(LinkList&L,ElemTypemink,ElemTypemaxk)/*Deletealltheelementswhichvalueisbetweenminkand*//*maxkfromthesinglesortedLinkListwithheadpointerL.*/(LinkListp,q;p=L;q=L->next;while(q)(if(q->data>=maxk)break;elseif(q->data<=mink)(p=q;q=q->next;}else(p->next=q->next;free(q);q=p-〉next;}20解:voidListDeleteLSameNode(LinkList&L){LinkListp,q,prev;P=L;prev=p;p=p-〉next;while(p){prev=p;p=p-〉next;if(p&&p->data==prev->data){prev->next=p->next;Q=P；p=p->next;free(q);)})解二:StatusDelete_Equal(Linklist&L)〃删除元素递增排列的链表L中所有值相同的元素(p=L->next;q=p->next;//p,q指向相邻两元素while(p->next){if(p->data!=q->data)(p=p->next;q=p->next;〃当相邻两元素不相等时,p,q都向后推•步}else{while(q->data==p->data)(free(q);q=q-〉next;}pー〉next二q;p=q;q=p-〉next;〃当相邻元素相等时删除多余元素}//else}//while}//Delete_Equal解3:［上机已实现)实现下列函数:voidPurge(LinkList&L);单链表类型定义如下:typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidPurge(LinkList&L)(LinkListp,q;p=L;q=L-〉next;if(!q)；else{p=q;q=q->next;}while(q){if(p->data==q->data){p-〉next二qー〉next;free(q);q=p->next;)else{p=q；q=q->next;2.21试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(%,…,。“)逆置为(も,…,4)。解:/Z顺序表的逆置StatusListOppose_Sq(SqList&L){inti;ElemTypex;for(i=0;i<L.length/2;i++){x=L.elem[i];L.elem[i]=L.elem[L.length-l-i];L.elem[L.length-l-i]=x;)returnOK;}解二:voidreverse(SqList&A)〃顺序表的就地逆置(for(i=l,j=A.length;i<j;i++,j-)A.elem[i]<->A.elem[j];}//reverse解3:(上机已实现)实现下列函数:voidInverse(SqList&L);顺序表类型定义如下:typedefstruct{ElemType*elem;int length;int listsize;}SqList;voidInverse(SqList&L){inti,j;ElemTypem;for(i=0,j=L.length-1;i<j;i++,j—)(m=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=m;})2.22试写ー算法,对单链表实现就地逆置。解:/Z带头结点的单链表的逆置StatusListOppose_L(LinkList&L){LinkListp,q;P=L;p=p-〉next;L->next=NULL;while(p){q=P；p=p->next;qー〉next=L->next;L->next=q;)returnOK;)解二:voidLinkList_reverse(Link1ist&L)//链表的就地逆置;为简化算法,假设表长大于2p二L一〉next;q=p->next;s=qー〉next;p->next=NULL;while(s->next)(q->next=p;p=q;q=s;s=s->next;〃把L的元素逐个插入新表表头}qー〉next二p;s-〉next二q;L-〉next二s;}//LinkListreverse分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头.解3：(上机已实现)实现下列函数:voidInverse(LinkList&L);/・对带头结点的单链表L实现就地逆置・/单链表类型定义如下:typedefstructLNode{ElemTypedata;structLNode*next;}LNode»札inkList;voidInverse(LinkList&L)/・对带头结点的单链表L实现就地逆置・/(LinkListp,q;p二Lー〉next;L->next=NULL;while(p){q=p->next; //q指向・p的后继pー〉next=L-〉next;Lー〉next二p; //*p插入在头结点之后p=q; 〃向后移动・p2.23解://将合并后的结果放在C表中,并删除B表StatusListMerge_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb;pa=A-〉next;pb=B-〉next;C=A;while(pa&&pb){qa=pa; qb=pb;pa=paー〉next;pb=pbー〉next;qbー〉next二qa-〉next;qa->next=qb;)if(!pa)qb->next=pb;pb=B;free(pb);returnOK;}解二:voidmergel(LinkList&A,LinkList&B,LinkList&C)〃把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间p二Aー〉next;q=B-〉next;C=A;while(p&&q)s=p->next;p->next=q:〃将B的元素插入if(s)(t=q->next;q->next=s:〃如A非空,将A的元素插入}P=s;q=t;}//while}//merge1解3:(上机已实现)实现下列函数:voidMerge(LinkListha,LinkListhb,LinkList&hc)/・依题意,合并带头结点的单链表ha和hb为he*/单链表类型定义如下:typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidMerge(LinkListha,LinkListhb,LinkList&hc)/・依题意,合并带头结点的单链表ha和hb为he*/(LinkListp,q,holdl,hold2;p二ha->next;q=hb-〉next;if(!p){hc=hb;free(ha);}else{hc=ha;while(p&&q)(holdl=p->next;hold2=qー〉next;p->next=q;if(holdl)(q->next=holdl;p二holdl;q=hold2;)elsebreak;}free(hb);}2.24解://将合并逆置后的结果放在C表中,并删除B表StatusListMergeOppose_L(LinkList&.A,LinkList&B,LinkList&C)(LinkListpa,pb,qa,qb;pa二A;pb=B;qa二pa;//保存pa的前驱指针qb=pb;//保存pb的前驱指针pa二paー〉next;pb=pb-〉next;A->next=NULL;C=A;while(pa&&pb){if(pa->dataくpbー〉data){qa=pa;pa=pa-〉next;qa->next=A->next; 〃将当前最小结点插入A表表头A->next=qa;)else{qb=pb;pb=pb->next;qb->next=A->next; 〃将当前最小结点插入A表表头A->next=qb;)}while(pa){qa=pa;pa=pa->next;qaー〉next二Aー〉next;A->next=qa;)while(pb){qb=pb;pb=pb->next;qb->next=A->next;Aー〉next=qb;}pb二B;free(pb);returnOK;)解二:voidreverse_merge(LinkList&A,LinkList&B,LinkList&C)〃把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用盧空间{pa=A->next;pb=B->next;pre=NULL;〃pa和pb分别指向A,B的当前元素while(pa||pb)(if(pa-〉dataくpb-〉dataII!pb)(pc=pa;q=pa-〉next;paー〉next=pre;pa=qi〃将A的兀素插入新表}else|pc=pb;q=pb->next;pb->next=pre;pb=q;〃将B的元素插入新表}pre=pc;)C二A;A-〉next=pc;〃构造新表头}//reverse_merge分析:本算注的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素.25解:/Z将A、B求交后的结果放在C表中StatusListCross_Sq(SqList&A,SqList&B,SqList&C){inti二〇,j二〇,k二〇;while(i<A.length&&j<B.length){if(A.elem[i]<B.elem[j])i++;elseif(A.elem[i]>B.elem[j])j++;else{ListlnsertSq(C,k,A.e1em[i]);i++；k++;}}returnOK;)解二:voidSqList_Intersect(SqListA,SqListB,SqList&C)〃求元素递增排列的线性表A和B的元素的交集并存入C中{i=l;j=l;k=O;while(A.elem[i]&&B.elem[j])(if(A.elem[i]<B.elem[j])i++;if(A.elem[i]>B.elem[j])j++;if(A.elem[i]==B.elem[j])(C.elem[++k]=A.elem[i]:〃当发现了一个在A,B中都存在的元素,i++；j++;〃就添加到C中}}//while}//SqList_Intersect2.26要求同2.25题。试对单链表编写求C的算法。解:/Z将A、B求交后的结果放在C表中,并删除B表StatusListCross_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;//保存pa的前驱指针qb=pb;//保存pb的前驱指针pa=pa->next;pb=pb->next;C=A;while(pa&&pb){if(pa-)dataくpbー〉data){pt=pa;pa=pa->next;qa->next=pa;free(pt);}elseif(pa->data>pb->data){pt=pb;pb=pb->next;qbー〉next=pb;free(pt);)else{qa=pa;pa=pa-〉next;while(pa){pt=pa;pa=pa->next;qaー〉next=pa;free(pt);}while(pb){pt=pb;pb=pb->next;qb->next=pb;free(pt);}pb=B;free(pb);returnOK;)解二:voidLinkListlntersect(LinkListA,LinkListB,LinkList&C)//在链表结构上重做上题(p=A-〉next;q=B-〉next;pc二(LNode*)malloc(sizeof(LNode));while(p&&q)(if(p-〉dataくq-〉data)p=p-〉next;elseif(p->data>q->data)q二q-〉next;else|s=(LNode*)malloc(sizeof(LNode));sー〉data=p-〉data;pcー〉next二s;pc=s;p=p->next;q=q->next;)}//whileC=pc;}//LinkList_Intersect解3:(上机已实现)实现下列函数:voidIntersect(LinkList&hc,LinkListha,LinkListhb);单链表类型定义如下:typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidIntersect(LinkList&hc,LinkListha,LinkListhb){LinkListp,q,pc,s;p二ha-〉next;q=hb-〉next;pc=hc;while(p&&q)(if(p-〉dataくqー〉data)p=p->next;elseif(p->data>q->data)q=q-〉next;else{s=(LNode*)malloc(sizeof(LNode));s->data=p->data;s->next=NULL;pcー)next二s;pc=s;p=p->next;q=q->next;2?解://A、B求交,然后删除相同元素,将结果放在C表中StatusListCrossDelSame_Sq(SqList&A,SqList&B,SqList&C)(inti=0,j=0,k=0;while(i<A.length&&j<B.length){if(A.elem[i]<B.elem[j])i++;elseif(A.elem[i]>B.elem[j])j++;else{if(C.lengthニニ〇){ListInsert_Sq(C,k,A.elem[i]);k++;)elseif(C.elem[C.length-1]!=A.elem[i]){ListInsert_Sq(C,k,A.elem[i]);k++;}i++；))returnOK;)解二:voidSqList_Intersect_True(SqList&A,SqListB)〃求元素递增排列的线性表A和B的元素的交集并存回A中(i=l;j=l;k=O;while(A.elem[i]&&B.elem[j])(if(A.elem[i]<B.elem[j])i++;elseif(A.elem[i]>B.elem[j])j++;elseif(A.elem[i]!=A.elem[k])(A.elem[++k]=A.elem[i];〃当发现了一个在A,B中都存在的元素i++;j++;〃且C中没有,就添加到C中)}//whilewhile(A.elem[k])A.elem[k++]=0;}//SqList_Intersect_True//A、B求交,然后删除相同元素,将结果放在A表中StatusListCrossDelSame_Sq(SqList&A,SqList&B)(inti二〇,j二〇,k二〇;while(i<A.length&&j<B.length){if(A.elem[i]<B.elem[j])i++;elseif(A.elem[i]>B.elem[j])j++;else{if(k==0){A.elem[k]=A.elem[i];k++;)elseif(A.elem[k]!=A.elem[i]){A.elem[k]-A.elem[i];k++;)i++；})A.length=k;returnOK;)2.28解:(1)//A、B求交,结果放在C表中,并删除相同元素StatusListCrossDelSameL(LinkList&A,LinkList&B,LinkList&C)(LinkListpa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;〃保存pa的前驱指针qb=pb:〃保存pb的前驱指针pa=pa->next;pb=pb->next;C=A;while(pa&&pb){if(pa->data<pb->data){pt=pa;pa=pa->next;qaー〉next二pa;free(pt);}elseif(pa-〉data〉pb-〉data){pt=pb;pb=pbー〉next;qb->next=pb;free(pt);)else{if(paー〉dataニニqa-〉data){pt=pa;pa=pa->next;qaー〉next二pa;free(pt);}else{qa=pa;pa=pa-〉next;while(pa){pt=pa;pa=pa-〉next;qaー〉next二pa;free(pt);}while(pb){pt=pb;pb二pb-〉next;qbー〉next二pb;free(pt);}pb=B;free(pb);returnOK;)解二:voidLinkList_Intersect_True(LinkList&A,LinkListB)〃在链表结构上重做上题(p=A-〉next;q=B->next;pc=A;while(p&&q)(if(p->data<q->data)p=p->next;elseif(p->data>q->data)q=q->next;elseif(p-〉data!二pc-〉data)(pc=pcー〉next;pcー〉data=p-〉data;p=p->next;q=q->next;}}//while}//LinkList_Intersect_True(2)//A、B求交,结果放在A表中,并删除相同元素StatusListCrossDelSame_L(LinkList&A,LinkList&B)(LinkListpa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;〃保存pa的前驱指针qb=pb!〃保存pb的前驱指针pa=pa-〉next;pb=pb-〉next;while(pa&&pb){if(paー〉dataくpb-〉data){pt=pa;pa二pa-〉next;qa-〉next=pa;free(pt);)elseif(pa-〉data〉pbー〉data){pt=pb;pb=pb-〉next;qb->next=pb;free(pt);)else{if(pa-)dataニニqaー〉data){pt=pa;pa二pa-〉next;qaー〉next二pa;free(pt);}else{qa=pa;pa=pa->next;while(pa){pt=pa;pa二pa-〉next;qa->next=pa;free(pt);}while(pb){pt=pb;pb=pb->next;qbー〉next二pb;free(pt);}pb=B;free(pb);returnOK;)2.29解:〃在A中删除既在B中出现又在C中出现的元素,结果放在口中StatusListUnion_Sq(SqList&D,SqList&A,SqList&B,SqList&C){SqListTemp;InitList_Sq(Temp);ListCrossL(B,C,Temp);ListMinus_L(A,Temp,D);}解二:voidSqList_IntersectDelete(SqList&A,SqListB,SqListC)(i二0;j=0ルニ〇;m二〇;//i指示A中元素原來的位置,m为移动后的位置while(i<A.length&&j<B.length&&k<C.length){if(B.elem[j]<C.elem[k])j++;elseif(B.elem[j]〉C.elem[k])k++;else(same二B.elem[j]; 〃找到了相同元素samewhile(B.elem[j]=same)j++;while(C.elem[k]=same)k++; //j,k后移到新的元素while(i<A.length&&A.elem[i]<same)A.elem[m++]二A.elem[i++]; 〃需保留的元素移动到新位置while(i<A.length&&A.elem[i]==same)i++;〃跳过相同的元素}}//whilewhile(i<A.length)A.elem[m++]=A.elem[i++];//A的剩余元素重新存储。A.length=m;}//SqList_Intersect_Delete分析:先从B和C中找由共有元素,记为same,再在A中从当前位置开始,凡小于same的元素均保留(存到新的位置),等于same的就跳过,到大于same时就再找下ー个same.2.30要求同2.29题。试对单链表编写算法,请释放A表中的无用结点空间。解://在A中删除既在B中出现又在C中出现的元素,并释放B、CStatusListUnion_L(LinkList&A,LinkList&B,LinkList&C)(ListCrossL(B,C);ListMinus_L(A,B);)//求集合A-B,结果放在A表中,并删除B表StatusListMinus_L(LinkList&A,LinkList&B)(LinkListpa,pb,qa,qb,pt;pa=A;pb二B;qa=pa;//保存pa的前驱指针qb=pb;//保存pb的前驱指针pa=pa->next;pb=pb->next;while(pa&&pb){if(pb->data<pa->data)(pt=pb;pb=pb->next;qb->next=pb;free(pt);)elseif(pb-〉data〉pa->data){qa=pa;pa=pa-〉next;)else{pt=pa;pa=pa-〉next;qa-〉next=pa;free(pt);)}while(pb){pt=pb;pb=pb->next;qbー〉next二pb;free(pt);}pb=B;free(pb);returnOK;)解二:voidLinkList_Intersect_Delete(LinkList&A,LinkListB,LinkListC)//在链表结构上重做上题{p=B-〉next;q=C-〉next;r=A-next;while(p&&q&&r)(if(p-〉dataくq-〉data)p=p-〉next;elseif(p->data>q->data)q=q->next;else|u=p->data;〃确定待删除元素uwhile(r->next->data<u)r=r->next;〃确定最后ー个小于u的元素指针rif(r->next->data=u)(s=r->next;while(s->data=u)(t=s;s=s->next;free(t);〃确定第一