數(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<y)temp=x;x=y;y=temp; if(x<z)temp=x;x=z;z=temp; if(y<z)temp=y;y=z;z=temp; 1.17 已知k階裴波那契序列的定義為f0=0, f1=0, , fk-2=0, fk-1=1;fn=fn-1+fn-2+fn-k, n=k,k+1,試編寫求k階裴波那契序列的第m項(xiàng)值的函數(shù)算法，k和m均以值調(diào)用的形式在函數(shù)參數(shù)表中出現(xiàn)。要求實(shí)現(xiàn)下列函數(shù)：Status Fibonacci(int k, int m, int &f);/* 如果能求得k階斐波那契序列的第m項(xiàng)的值f，則返回OK；*/* 否則（比如，參數(shù)k和m不合理）返回ERROR */Status Fibonacci(int k, int m, int &f) /* 求k階斐波那契序列的第m項(xiàng)的值f */ /沒想到m竟然是從0開始的 int i; long temp; int a1000; if(k<=1|m<0)return ERROR; for(i=0;i<k-1;i+)ai=0; ai=1; ak=1; for(temp=1,i=k+1;i<=m;+i) if(temp>MAXINT) return ERROR; temp=temp-ai-k-1+ai-1; ai=temp; f=am; return OK;  1.18 假設(shè)有A、B、C、D、E五個(gè)高等院校進(jìn)行田徑對抗賽，各院校的單項(xiàng)成績均以存入計(jì)算機(jī)并構(gòu)成一張表，表中每一行的形式為項(xiàng)目名稱 性別 校名 成績 得分編寫算法，處理上述表格，以統(tǒng)計(jì)各院校的男、女總分和團(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 structchar *sport; / 項(xiàng)目名稱Sex gender; / 性別（女：female；男：male）char schoolname; / 校名為A',B',C',D'或Echar *result; / 成績int score; / 得分（7,5,4,3,2或1） ResultType;typedef structint malescore; / 男子總分int femalescore; / 女子總分int totalscore; / 男女團(tuán)體總分 ScoreType;void Scores(ResultType *result, ScoreType *score) /* 求各校的男、女總分和團(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; scorej.malescore=0; scorej.femalescore=0; while(resulti.score!=0) if('A'+j=resulti.schoolname) if(male=resulti.gender) scorej.malescore+=resulti.score; if(female=resulti.gender) scorej.femalescore+=resulti.score; scorej.totalscore=scorej.malescore+scorej.femalescore; +i;   1.19 試編寫算法，計(jì)算i!×2i的值并存入數(shù)組a0.ARRSIZE-1的第i-1個(gè)分量中 (i=1,2,n)。假設(shè)計(jì)算機(jī)中允許的整數(shù)最大值為MAXINT，則當(dāng)n>ARRSIZE或?qū)δ硞€(gè)k(1kn)使k!×2k>MAXINT時(shí)，應(yīng)按出錯(cuò)處理。注意選擇你認(rèn)為較好的出錯(cuò)處理方法。要求實(shí)現(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，則返回OK，否則返回OVERFLOW */ int i=1,temp=1; while(i<=ARRSIZE) if(MAXINT/temp<2*i)return OVERFLOW; temp*=2; temp*=i; ai-1=temp; +i; return OK;  1.20 試編寫算法求一元多項(xiàng)式P(x) = a0 + a1x + a2x2 + + anxn的值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的元素ai為i次項(xiàng)的系數(shù)，i=0,1,n */float Polynomial(int n, int a, float x) /* 求一元多項(xiàng)式的值P(x)。 */ /* 數(shù)組a的元素ai為i次項(xiàng)的系數(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ù)結(jié)構(gòu)習(xí)題集 第2章答案2.11 設(shè)順序表L中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到L的適當(dāng)位置上，并保持該表的有序性。要求實(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; while(*p<x&&p<=(L.elem+L.length-1)/注意此處必須要注意-1， /容易粗心犯錯(cuò)的地方！ +p; /p為大于X的第一個(gè)元素指針 if(L.length=L.listsize) L.elem=(ElemType *)realloc(L.elem,L.listsize+10); if(L.elem) exit(OVERFLOW); L.listsize+=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,x,x,z)）。若A=B=空表，則A=B；若A=空表，而B 空表，或者兩者均不為空表，且A的首元小于B的首元，則A<b；否則a>B。試寫一個(gè)比較A和B大小的算法。（注意：在算法中，不要破壞原表A和B，也不一定先求得A和B才進(jìn)行比較）。要求實(shí)現(xiàn)下列函數(shù)：char Compare(SqList A, SqList B);/* 比較順序表A和B, */* 返回<', 若A<b; *="" <br=""> /* '=', 若A=B; */* '>, 若A>B */順序表類型定義如下：typedef struct ElemType *elem;int length;int listsize; SqList;char Compare(SqList A, SqList B) / 比較順序表A和B, / 返回'<', 若A<B; / '=', 若A=B; / '>', 若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)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 試寫一算法在帶頭結(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, *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 試寫一算法在帶頭結(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 LNodeElemType 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;  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 LNodeElemType data;struct LNode *next; LNode, *LinkList;/思路不是很清晰，很多細(xì)節(jié)問題，調(diào)試了很長時(shí)間 /主要考慮問題：1、i為0或負(fù)數(shù)時(shí) 2、i在鏈表長度內(nèi) 3、i為鏈表長度+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; 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->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 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號元素 /特殊位置首位、末尾 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<i-1;+j) 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 LNodeElemType 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); 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 length;int listsize; SqList;void Inverse(SqList &L) int i; ElemType *p,temp; p=L.elem; for(i=0;i<L.length/2;+i) temp=*(L.elem+i); *(L.elem+i)=*(L.elem+L.length-i-1); *(L.elem+L.length-i-1)=temp;  2.22 試寫一算法，對單鏈表實(shí)現(xiàn)就地逆置。實(shí)現(xiàn)下列函數(shù)：void Inverse(LinkList &L);/* 對帶頭結(jié)點(diǎn)的單鏈表L實(shí)現(xiàn)就地逆置 */單鏈表類型定義如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;void Inverse(LinkList &L) /* 對帶頭結(jié)點(diǎn)的單鏈表L實(shí)現(xiàn)就地逆置 */ LinkList last,cur,q; q=L->next; /保存首元素地址 last=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->next=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)mn時(shí)；或者 C=(a1,b1,an,bn,an+1,am) 當(dāng)mn時(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)/* 依題意，合并帶頭結(jié)點(diǎn)的單鏈表ha和hb為hc */單鏈表類型定義如下：typedef struct LNodeElemType 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; 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=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 假設(shè)有兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲(chǔ)結(jié)構(gòu)，請編寫算法將A表和B表歸并成一個(gè)按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表C， 并要求利用原表（即A表和B表）的結(jié)點(diǎn)空間構(gòu)造C表。實(shí)現(xiàn)下列函數(shù)：void Union(LinkList &lc, LinkList la, LinkList lb);/* 依題意，利用la和lb原表的結(jié)點(diǎn)空間構(gòu)造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->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->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; lb->next=temp->next; temp->next=last; last=temp; q->next=NULL; lc=la; lc->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 LNodeElemType data;struct LNode *next; LNode, *LinkList;ElemType DeleteNode(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.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; 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ù)字字符和其它字符），試編寫算法將該線性鏈表分割為三個(gè)循環(huán)鏈表，其中每個(gè)循環(huán)鏈表表示的線性表中均只含一類字符。實(shí)現(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, LinkList &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->data<='z') cur_c->next=p; cur_c=cur_c->next; else if(p->data>='0'&&p->data<='9') 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,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; 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%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ù)往前 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.datai.coef 存放ai， */* pn.datai.exp存放ei (i=1,2,m) */* 本算法計(jì)算并返回多項(xiàng)式的值。不判別溢出。 */* 入口時(shí)要求0e1<e2<.<em，算法內(nèi)不對此再作驗(yàn)證* <br=""> 多項(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.datai.coef 存放ai， */ /* pn.datai.exp存放ei (i=1,2,.,m) */ /* 本算法計(jì)算并返回多項(xiàng)式的值。不判別溢出。 */ /* 入口時(shí)要求0e1<e2<.<em，算法內(nèi)不對此再作驗(yàn)證*/ int i=0,j=1,cur;/沒想到這題目的數(shù)據(jù)i是從零開始的。 float total=0,temp=1; while(i<pn.length) for(cur=pn.datai.exp;j<=cur;+j) temp*=x; total+=temp*(pn.datai.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)， */* 將此鏈表修改成它的導(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) */ 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=last->next; cur=cur->next; if(cur=last->next)free(last);tail->next=pa; 數(shù)據(jù)結(jié)構(gòu)習(xí)題集 第3章答案3.17 試寫一個(gè)算法，識(shí)別依次讀入的一個(gè)以為結(jié)束符的字符序列是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&'，且序列2是序列1的逆序列。例如，a+b&b+a是屬該模式的字符序列，而1+3&3-1則不是。實(shí)現(xiàn)下列函數(shù): Status match(char *str);/* 若str是屬該模式的字符序列，*/* 則返回TRUE，否則返回FALSE */Stack是一個(gè)已實(shí)現(xiàn)的棧?？墒褂玫南嚓P(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(Stack 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) 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 試寫一個(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á)式； */ /* 若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) 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='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