《魔王语言数据结构实验报告》由会员分享，可在线阅读，更多相关《魔王语言数据结构实验报告（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告2.2 魔王语言解释 问题描述 有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言， 因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1） 12,m （2）（ 12,n) n n1, 1在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。 基本要求 用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。（1）B tAdA （2）A sae 测试数据
2、 B(ehnxgz)B 解释成 tsaedsaeezegexenehetsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。 t d s a e z g x n h 天 地 上 一只 鹅 追 赶 下 蛋 恨一：需求分析(1) 以一维数组demon i 表示魔王语言(2) 魔王语言由用户输入, 初始保存在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 数据对象： D ai|aiCharSet,i1,2, ,n,n=0 数据关系： R1|ai-1,aiD,i 2, ,n 基本操
4、作：initstack (s) 操作结果 : 构造一个空栈s. push (s,e) 初始条件 : 栈 s 已存在 . 操作结果 : 在栈 s 的栈顶插入新的栈顶元素e. pop( s, e) 初始条件 : 栈 s 已存在 . 操作结果 : 删除 s 的栈顶元素 , 并以 e 返回其值. ADT stack 2: 设定队列的抽象数据类型: ADT queue 数据对象： D ai|aiElemset,i1,2, ,n,n=0 数据关系： R1|ai-1,aiD,i 2, ,n 基本操作：initqueue( 初始化队列 ; 接收魔王语言输入到数组demoni ; 遍历数组将括号中元素进栈 ;
5、while(数组 demoni 中元素有大写字母) 翻译排序处理后入队列; 将对列元素保存在数组demoni ; 输出人类语言 (数组 demon i); 2) 括号内元素入栈处理模块. tempstack( 遇到小写字母 , 直接入队列 ; 遇到大写字母 , 翻译大写后入队列; 遇到括号 , 将栈中保存的元素依次出栈入队列; 4) 翻译大写处理模块. spenqueue( 排序入队模块 翻译大写处理模块; 三: 详细设计1. 定义全局变量#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define NULL 0 #de
6、fine OVERFLOW -2 #define MAXSIZE 100 #define stack_init_size 100 #define stackincrement 10 typedef char selemtype; typedef char qelemtype; typedef char elemtype; typedef int status; char e; char demonMAXSIZE; 2. 栈类型及其基本操作typedef struct selemtype *base; selemtype *top; int stacksize; sqstack; status
7、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; return OK; /*创建栈 */ status push (sqstack *s,selemtype e) if(s-top-s-base=s-stacksize) s-base=(elemtype *) realloc(s-base,(s-stacksize+stackincr
8、ement)*sizeof(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; /*出栈 */ 3. 队列类型及其基本操作typedef struct qnode qelemtype data; struct qn
9、ode *next; qnode,*queueptr; typedef struct queueptr front; queueptr rear; linkqueue; status initqueue(linkqueue *q) q-front=q-rear=(queueptr)malloc(sizeof(qnode); if(!q-front) exit(OVERFLOW); q-front-next=NULL; return OK; /*创建队列 */ status enqueue(linkqueue *q,qelemtype e) queueptr p; p=(queueptr)mal
10、loc(sizeof(qnode); 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; /*出队 */
11、 四: 调试分析1. 函数调用比较多, 因而得仔细对待数值和地址的传递. 2. 由于魔王语言中 B 中仍然包含着大写字母(tAdA).所以考虑设置flag. 3. 函数数组遍历 . 进栈出栈 . 入队出队中都要牵扯指针的移动 , 所以要仔细考虑一循环的条件以及进栈元素的个数. 五: 用户手册1. 本程序运行环境为DOS/WINDOWS操作系统 , 执行文件为 : 魔王语言解释 .exe 。 2. 进入程序即显示提示信息: WELCOME! * Please Input The Demons Words: !: Less Than 30 Letters: ) !: Please Stopped By #: ) * The Demons Words: 等待用户输入 . 用户输入字符以 # 回车结束 . * The Human Words: （翻译后的语言）* THANK YOU! 源程序（省略）测试结果
