《anyview 數(shù)據(jù)結構習題集 第10章答案》由會員分享，可在線閱讀，更多相關《anyview 數(shù)據(jù)結構習題集 第10章答案（78頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、數(shù)據(jù)結構習題集 第1章答案注意：此處代碼可能并非最優(yōu)化結果，等待代碼優(yōu)化中。1.16 試寫一算法，如果三個整數(shù)X，Y和Z的值不是依次非遞增的，則通過交換，令其為非遞增。要求實現(xiàn)下列函數(shù)：void Descend(int &x, int &y, int &z);/* 按從大到小順序返回x，y和z的值 */void Descend(int &x, int &y, int &z)/* 按從大到小順序返回x，y和z的值 */ int temp; if(xy)temp=x;x=y;y=temp; if(xz)temp=x;x=z;z=temp; if(yz)temp=y;y=z;z=temp;1.17

2、已知k階裴波那契序列的定義為f0=0, f1=0, , fk-2=0, fk-1=1;fn=fn-1+fn-2+fn-k, n=k,k+1,試編寫求k階裴波那契序列的第m項值的函數(shù)算法，k和m均以值調用的形式在函數(shù)參數(shù)表中出現(xiàn)。要求實現(xiàn)下列函數(shù)：Status Fibonacci(int k, int m, int &f);/* 如果能求得k階斐波那契序列的第m項的值f，則返回OK；*/* 否則（比如，參數(shù)k和m不合理）返回ERROR */Status Fibonacci(int k, int m, int &f) /* 求k階斐波那契序列的第m項的值f */ /沒想到m竟然是從0開始的 int

3、 i; long temp; int a1000; if(k=1|m0)return ERROR; for(i=0;ik-1;i+)ai=0; ai=1; ak=1; for(temp=1,i=k+1;iMAXINT) return ERROR; temp=temp-ai-k-1+ai-1; ai=temp; f=am; return OK; 1.18 假設有A、B、C、D、E五個高等院校進行田徑對抗賽，各院校的單項成績均以存入計算機并構成一張表，表中每一行的形式為項目名稱 性別 校名 成績 得分編寫算法，處理上述表格，以統(tǒng)計各院校的男、女總分和團體總分，并輸出。要求實現(xiàn)下列函數(shù)：void S

4、cores(ResultType *result, ScoreType *score);/* 求各校的男、女總分和團體總分, 并依次存入數(shù)組score */* 假設比賽結果已經(jīng)儲存在result 數(shù)組中, */* 并以特殊記錄 “”, male, , “”, 0 （域scorce=0）*/* 表示結束 */相關數(shù)據(jù)類型定義如下：typedef enum female,male Sex;typedef structchar *sport; / 項目名稱Sex gender; / 性別（女：female；男：male）char schoolname; / 校名為A,B,C,D或Echar *res

5、ult; / 成績int score; / 得分（7,5,4,3,2或1） ResultType;typedef structint malescore; / 男子總分int femalescore; / 女子總分int totalscore; / 男女團體總分 ScoreType;void Scores(ResultType *result, ScoreType *score) /* 求各校的男、女總分和團體總分, 并依次存入數(shù)組score */ /* 假設比賽結果已經(jīng)儲存在result 數(shù)組中, */ /* 并以特殊記錄 , male, , , 0 （域scorce=0）*/ /* 表示結

6、束 */ /感覺這道題題意有點模糊. int i,j; for(j=0;jARRSIZE或對某個k(1kn)使k!2kMAXINT時，應按出錯處理。注意選擇你認為較好的出錯處理方法。要求實現(xiàn)下列函數(shù)：Status Series(int ARRSIZE, int a);/* 求i!*2i序列的值并依次存入長度為ARRSIZE的數(shù)組a； */* 若所有值均不超過MAXINT，則返回OK，否則返回OVERFLOW */Status Series(int ARRSIZE, int a) /* 求i!*2i序列的值并依次存入長度為ARRSIZE的數(shù)組a； */ /* 若所有值均不超過MAXINT，則返回

7、OK，否則返回OVERFLOW */ int i=1,temp=1; while(i=ARRSIZE) if(MAXINT/temp2*i)return OVERFLOW; temp*=2; temp*=i; ai-1=temp; +i; return OK; 1.20 試編寫算法求一元多項式P(x) = a0 + a1x + a2x2 + + anxn的值P(x0)，并確定算法中每一語句的執(zhí)行次數(shù)和整個算法的時間復雜度。注意選擇你認為較好的輸入和輸出方法。要求實現(xiàn)下列函數(shù)：float Polynomial(int n, int a, float x0);/* 求一元多項式的值P(x0)。 *

8、/* 數(shù)組a的元素ai為i次項的系數(shù)，i=0,1,n */float Polynomial(int n, int a, float x) /* 求一元多項式的值P(x)。 */ /* 數(shù)組a的元素ai為i次項的系數(shù)，i=0,.,n */ int i=1; float temp=1; float total=a0; if(0=n)return total; while(i=n) temp*=x; total+=ai*temp; +i; return total; 數(shù)據(jù)結構習題集 第2章答案2.11 設順序表L中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到L的適當位置上，并保持該表的有序性。要求實現(xiàn)

9、下列函數(shù)：void InsertOrderList(SqList &L, ElemType x)/* 在有序的順序表 L 中保序插入數(shù)據(jù)元素 x */順序表類型定義如下：typedef struct ElemType *elem;int length;int listsize; SqList;void InsertOrderList(SqList &L, ElemType x) / 在有序的順序表 L 中保序插入數(shù)據(jù)元素 x ElemType *p,*q; p=L.elem; while(*px&p=p;q-) *(q+1)=*q; *p=x; +L.length; 2.12 設A=(a1,a

10、m)和B=(b1,bn)均為有序順序表，A和B分別為A和B中除去最大共同前綴后的子表（例如，A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，則兩者中最大的共同前綴為(x,y,y,z)， 在兩表中除去最大共同前綴后的子表分別為A=(x,z)和B=(y,x,x,z)）。若A=B=空表，則A=B；若A=空表，而B 空表，或者兩者均不為空表，且A的首元小于B的首元，則AB。試寫一個比較A和B大小的算法。（注意：在算法中，不要破壞原表A和B，也不一定先求得A和B才進行比較）。要求實現(xiàn)下列函數(shù)：char Compare(SqList A, SqList B);/* 比較順序表A和B

11、, */* 返回, 若Ab; *= /* =, 若A=B; */* , 若AB */順序表類型定義如下：typedef struct ElemType *elem;int length;int listsize; SqList;char Compare(SqList A, SqList B) / 比較順序表A和B, / 返回, 若A, 若AB char a,b; int la=1,lb=1; while(la=A.length&lb*(B.elem+lb-1)return ; else if(*(A.elem+la-1)*(B.elem+lb-1)return ; +la; +lb; if(A

12、.length=B.length) return =; /此處應先判斷長度是否相等！ if(la=A.length+1)return ; 2.13 試寫一算法在帶頭結點的單鏈表結構上實現(xiàn)線性表操作Locate(L,x)。實現(xiàn)下列函數(shù)：LinkList Locate(LinkList L, ElemType x);/ If x in the linked list whose head node is pointed/ by L, then return pointer pointing node x,/ otherwise return NULL單鏈表類型定義如下：typedef struct

13、 LNode ElemType data;struct LNode *next; LNode, *LinkList;LinkList Locate(LinkList &L, ElemType x) / If x in the linked list whose head node is pointed / by L, then return pointer ha pointing node x, / otherwise return NULL LinkList p=L-next; while(p) if(x=p-data) return p; p=p-next; return NULL; 2.

14、14 試寫一算法在帶頭結點的單鏈表結構上實現(xiàn)線性表操作Length(L)。實現(xiàn)下列函數(shù)：int Length(LinkList L);/ Return the length of the linked list/ whose head node is pointed by L單鏈表類型定義如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;int Length(LinkList L) / Return the length of the linked list / whose head node i

15、s pointed by L int i=0; LinkList p=L; while(p-next) +i; p=p-next; return i; 2.17 試寫一算法，在無頭結點的動態(tài)單鏈表上實現(xiàn)線性表操作INSERT(L,i,b)，并和在帶頭結點的動態(tài)單鏈表上實現(xiàn)相同操作的算法進行比較。實現(xiàn)下列函數(shù)：void Insert(LinkList &L, int i, ElemType b);單鏈表類型定義如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;/思路不是很清晰，很多細節(jié)問題，調試了很

16、長時間 /主要考慮問題：1、i為0或負數(shù)時 2、i在鏈表長度內 3、i為鏈表長度+1時 4、代碼精簡 void Insert(LinkList &L, int i, ElemType b) int j,count; LinkList p=L,q=L; if(inext; if(1=i) p=(LinkList)malloc(sizeof(LNode); p-data=b; p-next=L; L=p; else if (i1&i=count+1) for(p=L,j=1;jnext; p=(LinkList)malloc(sizeof(LNode); p-data=b; p-next=q-ne

17、xt; q-next=p; 2.18 同2.17題要求。試寫一算法，實現(xiàn)線性表操作DELETE(L,i)。實現(xiàn)下列函數(shù)：void Delete(LinkList &L, int i);單鏈表類型定義如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;void Delete(LinkList &L, int i) int j; int count=0; LinkList p=L,q; /1、求鏈表長度 while(p) p=p-next; +count; /2、查找第i-1號元素 /特殊位置首位、末尾

18、 p=L; if(1=i) L=p-next; free(p); /i=0時沒問題 else if(i1&i=count) for(p=L,j=1;jnext; q=p-next; p-next=q-next; free(q); 2.20 同2.19題條件，試寫一高效的算法，刪除表中所有值相同的多余元素 (使得操作后的線性表中所有元素的值均不相同) 同時釋放被刪結點空間，并分析你的算法的時間復雜度。實現(xiàn)下列函數(shù)：void Purge(LinkList &L);單鏈表類型定義如下：typedef struct LNodeElemType data;struct LNode *next; LNod

19、e, *LinkList;void Purge(LinkList &L) ElemType last=L-next-data; LinkList q=L-next,p=L-next; while(p) if(last=p-data&p!=L-next) q-next=p-next; free(p); p=q; else last=p-data; q=p; p=p-next; 2.21 試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表(a1,a2,an)逆置為(an,an-1,a1)。實現(xiàn)下列函數(shù)：void Inverse(SqList &L);順序表類型定義如下：typedef

20、struct ElemType *elem;int length;int listsize; SqList;void Inverse(SqList &L) int i; ElemType *p,temp; p=L.elem; for(i=0;inext; /保存首元素地址 last=L-next;/上一個指針 cur=L-next; /當前操作的指針 if(cur) while(cur)/此處沒注意，寫成了！cur，大意失荊州??！ cur=L-next; L-next=cur-next; cur-next=last; if(cur)last=cur; L-next=last; q-next=N

21、ULL; 2.23 設線性表A=(a1,am), B=(b1,bn)，試寫一個按下列規(guī)則合并A、B為線性表C的算法，即使得C=(a1,b1,am,bm,bm+1,bn) 當mn時；或者 C=(a1,b1,an,bn,an+1,am) 當mn時。線性表A、B和C均以單鏈表作存儲結構，且C表利用A表和B表中的結點空間構成。注意：單鏈表的長度值m和n均未顯式存儲。實現(xiàn)下列函數(shù)：void Merge(LinkList ha, LinkList hb, LinkList &hc)/* 依題意，合并帶頭結點的單鏈表ha和hb為hc */單鏈表類型定義如下：typedef struct LNodeElemT

22、ype data;struct LNode *next; LNode, *LinkList;void Merge(LinkList ha, LinkList hb, LinkList &hc) /* 依題意，合并帶頭結點的單鏈表ha和hb為hc */ LinkList cur_a,cur_b,cur_c; cur_a=ha-next; cur_b=hb-next; cur_c=ha;/這里要注意給cur_c賦值，不然地址為空 while(cur_a&cur_b) cur_c-next=cur_a;/Lc的next指向a; cur_c=cur_c-next;/cur_c指向c-next cur_

23、a=cur_a-next;/cur_a指向a-next cur_c-next=cur_b;/cur_c的next指向b cur_c=cur_c-next;/cur_c指向b cur_b=cur_b-next;/cur_b指向b-next if(cur_a) cur_c-next=cur_a; if(cur_b) cur_c-next=cur_b; hc=ha; 2.24 假設有兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲結構，請編寫算法將A表和B表歸并成一個按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表C， 并要求利用原表（即A表和B表）的結點空間構造C表。

24、實現(xiàn)下列函數(shù)：void Union(LinkList &lc, LinkList la, LinkList lb);/* 依題意，利用la和lb原表的結點空間構造lc表 */單鏈表類型定義如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;void Union(LinkList &lc, LinkList &la, LinkList &lb) LinkList temp,last,q; if(la-next-datanext-data) q=la-next;last=la-next; else q=

25、lb-next;last=lb-next; while(la-next&lb-next) if(la-next-datanext-data) temp=la-next; la-next=temp-next; temp-next=last; last=temp; else temp=lb-next; lb-next=temp-next; temp-next=last; last=temp; / while(la-next) temp=la-next; la-next=temp-next; temp-next=last; last=temp; while(lb-next) temp=lb-next

26、; lb-next=temp-next; temp-next=last; last=temp; q-next=NULL; lc=la; lc-next=temp; 2.31 假設某個單向循環(huán)鏈表的長度大于1，且表中既無頭結點也無頭指針。已知s為指向鏈表中某個結點的指針，試編寫算法在鏈表中刪除指針s所指結點的前驅結點。實現(xiàn)下列函數(shù)：ElemType DeleteNode(LinkList s);/* 刪除指針s所指結點的前驅結點，并返回被刪結點的元素值 */單鏈表類型定義如下：typedef struct LNodeElemType data;struct LNode *next; LNode,

27、 *LinkList;ElemType DeleteNode(LinkList s) /* 刪除指針s所指結點的前驅結點，并返回被刪結點的元素值 */ ElemType e; LinkList p,temp=s; while(temp-next-next!=s) temp=temp-next; e=temp-next-data; p=temp-next; temp-next=s; free(p); return e; 2.32 已知有一個單向循環(huán)鏈表，其每個結點中含三個域：prev、data和next，其中data為數(shù)據(jù)域，next為指向后繼結點的指針域，prev也為指針域，但它的值為空(NU

28、LL)，試編寫算法將此單向循環(huán)鏈表改為雙向循環(huán)鏈表，即使prev成為指向前驅結點的指針域。實現(xiàn)下列函數(shù)：void PerfectBiLink(BiLinkList &CL);雙向循環(huán)鏈表類型定義如下：typedef struct BiNode ElemType data;int freq; / 2.38題用struct BiNode *prev,*next; BiNode, *BiLinkList;void PerfectBiLink(BiLinkList &CL) BiLinkList p; p=CL; p-next-prev=p; p=p-next; while(p!=CL) p-next

29、-prev=p; p=p-next; 2.33 已知由一個線性鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如：字母字符、數(shù)字字符和其它字符），試編寫算法將該線性鏈表分割為三個循環(huán)鏈表，其中每個循環(huán)鏈表表示的線性表中均只含一類字符。實現(xiàn)下列函數(shù)：void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll);單鏈表類型定義如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;void Split(LinkList &lc, LinkLis

30、t &ld, LinkList &lo, LinkList ll) LinkList p,cur_c,cur_d,cur_o; p=ll-next; cur_c=lc; cur_d=ld; cur_o=lo; while(p) if(p-data=A&p-datanext=p; cur_c=cur_c-next; else if(p-data=0&p-datanext=p; cur_d=cur_d-next; else cur_o-next=p; cur_o=cur_o-next; p=p-next; cur_c-next=lc; cur_d-next=ld; cur_o-next=lo; 2

31、.37 設以帶頭結點的雙向循環(huán)鏈表表示的線性表L=(a1,a2,an)。試寫一時間復雜度為O(n)的算法，將L改造為L=(a1,a3,an,a4,a2)。實現(xiàn)下列函數(shù)：void ReverseEven(BiLinkList &L);雙向循環(huán)鏈表類型定義如下：typedef struct BiNode ElemType data;int freq; / 2.38題用struct BiNode *prev,*next; BiNode, *BiLinkList;void ReverseEven(BiLinkList &L) BiLinkList last,p,temp; int count=0; /

32、用count計結點個數(shù) p=L-next; /p指向第一個元素 while(p!=L-prev)/求鏈表長度-1 +count; p=p-next; last=p;/獲得最后一個元素的地址 if(count=2) p=p-prev; while(p!=L-next)/當p指向的不是第一個元素時 if(0=count%2)/判斷是否序號為偶數(shù)的結點 temp=p; p=p-prev; temp-prev-next=temp-next; temp-next-prev=temp-prev; last-next=temp; temp-prev=last; last=temp; else/奇號結點則繼續(xù)

33、往前 p=p-prev; -count; last-next=L;/構建循環(huán) L-prev=last;/構建循環(huán) 2.39 試對稀疏多項式Pn(x)采用存儲量同多項式項數(shù)m成正比的順序存儲結構，編寫求Pn(x0)的算法（x0為給定值），并分析你的算法的時間復雜度。實現(xiàn)下列函數(shù)：float Evaluate(SqPoly pn, float x);/* pn.datai.coef 存放ai， */* pn.datai.exp存放ei (i=1,2,m) */* 本算法計算并返回多項式的值。不判別溢出。 */* 入口時要求0e1e2.em，算法內不對此再作驗證* 多項式的順序存儲結構:typede

34、f struct int coef;int exp; PolyTerm;typedef struct PolyTerm *data;int length; SqPoly;float Evaluate(SqPoly pn, float x) /* pn.datai.coef 存放ai， */ /* pn.datai.exp存放ei (i=1,2,.,m) */ /* 本算法計算并返回多項式的值。不判別溢出。 */ /* 入口時要求0e1e2.em，算法內不對此再作驗證*/ int i=0,j=1,cur;/沒想到這題目的數(shù)據(jù)i是從零開始的。 float total=0,temp=1; while

35、(ipn.length) for(cur=pn.datai.exp;jnext,last=pa-next,tail=pa-next; if(pa-next)/此處改為cur時遇到空表會出錯，不知道為什么 if(0=last-exp)cur=cur-next;last-coef=0; while(cur!=pa) last-coef=cur-coef*(cur-exp); last-exp=cur-exp-1; tail=last; last=last-next; cur=cur-next; if(cur=last-next)free(last);tail-next=pa; 數(shù)據(jù)結構習題集 第3

36、章答案3.17 試寫一個算法，識別依次讀入的一個以為結束符的字符序列是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是屬該模式的字符序列，而1+3&3-1則不是。實現(xiàn)下列函數(shù):Status match(char *str);/* 若str是屬該模式的字符序列，*/* 則返回TRUE，否則返回FALSE */Stack是一個已實現(xiàn)的棧?？墒褂玫南嚓P類型和函數(shù)：typedef char SElemType; / 棧Stack的元素類型Status InitStack(Stack &s);Status Push(Stack &s

37、, SElemType e);Status Pop(Stack &s, SElemType &e);Status StackEmpty(Stack s);Status GetTop(Stack s, SElemType &e);Status match(char *str) /* 若str是屬該模式的字符序列，*/ /* 則返回TRUE，否則返回FALSE */ /文檔沒有說明字符串是以結尾的 /也沒有說棧的類型是SqStack，用Stack時編譯出錯 SqStack s; SElemType c; Status flag=1; InitStack(s); char *cur=str; whi

38、le(&!=*cur) Push(s,*cur); +cur; /入棧 +cur; if(!GetTop(s,c)&*cur!=)flag=0;/判斷?？?while(*cur!= ) Pop(s,c); if(c!=*cur)flag=0;break; +cur; /依次出棧匹配 if(GetTop(s,c)flag=0;/再次判斷是否非空 return flag; 3.18 試寫一個判別表達式中開、閉括號是否配對出現(xiàn)的算法。實現(xiàn)下列函數(shù)：Status MatchCheck(SqList exp);/* 順序表exp表示表達式； */* 若exp中的括號配對，則返回TRUE，否則返回FALS

39、E */* 注：本函數(shù)不使用棧 */順序表類型定義如下：typedef struct ElemType *elem;int length;int listsize; SqList; / 順序表Status MatchCheck(SqList exp) /* 順序表exp表示表達式； */ /* 若exp中的括號配對，則返回TRUE，否則返回FALSE */ /* 注：本函數(shù)不使用棧 */ /*/ / 此題top指針和cur指針要很仔細地運用，還有判錯條件也要小心 ElemType *cur,*top,*base; base=exp.elem;/模擬棧底 top=cur=base+1;/模擬棧頂

40、(top)和當前元素(cur) if()=*cur) return FALSE; /判斷第一個字符是否為右括號 if(0=exp.length) return TRUE; /判斷是否為空順序表 while(cur=base+exp.length-1)/依次遍歷 if(=*cur)/當元素為左括號時 if(top!=cur) *top=*cur; *cur=0; +top; /top始終指向第二個元素 / else if()=*cur) if(top=base) return FALSE; if(=*(top-1) *(-top)=0; *cur=0; / +cur; if(0=*base)return TRUE;/此處應為base，而不是top return FALSE