數(shù)據(jù)結(jié)構(gòu)題集C語言版嚴(yán)蔚敏著答案

第1章緒論簡述卜.列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。解：數(shù)據(jù)是對客觀事物的符號表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示。數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。是對一般數(shù)據(jù)類型的擴(kuò)展。1.2試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語言中數(shù)據(jù)類型概念的區(qū)別。解：抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但含義比一般數(shù)據(jù)類型更廣、更抽象。一般數(shù)據(jù)類型由具體語言系統(tǒng)內(nèi)部定義，直接提供給編程者定義用戶數(shù)據(jù)，因此稱它們?yōu)轭A(yù)定義數(shù)據(jù)類型。抽象數(shù)據(jù)類型通常由編程者定義，包括定義它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進(jìn)行的操作。在定義抽象數(shù)據(jù)類型中的數(shù)據(jù)部分和操作部分時(shí)，要求只定義到數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說明，不考慮數(shù)據(jù)的存儲結(jié)構(gòu)和操作的具體實(shí)現(xiàn)，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。設(shè)有數(shù)據(jù)結(jié)構(gòu)(D,R),其中D={d1,d2,d3,d4},R={r},r={0,d2),(d2,d3),(d3,d4)}試按圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。解：試仿照三元組的抽象數(shù)據(jù)類型分別寫出抽象數(shù)據(jù)類型復(fù)數(shù)和有理數(shù)的定義(有理數(shù)是其分子、分母均為自然數(shù)且分母不為零的分?jǐn)?shù))。解：ADTComplex{數(shù)據(jù)對象:D={r,i|r,i為實(shí)數(shù)}數(shù)據(jù)關(guān)系：R={〈r,i>}基本操作：InitComplex(&C,re,im)操作結(jié)果：構(gòu)造一個(gè)復(fù)數(shù)C,其實(shí)部和虛部分別為re和imDestroyCmoplex(&C)操作結(jié)果：銷毀復(fù)數(shù)CGet(C,k,&e)操作結(jié)果：用e返回復(fù)數(shù)C的第k元的值Put(&C,k,e)操作結(jié)果：改變復(fù)數(shù)C的第k元的值為eIsAscending(C)操作結(jié)果：如果復(fù)數(shù)C的兩個(gè)元素按升序排列，則返回1,否則返回0IsDescending(C)操作結(jié)果：如果復(fù)數(shù)C的兩個(gè)元素按降序排列，則返回1,否則返回0Max(C,&e)操作結(jié)果：用e返回復(fù)數(shù)C的兩個(gè)元素中值較大的一個(gè)Min(C,&e)操作結(jié)果：用e返回復(fù)數(shù)C的兩個(gè)元素中值較小的一個(gè)}ADTComplexADTRationalNumber{數(shù)據(jù)對象：D={s,m|s,m為自然數(shù),且m不為0}數(shù)據(jù)關(guān)系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作結(jié)果：構(gòu)造一個(gè)有理數(shù)R,其分子和分母分別為s和mDestroyRationa1Number(&R)操作結(jié)果：銷毀有理數(shù)RGet(R,k,&e)操作結(jié)果：用e返回有理數(shù)R的第k元的值Put(&R,k,e)操作結(jié)果：改變有理數(shù)R的第k元的值為eIsAscending(R)操作結(jié)果：若有理數(shù)R的兩個(gè)元素按升序排列，則返回1,否則返回0IsDescending(R)操作結(jié)果：若有理數(shù)R的兩個(gè)元素按降序排列，則返回1,否則返回0Max(R,&e)操作結(jié)果：用e返回有理數(shù)R的兩個(gè)元素中值較大的一個(gè)Min(R,&e)操作結(jié)果：用e返回有理數(shù)R的兩個(gè)元素中值較小的一個(gè)}ADTRationalNumber試畫出與下列程序段等價(jià)的框圖。1)product=l;i=l;while(i<=n){product*=i;i++;)2)i=0;do{i++;}while((i!=n)&&(a[i]!=x));3)switch{casex<y:z=y-x;break：casex=y:z=abs(x*y);break：default:z=(x-y)/abs(x)*abs(y);).6在程序設(shè)計(jì)中，常用下列三種不同的出錯(cuò)處理方式：(1)用exit語句終止執(zhí)行并報(bào)告錯(cuò)誤；(2)以函數(shù)的返回值區(qū)別正確返回或錯(cuò)誤返回；(3)設(shè)置一個(gè)整型變量的函數(shù)參數(shù)以區(qū)別正確返回或某種錯(cuò)誤返回。試討論這三種方法各自的優(yōu)缺點(diǎn)。解：(l)exit常用于異常錯(cuò)誤處理，它可以強(qiáng)行中斷程序的執(zhí)行，返回操作系統(tǒng)。(2)以函數(shù)的返回值判斷正確與否常用于子程序的測試，便于實(shí)現(xiàn)程序的局部控制。(3)用整型函數(shù)進(jìn)行錯(cuò)誤處理的優(yōu)點(diǎn)是可以給出借誤類型，便于迅速確定錯(cuò)誤。.7在程序設(shè)計(jì)中，可采用下列三種方法實(shí)現(xiàn)輸出和輸入：(1)通過scanf和printf語句：(2)通過函數(shù)的參數(shù)顯式傳遞；(3)通過全局變量隱式傳遞。試討論這三種方法的優(yōu)缺點(diǎn)。解：(1)用scanf和printf直接進(jìn)行輸入輸出的好處是形象、直觀，但缺點(diǎn)是需要對其進(jìn)行格式控制，較為煩瑣，如果出現(xiàn)錯(cuò)誤，則會引起整個(gè)系統(tǒng)的崩潰。(2)通過函數(shù)的參數(shù)傳遞進(jìn)行輸入輸出，便于實(shí)現(xiàn)信息的隱蔽，減少出錯(cuò)的可能。(3)通過全局變量的隱式傳遞進(jìn)行輸入輸出最為方便，只需修改變量的值即可，但過多的全局變量使程序的維護(hù)較為困難。.8設(shè)n為正整數(shù)。試確定下列各程序段中前置以記號@的語句的頻度：i=l;k=0;while(i<=n-l){@k+=10*i;i++；)i=l;k=0;do{@k+=10*i;i++；}while(i<=n-l);i=l;k=0;while(i<=n-l){i++；@k+=10*i;)k=0：for(i=l;i<=n;i++){for(j=i;j<=n;j++)@k++;)for(i=l;i<=n;i++){for(j=l;j<=i：j++){for(k=l;k<=j;k++)@x+=delta;i=l;j=0;while(i+j<=n){@if(i>j)j++；elsei++;}x=n;y=0; //n是不小于1的常數(shù)while(x>=(y+1)*(y+1)){?y++;}x=91;y=100;while(y>0){@if(x>100){x-=10;y-;}elsex++;}解：(1)n-1⑵n-1⑶n-1/c、 +n+(n-l)+(n-2)+...+1= 21+(1+2)+(1+2+3)+.??+(1+2+3+...+n)=i=lTOC\o"1-5"\h\z]〃 1n i n i n4?a+l)=；Z(/Zz=l Z/=1 Z /=! Z i=\=一〃(〃+1)(2〃+1)+—〃(〃+1)=-n(/j+1)(2〃+3)12 4 12(6)n(7)卜份_|向下取整(8)11001.9假設(shè)n為2的乘嘉，并且n>2,試求下列算法的時(shí)間復(fù)雜度及變量count的值(以n的函數(shù)形式表示)。intTime(intn){count=0; x=2;while(x<n/2){x*=2;count++;}returncount;)解:o(log2n)count=log2n—21.11已知有實(shí)現(xiàn)同一功能的兩個(gè)算法，其時(shí)間復(fù)雜度分別為0(2")和0(療°),假設(shè)現(xiàn)實(shí)計(jì)算機(jī)可連續(xù)運(yùn)算的時(shí)間為IO7秒(100多天)，又每秒可執(zhí)行基本操作(根據(jù)這些操作來估算算法時(shí)間復(fù)雜度)105次。試問在此條件下，這兩個(gè)算法可解問題的規(guī)模(即n值的范圍)各為多少？哪個(gè)算法更適宜？請說明理由。解：2"=1012 n=40H10=1012 n=16則對于同樣的循環(huán)次數(shù)n,在這個(gè)規(guī)模K.第二種算法所花費(fèi)的代價(jià)要大得多。故在這個(gè)規(guī)模F,第一種算法更適宜。12設(shè)有以下三個(gè)函數(shù):/(n)=21n4+n2+1000,g(n)=15n4+500n3,A(n)=500n35+nlogn請判斷以下斷言正確與否：f(n)是0(g(n))h(n^O(f(n))8((1)是0(11(11))h(n)是0(*)h(n)是O(nlogn)解：⑴對⑵錯(cuò)(3)錯(cuò)⑷對⑸錯(cuò)1.13試設(shè)定若干n值，比較兩函數(shù)〃2和50〃log?”的增長趨勢，并確定n在什么范圍內(nèi)，函數(shù)〃2的值大于50〃log2n的值。解：〃2的增長趨勢快。但在n較小的時(shí)候，50“l(fā)og2〃的值較大。當(dāng)n>438時(shí)，n2>50/?log,n1.14判斷下列各對函數(shù)/(〃)和g(〃)，當(dāng)〃一>oo時(shí)，哪個(gè)函數(shù)增長更快？/(〃)=IO"?+ln(〃!+10"),g(n)=2n4+n+7/(?)=(ln(n!)+5)2,g(n)=13n25f(n)=n~'+J/+1,g(n)=(ln(n!))2+n/(〃)=2(""+(2")一, =解：(l)g(n)快(2)g(n)快(3)f(n)快(4)f(n)快L15試用數(shù)學(xué)歸納法證明:>?+1)(2〃+1)/6(n>0)/=!=(x向一l)/(x-l) (x^l,n>0)i=0(m>1)i=\￡⑵-1)=〃2 (W>1)/=!試寫一算法，自大至小依次輸出順序讀入的三個(gè)整數(shù)X,Y和Z的值解：intmax3(intx,inty,intz)(if(x>y)if(x>z)returnx;elsereturnz;elseif(y>z)returny;elsereturnz;}已知k階斐波那契序列的定義為/o=。，力=。fk-2=。，fk-\=1；fn=A-1+fn-2+…+/"-*，〃=女,女+1,…試編寫求k階斐波那契序列的第m項(xiàng)位的函數(shù)算法，k和m均以值調(diào)用的形式在函數(shù)參數(shù)表中出現(xiàn)。解：k>0為階數(shù)，n為數(shù)列的第n項(xiàng)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+l;i++){if(i<k-l)p[i]=0;elsep[i]=l;for(i=k+l;i<n+l;i++){x=p[O];for(j=0;j<k;j++)p[j]=p[j+l];p[k]=2*p[k-l]-x;}returnp[k];)假設(shè)有A,B,C,D,E五個(gè)高等院校進(jìn)行田徑對抗賽，各院校的單項(xiàng)成績均己存入計(jì)算機(jī),并構(gòu)成一張表，表中每一行的形式為項(xiàng)目名稱性別校名成績得分編寫算法，處理上述表格，以統(tǒng)計(jì)各院校的男、女總分和團(tuán)體總分，并輸出。解：typedefenum{A,B,C,D,E}SchoolName;typedefenum{Female,Male}SexType;typedefstruct{charevent[3];〃項(xiàng)目SexTypesex;SchooINameschool;intscore;}Component;typedefstruct{int MaleSum; 〃男團(tuán)總分int FemaleSum; 〃女團(tuán)總分int TotalSum; 〃團(tuán)體總分}Sum;SumSumScore(SchooINamesn,Componenta[],intn){Sumtemp;temp.MaleSum=0;temp.FemaleSum=O;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.FemaleSum+=a[i].score;})temp.TotalSum=temp.MaleSum+temp.FemaleSum;returntemp;}1.19試編寫算法，計(jì)算i!*2'的值并存入數(shù)組a[0..arrsize-1]的第i-l個(gè)分量中(i=l,2,…,n)。假設(shè)計(jì)算機(jī)中允許的整數(shù)最大值為maxint,則當(dāng)n>arrsize或?qū)δ硞€(gè)使依?2?>maxint時(shí)，應(yīng)按出錯(cuò)處理。注意選擇你認(rèn)為較好的出錯(cuò)處理方法。解：#include<iostream.h>#include<stdlib.h>#defineMAXINT65535#defineArrSize100intfun(inti);intmain(){inti,k;inta[ArrSize];cout<<*Enterk:*;cin>>k;if(k>ArrSize-l)exit(0);for(i=0;i<=k;i++){if(i==0)else{if(2*i*a[i-l]>MAXINT)exit(O);elsea[i]=2*i*a[i-l];})for(i=0;i<=k;i++){if(a[i]>MAXINT)exit(O);elsecout?a[i]?*)return0;}1.20試編寫算法求一元多項(xiàng)式的值2(x)=￡的值匕(%),并確定算法中每一語句的執(zhí)/=0行次數(shù)和整個(gè)算法的時(shí)間復(fù)雜度。注意選擇你認(rèn)為較好的輸入和輸出方法。本題的輸入為=0,1,…,〃)，無。和〃，輸出為匕(X。)。解：#include<iostream.h>#include<stdlib.h>#defineN10doublepolynomail(inta[],inti,doublex,intn);intmain()|doublex;intn,i;inta[NJ;cout<〈”輸入變量的值x:";cin?x;cout<<”輸入多項(xiàng)式的階次n:;cin?n;if(n>N-l)exit(0);cout〈〈”輸入多項(xiàng)式的系數(shù)a[0]—a[n]for(i=0：i<=n;i++)cin?a[i]：cout<〈"Thepolynomailvalueisz，<<polynomail(a,n,x,n)?endl;return0;}doublepolynomail(inta[],inti,doublex,intn)if(i>0)returna[n-i]+polynomail(a,i-1,x,n)*x;elsereturna[n];本算法的時(shí)間復(fù)雜度為。(n).第2章線性表描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)(第一個(gè)元素結(jié)點(diǎn))。解：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針。首元結(jié)點(diǎn)是指鏈表中存儲第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。頭結(jié)點(diǎn)是在首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn),該結(jié)點(diǎn)不存儲數(shù)據(jù)元素，其指針域指向首元結(jié)點(diǎn)，其作用主要是為了方便對鏈表的操作。它可以對空表、非空表以及首元結(jié)點(diǎn)的操作進(jìn)行統(tǒng)一處理。2.2填空題。解：(1)在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素,具體移動(dòng)的元素個(gè)數(shù)5元素在表中的位置有失。(2)順序表中邏輯上相鄰的元素的物理位置幺謔緊鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定緊鄰。(3)在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位置由其前駁結(jié)點(diǎn)的鏈域的值指示。(4)在嵬函表中設(shè)罩.央靖點(diǎn)由忤用是插入和刪除首元結(jié)點(diǎn)時(shí)不用進(jìn)行特殊處理。在什么情況下用順序表比鏈表好？解：當(dāng)線性表的數(shù)據(jù)元素在物理位置上是連續(xù)存儲的時(shí)候，用順序表比用鏈表好，其特點(diǎn)是可以進(jìn)行隨機(jī)存取。對以下單鏈表分別執(zhí)行下列各程序段，并畫出結(jié)果示意圖。LLL(4LLL畫出執(zhí)行下列各行語句后各指針及鏈表的示意圖。L=(LinkList)malloc(sizeof(LNode));P=L;for(i=l;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next;P->data=i*2-l;)P->next=NULL;for(i=4;i>=l;i—)Ins_LinkList(L,i+1,i*2);for(i=l;i<=3;i++)Del_LinkList(L,i);解：L-?13?5——?7APL-? ?2 ——?4 ?6 ——?7 ?8人丁

p已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是ob.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是.c.在表首插入S結(jié)點(diǎn)的語句序列是.d.在表尾插入S結(jié)點(diǎn)的語句序列是.P->next=S;P->next=P->next->next;P->next=S-〉next;S->next=P->next;S->next=L;S->next=NULL;Q=P;while(P->next!=Q)P=P-〉next;while(P->next!=NULL)P=P->next;P=Q;P=L;L=S：L=P;解：a.(4)(1)(7)(11)(8)(4)(1)(5)(12)(9)(1)(6)2.7已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。a.刪除P結(jié)點(diǎn)的立接后繼結(jié)點(diǎn)的語句序列是。b.刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是.c.刪除P結(jié)點(diǎn)的語句序列是.d.刪除首元結(jié)點(diǎn)的語句序列是.e.刪除尾元結(jié)點(diǎn)的語句序列是.P=P->next;P->next=P;P->next=P->next->next;P=P->next->next;while(P!=NULL)P=P->next;while(Q->next!=NULL){P=Q;Q=Q->next;}while(P->next!=Q)P=P->next;while(P->next->next!=Q)P=P->next;while(P->next->next!=NULL)P=P->next;Q二P;Q=P->next;P=L;L=L->next;free(Q);解：a. (11) (3)(14)TOC\o"1-5"\h\z(10) (12) (8) (3) (14)(10) (12) (7) (3) (14)(12) (11) (3) (14)(9)(11)(3)(14)已知P結(jié)點(diǎn)是某雙向鏈表的中間結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是ob.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是oc,刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是od.刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是0e.刪除P結(jié)點(diǎn)的語句序列是-P->next=P->next->next;P->priou=P->priou->priou;P->next=S;P->priou=S;S->next=P;S->priou=P;S->next=P->next;S->priou=P->priou;P->priou->next=P->next;P->priou->next=P;P->next->priou=P;P->next->priou二S;P->priou->next=S;P->next->priou=P->priou;Q=P->next;Q=P->priou;free(P);free(Q);解：a.(7)(3)(6)(12)(8)(4)(5)(13)(15)(1)(11)(18)(16)(2)(10)(18)(14)(9)(17)簡述以下算法的功能。StatusA(LinkedListL){//L是無表頭結(jié)點(diǎn)的單鏈表if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;)returnOK;}voidBB(LNode*s,LNode*q){P二s;while(p->next!=q)p=p->next;p->next=s;|voidAA(LNode*pa,LNode*pb){//pa和pb分別指向單循環(huán)鏈表中的兩個(gè)結(jié)點(diǎn)BB(pa,pb);BB(pb,pa);)解：(1)如果L的長度不小于2,將L的首元結(jié)點(diǎn)變成尾元結(jié)點(diǎn)。(2)將單循環(huán)鏈表拆成兩個(gè)單循環(huán)鏈表。2.10指出以下算法中的錯(cuò)誤和低效之處，并將它改寫為一個(gè)既正確又高效的算法。StatusDeleteK(SqList&a,inti,intk)(〃本過程從順序存儲結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素if(i<l|k<01|i+k>a.length)returnINFEASIBLE;〃參數(shù)不合法else{for(count=l;count<k;count++){//刪除第一個(gè)元素for(j=a.length;j>=i+l;j-)a.elem[j-i]=a.elem[j];a.length—;}returnOK;)解：StatusDeleteK(SqList&a,inti,intk)(〃從順序存儲結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素〃注意i的編號從0開始intj;if(i<0|Ii>a.length-11k<0|k>a.length-i)returnINFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length_k;returnOK;11設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置匕以保持該表的有序性。解：StatusTnsertOrderList(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;)設(shè)A= )和8=(4，…，或)均為順序表，A'和B'分別為A和8中除去最大共同前綴后的子表。若4'=8'=空表，則A=8；若A'=空表，而B'w空表，或者兩者均不為空表，且A'的首元小于8'的首元，則A<8；否則A>8。試寫一個(gè)比較A,B大小的算法。解：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;}試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Located,x);解：intLocateElem_L(LinkList&L,ElemTypex){inti=0;LinkListp=L;while(p&&p->data!=x){p=p->next;i++;)if(!p)return0;elsereturni;試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Length(L)。解：〃返回單鏈表的長度intListLength_L(LinkList&L)inti=0;LinkListp=L;if(p)p=p-next;while(p){p=p->next;i++；returni;15已知指針ha和hb分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，并且已知兩個(gè)鏈表的長度分別為用和n。試寫一算法將這兩個(gè)鏈表連接在一起，假設(shè)指針he指向連接后的鏈表的頭結(jié)點(diǎn)，并要求算法以盡可能短的時(shí)間完成連接運(yùn)算。請分析你的算法的時(shí)間復(fù)雜度。解:voidMergeListL(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;))已知指針la和lb分別指向兩個(gè)無頭結(jié)點(diǎn)單鏈表中的首元結(jié)點(diǎn)。下列算法是從表la中刪除自第i個(gè)元素起共len個(gè)元素后，將它們插入到表1b中第i個(gè)元素之前。試問此算法是否正確？若有錯(cuò)，請改正之。StatusDeleteAndlnsertSub(LinkedListla,LinkedListlb,inti,intj,intlen)if(i<0!Ij<Oj|len<0)returnINFEASIBLE;p=la;k=l;TOC\o"1-5"\h\zwhile(k<i){p=p->next; k++;}q=P；while(k<=len){q=q->next; k++;}s=lb;k=l;while(k<j){s=s->next; k++;}s->next=p;q->next=s->next;returnOK;}解：StatusDeleteAndlnsertSub(LinkList&la,LinkList&lb,inti,intj,intlen){LinkListp,q,s,prev=NULL;intk=l;if(i<0||j<0||len<0)returnINFEASIBLE;//在la表中查找第i個(gè)結(jié)點(diǎn)p=la;while(p&&k<i){prev=p;p=p->next;k++;)if(!p)returnINFEASIBLE;//在la表中查找第i+len-l個(gè)結(jié)點(diǎn)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中刪除的結(jié)點(diǎn)插入到lb中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;)試寫一算法，在無頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)線性表操作Insert(L,i,b),并和在帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比較。解：StatusInsert(LinkList&L,inti,intb)〃在無頭結(jié)點(diǎn)鏈表L的第i個(gè)元素之前插入元素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個(gè)元素的位置}}//Insert2.18試寫一算法，實(shí)現(xiàn)線性表操作Delete。,i),并和在帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比較。解：StatusDelete(LinkList&L,inti)〃在無頭結(jié)點(diǎn)鏈表L中刪除第i個(gè)元素{if(i==l)L=L->next;〃刪除第一個(gè)元素else{P=L;while(-i>l)p=p->next;p->next=p->next->next;〃刪除第i個(gè)元素}}//Delete2.19已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效的算法，刪除表中所有值大于mink且小于maxk的元素(若表中存在這樣的元素)，同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時(shí)間復(fù)雜度(注意，mink和maxk是給定的兩個(gè)參變量，它們的值可以和表中的元素相同，也可以不同)。解：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;)2.20同2.19題條件，試寫一高效的算法，刪除表中所有值相同的多余元素(使得操作后的線性表中所有元素的值均不相同)，同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時(shí)間復(fù)雜度。解：voidListDelete_LSameNode(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);2.21試寫一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表(4,逆置為解：//順序表的逆置StatusListOpposeSq(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;)2.22試寫一算法，對單鏈表實(shí)現(xiàn)就地逆置。解：//帶頭結(jié)點(diǎn)的單鏈表的逆置StatusListOpposeL(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;}2.23設(shè)線性表A 《J，8=(伉，&，…,b“)，試寫一個(gè)按下列規(guī)則合并A,B為線性表C的算法，即使得C=(外,如…,b,"+|,…也)當(dāng)機(jī)4〃時(shí)；C={a},b},---,an,bn,an+],---,am)當(dāng)加>〃時(shí)。線性表A,B和C均以單鏈表作存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。解：//將合并后的結(jié)果放在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;)2.24假設(shè)有兩個(gè)按元素值遞增有序排列的線性表A和B,均以單鏈表作存儲結(jié)構(gòu)，請編寫算法將A表和B表歸并成一個(gè)按元素值遞減有序(即非遞增有序，允許表中含有值相同的元素)排列的線性表C,并要求利用原表(即A表和B表)的結(jié)點(diǎn)空間構(gòu)造C表。解：//將合并逆置后的結(jié)果放在C表中，并刪除B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb;pa=A;pb二B;qa=pa;//保存pa的前驅(qū)指針qb=pb;//保存pb的前驅(qū)指針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; 〃將當(dāng)前最小結(jié)點(diǎn)插入A表表頭A->next=qa;}else{qb=pb;pb=pb->next;qb->next=A->next; 〃將當(dāng)前最小結(jié)點(diǎn)插入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;2.25假設(shè)以兩個(gè)元素依值遞增有序排列的線性表A和B分別表示兩個(gè)集合(即同一表中的元素值各不相同)，現(xiàn)要求另辟空間構(gòu)成一個(gè)線性表C,其元素為A和B中元素的交集，且表C中的元素有依值遞增有序排列。試對順序表編寫求C的算法。解：//將A、B求交后的結(jié)果放在C表中StatusListCross_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{ListInsert_Sq(C,k,A.elem[i]);i++；k++;).}returnOK;)2.26要求同2.25題。試對單鏈表編寫求C的算法。解：//將A、B求交后的結(jié)果放在C表中，并刪除B表StatusListCross_L(LinkList&A,LinkList&B,LinkList&C)LinkListpa,pb,qa,qb,pt;pa=A：pb=B;qa=pa;//保存pa的前驅(qū)指針qb=pb;//保存pb的前驅(qū)指針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;2.27對2.25題的條件作以下兩點(diǎn)修改，對順序表重新編寫求得表C的算法。(1)假設(shè)在同一表(A或B)中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；(2)利用A表空間存放表C。解：//A、B求交，然后刪除相同元素，將結(jié)果放在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==O){ListInsertSq(C,k,A.elem[i]);k++;)elseif(C.elem[C.length-1]!=A.e1em[i]){ListInsert_Sq(C,k,A.elem[i]);k++;}i++;})returnOK;}//A、B求交，然后刪除相同元素，將結(jié)果放在A表中StatusListCrossDelSame_Sq(SqList&A,SqList&B)(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(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;28對2.25題的條件作以下兩點(diǎn)修改，對單鏈表重新編寫求得表C的算法。(1)假設(shè)在同一表(A或B)中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；(2)利用原表(A表或B表)中的結(jié)點(diǎn)構(gòu)成表C,并釋放A表中的無用結(jié)點(diǎn)空間。解：//A、B求交，結(jié)果放在C表中，并刪除相同元素StatusListCrossDelSame_L(LinkList&A,LinkList&B,LinkList&C)LinkListpa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;//保存pa的前驅(qū)指針qb=pb;//保存pb的前驅(qū)指針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;}//A、B求交，結(jié)果放在A表中，并刪除相同元素StatusListCrossDelSame_L(LinkList&A,LinkList&B){LinkListpa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;//保存pa的前驅(qū)指針qb=pb;//保存pb的前驅(qū)指針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為三個(gè)遞增有序的線性表，現(xiàn)要求對A表作如下操作：刪去那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素。試對順序表編寫實(shí)現(xiàn)上述操作的算法，并分析你的算法的時(shí)間復(fù)雜度(注意：題中沒有特別指明同一表中的元素值各不相同)。解：//在A中刪除既在B中出現(xiàn)又在C中出現(xiàn)的元素，結(jié)果放在D中StatusListUnion_Sq(SqList&D,SqList&A,SqList&B,SqList&C)SqListTemp;InitListSq(Temp);ListCross_L(B,C,Temp);ListMinusL(A,Temp,D);)30要求同2.29題。試對單鏈表編寫算法，請釋放A表中的無用結(jié)點(diǎn)空間。解：//在A中刪除既在B中出現(xiàn)又在C中出現(xiàn)的元素，并釋放B、CStatusListUnion_L(LinkList&A,LinkList&B,LinkList&C)(ListCross_L(B,C);ListMinus_L(A,B);}//求集合A-B,結(jié)果放在A表中，并刪除B表StatusListMinus_L(LinkList&A,LinkList&B){LinkListpa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;//保存pa的前驅(qū)指針qb二pb;〃保存pb的前驅(qū)指針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;}2.31假設(shè)某個(gè)單向循環(huán)鏈表的長度大于1,且表中既無頭結(jié)點(diǎn)也無頭指針。已知s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。解：//在單循環(huán)鏈表S中刪除S的前驅(qū)結(jié)點(diǎn)StatusListDelete_CL(LinkList&S){LinkListp,q;if(S==S->next)returnERROR;q二S;p=S->next;while(p->next!=S){q=P；p=p->next;}q->next=p->next;free(p);returnOK;}2.32已知有一個(gè)單向循環(huán)鏈表，其每個(gè)結(jié)點(diǎn)中含三個(gè)域：pre,data和next,其中data為數(shù)據(jù)域，next為指向后繼結(jié)點(diǎn)的指針域，pre也為指針域，但它的值為空，試編寫算法將此單向循環(huán)鏈表改為雙向循環(huán)鏈表，即使pre成為指向前驅(qū)結(jié)點(diǎn)的指針域。解：//建立一個(gè)空的循環(huán)鏈表StatusInitList_DL(DuLinkList&L){L=(DuLinkList)malloc(sizeof(DuLNode));if(!L)exit(OVERFLOW);—pre=NULL;L->next=L;returnOK;)//向循環(huán)鏈表中插入一個(gè)結(jié)點(diǎn)StatusListInsert_DL(DuLinkList&L,ElemTypee){DuLinkListp;p=(DuLinkList)malloc(sizeof(DuLNode));if(!p)returnERROR;p->data=e;p->next=L->next;L->next=p;returnOK;}//將單循環(huán)鏈表改成雙向鏈表StatusListCirToDu(DuLinkList&L){DuLinkListp,q;q=L;p=L->next;while(p!=L){p->pre=q;q=P；p=p->next;.}if(p==L)p->pre=q;returnOK;}2.33已知由一個(gè)線性鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素(如：字母字符、數(shù)字字符和其他字符)，試編寫算法將該線性表分割為三個(gè)循環(huán)鏈表，其中每個(gè)循環(huán)鏈表表示的線性表中均只含一類字符。解：//將單鏈表L劃分成3個(gè)單循環(huán)鏈表StatusListDivideInto3CL(LinkList&L,LinkList&sl,LinkList&s2,LinkList&s3)(LinkListp,q,ptl,pt2,pt3;p=L->next;ptl=sl;pt2=s2;pt3=s3;while(p){if(p->data>=0*&&p->data<=91){q=P；p=p->next;q->next=ptl->next;ptl->next=q;ptl=ptl->next;}elseif((p->data>=A*&&p->data<=Z*)||(p->data>=，a*&&p->data<=，z')){q=P；p=p->next;q->next=pt2_>next;pt2->next=q;pt2=pt2->next;)else(q二P；p=p->next;q->next=pt3->next;pt3->next=q;pt3=pt3->next;)}q=L;free(q);returnOK;)在2.34至2.36題中，“異或指針雙向鏈表”類型XorLinkedList和指針異或函數(shù)XorP定義為：typedefstructXorNode{chardata;structXorNode*LRPtr;}XorNode,*XorPointer;typedestruct{ 〃無頭結(jié)點(diǎn)的異或指針雙向鏈表XorPointerLeft,Right; 〃分別指向鏈表的左側(cè)和右端}XorLinkedList;XorPointerXorP(XorPointerp,XorPointerq);//指針異或函數(shù)XorP返回指針p和q的異或值2.34假設(shè)在算法描述語言中引入指針的二元運(yùn)算“異或”，若a和b為指針，則a?b的運(yùn)算結(jié)果仍為原指針類型，且a?(a?b)=(a?a)?b=b(a?b)?b=a?(b?b)=a則可利用一個(gè)指針域來實(shí)現(xiàn)雙向鏈表L鏈表L中的每個(gè)結(jié)點(diǎn)只含兩個(gè)域：data域和LRPtr域,其中LRPtr域存放該結(jié)點(diǎn)的左鄰與右鄰結(jié)點(diǎn)指針(不存在時(shí)為NULL)的異或。若設(shè)指針L.Left指向鏈表中的最左結(jié)點(diǎn)，L.Right指向鏈表中的最右結(jié)點(diǎn)，則可實(shí)現(xiàn)從左向右或從右向左遍歷此雙向鏈表的操作。試寫一算法按任一方向依次輸出鏈表中各元素的值。解：StatusTraversingLinkList(XorLinkedList&L,chard){XorPointerp,left,right;if(d='l'||d='L'){p=L.Left;left=NULL;while(p!=NULL){VisitingData(p->data);left=p;p=XorP(left,p->LRPtr);)elseif(d=='r'||d='R'){p=L.Right;right=NULL;while(p!=NULL){VisitingData(p->data);right=p;p=XorP(p->LRPtr,right);)}elsereturnERROR;returnOK;}2.35采用2.34題所述的存儲結(jié)構(gòu)，寫出在第i個(gè)結(jié)點(diǎn)之前插入一個(gè)結(jié)點(diǎn)的算法。解：StatusInsert_XorLinkedList(XorLinkedList&L,intx,inti)〃在異或鏈表L的第i個(gè)元素前插入元素x(p=L.left;pre=NULL;r=(XorNode*)malloc(sizeof(XorNode));r->data=x;if(i==l)〃當(dāng)插入點(diǎn)在最左邊的情況(p->LRPtr=XorP(p.LRPtr,r);r->LRPtr=p;L.left=r;returnOK;}j=l;q=p->LRPtr;〃當(dāng)插入點(diǎn)在中間的情況while(++j<i&&q){q=XorP(p->LRPtr,pre);pre=p;p=q;}//while〃在p,q兩結(jié)點(diǎn)之間插入if(!q)returnINFEASIBLE;//i不可以超過表長p->LRPtr=XorP(XorP(p->LRPtr,q),r);q->LRPtr=XorP(XorP(q->LRPtr,p),r);r->LRPtr=XorP(p,q);〃修改指針returnOK;}//Insert_XorLinkedList2.36采用2.34題所述的存儲結(jié)構(gòu)，寫出刪除第i個(gè)結(jié)點(diǎn)的算法。解：StatusDeleteXorLinkedList(XorlinkedList&L,inti)〃刪除異或鏈表L的第i個(gè)元素{p=L.left;pre=NULL;if(i==l)〃刪除最左結(jié)點(diǎn)的情況(q=p->LRPtr;q->LRPtr=XorP(q->LRPtr,p);L.left=q;free(p);returnOK;)j=l;q=p->LRPtr;while(++j<i&&q)(q=XorP(p->LRPtr,pre);pre=p;p=q;}//while〃找到待刪結(jié)點(diǎn)qif(!q)returnINFEASIBLE;//i不可以超過表長if(L.right==q)〃q為最右結(jié)點(diǎn)的情況(p->LRPtr=XorP(p->LRPtr,q);L.right=p;free(q);returnOK;}r=XorP(q->LRPtr,p);//q為中間結(jié)點(diǎn)的情況,此時(shí)p,r分別為其左右結(jié)點(diǎn)p->LRPtr=XorP(XorP(p->LRPtr,q),r);r->LRPtr=XorP(XorP(r->LRPtr,q),p);〃修改指針free(q);returnOK;}//Delete_XorLinkedList2.37設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表乙=(。|,出,…,4)。試寫一時(shí)間復(fù)雜度0(n)的算法，將L改造為L=(al,a3,---,an,---,a4,a2),,解：//將雙向鏈表L=(al,a2,...,an)改造為(al,a3,...,an,...,a2)StatusListChange_DuL(DuLinkList&L)inti;DuLinkListp,q,r;p=L->next;r=L->pre;i二l；whi1e(p!=r){if(i%2=0){q=p；p=p->next;//刪除結(jié)點(diǎn)q->pre->next=q->next;q->next->pre=q->pre;//插入到頭結(jié)點(diǎn)的左面q->pre=r->next->pre;r->next->pre=q;q->next=r->next;r->next=q;}elsep=p->next;i++;.}returnOK;)2.38設(shè)有一個(gè)雙向循環(huán)鏈表，每個(gè)結(jié)點(diǎn)中除有pre,data和next三個(gè)域外，還增設(shè)了一個(gè)訪問頻度域freq。在鏈表被起用之前，頻度域freq的值均初始化為零，而每當(dāng)對鏈表進(jìn)行一次Locate(L,x)的操作后，被訪問的結(jié)點(diǎn)(即元素值等于x的結(jié)點(diǎn))中的頻度域freq的值便增1,同時(shí)調(diào)整鏈表中結(jié)點(diǎn)之間的次序，使其按訪問頻度非遞增的次序順序排列，以便始終保持被頻繁訪問的結(jié)點(diǎn)總是靠近表頭結(jié)點(diǎn)。試編寫符合上述要求的Locate操作的算法。解：DuLinkListListLocate_DuL(DuLinkList&L,ElemTypee){DuLinkListp,q;p=L->next;while(p!=L&&p->data!=e)p=p->next;if(p==L)returnNULL;else{p->freq++;//刪除結(jié)點(diǎn)p->pre->next=p->next;p->next->pre=p->pre;//插入到合適的位置q=L->next;while(q!=L&&q->freq>p->freq)q=q->next;if(q==L){p->next=q->next;q->next=p;p->pre=q->pre;q->pre=p;}else{〃在q之前插入p->next=q->pre->next;q->pre->next=p;p->pre=q->pre;q->pre=p;}returnp;}}在2.39至2.40題中，稀疏多項(xiàng)式采用的順序存儲結(jié)構(gòu)SqPoly定義為typedefstruct{intcoef;intexp;}PolyTerm;typedefstruct{ 〃多項(xiàng)式的順序存儲結(jié)構(gòu)PolyTerm*data;intlast;}SqPoly;2.39已知稀疏多項(xiàng)式￡,(x)=C|X”+c2xf2+??+cmxe",其中〃=>em_}>???>4>0,c,.*0(/=1,2,???,/?).m>\,試采用存儲量同多項(xiàng)式項(xiàng)數(shù)m成正比的順序存儲結(jié)構(gòu)，編寫求2(/)的算法(/為給定值)，并分析你的算法的時(shí)間復(fù)雜度。解：typedefstruct{intcoef;intexp;PolyTerm;typedefstruct{PolyTerm*data;intlast;SqPoly;//建立一個(gè)多項(xiàng)式StatusPolylnit(SqPoly&L)PolyTerm*p;cout〈〈”請輸入多項(xiàng)式的項(xiàng)數(shù):"；cin>>L.last;L.data=(PolyTerm*)malloc(L.last*sizeof(PolyTerm));if(!L.data)returnERROR;p=L.data;for(i=0;i<L.last;i++){cout<<”請輸入系數(shù)：〃；cin>>p->coef;cout<<”請輸入指數(shù)：”;cin>>p->exp;P++；)returnOK;}//求多項(xiàng)式的值doublePolySum(SqPoly&L,doublexO){doublePn,x;inti,j;PolyTerm*p;p=L.data;for(i=0,Pn=0;i<L.last;i++,p++){for(j=0,x=l;j<p->exp;j++)x=x*xO;Pn=Pn+p->coef*x;}returnPn;}2.40采用2.39題給定的條件和存儲結(jié)構(gòu)，編寫求P(x)=《“(尤)-匕2(6的算法，將結(jié)果多項(xiàng)式存放在新辟的空間中，并分析你的嵬法的時(shí)間復(fù)雜度。解：//求兩多項(xiàng)式的差StatusPolyMinus(SqPoly&L,SqPoly&L1,SqPoly&L2){PolyTerm*p,*pl,*p2;p=L.data;pl=Ll.data;p2=L2.data;inti=0,j=0,k=0;while(i<Ll.last&&j<L2.last){if(pl->exp<p2->exp){p->coef=pl->coef;p->exp=pl->exp;p++;k++;pl++; i++;}elseif(pl->exp>p2->exp){p->coef=-p2->coef;p->exp=p2->exp;p++; k++;p2++; j++;}else{if(pl->coef!=p2->coef){p->coef=(pl->coef)-(p2->coef);p->exp=pl->exp;TOC\o"1-5"\h\zp++; k++;)pl++； p2++;i++； j++；))if(i<Ll.last)while(i<Ll.last){p->coef=pl->coef;p->exp=pl->exp;p++; k++;pl++; i++;}if(j<L2.last)while(j<L2.last){p->coef=-p2->coef;p->exp=p2->exp;p++; k++;p2++; j++;}L.last=k;returnOK;}在2.41至2.42題中，稀疏多項(xiàng)式采用的循環(huán)鏈表存儲結(jié)構(gòu)LinkedPoly定義為typedefstructPolyNode{PolyTermdata;structPolyNode*next;}PolyNode,*PolyLink;typedefPolyLinkLinkedPoly;2.41試以循環(huán)鏈表作稀疏多項(xiàng)式的存儲結(jié)構(gòu)，編寫求其導(dǎo)函數(shù)的方法，要求利用原多項(xiàng)式中的結(jié)點(diǎn)空間存放其導(dǎo)函數(shù)多項(xiàng)式，同時(shí)釋放所有無用結(jié)點(diǎn)。解：StatusPolyDifferential(LinkedPoly&L)|LinkedPolyp,q,pt;q=L;p=L->next;while(p!=L){if(p->data.exp==0){Pt=P；p=p->next;q->next=p;free(pt);}else{p->data.coef=p->data.coef*p->data.exp;p->data.exp—;q二P；p=p->next;})returnOK;}2.42試編寫算法，將一個(gè)用循環(huán)錐表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式，使這兩個(gè)多項(xiàng)式中各自僅含奇次項(xiàng)或偶次項(xiàng)，并要求利用原鏈表中的結(jié)點(diǎn)空間構(gòu)成這兩個(gè)鏈表。解：//將單鏈表L劃分成2個(gè)單循環(huán)鏈表StatusListDivideInto2CL(LinkedPoly&L,LinkedPoly&L1){LinkedPolyp,pl,q,pt;q=L;p=L->next;pl=Ll;while(p!=L){if(p->data.exp%2==0){Pt=P；p=p->next;q->next=p;pt->next=pl->next;pl->next=pt;pl=pl->next;}else{q=P；p=p->next;returnOK;第3章棧和隊(duì)列若按教科書3.L1節(jié)中圖3.1(b)所示鐵道進(jìn)行車廂調(diào)度(注意:兩側(cè)鐵道均為單向行駛道)，則請回答：(1)如果進(jìn)站的車廂序列為123,則可能得到的出站車廂序列是什么？(2)如果進(jìn)站的車廂序列為123456,則能否得到435612和135426的出站序列，并請說明為什么不能得到或者如何得到(即寫出以'S，表示進(jìn)棧和以'X'表示出棧的棧操作序列).解：⑴123231321213132(2)可以得到135426的出站序列,但不能得到435612的出站序列。因?yàn)?356出站說明12已經(jīng)在棧中，1不可能先于2出棧。簡述棧和線性表的差別。解：線性表是R有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表。寫出下列程序段的輸出結(jié)果(棧的元素類型SElemType為char)。voidmain()(StackS;charx,y;InitStack(S);x='c';y='k';Push(S,x);Push(S, *a*)：Push(S,y);Pop(S,x); Push(S, 't');Push(S,x);Pop(S,x);Push(S,，s');while(!StackEmpty(S)){Pop(S,y)：printf(y);}printf(x);)解:stack簡述以下算法的功能(棧的元素類型SElemType為int)。statusalgol(StackS)(inti,n,A[255];n=0;while(!StackEmpty(S)){n++;Pop(S,A[n]);}for(i=l;i<=n;i++)Push(S,A[i]);}statusalgo2(StackS,inte)StackT;intd;InitStack(T);while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);)while(!StackEmpty(T)){Pop(T,d);Push(S,d);解：（1）棧中的數(shù)據(jù)元素逆置 （2）如果棧中存在元素e,將其從棧中清除5假設(shè)以S和X分別表示入棧和出棧的操作，則初態(tài)和終態(tài)均為空棧的入棧和出棧的操作序列可以表示為僅由S和X組成的序列。稱可以操作的序列為合法序列（例如，SXSX為合法序列，SXXS為非法序列）。試給出區(qū)分給定序列為合法序列或非法序列的一般準(zhǔn)則，并證明：兩個(gè)不同的合法（棧操作）序列（對同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實(shí)體，而不是值）序列。解：任何前n個(gè)序列中S的個(gè)數(shù)一定大于X的個(gè)數(shù)。設(shè)兩個(gè)合法序列為：T1=S X S T2=S X X 假定前n個(gè)操作都相同，從第n+1個(gè)操作開始，為序列不同的起始操作點(diǎn)。由于前n個(gè)操作相同，故此時(shí)兩個(gè)棧（不妨為棧A、B）的存儲情況完全相同，假設(shè)此時(shí)棧頂元素均為a。第n+1個(gè)操作不同，不妨T1的第n+1個(gè)操作為S,T2的第n+1個(gè)操作為X。T1為入棧操作，假設(shè)將b壓棧，則T1的輸出順序一定是先b后a；而T2將a退棧，則其輸出順序一定是先a后bo由于T1的輸出為……ba……，而T2的輸出順序?yàn)椤璦b……，說明兩個(gè)不同的合法棧操作序列的輸出元素的序列一定不同。試證明：若借助棧由輸入序列12…n得到的輸出序列為p〃2…p“（它是輸入序列的一個(gè)排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j〈k使Pj〈Pk<P-解：這個(gè)問題和3.1題比較相似。因?yàn)檩斎胄蛄惺菑男〉酱笈帕械?，所以若PjVprPi，則可以理解為通過輸入序列Pjpkp,可以得到輸出序列p：PjPq顯然通過序列123是無法得到312的，參見3.1題。所以不可能存在著i〈j〈k使吃按照四則運(yùn)算加、減、乘、除和霉運(yùn)算（t）優(yōu)先關(guān)系的慣例，并仿照教科書3.2節(jié)例3-2的格式，畫出對下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程：A-BXC/D+EtF解：BC=GG/D=HA-H=IE-F=JI+J=K步驟OPT"OPND棧輸入字符主要操作1A-B*C/D+E"F#PUSH(OPND,A)2nA二B*C/D+E「F#PUSH(OPTR,-)3n-AB*C/D+E'F#PUSH(OPND,B)4#-AB*C/D+E'F#PUSH(OPTR,*)5#-*ABC/D+E'F#PUSH(0PND,C)6#-*ABC/D+E'F#Operate(B,*,C)7n-AG/D+E*F#PUSH(OPTR,/)8#-/AGD+E-F#PUSH(OPND,D)9#-/AGD士E'F#Operate(G,/,D)10AII+E*F#Operate(A,H)11I+E*F#PUSH(OPTR,+)12#+IPUSH(OPND,E)13#+IE二F#PUSH(OPTR,")14#+'1EPUSH(OPND.F)15#+'IEFOperate(E,,F)16#+IJ#Operated,+,J)17K#RETURN3.8試推導(dǎo)求解n階梵塔問題至少要執(zhí)行的move操作的次數(shù)。解：2n-13.9試將下列遞推過程改寫為遞歸過程。voidditui(intn)(inti;=n;while(i>l)cout<<i—;}解：void