anyview 數據結構習題集 第10章答案

數據結構習題集 第1章答案注意：此處代碼可能并非最優(yōu)化結果，等待代碼優(yōu)化中。1.16 試寫一算法，如果三個整數X，Y和Z的值不是依次非遞增的，則通過交換，令其為非遞增。要求實現(xiàn)下列函數：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項值的函數算法，k和m均以值調用的形式在函數參數表中出現(xiàn)。要求實現(xiàn)下列函數：Status Fibonacci(int k, int m, int &f);/* 如果能求得k階斐波那契序列的第m項的值f，則返回OK；*/* 否則（比如，參數k和m不合理）返回ERROR */Status Fibonacci(int k, int m, int &f) /* 求k階斐波那契序列的第m項的值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 假設有A、B、C、D、E五個高等院校進行田徑對抗賽，各院校的單項成績均以存入計算機并構成一張表，表中每一行的形式為項目名稱 性別 校名 成績 得分編寫算法，處理上述表格，以統(tǒng)計各院校的男、女總分和團體總分，并輸出。要求實現(xiàn)下列函數：void Scores(ResultType *result, ScoreType *score);/* 求各校的男、女總分和團體總分, 并依次存入數組score */* 假設比賽結果已經儲存在result 數組中, */* 并以特殊記錄 “”, male, , “”, 0 （域scorce=0）*/* 表示結束 */相關數據類型定義如下：typedef enum female,male Sex;typedef structchar *sport; / 項目名稱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; / 男女團體總分 ScoreType;void Scores(ResultType *result, ScoreType *score) /* 求各校的男、女總分和團體總分, 并依次存入數組score */ /* 假設比賽結果已經儲存在result 數組中, */ /* 并以特殊記錄 "", male, ' ', "", 0 （域scorce=0）*/ /* 表示結束 */ /感覺這道題題意有點模糊. 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 試編寫算法，計算i!×2i的值并存入數組a0.ARRSIZE-1的第i-1個分量中 (i=1,2,n)。假設計算機中允許的整數最大值為MAXINT，則當n>ARRSIZE或對某個k(1kn)使k!×2k>MAXINT時，應按出錯處理。注意選擇你認為較好的出錯處理方法。要求實現(xiàn)下列函數：Status Series(int ARRSIZE, int a);/* 求i!*2i序列的值并依次存入長度為ARRSIZE的數組a； */* 若所有值均不超過MAXINT，則返回OK，否則返回OVERFLOW */Status Series(int ARRSIZE, int a) /* 求i!*2i序列的值并依次存入長度為ARRSIZE的數組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 試編寫算法求一元多項式P(x) = a0 + a1x + a2x2 + + anxn的值P(x0)，并確定算法中每一語句的執(zhí)行次數和整個算法的時間復雜度。注意選擇你認為較好的輸入和輸出方法。要求實現(xiàn)下列函數：float Polynomial(int n, int a, float x0);/* 求一元多項式的值P(x0)。 */* 數組a的元素ai為i次項的系數，i=0,1,n */float Polynomial(int n, int a, float x) /* 求一元多項式的值P(x)。 */ /* 數組a的元素ai為i次項的系數，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; 數據結構習題集 第2章答案2.11 設順序表L中的數據元素遞增有序。試寫一算法，將x插入到L的適當位置上，并保持該表的有序性。要求實現(xiàn)下列函數：void InsertOrderList(SqList &L, ElemType x)/* 在有序的順序表 L 中保序插入數據元素 x */順序表類型定義如下：typedef struct ElemType *elem;int length;int listsize; SqList;void InsertOrderList(SqList &L, ElemType x) / 在有序的順序表 L 中保序插入數據元素 x ElemType *p,*q; p=L.elem; while(*p<x&&p<=(L.elem+L.length-1)/注意此處必須要注意-1， /容易粗心犯錯的地方！ +p; /p為大于X的第一個元素指針 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 設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。試寫一個比較A和B大小的算法。（注意：在算法中，不要破壞原表A和B，也不一定先求得A和B才進行比較）。要求實現(xiàn)下列函數：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 '=' /此處應先判斷長度是否相等！ if(la=A.length+1)return '<' if(lb=B.length+1)return '>'  2.13 試寫一算法在帶頭結點的單鏈表結構上實現(xiàn)線性表操作Locate(L,x)。實現(xiàn)下列函數：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 試寫一算法在帶頭結點的單鏈表結構上實現(xiàn)線性表操作Length(L)。實現(xiàn)下列函數：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 試寫一算法，在無頭結點的動態(tài)單鏈表上實現(xiàn)線性表操作INSERT(L,i,b)，并和在帶頭結點的動態(tài)單鏈表上實現(xiàn)相同操作的算法進行比較。實現(xiàn)下列函數：void Insert(LinkList &L, int i, ElemType b);單鏈表類型定義如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;/思路不是很清晰，很多細節(jié)問題，調試了很長時間 /主要考慮問題：1、i為0或負數時 2、i在鏈表長度內 3、i為鏈表長度+1時 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個元素的指針，q為p的j-1個指針 p=p->next; p=(LinkList)malloc(sizeof(LNode); p->data=b; p->next=q->next; q->next=p;  2.18 同2.17題要求。試寫一算法，實現(xiàn)線性表操作DELETE(L,i)。實現(xiàn)下列函數：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時沒問題 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題條件，試寫一高效的算法，刪除表中所有值相同的多余元素 (使得操作后的線性表中所有元素的值均不相同) 同時釋放被刪結點空間，并分析你的算法的時間復雜度。實現(xiàn)下列函數：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 試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表(a1,a2,an)逆置為(an,an-1,a1)。實現(xiàn)下列函數：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 試寫一算法，對單鏈表實現(xiàn)就地逆置。實現(xiàn)下列函數：void Inverse(LinkList &L);/* 對帶頭結點的單鏈表L實現(xiàn)就地逆置 */單鏈表類型定義如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;void Inverse(LinkList &L) /* 對帶頭結點的單鏈表L實現(xiàn)就地逆置 */ LinkList last,cur,q; q=L->next; /保存首元素地址 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=NULL;  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)下列函數：void Merge(LinkList ha, LinkList hb, LinkList &hc)/* 依題意，合并帶頭結點的單鏈表ha和hb為hc */單鏈表類型定義如下：typedef struct LNodeElemType 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_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表。實現(xiàn)下列函數：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->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 假設某個單向循環(huán)鏈表的長度大于1，且表中既無頭結點也無頭指針。已知s為指向鏈表中某個結點的指針，試編寫算法在鏈表中刪除指針s所指結點的前驅結點。實現(xiàn)下列函數：ElemType DeleteNode(LinkList s);/* 刪除指針s所指結點的前驅結點，并返回被刪結點的元素值 */單鏈表類型定義如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *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為數據域，next為指向后繼結點的指針域，prev也為指針域，但它的值為空(NULL)，試編寫算法將此單向循環(huán)鏈表改為雙向循環(huán)鏈表，即使prev成為指向前驅結點的指針域。實現(xiàn)下列函數：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 已知由一個線性鏈表表示的線性表中含有三類字符的數據元素（如：字母字符、數字字符和其它字符），試編寫算法將該線性鏈表分割為三個循環(huán)鏈表，其中每個循環(huán)鏈表表示的線性表中均只含一類字符。實現(xiàn)下列函數：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 設以帶頭結點的雙向循環(huán)鏈表表示的線性表L=(a1,a2,an)。試寫一時間復雜度為O(n)的算法，將L改造為L=(a1,a3,an,a4,a2)。實現(xiàn)下列函數：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計結點個數 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)/判斷是否序號為偶數的結點 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ù)往前 p=p->prev; -count; last->next=L;/構建循環(huán) L->prev=last;/構建循環(huán)  2.39 試對稀疏多項式Pn(x)采用存儲量同多項式項數m成正比的順序存儲結構，編寫求Pn(x0)的算法（x0為給定值），并分析你的算法的時間復雜度。實現(xiàn)下列函數：float Evaluate(SqPoly pn, float x);/* pn.datai.coef 存放ai， */* pn.datai.exp存放ei (i=1,2,m) */* 本算法計算并返回多項式的值。不判別溢出。 */* 入口時要求0e1<e2<.<em，算法內不對此再作驗證* <br=""> 多項式的順序存儲結構: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) */ /* 本算法計算并返回多項式的值。不判別溢出。 */ /* 入口時要求0e1<e2<.<em，算法內不對此再作驗證*/ int i=0,j=1,cur;/沒想到這題目的數據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àn)下列函數：void Difference(LinkedPoly &pa);/* 稀疏多項式 pa 以循環(huán)鏈表作存儲結構， */* 將此鏈表修改成它的導函數，并釋放無用結點 */鏈式多項式的類型定義：typedef struct PolyNode int coef;int exp;struct PolyNode *next; PolyNode, *PolyLink; / 多項式元素（項）結點類型typedef PolyLink LinkedPoly; / 鏈式多項式void Difference(LinkedPoly &pa) /* 稀疏多項式 pa 以循環(huán)鏈表作存儲結構， */ /* 將此鏈表修改成它的導函數，并釋放無用結點 */ LinkedPoly cur=pa->next,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; 數據結構習題集 第3章答案3.17 試寫一個算法，識別依次讀入的一個以為結束符的字符序列是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&'，且序列2是序列1的逆序列。例如，a+b&b+a是屬該模式的字符序列，而1+3&3-1則不是。實現(xiàn)下列函數: Status match(char *str);/* 若str是屬該模式的字符序列，*/* 則返回TRUE，否則返回FALSE */Stack是一個已實現(xiàn)的棧。可使用的相關類型和函數：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 */ /文檔沒有說明字符串是以結尾的 /也沒有說棧的類型是SqStack，用Stack時編譯出錯 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 試寫一個判別表達式中開、閉括號是否配對出現(xiàn)的算法。實現(xiàn)下列函數：Status MatchCheck(SqList exp);/* 順序表exp表示表達式； */* 若exp中的括號配對，則返回TRUE，否則返回FALSE */* 注：本函數不使用棧 */順序表類型定義如下：typedef struct ElemType *elem;int length;int listsize; SqList; / 順序表Status MatchCheck(SqList exp) /* 順序表exp表示表達式； */ /* 若exp中的括號配對，則返回TRUE，否則返回FALSE */ /* 注：本函數不使用棧 */ /*/ / 此題top指針和cur指針要很仔細地運用，還有判錯條件也要小心 ElemType *cur,*top,*base; base=exp.elem;/模擬棧底 top=cur=base+1;/模擬棧頂(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