魔王语言数据结构实验报告课案

1、数据结构实验报告2.2 魔王语言解释 问题描述有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1） 1 2, m（2）（ 1 2, n） nn 1, 1在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。 基本要求用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。（ 1） B tAdA （ 2） A sae

2、测试数据B（ehnxgz）B 解释成 tsaedsaeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是： “天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天 上一只鹅地上一只鹅”。 t d s a e z g x nh 天 地 上 一只 鹅 追 赶 下 蛋 恨一：需求分析以一维数组demon i 表示魔王语言魔王语言由用户输入, 初始保存在demon i 中 (3)魔王语言与人类语言对应关系固化在程序中(4) 实现过程：A：初始，魔王语言接收后存放在demon i 中B：初次遍历数组，将数组中括号内的元素入栈，同时插入相应首字母；C：再次遍历数组，将数

3、组元素依次入队。(小写字母直接入队；大写字母经翻译成相应字符后入队；遇到括号，将栈中保存的元素依次出栈入队)在翻译过程中，如果依旧包含大写字母，则置flag 为 1，否则为0。D：将队列中元素赋值给demon i 。如果此时flag=1 ，则再次重复C过程。直至所有元素为人类语言。E：输出demon i 。此时数组中元素为对应的人类语言。注： 如果程序中没有相应的对应关系，则翻译成 “ ?”。 二：概要设计：1：设定栈的抽象数据类型定义：ADT stack 数据对象：Dai|ai CharSet,i 1,2, , ,n,n=0 数据关系：R1 |ai-1,ai D,i 2, , ,n 基本操作

4、： TOC o 1-5 h z initstack ( s)操作结果: 构造一个空栈s. push ( s,e)初始条件: 栈 s 已存在.操作结果: 在栈 s 的栈顶插入新的栈顶元素e.pop( s, e)初始条件: 栈 s 已存在 .操作结果: 删除 s 的栈顶元素, 并以 e 返回其值 . ADT stack设定队列的抽象数据类型:ADT queue数据对象：Dai|ai Elemset,i 1,2, , ,n,n=0 数据关系：R1 |ai-1,ai D,i 2, , ,n 基本操作：initqueue(&q)操作结果: 构造一个空队列q.enqueue(&q, e)初始条件: 队列

5、q 已存在 .操作结果: 插入元素e 为 q 的新队尾元素.dequeue(&q,&e) TOC o 1-5 h z 初始条件: q 为非空队列.操作结果: 删除 q 的队头元素, 并用 e 返回其值 . ADT queue本程序包含四个模块:1)主函数模块. 其中主函数为:status main() 初始化栈; 初始化队列;接收魔王语言输入到数组demoni ; 遍历数组将括号中元素进栈;while( 数组 demoni 中元素有大写字母) 翻译排序处理后入队列;将对列元素保存在数组demoni ;输出人类语言( 数组 demon i); 括号内元素入栈处理模块. tempstack(&te

6、mps)将括号内元素入栈, 依次插入首字符. 举例： (abcd) adacaba.排序入队列模块. sort(&s,&q) TOC o 1-5 h z 遍历数组; 遇到小写字母, 直接入队列;遇到大写字母, 翻译大写后入队列;遇到括号, 将栈中保存的元素依次出栈入队列 ; 翻译大写处理模块. spenqueue(&*q,key) switch(key) 找到各个大写字母对应的字符串. 没有相应的则解释为? 各模块之间调用关系: 主函数模块括号内元素入栈处理模块;排序入队模块翻译大写处理模块; 三 : 详细设计定义全局变量#define TRUE 1 #define FALSE 0 #defi

7、neOK 1 #define ERROR 0 #define NULL0 #define OVERFLOW -2 #define MAXSIZE100 #define stack_init_size 100 #define stackincrement 10typedef char selemtype; typedef char qelemtype;typedef char elemtype; typedef int status;char e;char demonMAXSIZE;栈类型及其基本操作typedef struct selemtype *base; selemtype *top;

8、intstacksize; sqstack;status initstack (sqstack *s) s-base=(selemtype*)malloc(stack_init_size*sizeof(selemtype);if(!s-base) exit (OVERFLOW); s-top=s-base;s-stacksize=stack_init_size; returnOK; /*创建栈 */status push (sqstack *s,selemtype e) if(s-top-s-base=s-stacksize) s-base=(elemtype *)realloc(s-base

9、,(s-stacksize+stackincrement)*sizeo f(elemtype); if(!s-base) exit(OVERFLOW);s-top=s-base+s-stacksize;s-stacksize+=stackincrement; *(s-top+)=e; return OK; /*入栈 */status pop(sqstack *s,selemtype *e) if(s-top=s-base) return ERROR;*/*e=*(-(s-top); return OK; /*/队列类型及其基本操作typedef struct qnode qelemtype d

10、ata; struct qnode*next; qnode,*queueptr; typedef struct queueptr front; queueptr rear; linkqueue;status initqueue(linkqueue *q) q-front=q-rear=(queueptr)malloc(sizeof(qnode);OK; /* OK; /* 创建队列*/q-front-next=NULL; returnstatus enqueue(linkqueue *q,qelemtype e) queueptr p;p=(queueptr)malloc(sizeof(qno

11、de); if(!p) exit(OVERFLOW); p-data=e; p-next=NULL; q-rear-next=p; q-rear=p; return OK; /* 入队 */status dequeue(linkqueue *q,qelemtype *e) queueptr p;if(q-front=q-rear) return ERROR;p=q-front-next; *e=p-data;q-front-next=p-next; if(q-rear=p) q-rear=q-front; free(p);return OK; /*return OK; /*/四 : 调试分析函数调用比较多, 因而得仔细对待数值和地址的传递.由于魔王语言中B 中仍然包含着大写字母(tAdA).所以考虑设置flag.函数数组遍历. 进栈出栈. 入队出队中都要牵扯指针的移动, 所以要仔细考虑一循环的条件以及进栈元素的个数 . 五 : 用户手册1. 本程序运行环境为DOS/WINDOW操作系统S, 执行文件为 : 魔王语言解释.exe