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

1、 第一章緒習(xí) 題 一1.有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，試畫出它們分別對(duì)應(yīng)的圖形表示（當(dāng)出現(xiàn)多個(gè)關(guān)系時(shí)，對(duì)每個(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=, C=(K,R)其中K=a,b,c,d,f,g,hR=rr=, 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=,r2=,

2、r3=,解：是集合結(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，操作部分為：(請(qǐng)寫出下面每一個(gè)操作的具體實(shí)現(xiàn))。 初始化數(shù)據(jù)成員ab和c(假定用記錄類型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;

3、q.b=bb;q.c=cc;return q; 做兩個(gè)多項(xiàng)式加法,即使對(duì)應(yīng)的系數(shù)相加,并返回相加的結(jié)果。Quadratic Add(Quadratic q1,Quadratic q2);解：Quadratic 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

4、+q.c); 計(jì)算方程ax2+bx+c=0的兩個(gè)實(shí)數(shù)根，對(duì)于有實(shí)根、無實(shí)根和不是實(shí)根方程(即a=0)這三種情況要返回不同的整數(shù)值，以便于工作調(diào)用函數(shù)做不同的處理。int Root(Quadratic 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;elseretur

5、n 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)。void Print(Quadratic q)解：void Print(Quadratic q)if(q.a) coutq.a0)cout+q.bx;elsecoutq.b0)cout+q.c;elsecoutq.c;coutx2,x1=x2和x1=和x2) return;else if(x1=x2) return =;else return;其時(shí)間復(fù)雜度為O(1) 將一個(gè)字符串中的所有字符按相反方的次序重新放置。解：void Reverse(ch

6、ar*p)int n=strlen(p);for(int i=0;in/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;in;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(int i=1;i=n;i+)p*=x;s+=p/(i+1);re

7、turn 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;i5;i+)ci=0;/給數(shù)組c5中的每個(gè)元素賦初值0for(i=0;in;i+)if(ai200)return 0;/返回?cái)?shù)值0表示數(shù)組中數(shù)據(jù)有錯(cuò)，統(tǒng)計(jì)失敗for(j=0;j5;j+)/查找ai所在區(qū)間if(ai

8、=n和N=n的條件，Lin和Col為引用/形參，它是對(duì)應(yīng)實(shí)參的別名，其值由實(shí)參帶回Lin=0;Col=0;for(int i=0;im;i+)for(int j=0;jaLinCol)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(ix)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;

9、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(sn)s+=+i;return i;解：求出滿足不等式1+2+3.+in的最小i值， 其時(shí)間復(fù)雜度為O(n1/2)。 void UseFile(ifstream& inp,int c10)/假定

10、inp所對(duì)應(yīng)的文件中保存有n個(gè)整數(shù)for(int i=0;ix)i=x%10;ci+;解：利用數(shù)組c10中的每個(gè)元素ci對(duì)應(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+)couti*j=setw(2)i*j;coutend1;解：打印出一個(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

11、;iM;i+)for(int j=0;jN;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;iM;i+)for(j=0;jL;j+)cij=0;for(i=0;iM;i+)for(j=0;jL;j+)for(k=0;kN;k+)cij+=aik*bkj;解：矩陣相乘，即aMNbNLcML，時(shí)間復(fù)雜度為O(MNL)。5.題目略解：void InitSet(Set& s)for(int i=1;i=SETSIZE;i+)s.mi=0;解：v

12、oid InitSet(Set& s,int a,int n)fot(int i=0;in;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 operator(int e

13、lt,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)ostrfor(int i=1;i=SETSIZE;i+)if(s.mi=1)ostri,;ostrend1;return ostr;第二章 線性表 習(xí)題 二1.解：(79,62,34,57,26,48)解：(26,34,48,57,62,79)解：(48,56,57,62,79

14、,34)解：(56,57,79,34)解：(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類型

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

16、tL.size-1;L.size-;return x; 從線性表中刪除第i個(gè)元素并由函數(shù)返回。解：int Deletel(List& L,int i)/從線性表中刪除第i個(gè)元素并由函數(shù)返回if(iL.size)cerrIndex is out range!end1;exit(1);ElemType x;x=L.listi-1;for(int j=i-1;jL.size-1;j+)L.listj=L.listj+1;L.size-;return x; 向線性表中第i個(gè)元素位置插入一個(gè)元素。解：void Inser1(List& L,int i,ElemType x)/向線性表中第i個(gè)元素位置插入

17、一個(gè)元素if(iL.size+1)cerrIndex is out range!end1;exit(1);if(L.size=MaxSize)cerrList overflow!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(iL.size)if(L.listi=x)for(int j=i+1;jL.sizr;j+)L.listj-1=L.listj;L.size-;elsei+;

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

19、while(iL.size)/從有序表L中查找出大于等于s的第一個(gè)元素if(L.listis)i+;else break;if(iL.size)While(i+jL.size)&(L.listi+j=t)j+;/求出s和t之間元素的個(gè)數(shù)for(int k=i+j;kMaxSize)cerrList overflow!end1;exit(1);int i=0,j=0,k=0;while(iL1.size)&(jL2.size)if(L1.listi=L2.listj) /將L1中的元素賦給LL.listk=L1.listi;i+;else /將L2中的元素賦給LL.listk=L2.listj;

20、j+;k+;while(iL1.size) /將L1中剩余的元素賦給LL.listk=L1.listi;i+;k+;while(jL2.size) /將L2中剩余的元素賦給LL.listk=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(iL.size)int j=i+1;while(jL.size) /

21、刪除重復(fù)值為L.listi的所有元素if(L.listj=L.listi)for(int k=j+1;knext; /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(i1|HL=NULL)cerrIndex is out range!next;j+;if(cp=NULL)cerrIndex is out range!next;elseap-next=cp-next;delete cp; 從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回

22、，若單鏈表為空，則顯示出錯(cuò)信息并停止運(yùn)行。解：ElemType MaxValue(LNode*HL)/從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回if(HL=NULL)cerrLinked list is empty!data;LNode*p=HL-next;while(p!=NULL)if(maxdata) 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=

23、x) n+;HL=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=NULL; /HL

24、仍為待建立的有序表的表頭指針，祿始值為空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-datadata)break;elseap=cp;cp=cp-next; /將q結(jié)點(diǎn)插入到ap和cpxf hko pp ujq-next=cp;if(ap=NULL)HL=q;elseap-next=q; 將兩個(gè)有序單鏈表合并成一個(gè)有序單鏈表

25、，合并后使原有單鏈表為空。解：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-datadata)p-next=p1;p1=p1-next;elsep-next=p2;p2=p2-;p=p-next;if(p1!=NULL)p-next=p1;i

26、f(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作為新的有序單鏈表的表頭附加結(jié)點(diǎn)LNode*p=&a; /p指向結(jié)果有序單鏈表的表尾結(jié)點(diǎn)p-next=NULL; /初始指向表頭附加結(jié)點(diǎn)while(p1!=

27、NULL&(p2!=NULL) /處理兩個(gè)表非空時(shí)的情況LNode*newptr=new LNode;if(p1-datadata) /由p1-data建立新結(jié)點(diǎn)，然后p1指針后移newptr-data=p1-data;p1=p1-next;else /由p2-data建立新結(jié)點(diǎn)，然后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;

28、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-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*

29、&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單鏈表的/表尾結(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

30、;t2=newptr;p=p-next;t1-next=t2-next=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è)人的編號(hào)依次為1,2.,n)開始報(bào)數(shù)，則得到的出列次序?yàn)?4,8,5

31、,2,1,3,7,6。此算法要求以n、m和s(假定從第s個(gè)人開始第一次報(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;/從表頭開始順

32、序查找出第s個(gè)結(jié)點(diǎn)，對(duì)應(yīng)第一個(gè)開始報(bào)數(shù)的人LNode*ap=HL,*cp=HL-next;for(i=1;inext;/若cp指向了表頭附加結(jié)點(diǎn)，則仍需后移ap和cp指針，使之指向表頭結(jié)點(diǎn)if(cp=HL)ap=HL;cp=HL-next;/依次使n-1個(gè)人出列for(i=1;in;i+)/順序查找出待出列的人，即為循環(huán)結(jié)束后cp所指向的結(jié)點(diǎn)for(int j=1;jnext;if(cp=HL)ap=HL;cp=HL-next;/輸出cp結(jié)點(diǎn)的值，即出列的人coutdatanext=cp-next;delete cp;/使cp指向被刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)cp=ap-next;/若cp指向了表頭附加

33、結(jié)點(diǎn)，則后移ap和cp指針if(cp=HL)ap=HL;cp=HL-next;/使最后一個(gè)人出列coutnext-datanext;delete HL;7.對(duì)于在線性表抽象數(shù)據(jù)類型中定義的每一個(gè)操作，寫出結(jié)點(diǎn)類型為LNode的帶頭附加結(jié)點(diǎn)的循環(huán)單鏈表上實(shí)現(xiàn)的對(duì)應(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

34、=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 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(pos1)cerrpos is out range!next;

35、int i=0;while(p!=HL)i+;if(i=pos)break;p=p-next;if(p!=HL)return p-data;elsecerrpos is out range!next;while(p!=HL)coutdatanext;coutnext;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(

36、p-data=item)break;else p=p-next;if(p=HL)return 0;else/更新元素p-data=item;return 1;向單鏈表的未尾插入一個(gè)元素void InsertRear(LNode* HL,const ElemType& item)LNode* newptr;newptr=new LNode;newptr-data=item;/把新元素賦給動(dòng)態(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)鏈

37、接到表尾。向單鏈表的表頭插入一個(gè)元素void InsertFront(LNode* 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)i

38、f(itemdata)break;elseap=cp;cp=cp-next;newptr-next=cp;ap-next=newptr;(12)從單鏈表中刪除表頭元素ElemType DeleteFront(LNode* HL)if(HL-next=HL)cerrDeleteing from an empty list!next;HL-next=p-next;ElemType temp=p-data;delete p;return temp;(13)從單鏈表中刪除等于給定值的第一個(gè)元素int Delete(LNode* HL,const ElemType& item)LNode*ap=HL,*

39、cp=HL-next;while(cp!=HL)if(cp-data=item)break;elseap=cp;cp=cp-next;if(cp=HL)cerrDeleted element is not exitst!next=cp-next;delete cp;return 1;(14)利用單鏈表進(jìn)行數(shù)據(jù)排序void LinkSort(ElemType a,int n)LNode* head=new LNode;InitList(head);int i;for(i=0;inext;i=0;while(p!=head)ai+=p-data;p=p-next;ClearList(head);d

40、elete head;*8.對(duì)于結(jié)點(diǎn)類型為DNode的雙向鏈表，編寫出下列每一個(gè)算法。向雙向鏈表的未尾插入一個(gè)值為x的結(jié)點(diǎn)。解：void InsertRear(DNode*&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-r

41、ight=newptr;向雙向循環(huán)表的第i個(gè)結(jié)點(diǎn)位置插入一個(gè)值為x的結(jié)點(diǎn)。解：void Insert(DNode*&DL,int i, ElemType x)/i值越界，退出執(zhí)行if(i=0)cerri is out range!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;elseouti is range!right=DL;newptr-left=DL-left;DL-left-right=newptr;DL-left=newptr;DL=

42、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(ik+1)cerri is out range!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-left-right=p-right;p-right-left=p-left;delete p;return 1;9.假定有一種帶頭附加結(jié)點(diǎn)的鏈表，每個(gè)結(jié)點(diǎn)含三個(gè)域：data、next和range，其中data為整型值域，next和range均為指