棧和隊(duì)列作業(yè)答案市公開(kāi)課一等獎(jiǎng)省名師優(yōu)質(zhì)課賽課一等獎(jiǎng)?wù)n件

第三章棧和隊(duì)列作業(yè)評(píng)講3.43.63.7寫作業(yè)本上交3.1鏈棧中為何不設(shè)置頭結(jié)點(diǎn)3.2循環(huán)隊(duì)列優(yōu)點(diǎn)是什么?怎樣判別它空和滿?3.3設(shè)長(zhǎng)度為n鏈隊(duì)用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊(duì)出隊(duì)操作時(shí)間為何?若只設(shè)尾指針呢?

3.4回文是指正讀反讀均相同字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個(gè)算法判定給定字符向量是否為回文。(提醒：將二分之一字符入棧)3.5設(shè)計(jì)算法判斷一個(gè)算術(shù)表示式圓括號(hào)是否正確配對(duì)。(提醒：

對(duì)表示式進(jìn)行掃描，凡碰到'('就進(jìn)棧，遇')'就退掉棧頂'('，表示式被掃描完成，棧應(yīng)為空。3.6試將以下遞歸過(guò)程改寫為非遞歸過(guò)程voidtest(int&sum){intｘ；scanf(x);if(x==0)sum=0;else{test(sum);sum+=x;printf(sum);}3.7假設(shè)以帶頭結(jié)點(diǎn)循環(huán)鏈表表示隊(duì)列,而且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針),試編寫對(duì)應(yīng)隊(duì)列初始化、入隊(duì)列和出隊(duì)列算法.3.1鏈棧中為何不設(shè)置頭結(jié)點(diǎn)?

鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)行操作，假如加了頭結(jié)點(diǎn)，等于要對(duì)頭結(jié)點(diǎn)之后結(jié)點(diǎn)進(jìn)行操作，反而使算法更復(fù)雜，所以只要有鏈表頭指針就能夠了。3.2循環(huán)隊(duì)列優(yōu)點(diǎn)是什么?怎樣判別它空和滿?

循環(huán)隊(duì)列優(yōu)點(diǎn)是：它能夠克服次序隊(duì)列“假上溢”現(xiàn)象，能夠使存放隊(duì)列向量空間得到充分利用。判別循環(huán)隊(duì)列"空"或"滿"不能以頭尾指針是否相等來(lái)確定，普通是經(jīng)過(guò)以下幾個(gè)方法：一是另設(shè)一布爾變量來(lái)區(qū)分隊(duì)列空和滿。二是少用一個(gè)元素空間。每次入隊(duì)前測(cè)試入隊(duì)后頭尾指針是否會(huì)重合，假如會(huì)重合就認(rèn)為隊(duì)列已滿。三是設(shè)置一計(jì)數(shù)器統(tǒng)計(jì)隊(duì)列中元素總數(shù)，不但可判別空或滿，還能夠得到隊(duì)列中元素個(gè)數(shù)。

3.3設(shè)長(zhǎng)度為n鏈隊(duì)用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊(duì)、出隊(duì)操作時(shí)間為何?若只設(shè)尾指針呢?

當(dāng)只設(shè)頭指針時(shí)，出隊(duì)時(shí)間為1，而入隊(duì)時(shí)間需要n，因?yàn)槊看稳腙?duì)均需從頭指針開(kāi)始查找，找到最終一個(gè)元素時(shí)方可進(jìn)行入隊(duì)操作。若只設(shè)尾指針，則出、入隊(duì)時(shí)間均為1。因?yàn)槭茄h(huán)鏈表，尾指針?biāo)赶乱粋€(gè)元素就是頭指針?biāo)冈?，所以出?duì)時(shí)不需要遍歷整個(gè)隊(duì)列。

3.4回文是指正讀反讀均相同字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個(gè)算法判定給定字符向量是否為回文。(提醒：將二分之一字符入棧)

Typedefstruct{selemtype*base;selemtype*top;intstacksize;}sqstack;Statushuiwen(sqstackS,char*ch){intm,i,j;

S.base=(selemtype*)malloc(STACK_INIT_SIZE*sizeof(selemtype));if(!S.base)exit(OVERFLOW);S.top=s.base;S.stacksize=STACK_INIT_SIZE;m=strlen(ch);for(i=0;i<m/2;i++){*s.top=ch[i];s.top++;}if(m%2!=0)j=m/2+1;elsej=m/2;for(;j<m;j++){s.top=s.top-1;if(ch[j]!=*s.top)break;}if(i==m)returnOK;elsereturnERROR;}提醒：對(duì)表示式進(jìn)行掃描，凡碰到'('就進(jìn)棧，遇')'就退掉棧頂'('，表示式被掃描完成，棧應(yīng)為空。

依據(jù)提醒，能夠設(shè)計(jì)算法以下：

#include<string.h>

#include"stack.h"

intPairBracket(char*S)

{

//檢驗(yàn)表示式中括號(hào)是否配對(duì)

inti;

SeqStackT;//定義一個(gè)棧

InitStack(&T);

for(i=0;i<strlen(S);i++)

{

if(S[i]=='(')Push(&T,S[i]);//遇'('時(shí)進(jìn)棧

if(S[i]==')')Pop(&T);//遇')'時(shí)出棧

}

return!EmptyStack(&T);//由?？辗穹祷卣_配對(duì)是否

}3.5設(shè)計(jì)算法判斷一個(gè)算術(shù)表示式圓括號(hào)是否正確配對(duì)3.6試將以下遞歸過(guò)程改寫為非遞歸過(guò)程voidtest1(int&sum){intx;scanf(“%d”,&x);sum=0;while(x!=0){sum+=x;printf(“%10d”,sum);scanf(“%d”,&x);}return;}3.7假設(shè)以帶頭結(jié)點(diǎn)循環(huán)鏈表表示隊(duì)列,而且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針),試編寫對(duì)應(yīng)隊(duì)列初始化、入隊(duì)列和出隊(duì)列算法.typedefstructqueuenode

{Datatypedata;structqueuenode*next;}QueueNode; //以上是結(jié)點(diǎn)類型定義typedefstruct

{queuenode*rear;}LinkQueue; //只設(shè)一個(gè)指向隊(duì)尾元素指針statusInitQueue(LinkQueue*Q){Q->rear=(QueueNode*)malloc(sizeof(QueueNode));if(!Q->rear)exit(OVERFLOW);Q->rear->next=Q->rear;}intEmptyQueue(LinkQueue*Q){if(Q->rear==Q->rear->next)return1;elsereturn0;}voidEnQueue(LinkQueue*Q,Datatypex){QueueNode*p;p=(QueueNode*)malloc(sizeof(QueueNode));if(!p)exit(OVERFLOW);p->data=x;p->next=NULL;p->next=Q->rear->next;Q-rear->next=p;Q->rear=p;}DatatypeDeQueue(LinkQueue*Q){Datatypex;QueueNode*p;if(Q-