魔王语言解释（数据结构课程设计）.doc

《魔王语言解释（数据结构课程设计）.doc》由会员分享，可在线阅读，更多相关《魔王语言解释（数据结构课程设计）.doc（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、魔王语言解释1、绪论1.1 背景随着网络技术的发展，网络安全变得越来越重要，文件加密是其中一个重要部分。而“魔王语言”就是一个简单的文件加密。“魔王语言”就是有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是有规则的，可以通过相应的规则来解释。通过这次设计，要求在数据结构逻辑特性和物理分析、数据结构的选择和应用、算法的设计及其实现等方面，加深对基础知识的理解。同时，在程序设计方法以及上机造作等基本技能方面受到严格的训练。2、需求分析 题目魔王语言解释。2.2 基本要求 魔王的话没有人能听得懂，但他的语言是可以逐步解释

2、成人能听懂的语言，有着下面的基本要求：用下述两条具体规则和下述规则形式2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。以下是他的语言的两种形式的规则有语言逐步抽象上去的： 1） 转换为 12m 2）（12n） 转换为 nn1 1 在这两种形式重，从左到右均表示解释。试写一个魔王语言的解释兄，把他的话解释成人能听得懂的话。因此，我们编写了一个有趣的魔王语言解释程序来巩固和加强对栈和队列的理解。以下是他的语言的两种形式的具体规则： A 转换为 hdwhz，B 转化为 hasff，C 转化为 hwhll，D 转化

3、为 hkhbf，E 转化为 hkwsx，F 转化为 hxwsb。 h 转化为 “花”，d 转化为 “蝴蝶”，w 转化为 “为”，z 转化为 “醉”，s 转化为 “随”，fe 转化为 “风”，f 转化为 “飞”，k 转化为 “开”，ku 转化为 “哭”，b 转化为 “悲”，x 转化为 “谢”，l 转化为 “落泪”，ba 转化为 “瓣”。 A 转化为 “蝴蝶为花瓣”，B 转化为“花却随风飞”，C 转化为“花舞花落泪”，D 转化为“花哭花瓣飞”，E 转化为“花开为谁谢”，F 转化为“花谢为谁悲”。 2.3数据测试B（hdwz）B解释成 hasffhzhwhdhhasff 若将小写字母与汉字建立下表所

4、示的对应关系，则魔王说的话是：“花却随风飞花醉花为花蝴蝶花花却随风飞”。h z w d s f 花 醉 为 随 飞 2.4实现分析 以一维数组demon i 表示魔王语言 魔王语言由用户输入,初始保存在demon i 中 魔王语言与人类语言对应关系固化在程序中2.5实现过程 初始，魔王语言接收后存放在demon i 中 遍历数组，将数组中括号内的元素入栈，同时插入相应首字母； 再次遍历数组，将数组元素依次入队。（小写字母直接入队；大写字母翻译成相应字符入队；遇到括号，将栈中保存的元素依次出栈入队）在翻译过程中，如果依旧包含大写字母，则置flag为1，否则为0。 将队列中元素赋值给demon i

5、 。如果此时flag=1，则再次重复C过程。直至所有元素为人类语言。 输出demon i 。此时数组中元素为对应的人类语言。注：如果程序中没有相应的对应关系，则翻译成“?”。3、概要设计3.1 数据流程图魔王语言解释学年设计包括了主函数和栈和队列的操作两大部分，其中栈和队列的操作部分有构建、添加、删除、查找等函数。具体流程如图1：图1 数据流程图栈的抽象数据类型定义：ADT stack 数据对象：D=ai |aiCharSet,i=1,2,n,n=0 数据关系：R1=|ai-1,aiD，i=2，n基本操作：Initstack(&s)操作结果：构造一个空栈s.Push(&s,e)初始条件：栈s已

6、存在.操作结果：在栈s的栈顶插入新的栈顶元素e.Pop(&s,&e)初始条件：栈s已存在.操作结果：删除s的栈顶元素，并以e返回其值.ADT stack3.3设定队列的抽象数据类型：ADT queue数据对象：D=ai |aiElemset,i=1,2,n,n=0数据关系：R1=|ai-1,aiD,i=2,n基本操作：Initqueue(&q)操作结果：构造一个空队列q.Enqueue(&q,e)初始条件：队列q已存在.操作结果：插入元素e为q的新队尾元素.Dequeue(&q,&e)初始条件：q为非空队列.操作结果：删除q的队头元素，并用e返回其值.ADT queue3.4本程序包含四个模块

7、：主函数模块，其中主函数为：Status main()初始化栈；初始化队列；接收魔王语言输入到数组demoni；遍历数组将括号中元素进栈；While(数组demoni中元素有大写字母) 翻译排序处理后入队列；将队列元素保存在数组demoni； 输出人类语言（数组demoni）；括号内元素入栈处理模块.Tempstack(&temps)将括号内元素入栈，依次插入首字符.举例：(abcd)-adacaba.排序入队列模块.Sort(&s,&q) 遍历数组； 遇到小写字母，直接入队列；遇到大写字母，翻译大写后入队列；遇到括号，将栈中保存的元素依次出栈入队； 翻译大写处理模块. Spenqueue(&

8、*q,key)Switch(key) 找到各个大写字母对应的字符串.没有相应的则解释为?？ 各模块之间调用关系：主函数模块括号内元素入栈处理模块：排序入队模块翻译大写处理模块； 4、详细设计及宏的定义 #include#include#define STACK_INIT_SIZE 100#define STACK_INCREMENT 104.2 定义主函数主函数流程图如图2所示图2 主函数流程图主函数的编写，在主函数中编译魔王语言所遵循的规则，及栈、队列、相关数组结构的定义与调用，及输出结果的显示int main() /主函数从此开始进行 printf(*n); printf(* * 欢迎来到

9、滁州学院 * *n); printf(* * *n); printf(* * 魔王语言解释系统 * *n); printf(* * *n); printf(* * 班级：网络工程（2）班 * *n); printf(* * 组别：组1 * *n); printf(*n); int xunhuan=1;/是下面的 while循环一定执行 printf(请输入你想要解释的魔王语言：n); while (xunhuan=1) /一个总循环控制整个程序的重复进行 char A7=hdwhz,; /大写字母作为字符数组名存放小写字母 char B7=hqsff,; char C7=hwhll,; cha

10、r D7=hkhbf,; char E7=hkwsx,; char F7=hxwsb!; char flag=0; /flag用来标记处理括号 char e1,key,e2,e; /定义char型变量 int mark=1; /标记输入的魔王语言是否在允许的范围之内 int f=1; / 判断括号是否匹配 char MoWang100=0; /定义一个魔王变量，存放待解释的语言字符 struct Stack S; /作为栈存储元素，为后续操作和输出做准备 struct Stack temp; /用来处理括号外的元素 InitStack(S); InitStack(temp); struct L

11、inkQueue 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; break; while(!StackEmpty(S) Pop(S,e1); if(e1=) f=1; break; else if(!(e1=a&e1=A&e1=a&e1=A

12、&e1=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+;取出栈中的元素：出栈时，遵循先进后出的原则。提取指向的前一个元素。void Pop(struct Stack &s,char &e) /取出栈中的元素 e=*-s.top;判断栈是否为空：当提取

13、一个元素之后，进行判断。判断和是否满足。如果满足则栈为空，如果不满足则栈不为空程序继续进行。int StackEmpty(struct Stack s) /判断栈是否为空 if(s.top=s.base) return 1; else return 0;void ClearStack(struct Stack &s) /清空栈 s.top=s.base;把字符数组从右至左压入栈中：首先统计所有字符数据，然后将统计的字符按顺序从右往左压入栈中。void InStack(char* ch,struct Stack &s)/把字符数组从右至左压入栈中 int i,L=0; while(chL!=0)

14、 L+; for(i=L-1;i=0;i-) Push(s,chi); 44队列的初始化、进队列、出队列、判空 定义队列：队列时只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。允许插入的一端为队尾，允许删除的一端为队头。struct Queue /定义队列 char data; struct Queue* next;struct LinkQueue struct Queue* front; struct Queue* rear; 构造队列：构造一个队列，定义队列的空间大小，并确定队头。void InitQueue(struct LinkQueue &q) /构造队列 q.fron

15、t=q.rear=(struct Queue*)malloc(sizeof(struct Queue); q.front-next=NULL; 元素入队：元素入队遵循先进先出原则。定义一个指针P，并确定指针的空间大小。同时使指针P所在的地址为队头，即确定队头。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; 元素出队：定义一个指针型

16、队列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.front; free(p); 判空int QueueEmpty(struct LinkQueue q) /判断队列是否为空，如果对为空，返回，否则返回

17、 if(q.front=q.rear) return 1; else return 0;5、调试结果输入正确的魔王语言ABCDEF经翻译为“蝴蝶为花醉，花却随风飞，花舞花落泪，花哭花瓣飞，花开为谁谢，花谢为谁悲”。若继续翻译魔王的语言按数字1，退出程序按数字0调试结果如图3所示：输入语言在规则范围内的正确调试结果图3 符合测试要求的运行结果输入魔王语言ZJIAEFD,因为又不在规则范围内的语言所以翻译为“*蝴蝶为花醉，花开为谁谢，花谢为谁悲！花哭花瓣飞，”。若继续翻译魔王的语言按数字1，退出程序按数字0调试结果如图4所示：输入语言部分在规则范围内的调试结果图4 部分符合测试要求的运行结果输入错

18、误的魔王语言UKUITYOJOIOI;LOW则显示魔王语言错误。若继续翻译魔王的语言按数字1，退出程序按数字0调试结果如图5所示 ：输入语言全部不在规则范围内的调试结果及错误的魔王语言图5 完全不符合测试要求的运行结果6、学年设计总体设计与体会在设计的过程中，主要使用到了数据结构中的栈和队列，将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列在处理后入栈。此课程设计旨在解决魔王的语言逐步翻译为人能听懂的语言，可扩充为对相应简单加密的文件进行翻译解释。通过三次分别测试，包括符合测试要求、部分符合测试要求、不符合测试要求，并

19、且实验结果和我们预想的一样，说明了魔王语言解释系统是符合学年设计任务要求的。本学年设计，一方面在透彻地理解c语言和数据结构的基本概念和原理之上，使之由抽象理论转变成了具体的实际应用，化抽象为具体；另一方面，通过本学年设计极大地增强了该小组成员的实验手段与实践技能，提高了发现问题、分析问题、解决问题的能力。培养了应用知识的能力、团队合作精神和创新精神。虽然遇到了各种各样的问题，但是在设计的过程中我们发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，不过通过对所学课程的复习和老师的耐心指导设计终于顺利完成了，在此再次感谢刘老师。7、参考文献1 严蔚敏,吴伟民.数据结构M.北京

20、:清华大学出版社,2002.2 严蔚敏,吴伟民.数据结构题集(C语言版)M.北京:清华大学出版社,2003.3 胡学钢.数据结构(C语言版) M.北京:高等教育出版社,1999.8、附录#include#include#define STACK_INIT_SIZE 100#define STACK_INCREMENT 10struct Stack /定义栈 char* base; char* top; int stacksize;void InitStack(struct Stack &s) /构造栈 s.base=(char*)malloc(STACK_INIT_SIZE*sizeof(ch

21、ar);/栈动态分配空间 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=(char*)realloc(s.base,(s.stacksize+STACK_INCREMENT)*sizeof(char);/再分配 s.top=s.base+s.stacksize;/栈顶指针上移 s.stacksize+=STACK_INCREMENT;/栈的空间增

22、加 /不超过分配空间 *(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(struct Stack &s) /清空栈 s.top=s.base;struct Queue /定义队列 char data; struct Queue* next;struct LinkQueue struct Queue* front

23、; struct Queue* rear;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;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=

24、p) q.rear=q.front; free(p);int QueueEmpty(struct LinkQueue q) /判断队列是否为空，如果对为空，返回，否则返回 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(* * 欢迎来到滁州学院 * *n); printf(* *