当前位置：文档库 › 数据结构课程设计魔王语言

数据结构课程设计魔王语言

山东理工大学计算机学院课程设计

（数据结构）

班级

姓名

学号

指导教师

二○○七年七月二十日

课程设计任务书及成绩评定

课题名称魔王语言解释

Ⅰ、题目的目的和要求：

设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题。通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。

通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和

严格的训练。

Ⅱ、设计进度及完成情况

日期内容

7.2-7.4 熟悉设计任务，查阅有关文献资料，确定所采用的数据结构，初步制定解决问题的方法，完成课程设计说明书内容1-3部分。

7.5~7.10 选择合适的存储结构，明确解决问题的算法，上机编写并调试源程序。

7.11~7.1

2 整体调试程序并记录调试中的问题，完成课程设计说明书第4-7部分。

7.13 演示设计成果，考核成绩。整理课程设计说明书，上午11时，由学习委员交课程设计说明书(计算机科学系9#213或直接交给指导教师)

Ⅲ、主要参考文献及资料

[1]严蔚敏、吴伟民主编，《数据结构》（C语言版），清华大学出版社，2002。

[2] 殷人昆等著，《数据结构》（C++版），清华大学出版社，2001。

[3] 金远平著，《数据结构》（C++描述），清华大学出版社，2005。

[4]许卓群等著，《数据结构与算法》，高等教育出版社，2004。

[5] Frank M.Carrano等著, 《数据结构与Ｃ++高级教程》，清华大学出版社，2004。

[6]严蔚敏、吴伟民著，《数据结构习题集》（C语言版），清华大学出版社。Ⅳ、成绩评定：

设计成绩：（教师填写）

指导老师：（签字）

二○○七年七月二十日

第一章概述 (1)

第二章系统分析 (2)

第三章系统设计 (3)

第四章程序设计流程图 (7)

第五章源程序清单 (9)

第六章调试过程中的问题及系统测试情况 (13)

第七章结束语 (14)

第一章概述

1.1本课程设计意义

课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程进行更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。

数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

第二章系统分析

1.1主要功能：

魔王总是使用自己的一种非常精练而抽象的语言讲话,没人能听懂,但他的语言是可逐步解释成人能听懂的语言,因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的:

-----------------------------------------------------------

1)a---> (B1)(B2)....(Bm)

2)[(op1)(p2)...(pn)]---->[o(pn)][o(p(n-1))].....[o(p1)o]

-----------------------------------------------------------

在这两种形式中,从左到右均表示解释.试写一个魔王语言的解释系统,把他的话解释成人能听得懂的话.

1.2基本要求:

用下述两条具体规则和上述规则形式(2)实现.设大写字母表示魔王语言的词汇;小写字母表示人的语言的词汇;希腊字母表示可以用大写字母或小写字母代换的变量.魔王语言可含人的词汇.

1) B --> tAdA

2) A --> sae

第三章系统设计

功能模块层次结构图：

数据结构的名称及描述: （1）栈： ADT Stack {

数据对象：D={a[i]|a[i] ∈ Elemset,i=1,2,…,n, n>=0} 数据关系：R1={|a[i-1],a[i] ∈ D,i=2,…,n} 约定a[n]端为栈顶，a[1]端为栈底。基本操作：

Initstack(&s) 操作结果：构造一个空栈s 。 Destroystack(&s) 初始条件：栈s 已存在。操作结果：栈s 被取消。 Clearstack(&s) 初始条件：栈s 已存在。操作结果：将s 清为空栈。

调用Gzcin （）输入规则

调用Mycin （）输入语

言

调用Change （）进行翻

译

在屏幕输出输入一组规则

输入魔王语言

根据用POP （）

出栈的字符进行判断： A ：大写字符

B ：左括号

按规则进行翻译调用Link （）把括号中的字符全部进队列，按规则翻译

Stackempty(s)

初始条件：栈s已存在。

操作结果：若栈s为空栈，则返回TRUE，否则FALSE。

Stacklength(s)

初始条件：栈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 stack

栈的顺序存储表示：

#define STACK_INIT_SIZE 100; //存储空间初始分配量

#define STACKINCREMENT 10; //存储空间分配增量

Typedef struct{

SElemtype *base; //在栈构造之前和销毁之后，base的值为NULL

SElemtype *top; //栈顶指针

Int stacksize; //当前已分配的空间，以元素为单位

}Sqstack;

（2）队列：

ADT queue{

数据对象:D={a[i]|a[i]∈Elemset,i=1,2,…,n, n>=0}

数据关系：R1={|a[i-1],a[i]∈D,i=2,…,n}

约定其中a[1]端为队列头，a[n]端为队列尾。

基本操作：

Initqueue(&q)

操作结果：构造一个空队列q。

Destroyqueue(&q)

初始条件：队列q已存在。

操作结果：队列q被销毁，不再存在。

Clearqueue(&q)

初始条件：队列q已存在。

操作结果：将q清空为空队列。

Queueempty(q)

初始条件：队列q已存在。

操作结果:若队列q为空队列，则返回TRUE,否则FALSE。

Queuelength(q)

初始条件：队列q已存在。

操作结果: 返回q的元素个数，即队列的长度。

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 Queue

队列的链式存储结构：

Typedef struct qnode{

Qelemtype data;

Struct qnode *next;

}qnode,*queueptr;

Typedef struct{

Queueptr front; //对头指针 Queueptr rear; //队尾指针}linkqueue;

第四章程序设计流程图

（1）程序开始先由用户输入一种规则使用cin和cout函数。

（2）接着程序再读入想要翻译的魔王语言。

（3）程序对输入的规则进行翻译，翻译成人类语言。

（4）对魔王语言进行翻译，首先用POP（）函数把魔王语言每一个字符读出。

（5）再对字符进行筛选，符合输入规则的立即翻译。保存至transl中。

（6）对于括号中的字符，即人类语言。先把括号中的字符全部出栈，保存至link中。（7）按规则把队列中的字符串进行翻译，保存至transl中。

（8）依次执行，直到翻译完所有字符串。

程序设计流程图如下：

第五章源程序清单

程序清单如下：

魔王.cpp

/*-----------------------定义头文件---------------------------*/

#include

/*-----------------------定义全局变量-------------------------*/

int top=0;

int find=0;

//top=0;

char transl[200];

char leag[200];

char link[100];

int rear=1;

//rear=1;

/*-------------------MAIN()主函数---------------------------*/

int main()

{

char pop(); //定义出栈函数

char ml[2][200]; //定义两个规则，把它们存放到ml中

cout<

cout<<" ** ＝＝＝魔王语言程序设计＝＝＝

** "<

cout<<"

******************************************************* "<

cout<<"

******************************************************* "<

cout<<" ** 本程序可以翻译魔王语言且按以下两条形式规则由人

** "<

cout<<" **

** "<

cout<<" **的语言逐步抽象上去： ** "<

cout<<" **

** "<

cout<<" **①α->β1β2β3β4...

** "<

cout<<" **

** "<

cout<<" **②(θβ1β2β3)->θβ3θβ2θβ1θ

** "<

cout<<" **

** "<

cout<<" ** 下面只输入2个第一种形式的规则，且后输入的可以嵌

** "<

cout<<" **

** "<

cout<<" **套已输入的规则。 ** "<

cout<<" **

** "<

cout<<"

******************************************************* "<

cout<<"

******************************************************* "<

cout<<"******************************************************************

**************";

//本程序可以翻译魔王语言且按以下两条形式规则由人的语言逐步抽象上去：

// ①α->β1β2β3β4...

// ②(θβ1β2β3)θβ3θβ2θβ1θ

//下面只输入2个第一种形式的规则，且后输入的可以嵌套已输入的规则

/*开始输入规则A和B，A比B先输入，再输入B，这样B就可以嵌套A*/

cout<<"以下请开始翻译："<

cout<<"请先输入一组形式规则："<

cout<<"A->";

cin>>ml[0];

cout<<"B->";

cin>>ml[1];

cout<

/*输入魔王语言，其规则为大写为魔王语言，只限定A和B（暂时），小写为人类语言，

输入时用括号括起来*/

cout<<"请输入要解释的魔王语言：";

cin>>leag;

char temp[100]; //定义一个缓冲区，存放B的翻译

int sizeA=0; //定义A的长度

sizeA=strlen(ml[0]);

int wh=0; //定义缓冲区中的位置变量

for(int i=0;ml[1][i]!='\0';i++) //开始翻译B

{

if(ml[1][i]=='A') //如果嵌套了A

{

//cout<<"here is doing!!";

for(int n=0;n

{

temp[wh]=ml[0][n]; //翻译至缓存区}

}

else

{

temp[wh]=ml[1][i]; //如果不是A则原样写入

wh++;

}

temp[wh]=0; //为缓存区加上结束符

strcpy(ml[1],temp); //把缓存区中的串给ml[1] int sizeB=0; //定义B的长度

sizeB=strlen(ml[1]);

int length;

length=strlen(leag); //取得魔王语言的长度

int ch; //定义一个变量保存字符

int a;

int b;

/*-------开始翻译魔王语言，并把结果存至transl中------------*/

for(int t=0;t

{

ch=pop();

switch(ch)

{

case 'A': //如果是A的话for(a=0;a

{

transl[find]=ml[0][a];

}

break;

case 'B': //如果是B的话for(b=0;b

{

transl[find]=ml[1][b];

}

break;

case '(': //但ch='('时，把括号中的小写字母保存至link中

ch=pop();

link[0]=ch; //先把第一个字符存入，后面的从link[1]开始

while(ch!=')')

{

ch=pop();

link[rear]=ch; //记得rear的初值为1

rear++;

}

//由于while循环的原因，在link队列中多加了一个右括号字符，且rear 指针向后多移了2个单位

//故使rear减2

rear=rear-2;

transl[find++]=link[0];

for(rear;rear!=0;rear--)

{

transl[find++]=link[rear];

transl[find++]=link[0];

}

//为了使后面的翻译可行话，得把rear还原为初值，即rear=1

rear=1;

break;

default:break;

}//switch结束

/*--------翻译魔鬼语言结束，结果已存至transl中------------*/ }//for结束

cout<<"经过翻译，魔王想表达的语言是：";

//输出得到的翻译语言

cout<

return 0;

}

char pop() //出栈函数的实现{

return leag[top++];

}

第六章调试过程中的问题及系统测试情况

输入输出：

*输入注意：先输入的规则可以被后输入的规则嵌套，后输入的可以嵌套先输入的，但是注意先输入的不可以嵌套后输入的。

输入魔王语言时，人类语言（小写字符）要用括号括起来，魔王字符（大写字符）只能是以上规则提到的字符。

输入例子：

A->yui回车

B->tuAsdA回车

魔王语言：BABA(fqwerjijilo)ABAB

输出结果：

翻译输出：

结果正确。

第七章结束语

经过几天和同学进行的程序设计合作，使我明白了做一件事情如果靠团结的力量是很容易完成的。

再次感谢指导我们的老师，给了我们莫大的帮忙，使我们的工作事半功倍。

本次任务完成情况良好，能够完好的解决题目所给的要求，达到了程序设计的输入、输出、有穷性、可行性、确定性的程序要求。

参考文献:

[1]严蔚敏、吴伟民主编，《数据结构》（C语言版），清华大学出版社，2002。

[2] 殷人昆等著，《数据结构》（C++版），清华大学出版社，2001。

[3] 金远平著，《数据结构》（C++描述），清华大学出版社，2005。

[4]许卓群等著，《数据结构与算法》，高等教育出版社，2004。

[5] Frank M.Carrano等著, 《数据结构与Ｃ++高级教程》，清华大学出版社，2004。

[6]严蔚敏、吴伟民著，《数据结构习题集》（C语言版），清华大学出版社。

魔王语言解释-大数据结构课程设计

实习2、魔王语言解释一、需求分析 1. 问题描述有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没人能听的懂，但他的语言是可以逐步解释成人能懂得语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）α->β1 β2 ... βn （2）(θδ1 δ2 ... δn) —>θδn θδn-1 ...θδ1 θ 在这两种形式中，从左到右均表示解释。试写一个魔王解释系统，把他的话解释成人能听懂得话。 2. 基本要求用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写或小写字母代换的变量。魔王语言可含人的词汇。（1）B—>tAdA （2）A—>sae 3. 测试数据 B（ehnxgz）B 解释成tsaedsaeezegexenehetsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一个鹅地上一个鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅”。 4. 实现提示将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考如何处理。应首先实现栈和队列的基本操作。二、概要设计 1、设定栈的抽象数据类型定义： ADT Stack { 数据对象：D= {a i| a i∈CharSet, i= 1,2,……n,. n≥0 } 数据关系：R1={ | a i-1,a i∈D, a i-1