魔王语言解释数据结构课程设计报告.pdf

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

1、（魔王语言解释程序 一、问题引入 1.问题描述 有一个魔王总是使用自已的一种非常精练而抽象的语言讲话，没有人能听得懂。但他的语言是可以逐步解释成人能懂的语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）12m （2）(12m)(m21)在这两种形式中，从左到右均表示解释。写一个魔王解释程序，将魔王的话解释成人能听懂的话。2.【3.基本要求 用下述两种规则和下述规则（2）实现。设大写字母表示魔王语言的词汇，小写字母表示人的词汇，希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。(1)BtAdA (2)Asae 3.测试数据 B(einxgz)B 解释成

2、 tsaedsaeezegexeneietsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。t d s a e z g x n!h 天 地 上 一只 鹅 追 赶#下 蛋 恨 4实现提示 将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列在处理后入栈。5.本程序采用的是顺序栈。基本操作列表：(1)据括号的个数设一个标记。记下括号的位置。(2)(3)根据标记来执行依次的操作。(4)没有括号，直接进队，据翻译函数 2 输出人的语言。(5

3、)有括号，分为括号内的和括号外的。，根据括号的位置：括号外的从右到左入栈；括号内的从左到右入栈，并且依次插入括号内的第一个字符。据翻译函数 2 出栈并且翻译。二、需求分析 1.本演示程序中，魔王语言限制在小写字母a-z之间，且必须限制在括号内以及大写字母 A 和 B。且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。2.魔王语言遵守如下规则：（123n）nn-11 BtAdA Asae 3.演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。4.程序的执行命令有：1）选择

4、操作 2）任意键结束 5.数据测试 B(ehnxgz)B 解释成：tsaedsaeezegexenehetsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。t d s a e z g x n h、天 地 上 一只 鹅 追 赶 下?蛋 恨 三、概要设计 为实现上述功能，需要栈和队列两个抽象数据类型。1.栈抽象数据类型定义 ADT stack 数据对象：D=ai|aiElemset,i=1,2,3,n,n=0*数据关系：R1=|ai-1,aiD,i=2,n 基本操作：InitStack(&s)操作结果：构造

5、一个空栈 s。Push(&s,e)初始条件：栈 s 已存在。操作结果：插入元素 e 为新的栈顶元素。Pop(&s,&e)?初始条件：栈 s 已存在且非空。操作结果：删除栈 s 的栈顶元素，并用 e 返回其值。StackLenth(&s)初始条件：栈 s 已存在。操作结果：返回 s 的元素个数，即栈的长度。ClearStack(&s)初始条件：栈 s 已存在。操作结果：将 s 清为空栈。?DestoryStack(&s)初始条件：栈 s 已存在。操作结果：栈 s 被销毁。StackEmpty(&s)初始条件：栈 s 已存在。操作结果：若是为空栈，则返回 TRUE,否则返回 FALSE。Trave

6、rse(&s,void(*visit)()初始条件：栈 s 已存在。操作结果：依次遍历栈 s 中的元素，依次调用函数，一旦失败，则操作失败。ADT stack 2.队列抽象数据类型定义 ADT Queue 数据对象：D=ai|aiElemset,i=1,2,3,n,n=0 数据关系：R1=|ai-1,aiD,i=2,n 基本操作：（InitQueue(&q)操作结果：构造一个空队列 Q。EnQueue(&q,e)初始条件：队列 Q 已存在。操作结果：插入元素 e 为 Q 的新的队尾元素。QueueLenth(&q)初始条件：队列已存在。操作结果：返回 Q 的元素个数，即队列的长度。DeQueu

7、e(&q,&e)初始条件：队列已存在。操作结果：删除 Q 的队尾元素，并用 e 返回其值。QueueEmpty(&q)初始条件：队列 Q 已存在。操作结果：若 Q 为空队列，则返回 TRUE，否则返回 FALSE.ClearQueue(&q)初始条件：队列 Q 已存在。、操作结果：清空队列 Q。DestoryQueue(&q)初始条件：队列 Q 已存在。操作结果：队列 Q 被销毁。不再存在。QueueTraverse(&q,Status(*visit)()初始条件：队列 Q 已存在。操作结果：依次遍历队列 Q 的元素，依次调用函数，一旦失败，则操作失败。ADT Queue 流程图如下:本程序主

8、要包括以下几个模块：主程序模块：int main()GhostLanage();printf(nt 按任意键退出nn);各子程序模块：/*初始化栈*/void InitStack(SeqStack*s)s-top=-1;/*进栈操作*/void Push(SeqStack*s,StackElementType x)if(s-top=Stack_Size-1)printf(nt 栈已满！);、else s-top+;s-elems-top=x;/*出栈操作*/void Pop(SeqStack*s,StackElementType*x)if(s-top=-1)printf(nt 栈为空！);el

9、se*x=s-elems-top;s-top-;./*取栈顶元素*/void GetTop(SeqStack*s,StackElementType*x)if(s-top=-1)printf(nt 栈为空！);else*x=s-elems-top;/*判断栈是否为空*/int IsEmpty(SeqStack*s)if(s-top=-1)return(0);else return(1);/*魔王语言翻译函数*/void GhostLanage()SeqStack B,A,s,B1,A1,r,M;StackElementType ch,ch1,ch2,x;char aa100;.int choic

10、e,i=0,n;InitStack(&B);InitStack(&A);InitStack(&s);InitStack(&r);InitStack(&M);printf(魔王语言的转换形式：B-tAdA A-sae);Push(&B,t);Push(&B,A);Push(&B,d);Push(&B,A);Push(&A,s);Push(&A,a);Push(&A,e);printf(n 请输入要翻译的魔王语言:n);scanf(%s,aa);for(i=0;aai!=0;i+)Push(&s,aai);while(IsEmpty(&s);Pop(&s,&ch);if(ch=B)B1=B;whi

11、le(IsEmpty(&B1)Pop(&B1,&ch1);if(ch1=A)A1=A;while(IsEmpty(&A1)】Pop(&A1,&ch2);Push(&r,ch2);else Push(&r,ch1);else if(ch=A).A1=A;while(IsEmpty(&A1)Pop(&A1,&ch2);Push(&r,ch2);else if(ch=)Pop(&s,&ch2);%while(ch2!=()Push(&M,ch2);Pop(&s,&ch2);GetTop(&M,&ch2);x=ch2;Pop(&M,&ch2);while(IsEmpty(&M)、Push(&r,x);

12、Pop(&M,&ch2);Push(&r,ch2);Push(&r,x);else Push(&r,ch);?M=r;printf(nnt 翻译的结果为：);while(IsEmpty(&M)Pop(&M,&ch);printf(%c,ch);printf(nnt 是否继续翻译为汉语：（1-继续，0-不继续）);scanf(%d,&n);if(n=1)printf(nnt 翻译为汉语的结果为：nnt);M=r;while(IsEmpty(&M)Pop(&M,&ch);if(ch=t)printf(天);else if(ch=d)printf(地);else if(ch=s)printf(上);

13、else if(ch=a)printf(一只);else if(ch=e)printf(鹅);else if(ch=z)printf(追);else if(ch=g)printf(赶);else if(ch=x)printf(下);else if(ch=n)printf(蛋);else if(ch=h)printf(恨);、printf(n);else;模块间的关系是：)主程序 翻译函数1 栈模块 四、详细设计 本程序中的主要函数有：-void InitStack(SeqStack*s);/*初始化栈*/void Push(SeqStack*s,StackElementType x);/*进栈

14、操作*/void Pop(SeqStack*s,StackElementType*x);/*出栈操作*/void GetTop(SeqStack*s,StackElementType*x);/*取栈顶元素*/int IsEmpty(SeqStack*s);/*判断栈是否为空*/void GhostLanage();/*魔王语言翻译函数*/函数间的调用关系：主程序调用魔王语言翻译函数，然后魔王语言翻译函数调用其它的函数（初始化栈，进栈，出栈，取栈顶元素，判断栈空），以此来实现整个程序的运行。程序的头文件及全局变量的定义#include#include#define StackElementTyp

15、e char#define Stack_Size 100 类型及其基本操作 typedef struct StackElementType elemStack_Size;int top;(SeqStack;void InitStack(SeqStack*s);/*初始化栈*/void Push(SeqStack*s,StackElementType x);/*进栈操作*/void Pop(SeqStack*s,StackElementType*x);/*出栈操作*/void GetTop(SeqStack*s,StackElementType*x);/*取栈顶元素*/int IsEmpty(S

16、eqStack*s);/*判断栈是否为空*/void GhostLanage();/*魔王语言翻译函数*/函数%int main()system(color 1b);GhostLanage();printf(nt 按任意键退出nn);/*初始化栈*/void InitStack(SeqStack*s)s-top=-1;/*进栈操作*/void Push(SeqStack*s,StackElementType x)if(s-top=Stack_Size-1)printf(nt 栈已满！);else s-top+;s-elems-top=x;/*出栈操作*/void Pop(SeqStack*s,

17、StackElementType*x)if(s-top=-1)printf(nt 栈为空！);else*x=s-elems-top;s-top-;/*取栈顶元素*/void GetTop(SeqStack*s,StackElementType*x)：if(s-top=-1)printf(nt 栈为空！);else*x=s-elems-top;/*判断栈是否为空*/int IsEmpty(SeqStack*s)if(s-top=-1)return(0);else return(1);王语言翻译函数 void GhostLanage()SeqStack B,A,s,B1,A1,r,M;StackE

18、lementType ch,ch1,ch2,x;char aa100;int choice,i=0,n;InitStack(&B);InitStack(&A);InitStack(&s);InitStack(&r);InitStack(&M);】printf(tt*魔王语言翻译程序*n);printf(tt*ttt*tn);printf(tt*ttt*tn);printf(tt*ttt*tn);Push(&B,t);Push(&B,A);Push(&B,d);Push(&B,A);Push(&A,s);Push(&A,a);Push(&A,e);printf(nttt 请输入要翻译的魔王语言:

19、);scanf(%s,aa);for(i=0;aai!=0;i+)Push(&s,aai);while(IsEmpty(&s)，Pop(&s,&ch);if(ch=B)B1=B;while(IsEmpty(&B1)Pop(&B1,&ch1);if(ch1=A)A1=A;while(IsEmpty(&A1)Pop(&A1,&ch2);Push(&r,ch2);else Push(&r,ch1);else if(ch=A)A1=A;while(IsEmpty(&A1)Pop(&A1,&ch2);Push(&r,ch2);else if(ch=)Pop(&s,&ch2);while(ch2!=()P

20、ush(&M,ch2);Pop(&s,&ch2);GetTop(&M,&ch2);x=ch2;Pop(&M,&ch2);while(IsEmpty(&M)、Push(&r,x);Pop(&M,&ch2);Push(&r,ch2);Push(&r,x);else Push(&r,ch);】M=r;printf(nnt 翻译的结果为：);while(IsEmpty(&M)Pop(&M,&ch);printf(%c,ch);printf(nnt 是否继续翻译为汉语：（1-继续，0-不继续）);scanf(%d,&n);*if(n=1)printf(nnt 翻译为汉语的结果为：nnt);M=r;whi

21、le(IsEmpty(&M)Pop(&M,&ch);if(ch=t)printf(天);else if(ch=d)printf(地);else if(ch=s)printf(上);else if(ch=a)printf(一只);else if(ch=e)printf(鹅);else if(ch=z)printf(追);else if(ch=g)printf(赶);else if(ch=x)printf(下);else if(ch=n)printf(蛋);else if(ch=h)printf(恨);printf(n);else;五、调试分析 1.若是括号外的从左到右入栈，并进行翻译，则出来的运

22、行结果是反着的，并未达到要求的结果。所以进行调试，发现应该从右到左入栈，根据出栈的顺序，先进后出，正好可以达到相应的结果。2.、3.括号内的字符的入栈错误。本来只是将括号内的字符也是据 1 从右到左入栈。并且循环插入括号内的第一个字符。发现结果又是反的。据调试，发现括号内的字符应该是从左到右入栈，正好符合规则 1，结果未相反。4.将括号内的第一个字符按照循环，进一个字符，再插一个括号内的第一个字符。发现结果与规则 1 不符，所以据调试，应在循环外先插入一个括号内的第一个字符，后再进行以上的循环，这样输出的结果与规则 1 相符，并且第一个输出的不会少了括号内的第一个字符，也不会重复第一个字符的输

23、出。5.指针和地址符的误用。在调用函数时，总是误用这两个符号，导致许多不必要的错误。所以，经过调试，也熟悉了这两个符号的用法。六、用户手册 第一步：启动魔王语言.exe 应用程序，进入程序界面，如下：第二步：输入要翻译的魔王语言后按 Enter 键确认，结果如下：第三步：程序将输入翻译为魔王语言后会再次询问要不要翻译为汉语，如果要翻译为汉语，选择 1，按 Enter 确认，则程序会再次将魔王语言翻译为汉语形式。具体如下：第四步：翻译结束后按任意键退出程序。、七、测试结果 输入的魔王语言为：B(ehnxgz)B 翻译的结果为：tsaedsaeezegexenehetsaedsae 翻译为汉语的结

24、果为：天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅 结论：此程序能够按照给定的翻译规则解释魔王语言。八、结束语 通过这个实验。特别是实验中对栈的应用，让我更深入的了解了栈的特性，更加了解了栈的构造及构造方法。这次实验实现了简单的魔王语言解释，按照给定的规则能够翻译出一句有意义的话，但不足的是，程序中的规则是指导书中给定的规则，没有定义出自己的规则，在今后的时间里，还需要自己进行不断的改善，争取能够自己定义规则。这次实验对魔王语言的解释，让我看到了如何对信息进行简单的加密，看到了加密的雏形，这对于今后更深入的学习起到了启蒙的作用。总的来说，这次实验让我收获了很多，同时也让我发现

25、了很多的不足，希望在今后的学习中，不断努力，使程序更加的完美。#九、附录 程序源代码如下：#include#include&#define StackElementType char#define Stack_Size 100 typedef struct StackElementType elemStack_Size;int top;SeqStack;void InitStack(SeqStack*s);/*初始化栈*/void Push(SeqStack*s,StackElementType x);/*进栈操作*/$void Pop(SeqStack*s,StackElementType*

26、x);/*出栈操作*/void GetTop(SeqStack*s,StackElementType*x);/*取栈顶元素*/int IsEmpty(SeqStack*s);/*判断栈是否为空*/void GhostLanage();/*魔王语言翻译函数*/*主函数*/int main()system(color 1b);/GhostLanage();printf(nt 按任意键退出nn);/*初始化栈*/void InitStack(SeqStack*s)s-top=-1;/*进栈操作*/void Push(SeqStack*s,StackElementType x)if(s-top=Sta

27、ck_Size-1)printf(nt 栈已满！);else s-top+;s-elems-top=x;/*出栈操作*/void Pop(SeqStack*s,StackElementType*x)if(s-top=-1)printf(nt 栈为空！);else*x=s-elems-top;s-top-;/*取栈顶元素*/void GetTop(SeqStack*s,StackElementType*x)if(s-top=-1)printf(nt 栈为空！);else*x=s-elems-top;|/*判断栈是否为空*/int IsEmpty(SeqStack*s)if(s-top=-1)re

28、turn(0);else return(1);/*魔王语言翻译函数*/void GhostLanage()￥SeqStack B,A,s,B1,A1,r,M;StackElementType ch,ch1,ch2,x;char aa100;int choice,i=0,n;InitStack(&B);InitStack(&A);InitStack(&s);InitStack(&r);InitStack(&M);printf(tt*魔王语言解释程序*n);printf(tt*tt*tn);printf(tt*tt*tn);printf(tt*tt*tn);Push(&B,t);Push(&B,A

29、);Push(&B,d);Push(&B,A);Push(&A,s);Push(&A,a);Push(&A,e);（printf(ntt 请输入要翻译的魔王语言:);scanf(%s,aa);for(i=0;aai!=0;i+)Push(&s,aai);while(IsEmpty(&s)Pop(&s,&ch);if(ch=B)B1=B;while(IsEmpty(&B1)Pop(&B1,&ch1);if(ch1=A)A1=A;while(IsEmpty(&A1)Pop(&A1,&ch2);Push(&r,ch2);else Push(&r,ch1);else if(ch=A)A1=A;whil

30、e(IsEmpty(&A1)Pop(&A1,&ch2);Push(&r,ch2);else if(ch=)Pop(&s,&ch2);while(ch2!=()Push(&M,ch2);Pop(&s,&ch2);GetTop(&M,&ch2);x=ch2;Pop(&M,&ch2);while(IsEmpty(&M)Push(&r,x);Pop(&M,&ch2);Push(&r,ch2);Push(&r,x);else Push(&r,ch);M=r;printf(nnt 翻译的结果为：);while(IsEmpty(&M)Pop(&M,&ch);printf(%c,ch);printf(nnt

31、是否继续翻译为汉语：（1-继续，0-不继续）);scanf(%d,&n);if(n=1)printf(nnt 翻译为汉语的结果为：nnt);M=r;while(IsEmpty(&M)Pop(&M,&ch);if(ch=t)printf(天);else if(ch=d)printf(地);else if(ch=s)printf(上);else if(ch=a)printf(一只);else if(ch=e)printf(鹅);else if(ch=z)printf(追);else if(ch=g)printf(赶);else if(ch=x)printf(下);else if(ch=n)printf(蛋);else if(ch=h)printf(恨);printf(n);else;