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

第1章緒論簡(jiǎn)述下列術(shù)語(yǔ)：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型。解：數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示。數(shù)據(jù)類(lèi)型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱(chēng)。抽象數(shù)據(jù)類(lèi)型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。是對(duì)一般數(shù)據(jù)類(lèi)型的擴(kuò)展。試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類(lèi)型的概念與程序設(shè)計(jì)語(yǔ)言中數(shù)據(jù)類(lèi)型概念的區(qū)別。解：抽象數(shù)據(jù)類(lèi)型包含一般數(shù)據(jù)類(lèi)型的概念，但含義比一般數(shù)據(jù)類(lèi)型更廣、更抽象。一般數(shù)據(jù)類(lèi)型由具體語(yǔ)言系統(tǒng)內(nèi)部定義，直接提供給編程者定義用戶(hù)數(shù)據(jù)，因此稱(chēng)它們?yōu)轭A(yù)定義數(shù)據(jù)類(lèi)型。抽象數(shù)據(jù)類(lèi)型通常由編程者定義，包括定義它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進(jìn)行的操作。在定義抽象數(shù)據(jù)類(lèi)型中的數(shù)據(jù)部分和操作部分時(shí),要求只定義到數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說(shuō)明，不考慮數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和操作的具體實(shí)現(xiàn)，這樣抽象層次更高，更能為其他用戶(hù)提供良好的使用接設(shè)有數(shù)據(jù)結(jié)構(gòu)(D,R),其中D={dl,d2,d3,d4}, =r= J2),(J2,J3),(J3,J4))試按圖論中圖的畫(huà)法慣例畫(huà)出其邏輯結(jié)構(gòu)圖。試仿照三元組的抽象數(shù)據(jù)類(lèi)型分別寫(xiě)出抽象數(shù)據(jù)類(lèi)型復(fù)數(shù)和有理數(shù)的定義(有理數(shù)是其分子、分母均為自然數(shù)且分母不為零的分?jǐn)?shù)1解：ADTComplex{數(shù)據(jù)對(duì)象：D={r,ilr,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é)果：銷(xiāo)毀復(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ù)對(duì)象：D={s,mls,m為自然數(shù)，且m不為0}數(shù)據(jù)關(guān)系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作結(jié)果：構(gòu)造一個(gè)有理數(shù)R,其分子和分母分別為s和mDestroyRationalNumber(&R)操作結(jié)果：銷(xiāo)毀有理數(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è)}ADTRationalNumber1.5試畫(huà)出與下列程序段等價(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語(yǔ)句終止執(zhí)行用艮告錯(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ù)的返回值判斷正確與否常用于子程序的測(cè)試，便于實(shí)現(xiàn)程序的局部控制。⑶用整型函數(shù)進(jìn)行錯(cuò)誤處理的優(yōu)點(diǎn)是可以給出錯(cuò)誤類(lèi)型，便于迅速確定錯(cuò)誤。.7在程序設(shè)計(jì)中，可采用下列三種方法實(shí)現(xiàn)輸出和輸入：(1)通過(guò)scanf和printf語(yǔ)句；(2)通過(guò)函數(shù)的參數(shù)顯式傳遞；(3)通過(guò)全局變量隱式傳遞。試討論這三種方法的優(yōu)缺點(diǎn)。解：(1)用scanf和printf直接進(jìn)行輸入輸出的好處是形象、直觀，但缺點(diǎn)是需要對(duì)其進(jìn)行格式控制，較為煩瑣，如果出現(xiàn)錯(cuò)誤，則會(huì)引起整個(gè)系統(tǒng)的崩潰。⑵通過(guò)函數(shù)的參數(shù)傳遞進(jìn)行輸入輸出，便于實(shí)現(xiàn)信息的隱蔽，減少出錯(cuò)的可能。⑶通過(guò)全局變量的隱式傳遞進(jìn)行輸入輸出最為方便，只需修改變量的值即可，但過(guò)多的全局變量使程序的維護(hù)較為困難。.8設(shè)n為正整數(shù)。試確定下列各程序段中前置以記號(hào)@的語(yǔ)句的頻度：(l)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=O;while(i+j<=n){@if(i>j)>+;elsei++;x=n;y=0; //n是不小于1的常數(shù)while(x>=(y+l)*(y+l)){@y++;}x=91;y=100;while(y>0){@if(x>100){x-=10;y-;}elsex++;|解：(l)n-ln-1n-1n+(n-l)+(n-2)+...+lJ"一21+(1+2)+(1+2+3)+...+(1+2+3+...+n)=七<=12=掙》)=宓2+，)=抄+迫乙1=1 乙i=l ,i=lZ/=1=n(n4-1)(2〃+1)+—n(n4-1)=-n(n+1)(2〃+3)12 4 12(6)n(7)[VnJ向下取整(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=log7n-2已知有實(shí)現(xiàn)同一功能的兩個(gè)算法，其時(shí)間復(fù)雜度分別為。(2")和。(儲(chǔ)°)，假設(shè)現(xiàn)實(shí)計(jì)算機(jī)可連續(xù)運(yùn)算的時(shí)間為1。7秒(100多天)，又每秒可執(zhí)行基本操作(根據(jù)這些操作來(lái)估算算法時(shí)間復(fù)雜度)ICT次。試問(wèn)在此條件下，這兩個(gè)算法可解問(wèn)題的規(guī)模(即n值的范圍)各為多少？哪個(gè)算法更適宜？請(qǐng)說(shuō)明理由。解：2"=1()12 n=40〃"=1012 n=16則對(duì)于同樣的循環(huán)次數(shù)n,在這個(gè)規(guī)模下，第二種算法所花費(fèi)的代價(jià)要大得多。故在這個(gè)規(guī)模下，第一種算法更適宜。設(shè)有以下三個(gè)函數(shù)：/(〃)=21〃4+〃2+1000,g(n)=15/?4+500/i3,/?(n)=500n35+wlog/7請(qǐng)判斷以下斷言正確與否：f(n堤O(píng)(g(n))h(n)是O(f(n))g(n)是O(h(n))h(n)是Odi3-5)h(n)是O(nlogn)解：⑴對(duì)(2)錯(cuò)(3)錯(cuò)(4)對(duì)(5)錯(cuò)試設(shè)定若干n值，比較兩函數(shù)〃2和50〃log2〃的增長(zhǎng)趨勢(shì)，并確定n在什么范圍內(nèi)，函數(shù)〃2的值大于50〃log2〃的值。解：〃2的增長(zhǎng)趨勢(shì)快。但在n較小的時(shí)候，50〃log2〃的值較大。當(dāng)n>438時(shí)，n2>50nlog2n判斷下列各對(duì)函數(shù)/(〃)和g(〃)，當(dāng)〃f-時(shí)，哪個(gè)函數(shù)增長(zhǎng)更快？/(〃)=10〃2+]n(〃!+io『)，g(〃)=2/+〃+7/(n)=(ln(n!)+5)2,g(n)=13n25/(n)= +J”，+1,g(〃)=(ln(〃!))2+〃/(〃)= +(2"J,g(〃)=〃("-)+〃5解：(l)g(n)快(2)g(n)快(3)f(n)快(4)f(n)快試用數(shù)學(xué)歸納法證明：=〃(〃+1]2〃+1)/6(n>0)/=1X.r'=(x"+1-l)/(x-l)(xw1,〃N0)i=0‘2"=2〃一1 (n>l)/=!Z⑵-1)=〃2 (n-0i=l試寫(xiě)一算法，自大至小依次輸出順序讀入的三個(gè)整數(shù)X,Y和Z的值解：intmax3(intx,inty,intz)(if(x>y)if(x>z)returnx;elsereturnz;elseif(y>z)returny;elsereturnz;已知k階斐波那契序列的定義為/?=0，力=0,…,A-2=o,a_.=i；f?=fn-\+fn-2+--+fn-k'〃=&?+1,…試編寫(xiě)求k階斐波那契序列的第m項(xiàng)值的函數(shù)算法，k和m均以值調(diào)用的形式在函數(shù)參數(shù)表中出現(xiàn)。解：k>o為階數(shù)，n為數(shù)列的第n項(xiàng)intFibonacci(intk,intn)(if(k<l)exit(OVERFLOW);int*p,x;p=newint[k+l];if(!p)exit(OVERFLOW);inti,j;for(i=0;i<k+l;i++){if(i<k-l)p[i]=O;elsep[i]=l;}for(i=k+1;ivn+1;i++){x=p[0];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)行田徑對(duì)抗賽，各院校的單項(xiàng)成績(jī)均已存入計(jì)算機(jī)，并構(gòu)成一張表，表中每一行的形式為項(xiàng)目名稱(chēng)性別校名成績(jī)得分編寫(xiě)算法，處理上述表格，以統(tǒng)計(jì)各院校的男、女總分和團(tuán)體總分，并輸出。解：typedefenum{A,B,C,D,E}SchoolName;typedefenum{Female,Male}SexType;typedefstruct{chare/ent[3];/傾目SexTypesex;SchoolNameschool;intscore;}Component;typedefstruct{intMaleSum;〃男團(tuán)總分intFemaleSum;〃女團(tuán)總分intTotalSum; 〃團(tuán)體總分}Sum;SumSumScore(SchoolNamesn,Componenta[],intn)(Sumtemp;temp.MaleSum=O;temp.FemaleSum=O;temp.TotalSum=0;inti;for(i=0;ivn;i++){if(a[i].school==sn){if(afi].sex==Male)temp.MaleSum+=a[i].score;if(a[i].sex==Female)temp.FemaleSum+=a[i].score;1}temp.TotalSum=temp.MaleSum+temp.FemaleSum;returntemp;)試編寫(xiě)算法，計(jì)算i!*2,的值并存入數(shù)組a[O..arrsize-l]的第i-1個(gè)分量中(i=l,2,...,n)o假設(shè)計(jì)算機(jī)中允許的整數(shù)最大值為maxint,則當(dāng)n>arrsize或?qū)δ硞€(gè)Ml4憶《〃)，使依?2?>maxint時(shí)，應(yīng)按出錯(cuò)處理。注意選擇你認(rèn)為較好的出錯(cuò)處理方法。解：#include<iostream.h>#include<stdlib.h>#defineMAXINT65535#defineArrSize100intfun(inti);intmain()(inti,k;intafArrSize];cout?"Enterk:n;cin?k;if(k>ArrSize-l)exit(O);for(i=0;i<=k;i++){if(i==O)a[i]=l;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]?n)return0;}試編寫(xiě)算法求一元多項(xiàng)式的值的值P.(x。),并確定算法中每1=0一語(yǔ)句的執(zhí)行次數(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[N];cout<〈”輸入變量的值X："；cin?x;coutvv”輸入多項(xiàng)式的階次n:n;cin?n;if(n>N-l)exit(O);cout<<"輸入多項(xiàng)式的系數(shù)a[O]-a[n]:";for(i=0;i<=n;i++)cin?a[i];cout?"Thepolynomailvalueisn?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ù)雜度為o(n)。第2章線(xiàn)性表描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)(第一個(gè)元素結(jié)點(diǎn)1解：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針。首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。頭結(jié)點(diǎn)是在首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)元素，其指針域指向首元結(jié)點(diǎn)，其作用主要是為了方便對(duì)鏈表的操作。它可以對(duì)空表、非空表以及首元結(jié)點(diǎn)的操作進(jìn)行統(tǒng)一處理。填空題。解：(1)在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表史二痂素，具體移動(dòng)的元素個(gè)數(shù)與元檢賽艇位置有關(guān)。[II頁(yè)序表中邏輯上相鄰的元素的物理位置線(xiàn)緊鄰。單鏈表中邏輯上相鄰的元素的物理位置丕逐緊鄰。(3)在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由真物踏點(diǎn)的綠(4)在卑鏈表中設(shè)急皓點(diǎn)的忤語(yǔ)是插入和刪除首元結(jié)點(diǎn)時(shí)不用進(jìn)行特殊

在什么情況下用順序表比鏈表好？解：當(dāng)線(xiàn)性表的數(shù)據(jù)元素在物理位置上是連續(xù)存儲(chǔ)的時(shí)候，用順序表比用鏈表好，其特點(diǎn)是可以進(jìn)行隨機(jī)存取。對(duì)以下單鏈表分別執(zhí)行下列各程序段，并畫(huà)出結(jié)果示意圖。L/TXLL⑸L/TXLL⑸畫(huà)出執(zhí)行下列各行語(yǔ)句后各指針及鏈表的示意圖。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+l,i*2);for(i=l;i<=3;i++)Del_LinkList(L,i);解：L. ?1 >3 .5 ?7A—————p 二L? ——?2 ——?4 >6 ——?7 ?8a—————丁一P已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語(yǔ)句序列。a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句序列是_41b.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是—711841.c.在表首插入S結(jié)點(diǎn)的語(yǔ)句序列是—512d.在表尾插入S結(jié)點(diǎn)的語(yǔ)句序列是 916P->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)b.⑺⑴)(8)(4)(1)c.(5)(12)d.⑼⑴(6)已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語(yǔ)句序列。TOC\o"1-5"\h\za.刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列是 .b.刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是 .c.刪除P結(jié)點(diǎn)的語(yǔ)句序列是 .d.刪除首元結(jié)點(diǎn)的語(yǔ)句序列是 。e.刪除尾元結(jié)點(diǎn)的語(yǔ)句序列是 .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)0)(14)b.(10)(12)(8)(3)(14)c.(10)(12)(7)(3)(14)d.(⑵(11)⑶(14)e.(9)(11)(3)(14)已知P結(jié)點(diǎn)是某雙向鏈表的中間結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語(yǔ)句序列。TOC\o"1-5"\h\za.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句序列是 。b.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是 。c.冊(cè)!］除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列是 .d.刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是 。e.刪除P結(jié)點(diǎn)的語(yǔ)句序列是 0P->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);(18)free(Q);解：a.(7)(3)(6)(12)b.(8)(4)(5)(13)c.(15)(i)(ll)(18)d.(16)(2)(10)(18)e.(14)(9)(17)簡(jiǎn)述以下算法的功能。StatusA(LinkedListL){//L是無(wú)表頭結(jié)點(diǎn)的單鏈表Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;returnOK;)voidBB(LNodeLNode*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的長(zhǎng)度不小于2,將L的首元結(jié)點(diǎn)變成尾元結(jié)點(diǎn)。(2)將單循環(huán)鏈表拆成兩個(gè)單循環(huán)鏈表。指出以下算法中的錯(cuò)誤和低效之處，并將它改寫(xiě)為一個(gè)既正確又高效的算法。StatusDeleteK(SqList&a,inti,intk)(〃本過(guò)程從順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表a中刪除第i個(gè)元素起的k個(gè)元素if(i<lllk<Olli+k>a.length)returnINFEASIBLE;//參數(shù)不合法else{fbr(count=1;count<k;count++){〃刪除第一個(gè)元素for(j=a.length;j>=i+l;j—)a.elem[j-i]=a.elem|j];a.length—;)returnOK;)解：StatusDeIeteK(SqList&a,inti,intk)〃從順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表a中刪除第i個(gè)元素起的k個(gè)元素〃注意i的編號(hào)從0開(kāi)始intj;if(i<Olli>a.length-1llk<Ollk>a.length-i)returnINFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j4-i+k];a.length=a.length-k;returnOK;)設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫(xiě)一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。解：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-1];va.elem[i]=x;va.length++;returnOK;)設(shè)A=(q,…,％,)和8=(仿,…e)均為順序表，和*分別為A和8中除去最大共同前綴后的子表。若4'="=空表，則A=8；若4=空表，而"#空表,或者兩者均不為空表，且A的首元小于B'的首元，則A<B；否則A>8。試寫(xiě)一個(gè)比較A,8大小的算法。解：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=-1;if(A.length==B.length)j=0;returnj;)試寫(xiě)一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線(xiàn)性表操作Locate(L,x);解：intLocateElem_L(LinkList&L,ElemTypex)(inti=0;LinkListp=L;while(p&&p->data!=x){p=p->next;i++；)if(!p)return0;elsereturni;}試寫(xiě)一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線(xiàn)性表操作Length(L)o解：〃返回單鏈表的長(zhǎng)度intListLength_L(LinkList&L)(inti=0;LinkListp=L;if(p)p=p-next;while(p){p=p->next;i++；}returni;}已知指針ha和hb分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，并且已知兩個(gè)鏈表的長(zhǎng)度分別為m和no試寫(xiě)一算法將這兩個(gè)鏈表連接在一起，假設(shè)指針he指向連接后的鏈表的頭結(jié)點(diǎn),并要求算法以盡可能短的時(shí)間完成連接運(yùn)算。請(qǐng)分析你的算法的時(shí)間復(fù)雜度。解：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;)}已知指針la和lb分別指向兩個(gè)無(wú)頭結(jié)點(diǎn)單鏈表中的首元結(jié)點(diǎn)。下列算法是從表la中刪除自第i個(gè)元素起共len個(gè)元素后，將它們插入到表1b中第i個(gè)元素之前。試問(wèn)此算法是否正確？若有錯(cuò)，請(qǐng)改正之。StatusDeleteAndInsertSub(LinkedListla,LinkedListlb,inti,intj,intlen)(if(i<0llj<0lllen<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;解：StatusDeleteAndInsertSub(LinkList&la,LinkList&lb,inti,intj,intlen)(LinkListp,q,s,prev=NULL;intk=l;if(i<0llj<0lllen<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-1個(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中q->next=lb;lb=p;)else{s=lb;k=l;while(s&&k<j-1){s=s->next;k++;)if(!s)returnINFEASIBLE;q->next=s->next;s->next=p;//完成插入returnOK;試寫(xiě)一算法，在無(wú)頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)線(xiàn)性表操作Insert(L,i,b),并和在帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比較。試寫(xiě)一算法，實(shí)現(xiàn)線(xiàn)性表操作Delete(L,i),并和在帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比較。已知線(xiàn)性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫(xiě)一高效的算法，刪除表中所有值大于mink且小于maxk的元素(若表中存在這樣的元素)，同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時(shí)間復(fù)雜度(注意，mink和maxk是給定的兩個(gè)參變量，它們的值可以和表中的元素相同，也可以不同1解：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.19題條件，試寫(xiě)一高效的算法，刪除表中所有值相同的多余元素(使得操作后的線(xiàn)性表中所有元素的值均不相同），同時(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);)})試寫(xiě)一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲(chǔ)空間將線(xiàn)性表(%,???,〃〃)逆置為解：//順序表的逆置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-1-i]=x;}」returnOK;試寫(xiě)一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。解：//帶頭結(jié)點(diǎn)的單鏈表的逆置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;)設(shè)線(xiàn)性表A=伍,,B=(伉也，…也)試寫(xiě)一個(gè)按下列規(guī)則合并A,B為線(xiàn)性表C的算法，即使得C=(ai,bi,->-,am,bm,bm+l,---,bn)當(dāng)mW〃時(shí)；C=(q,4，…,?！币?%+1，當(dāng)m>〃時(shí)。線(xiàn)性表A,B和C均以單鏈表作存儲(chǔ)結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：?jiǎn)捂湵淼拈L(zhǎng)度值m和n均未顯式存儲(chǔ)。解：//將合并后的結(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;)假設(shè)有兩個(gè)按元素值遞增有序排列的線(xiàn)性表A和B,均以單鏈表作存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫(xiě)算法將A表和B表歸并成一個(gè)按元素值遞減有序(即非遞增有序，允許表中含有值相同的元素)排列的線(xiàn)性表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;陽(yáng)各當(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;)假設(shè)以?xún)蓚€(gè)元素依值遞增有序排列的線(xiàn)性表A和B分別表示兩個(gè)集合(即同一表中的元素值各不相同)，現(xiàn)要求另辟空間構(gòu)成一個(gè)線(xiàn)性表C,其元素為A和B中元素的交集，且表C中的元素有依值遞增有序排列。試對(duì)順序表編寫(xiě)求C的算法。解：//將A、B求交后的結(jié)果放在C表中StatusListCross_Sq(SqList&A,SqList&B,SqList&C)(inti=O,j=O,k=O;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.25題。試對(duì)單鏈表編寫(xiě)求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;)對(duì)2.25題的條件作以下兩點(diǎn)修改，對(duì)順序表重新編寫(xiě)求得表C的算法。⑴假設(shè)在同一表(A或B)中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；(2)利用A表空間存放表C。解：//A、B求交，然后刪除相同元素，將結(jié)果放在C表中StatusListCrossDelSame_Sq(SqList&A,SqList&B,SqList&C)(inti=O,j=O,k=O;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){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;}〃A、B求交，然后刪除相同元素,將結(jié)果放在A表中StatusListCrossDelSame_Sq(SqList&A,SqList&B)(inti=O,j=O,k=O;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==O){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;}對(duì)2.25題的條件作以下兩點(diǎn)修改，對(duì)單鏈表重新編寫(xiě)求得表C的算法。(1)假設(shè)在同一表(A或B)中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；(2)利用原表(A表或B表)中的結(jié)點(diǎn)構(gòu)成表C,并釋放A表中的無(wú)用結(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;)已知A,B和C為三個(gè)遞增有序的線(xiàn)性表，現(xiàn)要求對(duì)A表作如下操作：刪去那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素。試對(duì)順序表編寫(xiě)實(shí)現(xiàn)上述操作的算法，并分析你的算法的時(shí)間復(fù)雜度(注意：題中沒(méi)有特別指明同一表中的元素值各不相同1解：〃在A中刪除既在B中出現(xiàn)又在C中出現(xiàn)的元素，結(jié)果放在D中StatusListUnion_Sq(SqList&D,SqList&A,SqList&B,SqList&C)SqListTemp;InitList_Sq(Temp);ListCross_L(B,C,Temp);ListMinus_L(A,Temp,D);}要求同2.29題。試對(duì)單鏈表編寫(xiě)算法，請(qǐng)釋放A表中的無(wú)用結(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;)假設(shè)某個(gè)單向循環(huán)鏈表的長(zhǎng)度大于1,且表中既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。已知s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫(xiě)算法在鏈表中刪除指針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)retumERROR;q=S;p=S->next;while(p->next!=S){q二p；p=p->next;}q->next=p->next;free(p);returnOK;)已知有一個(gè)單向循環(huán)鏈表，其每個(gè)結(jié)點(diǎn)中含三個(gè)域：pre,data和next,其中data為數(shù)據(jù)域，next為指向后繼結(jié)點(diǎn)的指針域，pre也為指針域，但它的值為空，試編寫(xiě)算法將此單向循環(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);L->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;)已知由一個(gè)線(xiàn)性鏈表表示的線(xiàn)性表中含有三類(lèi)字符的數(shù)據(jù)元素(如：字母字符、數(shù)字字符和其他字符)，試編寫(xiě)算法將該線(xiàn)性表分割為三個(gè)循環(huán)鏈表，其中每個(gè)循環(huán)鏈表表示的線(xiàn)性表中均只含一類(lèi)字符。解：//將單鏈表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=pt1->next;ptl->next=q;ptl=ptl->next;1elseif((p?>data>='A'&&p->data<=,Z,)II(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題中，“異或指針雙向鏈表”類(lèi)型XorLinkedList和指針異或函數(shù)XorP定義為：typedefstructXorNode{chardata;structXorNode*LRPtr;}XorNode,*XorPointer;typedestruct{ 〃無(wú)頭結(jié)點(diǎn)的異或指針雙向鏈表XorPointerLeft,Right; 〃分別指向鏈表的左側(cè)和右端}XorLinkedList;XorPointerXorP(XorPointerp,XorPointerq);//指針異或函數(shù)XorP返回指針p和q的異或值假設(shè)在算法描述語(yǔ)言中引入指針的二元運(yùn)算“異或”，若a和b為指針，則aeb的運(yùn)算結(jié)果仍為原指針類(lèi)型，且a?(a?b)=(a?a)?b=b(a?b)?b=a?(b?b)=a則可利用一個(gè)指針域來(lái)實(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)從左向右或從右向左遍歷此雙向鏈表的操作。試寫(xiě)一算法按任一方向依次輸出鏈表中各元素的值。解：StatusTraversingLinkList(XorLinkedList&L,chard)(XorPointerp,left,right;if(d='l'lld=='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.34題所述的存儲(chǔ)結(jié)構(gòu)，寫(xiě)出在第i個(gè)結(jié)點(diǎn)之前插入一個(gè)結(jié)點(diǎn)的算法。采用2.34題所述的存儲(chǔ)結(jié)構(gòu)，寫(xiě)出刪除第i個(gè)結(jié)點(diǎn)的算法。設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線(xiàn)性表乙=伍,出，一，%)。試寫(xiě)一時(shí)間復(fù)雜度O(n)的算法，將L改造為L(zhǎng)=(q,生，…’〃4，。2)。解：//將雙向鏈表L=(al,a2,...,an)改造為(al,a3,…,an,...,a2)StatusListChange_DuL(DuLinkList&L)(inti;DuLinkListp,q,r;p=L->next;r=L->pre;i=l；while(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;1elsep=p->next;i++；returnOK;設(shè)有一個(gè)雙向循環(huán)鏈表，每個(gè)結(jié)點(diǎn)中除有pre,data和next三個(gè)域外，還增設(shè)了一個(gè)訪問(wèn)頻度域freq。在鏈表被起用之前，頻度域freq的值均初始化為零，而每當(dāng)對(duì)鏈表進(jìn)行一次Located,x)的操作后，被訪問(wèn)的結(jié)點(diǎn)(即元素值等于x的結(jié)點(diǎn))中的頻度域freq的值便增1，同時(shí)調(diào)整鏈表中結(jié)點(diǎn)之間的次序，使其按訪問(wèn)頻度非遞增的次序順序排列，以便始終保持被頻繁訪問(wèn)的結(jié)點(diǎn)總是靠近表頭結(jié)點(diǎn)。試編寫(xiě)符合上述要求的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)式采用的順序存儲(chǔ)結(jié)構(gòu)SqPoly定義為typedefstruct{intcoef;intexp;}PolyTerm;typedefstruct{ 〃多項(xiàng)式的順序存儲(chǔ)結(jié)構(gòu)PolyTerm*data;intlast;}SqPoly;已知稀疏多項(xiàng)式^,(x)=clx<，1+c2xe-+--+cmxe-,其中n=em>em_}>->ex>0,q￥0(i=1,2,…,m),m>\,試采用存儲(chǔ)量同多項(xiàng)式項(xiàng)數(shù)m成正比的順序存儲(chǔ)結(jié)構(gòu)，編寫(xiě)求匕(%)的算法(/為給定值)，并分析你的算法的時(shí)間復(fù)雜度。解：typedefstruct{intcoef;intexp;}PolyTerm;typedefstruct{PolyTerm*data;intlast;}SqPoly;//建立一個(gè)多項(xiàng)式StatusPolyInit(SqPoly&L){inti;PolyTerm*p;coutvv”請(qǐng)輸入多項(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<<”請(qǐng)輸入系數(shù):“；cin?p->coef;cout?"請(qǐng)輸入指數(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=1;j<p->exp;j++)x=x*xO;Pn=Pn+p->coef*x;}returnPn;}采用2.39題給定的條件和存儲(chǔ)結(jié)構(gòu)，編寫(xiě)求P(x)=%(x)-%(x)的算法,將結(jié)果多項(xiàng)式存放在新辟的空間中，并分析你的算法的時(shí)間復(fù)雜度。解：//求兩多項(xiàng)式的差StatusPolyMinus(SqPoly&L,SqPoly&Ll,SqPoly&L2){PolyTerm*p,*pl,*p2;p=L.data;pl=Ll.data;p2=L2.data;inti=O,j=O,k=O;while(i<L1.last&&j<L2.1ast){if(p1->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(p1->coef!=p2->coef){p->coef=(p1->coef)-(p2->coeD；p->exp=p1->exp;p++; 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.1ast)while(j<L2.1ast){p->coef=-p2->coef;p->exp=p2->exp;p++; k++;p2++；j++；)L.last=k;returnOK;)在2.41至2.42題中，稀疏多項(xiàng)式采用的循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)LinkedPoly定義typedefstructPolyNode{PolyTermdata;structPolyNode*next;}PolyNode,*PolyLink;typedefPolyLinkLinkedPoly;試以循環(huán)鏈表作稀疏多項(xiàng)式的存儲(chǔ)結(jié)構(gòu)，編寫(xiě)求其導(dǎo)函數(shù)的方法，要求利用原多項(xiàng)式中的結(jié)點(diǎn)空間存放其導(dǎo)函數(shù)多項(xiàng)式，同時(shí)釋放所有無(wú)用結(jié)點(diǎn)。解：StatusPolyDifferential(LinkedPoly&L)(LinkedPolyp,q,pt;q=L;p=L->next;while(p!=L){if(p->data.exp==O){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;}試編寫(xiě)算法，將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式，使這兩個(gè)多項(xiàng)式中各自?xún)H含奇次項(xiàng)或偶次項(xiàng)，并要求利用原鏈表中的結(jié)點(diǎn)空間構(gòu)成這兩個(gè)鏈表。解：//將單鏈表L劃分成2個(gè)單循環(huán)鏈表StatusListDivideInto2CL(LinkedPoIy&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=p1->next;pl->next=pt;pl=pl->next;)else{q=p;p=p->next;))returnOK;)第3章棧和隊(duì)列若按教科書(shū)3.1.1節(jié)中圖3.1(b)所示鐵道進(jìn)行車(chē)廂調(diào)度(注意：兩側(cè)鐵道均為單向行駛道)，則請(qǐng)回答：(1)如果進(jìn)站的車(chē)廂序列為123,則可能得到的出站車(chē)廂序列是什么？(2)如果進(jìn)站的車(chē)廂序列為123456,則能否得到435612和135426的出站序列，并請(qǐng)說(shuō)明為什么不能得到或者如何得到(即寫(xiě)出以S表示進(jìn)棧和以牙表示出棧的棧操作序列I解：(1)123231321213132(2)可以得到135426的出站序列但不能得到435612的出站序列。因?yàn)?356出站說(shuō)明12已經(jīng)在棧中，1不可能先于2出棧。簡(jiǎn)述棧和線(xiàn)性表的差別。解：線(xiàn)性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。棧是限定僅在表尾進(jìn)行插入或刪除操作的線(xiàn)性表。寫(xiě)出下列程序段的輸出結(jié)果(棧的元素類(lèi)型SElemType為charXvoidmain(){StackS;charx,y;InitStack(S);x=，c';y=Push(S,x);Push(SJa'); Push(S,y);Pop(S,x);Push(S,Push(S9x);Pop(S,x);Push(SJs');while(!StackEmpty(S)){Pop(S,y);printf(y);}printf(x);}解：stack簡(jiǎn)述以下算法的功能(棧的元素類(lèi)型SElemType為int工statusalgo1(StackS){inti,n,A[255];n=0;while(!StackEmpty(S)){n++;Pop-]);}for(i=l;i<=n;i++)Push(S,A[i]);)statusalgo2(StackS9inte){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,將其從棧中清除假設(shè)以S和X分別表示入棧和出棧的操作，則初態(tài)和終態(tài)均為空棧的入棧和出棧的操作序列可以表示為僅由S和X組成的序列。稱(chēng)可以操作的序列為合法序列（例如，SXSX為合法序列，SXXS為非法序列I試給出區(qū)分給定序列為合法序列或非法序列的一般準(zhǔn)則，并證明：兩個(gè)不同的合法（棧操作）序列（對(duì)同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實(shí)體，而不是值）序列。解：任何前n個(gè)序列中S的個(gè)數(shù)一定大于X的個(gè)數(shù)。設(shè)兩個(gè)合法序列為：T1=S X S T2=S X X 假定前n個(gè)操作都相同，從第n+1個(gè)操作開(kāi)始，為序列不同的起始操作點(diǎn)。由于前n個(gè)操作相同，故此時(shí)兩個(gè)棧（不妨為棧A、B）的存儲(chǔ)情況完全相同，假設(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后b。由于T1的輸出為……ba 而T2的輸出順序?yàn)椤璦b 說(shuō)明兩個(gè)不同的合法棧操作序列的輸出元素的序列一定不同。試證明：若借助棧由輸入序列12...n得到的輸出序列為p/2…凡（它是輸入序列的一個(gè)排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j<k使Pj<PSPi。解：這個(gè)問(wèn)題和3.1題比較相似。因?yàn)檩斎胄蛄惺菑男〉酱笈帕械?，所以若Pj<Pk<Pi>則可以理解為通過(guò)輸入序列PjP*P,.可以得到輸出序列PjPjpk,顯然通過(guò)序列123是無(wú)法得到312的，參見(jiàn)3」題。所以不可能存在著i<j<k使Pj<Pk<Pi?按照四則運(yùn)算加、減、乘、除和鬲運(yùn)算價(jià)）優(yōu)先關(guān)系的慣例，并仿照教科書(shū)節(jié)例3-2的格式，畫(huà)出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程：A-BxC/D+EtF解：BC=GG/D=HA-H=IEAF=JI+J=K步驟OPTR棧OPND棧輸入字符主要操作1#A-B*C/D+EAF#PUSH(OPND,A)2#A-B*C/D+EAF#PUSH(OPTR,-)3#-AB*C/D+EAF#PUSH(OPND,B)4#-AB1C/D+EAF#PUSH(OPTR,*)5ABC/D+EAF#PUSH(OPND,C)6#-*ABC/D+EAF#Operate(B,*,C)7#-AG/D+EAF#PUSH(OPTR,/)8#-/AGD+EAF#PUSH(OPND,D)9#-/AGD+EAF#Operate(G,/,D)10#-AH+EAF#Operate(A,-,H)11#I+EAF#PUSH(OPTR,+)12#+IEAF#PUSH(OPND,E)13#+IE)F#PUSH(OPTR,A)14#+AIEF#PUSH(OPND,F)15#+AIEF#Operate(E,A,F)16#+IJ#Operate(I,+,J)17#K#RETURN3.8試推導(dǎo)求解n階梵塔問(wèn)題至少要執(zhí)行的move操作的次數(shù)。解：2n-1試將下列遞推過(guò)程改寫(xiě)為遞歸過(guò)程。voidditui(intn){inti;=n;while(i>l)cout?i—;解：voidditui(intj)(if(j>D{cout?j;ditui(j-l);}return;}.10試將下列遞歸過(guò)程改寫(xiě)為非遞歸過(guò)程。voidtest(int&sum){intx;cin?x;if(x==0)sum=0;else{test(sum);sum+=x;)cout?sum;}解：voidtest(int&sum)(Stacks;InitStack(s);intx;do{cin?x;Push(s,x);}while(x>0);while(!StackEmpty(s)){Pop(s,x);sum+=x;cout?sum?endl;DestoryStack(s);簡(jiǎn)述隊(duì)列和堆棧這兩種數(shù)據(jù)類(lèi)型的相同點(diǎn)和差異處。解：棧是一種運(yùn)算受限的線(xiàn)性表，其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。隊(duì)列也是一種運(yùn)算受限的線(xiàn)性表，其限制是僅允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。寫(xiě)出以下程序段的輸出結(jié)果(隊(duì)列中的元素類(lèi)型QEIemType為charIvoidmain(){QueueQ;InitQueue(Q);charx=6e\y=’c';EnQueue(Q,，1T);EnQueue(Q,T);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,，')；While(!QueueEmpty(Q)){DeQueue(Q,y);cout?y;}cout?x;}解：char簡(jiǎn)述以下算法的功能(棧和隊(duì)列的元素類(lèi)型均為intXvoidalgo3(Queue&Q)(StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);}while(!StackEmpty(S))Pop(S,d);EnQueue(Q,d);))解：隊(duì)列逆置若以1234作為雙端隊(duì)列的輸入序列，試分別求出滿(mǎn)足以下條件的輸出序列：(1)能由輸入受限的雙端隊(duì)列得到，但不能由輸出受限的雙端隊(duì)列得到的輸出序列。(2)能由輸出受限的雙端隊(duì)列得到，但不能由輸入受限的雙端隊(duì)列得到的輸出序列。(3)既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列。假設(shè)以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)一個(gè)雙向棧，即在一維數(shù)組的存儲(chǔ)空間中存在著兩個(gè)棧，它們的棧底分別設(shè)在數(shù)組的兩個(gè)端點(diǎn)。試編寫(xiě)實(shí)現(xiàn)這個(gè)雙向棧tws的三個(gè)操作：初始化inistack(tws)、入棧push(tws,i,x)和出棧pop(tws,i)的算法，其中i為0或1,用以分別指示設(shè)在數(shù)組兩端的兩個(gè)棧，并討論按過(guò)程(正/誤狀態(tài)變量可設(shè)為變參)或函數(shù)設(shè)計(jì)這些操作算法各有什么有缺點(diǎn)。解：classDStack{ElemType*top[2];ElemType*p;intstacksize;intdi;public:DStack(intm)p=newElemType[m];if(!p)exit(OVERFLOW);top[0]=p+m/2;top[l]=top[0];stacksize=m;)-DStack(){deletep;}voidPush(inti,ElemTypex)(di=i;if(di==O){if(top[0]>=p)*top[0]—=x;elsecerr?°Stackoverflow!0;)else{if(top[1]<p+stacksize-1)*++top[l]=x;elsecerr?uStackoverflow!0;)}ElemTypePop(inti)(di=i;if(di==O){if(top[0]<top[l])return*++top[0];elsecerr?nStackempty!M;}else{if(top[l]>top[0])return*top[l]—;elsecerr?nStackempty!";}returnOK;));//鏈棧的數(shù)據(jù)結(jié)構(gòu)及方法的定義typedefstructNodeType{ElemTypedata;NodeType*next;}NodeType,*LinkType;typedefstruct{LinkTypetop;intsize;}Stack;voidInitStack(Stack&s)s.top=NULL;s.size=O;voidDestroyStack(Stack&s)(LinkTypep;while(s.top){p=s.top;s.top=p->next;deletep;s.size—;})voidCIearStack(Stack&s)(LinkTypep;while(s.top){p=s.top;s.top=p->next;