數(shù)據(jù)結(jié)構(gòu)實(shí)用教程課后答案

1、第一題一一、單選題1.一個(gè)數(shù)組ai與( A )的表示等價(jià)。A *(a+i) B a+i C *a+i D &a+i2.對(duì)于兩個(gè)函數(shù)，若函數(shù)名相同，但只是( C) 不同則不是重載函數(shù)。A 參數(shù)類型 B 參數(shù)個(gè)數(shù) C 函數(shù)類型3.若需要利用形參直接實(shí)參，則應(yīng)把形參變量說(shuō)明為 (B) 參數(shù)。A 指針 BC 值4.下面程序段的復(fù)雜度為 (C )。for(int i=0;i<m;i+)for(int j=0;j<n;j+) aij=i*j;A O(m2) B O(n2) C O(m*n) D O(m+n)5.執(zhí)行下面程序段時(shí)，執(zhí)行S語(yǔ)句的次數(shù)為 (D )。for(int i=1;i&

2、lt;=n;i+)for(int j=1; j<=i;j+) S;A n2 B n2/2+1) D n(n+1)/26.下面算法的時(shí)間復(fù)雜度為( B) 。int f(unsigned int n)if(n=0|n=1) return 1; Else return n*f(n-1);A O(1) B O(n) C O(n2)D O(n!)二、填空題1.數(shù)據(jù)的邏輯結(jié)構(gòu)被除數(shù)分為 集合結(jié)構(gòu) 、 線性結(jié)構(gòu) 、結(jié)構(gòu) 和 圖形結(jié)構(gòu) 四種。2.數(shù)據(jù)的結(jié)構(gòu)被分為 順序結(jié)構(gòu) 、結(jié)構(gòu) 、 索引結(jié)構(gòu) 和 散列結(jié)構(gòu) 四種。3.性結(jié)構(gòu)、結(jié)構(gòu)和圖形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點(diǎn)之間分別著 1對(duì)1 、 1對(duì)N 和 M對(duì)N 的

3、。4.一種抽象數(shù)據(jù)類型數(shù)據(jù) 和 操作 兩個(gè)部分。5.當(dāng)一個(gè)形參類型的長(zhǎng)度較大時(shí)，應(yīng)最好說(shuō)明為，以節(jié)省參數(shù)值的傳輸時(shí)間和參數(shù)的空間。6.當(dāng)需要用一個(gè)形參對(duì)應(yīng)的實(shí)參時(shí)，則該形參應(yīng)說(shuō)明為。7.在函數(shù)中對(duì)函數(shù)的內(nèi)部，形參的修改就是對(duì)相應(yīng) 實(shí)參 的修改，對(duì) 值(或賦值)形參的修改只局限在該反映到對(duì)應(yīng)的實(shí)參上。8.當(dāng)需要進(jìn)行標(biāo)準(zhǔn)I/O操作時(shí)，則應(yīng)在程序文件中包含 iostream.h 頭文件，當(dāng)需要進(jìn)行文件I/O操作時(shí)， 則應(yīng)在程序文件中包含 fstream.h 頭文件。9.在包含有 stdlib.h 頭文件的程序文件中，使用 rand()%21 能夠產(chǎn)生0-20之間的一個(gè)隨機(jī)數(shù)。10.一個(gè)r理論上占有的

4、空間的大小等于所有域的 長(zhǎng)度之和 ，實(shí)際上占有的空間的大小即長(zhǎng)度為 sizeof(r) 。11.一個(gè)數(shù)組a所占有的空間的大小即數(shù)組長(zhǎng)度為 sizeof(a) ，下標(biāo)為i的ai的地址為 a+1 ，或者為 (char*)a+i*sizeof(ai) 。12.函數(shù)重載要求 參數(shù)類型 、 參數(shù)個(gè)數(shù) 或 排列順序 有所不同。13.對(duì)于雙目操作符，其重載函數(shù)帶有 2 個(gè)參數(shù)，其中至少有一個(gè)為 用戶自定義的類型。14.若對(duì)象ra和rb中至少有一個(gè)屬于用戶定義的類型，則執(zhí)行ra=rb時(shí)，需要調(diào)用 等于號(hào)(=) 重載函數(shù)，該函數(shù)第一個(gè)參數(shù)應(yīng)與 ra ，的類型相同，第二個(gè)參數(shù)應(yīng)與rb 的類型相同。15.從一維數(shù)組

5、an中順序查找出一個(gè)最大值元素的時(shí)間復(fù)雜度為 O(n) ，輸出一個(gè)二維數(shù)組bmn中所有元素值的時(shí)間復(fù)雜度為 O(m*n) 。16.在下面程序段中，s=s+p語(yǔ)句的執(zhí)行次數(shù)為 n ，p*=j語(yǔ)句的執(zhí)行次數(shù)為n(n+1)/2，該程序段的時(shí)間復(fù)雜度為 O(n2) 。int i=0,s=0; while(+i<=n) int p=1;for(int j=1;j<=i;j+) P*=j; s=s+p;17.一個(gè)算法的時(shí)間復(fù)雜度為(3n2+2nlog2n+4n-7)/(5n),其數(shù)量級(jí)表示為 O(n) 。18.從一個(gè)數(shù)組a7中順序查找元素時(shí)，假定查找第一個(gè)元素a0的概率為1/3，查找第二個(gè)元素

6、a1的概率為1/4，查找其余元素的概率均相同，則在查找較次數(shù)為 35/12 。時(shí)同元素的平均比三、普通題 1.有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，試畫出它們分別對(duì)應(yīng)的圖形表示（當(dāng)出現(xiàn)多個(gè)時(shí)，對(duì)每個(gè)畫出相應(yīng)的結(jié)構(gòu)圖），并指出它們分別屬于何種結(jié)構(gòu)。 A=(K,R)其中K=a1,a2,a3.,an R= B=(K,R)其中K=a,b,c,d,e,f,g,h R=rr=<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h> C=(K,R)其中K=a,b,c,d,f,g,h R=rr=<d

7、,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,<e,f> D=(K,R)其中K=1,2,3,4,5,6 R=rr=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6) E=(K,R)其中K=48,25,64,57,82,36,75,43 R=r1,r2,r3r1=<48,25>,<25,64>,<64,57>,<57,82>,<82,36>,<36,75>,<75,43>

8、 r2=<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>,<36,43> r3=<25,36>,<36,43>,<43,48>,<48,57>,<57,64>,<64,75>,<75,82>解：是集合結(jié)構(gòu)；是線性結(jié)構(gòu)；是結(jié)構(gòu)；散列結(jié)構(gòu)。只作為參考。2.設(shè)計(jì)二次多項(xiàng)式ax2+bx+c的一種抽象數(shù)據(jù)類型，假定起名為QIAdratic,該類型的數(shù)據(jù)部分分為三個(gè)系數(shù)項(xiàng)a、b和c，操作部分為：

9、(請(qǐng)寫出下面每一個(gè) 操作的具體實(shí)現(xiàn))。 初始化數(shù)據(jù)成員ab和c(假定用員的默認(rèn)值為0。類型Quadratie定義成員)，每個(gè)數(shù)據(jù)成Quadratic InitQuadratic(float aa=0,float bb=0,float cc=0); 解：Quadratic InitQuadratic(float aa,float bb,float cc)Quadratic q; q.a=aa; q.b=bb; q.c=cc; return q; 做兩個(gè)多項(xiàng)式加法,即使對(duì)應(yīng)的系數(shù)相加,并返回相加的結(jié)果。Quadratic Add(Quadratic q1,Quadratic q2);解：Quadr

10、atic Add(Quadratic q1,Quadratic q2);Quadratic q; q.a=q1.a+q2.a; q.b=q1.b+q2.b; q.c=q1.c+q2.c;return q; 根據(jù)給定x的值計(jì)算多項(xiàng)式的值。float Eval(Quadratic q,float x);解：float Eval(Quadratic q,float x)return(q.a*x*x+q.b*x+q.c); 計(jì)算方程ax2+bx+c=0的兩個(gè)實(shí)數(shù)根，對(duì)于有實(shí)根、無(wú)實(shí)根和不是實(shí)根方程(即a=0)這三種情況要返回不同的整數(shù)值，以便于工作調(diào)用函數(shù)做不同的處理。 int Root(Quadra

11、tic q,float& r1,float& r2);解：int Root(Quadratic q,float& r1,float& r2)if(q.a=0)return -1;float x=q.b*q.b-4*q.a*q.c; if(x>=0)r1=(float)(-q.b+sqrt(x)/(2*q.a);r2=(float)(-q.b-sqrt(x)/(2*q.a); return 1;elsereturn 0; 按照ax*2+bx+c的格式(x2用x*2表示)輸出二次多項(xiàng)式，在輸出時(shí)要注意去掉系數(shù)為0的項(xiàng)，并且當(dāng)b和c的值為負(fù)時(shí)，其前不能出現(xiàn)加號(hào)。

12、void Print(Quadratic q) 解：void Print(Quadratic q)if(q.a) cout<<q.a<<"x*2" if(q.b)if(q.b>0)cout<<"+"<<q.b<<"x" elsecout<<q.b<<"x" if(q.c)if(q.c>0) cout<<"+"<<q.c; elsecout<<q.c; cout<

13、;<end1;3.用c+函數(shù)描述下列每一個(gè)算法，并分別求出它們的時(shí)間復(fù)雜度。 比較同一簡(jiǎn)單類型的兩個(gè)數(shù)據(jù)x1和x2的大小，對(duì)于x1>x2,x1=x2和x1<x2這三種不同情況分別返回'>''='和'<'字符。假定簡(jiǎn)單類型用SimpleType表示，它可通過(guò)typedef語(yǔ)句定義為任一簡(jiǎn)單類型。解：char compare(SimpleType x1,SimpleType x2)if(x1>x2) return'>'else if(x1=x2) return '=' else

14、 return'<'其時(shí)間復(fù)雜度為O(1) 將一個(gè)字符串中的所有字符按相反方的次序重新放置。解：void Reverse(char*p)int n=strlen(p);for(int i=0;i<n/2;i+) char ch;ch=pi pi=pn-i-1;pn-i-1=ch;其時(shí)間復(fù)雜度為O(n) 求一維double型數(shù)組an中的所有元解：double product(double a,int n)double p=1;for(int i=0;i<n;i+) p*=ai;return p;其時(shí)間復(fù)雜度為O(n)乘積。 計(jì)算ni=0xi/i+1的值。解：do

15、uble Accumulate(double x,int n)double p=1,s=1; for(int i=1;i<=n;i+) p*=x;s+=p/(i+1);return s;其時(shí)間復(fù)雜度為O(n) 假定一維數(shù)組an中的每個(gè)元素值均在0，200區(qū)間內(nèi)，分別統(tǒng)計(jì)出落在0，20),20,50),50,80),80,130),130,200等各區(qū)間的元素個(gè)數(shù)。解：int Count(int a,int n,int c5)/用數(shù)組c5保存統(tǒng)計(jì)結(jié)果int d5=20,50,80,130,201;/用來(lái)保存各統(tǒng)計(jì)區(qū)間的上限int i,j; for(i=0;i<5;i+)ci=0;/給

16、數(shù)組c5中的每個(gè)元素賦初值0 for(i=0;i<n;i+)if(ai<0|ai>200)return 0;/返回?cái)?shù)值0表示數(shù)組中數(shù)據(jù)有錯(cuò)，統(tǒng)計(jì)失敗for(j=0;j<5;j+)/查找ai所在區(qū)間if(ai<dj) break; cj+;/使統(tǒng)計(jì)相應(yīng)區(qū)間的元素增1return 1;/返回?cái)?shù)值1表示統(tǒng)計(jì)其時(shí)間復(fù)雜度為O(n) 從二維整型數(shù)組amn中查找出最大元素所在的行、列下標(biāo)。解：void find(int aMN,int m,int n,int&Lin,int&Col)/M和N為全局，應(yīng)滿足M>=n和N>=n的條件，Lin和Col為/

17、形參，它是對(duì)應(yīng)實(shí)參的別名，其值由實(shí)參帶回Lin=0;Col=0;for(int i=0;i<m;i+) for(int j=0;j<n;j+)if(aij>aLinCol)Lin=i;Col=j;其時(shí)間復(fù)雜度為O(m*n)4.指出下列各算法的功能并求出其時(shí)間復(fù)雜度。 int prime(int n)int i=2;int x=(int)sqrt(n); while(i<=x) if(n%i=0)break; i+;if(i>x) return 1; else return 0;解：n是否是一個(gè)O(n1/2)。，若是則返回?cái)?shù)值1，否則返回0。該算法的時(shí)間復(fù)雜度為 i

18、nt sum1(int n)int p=1,s=0;for(int i=1;i<=n;i+) p*=i;s+=p;return s;解：計(jì)算i!(上標(biāo)為n，下標(biāo)為i=1)的值，其時(shí)間的復(fù)雜度為O(n)。 int sum2(int n)int s=0;for(int i=1;i<=n;i+) int p=1;for(int j=1;j<=i;j+) p*=j;s+=p;return s;解：計(jì)算i!的值，時(shí)間復(fù)雜度為O(n2) int fun(int n)int i=1,s=1; while(s<n) s+=+i;return i;解：求出滿足不等式1+2+3.+in的最

19、小i值， 其時(shí)間復(fù)雜度為O(n1/2)。 void UseFile(ifstream& inp,int c10)/假定inp所對(duì)應(yīng)的文件中保存有n個(gè)整數(shù)for(int i=0;i<10;i+) ci=0;int x; while(inp>>x) i=x%10; ci+;解：利用數(shù)組c10中的每個(gè)元素ci對(duì)應(yīng)統(tǒng)計(jì)出inp所數(shù)，時(shí)間復(fù)雜度為O(n)的整數(shù)文件中個(gè)位值同為i的整數(shù)個(gè) void mtable(int n)for(int i=1;i<=n;i+) for(int j=i;j<=n;j+) cout<<i<<"*&qu

20、ot;<<j<<"="<<setw(2)<<i*j<<"" cout<<end1;解：打印出一個(gè)具有n行的乘法表，第i行(1in)中有n-i+1個(gè)乘法項(xiàng)，每個(gè)乘法項(xiàng)為i與j( ijn)的乘積，時(shí)間復(fù)雜度為O(n2)。 void cmatrix(int aMN,int d)/M和N為全局整型for(int i=0;i<M;i+) for(int j=0;j<N;j+) aij*=d;解：使數(shù)組aMN中的每一個(gè)元素均詳細(xì)以d的值，時(shí)間復(fù)雜度為O(M*N) void matri

21、mult(int aMN,int bNL,int cML)/int i,j,k; for(i=0;i<M;i+) for(j=0;j<L;j+) cij=0; for(i=0;i<M;i+) for(j=0;j<L;j+) for(k=0;k<N;k+)cij+=aik*bkj;解：矩陣相乘，即aMN×bNLcML，時(shí)間復(fù)雜度為O(M×N×L)。5.題目略解：void InitSet(Set& s)for(int i=1;i<=SETSIZE;i+) s.mi=0;解：void InitSet(Set& s,in

22、t a,int n)fot(int i=0;i<n;i+) s.mai=1;解：Set operator + (Set s1,Set s2)Set s; InitSet(s);for(int i=1;i<=SETSIZE;i+) if(s1.mi=1)|s2.mi=1) s.mi=1;return s;解：Set operator*(Set s1,Set s2)Set s; InitSet(s);for(int i=1;i<=SETSIZE;i+) if(s1.mi=1)&&(s2.mi=1) s.mi=1;return s;解：Boolean operato

23、r(int elt,Set s)if(s.melt=1) return True; elsereturn False;解：void Inisert(Set& s,int n)s.mn=1;解：void Delete(Set& s,int n)s.mn=0;解：ostream& operator<<(ostream& ostr,Set& s)ostr<<''for(int i=1;i<=SETSIZE;i+) if(s.mi=1)ostr<<i<<',' ostr<

24、<''<<end1; return ostr;類別：數(shù)據(jù)結(jié)構(gòu)習(xí) 題 二一、單選題 1.在一個(gè)長(zhǎng)度為n的順序的線性表中，向第i個(gè)元素(1in+1)之前一個(gè)新元素時(shí)，需要從年向前依次移 B 個(gè)元素。A n-i B n-i+1C n-i-1 D i2.在一個(gè)長(zhǎng)度為n的順序前移 A 個(gè)元素。的線性表中，刪除第i個(gè)元素(1in+1)時(shí)，需要從前依次3.在一個(gè)長(zhǎng)度為n的線性表中順序查找值為x的元素時(shí)，查找的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為 C 。A n B n/2 C (n+1)/2 D (n-1)/2的平均查找長(zhǎng)度（即x同元素4.在一個(gè)單鏈表HL中，若要向

25、表頭一個(gè)指針p指向的結(jié)點(diǎn)，則執(zhí)行 B 。A HL=p;p->next=HL; B p=next=HL; HL=p;C p->next=HL; p=HL; D p->next=HL->next;HL->next=p;5.在一個(gè)單鏈表HL中，若要在指針q所指結(jié)點(diǎn)的后面D 。A q->next=p->next;p->next=q; B p->next=q->next;q=p;一個(gè)指針p所指向的結(jié)點(diǎn)，則執(zhí)行C q->next=p->next;p->next=q D p->next=q->next;q->ne

26、xt=p;6.在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行 C 。A p=q->next;p->next=q->next; B p=q->next;q->next=p;C p=q->next;q->next;q->next=q; D q->next=q=->Next->next;q->next=q;二、填空題1.性表的單結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)包含有兩個(gè)域，一個(gè)叫 值 ，另一個(gè)叫 指針 域。2.在下面數(shù)組a中60,42,74) 。a 0 1 2 3 4 5 6 7 8data 60 56 42 38 74 25

27、著一個(gè)線性表，表頭指針為a0.next，則該線性表為 (38,56,25,next 4 3 7 6 2 0 13.對(duì)于一個(gè)長(zhǎng)度為l的順序的線性表，在表頭元素的時(shí)間復(fù)雜度帾 o(n) ，在表尾插入元素的時(shí)間復(fù)雜度為 O(1) 。4.對(duì)于一個(gè)單的線性表，在表頭結(jié)點(diǎn)祫時(shí)話里有話復(fù)雜度為 o(1) ，在表尾元素的時(shí)間復(fù)雜度為 o(n) 。5.性表的順序中，若一個(gè)元素的下標(biāo)為i，則它的前驅(qū)元素的下標(biāo)為 i-1 ，后繼元素的下標(biāo)為 i+1 。6.性表的單中，若一個(gè)元素所在結(jié)點(diǎn)的地址為p，則后繼結(jié)點(diǎn)的地址為 p->next ，若假定p為一個(gè)數(shù)組a中的下標(biāo)，則其后繼結(jié)點(diǎn)的下標(biāo)為 ap.next 。7.在

28、循環(huán)單表中，最后一個(gè)結(jié)點(diǎn)的指針域指向 表頭 結(jié)點(diǎn)。8.在雙向結(jié)點(diǎn)。表中每個(gè)結(jié)點(diǎn)包含有兩個(gè)針域，一個(gè)指向其 前驅(qū) 結(jié)點(diǎn)，另一個(gè)指向其 后繼9.在循環(huán)雙向向 表頭 結(jié)點(diǎn)。表中表頭結(jié)點(diǎn)的左指針域指向 表尾 結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的右指針域指10.在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單HL->next=HL 。表中，鏈表為空的條件分別為 HL->next=NULL11.在由數(shù)組a中元素結(jié)點(diǎn)的單鏈表中，刪除下標(biāo)為i的結(jié)點(diǎn)后，需要把該結(jié)點(diǎn)到空閑表的表頭，具體操作為 ai.next=a1.next;a1.next=i; 。12.在由數(shù)組a中元素結(jié)點(diǎn)的單鏈表中，在下標(biāo)為i的結(jié)點(diǎn)后，需要從空閑表頭中刪除

29、一個(gè)結(jié)點(diǎn)，并將該結(jié)點(diǎn)下標(biāo)賦給i，具體操作為 i=a1.next;a1.next=ai.next; 。13.在由數(shù)組a中元素結(jié)點(diǎn)的單鏈表中，刪除下標(biāo)為i的后繼結(jié)點(diǎn)并將被刪除結(jié)點(diǎn)的下標(biāo)賦給i時(shí)，所進(jìn)行的操作描述為 p=ai.next;ai.next=ap.next;i=p; 。14.在由數(shù)組a中元素結(jié)點(diǎn)的單鏈表中，在下標(biāo)為i的結(jié)點(diǎn)的后面一個(gè)下標(biāo)為j的結(jié)點(diǎn)時(shí)，需要進(jìn)行的操作為 aj.next=ai.next;ai.next=j; 。三、普通題1.解：(79,62,34,57,26,48)解：(26,34,48,57,62,79)解：(48,56,57,62,79,34)解：(56,57,79,34)

30、解：(26,34,39,48,57,62)2.解：為了排版方便，假定采用以下輸出格式表示單表的示意圖；每個(gè)括號(hào)內(nèi)的數(shù)據(jù)表示一個(gè)元素結(jié)點(diǎn)，其中第一個(gè)數(shù)據(jù)為元素值，第二個(gè)數(shù)據(jù)為后繼結(jié)點(diǎn)的指針，第一個(gè)元素結(jié)點(diǎn)前的數(shù)值為表頭指針。(7(79,6),(62,5),(34,4),(57,3),(26,2),(48,0)(3(26,5),(34,2),(48,4),(57,6),(62,7),(79,0)(2(48,8),(56,4),(57,6),(62,7),(79,5),(34,0)(8(56,4),(57,7),(79,5),(34,0)3.對(duì)于List類型的線性表,編寫出下列每個(gè)算法。 從線性表中

31、刪除具有最小值的元素并由函數(shù)返回，空出的位置由最后一個(gè)元素填補(bǔ)，若線性表為空則顯示出錯(cuò)信息并解： ElemType DMValue(List&L)運(yùn)行。/從線性表中刪除具有最小值的元素并由函數(shù)返回,空出的位置/由最后一個(gè)元素填補(bǔ),若線性表為空則顯示出錯(cuò)信息并if(ListEmpty(L)cerr<<"List is Empty!"<<end1; exit(1);ElemType x; x=L.list0; int k=0;for(int i=1;i<L.size;i+) ElemType y=L.listi; if(y<x)x=y

32、;k=i;L.listk=L.listL.size-1; L.size-;return x;運(yùn)行 從線性表中刪除第i個(gè)元素并由函數(shù)返回。解：int Deletel(List& L,int i)/從線性表中刪除第i個(gè)元素并由函數(shù)返回if(i<1|i>L.size)cerr<<"Index is out range!"<<end1; exit(1);ElemType x; x=L.listi-1;for(int j=i-1;j<L.size-1;j+) L.listj=L.listj+1;L.size-;return x; 向線

33、性表中第i個(gè)元素位置一個(gè)元素。解：void Inser1(List& L,int i,ElemType x)/向線性表中第i個(gè)元素位置if(i<1|i>L.size+1)一個(gè)元素cerr<<"Index is out range!"<<end1; exit(1);if(L.size=MaxSize)cerr<<"List overflow!"<<end1; exit(1);for(int j=L.size-1;j>i-1;j-)L.listj+1=L.listj;L.listi-1

34、=x; L.size+; 從線性表中刪除具有給定值x的所有元素。解：void Delete2(List& L,ElemType x)/從線性表中刪除具有給定值x的所有元素int i=0; while(i<L.size) if(L.listi=x)for(int j=i+1;j<L.sizr;j+) L.listj-1=L.listj;L.size-;else i+; 從線性表中刪除其值在給定值s和t之間(要求s小于t)的所有元素。解：void Delete3(List& L,ElemType s,ElemType t)/從線性表中刪除其值在給定值s和t之間的所有元素

35、int i=0; while(i<L.size)if(L.listi>=s)&&(L.listi<=t) for(int j=i+1;j<L.size;j+)L.listj-i=L.listj; L.size-;else i+; 從有序表中刪除其值在給定值s和t之間(要求s小于t)的所有元素。解：void Delete4(List& L,ElemType s,ElemType t)/從有序表中刪除其值在給定值s和t之間的所有元素int i=0; while(i<L.size)/從有序表L中查找出大于等于s的第一個(gè)元素if(L.listi&l

36、t;s)i+;else break; if(i<L.size)While(i+j<L.size)&&(L.listi+j<=t) j+;/求出s和t之間元素的個(gè)數(shù)for(int k=i+j;k<L.size;k+)L.listk-j=L.listk; L.size-=j; 將兩個(gè)有序表合并成一個(gè)新的有序表并由變量返回。解：void Merge(List& L1,List& L2,List& L3)/將兩個(gè)有序表合并成一個(gè)新的有序表并由變量返回if(L1.size+L2.size>MaxSize) cerr<<&q

37、uot;List overflow!"<<end1; exit(1);int i=0,j=0,k=0; while(i<L1.size)&&(j<L2.size) if(L1.listi<=L2.listj) /將L1中的元素賦給L L.listk=L1.listi;i+;else /將L2中的元素賦給L L.listk=L2.listj;j+; k+;while(i<L1.size) /將L1中剩余的元素賦給L L.listk=L1.listi;i+;k+;while(j<L2.size) /將L2中剩余的元素賦給L L.l

38、istk=L2.listj;j+;k+;L.size=k; 從線性表中刪除所有其值重復(fù)的元素，使其所有元素的值均不同，如對(duì)于線性表(2,8,9, 2,5,5,6,8,7,2)，則執(zhí)行此算法后變?yōu)?2,8,9,5,6,7)。解：void Delete5(List& L)/從線性表中刪除所有其值重復(fù)的元素,使其所有元素的值均不同int i=0; while(i<L.size) int j=i+1; while(j<L.size) /刪除重復(fù)值為L(zhǎng).listi的所有元素if(L.listj=L.listi)for(int k=j+1;k<L.size;k+) L.listk

39、-1=L.listk;L.size-;else j+;i+;4.對(duì)于結(jié)點(diǎn)類型為L(zhǎng)Node的單表,編寫出下列每個(gè)算法。 將一個(gè)單表按逆序,即若原單鏈表中元素的次序?yàn)閍1,a2,.,an,則逆序后變?yōu)閍n,an-1,.a1。解：void Contrary(LNode*&HL)/將一個(gè)單多辦實(shí)事有按逆序LNode*p=HL;/p指向待逆序的第一個(gè)結(jié)點(diǎn)，初始指向原表頭結(jié)點(diǎn)HL=NULL;/HL仍為逆序后的表頭指針，值為空while(p!=NULL) /把原單鏈表中的結(jié)點(diǎn)依次進(jìn)行逆序LNode*q=p; /q指向待處理的結(jié)點(diǎn)p=p->next; /p指向下一個(gè)待逆序的結(jié)點(diǎn)/將q結(jié)點(diǎn)q-&g

40、t;next=HL; HL=q;到已單鏈表的表頭 刪除單鏈表中的第i個(gè)結(jié)點(diǎn)。解：void Delete1(LNode*&HL,int i)/刪除單鏈表中的第i個(gè)結(jié)點(diǎn)if(i<1|HL=NULL)cerr<<"Index is out range!"<<end1; exit(1);LNode*ap,*cp;ap=NULL;cp=HL; /cp指向當(dāng)前結(jié)點(diǎn)，ap指向其前驅(qū)結(jié)點(diǎn)int j=1;while(cp!=NULL) if(j=i)break; /cp結(jié)點(diǎn)即為第i個(gè)結(jié)點(diǎn)else /繼續(xù)ap=cp; cp=cp->next; j+;

41、if(cp=NULL)尋找cerr<<"Index is out range!"<<end1; exit(1);if(ap=NULL) HL=HL->next; elseap->next=cp->next; delete cp; 從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回，若單鏈表為空，則顯示出錯(cuò)信息并停止運(yùn)行。解：ElemType MaxValue(LNode*HL)/從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回if(HL=NULL)cerr<<"Linked list is empty!"

42、;<<end1; exit(1);ElemType max=HL->data; LNode*p=HL->next; while(p!=NULL)if(max<p->data) max=p->data; p=p->next;return max; 統(tǒng)計(jì)出單鏈表中結(jié)點(diǎn)的值等于給定值x的結(jié)點(diǎn)數(shù)。解：int Count(LNode*HL,ElemType x)/統(tǒng)計(jì)出單鏈表中結(jié)點(diǎn)的值等于給定值x的結(jié)點(diǎn)數(shù)int n=0; while(HL!=NULL) if(HL->data=x) n+; HL=HL->next;return n; 根據(jù)一維數(shù)

43、組an建立一個(gè)單鏈表，使單鏈表中元素的次序與an中元素的次序相同， 并使該算法的時(shí)間復(fù)雜度為O(n)。解：void Create(LNode*&HL,ElemType a,int n)/根據(jù)一維數(shù)組an建立一個(gè)單鏈表InitList(HL);for(int i=n-1;i>=0;i-) InsertFront(HL,ai; 將一個(gè)單鏈表重新成有序單鏈表。解：void OrderList(LNode*&HL)/將一個(gè)單鏈表重新成有序單鏈表LNode* p=HL;/p指向待處理的第一個(gè)結(jié)點(diǎn)，初始指向原表頭結(jié)點(diǎn)HL=NULL; /HL仍為待建立的有序表的表頭指針， while(

44、p!=NULL) /把原單鏈表中的結(jié)點(diǎn)依次進(jìn)行有序值為空LNode* q=p; /q指向待處理的結(jié)點(diǎn)p=p->next; /p指向下一個(gè)待處理的結(jié)點(diǎn)LNode* ap=NULL,*cp=HL;/cp指向有序表中待比較的結(jié)點(diǎn)，ap指向其前驅(qū)結(jié)點(diǎn)while(cp!=NULL) /為q結(jié)點(diǎn)尋找位置if(q->data<cp->data) break;elseap=cp; cp=cp->next; /將q結(jié)點(diǎn)q->next=cp;if(ap=NULL) HL=q;elseap->next=q;到ap和cpxf hko pp uj 將兩個(gè)有序單鏈表合并成一個(gè)有序

45、單鏈表，合并后使原有單鏈表為空。解：LNode*Mergel(LNode*&p1,LNode*&p2)/將兩個(gè)有序單鏈表合并成一個(gè)有序單鏈表LNode a; /a結(jié)點(diǎn)作為結(jié)果的有序單鏈表的表頭附加結(jié)點(diǎn)，這樣便于處理，處理/結(jié)束后返回a結(jié)點(diǎn)的鐨針域的值LNode*p=&a; /p指向結(jié)果的有序單鏈表的表尾結(jié)點(diǎn)p->next=NULL;/初始指向表頭附加結(jié)點(diǎn)while(p1!=NULL)&&(p2!=NULL)/處理兩個(gè)表非空的情況if(p1->data<p2->data)p->next=p1;p1=p1->next;el

46、sep->next=p2;p2=p2->p=p->next;if(p1!=NULL)p->next=p1; if(p2!=NULL)p->next=p2; p1=p2=NULL;return a.next; 根據(jù)兩個(gè)有序單鏈表生成一個(gè)新的有序單鏈表，原有單鏈表保持不變。如假定兩個(gè)有序單鏈表中的元素為(2,8,10,20)和(3,8,9,15,16)，則生成的新單鏈表中的元素為(2,3,8,8,9,10,15,16,20)。解：LNode*Merge2(LNode*p1,LNode*p2)/根據(jù)兩個(gè)有序單鏈表生成一個(gè)新的有序單鏈表LNode a; /用a作為新的有序

47、單鏈表的表頭附加結(jié)點(diǎn)LNode*p=&a; /p指向結(jié)果有序單鏈表的表尾結(jié)點(diǎn)p->next=NULL; /初始指向表頭附加結(jié)點(diǎn)while(p1!=NULL&&(p2!=NULL) /處理兩個(gè)表非空時(shí)的情況LNode*newptr=new LNode; if(p1->data<p2->data) /由p1->data建立新結(jié)點(diǎn)，然后p1指針后移newptr->data=p1->data;p1=p1->next;else /由p2->data建立新結(jié)點(diǎn)，然后p2指針后移newptr->data=p2->dat

48、a;p2=p2->next;/將newptr結(jié)點(diǎn)p->next=newptr; p=newptr;while(p1!=NULL)到結(jié)果的有序表的表尾 /繼續(xù)處理p1單鏈表中剩余的結(jié)點(diǎn)LNode*newptr=new LNode;newptr->data=p1->data; p1=p1->next;p->next=newptr; p=newptr;while(p2!=NULL) /繼續(xù)處理p2單鏈表中剩余的結(jié)點(diǎn)LNode*newptr=new LNode;newptr->data=p2->data; p2=p2->next;p->nex

49、t=newptr; p=newptr;p->next=NULL;return a.next; 根據(jù)一個(gè)元素類型為整型的單鏈表生成兩個(gè)單鏈表，使得第一個(gè)單鏈表中包含原單鏈表中所有元素值為奇數(shù)的結(jié)點(diǎn)，使得第二個(gè)單鏈表中包含原單鏈表中所有元素值為偶數(shù)的結(jié)點(diǎn)。原有單鏈表保持不變。解：void Separate(LNode*HL,LNode*&p1,LNode*&p2)/根據(jù)一個(gè)單鏈表HL按條件拆分生成兩個(gè)單鏈表p1和p2LNode a,b; /a和b結(jié)點(diǎn)分別作為p1和p2單鏈表的表頭附加結(jié)點(diǎn)LNode*t1=&a,*t2=&b; /t1和t2分別作為指向p1和p2

50、單鏈表的/表尾結(jié)點(diǎn)，初始指向表頭附加結(jié)點(diǎn)Lnode*p=HL;while(p!=NULL) /每循環(huán)一次產(chǎn)生一個(gè)新結(jié)點(diǎn)，并把它加入到p1或p2單鏈表/的未尾LNode*newptr=new LNode; if(p->data%2=1)newptr->data=p->data; t1->next=newptr; t1=newptr;elsenewptr->data=p->data; t2->next=newptr; t2=newptr;p=p->next;t1->next=t2->next=NULL;p1=a.next;p2=b.nex

51、t; /把指向兩個(gè)單鏈表的表頭結(jié)點(diǎn)的指針?lè)謩e賦給/p1和p2返回6.編寫一個(gè)算法，使用表頭附加結(jié)點(diǎn)的循環(huán)單鏈表解決(Josephus)。其是：設(shè)有n個(gè)人圍坐在一張圓桌周圍，現(xiàn)從某個(gè)人開始從1報(bào)數(shù)，數(shù)到m的人出列(即離開坐位， 不參加以后的報(bào)數(shù))，接著從出列的下一個(gè)人開始重新從1報(bào)數(shù)，數(shù)到m的人又出列，如此下 去直到所有人都出列為止，試求出它們的出列次序。假如，當(dāng)n=8、m=4時(shí)，若從第一個(gè)人(假定每個(gè)人的編號(hào)依次為1,2.,n)開始報(bào)數(shù)，則得 到的出列次序?yàn)?4,8,5,2,1,3,7,6。此算法要求以n、m和s(假定從第s個(gè)人開始第一次報(bào)數(shù))作為值參。解：void Josephus(int

52、n,int m,int s)/使用帶表頭附加結(jié)點(diǎn)的循環(huán)單鏈表解決/生成表頭附加結(jié)點(diǎn)，此時(shí)循環(huán)單鏈表為空LNode*HL=new LNode;HL->next=HL; int i;/生成含有n個(gè)結(jié)點(diǎn)、結(jié)點(diǎn)依次為1,2,.n的帶表頭結(jié)點(diǎn)的循環(huán)單鏈表for(i=n;i>=1;i-)/生成新的結(jié)點(diǎn)LNode*newptr=new LNode; newptr->data=i;/把新的結(jié)點(diǎn)到表頭newptr->next=HL->next; HL->next=newptr;/從表頭開始順序查找出第s個(gè)結(jié)點(diǎn)，對(duì)應(yīng)第一個(gè)開始報(bào)數(shù)的人LNode*ap=HL,*cp=HL->

53、;next;for(i=1;i<s;i+)/ap和cp指針后移一個(gè)位置ap=cp;cp=cp->next;/若cp指向了表頭附加結(jié)點(diǎn)，則仍需后移ap和cp指針，使之指向表頭結(jié)點(diǎn)if(cp=HL)ap=HL;cp=HL->next;/依次使n-1個(gè)人出列for(i=1;i<n;i+)/順序查找出待出列的人，即為循環(huán)結(jié)束后cp所指向的結(jié)點(diǎn)for(int j=1;j<m;j+)ap=cp; cp=cp->next;if(cp=HL)ap=HL;cp=HL->next;/輸出cp結(jié)點(diǎn)的值，即出列的人cout<<cp->data<<

54、""/從單鏈表中刪除cp結(jié)點(diǎn)ap->next=cp->next;delete cp;/使cp指向被刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)cp=ap->next;/若cp指向了表頭附加結(jié)點(diǎn)，則后移ap和cp指針if(cp=HL)ap=HL;cp=HL->next;/使最后一個(gè)人出列cout<<HL->next->data<<end1;/刪除表頭結(jié)點(diǎn)和表頭附加結(jié)點(diǎn)delete HL->next; delete HL;7.對(duì)于性表抽象數(shù)據(jù)類型中定義的每一個(gè)操作，寫出結(jié)點(diǎn)類型為L(zhǎng)Node的附加結(jié)點(diǎn)的循環(huán)單鏈表上實(shí)現(xiàn)的對(duì)應(yīng)算法。初始化單鏈

55、表解：void InitList(LNode*HL)HL->next=HL;/將單鏈表置空刪除單鏈表中的所有結(jié)點(diǎn)，使之成為一個(gè)空表void ClearList(LNode*HL)LNode*cp,*np;cp=HL->next;/將指向第一個(gè)結(jié)點(diǎn)的指針賦給cpwhile(cp!=HL)/遍歷單鏈表，交回每一個(gè)結(jié)點(diǎn)。np=cp->next;/保存下一個(gè)結(jié)點(diǎn)的指針。delete cp;/刪除當(dāng)前結(jié)點(diǎn)。cp=np;/使下一個(gè)結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)。HL->next=HL;/置單鏈表為空得到單鏈表的長(zhǎng)度int ListSize(LNode*HL)LNode*p=HL->next

56、; int i=0;while(p!=HL)i+;p=p->next; return i;檢查單鏈表是否為空int ListEmpty(LNode*hl)return(HL->next=HL);得到單鏈表中第pos個(gè)結(jié)點(diǎn)中的元素ElemType GetElem(LNode*HL,int pos)if(pos<1)cerr<<"pos is out range!"<<end1; exit(1);LNode* p=HL->next; int i=0; while(p!=HL)i+;if(i=pos)break; p=p->n

57、ext;if(p!=HL)return p->data; elsecerr<<"pos is out range!"<<end1; exit(1);遍歷單鏈表void TraverseList(LNode*HL)LNode* p=HL->next; while(p!=HL) cout<<p->data<<"" p=p->next;cout<<end1;從單鏈表查找具有給定值的第一個(gè)元素int Find(LNode* HL,ElemType& item)LNode* p=HL