魔王语言解释（数据结构课程设计）_精品.doc

魔王语言解释 1、绪论 1.1 背景。而“魔王语言”就是一个简单的文件加密。“魔王语言”就是有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是有规则的，可以通过相应的规则来解释。 1.2研究目的 通过这次设计，要求在数据结构逻辑特性和物理分析、数据结构的选择和应用、算法的设计及其实现等方面，加深对基础知识的理解。同时，在程序设计方法以及上机造作等基本技能方面受到严格的训练。 2、需求分析 2.1 题目 魔王语言解释。2.2 基本要求 魔王的话没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，有着下面的基本要求： 用下述两条具体规则和述规则形式实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。α 转换为 β1β2…βm （θδ1δ2…δn） 转换为 θδnθδn－1… θδ1θ 在这两种形式重，从左到右均表示解释。试写一个魔王语言的解释兄，把他的话解释成人能听得懂的话。因此，我们编写了一个有趣的魔王语言解释程序来巩固和加强对栈和队列的理解。 ⑴ A 转换为 hdwhz，B 转化为 hasff，C 转化为 hwhll，D 转化为 hkhbf，E 转化为 hkwsx，F 转化为 hxwsb。 ⑵ h 转化为 “花”，d 转化为 “蝴蝶”，w 转化为 “为”，z 转化为 “醉”，s 转化为 “随”，fe 转化为 “风”，f 转化为 “飞”，k 转化为 “开”，ku 转化为 “哭”，b 转化为 “悲”，x 转化为 “谢”，l 转化为 “落泪”，ba 转化为 “瓣”。⑶ A 转化为 “蝴蝶为花瓣”，B 转化为“花却随风飞”，C 转化为“花舞花落泪”，D 转化为“花哭花瓣飞”，E 转化为“花开为谁谢”，F 转化为“花谢为谁悲”。 2.数据测试 B（hdwz）B解释成 hasffhzhwhdhhasff 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“花却随风飞花醉花为花蝴蝶花花却随风飞”。 h z w d s f 花 醉 为 随 飞 2.实现分析 ⑴ 以一维数组demon[ i ]表示魔王语言． ⑵ 魔王语言由用户输入,初始保存在demon[ i ]中． ⑶ 魔王语言与人类语言对应关系固化在程序中． 2.实现过程 ⑴ 初始，魔王语言接收后存放在demon[ i ]中． ⑵ 遍历数组，将数组中括号内的元素入栈，同时插入相应首字母； ⑶ 再次遍历数组，将数组元素依次入队。（小写字母直接入队；大写字母翻译成相应字符入队；遇到括号，将栈中保存的元素依次出栈入队）在翻译过程中，如果依旧包含大写字母，则置flag为1，否则为0。 ⑷ 将队列中元素赋值给demon[ i ]。如果此时flag=1，则再次重复C过程。直至所有元素为人类语言。 ⑸ 输出demon[ i ]。此时数组中元素为对应的人类语言。注：如果程序中没有相应的对应关系，则翻译成“???”。 3、概要设计 3.1 数据流程图 图1 数据流程图 3.2设定栈的抽象数据类型定义： ADT stack{ 数据对象：D={ai |ai∈CharSet,i=1,2,…,n,n=0} 数据关系：R1={ai-1,ai|ai-1,ai∈D，i=2，…，n} 基本操作： Initstack(s) 操作结果：构造一个空栈s. Push(s,e) 初始条件：栈s已存在. 操作结果：在栈s的栈顶插入新的栈顶元素e. Pop(s,e) 初始条件：栈s已存在. 操作结果：删除s的栈顶元素，并以e返回其值. }ADT stack 3.3设定队列的抽象数据类型： ADT queue{ 数据对象：D={ai |ai∈Elemset,i=1,2,…,n,n=0} 数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,…,n} 基本操作： Initqueue(q) 操作结果：构造一个空队列q. Enqueue(q,e) 初始条件：队列q已存在. 操作结果：插入元素e为q的新队尾元素. Dequeue(q,e) 初始条件：q为非空队列. 操作结果：删除q的队头元素，并用e返回其值. }ADT queue 3.4本程序包含四个模块： ⑴主函数模块，其中主函数为： Status main() { 初始化栈； 初始化队列； 接收魔王语言输入到数组demon[i]； 遍历数组将括号中元素进栈； While(数组demon[i]中元素有大写字母) { 翻译排序处理后入队列； 将队列元素保存在数组demon[i]； } 输出人类语言（数组demon[i]）； } ⑵括号内元