7、Pop(S,l);switch(l){ //有左括號匹配，但是括號不匹配case (:if(exp.elem[i]!=)) return FALSE;break;case [:if(exp.elem[i]!=]) return FALSE;break;case {:if(exp.elem[i]!=}) return FALSE;}}}} if(StackEmpty(S)) return TRUE;else return FALSE;//左括號多余}3 .2 0③假設(shè)以二維數(shù)組g(1 ..m,1 ..n)表示一個(gè)圖像區(qū)域，g[i,j]表示該區(qū)域中點(diǎn)(i,j)所具顏色，其值為從0到k的整數(shù)。編寫算
8、法置換點(diǎn)(i0 ,j0 )所在區(qū)域的顏色。約定和(i0 ,j0 )同色的上、下、左、右的鄰接點(diǎn)為同色區(qū)域的點(diǎn)。 實(shí)現(xiàn)下列函數(shù)：void ChangeColor(GTYPE g, int m, int n,char c, int i0 , int j0 );/*在g[1 ..m][1 ..n]中，將元素g[i0 ][j0 ] *//*所在的同色區(qū)域的顏色置換為顏色c */表示圖像區(qū)域的類型定義如下：typedef char GTYPE[m+1 ][n+1 ];Stack是一個(gè)已實(shí)現(xiàn)的棧?？墒褂玫南嚓P(guān)類型和函數(shù)：typedef int SElemType; //棧Stack的元素類型Status
9、StackInit(Stack Status Push(Stack Status Pop(Stack Status StackEmpty(Stack s);Status GetTop(Stack s, SElemType void ChangeColor(GTYPE g, int m, int n,char c, int i0 , int j0 )/*在g[1 ..m][1 ..n]中，將元素g[i0 ][j0 ] *//*所在的同色區(qū)域的顏色置換為顏色c */{ Stack S;int x,y,di=1 ;//di代表東北西南四個(gè)方向char color;StackInit(S,(m+1 )
10、*(n+1 ));x=i0 ;y=j0 ;if(x<=0 ||ym||y>n) exit(OVERFLOW);color=g[x][y]; //總體的思路是，從g[i0 ][j0 ]開始//對每個(gè)符合所求的元素的依次找東北西南，//即先找當(dāng)前元素的東邊，沒有找北邊，若北有，向北走一步，//再找（走到的那個(gè)元素）的東邊，依次類推//直到最后一個(gè)元素東北西南都被找過了，就回退//用Pop(S,di)為指導(dǎo)方向，找一些（因在某些元素北西南方）而被遺漏了的元素//此時(shí)，因?yàn)樵瓉肀闅v的元素已經(jīng)被標(biāo)記成c，即某些元素的（東北西）已不再是所找元素//因此，可以如愿走（某些元素的（北西南）方向do{ //如果
11、是所找的那個(gè)符號需要進(jìn)行的操作if(x>0 g[x][y]=c;y++;Push(S,di);}else //如果不是所找的那個(gè)符號需要進(jìn)行的操作{ Pop(S,di); //第一步，先退一步回到原來位置switch(di){ case 1 :y--;break;case 2 :x--; break;case 3 :y++; break;case 4 : x++;break;}di++; //第二步，換一個(gè)方向走下一個(gè)位置 if(di=a/* if m<0 or n<0 then return -1 . */ int G(int m, int n)/* if m<0 or n<0 then r
12、eturn -1 . */{ if(m<0 ||n0 實(shí)現(xiàn)下列函數(shù)：int F(int n);/* if n<0 then return -1 . */int F(int n)/* if n<0 then return -1 . */{ if(nnext=rear;if(!front||!rear) exit(OVERFLOW);return OK; //需要return OK} Status EnCLQueue(CLQueue p=(CLQueue)malloc(sizeof(LNode));p->data=x;p->next=rear->next;//先讓p新開的節(jié)點(diǎn)指向頭結(jié)點(diǎn) rear-
13、>next=p;rear=p;return OK;}Status DeCLQueue(CLQueue CLQueue p=front->next;if(front==rear) return ERROR;x=p->data;front->next=p->next;free(p); return OK;}3 .2 9③如果希望循環(huán)隊(duì)列中的元素都能得到利用，則需設(shè)置一個(gè)標(biāo)志域tag，并以tag的值為0或1來區(qū)分，尾指針和頭指針值相同時(shí)的隊(duì)列狀態(tài)是"空"還是"滿"。試編寫與此結(jié)構(gòu)相應(yīng)的入隊(duì)列和出隊(duì)列的算法，并從時(shí)間和空間角度討論設(shè)標(biāo)志和不設(shè)標(biāo)志這兩種方法的使用范圍（比如，當(dāng)循環(huán)隊(duì)列容量較小而隊(duì)列中每
14、個(gè)元素占的空間較多時(shí)，那一種方法 較好？）。實(shí)現(xiàn)下列函數(shù)：Status EnCQueue(CTagQueue Status DeCQueue(CTagQueue 本題的循環(huán)隊(duì)列CTagQueue的類型定義如下：typedef char QElemType;typedef struct {QElemType elem[MAXQSIZE];int tag;int front;int rear; } CTagQueue;Status EnCQueue(CTagQueue }else{ Q.elem[Q.rear]=x;Q.rear=(Q.rear+1 )%MAXQSIZE;}return OK;}S
15、tatus DeCQueue(CTagQueue } else{ x=Q.elem[Q.front];Q.front=(Q.front+1 )%MAXQSIZE;} //當(dāng)指針前移時(shí)，原來的front位置就空了return OK; //不需其他操作}◆3 .3 0②假設(shè)將循環(huán)隊(duì)列定義為：以域變量rear和length分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和內(nèi)含元素的個(gè)數(shù)。試給出此循環(huán)隊(duì)列的隊(duì)滿條件，并 寫出相應(yīng)的入隊(duì)列和出隊(duì)列的算法（在出隊(duì)列的算法中要返回隊(duì)頭元素）。實(shí)現(xiàn)下列函數(shù)：Status EnCQueue(CLenQueue Status DeCQueue(CLenQueue 本題的循環(huán)隊(duì)列C
16、LenQueue的類型定義如下：typedef char QElemType;typedef struct {QElemType elem[MAXQSIZE];int length;int rear; } CLenQueue;Status EnCQueue(CLenQueue }else{ Q.elem[(Q.rear+1 )%MAXQSIZE]=x;Q.rear=(Q.rear+1 )%MAXQSIZE; //有可能加到MAXQSIZEQ.length++;}return OK;}Status DeCQueue(CLenQueue if(Q.length==0 ) { return ERRO
17、R;}else{ if((front=Q.rear-Q.length+1 )<0 ){ front=MAXQSIZE+front; }x=Q.elem[front];front=(front+1 )%MAXQSIZE;//有可能加到MAXQSIZEQ.length--;} //當(dāng)指針前移時(shí)，原來的front位置就空了return OK; //不需其他操作}◆3 .3 1③假設(shè)稱正讀和反讀都相同的字符序列為"回文"，例如，abba和abcba是回文，abcde 和ababab則不是回文。試寫一個(gè)算法判別讀入的一個(gè)以@為結(jié)束符的字符序列是否是"回文"。實(shí)現(xiàn)下列函數(shù)：Status Palindrom
18、e(char *word);/*利用棧和隊(duì)列判定字符序列word是否是回文*/可使用棧Stack和隊(duì)列Queue及其下列操作：Status InitStack(Stack Status Push(Stack Status Pop(Stack Status StackEmpty(Stack S); Status InitQueue(Queue Status EnQueue(Queue Status DeQueue(Queue Status QueueEmpty(Queue Q); Status Palindrome(char *word)/*利用棧和隊(duì)列判定字符序列word是否是回文*/{ Stack S;Queue Q;char s,q;InitStack(S);InitQueue(Q);while(*word!=@){ Push(S,*word);EnQueue(Q,*word);word++;} while(!StackEmpty(S)){ Pop(S,s);DeQueue(Q,q);if(s!=q){ return FALSE;}}return TRUE;}
廣東工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)Aniview系統(tǒng)第三章參考答案.pdf
