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

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

《魔王语言--数据结构试验报告.doc》由会员分享，可在线阅读，更多相关《魔王语言--数据结构试验报告.doc（15页珍藏版）》请在冰点文库上搜索。

魔王语言系统解释

一、需求分析

[问题描述] 

有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没人能听的懂。

但他的语言是可以逐步解释成人能懂得语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：

（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                  

 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一个鹅地上一个鹅 

 鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅。

” 

 tdsaezGxni 

 天地上一个鹅追 赶下蛋恨 

[实现提示] 

 将魔王的语言自右至左进栈，总是处理栈顶。

若是开括号，则逐一出栈，将字母顺序入队 

 列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。

其他情形较简单，请读者 

 思考如何处理，应首先实现栈和队列的基本运算

二、概要设计

为实现上述程序功能，应以栈和队列来表示。

1.设定栈的抽象数据类型定义为：

ADTStack｛

数据对象：

D=｛ai|ai∈CharSet，I=1，2，......，n,n≥0｝

数据关系：

R1=｛|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返回其值。

}ADTStack

2.设定队列的抽象数据类型定义为：

ADTQueue｛

数据对象：

D=｛ai|ai∈ElemSet，I=1，2，......，n,n≥0｝

数据关系：

R1=｛|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返回其值。

}ADTQueue

2.程序包含四个模块：

1）主程序模块：

Voidmain（）

{

初始化；

For（）

{

接受处理命令；

}

接受处理；

}

2）栈模块——实现栈的抽象数据类型；

3）队列模块——实现队列的抽象数据类型。

4）魔王语言解释模块——定义线性表的结点结构。

各模块的之间的调用关系如下：

主程序模块

魔王语言解释模块

  栈模块

队列模块

三、详细设计

1.栈类型

structStack

{

char*base;

char*top;

intstacksize;

};

2.队列类型

structStack

{

char*base;

char*top;

intstacksize;

};

structLinkQueue

{

structQueue*front;

structQueue*rear;

};

3.栈的基本操作

//构造栈

voidInitStack（structStack&s）

{

s.base=（char*）malloc（STACK_INIT_SIZE*sizeof（char））;

s.top=s.base;

s.stacksize=STACK_INIT_SIZE;

}

//往栈中压入元素

voidPush（structStack&s,chare）

{

if（s.top-s.base>=STACK_INIT_SIZE）

{

s.base=（char*）realloc（s.base,（s.stacksize+STACK_INCREMENT）*sizeof（char））;

s.top=s.base+s.stacksize;

s.stacksize+=STACK_INCREMENT;

}

*（s.top）=e;

s.top++;

}

//取出栈中的元素

voidPop（structStack&s,char&e）

{

e=*--s.top;

}

//判断栈是否为空

intStackEmpty（structStacks）

{

if（s.top==s.base）return1;

elsereturn0;

}

//清空栈

voidClearStack（structStack&s）

{

s.top=s.base;

}

4队列的基本操作

//构造队列

voidInitQueue（structLinkQueue&q）

{

q.front=q.rear=（structQueue*）malloc（sizeof（structQueue））;

q.front->next=NULL;

}

//元素入队

voidEnQueue（structLinkQueue&q,chare）

{

structQueue*p;

p=（structQueue*）malloc（sizeof（structQueue））;

p->data=e;

p->next=NULL;

q.rear->next=p;

q.rear=p;

}

//元素出队

voidDeQueue（structLinkQueue&q,char&e）{

structQueue*p;

p=q.front->next;

e=p->data;

q.front->next=p->next;

if（q.rear==p）q.rear=q.front;

free（p）;

}

//判断队列是否为空，如果对为空，返回，否则返回

intQueueEmpty（structLinkQueueq）{

if（q.front==q.rear）return1;

elsereturn0;

}

//把字符数组从右至左压入栈中

voidInStack（char*ch,structStack&s）

{

inti,L=0;

while（ch[L]!

='\0'）L++;

for（i=L-1;i>=0;i--）Push（s,ch[i]）;

}

4.主函数和其他函数的算法（含注释）：

#include

#include

#defineSTACK_INIT_SIZE100

#defineSTACK_INCREMENT10

intmain（）

{

printf（"**************************************************************\n"）;

printf（"******************************\n"）;

printf（"**魔王语言解释系统**\n"）;

printf（"******************************\n"）;

printf（"*班级：

物联网工程1001班*\n"）;

printf（"*姓名:

*********\n"）;

printf（"*学号:

0909100818*\n"）;

printf（"**************************************************************\n\n"）;

intxunhuan=1;

printf（"请输入你想要解释的魔王语言：

\n"）;

while（xunhuan==1）//一个总循环控制整个程序的重复进行

{

charA[]="sae";//大写字母作为字符数组名存放小写字母

charB[]="tsaedsae";

charflag='0';//flag用来标记处理括号

chare1,key,e2,e;

intmark=1;//标记输入的魔王语言是否在允许的范围之内

intf=1;//判断括号是否匹配

charMoWang[100]="\0";//定义一个魔王变量，存放待解释的语言字符

structStackS;//作为栈存储元素，为后续操作和输出做准备

structStacktemp;//用来处理括号外的元素

InitStack（S）;

InitStack（temp）;

structLinkQueueQ;

InitQueue（Q）;

gets（MoWang）;//变量MoWang存储输入的语言

InStack（MoWang,S）;//把要解释的魔王语言压入栈中

while（!

StackEmpty（S））//把魔王语言进行出栈，不符合语言的进行提示

{

Pop（S,e1）;

if（e1=='（'）

{

if（StackEmpty（S））

{

printf（"魔王语言错误!

\n"）;

mark=0;f=0;

break;

}

while（!

StackEmpty（S））

{

Pop（S,e1）;

if（e1=='）'）

{

f=1;

break;

}

elseif（!

（e1>='a'&&e1<='z'）&&!

（e1>='A'&&e1<='Z'））

{

printf（"魔王语言错误！

\n"）;

mark=0;

break;

}

}

if（mark==0）

break;

if（f!

=1）

{

printf（"魔王语言错误！

\n"）;

break;

}

}

elseif（e1=='）'）

{

printf（"魔王语言错误！

\n"）;

mark=0;

break;

}

elseif（!

（e1>='a'&&e1<='z'）&&!

（e1>='A'&&e1<='Z'））

{

printf（"魔王语言错误！

\n"）;

mark=0;

break;

}

}

if（mark==1&&f==1）//对符合语言规则的魔王语言进行规则处理

{

ClearStack（S）;

InStack（MoWang,S）;//把魔王语言从右至左压栈存放

while（!

StackEmpty（S））//栈不空时，用栈temp进行存储不带括号内元素的元素

{

Pop（S,e1）;

if（e1=='B'||e1=='A'）Push（temp,e1）;

elseif（e1=='（'）//用队存储括号中的元素

{

Push（temp,flag）;//有括号的话就用flag标记

Pop（S,e1）;

while（e1!

='）'）//把括号中的元素存入队列中

{

EnQueue（Q,e1）;

Pop（S,e1）;

}

if（!

QueueEmpty（Q））DeQueue（Q,key）;//将队头的元素赋值给key

}

elsePush（temp,e1）;

}

while（!

StackEmpty（temp））//将魔王说的语言规则地压入栈s中

{

Pop（temp,e1）;

if（e1!

=flag）Push（S,e1）;//把括号外的元素压入中

else{

while（!

QueueEmpty（Q））//处理括号中的元素进栈

{

DeQueue（Q,e2）;

Push（S,key）;

Push（S,e2）;

}

Push（S,key）;//最后还要压一个key

}

}

printf（"解释后的语言为：

\n"）;

while（!

StackEmpty（S））//依次出栈输出处理后的元素

{

Pop（S,e）;

EnQueue（Q,e）;//元素进队是为了输出对应汉字

if（e=='B'）printf（"%s",B）;

elseif（e=='A'）printf（"%s",A）;

elseprintf（"%c",e）;

}

printf（"\n"）;

while（!

QueueEmpty（Q））//翻译成对应的汉字

{

DeQueue（Q,e）;

switch（e）

{

case't':

printf（"天"）;break;

case'd':

printf（"地"）;break;

case's':

printf（"上"）;break;

case'a':

printf（"一只"）;break;

case'e':

printf（"鹅"）;break;

case'z':

printf（"追"）;break;

case'g':

printf（"赶"）;break;

case'x':

printf（"下"）;break;

case'n':

printf（"蛋"）;break;

case'h':

printf（"恨"）;break;

case'B':

printf（"天上一只鹅地上一只鹅"）;break;

case'A':

printf（"上一只鹅"）;break;

default:

printf（"*"）;break;

}

}

printf（"\n"）;

}

printf（"再次输入魔王语言（按数字键：

0----退出）\n"）;

scanf（"%d",&xunhuan）;

}

return0;

}

四、调试分析

1.函数调用。

函数调用是语言中一块十分重要部分，它可以把一个程序分成若干部分，然后进行配置，所以这块内容一定要学好。

2.栈和队列问题比较简单。

3.由于考虑不周，如果同样的字母出现时，规则会要求重复输入，最终以最后一个为准，这是一个失误，后来改正程序，过滤掉重复字母。

五、测试分析

1、当输入A时系统显示：

2、当输入B（ehnxgz）B是系统显示：

六、用户手册

1、本程序运行在DOS命令下

2、进入程序后即显示用户界面：

3、注意输入后即可得到相应的结果。

七、附录（代码源程序及注释）

#include

#include

#defineSTACK_INIT_SIZE100

#defineSTACK_INCREMENT10

structStack//定义栈

{

char*base;

char*top;

intstacksize;

};

voidInitStack（structStack&s）//构造栈

{

s.base=（char*）malloc（STACK_INIT_SIZE*sizeof（char））;

s.top=s.base;

s.stacksize=STACK_INIT_SIZE;

}

voidPush（structStack&s,chare）//往栈中压入元素

{

if（s.top-s.base>=STACK_