云南大学数据结构实验3

实验难度：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);