资源描述：
《魔王语言 数据结构试验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、魔王语言系统解释一、需求分析[问题描述] 有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没人能听的懂。但他的语言是可以逐步解释成人能懂得语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的： （1）α->β1β2...βn（2）(θδ1δ2...δn)->θδnθδn-1...θδ1θ 在这两种形式中，从左到右均表示解释；从右到左表示抽象。试写一个魔王解释系统，把 他的话解释成人能听懂得话。 [基本要求] 用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字 母表示
2、人的语言词汇；希腊字母（a,b1,s,y1等）表示可以用大写或小写字母代换的变量。 魔王语言可含人的词汇。 （1）B->tAdA (2) A->sae [测试数据] B（einxgz）B 解释成 tsaedsaeezegexeneietsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一个鹅地上一个鹅 鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅。” tdsaezGxni 天地上一个鹅追 赶下蛋恨 [实现提示] 将魔王的语言自右至左进栈，
3、总是处理栈顶。若是开括号，则逐一出栈，将字母顺序入队 列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者 思考如何处理，应首先实现栈和队列的基本运算二、概要设计为实现上述程序功能，应以栈和队列来表示。1.设定栈的抽象数据类型定义为：ADTStack｛数据对象：D=｛ai
4、ai∈CharSet，I=1，2，......，n,n≥0｝数据关系：R1=｛
5、ai-1，ai∈D,I=1，2，......，n｝基本操作：ListInitiate(&S)操作结果：构造一个空栈S。Stack
6、Empty（S）初始条件：栈S已经存在。操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。Push（&S,e）初始条件：栈S已经存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop（&S,&e）初始条件：栈S已经存在。操作结果：删除S的栈顶元素，并以e返回其值。}ADTStack2.设定队列的抽象数据类型定义为：ADTQueue｛数据对象：D=｛ai
7、ai∈ElemSet，I=1，2，......，n,n≥0｝数据关系：R1=｛
8、ai-1，ai∈D,I=1，2，......，n｝基本操作：Lis
9、tInitiate(&Q)操作结果：构造一个空队列Q。StackEmpty（Q）初始条件：队列Q已经存在。操作结果：若队列Q为空栈，则返回TRUE，否则返回FALSE。EnQueue（&Q,e）初始条件：队列Q已经存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue（&Q,&e）初始条件：队列Q已经存在。操作结果：删除Q的对头元素，并以e返回其值。}ADTQueue1.程序包含四个模块：1）主程序模块：Voidmain(){初始化；For（）{接受处理命令；}接受处理；}1）栈模块——实现栈的抽象数据类型；2）队列模
10、块——实现队列的抽象数据类型。3）魔王语言解释模块——定义线性表的结点结构。各模块的之间的调用关系如下：主程序模块魔王语言解释模块 栈模块队列模块三、详细设计1.栈类型structStack{char*base;char*top;intstacksize;};2.队列类型structStack{char*base;char*top;intstacksize;};structLinkQueue{structQueue*front;structQueue*rear;};3.栈的基本操作//构造栈voidInitStack(st
11、ructStack&s){s.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));s.top=s.base;s.stacksize=STACK_INIT_SIZE;}//往栈中压入元素voidPush(structStack&s,chare){if(s.top-s.base>=STACK_INIT_SIZE){s.base=(char*)realloc(s.base,(s.stacksize+STACK_INCREMENT)*sizeof(char));s.top=s.base+
12、s.stacksize;s.stacksize+=STACK_INCREMENT;}*(s.top)=e;s.top++;}//取出栈中的元素voidPop(structStack&s,char&e){e=*--s.top;}//判断栈是否为空intStackEmpty(structSta
