数据结构第二次实验报告
- 格式：doc
- 大小：146.00 KB
- 文档页数：16
数据结构课程设计报告题目：魔王语言解释院系：信息学院班级：信管11-1姓名：丁升学号：201101050905指导教师：张晓庆实习报告题目：编制一个魔王语言翻译的程序班级：信息管理与信息系统11-1 姓名：丁升学号：201101050905 完成日期：2013.6.5一、需求分析1. 本演示程序中，魔王语言限制在小写字母‘a’-‘z’之间，且必须限制在括号内以及大写字母A和B。
且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。
2. 魔王语言遵守如下规则：（θδ1δ2δ3…δn）→θδnθδn-1…θδ1θB→tAdA A→sae3. 演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。
4. 程序的执行命令有：1）选择操作 2）任意键结束5. 数据测试B(ehnxgz)B解释成：tsaedsaeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。
二、概要设计为实现上述功能，需要栈和队列两个抽象数据类型。
1. 栈抽象数据类型定义ADT stack{数据对象：D={ai|ai∈Elemset,i=1,2,3,…n,n>=0}基本操作：InitStack(&s)操作结果：构造一个空栈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。
Traverse(&s,void(*visit)())初始条件：栈s已存在。
操作结果：依次遍历栈s中的元素，依次调用函数，一旦失败，则操作失败。
}ADT stack2. 队列抽象数据类型定义ADT Queue{数据对象：D={ai|ai∈Elemset,i=1,2,3,…n,n>=0}基本操作：InitQueue(&q)操作结果：构造一个空队列Q。
EnQueue(&q, e)初始条件：队列Q已存在。
操作结果：插入元素e为Q的新的队尾元素。
QueueLenth(&q)初始条件：队列已存在。
操作结果：返回Q的元素个数，即队列的长度。
DeQueue(&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 Queue3.本程序包含三个模块⑴主程序模块： int main(){GhostLanage();printf("\n\t按任意键退出\n\n");}⑵栈和队列模块—实现魔王语言的进栈和入队⑶魔王语言翻译模块—实现魔王语言的转换各模块之间的调用关系如下：主程序模块栈和队列模块魔王语言翻译模块三、详细设计1. 程序的头文件及全局变量的定义#include <stdio.h>#include <stdlib.h>#define StackElementType char#define Stack_Size 1002.栈类型及其基本操作typedef struct{StackElementType elem[Stack_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 GhostLanage();/*魔王语言翻译函数*/其中部分算法如下：/*初始化栈*/void InitStack(SeqStack *s){s->top=-1;}/*进栈操作*/void Push(SeqStack *s,StackElementType x){if(s->top==Stack_Size-1)printf("\n\t栈已满！");else {s->top++;s->elem[s->top]=x;}}/*出栈操作*/void Pop(SeqStack *s,StackElementType *x){if(s->top==-1)printf("\n\t栈为空！");else {*x=s->elem[s->top];s->top--;}}/*取栈顶元素*/void GetTop(SeqStack *s,StackElementType *x){if(s->top==-1)printf("\n\t栈为空！");else *x=s->elem[s->top];}/*判断栈是否为空*/int IsEmpty(SeqStack *s){if(s->top==-1) return(0);else return(1);}3.魔王语言翻译函数void GhostLanage(){SeqStack B,A,s,B1,A1,r,M;StackElementType ch,ch1,ch2,x;char aa[100];int choice,i=0,n;InitStack(&B);InitStack(&A);InitStack(&s);InitStack(&r);InitStack(&M); printf("\t\t*************魔王语言翻译程序***************\n");printf("\t\t*********\t\t\t************\t\n");printf("\t\t*********\t\t\t************\t\n");printf("\t\t*********\t\t\t************\t\n");Push(&B,'t');Push(&B,'A');Push(&B,'d');Push(&B,'A');Push(&A,'s');Push(&A,'a');Push(&A,'e');printf("\n\t\t\t请输入要翻译的魔王语言:");scanf("%s",aa);for(i=0;aa[i]!='\0';i++)Push(&s,aa[i]);while(IsEmpty(&s)){Pop(&s,&ch);if(ch=='B'){B1=B;while(IsEmpty(&B1))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);Pop(&M,&ch2);}Push(&r,x);}else Push(&r,ch);}M=r;printf("\n\n\t翻译的结果为：");while(IsEmpty(&M)){Pop(&M,&ch);printf("%c",ch);}printf("\n\n\t是否继续翻译为汉语：（1-继续，0-不继续）"); scanf("%d",&n);if(n==1){ printf("\n\n\t翻译为汉语的结果为：\n\n\t");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 ;}4.主函数int main(){GhostLanage();printf("\n\t按任意键退出\n\n");}四、调试分析1.若是括号外的从左到右入栈，并进行翻译，则出来的运行结果是反着的，并未达到要求的结果。
