實驗難度：A□團

序號學號姓名成績

指導教師（簽名）

學期：秋季學期

任課教師儲星

實驗題目棧和隊列及其應用

組員及組長_______________________

承擔工作：______________________

聯系電話_______________________

電子郵件_______________________

完成提交時間：年月日

一、【實驗構思(Conceive)](10%)

(棉冊應包括:描述翦豚現的基本思鼠例新用到楣徽修工被譚、g

械糊關血對臧堿嬲通

虹磊踴徽M

B—tAdA；ATsae；(dinxgz)一■ezegexendie則魔王語言B(dinxgz)B解釋成

tsaedsaeezegexenehetsaedsae

居字母指魁黯的翊L小寫字疇人的即黯觸露桐以包含

括號,II黯的產物搠腋程神跳,螂腫斷的能的虹黯凱

軸用船酷廨函懿實鵬譯。

在AMt,(轆產生市自定兒聊將一段所王的話廨為故意義的人類語

言仲文):

字母雙字對應表：

天地上一個指追趕下備恨

齪了懶郛虺林碩郵冊嬲

二、【實驗設計(Design)](20%)

體部船包括:抽象轆類聊定義颼椽作朝，程胞含的麟以及各殿

伽用繇,繳《?源蜻,蛹靦獻界砒訪

能說賺

腋恥魂鋤能，應以棚側瀛。

1.璇麟抽象魏類型定義為：

typedefstructstack

(

char*base;//順序棧的棧底指針

char*top;//順序棧的棧頂

intstacksize;//棧元素空間的大小

}stack;//結構體類型順序棧

基樵作：

Listinitiate(&S)構選一個空楨So

StackEmpty(S)棧S幽諉部S為空戰,則返回TOE,否則返FALSE

回

Push(&S,e)我S已經存在。在棧Pop(S雌魄入新的胡遙

S的枝頂元素,那,

&S,&e)枝S已經存在。刪除

2豌隊娜鵬麴類型定義為：

typedefstructQNode

{

chardata;

structQNode*next;

}*LinkQueueNode;

typedefstruct

{

LinkQueueNodefront;

LinkQueueNoderear;

}LinkQueue;

〃結構體隊列類型*/

基糖作：

Listinitiate(&Q)構造一個瓠列Q。

StackEmptyfQ)隊列Q已經存在。若隊列Q為空，則返回TRUE,否則返回FALSE*

EnQueue(&Q,e)隊列Q整存在擷玩素e為Q的新的廉元熬

DeQueue(&Q,&e)隊列Q已經存在。刪除Q的隊頭港,亦以e返回其直

2.程序包含四個模塊：

1)主程序模塊：

Voidmain()

初始化;

For(){

接受處理命令;

)

接受處理;

2戒模塊一實現捌咖皴懈類型;

3)隊列模I現隊列的抽象獨類也

魔王磊解雕4定義轆表蜂皤機

各漱吃間的調用繇如下：

主新模塊

口

口

棧徽

口

隊列模塊

三、【實現(Implement)](30%)

體部粗匏括:抽象轆類重微作的OO'關跳作的黑棋法實取

函數覿,攜序期博,韓船瞬螂桐復雜度分根嬸界面則需包括界

面的關微現方濾.)

棧的基棣作：

intInitstack(stack&s)//初始化空棧

{

s.base=(char*)malloc(ioo*sizeof(char));

if(!s.base)exit(o);

s.top=s.base;

s.stacksize=100;

return1；

}

intStackEmpty(stacks)//判斷棧是否為空

{

if(s.top==s.base)retum1；

returno;

)

voidpush(stack&s,chare)//入棧

{

if(s.top-s.base>=s.stacksize)

{

s.base=(char*)realloc(s.base,(s.stacksize+10)*sizeof(char));

if(!s.base)exit(o);

s.top=s.base+s.stacksize;

s.stacksize+=10;

*s.top++=e;

)

intpop(stack&s,char&e)//出棧

{

if(s.top==s.base)exit(o);

e=*-s.top;

return1；

}

隊列的基械俏

intInitQueue(LinkQueue&Q)//初始化空隊列

{

Q.front=Q.rear=(LinkQueueNode)malloc(sizeof(LinkQueueNode));

if(!Q.front)exit(-i);

Q.front->next=NULL;

returni;

}

intQueueEmpty(LinkQueueQ)//判斷隊列是否為空

{

if(Q.front==Q.rear)returni;

returno；

)

intEnQueue(LinkQueue&q,chare)//入隊列

{

LinkQueueNodep;

p=(LinkQueueNode)malloc(sizeof(QNode));

if(!p)exit(-i);

p->data=e;

p->next=NULL;

q.rear->next=p;

q.rear=p;

returni;

}

charDeQueue(LinkQueue&q,char&e)//刪除隊列隊頭元素并返回其值

(

LinkQueueNodep;

if(q.front==q.rear)returno；

p=q.front->next;

e=p->data;

q.front->next=p->next;

if(q.rear==p)q.rear=q.front;

free(p);

returnc;

信黯廨的具觸現：

voidchecke(chare)//翻譯列表根據彈棧字母轉化為漢字并打印

voidtransmite(stacks)//翻譯模塊

(

LinkQueueq;

InitQueue(q);

charc,e;

printf(魔王是說：);

while(!StackEmpty(s))//若棧不為空則開始翻譯

pop(s,e);

checke(e);

if(e==?(*)//括號處理

while(pop(s,e)&&e!=*)*)//括號匹配

EnQueue(q,e);

push(s,e);

DeQueue(q,c);

while(!QueueEmpty(q))

{

DeQueue(q,e);

push(s,c);

push(s,e);

)

push(s,c);

while(IStackEmpty(s))

{

pop(s,e);

if(e==')')break;

elsechecke(e);

)

)

)

printf();

}

四、【測試結果(Testing)](10%)

體部施包揀喉嬲雌應琳珊每次蛹腌燦酸以及輸出的

魏,樹妣靖顆行頹,可雌弱

I■'C:\Users\li_yu\source\repos\calc\Release\calc.exe

a-鄧132…Bn

(95152...5n)->05n85n-1...8516

字母-漢字對應表：

tdsaezgxnh

天地上一個鵝追趕下蛋恨

魔王說：ABtds(aezg)hn

速王；!說：上一只藕天上一只鵝地上一只鵝天地上一只趕一只追一只鵝一只恨蛋

售按荏意鍵繼續??.

五、【姬總結］(10%)

體部份應包揀自強實盼中完橢任備及存在的颼,所完成實物那中的具

槌虢陳心御

問題關鍵:

1.ffiW.入黜藤作,喇哂,頗的啾入腳跚

就,那為空神斷以及隊加斯-餞素柵除后躺的皴。

2一約節處理,比如數鰥作等。

3.將魁黯作為一個字符串讀入峽,苜曲靖括號是彼，如果碰戰我

B.W,費后游群從尾到頭雌哦S中，懶S中觸容擲燃

出壓雄S2中,直至遇到右括號,將其壓入板S1中，㈱棧S2彈出挨加棧

中,直鋤左括號壓入板S1中,這樣枝S1中存放的內容就題配的第一個內重

括號,雕S1擷元燕括號彈出,將挪號師的游藏保劭el變量中,

版將期阮素彈出撕惡入板S3中，在將el與板S3中韌理出的元素口板

S2中,重復沿魂,直魏疑露中所郁I括號都媚院恥,蒯這個螂

可以處理多就鞭套的問蜃

六、思量題或者【項目運作描述(Operate)](10%)

曲廨的才需鸚寫項目運作髓”，其他瞰的牖完成思能)

頌脆作髓的括:朔的成極益分布應腋果等的分根)

I.機能兢是一個就后出踴機

?：酸潮物瓦賺粉越赫他越宮糕在(RJ?

主要翱蹴哈福福柳娜1,W?#?.播程黯中:援用

魁的肺調用硬瓦可城在計算腫只魏螂腺礴跣a后出褫a

都觥虢螂楣蒯齷計算機機磁醐制

腳常轆甘懶雌鼬腰施螂懶囑舸姍

隊列。

2,可睬用瓣存讖楙口賦存瑞機因為伽都是娜襲雌-檎在一

條牡耿，蹴縫甘於彼,避瀛殆酸,確觸煽

尾,??WJ.

七、【代碼】(10%)

(本部艇包括:完整的脩駁充分的注氟注意懶的實物賠無需包括此部份。

格式統一為,字體：Geo畫砸：雕砸12,字號:小五)

#inchide<iostream>

#include<stdlib.h>

usingnamespacestd;

typedefstructstack

{

char*base;//順序棧的棧底指針

char*top;//順序棧的棧頂

intstacksize;//棧元素空間的大小

}stack;//結構體類型順序棧

typedefstructQNode

(

chardata;

structQNode*next;

}*LinkQueueNode;

typedefstruct

{

LinkQueueNodcfront;

LinkQueueNodcrear;

}LinkQueue;

/*結構體隊列類型*/

intInitstack(stack&s)//初始化空棧

{

s.base=(char*)malloc(ioo*sizeof(char));

if(!s.base)exit(o);

s.top=s.base;

s.stacksize=100;

return1；

)

intStackEmpty(stacks)//判斷棧是否為空

(

if(s.top==s.base)return1；

returno;

)

voidpush(stack&s,chare)//入棧

(

if(s.top-s.base>=s.stacksize)

{

s.base=(char*)realloc(s.base,(s.stacksize+10)*sizeof(char));

if(!s.base)exit(o);

s.top=s.base+s.stacksize;

s.stacksize+=10；

}

*s.top++=e;

)

intpopfstack&s,char&e)//出棧

{

if(s.top==s.base)exit(o);

e=*-s.top;

return1；

}

intInitQueue(LinkQueue&Q)//初始化空隊列

Q.front=Q.rear=(LinkQueueNode)malloc(sizeof(LinkQucueNode));

if(!Q.front)exit(-i);

Q.front->next=NULL;

return1；

}

intQueueEmpty(LinkQueueQ)//判斷隊歹U是否為空

(

if(Q.front==Q.rear)return1;

returno;

)

intEnQueue(LinkQueue&q,chare)//入隊列

{

LinkQueueNodep;

p=(LinkQueueNode)malloc(sizeof(QNode));

if(!p)exit(-i);

p->data=e;

p->next=NULL;

q.rear->next=p;

q.rear=p;

return1;

}

charDeQueue(LinkQueue&q,char&「)〃刪除隊列隊頭元素并返回其值

(

LinkQueueNodep;

if(q.front==q.rear)returno；

p=q.front->next;

e=p->data;

q.front->next=p->next;

if(q.rear==p)q.rear=q.front;

free(p);

returne;

}

voidchecke(chare)//翻譯列表

(

if(e==B)

printf(天上一只鵝地上一只鵝);

elseif(e=='A')

printf(上一只鵝);

elseif(e=='t*)

printf(天)；

elseif(e==d)

printf(地);

elseif(e==,s')

printf(±);

elseif(e=='a')

printf(一只);

elseif(e=='e')

printf(鵝);

elseif(e=='z')

printf(追);

elseif(e==g)

printf(趕);

elseif(e=='x*)

printf(下);

elseif(e==*n')

printf(蛋);

elseif(e==h)

printf(恨);

elseif(e!=fC&&e!"')')

printf(,e);

)

voidtransmite(stacks)//翻譯模塊

{

LinkQueucq;

InitQueue(q);

charc,e;

printf(魔王是說：);

while(!StackEmpty(s))//若棧不為空則開始翻譯

{

pop(s,e);

checke(e);

if(e=='C)//括號處理

{

while(pop(s,e)&&e!=')')〃括號匹配

EnQueue(q,e);