魔王语言数据结构实验报告课案

数据结构实验报告2.2魔王语言解释[问题描述]有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）α－β1β2„βm（2）（θδ1δ2„δn)－θδnθδn－1„θδ1θ在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。[基本要求]用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。（1）B－tAdA（2）A－sae[测试数据]B(ehnxgz)B解释成tsaedsaeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。tdsaezgxnh天地上一只鹅追赶下蛋恨一：需求分析(1)以一维数组demon[i]表示魔王语言．(2)魔王语言由用户输入,初始保存在demon[i]中．(3)魔王语言与人类语言对应关系固化在程序中．(4)实现过程：A：初始，魔王语言接收后存放在demon[i]中．B：初次遍历数组，将数组中括号内的元素入栈，同时插入相应首字母；C：再次遍历数组，将数组元素依次入队。（小写字母直接入队；大写字母经翻译成相应字符后入队；遇到括号，将栈中保存的元素依次出栈入队）在翻译过程中，如果依旧包含大写字母，则置flag为1，否则为0。D：将队列中元素赋值给demon[i]。如果此时flag=1，则再次重复C过程。直至所有元素为人类语言。E：输出demon[i]。此时数组中元素为对应的人类语言。注：如果程序中没有相应的对应关系，则翻译成“???”。二：概要设计：1：设定栈的抽象数据类型定义：ADTstack｛数据对象：D＝｛ai|ai∈CharSet,i＝1,2,„,n,n=0｝数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i＝2,„,n}基本操作：initstack(＆s)操作结果:构造一个空栈s.push(＆s,e)初始条件:栈s已存在.操作结果:在栈s的栈顶插入新的栈顶元素e.pop(＆s,＆e)初始条件:栈s已存在.操作结果:删除s的栈顶元素,并以e返回其值.}ADTstack2:设定队列的抽象数据类型:ADTqueue{数据对象：D＝｛ai|ai∈Elemset,i＝1,2,„,n,n=0｝数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i＝2,„,n}基本操作：initqueue(&q)操作结果:构造一个空队列q.enqueue(&q,e)初始条件:队列q已存在.操作结果:插入元素e为q的新队尾元素.dequeue(&q,&e)初始条件:q为非空队列.操作结果:删除q的队头元素,并用e返回其值.}ADTqueue3:本程序包含四个模块:1)主函数模块.其中主函数为:statusmain(){初始化栈;初始化队列;接收魔王语言输入到数组demon[i];遍历数组将括号中元素进栈;while(数组demon[i]中元素有大写字母){翻译排序处理后入队列;将对列元素保存在数组demon[i];}输出人类语言(数组demon[i]);}2)括号内元素入栈处理模块.tempstack(&temps)将括号内元素入栈,依次插入首字符.举例：(abcd)－adacaba.3)排序入队列模块.sort(&s,&q){遍历数组;{遇到小写字母,直接入队列;遇到大写字母,翻译大写后入队列;遇到括号,将栈中保存的元素依次出栈入队列;}}4)翻译大写处理模块.spenqueue(&*q,key){switch(key){找到各个大写字母对应的字符串.没有相应的则解释为’???’}}各模块之间调用关系:主函数模块{括号内元素入栈处理模块;排序入队模块{翻译大写处理模块;}}三:详细设计1.定义全局变量#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineNULL0#defineOVERFLOW-2#defineMAXSIZE100#definestack_init_size100#definestackincrement10typedefcharselemtype;typedefcharqelemtype;typedefcharelemtype;typedefintstatus;chare;chardemon[MAXSIZE];2.栈类型及其基本操作typedefstruct{selemtype*base;selemtype*top;intstacksize;}sqstack;statusinitstack(sqstack*s){s-base=(selemtype*)malloc(stack_init_size*sizeof(selemtype));if(!s-base)exit(OVERFLOW);s-top=s-base;s-stacksize=stack_init_size;returnOK;}/*创建栈*/statuspush(sqstack*s,selemtypee){if(s-top-s-base=s-stacksize){s-base=(elemtype*)realloc(s-base,(s-stacksize+stackincrement)*sizeof(elemtype));if(!s-base)exit(OVERFLOW);s-top=s-base+s-stacksize;s-stacksize+=stackincrement;}*(s-top++)=e;returnOK;}/*入栈*/statuspop(sqstack*s,selemtype*e){if(s-top==s-base)returnERROR;*e=*(--(s-top));returnOK;}/*出栈*/3.队列类型及其基本操作typedefstructqnode{qelemtypedata;structqnode*next;}qnode,*queueptr;typedefstruct{queueptrfront;queueptrrear;}linkqueue;statusinitqueue(linkqueue*q){q-front=q-rear=(queueptr)malloc(sizeof(qnode));if(!q-front)exit(OVERFLOW);q-front-next=NULL;returnOK;}/*创建队列*/statusenqueue(linkqueue*q,qelemtypee){queueptrp;p=(queueptr)malloc(sizeof(qnode));if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;q-rear-next=p;q-rear=p;returnOK;}/*入队*/statusdequeue(linkqueue*q,qelemtype*e){queueptrp;if(q-front==q-rear)returnERROR;p=q-front-next;*e=p-data;q-front-next=p-next;if(q-rear==p){q-rear=q-front;}free(p);returnOK;}/*出队*/四:调试分析1.函数调用比较多,因而得仔细对待数值和地址的传递.2.由于魔王语言中’B’中仍然包含着大写字母(tAdA).所以考虑设置flag.3.函数数组遍历.进栈出栈.入队出队中都要牵扯指针的移动,所以要仔细考虑一循环的条件以及进栈元素的个数.五:用户手册1.本程序运行环境为DOS/WINDOWS操作系统,执行文件为:魔王语言解释.exe。2.进入程序即显示提示信息:WELCOME!***************************************PleaseInputTheDemon'sWords:!:LessThan30Letters:)!:PleaseStoppedBy'#':)***************************************TheDemon'sWords:等待用户输入.用户输入字符以’#’回车结束.***************************************TheHumanWords:（翻译后的语言）***************************************THANKYOU!源程序（省略）测试结果