魔王语言__数据结构试验报告.doc

魔王语言系统解释 需求分析 [问题描述] ? 有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没人能听的懂。但他的语言是可以逐步解释成人能懂得语言的，因为他的语言是由以下两种形式的规则由人的语言逐 步抽象上去的： ? ? 1）α-β1β2...βn （2）(θδ1δ2...δn)-θδnθδn-1...θδ1θ ? ? 在这两种形式中，从左到右均表示解释；从右到左表示抽象。试写一个魔王解释系统，把 ? ? 他的话解释成人能听懂得话。 ? [基本要求] ? ? 用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字 ? ? 母表示人的语言词汇；希腊字母（a,b1,s,y1等）表示可以用大写或小写字母代换的变量。 ? ? 魔王语言可含人的词汇。 ? ? （1）B-tAdA ? ? ? (2) ? A-sae ? [测试数据] ? ? B（einxgz）B ? ? 解释成 ? ? tsaedsaeezegexeneietsaedsae ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一个鹅地上一个鹅 ? ? 鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅。” ? ? t d s a e z G x n i ? ? 天 地 上 一个 鹅 追 ? 赶 下 蛋 恨 ? [实现提示] ? ? 将魔王的语言自右至左进栈，总是处理栈顶。若是开括号，则逐一出栈，将字母顺序入队 ? ? 列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者 ? ? 思考如何处理，应首先实现栈和队列的基本运算 概要设计 为实现上述程序功能，应以栈和队列来表示。 设定栈的抽象数据类型定义为： ADT Stack｛ 数据对象：D=｛ai | ai∈CharSet，I=1，2，......，n,n≥0｝ 数据关系：R1=｛ ai-1，ai |ai-1，ai∈D,I=1，2，......，n｝ 基本操作： ListInitiate (S) 操作结果：构造一个空栈S。 StackEmpty（S） 初始条件：栈S已经存在。 操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。 Push（S,e） 初始条件：栈S已经存在。 操作结果：在栈S的栈顶插入新的栈顶元素e。 Pop（S,e） 初始条件：栈S已经存在。 操作结果：删除S的栈顶元素，并以e返回其值。 } ADT Stack 2. 设定队列的抽象数据类型定义为： ADTQueue｛ 数据对象：D=｛ai | ai∈ElemSet，I=1，2，......，n,n≥0｝ 数据关系：R1=｛ ai-1，ai |ai-1，ai∈D,I=1，2，......，n｝ 基本操作： ListInitiate (Q) 操作结果：构造一个空队列Q。 StackEmpty（Q） 初始条件：队列Q已经存在。 操作结果：若队列Q为空栈，则返回TRUE，否则返回FALSE。 EnQueue（Q,e） 初始条件：队列Q已经存在。 操作结果：插入元素e为Q的新的队尾元素。 DeQueue（Q,e） 初始条件：队列Q已经存在。 操作结果：删除Q的对头元素，并以e返回其值。 } ADT Queue 程序包含四个模块： 主程序模块： Void main() { 初始化； For（） { 接受处理命令； } 接受处理； } 栈模块——实现栈的抽象数据类型； 队列模块——实现队列的抽象数据类型。 魔王语言解释模块——定义线性表的结点结构。 各模块的之间的调用关系如下： 主程序模块 魔王语言解释模块 ? ? 栈模块 队列模块 { char* base; char* top; int stacksize; }; 2. 队列类型 struct Stack { char* base; char* top; int stacksize; }; struct LinkQueue { struct Queue* front; struct Queue* rear; }; 3.栈的基本操作 //构