数据结构课程设计_魔王语言解释系统

1、石家庄经济学院 本科生课程设计报告书题 目 魔王语言解释系统 姓名 XXXXXX 学号 学 院 信息工程学院 专业 电气信息类 指导教师 XXXXXX 完成日期： 魔王语言解释系统1 需求分析问题描述 有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的： （1） > 12m （2）（12n)>nn1 1 在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。 基本要求 用下述两条具体规则和上述规则形式（2）实现。设大写字母

2、表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。 （1）B > tAdA （2）A > sae 测试数据 B(ehnxgz)B解释成tsaedsaeezegexenehetsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。 tdsaezgxnh天地上一只鹅追赶下蛋恨过程分析(1)以一维数组demon i 表示魔王语言。 (2)魔王语言由用户输入,初始保存在demon i 中。 (3)魔王语言与人类语言对应关系固化在程序中。

3、(4)实现过程： A：初始将魔王语言接收后存放在demon i 中。 B：初次遍历数组，将数组中括号内的元素入栈，同时插入相应的首字母； C：再次遍历数组，将数组元素依次入队。（小写字母直接入队；大写字母经翻译成相应字符后入队；遇到括号，将栈中保存的元素依次出栈入队）在翻译过程中，如果依旧包含大写字母或括号，则置flag为1，否则为0。 D：将队列中元素赋值给demon i 。如果此时flag=1，则再次重复C过程。直至所有元素为人类语言。 E：输出demon i ，此时数组中元素为对应的人类语言。注：如果程序中没有相应的对应关系，则翻译成“*”。F:将输出数据存盘。2 概要设计为实现上述程序

4、功能，应以栈和队列来表示。 1）.设定栈的抽象数据类型定义为：ADT Stack 数据对象：D=ai|aiCharSet,i=1，2，,n,n0 数据关系：R1=<ai-1,ai>|ai-1,aiD,i=1,2,n基本操作：InitStack(&S)操作结果：构造一个空栈S DestroyStack（&S）初始条件：栈S已存在。操作结果：栈S被销毁。 ClearStack（&S）初始条件：栈S已存在。操作结果：将S清为空栈。 StackEmpty（S）初始条件：栈S已存在。操作结果：若栈S为空，则返回TURE，否则FLASE。 StackLength（S）初

5、始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。 GetTop（S，&e）初始条件：栈S已存在。操作结果：用e 返回S的栈顶元素。 Push（&S，&e）初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop（&S,&e）初始条件：栈S已存在。操作结果：删除S的栈顶元素，并用e的返回其值。 StackTraverse（S,Visit（）初始条件：栈S已存在且非空。操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit（）。一旦visit（）失败，则操作失效。ADT Stack2）. 设定队列的抽象数据类型定义为：ADT Qu

6、eue 数据对象：D=ai|aiElemSet,i=1，2，,n,n0 数据关系：R1=<ai-1,ai>|ai-1,aiD,i=1,2,n基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。 DestroyQueue（&Q）初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。 ClearQueue（&Q）初始条件：队列Q已存在。操作结果：将Q清为空队列。 QueueEmpty（Q）初始条件：队列Q已存在。操作结果：若队列Q为空，则返回TURE，否则FLASE。 QueueLength（Q）初始条件：队列Q已存在。操作结果：返回Q的元素个数

7、，即队列的长度。 GetHead（Q，&e）初始条件：Q为非空队列。操作结果：用e 返回Q的对头元素。 EnQueue（&Q，&e）初始条件：队列Q已存在。操作结果：插入元素e为Q的新队尾元素。DeQueue（&Q,&e）初始条件：Q为非空队列。操作结果：删除Q的对头元素，并用e的返回其值。 QueueTraverse（Q,Visit（）初始条件：Q已存在且非空。操作结果：从对头到栈队尾依次对Q的每个数据元素调用函数visit（）。一旦visit（）失败，则操作失效。ADT Queue3）.各模块之间调用关系: 主函数模块 括号内元素入栈处理模块; 排序

8、入队模块 翻译大写处理模块; 图2.1 3 详细设计流程图 图 3.1本程序包含四个模块：A主函数模块。其中主函数为：Status main()初始化栈；初始化队列; 接收魔王语言输入到数组demoni ; 遍历数组将括号中元素进栈; while(数组demoni 中元素有大写字母) 翻译排序处理后入队列; 将对列元素保存在数组demoni ; 输出人类语言(数组demon i); B.括号内元素入栈处理模块. tempstack(&temps) 将括号内元素入栈,依次插入首字符.。举例：(abcd)>adacaba.。C.排序入队列模块. sort(&s,&q)

9、 遍历数组; 遇到小写字母,直接入队列; 遇到大写字母,翻译大写后入队列; 遇到括号,将栈中保存的元素依次出栈入队列; D.翻译大写处理模块. spenqueue(&*q,key) switch(key) 找到各个大写字母对应的字符串. 没有相应的则解释为* 4 编码调试1. 函数调用比较多,因而得仔细对待数值和地址的传递. 2. 由于魔王语言中B中仍然包含着大写字母(tAdA).所以考虑设置flag. 3. 函数数组遍历.进栈出栈.入队出队中都要牵扯指针的移动,所以要仔细考虑一循环的条件以及进栈元素的个数.5 设计体会1. 本次课程设计各阶段（需求分析、概要设计、详细设计、编码调试等

10、）所遇到的问题，问题的现象描述，产生的原因，解决方案（措施），解决的结果（1） 在需求分析阶段：A错误：再次遍历时时，只有当数组中包含大写字母时flag=1，且flag=1时只重复D过程改正：再次遍历时，应为当数组中含有大写字母或者是括号时flag=1，因此flag=1时应重复C、D两个过程，而不应只重复D过程 即：在初次遍历后入栈元素中仍有可能包含括号，这就需要多次对数组内元素进行初次遍历的过程，所以重复过程应将C包含在内。 B错误：E过程中没有考虑到无相应对应关系的情况。 改正：添加“如果程序中没有相应的对应关系，则翻译成“*”。”（2） 在详细设计阶段 A错误：下面模块语言出现逻辑错误，

11、无法正确执行 改正：（3） 在编码调试阶段A 错误：在调试阶段弹出问题，不能完成程序的输出 改正：指针发生冲突，下面的函数出现错误，红色部分为修改内容status sort(sqstack *s,linkqueue *q) qnode b1; qnode *b=&b1; int flag=0;/*大写字母、括号监视哨置零*/ . . .B 错误：将上述问题修改后，可实现程序的编译和运行但运行结果仍出现问题，不能对大写字母B进行二次翻译。改正：原错误代码：status reverse (sqstack *s,linkqueue *q) int a; int i,flag=0; for(i

12、=0;demoni!='#'i+)/*遍历数组*/ a=demoni; if('A'<=a&&a<='Z')|a='(') /*翻译后的数组若仍然含有大写字母或是括号则将flag赋值为*/ flag=1; else flag=0; return flag; 修改后代码：status reverse (sqstack *s,linkqueue *q) int a; int i,flag; for(i=0;demoni!='#'i+)/*遍历数组*/ a=demoni; if('A&

13、#39;<=a&&a<='Z')|a='(')/*翻译后的数组若仍然含有大写字母或是括号则将flag赋值为*/ flag=1; return 1; else flag=0; 6 致谢在这次课程设计的撰写过程中，我得到了许多人的帮助。首先我要感谢我的老师在课程设计上给予我的指导、提供给我的支持和帮助，这是我能顺利完成这次报告的主要原因，更重要的是老师帮我解决了许多技术上的难题，让我能把系统做得更加完善。在此期间，我不仅学到了许多新的知识，而且也开阔了视野，提高了自己的设计能力。其次，我要感谢帮助过我的同学，他们也为我解决了不少我不太明白的设计商的