山东理工大学计算机学院
课
程
设
计
（数据结构）
班姓学
级名号
计科0904李少朋0911051142张艳华
指导教师
二○一一年一月二十日
f课程设计任务书及成绩评定
课题名称魔王语言
题目的目的和要求：Ⅰ、题目的目的和要求
1、设计目的
巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。
2、设计题目要求：设计题目要求
【问题描述】有一个魔王总是使用自己的一种非常精炼而抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是有以下两种形式的规则由人的语言逐步抽象上去的：（1）αβ1β2…βm（2）（θδ1δ2…δ
）θδ
θδ
1…θδ1θ在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听懂的话。【基本要求】用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。（1）BtAdA（2）Asae【测试数据】Beh
xgzB解释成tsaedsaeezegexe
ehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。
T
D
s
a
e
z
g
x


h
f天
地
上
一只
鹅
追
赶
下
蛋
恨
【实现提示】将魔王语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考应如何处理。首先实现栈和队列的基本操作。【选作内容】（1）由于问题的特殊性，可以实现栈和队列的顺序存储空间共享。（2）代换变量的数目不限，则在程序开始运行时首先读入一组第一种形式的规则，而不是把规则固定在程序中（第二种形式的规则只能固定在程序中）。
Ⅱ、设计进度及完成情况日期内
创建相关数据结构录入源程序。调试程序并记录调试中的问题，初步完成课程设计报告。上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师34个问题。考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。
容
11011111r