《魔王语言解释数据结构课程设计报告.doc》由会员分享，可在线阅读，更多相关《魔王语言解释数据结构课程设计报告.doc（13页珍藏版）》请在金锄头文库上搜索。
1、-魔王语言解释程序一、 问题引入1. 问题描述有一个魔王总是使用自已的一种非常精练而抽象的语言讲话，没有人能听得懂。但他的语言是可以逐步解释成人能懂的语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：112m 2(12m)(m21) 在这两种形式中，从左到右均表示解释。写一个魔王解释程序，将魔王的话解释成人能听懂的话。2. 根本要求用下述两种规则和下述规则2实现。设大写字母表示魔王语言的词汇，小写字母表示人的词汇，希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。(1) BtAdA (2) Asae 3. 测试数据B(ein*gz)B解释成tsaedsae
2、ezege*eneietsaedsae假设将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅。tdsaezg*nh天地上一只鹅追赶下蛋恨4实现提示将魔王的语言自右至左进栈，总是处理栈顶字符。假设是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列在处理后入栈。5.本程序采用的是顺序栈。根本操作列表：(1) 据括号的个数设一个标记。记下括号的位置。(2) 根据标记来执行依次的操作。(3) 没有括号，直接进队，据翻译函数2输出人的语言。(4) 有括号，分为括号的和括号外的。，根据括号的位置：括号外的从右到
3、左入栈；括号的从左到右入栈，并且依次插入括号的第一个字符。据翻译函数2 出栈并且翻译。二、需求分析1. 本演示程序中，魔王语言限制在小写字母a-z之间，且必须限制在括号以及大写字母A和B。且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。2. 魔王语言遵守如下规则：123nnn-11BtAdA Asae 3. 演示程序以用户和计算机对话的形式进展，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。4. 程序的执行命令有：1选择操作 2任意键完毕5. 数据测试 B(ehn*gz)B解释成：tsaedsaeez
4、ege*enehetsaedsae假设将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅。tdsaezg*nh天地上一只鹅追赶下蛋恨三、概要设计为实现上述功能，需要栈和队列两个抽象数据类型。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(&s, &e)初始条件：栈s已存在且
5、非空。操作结果：删除栈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. 队列抽象数据类型定义ADT Qu
6、eue数据对象：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，否则返回FALSE.ClearQueue(
7、&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;/*进栈操作*/void Push(S
8、eqStack *s,StackElementType *)if(s-top=Stack_Size-1) printf(nt栈已满！ );else s-top+;s-elems-top=*;/*出栈操作*/void Pop(SeqStack *s,StackElementType *)if(s-top=-1)printf(nt栈为空！ );else *=s-elems-top;s-top-;/*取栈顶元素*/void GetTop(SeqStack *s,StackElementType *)if(s-top=-1)printf(nt栈为空！ );else *=s-elems-top;/*判断
9、栈是否为空*/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,*;char aa100;int choice,i=0,n;InitStack(&B);InitStack(&A);InitStack(&s);InitStack(&r);InitStack(&M);printf(魔王语言的转换形式： B-tAdA A-sae);Push(&B,t);Push(
10、&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(&r,ch1); else if(ch
11、=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); *=ch2; Pop(&M,&ch2); while(IsEmpty(&M) Push(&r,*); Pop(&M,&ch2); Push(&r,ch2); Push(&r,*); else Push(&r,ch);M=r;printf(nnt翻译的结果为： );while(IsEmpty(&M) Pop(&M
12、,&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) printf(追); else if(ch=g) printf(赶); else if(ch=*) printf(下); else if(ch=n) pri
