魔王语言解释课程设计报告

山东理工大学计算机学院课程设计（数据结构）班级姓名学号指导教师二○一一年一月二十日课程设计任务书及成绩评定课题名称魔王语言解释系统设计Ⅰ、题目的目的和要求：1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（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。魔王语言tdsaexghnAtx解释成txtttsaetnthtgtztetatstdtⅡ、设计进度及完成情况日期内容1.10-1.11选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。1.12~1.14创建相关数据结构,录入源程序。1.17~1.19调试程序并记录调试中的问题，初步完成课程设计报告。1.20~1.21上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。Ⅲ、主要参考文献及资料[1]严蔚敏数据结构（C语言版）清华大学出版社1999[2]严蔚敏数据结构题集（C语言版）清华大学出版社1999[3]谭浩强C语言程序设计清华大学出版社[4]与所用编程环境相配套的C语言或C++相关的资料Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二○一一年一月二十一日目录第一章概述……………………………………………………………1第二章系统分析………………………………………………………2第三章概要设计………………………………………………………第四章详细设计………………………………………………………第五章运行与测试……………………………………………………第六章总结与心得……………………………………………………参考文献………………………………………………………………1第一章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次的课程设计中我选择的题目是魔王语言解释系统。此魔王语言解释系统的具体作用是：针对魔王所说的人听不懂的语言，用符合题目要求的规则进行输出（翻译），解释成人类能听得懂的语言。在此用到数据结构所学习的栈的思想和队列的思想进行设计，将魔王所说的语言按照一定的规则进行一系列的入栈、出栈、入队、出队的操作，再按照魔王的语言对应的汉字进行输出。2第二章系统分析1．魔王语言解释系统的基本业务活动包括：对魔王语言要说的话进行录入存储、判断语言是否符合规则、对语言进行转换输出等等。由于上述三种基本活动都是通过一定的先后顺序进行的，所以要用到栈和队列的思想，以按一定的规则进行编排。故重点是要完成元素的入栈、出栈，队列的入队、出队等基本操作。2．既为魔王语言解释系统，就需要一个模块完成对语言规则的判断，另一个模块用来完成对语言的规则录入，规则输出，本程序使用栈来完成魔王语言的规则判断，用栈和队列结合的思想进行魔王语言的规则录入输出。3．演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言是转化。4．程序执行时的命令：本程序为了使用时的方便，采用了一个总体的大循环进行控制，用户几乎不用输入什么特殊的命令，只需按提示输入魔王语言判断魔王语言魔王语言翻译或者是提示退出魔王语言输入制定符号退出5.测试数据。魔王语言dAzgtA解释成:dsaezgtsae,翻译成：地上一只鹅追赶天上一只鹅魔王语言B(ehnxgz)B解释成:tsaedsaeezegexenehetsaedsae,翻译成：天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅。3第三章概要设计1、数据结构的设计本程序设计主要采用的数据结构是两种特殊的线性表：栈和队列。栈用来存储括号外的数据元素，队列用来存储括号内的数据元素。利用栈的“后进先出”的思想，队列的“先进先出”的思想进行设计。例如：将魔王语言dAzgtA解释成:dsaezgtsae,翻译成：地上一只鹅追赶天上一只鹅将魔王语言B(ehnxgz)B翻译成：tsaedsaeezegexenehetsaedsae,翻译成：天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅。此次设计的思想是线性进行的，因此只需用到特殊线性表进行数据的录入，规则编排，规则输出。2、算法的设计本程序设计主要分为三个大的模块：（1）第一个模块是构造两种主要的线性表----栈和队列，以及设计线性表的主要应用函数：structStack（定义栈）、voidInitStack(structStack&s)（构造栈）、voidPush(structStack&s,chare)（往栈中压入元素）、voidPop(structStack&s,char&e)（取出栈中的元素）、intStackEmpty(structStacks)（判断栈是否为空）、voidClearStack(structStack&s)（清空栈）、structQueue、structLinkQueue（定义队列）、voidInitQueue(structLinkQueue&q)（构造队列）、voidEnQueue(structLinkQueue&q,chare)（元素入队）、voidDeQueue(structLinkQueue&q,char&e)（元素出队）、intQueueEmpty(structLinkQueueq)（判断队列是否为空，如果对为空，返回1，否则返回0）、voidInStack(char*ch,structStack&s)（把字符数组从右至左压入栈中）（2）第二个模块是录入魔王语言，对魔王语言进行判断，是否符合语言规则。对符合规则的语言进行后续操作，不符合语言规则的语言进行提示“魔王语言错误！”gets(MoWang);//变量MoWang存储输入的语言InStack(MoWang,S);//把要解释的魔王语言压入栈中while(!StackEmpty(S))//把魔王语言进行出栈，不符合语言的进行提示{Pop(S,e1);if(e1=='('){……}elseif(e1==')'){……}elseif(!(e1='a'&&e1='z')&&!(e1='A'&&e1='Z')){……}}4（3）第三个模块是对符合魔王语言规则的语言进行解释翻译。if(mark==1&&f==1)//对符合魔王语言规则的语言进行解释翻译{……while(!StackEmpty(S))//魔王语言括号外的入栈，括号内入队{Pop(S,e1);if(e1=='B'||e1=='A')Push(temp,e1);//对大写字母直接入栈elseif(e1=='('){……while(e1!=')'){EnQueue(Q,e1);Pop(S,e1);}……}else{……}}while(!StackEmpty(temp))//把语言规则的进栈{Pop(temp,e1);if(e1!=flag)Push(S,e1);else{……}}while(!StackEmpty(S))//把语言规则的入队{Pop(S,e);EnQueue(Q,e);……}while(!QueueEmpty(Q))//出队翻译成对应的汉字{DeQueue(Q,e);switch(e){5……}}3、抽象数据类型的设计本程序所用到的数据类型是栈和队列的思想。其中所用到的抽象数据类型如下：（1）定义栈：structStack{char*base;char*top;intstacksize;};（2）构造栈：voidInitStack(structStack&s){s.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));s.top=s.base;s.stacksize=STACK_INIT_SIZE;}（3）往栈中压入元素：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+s.stacksize;s.stacksize+=STACK_INCREMENT;}*(s.top)=e;s.top++;}（4）取出栈中的元素：voidPop(structStack&s,char&e){e=*--s.top;}（5）判断栈是否为空：intStackEmpty(structStacks){if(s.top==s.base)return1;elsereturn0;6}（6）清空栈：voidClearStack(structStack&s){s.top=s.base;}（7）定义队列：structQueue{chardata;structQueue*next;};structLinkQueue{structQueue*front;structQueue*rear;};（8）构造队列：voidInitQueue(structLinkQueue&q){q.front=q.rear=(structQueue*)malloc(sizeof(structQueue));q.front-next=NULL;}（9）元素入队：voidEnQueue(structLinkQueue&q,chare){structQueue*p;p=(structQueue*)malloc(sizeof(structQueue));p-data=e;p-next=NULL;q.rear-next=p;q.rear=p;}（10）元素出队：voidDeQueue(structLinkQueue&q,char&e){structQueue*p;p=q.front-next;e=p-data;7q.front-next=p-next;if(q.rear==p)q.rear=q.front;free(p);}（11）判断队列是否为空，如果对为空，返回1，否则返回0：intQueueEmpty(structLinkQueueq){if(q.front==q.rear)return1;elsereturn0;}8第四章详细设计#includestdio.h#includestdlib.h#defineSTACK_INIT_SIZE100#defineSTACK_INCREMENT10structStack//定义栈{char*base;char*top;intstacksize;};voidInitStack(structStack&s)/