數(shù)據(jù)結構實用教程課后答案

1、第一題一一、單選題1.一個數(shù)組ai與( A )的表示等價。A *(a+i) B a+i C *a+i D &a+i2.對于兩個函數(shù)，若函數(shù)名相同，但只是( C) 不同則不是重載函數(shù)。A 參數(shù)類型 B 參數(shù)個數(shù) C 函數(shù)類型3.若需要利用形參直接實參，則應把形參變量說明為 (B) 參數(shù)。A 指針 BC 值4.下面程序段的復雜度為 (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í)行下面程序段時，執(zhí)行S語句的次數(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.下面算法的時間復雜度為( 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ù)的邏輯結構被除數(shù)分為 集合結構 、 線性結構 、結構 和 圖形結構 四種。2.數(shù)據(jù)的結構被分為 順序結構 、結構 、 索引結構 和 散列結構 四種。3.性結構、結構和圖形結構中，前驅(qū)和后繼結點之間分別著 1對1 、 1對N 和 M對N 的

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

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

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

6、a1的概率為1/4，查找其余元素的概率均相同，則在查找較次數(shù)為 35/12 。時同元素的平均比三、普通題 1.有下列幾種用二元組表示的數(shù)據(jù)結構，試畫出它們分別對應的圖形表示（當出現(xiàn)多個時，對每個畫出相應的結構圖），并指出它們分別屬于何種結構。 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>解：是集合結構；是線性結構；是結構；散列結構。只作為參考。2.設計二次多項式ax2+bx+c的一種抽象數(shù)據(jù)類型，假定起名為QIAdratic,該類型的數(shù)據(jù)部分分為三個系數(shù)項a、b和c，操作部分為：

9、(請寫出下面每一個 操作的具體實現(xiàn))。 初始化數(shù)據(jù)成員ab和c(假定用員的默認值為0。類型Quadratie定義成員)，每個數(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; 做兩個多項式加法,即使對應的系數(shù)相加,并返回相加的結果。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的值計算多項式的值。float Eval(Quadratic q,float x);解：float Eval(Quadratic q,float x)return(q.a*x*x+q.b*x+q.c); 計算方程ax2+bx+c=0的兩個實數(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表示)輸出二次多項式，在輸出時要注意去掉系數(shù)為0的項，并且當b和c的值為負時，其前不能出現(xiàn)加號。

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ù)描述下列每一個算法，并分別求出它們的時間復雜度。 比較同一簡單類型的兩個數(shù)據(jù)x1和x2的大小，對于x1>x2,x1=x2和x1<x2這三種不同情況分別返回'>''='和'<'字符。假定簡單類型用SimpleType表示，它可通過typedef語句定義為任一簡單類型。解：char compare(SimpleType x1,SimpleType x2)if(x1>x2) return'>'else if(x1=x2) return '=' else

14、 return'<'其時間復雜度為O(1) 將一個字符串中的所有字符按相反方的次序重新放置。解：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;其時間復雜度為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;其時間復雜度為O(n)乘積。 計算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;其時間復雜度為O(n) 假定一維數(shù)組an中的每個元素值均在0，200區(qū)間內(nèi)，分別統(tǒng)計出落在0，20),20,50),50,80),80,130),130,200等各區(qū)間的元素個數(shù)。解：int Count(int a,int n,int c5)/用數(shù)組c5保存統(tǒng)計結果int d5=20,50,80,130,201;/用來保存各統(tǒng)計區(qū)間的上限int i,j; for(i=0;i<5;i+)ci=0;/給

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

17、形參，它是對應實參的別名，其值由實參帶回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;其時間復雜度為O(m*n)4.指出下列各算法的功能并求出其時間復雜度。 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是否是一個O(n1/2)。，若是則返回數(shù)值1，否則返回0。該算法的時間復雜度為 i

18、nt sum1(int n)int p=1,s=0;for(int i=1;i<=n;i+) p*=i;s+=p;return s;解：計算i!(上標為n，下標為i=1)的值，其時間的復雜度為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;解：計算i!的值，時間復雜度為O(n2) int fun(int n)int i=1,s=1; while(s<n) s+=+i;return i;解：求出滿足不等式1+2+3.+in的最

19、小i值， 其時間復雜度為O(n1/2)。 void UseFile(ifstream& inp,int c10)/假定inp所對應的文件中保存有n個整數(shù)for(int i=0;i<10;i+) ci=0;int x; while(inp>>x) i=x%10; ci+;解：利用數(shù)組c10中的每個元素ci對應統(tǒng)計出inp所數(shù)，時間復雜度為O(n)的整數(shù)文件中個位值同為i的整數(shù)個 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;解：打印出一個具有n行的乘法表，第i行(1in)中有n-i+1個乘法項，每個乘法項為i與j( ijn)的乘積，時間復雜度為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中的每一個元素均詳細以d的值，時間復雜度為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，時間復雜度為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ù)結構習 題 二一、單選題 1.在一個長度為n的順序的線性表中，向第i個元素(1in+1)之前一個新元素時，需要從年向前依次移 B 個元素。A n-i B n-i+1C n-i-1 D i2.在一個長度為n的順序前移 A 個元素。的線性表中，刪除第i個元素(1in+1)時，需要從前依次3.在一個長度為n的線性表中順序查找值為x的元素時，查找的平均比較次數(shù)，假定查找每個元素的概率都相等）為 C 。A n B n/2 C (n+1)/2 D (n-1)/2的平均查找長度（即x同元素4.在一個單鏈表HL中，若要向

25、表頭一個指針p指向的結點，則執(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.在一個單鏈表HL中，若要在指針q所指結點的后面D 。A q->next=p->next;p->next=q; B p->next=q->next;q=p;一個指針p所指向的結點，則執(zhí)行C q->next=p->next;p->next=q D p->next=q->next;q->ne

26、xt=p;6.在一個單鏈表HL中，若要刪除由指針q所指向結點的后繼結點，則執(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.性表的單結構中，每個結點包含有兩個域，一個叫 值 ，另一個叫 指針 域。2.在下面數(shù)組a中60,42,74) 。a 0 1 2 3 4 5 6 7 8data 60 56 42 38 74 25

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

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

29、一個結點，并將該結點下標賦給i，具體操作為 i=a1.next;a1.next=ai.next; 。13.在由數(shù)組a中元素結點的單鏈表中，刪除下標為i的后繼結點并將被刪除結點的下標賦給i時，所進行的操作描述為 p=ai.next;ai.next=ap.next;i=p; 。14.在由數(shù)組a中元素結點的單鏈表中，在下標為i的結點的后面一個下標為j的結點時，需要進行的操作為 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.解：為了排版方便，假定采用以下輸出格式表示單表的示意圖；每個括號內(nèi)的數(shù)據(jù)表示一個元素結點，其中第一個數(shù)據(jù)為元素值，第二個數(shù)據(jù)為后繼結點的指針，第一個元素結點前的數(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.對于List類型的線性表,編寫出下列每個算法。 從線性表中

31、刪除具有最小值的元素并由函數(shù)返回，空出的位置由最后一個元素填補，若線性表為空則顯示出錯信息并解： ElemType DMValue(List&L)運行。/從線性表中刪除具有最小值的元素并由函數(shù)返回,空出的位置/由最后一個元素填補,若線性表為空則顯示出錯信息并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;運行 從線性表中刪除第i個元素并由函數(shù)返回。解：int Deletel(List& L,int i)/從線性表中刪除第i個元素并由函數(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個元素位置一個元素。解：void Inser1(List& L,int i,ElemType x)/向線性表中第i個元素位置if(i<1|i>L.size+1)一個元素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的第一個元素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之間元素的個數(shù)for(int k=i+j;k<L.size;k+)L.listk-j=L.listk; L.size-=j; 將兩個有序表合并成一個新的有序表并由變量返回。解：void Merge(List& L1,List& L2,List& L3)/將兩個有序表合并成一個新的有序表并由變量返回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; 從線性表中刪除所有其值重復的元素，使其所有元素的值均不同，如對于線性表(2,8,9, 2,5,5,6,8,7,2)，則執(zhí)行此算法后變?yōu)?2,8,9,5,6,7)。解：void Delete5(List& L)/從線性表中刪除所有其值重復的元素,使其所有元素的值均不同int i=0; while(i<L.size) int j=i+1; while(j<L.size) /刪除重復值為L.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.對于結點類型為LNode的單表,編寫出下列每個算法。 將一個單表按逆序,即若原單鏈表中元素的次序為a1,a2,.,an,則逆序后變?yōu)閍n,an-1,.a1。解：void Contrary(LNode*&HL)/將一個單多辦實事有按逆序LNode*p=HL;/p指向待逆序的第一個結點，初始指向原表頭結點HL=NULL;/HL仍為逆序后的表頭指針，值為空while(p!=NULL) /把原單鏈表中的結點依次進行逆序LNode*q=p; /q指向待處理的結點p=p->next; /p指向下一個待逆序的結點/將q結點q-&g

40、t;next=HL; HL=q;到已單鏈表的表頭 刪除單鏈表中的第i個結點。解：void Delete1(LNode*&HL,int i)/刪除單鏈表中的第i個結點if(i<1|HL=NULL)cerr<<"Index is out range!"<<end1; exit(1);LNode*ap,*cp;ap=NULL;cp=HL; /cp指向當前結點，ap指向其前驅(qū)結點int j=1;while(cp!=NULL) if(j=i)break; /cp結點即為第i個結點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ù)返回，若單鏈表為空，則顯示出錯信息并停止運行。解：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)計出單鏈表中結點的值等于給定值x的結點數(shù)。解：int Count(LNode*HL,ElemType x)/統(tǒng)計出單鏈表中結點的值等于給定值x的結點數(shù)int n=0; while(HL!=NULL) if(HL->data=x) n+; HL=HL->next;return n; 根據(jù)一維數(shù)

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

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

45、單鏈表，合并后使原有單鏈表為空。解：LNode*Mergel(LNode*&p1,LNode*&p2)/將兩個有序單鏈表合并成一個有序單鏈表LNode a; /a結點作為結果的有序單鏈表的表頭附加結點，這樣便于處理，處理/結束后返回a結點的鐨針域的值LNode*p=&a; /p指向結果的有序單鏈表的表尾結點p->next=NULL;/初始指向表頭附加結點while(p1!=NULL)&&(p2!=NULL)/處理兩個表非空的情況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ù)兩個有序單鏈表生成一個新的有序單鏈表，原有單鏈表保持不變。如假定兩個有序單鏈表中的元素為(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ù)兩個有序單鏈表生成一個新的有序單鏈表LNode a; /用a作為新的有序

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

48、a;p2=p2->next;/將newptr結點p->next=newptr; p=newptr;while(p1!=NULL)到結果的有序表的表尾 /繼續(xù)處理p1單鏈表中剩余的結點LNode*newptr=new LNode;newptr->data=p1->data; p1=p1->next;p->next=newptr; p=newptr;while(p2!=NULL) /繼續(xù)處理p2單鏈表中剩余的結點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ù)一個元素類型為整型的單鏈表生成兩個單鏈表，使得第一個單鏈表中包含原單鏈表中所有元素值為奇數(shù)的結點，使得第二個單鏈表中包含原單鏈表中所有元素值為偶數(shù)的結點。原有單鏈表保持不變。解：void Separate(LNode*HL,LNode*&p1,LNode*&p2)/根據(jù)一個單鏈表HL按條件拆分生成兩個單鏈表p1和p2LNode a,b; /a和b結點分別作為p1和p2單鏈表的表頭附加結點LNode*t1=&a,*t2=&b; /t1和t2分別作為指向p1和p2

50、單鏈表的/表尾結點，初始指向表頭附加結點Lnode*p=HL;while(p!=NULL) /每循環(huán)一次產(chǎ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; /把指向兩個單鏈表的表頭結點的指針分別賦給/p1和p2返回6.編寫一個算法，使用表頭附加結點的循環(huán)單鏈表解決(Josephus)。其是：設有n個人圍坐在一張圓桌周圍，現(xiàn)從某個人開始從1報數(shù)，數(shù)到m的人出列(即離開坐位， 不參加以后的報數(shù))，接著從出列的下一個人開始重新從1報數(shù)，數(shù)到m的人又出列，如此下 去直到所有人都出列為止，試求出它們的出列次序。假如，當n=8、m=4時，若從第一個人(假定每個人的編號依次為1,2.,n)開始報數(shù)，則得 到的出列次序為:4,8,5,2,1,3,7,6。此算法要求以n、m和s(假定從第s個人開始第一次報數(shù))作為值參。解：void Josephus(int

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

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

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

55、表解：void InitList(LNode*HL)HL->next=HL;/將單鏈表置空刪除單鏈表中的所有結點，使之成為一個空表void ClearList(LNode*HL)LNode*cp,*np;cp=HL->next;/將指向第一個結點的指針賦給cpwhile(cp!=HL)/遍歷單鏈表，交回每一個結點。np=cp->next;/保存下一個結點的指針。delete cp;/刪除當前結點。cp=np;/使下一個結點成為當前結點。HL->next=HL;/置單鏈表為空得到單鏈表的長度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個結點中的元素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;從單鏈表查找具有給定值的第一個元素int Find(LNode* HL,ElemType& item)LNode* p=HL