第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);〃確定第一