《魔王语言数据结构试验报告.doc》由会员分享，可在线阅读，更多相关《魔王语言数据结构试验报告.doc（15页珍藏版）》请在三一文库上搜索。
1、 魔王语言系统解释一、 需求分析问题描述 有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没人能听的懂。但他的语言是可以逐步解释成人能懂得语言的，因为他的语言是由以下两种形式的规则由人的语言逐 步抽象上去的： （1）-12.n（2）(12.n)-nn-1.1 在这两种形式中，从左到右均表示解释；从右到左表示抽象。试写一个魔王解释系统，把 他的话解释成人能听懂得话。 基本要求 用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字 母表示人的语言词汇；希腊字母（a,b1,s,y1等）表示可以用大写或小写字母代换的变量。 魔王语言可含人的词汇。 （1）B-tAdA
2、(2) A-sae 测试数据 B（einxgz）B 解释成 tsaedsaeezegexeneietsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一个鹅地上一个鹅 鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅。” t d s a e z G x n i 天 地 上 一个 鹅 追 赶 下 蛋 恨 实现提示 将魔王的语言自右至左进栈，总是处理栈顶。若是开括号，则逐一出栈，将字母顺序入队 列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者 思考如何处理，应首先实现栈和队列的基本运算二、 概要设计 为实现上述程序功能，应以栈和队列来表示。1.
3、设定栈的抽象数据类型定义为： ADT Stack 数据对象：D=ai | aiCharSet，I=1，2，.，n,n0 数据关系：R1= |ai-1，aiD,I=1，2，.，n 基本操作： ListInitiate (&S) 操作结果：构造一个空栈S。StackEmpty（S）初始条件：栈S已经存在。操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。Push（&S,e）初始条件：栈S已经存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop（&S,&e）初始条件：栈S已经存在。操作结果：删除S的栈顶元素，并以e返回其值。 ADT Stack2. 设定队列的抽象数据类型定义为：ADTQ
4、ueue 数据对象：D=ai | aiElemSet，I=1，2，.，n,n0 数据关系：R1= |ai-1，aiD,I=1，2，.，n 基本操作： ListInitiate (&Q) 操作结果：构造一个空队列Q。StackEmpty（Q）初始条件：队列Q已经存在。操作结果：若队列Q为空栈，则返回TRUE，否则返回FALSE。EnQueue（&Q,e）初始条件：队列Q已经存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue（&Q,&e）初始条件：队列Q已经存在。操作结果：删除Q的对头元素，并以e返回其值。 ADT Queue2. 程序包含四个模块：1） 主程序模块：Void main(
5、)初始化；For（）接受处理命令；接受处理；2） 栈模块实现栈的抽象数据类型；3） 队列模块实现队列的抽象数据类型。4） 魔王语言解释模块定义线性表的结点结构。各模块的之间的调用关系如下： 主程序模块 魔王语言解释模块 栈模块队列模块三、详细设计1. 栈类型struct Stack char* base; char* top; int stacksize;2. 队列类型struct Stack char* base; char* top; int stacksize;struct LinkQueue struct Queue* front; struct Queue* rear;3.栈的基本操
6、作/构造栈void InitStack(struct Stack &s) s.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char); 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.stacksi
7、ze; s.stacksize+=STACK_INCREMENT; *(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;4队列的基本操作/构造队列void InitQueue(struct LinkQueue &q) q.front=q.rear=(
8、struct Queue*)malloc(sizeof(struct Queue); q.front-next=NULL;/元素入队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
9、-data; q.front-next=p-next; if(q.rear=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); 4.主函数和其他函数的算法（含注释）：#i
10、nclude#include#define STACK_INIT_SIZE 100#define STACK_INCREMENT 10int main() printf(*n); printf(* * *n); printf(* * 魔王语言解释系统 * *n); printf(* * *n); printf(* 班级：物联网工程1001班 *n); printf(* 姓名: * *n); printf(* 学号: 0909100818 *n); printf(*nn); int xunhuan=1; printf(请输入你想要解释的魔王语言：n); while (xunhuan=1) /一个
11、总循环控制整个程序的重复进行 char A=sae; /大写字母作为字符数组名存放小写字母 char B=tsaedsae; char flag=0; /flag用来标记处理括号 char e1,key,e2,e; int mark=1; /标记输入的魔王语言是否在允许的范围之内 int f=1; / 判断括号是否匹配 char MoWang100=0; /定义一个魔王变量，存放待解释的语言字符 struct Stack S; /作为栈存储元素，为后续操作和输出做准备 struct Stack temp; /用来处理括号外的元素 InitStack(S); InitStack(temp); s
12、truct LinkQueue 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&e1=
13、Z) printf(魔王语言错误！n); mark=0; break; if(mark=1&f=1) /对符合语言规则的魔王语言进行规则处理 ClearStack(S); InStack(MoWang,S); /把魔王语言从右至左压栈存放 while(!StackEmpty(S) /栈不空时，用栈temp进行存储不带括号内元素的元素 Pop(S,e1); if(e1=B|e1=A) Push(temp,e1); else if(e1=() /用队存储括号中的元素 Push(temp,flag); /有括号的话就用flag标记 Pop(S,e1); while(e1!=) /把括号中的元素存入队
14、列中 EnQueue(Q,e1); Pop(S,e1); if(!QueueEmpty(Q) DeQueue(Q,key); /将队头的元素赋值给key else Push(temp,e1); while(!StackEmpty(temp) /将魔王说的语言规则地压入栈s中 Pop(temp,e1); if(e1!=flag) Push(S,e1); /把括号外的元素压入中 else while(!QueueEmpty(Q) /处理括号中的元素进栈 DeQueue(Q,e2); Push(S,key); Push(S,e2); Push(S,key); /最后还要压一个key printf(解
15、释后的语言为：n); while(!StackEmpty(S) /依次出栈输出处理后的元素 Pop(S,e); EnQueue(Q,e); /元素进队是为了输出对应汉字 if(e=B) printf(%s,B); else if(e=A) printf(%s,A); else printf(%c,e); printf(n); while(!QueueEmpty(Q) /翻译成对应的汉字 DeQueue(Q,e); switch(e) case t: printf(天);break; case d : printf(地); break; case s : printf(上); break; ca
16、se a : printf(一只); break; case e : printf(鹅); break; case z : printf(追); break; case g : printf(赶); break; case x : printf(下); break; case n : printf(蛋); break; case h : printf(恨); break; case B : printf(天上一只鹅地上一只鹅);break; case A : printf(上一只鹅);break; default : printf(*);break; printf(n); printf(再次输
17、入魔王语言(按数字键：0-退出)n);scanf(%d,&xunhuan); return 0;四、调试分析1.函数调用。函数调用是语言中一块十分重要部分，它可以把一个程序分成若干部分，然后进行配置，所以这块内容一定要学好。2.栈和队列问题比较简单。3.由于考虑不周，如果同样的字母出现时，规则会要求重复输入，最终以最后一个为准，这是一个失误，后来改正程序，过滤掉重复字母。五、测试分析1、当输入A时系统显示：2、当输入B(ehnxgz)B是系统显示：六、用户手册 1、本程序运行在DOS命令下 2、进入程序后即显示用户界面：3、注意输入后即可得到相应的结果。七、附录（代码源程序及注释）#inclu
18、de#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(char); s.top=s.base; s.stacksize=STACK_INIT_SIZE;void Push(struct Stack &s,char e)/往栈中压入元素 if(s.top-s
19、.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; *(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 retu
20、rn 0;void ClearStack(struct Stack &s) /清空栈 s.top=s.base;struct Queue /定义队列 char data; struct Queue* next;struct LinkQueue struct Queue* front; struct Queue* rear;void InitQueue(struct LinkQueue &q) /构造队列 q.front=q.rear=(struct Queue*)malloc(sizeof(struct Queue); q.front-next=NULL;void EnQueue(struct
21、 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=p) q.rear=q.front; free(p);int QueueEmpt
22、y(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(* * 魔王语言解释系统 * *n); printf(* * *n); printf
23、(* 班级：物联网工程1001班 *n); printf(* 姓名: 彭国龙 *n); printf(* 学号: 0909100818 *n); printf(*nn); int xunhuan=1; printf(请输入你想要解释的魔王语言：n); while (xunhuan=1) /一个总循环控制整个程序的重复进行 char A=sae; /大写字母作为字符数组名存放小写字母 char B=tsaedsae; char flag=0; /flag用来标记处理括号 char e1,key,e2,e; int mark=1; /标记输入的魔王语言是否在允许的范围之内 int f=1; / 判
24、断括号是否匹配 char MoWang100=0; /定义一个魔王变量，存放待解释的语言字符 struct Stack S; /作为栈存储元素，为后续操作和输出做准备 struct Stack temp; /用来处理括号外的元素 InitStack(S); InitStack(temp); struct LinkQueue Q; InitQueue(Q); gets(MoWang); /变量MoWang存储输入的语言 InStack(MoWang,S); /把要解释的魔王语言压入栈中 while(!StackEmpty(S) /把魔王语言进行出栈，不符合语言的进行提示 Pop(S,e1); i
25、f(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&e1=Z) printf(魔王语言错误！n); mark=0; break; if(mark=1&f=1) /对符合语言规则的魔王语言进行规则处理 ClearStack(S); InStack(MoWang,S); /把魔王语言从右至左压栈存放 while(!StackEmpty(S) /栈不空时，用栈temp进行存储不带括号内元素的元素 Pop(S,e1); if(e1=B|e1=A) Push(temp,e1); else if(e1=() /用队存储括号中的元素 Push(temp,flag); /有括号的话就用flag标记 Pop(S,e1); while(e1!=) /把括号中的元素存入队列中 EnQueue(Q,e1); Pop(S,e1); if(!QueueEmpty(Q) DeQueue(Q,key); /将队头的元素赋值给key