魔王语言解释-数据结构课程设计.doc

《魔王语言解释-数据结构课程设计.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实习2、魔王语言解释一、需求分析1.问题描述有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没人能听的懂，但他的语言是可以逐步解释成人能懂得语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）α->β1β2...βn（2）(θδ1δ2...δn)—>θδnθδn-1...θδ1θ在这两种形式中，从左到右均表示解释。试写一个魔王解释系统，把他的话解释成人能听懂得话。2.基本要求 用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写或小写字母代换的

2、变量。魔王语言可含人的词汇。 （1）B—>tAdA （2）A—>sae3.测试数据B（ehnxgz）B解释成tsaedsaeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一个鹅地上一个鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅”。tdsaezgxnh天地上一只鹅追赶下蛋恨4.实现提示 将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考如何处理。应首先实现栈和队列的基本操作。

3、二、概要设计1、设定栈的抽象数据类型定义：ADTStack{数据对象：D={ai

4、ai∈CharSet,i=1,2,……n,.n≥0}数据关系：R1={

5、ai-1,ai∈D,ai-1

6、k(*S)初始条件：栈S已存在操作结果：将栈S清空。InStack(char*ch,SqStack*s)初始条件：栈S已存在操作结果：把字符数组从右至左压入栈中。}ADTStackADTQueue{数据对象：D={ai

7、ai∈CharSeti=1,2,……n,.n≥0}数据关系：R1={

8、ai-1,ai∈Dti=1,2,……n}基本操作：InitQueue(*Q)操作结果：构造一个空队列Q。EnQueue（*Q,e）初始条件：队列Q已经存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue（*Q,*e）初始条件：队列

9、Q已经存在。操作结果：删除Q的对头元素，并以e返回其值。QueueEmpty（Q）初始条件：队列Q已经存在。操作结果：若队列Q为空栈，则返回1，否则返回0。}ADTQueue一、详细设计（源代码）（使用C语言）#include#include#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量typedefstruct{char*base;//栈底指针char*top;//栈顶指针intstacksize;}SqSta

10、ck;typedefstructQNote{chardata;structQNote*next;}QNote,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;voidInitStack(SqStack*s){//构造一个空栈s->base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));s->top=s->base;s->stacksize=STACK_INIT_SIZE;}voidPush(SqSta

11、ck*s,chare){//插入元素e为新的栈顶元素if(s->top-s->base>=STACK_INIT_SIZE){s->base=(char*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char));s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;}*(s->top)=e;s->top++;}voidPop(SqStack*s,char*e){//元素e出栈*e=*--s->top;}intStackE

12、mpty(SqStacks){//判断栈是否为空if(s.top==s.base)return1;elsereturn0;}voidClearStack(SqStack*s){/