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

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

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

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

4、)B解释成：tsaedsaeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。tdsaezgxnh天地上一只鹅追赶下蛋恨三、概要设计为实现上述功能，需要栈和队列两个抽象数据类型。1. 栈抽象数据类型定义ADT stack数据对象：D=ai|aiElemset,i=1,2,3,n,n=0数据关系：R1=|ai-1,aiD,i=2, n基本操作：InitStack(&s)操作结果：构造一个空栈s。Push(&s, e)初始条件：栈s已存在。操作结果：插入元素e为新的栈顶元素。Pop(&

5、s, &e)初始条件：栈s已存在且非空。操作结果：删除栈s的栈顶元素，并用e返回其值。StackLenth(&s)初始条件：栈s已存在。操作结果：返回s的元素个数，即栈的长度。ClearStack(&s)初始条件：栈s已存在。操作结果：将s清为空栈。DestoryStack(&s)初始条件：栈s已存在。操作结果：栈s被销毁。StackEmpty(&s)初始条件：栈s已存在。操作结果：若是为空栈，则返回TRUE,否则返回FALSE。Traverse(&s,void(*visit)()初始条件：栈s已存在。操作结果：依次遍历栈s中的元素，依次调用函数，一旦失败，则操作失败。ADT stack2.

6、队列抽象数据类型定义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的元素个数，即队列的长度。DeQueue(&q, &e)初始条件：队列已存在。操作结果：删除Q的队尾元素，并用e返回其值。QueueEmpty(&q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FA

7、LSE.ClearQueue(&q)初始条件：队列Q已存在。操作结果：清空队列Q。DestoryQueue(&q)初始条件：队列Q已存在。操作结果：队列Q被销毁。不再存在。QueueTraverse(&q,Status(*visit)()初始条件：队列Q已存在。操作结果：依次遍历队列Q的元素，依次调用函数，一旦失败，则操作失败。ADT Queue流程图如下:本程序主要包括以下几个模块：主程序模块： int main()GhostLanage();printf(nt按任意键退出nn);各子程序模块： /*初始化栈*/void InitStack(SeqStack *s)s-top=-1;/*进栈

8、操作*/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栈为空！ );else *x=s-elems-top;s-top-;/*取栈顶元素*/void GetTop(SeqStack *s,StackElementType *x)if(s-top=-1)printf(nt栈为空！ );else

9、*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 choice,i=0,n;InitStack(&B);InitStack(&A);InitStack(&s);InitStack(&r);InitStack(&M);printf(魔王语言的转换形式： B-tAdA A-sa

10、e);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; while(IsEmpty(&B1) Pop(&B1,&ch1); if(ch1=A) A1=A; while(IsEmpty(&A1) Pop(&A1,&ch2); Push(&r,ch2); else Push(

11、&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); Pop(&M,&ch2); Push(&r,ch2); Push(&r,x); else Push(&r,ch);M=r;printf(nnt翻译的结果为： );while

12、(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(上); else if(ch=a) printf(一只); else if(ch=e) printf(鹅); else if(ch=z) print

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

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

15、ypedef structStackElementType 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(SeqStack *s);/*判断栈是否为空*/void GhostL

16、anage();/*魔王语言翻译函数*/3.主函数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,StackElementType *x)if(s-top=

17、-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);/4.魔王语言翻译函数void GhostLanage()SeqStack B,A,s,B1,A1,r,M;StackElementType ch,ch1,ch2,

18、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请输入要翻译的魔王语言:);scanf(%s,aa);for(i=0;a

19、ai!=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!=() Push(&M

20、,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;

21、 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 ;五、调试分析

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

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

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

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

26、mentType *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

27、)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栈为空！);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

28、*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 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);Push(&B,d);Push(&B,A);Push(&A,s);Push(&A,a);Push(&A,e)