數(shù)據(jù)結構實用教程第二版答案-徐孝凱

1、精選優(yōu)質文檔-傾情為你奉上 第一章緒習 題 一1.有下列幾種用二元組表示的數(shù)據(jù)結構，試畫出它們分別對應的圖形表示（當出現(xiàn)多個關系時，對每個關系畫出相應的結構圖），并指出它們分別屬于何種結構。 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>解：是集合結構；是線性結構；是樹型結構；散列結構。只作為參考。2.設計二次多項式ax2+bx+c的一種抽象數(shù)據(jù)類型，假定起名為QIAdratic,該類型的數(shù)據(jù)部分分為三個系數(shù)項a、b和c，操作部分為：(請寫出下面每一個操作的具體實現(xiàn))。 初始化數(shù)據(jù)成員ab和c(

4、假定用記錄類型Quadratie定義成員)，每個數(shù)據(jù)成員的默認值為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; 做兩個多項式加法,即使對應的系數(shù)相加,并返回相加的結果。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的值計算多項式的值。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ù)值，以便于工作調用函數(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表示)輸出二次多項式，在輸出時要注意去掉系數(shù)為0的項，并且當b和c的值為負時，其前不能出現(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ù)描述下列每一個算法，并分別求出它們的時間復雜度。 比較同一簡單

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

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;其時間復雜度為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的值。解：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;其時間復雜度為O(n) 假定一維數(shù)組an中的每個元素值均在0，200區(qū)間內，分別統(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;/給數(shù)組c5中的每個元素賦初值0for(i=0;i<n;i+)if(ai<0|ai>200)

11、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為引用/形參，它是對應實參的別名，其值由實參帶回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;其時間復雜度為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;elsereturn 0;解：判斷n是否是一個素數(shù)，若是則返回數(shù)值1，否則返回0。該算法的時間復雜度為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;解：計算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的最小i值， 其時間復雜度為O(n1/2)。 void UseFile(ifstream& inp,int c

14、10)/假定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所聯(lián)系的整數(shù)文件中個位值同為i的整數(shù)個數(shù)，時間復雜度為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;解：打印出一個具有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 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，時間復雜度為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;第二章 線性表 習題 二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.解：為了排版方便，假定采用以下輸出格式表示單鏈接表的示意圖；每個括號內的數(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)

20、,(57,7),(79,5),(34,0)3.對于List類型的線性表,編寫出下列每個算法。 從線性表中刪除具有最小值的元素并由函數(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(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個元素并由函數(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.s

22、ize-1;j+)L.listj=L.listj+1;L.size-;return x; 向線性表中第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

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的第一個元素if(L.listi<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.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; 從線性表中刪除所有其值重復的元素，使其所有元素的值均不同，如對于線性表(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;

28、k<L.size;k+)L.listk-1=L.listk;L.size-;elsej+;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指向待處理的結

29、點p=p->next; /p指向下一個待逆序的結點/將q結點插入到已陳序單鏈表的表頭q->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指向其前驅結點int j=1;while(cp!=NULL)if(j=i)break; /cp結點即為第

30、i個結點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ù)返回，若單鏈表為空，則顯示出錯信息并停止運行。解：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)計出單鏈表中結點的值等于給定值x的結點數(shù)。解：int Count(LNode*HL,ElemType x)/統(tǒng)計出單鏈表中結點的值等于給定值x的結點數(shù)int n=0;while(HL!=NULL)if(HL->data=x) n+;HL=

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

33、LL; /HL仍為待建立的有序表的表頭指針，祿始值為空while(p!=NULL) /把原單鏈表中的結點依次進行有序鏈接LNode* q=p; /q指向待處理的結點p=p->next; /p指向下一個待處理的結點LNode* ap=NULL,*cp=HL;/cp指向有序表中待比較的結點，ap指向其前驅結點while(cp!=NULL) /為插入q結點尋找插入位置if(q->data<cp->data)break;elseap=cp;cp=cp->next; /將q結點插入到ap和cpxf hko pp ujq->next=cp;if(ap=NULL)HL=q

34、;elseap->next=q; 將兩個有序單鏈表合并成一個有序單鏈表，合并后使原有單鏈表為空。解：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->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ù)兩個有序單鏈表生成一個新的有序單鏈表，原有單鏈表保持不變。如假定兩個有序單鏈表中的元素為(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ù)兩個有

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

37、p2指針后移newptr->data=p2->data;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->

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

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

40、=NULL;p1=a.next;p2=b.next; /把指向兩個單鏈表的表頭結點的指針分別賦給/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個人開始第一次

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

42、應第一個開始報數(shù)的人LNode*ap=HL,*cp=HL->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結點的值，即出列的人

43、cout<<cp->data<<""/從單鏈表中刪除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ù)類型中定義的每一個操作，寫出結點類

44、型為LNode的帶頭附加結點的循環(huán)單鏈表上實現(xiàn)的對應算法。初始化單鏈表解：void InitList(LNode*HL)HL->next=HL;/將單鏈表置空刪除單鏈表中的所有結點，使之成為一個空表void ClearList(LNode*HL)LNode*cp,*np;cp=HL->next;/將指向第一個結點的指針賦給cpwhile(cp!=HL)/遍歷單鏈表，向系統(tǒng)交回每一個結點。np=cp->next;/保存下一個結點的指針。delete cp;/刪除當前結點。cp=np;/使下一個結點成為當前結點。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個結點中的元素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;從單鏈表查找具有給定值的第一個元素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;更新單鏈表中具有給定值的第一個元素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;向單鏈表的未尾插入一個元素void InsertRear(LNode* HL,const ElemType& item)LNode* newptr;newptr=new LNode;newptr->data=item;/把新元素賦給動態(tài)結點*newptr的值域。LNode* p=HL;while(p->next!=HL)/從表頭開始遍歷到最后一個結點為止。p=p->next;newptr->next=HL;p->next=newptr;/把新結點鏈接到表尾。向單鏈表的表頭插入一個元素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)向單鏈表中插入一個元素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)從單鏈表中刪除等于給定值的第一個元素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)利用單鏈表進行數(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.對于結點類型為DNode的雙向鏈表，編寫出下列每一個算法。向雙向鏈表的未尾插入一個值為x的結點。解：void InsertRear(DNode

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

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

55、e!"<<end1;exit(1);/實現(xiàn)i等于1時的插入if(i=1)newptr->right=DL;newptr->left=DL->left;DL->left->right=newptr;DL->left=newptr;DL=newptr;return;/查找第i個結點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結點插入到p結點之前newptr->right=p;newptr->left=p->left;p->left->right=newptr;p->left=newptr;return;從雙向循環(huán)鏈表中刪除值為x的結點。解：bool Delete(DNode*&DL,ElemType x)if(DL=NULL)return 0;/當表頭結點為x時則刪除之DNode*p=DL;if(DL->data=x)DL=DL->right;p->left->right=DL;DL->left=p->left;delete p;return 1;/查找值為x的結點p=p->right;while(p!=DL)if(p->data=x)break;else p=p->right;/不存在值為x的結點則返回0if(p=DL)return 0;/刪除值為x的結點p->le