云南大學數(shù)據(jù)結(jié)構(gòu)實驗3

實驗難度：A□團

序號學號姓名成績

指導教師（簽名）

學期：秋季學期

任課教師儲星

實驗題目棧和隊列及其應(yīng)用

組員及組長_______________________

承擔工作：______________________

聯(lián)系電話_______________________

電子郵件_______________________

完成提交時間：年月日

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

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

械糊關(guān)血對臧堿嬲通

虹磊踴徽M

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

tsaedsaeezegexenehetsaedsae

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

括號,II黯的產(chǎn)物搠腋程神跳,螂腫斷的能的虹黯凱

軸用船酷廨函懿實鵬譯。

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

言仲文):

字母雙字對應(yīng)表：

天地上一個指追趕下備恨

齪了懶郛虺林碩郵冊嬲

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

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

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

能說賺

腋恥魂鋤能，應(yīng)以棚側(cè)瀛。

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

typedefstructstack

(

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

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

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

}stack;//結(jié)構(gòu)體類型順序棧

基樵作：

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

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

回

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

S的枝頂元素,那,

&S,&e)枝S已經(jīng)存在。刪除

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

typedefstructQNode

{

chardata;

structQNode*next;

}*LinkQueueNode;

typedefstruct

{

LinkQueueNodefront;

LinkQueueNoderear;

}LinkQueue;

〃結(jié)構(gòu)體隊列類型*/

基糖作：

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

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

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

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

2.程序包含四個模塊：

1)主程序模塊：

Voidmain()

初始化;

For(){

接受處理命令;

)

接受處理;

2戒模塊一實現(xiàn)捌咖皴懈類型;

3)隊列模I現(xiàn)隊列的抽象獨類也

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

各漱吃間的調(diào)用繇如下：

主新模塊

口

口

?；?/p>

口

隊列模塊

三、【實現(xiàn)(Implement)](30%)

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

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

面的關(guān)微現(xiàn)方濾.)

棧的基棣作：

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;

信黯廨的具觸現(xiàn)：

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

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();

}

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

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

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

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

a-鄧132…Bn

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

字母-漢字對應(yīng)表：

tdsaezgxnh

天地上一個鵝追趕下蛋恨

魔王說：ABtds(aezg)hn

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

售按荏意鍵繼續(xù)??.

五、【姬總結(jié)］(10%)

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

槌虢陳心御

問題關(guān)鍵:

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

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

2一約節(jié)處理,比如數(shù)鰥作等。

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

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

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

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

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

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

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

可以處理多就鞭套的問蜃

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

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

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

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

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

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

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

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

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

隊列。

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

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

尾,??WJ.

七、【代碼】(10%)

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

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

#inchide<iostream>

#include<stdlib.h>

usingnamespacestd;

typedefstructstack

{

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

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

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

}stack;//結(jié)構(gòu)體類型順序棧

typedefstructQNode

(

chardata;

structQNode*next;

}*LinkQueueNode;

typedefstruct

{

LinkQueueNodcfront;

LinkQueueNodcrear;

}LinkQueue;

/*結(jié)構(gòu)體隊列類型*/

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);