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

1、 课 程 设 计（数据结构）班 级 姓 名学 号 指导教师 课程设计任务书及成绩评定课题名称 魔王语言解释系统设计 、题目的目的和要求： 1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。2、设计题目要求： 【问题描述】 有一个魔王总是使用自己的一种非常精炼而抽象的语言讲话，没有人能听懂，但他的语言是可以逐步解释成人能听得懂的语言，因为他的语言是由以下两种

2、形式的规则逐步抽象上去的：（1）->12m（2）（12n）>nn-11   【基本要求】用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。我们有魔王语言的解释规则：（1）B>tAdA ；（2）A->sae；【测试数据】魔王语言 B(ehnxgz)B解释成tsaedsaeezegexenehetsaedsae。魔王语言tdsaexghnAtx解释成txtttsaetnthtgtztetatstdt、设计进度及完成情况日 期内 容1.10-1.11

3、选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。1.121.14创建相关数据结构,录入源程序。1.171.19调试程序并记录调试中的问题，初步完成课程设计报告。1.201.21上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。、主要参考文献及资料1 严蔚敏 数据结构（C语言版）清华大学出版社 19992 严蔚敏 数据结构题集（C语言版）清华大学出版社 19993 谭浩强 C语言程序设计 清华大学出版社4 与所用编程环境相配套的C语言或C+相关的资料、成绩评定：设计成绩： （教师填

4、写）指导老师： （签字）二一一 年 一 月 二 十一 日目 录第一章 概述1第二章 系统分析2第三章 概要设计第四章 详细设计第五章 运行与测试第六章 总结与心得参考文献第一章 概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及

5、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次的课程设计中我选择的题目是魔王语言解释系统。此魔王语言解释系统的具体作用是：针对魔王所说的人听不懂的语言，用符合题目要求的规则进行输出（翻译），解释成人类能听得懂的语言。在此用到数据结构所学习的栈的思想和队列的思想进行设计，将魔王所说的语言按照一定的规则进行一系列的入栈、出栈、入队、出队的操作，再按照魔王的语言对应的汉字进行输出。第二章 系统分析 1 魔王语言解释系统的基本业务活动包括：对魔王语言要说的话进行录入存储、判断语言是否符合规则、对语言进行转换输出等等。由于上述三种基本活动都是通过一定的先后顺序进行的，所以要用

6、到栈和队列的思想，以按一定的规则进行编排。故重点是要完成元素的入栈、出栈，队列的入队、出队等基本操作。2 既为魔王语言解释系统，就需要一个模块完成对语言规则的判断，另一个模块用来完成对语言的规则录入，规则输出，本程序使用栈来完成魔王语言的规则判断，用栈和队列结合的思想进行魔王语言的规则录入输出。3 演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言是转化。4 程序执行时的命令：本程序为了使用时的方便，采用了一个总体的大循环进行控制，用户几乎不用输入什么特殊的命令，只需按 提示输入魔王语言à判断魔王语言à魔王语言翻译 或者是 提示退出魔王语言

7、24;输入制定符号退出5.测试数据。魔王语言dAzgtA 解释成:dsaezgtsae,翻译成：地上一只鹅追赶天上一只鹅魔王语言 B(ehnxgz)B 解释成:tsaedsaeezegexenehetsaedsae,翻译成：天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅。第三章 概要设计1、 数据结构的设计本程序设计主要采用的数据结构是两种特殊的线性表：栈和队列。栈用来存储括号外的数据元素，队列用来存储括号内的数据元素。利用栈的“后进先出”的思想，队列的“先进先出”的思想进行设计。例如：将魔王语言dAzgtA 解释成:dsaezgtsae,翻译成：地上一只鹅追赶天上一只鹅将魔王

8、语言 B(ehnxgz)B 翻译成：tsaedsaeezegexenehetsaedsae,翻译成：天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅。此次设计的思想是线性进行的，因此只需用到特殊线性表进行数据的录入，规则编排，规则输出。2、 算法的设计本程序设计主要分为三个大的模块：（1）第一个模块是构造两种主要的线性表-栈和队列，以及设计线性表的主要应用函数：struct Stack（定义栈）、void InitStack(struct Stack &s) （构造栈）、void Push(struct Stack &s,char e)（往栈中压入元素）、void

9、 Pop(struct Stack &s,char &e)（取出栈中的元素）、int StackEmpty(struct Stack s)（判断栈是否为空）、void ClearStack(struct Stack &s)（清空栈）、struct Queue、struct LinkQueue（定义队列）、void InitQueue(struct LinkQueue &q)（构造队列）、void EnQueue(struct LinkQueue &q,char e)（元素入队）、void DeQueue(struct LinkQueue &q,c

10、har &e)（元素出队）、int QueueEmpty(struct LinkQueue q)（判断队列是否为空，如果对为空，返回1，否则返回0）、void InStack(char* ch,struct Stack &s)（把字符数组从右至左压入栈中）（2）第二个模块是录入魔王语言，对魔王语言进行判断，是否符合语言规则。对符合规则的语言进行后续操作，不符合语言规则的语言进行提示“ 魔王语言错误！”gets(MoWang); /变量MoWang存储输入的语言InStack(MoWang,S); /把要解释的魔王语言压入栈中while(!StackEmpty(S) /把魔王语言

11、进行出栈，不符合语言的进行提示 Pop(S,e1);if(e1='(') else if(e1=')')else if(!(e1>='a'&&e1<='z')&&!(e1>='A'&&e1<='Z') （3）第三个模块是对符合魔王语言规则的语言进行解释翻译。if(mark=1&&f=1) /对符合魔王语言规则的语言进行解释翻译 while(!StackEmpty(S) /魔王语言括号外的入栈，括号内入队Pop(S

12、,e1); if(e1='B'|e1='A') Push(temp,e1);/对大写字母直接入栈else if(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) /出队翻译成对应

13、的汉字 DeQueue(Q,e);switch(e) 3、 抽象数据类型的设计本程序所用到的数据类型是栈和队列的思想。其中所用到的抽象数据类型如下：（1） 定义栈：struct Stack char* base; char* top; int stacksize;（2） 构造栈：void InitStack(struct Stack &s) s.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char); s.top=s.base; s.stacksize=STACK_INIT_SIZE;（3） 往栈中压入元素：void Push(struct St

14、ack &s,char e) 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） 取出栈中的元素：void Pop(struct Stack &s,char &e) e=*-s.top;（5） 判断栈是否为空：int StackEmpty(struct

15、 Stack s) if(s.top=s.base) return 1; else return 0;（6） 清空栈：void ClearStack(struct Stack &s) s.top=s.base;（7） 定义队列：struct Queue char data; struct Queue* next;struct LinkQueue struct Queue* front; struct Queue* rear;（8） 构造队列：void InitQueue(struct LinkQueue &q) q.front=q.rear=(struct Queue*)mal

16、loc(sizeof(struct Queue); q.front->next=NULL;（9） 元素入队：void EnQueue(struct LinkQueue &q,char e) struct Queue* p; p=(struct Queue*)malloc(sizeof(struct Queue); p->data=e; p->next=NULL; q.rear->next=p; q.rear=p;（10） 元素出队：void DeQueue(struct LinkQueue &q,char &e) struct Queue* p;

17、 p=q.front->next; e=p->data; q.front->next=p->next; if(q.rear=p) q.rear=q.front; free(p);（11）判断队列是否为空，如果对为空，返回1，否则返回0： int QueueEmpty(struct LinkQueue q) if(q.front=q.rear) return 1; else return 0;第四章 详细设计#include<stdio.h>#include<stdlib.h>#define STACK_INIT_SIZE 100#define S

18、TACK_INCREMENT 10struct Stack /定义栈 char* base; char* top; int stacksize;void InitStack(struct Stack &s) /构造栈 s.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char); s.top=s.base; s.stacksize=STACK_INIT_SIZE;void Push(struct Stack &s,char e)/往栈中压入元素 if(s.top-s.base>=STACK_INIT_SIZE) s.base=(cha

19、r*)realloc(s.base,(s.stacksize+STACK_INCREMENT)*sizeof(char); s.top=s.base+s.stacksize; s.stacksize+=STACK_INCREMENT; *(s.top)=e; s.top+;void Pop(struct Stack &s,char &e) /取出栈中的元素 e=*-s.top;int StackEmpty(struct Stack s) /判断栈是否为空 if(s.top=s.base) return 1; else return 0;void ClearStack(struc

20、t Stack &s) /清空栈 s.top=s.base;struct Queue /定义队列 char data; struct Queue* next;struct LinkQueue struct Queue* front; struct Queue* rear;void InitQueue(struct LinkQueue &q) /构造队列 q.front=q.rear=(struct Queue*)malloc(sizeof(struct Queue); q.front->next=NULL;void EnQueue(struct LinkQueue &am

21、p;q,char e) /元素入队 struct Queue* p; p=(struct Queue*)malloc(sizeof(struct Queue); p->data=e; p->next=NULL; q.rear->next=p; q.rear=p;void DeQueue(struct LinkQueue &q,char &e) /元素出队 struct Queue* p; p=q.front->next; e=p->data; q.front->next=p->next; if(q.rear=p) q.rear=q.fr

22、ont; free(p);int QueueEmpty(struct LinkQueue q) /判断队列是否为空，如果对为空，返回1，否则返回0 if(q.front=q.rear) return 1; else return 0;void InStack(char* ch,struct Stack &s)/把字符数组从右至左压入栈中 int i,L=0; while(chL!='0') L+; for(i=L-1;i>=0;i-) Push(s,chi); int main() /主函数从此开始进行 printf("*n");printf(

23、"* * 欢迎光临山东理工大学 * *n");printf("* * *n");printf("* * 魔王语言解释系统 * *n");printf("* * *n");printf("* 班级：计算机科学与技术学院计升一班 *n");printf("* 姓名: 刘海龙 学号: 1021051005 *n");printf("*n");int xunhuan=1; printf("请输入你想要解释的魔王语言：n");while (xun

24、huan=1) /一个总循环控制整个程序的重复进行 int i=0; /i作为计数器 char A="sae" /大写字母作为字符数组名存放小写字母 char B="tsaedsae" char flag='0' /flag用来标记处理括号 char e1,key,e2,e; int mark=1; /标记输入的魔王语言是否在允许的范围之内 int f=1; / 判断括号是否匹配 char MoWang100="0" /定义一个魔王变量，存放待解释的语言字符 struct Stack S; /作为栈存储元素，为后续操作

25、和输出做准备 struct Stack temp; /用来处理括号外的元素 InitStack(S); InitStack(temp); struct LinkQueue Q; InitQueue(Q); gets(MoWang); /变量MoWang存储输入的语言 InStack(MoWang,S); /把要解释的魔王语言压入栈中 while(!StackEmpty(S) /把魔王语言进行出栈，不符合语言的进行提示 Pop(S,e1); if(e1='(') if(StackEmpty(S) printf("魔王语言错误!n"); mark=0;f=0;

26、break; while(!StackEmpty(S) Pop(S,e1); if(e1=')') f=1; break; else if(!(e1>='a'&&e1<='z')&&!(e1>='A'&&e1<='Z') printf("魔王语言错误！n"); mark=0; break; if(mark=0) break; if(f!=1) printf("魔王语言错误！n"); break; else

27、 if(e1=')') printf("魔王语言错误！n"); mark=0; break; else if(!(e1>='a'&&e1<='z')&&!(e1>='A'&&e1<='Z') printf("魔王语言错误！n"); mark=0; break; if(mark=1&&f=1) /对符合语言规则的魔王语言进行规则处理 ClearStack(S); InStack(MoWang

28、,S); /把魔王语言从右至左压栈存放 while(!StackEmpty(S) /栈不空时，用栈temp进行存储 Pop(S,e1); if(e1='B'|e1='A') Push(temp,e1); else if(e1='(') /用队存储括号中的元素 Push(temp,flag); /有括号的话就用flag标记 Pop(S,e1); while(e1!=')') /把括号中的元素存入队列中 EnQueue(Q,e1); Pop(S,e1); if(!QueueEmpty(Q) DeQueue(Q,key); /将队头的元

29、素赋值给key else Push(temp,e1); f=0; while(!StackEmpty(temp) /将魔王说的语言规则地压入栈s中 Pop(temp,e1); if(e1!=flag) Push(S,e1); /把括号外的元素压入中else while(!QueueEmpty(Q) /处理括号中的元素进栈 DeQueue(Q,e2); Push(S,key); Push(S,e2); if(f!=0) Push(S,key); /最后还要压一个key printf("解释后的语言为：n"); while(!StackEmpty(S) /依次出栈输出处理后的元

30、素 Pop(S,e); EnQueue(Q,e); /元素进队是为了输出对应汉字 if(e='B') printf("%s",B); else if(e='A') printf("%s",A); else printf("%c",e); printf("n"); while(!QueueEmpty(Q) /翻译成对应的汉字 DeQueue(Q,e); switch(e) /对应不同的解释输出相应的汉字 case 't': printf("天");b

31、reak; case 'd' : printf("地"); break; case 's' : printf("上"); break; case 'a' : printf("一只"); break; case 'e' : printf("鹅"); break; case 'z' : printf("追"); break; case 'g' : printf("赶"); break;

32、 case 'x' : printf("下"); break; case 'n' : printf("蛋"); break; case 'h' : printf("恨"); break; case 'B' : printf("天上一只鹅地上一只鹅");break; case 'A' : printf("上一只鹅");break; default : printf("*");break; print