1、廣東工業(yè)大學數(shù)據(jù)結(jié)構 Aniview 第三章參考答案3.17 試寫一個算法，識別依次讀入的一個以為結(jié)束符的字符序列是否為形如序列 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 I

2、nitStack(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*/ Stack S; int i; SElemType e; InitStack(S); for(i=0;stri!=&;i+) Push(S,stri); f

3、or(i=i+1;!StackEmpty(S)&stri!=;i+)Pop(S,e);if(e!=stri) return FALSE;if(StackEmpty(S)&stri=) return TRUE;3.18 試寫一個判別表達式中開、閉括號是否配對出現(xiàn)的算法。實現(xiàn)下列函數(shù)：Status MatchCheck(SqList exp);/* 順序表 exp 表示表達式；*/* 若 exp 中的括號配對，則返回 TRUE，否則返回 FALSE */*注：本函數(shù)不使用棧*/順序表類型定義如下：typedef struct ElemType *elem;intlength;intlistsize

4、; SqList;/ 順序表Status MatchCheck(SqList exp)/* 順序表 exp 表示表達式；*/* 若 exp 中的括號配對，則返回 TRUE，否則返回 FALSE */* 注：本函數(shù)不使用棧/exp 里面是純括號，純小括號int l=0,i;*/for(i=0;iexp.length;i+)if(exp.elemi=() l+;if(exp.elemi=)l-;if(l0) return FALSE;/有左，沒右else return TRUE;3.19 假設一個算術表達式中可以包含三種括號：圓括號( 和)，方括號和和花括號和，且這三種括號可按任意的次序嵌套使用（

5、如：()）。編寫判別給定表達式中所含括號是否正確配對出現(xiàn)的算法(已知表達式已存入數(shù)據(jù)元素為字符的順序表中)。實現(xiàn)下列函數(shù)：Status MatchCheck(SqList exp);/* 順序表 exp 表示表達式；*/* 若 exp 中的括號配對，則返回 TRUE，否則返回 FALSE */順序表類型定義如下：typedef struct ElemType *elem;intlength;intlistsize; SqList;/ 順序表Stack 是一個已實現(xiàn)的棧。可使用的相關類型和函數(shù)：typedef char SElemType; / 棧 Stack 的元素類型Status InitS

6、tack(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 MatchCheck(SqList exp)/* 順序表 exp 表示表達式； */ /* 若 exp 中的括號配對，則返回 TRUE，否則返回 FALSE */ int i; Stack S; ElemType l; InitStack(S); for(i=0;iexp.length;

7、i+)if(exp.elemi=(|exp.elemi=|exp.elemi=) Push(S,exp.elemi); if(exp.elemi=)|exp.elemi=|exp.elemi=)if(StackEmpty(S) return FALSE; /無左括號匹配 elsePop(S,l);switch(l) /有左括號匹配，但是括號不匹配 case (:if(exp.elemi!=) return FALSE; break;case :if(exp.elemi!=) return FALSE;break;case :if(exp.elemi!=) return FALSE;if(Sta

8、ckEmpty(S) return TRUE;else return FALSE;/左括號多余3.20 假設以二維數(shù)組 g(1.m,1.n)表示一個圖像區(qū)域，gi,j表示該區(qū)域中點(i,j)所具顏色，其值為從 0 到 k 的整數(shù)。編寫算法置換點(i0,j0)所在區(qū)域的顏色。約定和(i0,j0)同色的上、下、左、右的鄰接點為同色區(qū)域的點。實現(xiàn)下列函數(shù)：void ChangeColor(GTYPE g, int m, int n,char c, int i0, int j0);/* 在 g1.m1.n中，將元素 gi0j0 */* 所在的同色區(qū)域的顏色置換為顏色 c*/表示圖像區(qū)域的類型定義如下：

9、typedef char GTYPEm+1n+1;Stack 是一個已實現(xiàn)的棧?？墒褂玫南嚓P類型和函數(shù)：typedef int SElemType; / 棧 Stack 的元素類型Status StackInit(Stack &s, int initsize);Status Push(Stack &s, SElemType e);Status Pop(Stack &s, SElemType &e);Status StackEmpty(Stack s);Status GetTop(Stack s, SElemType &e);void ChangeColor(GTYPE g, int m, in

10、t n,char c, int i0, int j0)/* 在 g1.m1.n中，將元素 gi0j0 */* 所在的同色區(qū)域的顏色置換為顏色 c*/Stack S;int x,y,di=1;/di 代表東北西南四個方向char color;StackInit(S,(m+1)*(n+1);x=i0;y=j0;if(x=0|ym|yn) exit(OVERFLOW);color=gxy;/總體的思路是，從 gi0j0開始/對每個符合所求的元素的依次找東北西南，/即先找當前元素的東邊，沒有找北邊，若北有，向北走一步，/再找（走到的那個元素）的東邊，依次類推/直到最后一個元素東北西南都被找過了，就回退

11、/用 Pop(S,di)為指導方向，找一些（因在某些元素北西南方）而被遺漏了的元素/此時，因為原來遍歷的元素已經(jīng)被標記成 c，即某些元素的（東北西）已不再是所找元素/因此，可以如愿走（某些元素的（北西南）方向 do /如果是所找的那個符號需要進行的操作 if(x0&y0&x=m&y=n&gxy=color) di=1;gxy=c;y+;Push(S,di);else /如果不是所找的那個符號需要進行的操作 Pop(S,di); /第一步，先退一步回到原來位置 switch(di) case 1:y-;break; case 2:x-; break;case 3:y+; break;case 4

12、: x+;break;di+;/第二步，換一個方向走下一個位置if(di=a&ei=0g(m,n) = g(m-1,2n)+n當 m0,n=0并根據(jù)算法畫出求 g(5,2)時棧的變化過程。實現(xiàn)下列函數(shù)：int g(int m, int n);/* if m0 or n0 then return -1. */int G(int m, int n)/* if m0 or n0 then return -1. */if(m0|n0實現(xiàn)下列函數(shù)：int F(int n);/* if n0 then return -1. */int F(int n)/* if n0 then return -1. */

13、if(nnext=rear;if(!front|!rear) exit(OVERFLOW);return OK;/需要 return OKStatus EnCLQueue(CLQueue &rear, ElemType x) CLQueue p; p=(CLQueue)malloc(sizeof(LNode); p-data=x;p-next=rear-next;/先讓 p 新開的節(jié)點指向頭結(jié)點rear-next=p;rear=p;return OK;Status DeCLQueue(CLQueue &rear, ElemType &x)CLQueue front=rear-next;CLQu

14、eue p=front-next;if(front=rear) return ERROR;x=p-data;front-next=p-next;free(p);return OK;3.29 如果希望循環(huán)隊列中的元素都能得到利用，則需設置一個標志域 tag，并以 tag 的值為 0 或 1 來區(qū)分，尾指針和頭指針值相同時的隊列狀態(tài)是空還是滿。試編寫與此結(jié)構相應的入隊列和出隊列的算法，并從時間和空間角度討論設標志和不設標志這兩種方法的使用范圍（比如，當循環(huán)隊列容量較小而隊列中每個元素占的空間較多時，那一種方法較好？）。實現(xiàn)下列函數(shù)：Status EnCQueue(CTagQueue &Q, QEl

15、emType x);Status DeCQueue(CTagQueue &Q, QElemType &x);本題的循環(huán)隊列 CTagQueue 的類型定義如下：typedef char QElemType;typedef struct QElemType elemMAXQSIZE;int tag;int front;int rear; CTagQueue;Status EnCQueue(CTagQueue &Q, QElemType x)if(Q.rear=Q.front&Q.tag=1) return ERROR; else Q.elemQ.rear=x;Q.rear=(Q.rear+1)%

16、MAXQSIZE;return OK;Status DeCQueue(CTagQueue &Q, QElemType &x)if(Q.front=Q.rear&Q.tag=0) return ERROR; else x=Q.elemQ.front; Q.front=(Q.front+1)%MAXQSIZE; /當指針前移時，原來的 front 位置就空了return OK;/不需其他操作3.30假設將循環(huán)隊列定義為：以域變量 rear和 length 分別指示循環(huán)隊列中隊尾元素的位置和內(nèi)含元素的個數(shù)。試給出此循環(huán)隊列的隊滿條件，并寫出相應的入隊列和出隊列的算法（在出隊列的算法中要返回隊頭元素）

17、。實現(xiàn)下列函數(shù)：Status EnCQueue(CLenQueue &Q, QElemType x);Status DeCQueue(CLenQueue &Q, QElemType &x);本題的循環(huán)隊列 CLenQueue 的類型定義如下：typedef char QElemType;typedef struct QElemType elemMAXQSIZE;int length;int rear; CLenQueue;Status EnCQueue(CLenQueue &Q, QElemType x)if(Q.length=MAXQSIZE) return ERROR; else Q.el

18、em(Q.rear+1)%MAXQSIZE=x;Q.rear=(Q.rear+1)%MAXQSIZE; /有可能加到 MAXQSIZE Q.length+;return OK;Status DeCQueue(CLenQueue &Q, QElemType &x) int front; if(Q.length=0) return ERROR; else if(front=Q.rear-Q.length+1)0) front=MAXQSIZE+front; x=Q.elemfront; front=(front+1)%MAXQSIZE;/有可能加到 MAXQSIZE Q.length-; /當指針前移時，原來的 front 位置就空了return OK;/不需其他操作3.31 假設稱正讀和反讀都相同的字符序列為回文，例如，abba和abcba是回文，abcde和ababab則不是回文。試寫一