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

1、数据结构实验报告2.2魔王语言解释问题描述有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的:a31P2Pm(051525n)05n05n10510在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。基本要求用下述两条具体规则和上述规则形式(2)实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。(1)BtAdA(2)Asae测试数据B(ehnxgz)B

2、解释成tsaedsaeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。tdsaezgxnh天地上一只鹅追赶下蛋恨一：需求分析(1)以一维数组demon】i表示魔王语言.魔王语言由用户输入，初始保存在demon】i中魔王语言与人类语言对应关系固化在程序中.(4)实现过程:A：初始，魔王语言接收后存放在demon】i中B：初次遍历数组，将数组中括号内的元素入栈，同时插入相应首字母；C：再次遍历数组，将数组元素依次入队。(小写字母直接入队；大写字母经翻译成相应字符后入队；遇到括号，将栈

3、中保存的元素依次出栈入队)在翻译过程中，如果依旧包含大写字母，则置flag为1,否则为0。D：将队列中元素赋值给demoni。如果此时flag=1,则再次重复C过程。直至所有元素为人类语言。E：输出demoni。此时数组中元素为对应的人类语言。注=如果程序中没有相应的对应关系，则翻译成“?”。概要设计:1=设定栈的抽象数据类型定义:ADTstack数据对象：D=ai|aiGCharSet,i=1,2,n,n=0数据关系：R1=|ai-1,aiGD,i=2,n基本操作：initstack(&s)操作结果:构造一个空栈s.push(&s,e)初始条件:栈s已存在.操作结果:在栈s的栈顶插入新的栈顶

4、元素e.pop(&s,&e)初始条件:栈s已存在.操作结果:删除s的栈顶元素，并以e返回其值.ADTstack2:设定队列的抽象数据类型：ADTqueue数据对象：D=ai|aiGElemset,i=1,2,n,n=0数据关系：R1=|ai-1,aiGD,i=2,n基本操作：initqueue(&q)操作结果：构造一个空队列q.enqueue(&q,e)初始条件：队列q已存在.操作结果：插入元素e为q的新队尾元素.dequeue(&q,&e)初始条件：q为非空队列.操作结果：删除q的队头元素，并用e返回其值.ADTqueue3:本程序包含四个模块:1）主函数模块其中主函数为:statusmai

5、n()初始化栈；初始化队列；接收魔王语言输入到数组demoni;遍历数组将括号中元素进栈；翻译while（数组demoni中元素有大写字母）翻译TOC o 1-5 h z将对列元素保存在数组demoni;输出人类语言（数组demoni）;2）括号内元素入栈处理模块.tempstack（&temps）将括号内元素入栈，依次插入首字符.举例：（abcd）adacaba3）排序入队列模块.sort（&s,&q）遍历数组；遇到小写字母，直接入队列；遇到大写字母，翻译大写后入队列；遇到括号，将栈中保存的元素依次出栈入队列；翻译大写处理模块.spenqueue(&*q,key)switch(key)找到各

6、个大写字母对应的字符串找到各个大写字母对应的字符串没有相应的则解释为?各模块之间调用关系：主函数模块括号内元素入栈处理模块;排序入队模块括号内元素入栈处理模块;排序入队模块翻译大写处理模块;三:详细设计1定义全局变量#defineTRUE#defineFALSE0#defineOK1#defineERROR#defineNULL#defineTRUE#defineFALSE0#defineOK1#defineERROR#defineNULL0#defineOVERFLOW-2#defineMAXSIZE0#defineOVERFLOW-2#defineMAXSIZE100#definestac

7、k_init_size100#definestackincrement10typedefcharselemtype;typedefcharqelemtype;typedefcharelemtype;typedefintstatus;chare;chardemonMAXSIZE;2栈类型及其基本操作typedefstructselemtype*base;selemtype*top;intstacksize;sqstack;TOC o 1-5 h zstatusinitstack(sqstack*s)s-base=(selemtype*)malloc(stack_init_size*sizeof(

8、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+=sta

9、ckincrement;*(s-top+)=e;returnOK;/*入栈*/statuspop(sqstack*s,selemtype*e)if(s-top=s-base)returnERROR;*e=*(-(s-top);returnOK;/*出栈*/3.队列类型及其基本操作typedefstructqnodeqelemtypedata;structqnode*next;qnode,*queueptr;typedefstructqueueptrfront;queueptrrear;linkqueue;statusinitqueue(linkqueue*q)q-front=q-rear=(q

10、ueueptr)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;/*入队*/TOC o 1-5 h zstatusdequeue(linkqueue*q,qelemtype*

11、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;returnOK;/*出队*/1.函数调用比较多，因而得仔细对待数值和地址的传递.递.2.由于魔王语言中B中仍然包含着大写字母(tAdA)所以考虑设置flag.3.函数数组遍历进栈出栈入队出队中都要牵扯指针的移动,所以要仔细考虑一循环的条件以及进栈元素的个数.五:用户手册1.本程序运行环境为DOS/WINDOWS操作系统,执行文件为：魔王语言解释.exe。2.进入程序即显示提示信息:WELCOME!PleaseInputTheDemonsWords:!:LessThan30Letters:)!:PleaseStoppedBy#:)TheDemonsWords: