1、数据结构数据结构课程设计课程设计 1 魔王语言解释魔王语言解释 一一 目的目的 通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理 论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设 计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能 力。 二二 需求分析需求分析 1、输入输出形式 输入一个用于表示魔王语言的字符串，用数组存储，输入应该是含有大小写字母及括 号的字符串；输出包括解释成表示认得语言词汇的小写字母和相对应的汉字。 2、程序功能 写一个魔王语言的解释系统，把他的话解释成人能听懂的话容。设大写字母表示魔王 语
2、言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换 的变量。魔王语言可含人的词汇。规则如下： 规则 1 (12. n)nn-1 1 规则 2 BtAdA 规则 3 Asae 例如，将 B（ehnxgz）B 解释成 tsaedsaeezegexenehetsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“B（鹅恨蛋下赶 追）B”。翻译输出为“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一 只鹅”。 t d s a e z g x n h 天 地 上 一只 鹅 追 赶 下 蛋 恨 三三 概要设计概要设计 1、数据类型定义及含义 本程序中
3、使用了栈和队列两种数据类型，其中使用 s 栈用于将魔王语言的所有元素压 入，temp 栈用于压入魔王语言中括号外面的元素，队列 q 用于放括号里面的元素。 数据结构数据结构课程设计课程设计 2 2、主程序流程 主程序先调用 InitStack 构造两个空栈 S 和 Temp，接着调用 InitQueue 构造队列 q，然 后通过调用函数 lhh 完成魔王语言的翻译。再通过询问方式询问用户是否继续进行操作。 3、各模块功能 各模块功能如下： main 主函数；InitStack 构造空栈；Push 入栈；Pop 出栈；StackEmpty 判断 栈是否为空；ClearStack 清空栈；Init
4、Queue 构造一个队列；EnQueue 入队； DeQueue 出队；QueueEmpty 判断队列是否为空；InStack 将字符数组所有元素入栈； check_MoWang 检验魔王语言是否正确；Translate 翻译魔王语言；lhh 核心代码部 分，处理括号里的元素以及调用其它函数翻译魔王语言。 四四 详细设计详细设计 1、数据类型的实现 程序中使用的栈和队列两种数据结构的类型定义如下： struct Stack /栈结构定义 char* base;/在构造之前和销毁之后，base 值为 NULL char* top;/栈顶指针 int stacksize;/当前已分配的存储空间 ;
5、 /队结构定义 struct Queue char data; struct Queue* next; ; struct LinkQueue struct Queue* front;/队头指针 struct Queue* rear;/队尾指针 ; 2、函数调用关系图 函数调用关系图如下，由于为了简化，下图中除了 main 函数以外都采用了概要设计第 3 部分中的函数标号代替函数名： 数据结构数据结构课程设计课程设计 3 3、主要函数模块的算法实现 void InStack(char* ch,struct Stack while(chL!=0) L+; for(i=L-1;i=0;i-) Pus
6、h(s,chi); void Translate(struct Stack char B=“tsaedsae“; char e; printf(“n 解释后的语言为：n “); while(!StackEmpty(s) /依次出栈输出处理后的元素 Pop(s,e); EnQueue(q,e);/元素进队 if(e=B) printf(“%s“,B);/规则 2 else if(e=A) printf(“%s“,A);/规则 3 else printf(“%c“,e); /while printf(“n 翻译后的语言为：n “); while(!QueueEmpty(q) /输出对应汉字 Main 数据结构数据结构课程设计课程设计 4 DeQueue(q,e); switch(
