anyview 數(shù)據(jù)結(jié)構(gòu)習(xí)題集 第10章答案

《anyview 數(shù)據(jù)結(jié)構(gòu)習(xí)題集 第10章答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《anyview 數(shù)據(jù)結(jié)構(gòu)習(xí)題集 第10章答案（78頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題集 第1章答案 注意：此處代碼可能并非最優(yōu)化結(jié)果，等待代碼優(yōu)化中。。。。 ◆1.16② 試寫一算法，如果三個(gè)整數(shù)X，Y和Z 的值不是依次非遞增的，則通過交換，令其為 非遞增。 要求實(shí)現(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(x

2、 if(x

3、，參數(shù)k和m不合理）返回ERROR */ Status Fibonacci(int k, int m, int &f) /* 求k階斐波那契序列的第m項(xiàng)的值f */ //沒想到m竟然是從0開始的∵ ∵ { int i; long temp; int a[1000]; if(k<=1||m<0){return ERROR;} for(i=0;i

4、;i<=m;++i){ if(temp>MAXINT) return ERROR; temp=temp-a[i-k-1]+a[i-1]; a[i]=temp; } f=a[m]; return OK; } ? 1.18③ 假設(shè)有A、B、C、D、E五個(gè)高等院校進(jìn)行田徑對抗賽， 各院校的單項(xiàng)成績均以存入計(jì)算機(jī)并構(gòu)成一張表，表中每一 行的形式為 項(xiàng)目名稱 性別 校名 成績 得分 編寫算法，處理上述表格，以統(tǒng)計(jì)各院校的男

5、、女總分和團(tuán) 體總分，并輸出。 要求實(shí)現(xiàn)下列函數(shù)： void Scores(ResultType *result, ScoreType *score); /* 求各校的男、女總分和團(tuán)體總分, 并依次存入數(shù)組score */ /* 假設(shè)比賽結(jié)果已經(jīng)儲(chǔ)存在result[ ]數(shù)組中, */ /* 并以特殊記錄 {“”, male, ‘ ‘, “”, 0 }（域scorce=0）*/ /* 表示結(jié)束 */ 相關(guān)數(shù)據(jù)類型定義如下： typedef enum {female,male} Sex; typedef struct{ char *sport; // 項(xiàng)目名稱 Sex

6、gender; // 性別（女：female；男：male） char schoolname; // 校名為’A',’B',’C',’D'或’E’ char *result; // 成績 int score; // 得分（7,5,4,3,2或1） } ResultType; typedef struct{ int malescore; // 男子總分 int femalescore; // 女子總分 int totalscore; // 男女團(tuán)體總分 } ScoreType; void Scores(ResultType *result, ScoreType *scor

7、e) /* 求各校的男、女總分和團(tuán)體總分, 并依次存入數(shù)組score */ /* 假設(shè)比賽結(jié)果已經(jīng)儲(chǔ)存在result[ ]數(shù)組中, */ /* 并以特殊記錄 {"", male, ' ', "", 0 }（域scorce=0）*/ /* 表示結(jié)束 */ //感覺這道題題意有點(diǎn)模糊.... { int i,j; for(j=0;j<5;++j){ i=0; score[j].mal

8、escore=0; score[j].femalescore=0; while(result[i].score!=0) { if('A'+j==result[i].schoolname){ if(male==result[i].gender) score[j].malescore+=result[i].score; if(female==result[i].gender)

9、 score[j].femalescore+=result[i].score; } score[j].totalscore=score[j].malescore+score[j].femalescore; ++i; } } } ? ? ◆1.19④ 試編寫算法，計(jì)算i!×2^i的值并存入數(shù)組 a[0..ARRSIZE-1]的第i-1個(gè)分量中 (i=1,2,…,n)。 假設(shè)計(jì)算機(jī)中允許的整數(shù)最大值為MAXINT

10、，則當(dāng)n> ARRSIZE或?qū)δ硞€(gè)k(1≤k≤n)使k!×2^k>MAXINT時(shí)，應(yīng) 按出錯(cuò)處理。注意選擇你認(rèn)為較好的出錯(cuò)處理方法。 要求實(shí)現(xiàn)下列函數(shù)： Status Series(int ARRSIZE, int a[]); /* 求i!*2^i序列的值并依次存入長度為ARRSIZE的數(shù)組a； */ /* 若所有值均不超過MAXINT，則返回OK，否則返回OVERFLOW */ Status Series(int ARRSIZE, int a[]) /* 求i!*2^i序列的值并依次存入長度為ARRSIZE的數(shù)組a； */ /* 若所有值均不超過MAXIN

11、T，則返回OK，否則返回OVERFLOW */ { int i=1,temp=1; while(i<=ARRSIZE){ if(MAXINT/temp<2*i)return OVERFLOW; temp*=2; temp*=i; a[i-1]=temp; ++i; } return OK; } ? ◆1.20④ 試編寫算法求一元多項(xiàng)式 P(x) = a0 + a1x + a2x^2 + … + anx^n

12、的值P(x0)，并確定算法中每一語句的執(zhí)行次數(shù)和整個(gè)算法 的時(shí)間復(fù)雜度。注意選擇你認(rèn)為較好的輸入和輸出方法。 要求實(shí)現(xiàn)下列函數(shù)： float Polynomial(int n, int a[], float x0); /* 求一元多項(xiàng)式的值P(x0)。 */ /* 數(shù)組a的元素a[i]為i次項(xiàng)的系數(shù)，i=0,1,…,n */ float Polynomial(int n, int a[], float x) /* 求一元多項(xiàng)式的值P(x)。 */ /* 數(shù)組a的元素a[i]為i次項(xiàng)的系數(shù)，i=0,...,n */ {

13、 int i=1; float temp=1; float total=a[0]; if(0==n){return total;} while(i<=n){ temp*=x; total+=a[i]*temp; ++i; } return total; } 數(shù)據(jù)結(jié)構(gòu)習(xí)題集 第2章答案 ◆2.11② 設(shè)順序表L中的數(shù)據(jù)元素遞增有序。 試寫一算法，將x插入到L的適當(dāng)位置上，并保

14、 持該表的有序性。 要求實(shí)現(xiàn)下列函數(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

15、; while(*p

16、stsize+=10; } for(q=L.elem+L.length-1;q>=p;q--){ *(q+1)=*q; } *p=x; ++L.length; } ? ◆2.12③ 設(shè)A=(a1,…,am)和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,

17、x,x,z)）。若A’=B’=空表， 則A=B；若A’=空表，而B’≠ 空表，或者兩者均不為空表， 且A’的首元小于B’的首元，則AB。試寫一個(gè)比 較A和B大小的算法。（注意：在算法中，不要破壞原表A 和B，也不一定先求得A’和B’才進(jìn)行比較）。 要求實(shí)現(xiàn)下列函數(shù)： char Compare(SqList A, SqList B); /* 比較順序表A和B, */ /* 返回’<', 若A?/* '=', 若A=B; */ /* '>‘, 若A>B */ 順序表類型定義如下： typedef struct { ElemTyp

18、e *elem; int length; int listsize; } SqList; char Compare(SqList A, SqList B) // 比較順序表A和B, // 返回'<', 若A', 若A>B { char a,b; int la=1,lb=1; while(la<=A.length&&lb<=B.length){ if(*(A.elem+la-1)>*(B.elem+lb-1))

19、{return '>';} else if(*(A.elem+la-1)<*(B.elem+lb-1)){return '<';} ++la; ++lb; } if(A.length==B.length) return '='; //此處應(yīng)先判斷長度是否相等！！ if(la==A.length+1){return '<';} if(lb==B.length+1){return '>';} } ? 2.13② 試寫一算法在帶

20、頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作 Locate(L,x)。 實(shí)現(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 LNode { ElemType data; struct LNode *next; } LNode

21、, *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){

22、 return p; } p=p->next; } return NULL; } ? 2.14② 試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表 操作Length(L)。 實(shí)現(xiàn)下列函數(shù)： int Length(LinkList L); // Return the length of the linked list // whose head node is pointed by ‘L’ 單鏈表類型定義如下： typedef struct LNode{ Elem

23、Type data; struct LNode *next; } LNode, *LinkList; int Length(LinkList L) // Return the length of the linked list // whose head node is pointed by 'L' { int i=0; LinkList p=L; while(p->next){ ++i; p=p->next; } return i; }

24、 ? 2.17② 試寫一算法，在無頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn) 線性表操作INSERT(L,i,b)，并和在帶頭結(jié)點(diǎn)的動(dòng)態(tài)單 鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比較。 實(shí)現(xiàn)下列函數(shù)： void Insert(LinkList &L, int i, ElemType b); 單鏈表類型定義如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList; //思路不是很清晰，很多細(xì)節(jié)問題，調(diào)試了很長時(shí)間 //主要考慮問題：1、i為0或負(fù)數(shù)時(shí) 2、i在鏈表長度內(nèi) 3、i為鏈表長度+

25、1時(shí) 4、代碼精簡 void Insert(LinkList &L, int i, ElemType b) { int j,count; LinkList p=L,q=L; if(i<0){exit(OVERFLOW);} for(count=0;p!=NULL;++count){ p=p->next; } if(1==i){ p=(LinkList)malloc(sizeof(LNode)); p->data=b;

26、 p->next=L; L=p; } else if (i>1&&i<=count+1){ for(p=L,j=1;j<=i-1&&p;++j){ q=p;//p為第j個(gè)元素的指針，q為p的j-1個(gè)指針 p=p->next; } p=(LinkList)malloc(sizeof(LNode)); p->data=b; p->next=q->

27、next; q->next=p; } } ? 2.18② 同2.17題要求。試寫一算法， 實(shí)現(xiàn)線性表操作DELETE(L,i)。 實(shí)現(xiàn)下列函數(shù)： void Delete(LinkList &L, int i); 單鏈表類型定義如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList; void Delete(LinkList &L, int i) { int j; int count=0;

28、 LinkList p=L,q; //1、求鏈表長度 while(p){ p=p->next; ++count; } //2、查找第i-1號元素 //特殊位置首位、末尾 p=L; if(1==i){ L=p->next; free(p); } //i==0時(shí)沒問題 else if(i>1&&i<=count) { for(p=L,j=1;j

29、{ p=p->next; } q=p->next; p->next=q->next; free(q); } } ? 2.20② 同2.19題條件，試寫一高效的算法，刪除表中所 有值相同的多余元素 (使得操作后的線性表中所有元素的 值均不相同) 同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法的 時(shí)間復(fù)雜度。 實(shí)現(xiàn)下列函數(shù)： void Purge(LinkList &L); 單鏈表類型定義如下： typedef struct

30、LNode{ ElemType data; struct LNode *next; } LNode, *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);

31、p=q; } else {last=p->data;} q=p; p=p->next; } } ? ◆2.21③ 試寫一算法，實(shí)現(xiàn)順序表的就地逆置， 即利用原表的存儲(chǔ)空間將線性表(a1,a2,…,an) 逆置為(an,an-1,…,a1)。 實(shí)現(xiàn)下列函數(shù)： void Inverse(SqList &L); 順序表類型定義如下： typedef struct { ElemType *elem; int lengt

32、h; int listsize; } SqList; void Inverse(SqList &L) { int i; ElemType *p,temp; p=L.elem; for(i=0;i

33、③ 試寫一算法，對單鏈表實(shí)現(xiàn)就地逆置。 實(shí)現(xiàn)下列函數(shù)： void Inverse(LinkList &L); /* 對帶頭結(jié)點(diǎn)的單鏈表L實(shí)現(xiàn)就地逆置 */ 單鏈表類型定義如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList; void Inverse(LinkList &L) /* 對帶頭結(jié)點(diǎn)的單鏈表L實(shí)現(xiàn)就地逆置 */ { LinkList last,cur,q; q=L->next; //保存首元素地址 la

34、st=L->next;//上一個(gè)指針 cur=L->next; //當(dāng)前操作的指針 if(cur){ while(cur){//此處沒注意，寫成了！cur，大意失荊州啊！ cur=L->next; L->next=cur->next; cur->next=last; if(cur){last=cur;} } L->next=last; q->nex

35、t=NULL; } } ? 2.23③ 設(shè)線性表A=(a1,…,am), B=(b1,…,bn)，試寫 一個(gè)按下列規(guī)則合并A、B為線性表C的算法，即使得 C=(a1,b1,…,am,bm,bm+1,…,bn) 當(dāng)m≤n時(shí)； 或者 C=(a1,b1,…,an,bn,an+1,…,am) 當(dāng)m＞n時(shí)。 線性表A、B和C均以單鏈表作存儲(chǔ)結(jié)構(gòu)，且C表利用A表和 B表中的結(jié)點(diǎn)空間構(gòu)成。注意：單鏈表的長度值m和n均未 顯式存儲(chǔ)。 實(shí)現(xiàn)下列函數(shù)： void Merge(LinkList ha, LinkList hb, LinkList &hc) /* 依

36、題意，合并帶頭結(jié)點(diǎn)的單鏈表ha和hb為hc */ 單鏈表類型定義如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList; void Merge(LinkList ha, LinkList hb, LinkList &hc) /* 依題意，合并帶頭結(jié)點(diǎn)的單鏈表ha和hb為hc */ { LinkList cur_a,cur_b,cur_c; cur_a=ha->next; cur_b=hb->next;

37、 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_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=cu

38、r_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④ 假設(shè)有兩個(gè)按元素值遞增有序排列的線性表 A和B，均以單鏈表作存儲(chǔ)結(jié)構(gòu)，請編寫算法將A表和B表 歸并成一個(gè)按元素值遞減有序（即非遞增有序，允許表 中含有值相同的元素）排列的線性表C， 并要求利用原 表（即A表和B表）的結(jié)點(diǎn)空間構(gòu)

39、造C表。 實(shí)現(xiàn)下列函數(shù)： void Union(LinkList &lc, LinkList la, LinkList lb); /* 依題意，利用la和lb原表的結(jié)點(diǎn)空間構(gòu)造lc表 */ 單鏈表類型定義如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList; void Union(LinkList &lc, LinkList &la, LinkList &lb) { LinkList temp,last,q; if(la->next-

40、>data<=lb->next->data){ q=la->next;last=la->next; } else { q=lb->next;last=lb->next; } while(la->next&&lb->next){ if(la->next->data<=lb->next->data){ temp=la->next; la->next=temp->next; temp->ne

41、xt=last; last=temp; } else{ temp=lb->next; lb->next=temp->next; temp->next=last; last=temp; } } // while(la->next){ temp=la->nex

42、t; la->next=temp->next; temp->next=last; last=temp; } while(lb->next){ temp=lb->next; lb->next=temp->next; temp->next=last; last=temp; } q->next=NULL; lc=la; l

43、c->next=temp; } ? 2.31② 假設(shè)某個(gè)單向循環(huán)鏈表的長度大于1，且表 中既無頭結(jié)點(diǎn)也無頭指針。已知s為指向鏈表中某個(gè) 結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié) 點(diǎn)的前驅(qū)結(jié)點(diǎn)。 實(shí)現(xiàn)下列函數(shù)： ElemType DeleteNode(LinkList s); /* 刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，并返回被刪結(jié)點(diǎn)的元素值 */ 單鏈表類型定義如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList; ElemType DeleteNo

44、de(LinkList s) /* 刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，并返回被刪結(jié)點(diǎn)的元素值 */ { 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

45、.32② 已知有一個(gè)單向循環(huán)鏈表，其每個(gè)結(jié)點(diǎn)中 含三個(gè)域：prev、data和next，其中data為數(shù)據(jù)域， next為指向后繼結(jié)點(diǎn)的指針域，prev也為指針域， 但它的值為空(NULL)，試編寫算法將此單向循環(huán)鏈 表改為雙向循環(huán)鏈表，即使prev成為指向前驅(qū)結(jié)點(diǎn) 的指針域。 實(shí)現(xiàn)下列函數(shù)： void PerfectBiLink(BiLinkList &CL); 雙向循環(huán)鏈表類型定義如下： typedef struct BiNode { ElemType data; int freq; // 2.38題用 struct BiNode *prev, *next; }

46、 BiNode, *BiLinkList; void PerfectBiLink(BiLinkList &CL) { BiLinkList p; p=CL; p->next->prev=p; p=p->next; while(p!=CL){ p->next->prev=p; p=p->next; } } ? ◆2.33③ 已知由一個(gè)線性鏈表表示的線性表中含有 三類字符的數(shù)據(jù)元素（如：字母字符、數(shù)字字符和其 它字符），試編寫算法將該線性鏈表

47、分割為三個(gè)循環(huán) 鏈表，其中每個(gè)循環(huán)鏈表表示的線性表中均只含一類 字符。 實(shí)現(xiàn)下列函數(shù)： void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll); 單鏈表類型定義如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList; void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll) { LinkList p,

48、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->data<='z'){ cur_c->next=p; cur_c=cur_c->next; } else if(p->data>='0'&&p->data<='9'){

49、 cur_d->next=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.37④ 設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性 表L=(a1,a2,

50、…,an)。試寫一時(shí)間復(fù)雜度為O(n)的 算法，將L改造為L=(a1,a3,…,an,…,a4,a2)。 實(shí)現(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

51、; int count=0; //用count計(jì)結(jié)點(diǎn)個(gè)數(shù) p=L->next; //p指向第一個(gè)元素 while(p!=L->prev){//求鏈表長度-1 ++count; p=p->next; } last=p;//獲得最后一個(gè)元素的地址 if(count>=2){ p=p->prev; while(p!=L->next){//當(dāng)p指向的不是第一個(gè)元素時(shí) if(0==count

52、%2){//判斷是否序號為偶數(shù)的結(jié)點(diǎn) temp=p; p=p->prev; temp->prev->next=temp->next; temp->next->prev=temp->prev; last->next=temp; temp->prev=last; last=temp; } else{//奇號結(jié)點(diǎn)則繼續(xù)往前

53、 p=p->prev; } --count; } last->next=L;//構(gòu)建循環(huán) L->prev=last;//構(gòu)建循環(huán) } } ? ◆2.39③ 試對稀疏多項(xiàng)式Pn(x)采用存儲(chǔ)量同多項(xiàng)式項(xiàng) 數(shù)m成正比的順序存儲(chǔ)結(jié)構(gòu)，編寫求Pn(x0)的算法（x0為 給定值），并分析你的算法的時(shí)間復(fù)雜度。 實(shí)現(xiàn)下列函數(shù)： float Evaluate(SqPoly pn, float x); /* pn.data[i].coef 存放ai， */

54、 /* pn.data[i].exp存放ei (i=1,2,…,m) */ /* 本算法計(jì)算并返回多項(xiàng)式的值。不判別溢出。 */ /* 入口時(shí)要求0≤e1?多項(xiàng)式的順序存儲(chǔ)結(jié)構(gòu): typedef struct { int coef; int exp; } PolyTerm; typedef struct { PolyTerm *data; int length; } SqPoly; float Evaluate(SqPoly pn, float x) /* pn.data[i].coef 存放ai，

55、 */ /* pn.data[i].exp存放ei (i=1,2,...,m) */ /* 本算法計(jì)算并返回多項(xiàng)式的值。不判別溢出。 */ /* 入口時(shí)要求0≤e1

56、+j){ temp*=x; } total+=temp*(pn.data[i].coef); ++i; } return total; } ? ◆2.41② 試以循環(huán)鏈表作稀疏多項(xiàng)式的存儲(chǔ)結(jié)構(gòu)， 編寫求其導(dǎo)函數(shù)的算法，要求利用原多項(xiàng)式中的結(jié) 點(diǎn)空間存放其導(dǎo)函數(shù)（多項(xiàng)式），同時(shí)釋放所有無 用（被刪）結(jié)點(diǎn)。 實(shí)現(xiàn)下列函數(shù)： void Difference(LinkedPoly &pa); /* 稀疏多項(xiàng)式 pa 以循環(huán)鏈表作存儲(chǔ)結(jié)構(gòu)，

57、 */ /* 將此鏈表修改成它的導(dǎo)函數(shù)，并釋放無用結(jié)點(diǎn) */ 鏈?zhǔn)蕉囗?xiàng)式的類型定義： typedef struct PolyNode { int coef; int exp; struct PolyNode *next; } PolyNode, *PolyLink; // 多項(xiàng)式元素（項(xiàng)）結(jié)點(diǎn)類型 typedef PolyLink LinkedPoly; // 鏈?zhǔn)蕉囗?xiàng)式 void Difference(LinkedPoly &pa) /* 稀疏多項(xiàng)式 pa 以循環(huán)鏈表作存儲(chǔ)結(jié)構(gòu)， */ /* 將此鏈表修改成它的導(dǎo)函數(shù)，并釋放無用結(jié)點(diǎn) */ {

58、 LinkedPoly cur=pa->next,last=pa->next,tail=pa->next; if(pa->next){//此處改為cur時(shí)遇到空表會(huì)出錯(cuò)，不知道為什么 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=

59、last->next; cur=cur->next; } if(cur=last->next){free(last);tail->next=pa;} } } 數(shù)據(jù)結(jié)構(gòu)習(xí)題集 第3章答案 ◆3.17③ 試寫一個(gè)算法，識別依次讀入的一個(gè)以@ 為結(jié)束符的字符序列是否為形如’序列1&序列2′模式 的字符序列。其中序列1和序列2中都不含字符’&'， 且序列2是序列1的逆序列。例如，’a+b&b+a’是屬該 模式的字符序列，而’1+3&3-1′則不是。 實(shí)現(xiàn)下

60、列函數(shù):? Status match(char *str); /* 若str是屬該模式的字符序列，*/ /* 則返回TRUE，否則返回FALSE */ Stack是一個(gè)已實(shí)現(xiàn)的棧。 可使用的相關(guān)類型和函數(shù)： typedef char SElemType; // 棧Stack的元素類型 Status InitStack(Stack &s); Status Push(Stack &s, SElemType e); Status Pop(Stack &s, SElemType &e); Status StackEmpty(Stack s); Status GetTop(Stac

61、k s, SElemType &e); Status match(char *str) /* 若str是屬該模式的字符序列，*/ /* 則返回TRUE，否則返回FALSE */ { //文檔沒有說明字符串是以@結(jié)尾的 //也沒有說棧的類型是SqStack，用Stack時(shí)編譯出錯(cuò) SqStack s; SElemType c; Status flag=1; InitStack(s); char *cur=str; while('&'!=*cur){

62、 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;

63、 } ? 3.18② 試寫一個(gè)判別表達(dá)式中開、閉括號是否配對出現(xiàn)的算法。 實(shí)現(xiàn)下列函數(shù)： Status MatchCheck(SqList exp); /* 順序表exp表示表達(dá)式； */ /* 若exp中的括號配對，則返回TRUE，否則返回FALSE */ /* 注：本函數(shù)不使用棧 */ 順序表類型定義如下： typedef struct { ElemType *elem; int length; int listsize; } SqList; // 順序表 Status MatchCheck(SqList exp) /* 順序表exp表示表達(dá)式；

64、 */ /* 若exp中的括號配對，則返回TRUE，否則返回FALSE */ /* 注：本函數(shù)不使用棧 */ /*****************************/ // 此題top指針和cur指針要很仔細(xì)地運(yùn)用，還有判錯(cuò)條件也要小心 { ElemType *cur,*top,*base; base=exp.elem;//模擬棧底 top=cur=base+1;//模擬棧頂(top)和當(dāng)前元素(cur)

65、if(')'==*cur){ return FALSE; } //判斷第一個(gè)字符是否為右括號 if(0==exp.length){ return TRUE; }//判斷是否為空順序表 while(cur<=base+exp.length-1){//依次遍歷 if('('==*cur){//當(dāng)元素為左括號時(shí) if(top!=cur){ *top=*cur; *cur='

66、0'; } ++top; }//top始終指向第二個(gè)元素 //////////////////////////// else if(')'==*cur){ if(top==base){ return FALSE; } if('('==*(top-1)){ *(--top)='0'; *cur='0'; } } //////////////////////////// ++cur; } if('0'==*base){return TRUE;}//此處應(yīng)為base，而不是top return FALSE