數(shù)據(jù)結(jié)構(gòu)實(shí)用教程第二版答案-徐孝凱

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 第一章緒習(xí) 題 一1.有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，試畫出它們分別對應(yīng)的圖形表示（當(dāng)出現(xiàn)多個(gè)關(guān)系時(shí)，對每個(gè)關(guān)系畫出相應(yīng)的結(jié)構(gòu)圖），并指出它們分別屬于何種結(jié)構(gòu)。 A=(K,R)其中K=a1,a2,a3.,anR= B=(K,R)其中K=a,b,c,d,e,f,g,hR=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,hR=rr=<d,b>,<d,g>,<b,a>

2、;,<b,c>,<g,e>,<g,h>,<e,f> D=(K,R)其中K=1,2,3,4,5,6R=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,43R=r1,r2,r3r1=<48,25>,<25,64>,<64,57>,<57,82>,<82,36>,<36,75>,<75,43>r2=<48,25>,<48,64>,

3、<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，操作部分為：(請寫出下面每一個(gè)操作的具體實(shí)現(xiàn))。 初始化數(shù)據(jù)成員ab和c(

4、假定用記錄類型Quadratie定義成員)，每個(gè)數(shù)據(jù)成員的默認(rèn)值為0。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)式加法,即使對應(yīng)的系數(shù)相加,并返回相加的結(jié)果。Quadratic Add(Quadratic q1,Quadratic q2);解：Quadratic Add(Quadratic q1,Quadratic q2)

5、;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ù)根，對于有實(shí)根、無實(shí)根和不是實(shí)根方程(即a=0)這三種情況要返回不同的整數(shù)值，以便于工作調(diào)用函數(shù)做不同的處理。int Root(Quadratic q,float& r1,float& r2);解：in

6、t 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)加號。void Print(Quadratic q)解：void Print(Quadr

7、atic 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<<end1;3.用c+函數(shù)描述下列每一個(gè)算法，并分別求出它們的時(shí)間復(fù)雜度。 比較同一簡單

8、類型的兩個(gè)數(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 return'<'其時(shí)間復(fù)雜度為O(1) 將一個(gè)字符串中的所有字符按相反方

9、的次序重新放置。解：void Reverse(char*p)int n=strlen(p);for(int i=0;i<n/2;i+)char ch;ch=pipi=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的值。解：double Accumulate(double x,int n)double p=1,s=1;for(

10、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;/用來保存各統(tǒng)計(jì)區(qū)間的上限int i,j;for(i=0;i<5;i+)ci=0;/給數(shù)組c5中的每個(gè)元素賦初值0for(i=0;i<n;i+)if(ai<0|ai>200)

11、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為引用/形參，它是對應(yīng)實(shí)參的別名，其值由實(shí)參帶回Lin=0;Col=0;for(int i=0;i<

12、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;elsereturn 0;解：判斷n是否是一個(gè)素?cái)?shù)，若是則返回?cái)?shù)值1，否則返回0。該算法的時(shí)間復(fù)雜度為O(n1/2)。 int sum1(int n)int p=1,s=0;for(int i=1;i<=n;i+)p*=

13、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的最小i值， 其時(shí)間復(fù)雜度為O(n1/2)。 void UseFile(ifstream& inp,int c

14、10)/假定inp所對應(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對應(yīng)統(tǒng)計(jì)出inp所聯(lián)系的整數(shù)文件中個(gè)位值同為i的整數(shù)個(gè)數(shù)，時(shí)間復(fù)雜度為O(n) void mtable(int n)for(int i=1;i<=n;i+)for(int j=i;j<=n;j+)cout<<i<<"*"<<j<<"="<<setw(2)<<i*j&l

15、t;<""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 matrimult(int aMN,int bNL,int cML)/int i,j,k;for(i=0;i<M;i+)for(j

16、=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,int a,int n)fot(int i=0;i<n;i+)s.mai=1;解：Set operator + (Set s1,Set s

17、2)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 operator(int elt,Set s)if(s.melt=1)return True;elsereturn False;解：void Inisert(Set&a

18、mp; 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<<''<<end1;return ostr;第二章 線性表 習(xí)題 二1.解：(79,62,34,57,26,48)解：(26,3

19、4,48,57,62,79)解：(48,56,57,62,79,34)解：(56,57,79,34)解：(26,34,39,48,57,62)2.解：為了排版方便，假定采用以下輸出格式表示單鏈接表的示意圖；每個(gè)括號內(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)

20、,(57,7),(79,5),(34,0)3.對于List類型的線性表,編寫出下列每個(gè)算法。 從線性表中刪除具有最小值的元素并由函數(shù)返回，空出的位置由最后一個(gè)元素填補(bǔ)，若線性表為空則顯示出錯(cuò)信息并退出運(yùn)行。解： ElemType DMValue(List&L)/從線性表中刪除具有最小值的元素并由函數(shù)返回,空出的位置/由最后一個(gè)元素填補(bǔ),若線性表為空則顯示出錯(cuò)信息并退出運(yùn)行if(ListEmpty(L)cerr<<"List is Empty!"<<end1;exit(1);ElemType x;x=L.list0;int k=0;for(in

21、t i=1;i<L.size;i+)ElemType y=L.listi;if(y<x)x=y;k=i;L.listk=L.listL.size-1;L.size-;return x; 從線性表中刪除第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.s

22、ize-1;j+)L.listj=L.listj+1;L.size-;return x; 向線性表中第i個(gè)元素位置插入一個(gè)元素。解：void Inser1(List& L,int i,ElemType x)/向線性表中第i個(gè)元素位置插入一個(gè)元素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

23、=L.size-1;j>i-1;j-)L.listj+1=L.listj;L.listi-1=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-;elsei+; 從線性表中刪除其值在給定值s和t之間(要求s小于t)的所有元素。解：void Delete3(List& L,El

24、emType s,ElemType t)/從線性表中刪除其值在給定值s和t之間的所有元素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-;elsei+; 從有序表中刪除其值在給定值s和t之間(要求s小于t)的所有元素。解：void Delete4(List& L,ElemType s,ElemType t)/從有序表中刪除其值在給定值s和t之間的所有元素int i=0;while(i<L

25、.size)/從有序表L中查找出大于等于s的第一個(gè)元素if(L.listi<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.siz

26、e+L2.size>MaxSize)cerr<<"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中的元素賦給LL.listk=L1.listi;i+;else /將L2中的元素賦給LL.listk=L2.listj;j+;k+;while(i<L1.size) /將L1中剩余的元素賦給LL.listk=L1.listi;i+;k+;while(j&l

27、t;L2.size) /將L2中剩余的元素賦給LL.listk=L2.listj;j+;k+;L.size=k; 從線性表中刪除所有其值重復(fù)的元素，使其所有元素的值均不同，如對于線性表(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.listi的所有元素if(L.listj=L.listi)for(int k=j+1;

28、k<L.size;k+)L.listk-1=L.listk;L.size-;elsej+;i+;4.對于結(jié)點(diǎn)類型為LNode的單鏈接表,編寫出下列每個(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é)

29、點(diǎn)p=p->next; /p指向下一個(gè)待逆序的結(jié)點(diǎn)/將q結(jié)點(diǎn)插入到已陳序單鏈表的表頭q->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)即為第

30、i個(gè)結(jié)點(diǎn)else /繼續(xù)向后尋找ap=cp;cp=cp->next;j+;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<&l

31、t;"Linked list is empty!"<<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=

32、HL->next;return n; 根據(jù)一維數(shù)組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=NU

33、LL; /HL仍為待建立的有序表的表頭指針，祿始值為空while(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)插入到ap和cpxf hko pp ujq->next=cp;if(ap=NULL)HL=q

34、;elseap->next=q; 將兩個(gè)有序單鏈表合并成一個(gè)有序單鏈表，合并后使原有單鏈表為空。解：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->d

35、ata)p->next=p1;p1=p1->next;elsep->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è)有

36、序單鏈表生成一個(gè)新的有序單鏈表LNode a; /用a作為新的有序單鏈表的表頭附加結(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)，然后

37、p2指針后移newptr->data=p2->data;p2=p2->next;/將newptr結(jié)點(diǎn)插入到結(jié)果的有序表的表尾p->next=newptr;p=newptr;while(p1!=NULL) /繼續(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->

38、;data;p2=p2->next;p->next=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,

39、*t2=&b; /t1和t2分別作為指向p1和p2單鏈表的/表尾結(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

40、=NULL;p1=a.next;p2=b.next; /把指向兩個(gè)單鏈表的表頭結(jié)點(diǎn)的指針分別賦給/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è)人的編號依次為1,2.,n)開始報(bào)數(shù)，則得到的出列次序?yàn)?4,8,5,2,1,3,7,6。此算法要求以n、m和s(假定從第s個(gè)人開始第一次

41、報(bào)數(shù))作為值參。解：void Josephus(int 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)，對

42、應(yīng)第一個(gè)開始報(bào)數(shù)的人LNode*ap=HL,*cp=HL->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)的值，即出列的人

43、cout<<cp->data<<""/從單鏈表中刪除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.對于在線性表抽象數(shù)據(jù)類型中定義的每一個(gè)操作，寫出結(jié)點(diǎn)類

44、型為LNode的帶頭附加結(jié)點(diǎn)的循環(huán)單鏈表上實(shí)現(xiàn)的對應(yīng)算法。初始化單鏈表解：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)/遍歷單鏈表，向系統(tǒng)交回每一個(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;/置單鏈表為空得到單鏈表的長度int

45、ListSize(LNode*HL)LNode*p=HL->next;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!

46、=HL)i+;if(i=pos)break;p=p->next;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

47、,ElemType& item)LNode* p=HL->next;while(p!=HL)if(p->data=item)item=p->data;return 1;elsep=p->next;return 0;更新單鏈表中具有給定值的第一個(gè)元素int Updata(LNode* HL,const ElemType& item)LNode* p=HL->next;while(p!=HL)/查找元素if(p->data=item)break;else p=p->next;if(p=HL)return 0;else/更新元素p->d

48、ata=item;return 1;向單鏈表的未尾插入一個(gè)元素void InsertRear(LNode* HL,const ElemType& item)LNode* newptr;newptr=new LNode;newptr->data=item;/把新元素賦給動態(tài)結(jié)點(diǎn)*newptr的值域。LNode* p=HL;while(p->next!=HL)/從表頭開始遍歷到最后一個(gè)結(jié)點(diǎn)為止。p=p->next;newptr->next=HL;p->next=newptr;/把新結(jié)點(diǎn)鏈接到表尾。向單鏈表的表頭插入一個(gè)元素void InsertFront(LN

49、ode* HL,const ElemType& item)LNode* newptr;newptr=new LNode;newptr->data=item;newptr->next=HL->next;HL->next=newptr;(11)向單鏈表中插入一個(gè)元素void Insert(LNode* HL,const ElemType& item)LNode* newptr;newptr=new LNode;newptr->data=item;LNode *ap,*cp;ap=HL;cp=HL->next;while(cp!=HL)if(ite

50、m<cp->data)break;elseap=cp;cp=cp->next;newptr->next=cp;ap->next=newptr;(12)從單鏈表中刪除表頭元素ElemType DeleteFront(LNode* HL)if(HL->next=HL)cerr<<"Deleteing from an empty list!"<<end1;exit(1);LNode* p=HL->next;HL->next=p->next;ElemType temp=p->data;delete

51、p;return temp;(13)從單鏈表中刪除等于給定值的第一個(gè)元素int Delete(LNode* HL,const ElemType& item)LNode*ap=HL,*cp=HL->next;while(cp!=HL)if(cp->data=item)break;elseap=cp;cp=cp->next;if(cp=HL)cerr<<"Deleted element is not exitst!"<<end1;return 0;elseap->next=cp->next;delete cp;ret

52、urn 1;(14)利用單鏈表進(jìn)行數(shù)據(jù)排序void LinkSort(ElemType a,int n)LNode* head=new LNode;InitList(head);int i;for(i=0;i<n;i+)Insert(head.ai);LNode* p=head->next;i=0;while(p!=head)ai+=p->data;p=p->next;ClearList(head);delete head;*8.對于結(jié)點(diǎn)類型為DNode的雙向鏈表，編寫出下列每一個(gè)算法。向雙向鏈表的未尾插入一個(gè)值為x的結(jié)點(diǎn)。解：void InsertRear(DNode

53、*&DL,ElemType x)/建立值為x的結(jié)點(diǎn)DNode* newptr=new DNode;newptr->data=x;newptr->left=newptr->right=newptr;/當(dāng)鏈表為空時(shí)完成插入if(DL=NULL)DL=newptr;return;/當(dāng)鏈表不為空時(shí)完成插入DNode*p=DL->left;newptr->right=p->right;DL->left=newptr;newptr->left=p;p->right=newptr;向雙向循環(huán)表的第i個(gè)結(jié)點(diǎn)位置插入一個(gè)值為x的結(jié)點(diǎn)。解：void I

54、nsert(DNode*&DL,int i, ElemType x)/i值越界，退出執(zhí)行if(i<=0)cerr<<"i is out range!"<<end1;exit(1);/建立值為x的新結(jié)點(diǎn)DNode*newptr=new DNode;newptr->data=x;newptr->left=newptr->right=newptr;/當(dāng)鏈表為空同時(shí)i等于1時(shí)進(jìn)行插入，i不為1則退出if(DL=NULL)if(i=1)DL=newptr;return;elseout<<"i is rang

55、e!"<<end1;exit(1);/實(shí)現(xiàn)i等于1時(shí)的插入if(i=1)newptr->right=DL;newptr->left=DL->left;DL->left->right=newptr;DL->left=newptr;DL=newptr;return;/查找第i個(gè)結(jié)點(diǎn)int k=1;DNode*p=DL->right;while(p!=DL)k+;if(k=i)break;p=p->right;/i值越界，退出執(zhí)行if(i>k+1)cerr<<"i is out range!"

56、<<end1;exit(1);/把newptr結(jié)點(diǎn)插入到p結(jié)點(diǎn)之前newptr->right=p;newptr->left=p->left;p->left->right=newptr;p->left=newptr;return;從雙向循環(huán)鏈表中刪除值為x的結(jié)點(diǎn)。解：bool Delete(DNode*&DL,ElemType x)if(DL=NULL)return 0;/當(dāng)表頭結(jié)點(diǎn)為x時(shí)則刪除之DNode*p=DL;if(DL->data=x)DL=DL->right;p->left->right=DL;DL->left=p->left;delete p;return 1;/查找值為x的結(jié)點(diǎn)p=p->right;while(p!=DL)if(p->data=x)break;else p=p->right;/不存在值為x的結(jié)點(diǎn)則返回0if(p=DL)return 0;/刪除值為x的結(jié)點(diǎn)p->le