魔王语言--数据结构试验报告Word格式文档下载.doc
《魔王语言--数据结构试验报告Word格式文档下载.doc》由会员分享，可在线阅读，更多相关《魔王语言--数据结构试验报告Word格式文档下载.doc（15页珍藏版）》请在冰点文库上搜索。
其他情形较简单，请读者
思考如何处理，应首先实现栈和队列的基本运算
二、概要设计
为实现上述程序功能，应以栈和队列来表示。
1.设定栈的抽象数据类型定义为：
ADTStack｛
数据对象：
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的栈顶插入新的栈顶元素e。
Pop（&
S,&
e）
删除S的栈顶元素，并以e返回其值。
}ADTStack
2.设定队列的抽象数据类型定义为：
ADTQueue｛
D=｛ai|ai∈ElemSet，I=1，2，......，n,n≥0｝
Q）
构造一个空队列Q。
StackEmpty（Q）
队列Q已经存在。
若队列Q为空栈，则返回TRUE，否则返回FALSE。
EnQueue（&
Q,e）
插入元素e为Q的新的队尾元素。
DeQueue（&
Q,&
删除Q的对头元素，并以e返回其值。
}ADTQueue
2.程序包含四个模块：
1）主程序模块：
Voidmain（）
{
初始化；
For（）
接受处理命令；
}
接受处理；
2）栈模块——实现栈的抽象数据类型；
3）队列模块——实现队列的抽象数据类型。
4）魔王语言解释模块——定义线性表的结点结构。
各模块的之间的调用关系如下：
主程序模块
魔王语言解释模块
栈模块
队列模块
三、详细设计
1.栈类型
structStack
char*base;
char*top;
intstacksize;
};
2.队列类型
structStack
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;
q.rear->
next=p;
q.rear=p;
//元素出队
voidDeQueue（structLinkQueue&
q,char&
e）{
p=q.front->
next;
e=p->
data;
next=p->
if（q.rear==p）q.rear=q.front;
free（p）;
//判断队列是否为空，如果对为空，返回，否则返回
intQueueEmpty（structLinkQueueq）{
if（q.front==q.rear）return1;
elsereturn0;
//把字符数组从右至左压入栈中
voidInStack（char*ch,structStack&
{
inti,L=0;
while（ch[L]!
='
\0'
）L++;
for（i=L-1;
i>
=0;
i--）Push（s,ch[i]）;
}
4.主函数和其他函数的算法（含注释）：
#include<
stdio.h>
stdlib.h>
#defineSTACK_INIT_SIZE100
#defineSTACK_INCREMENT10
intmain（）
printf（"
**************************************************************\n"
）;
******************************\n"
**魔王语言解释系统**\n"
*班级：
物联网工程1001班*\n"
*姓名:
*********\n"
*学号:
0909100818*\n"
**************************************************************\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（"
魔王语言错误!
mark=0;
f=0;
break;
}
while（!
StackEmpty（S））
{
Pop（S,e1）;
if（e1=='
）'
{
f=1;
break;
}
elseif（!
（e1>
a'
&
e1<
z'
）&
!
A'
Z'
））
printf（"
魔王语言错误！
mark=0;
}
}
if（mark==0）
break;
if（f!
=1）
{
}
}
elseif（e1=='
printf（"
mark=0;
break;
elseif（!
））
}
}
if（mark==1&
f==1）//对符合语言规则的魔王语言进行规则处理
{
ClearStack（S）;
InStack（MoWang,S）;
//把魔王语言从右至左压栈存放
while（!
StackEmpty（S））//栈不空时，用栈temp进行存储不带括号内元素的元素
{
Pop（S,e1）;
if（e1=='
B'
||e1=='
）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）;
}
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
}
}
解释后的语言为：
StackEmpty（S））//依次出栈输出处理后的元素
Pop（S,e）;
EnQueue（Q,e）;
//元素进队是为了输出对应汉字
if（e=='
）printf（"
%s"
B）;
elseif（e=='
A）;
elseprintf（"
%c"
e）;
QueueEmpty（Q））//翻译成对应的汉字
DeQueue（Q,e）;
switch（e）
case'
t'
:
printf（"
天"
break;
d'
:
地"
break;
s'
上"
一只"
e'
鹅"
追"
g'
赶"
x'
下"
n'
蛋"
h'
恨"
天上一只鹅地上一只鹅"
上一只鹅"
default:
*"
printf（"
再次输入魔王语言（按数字键：
0----退出）\n"
scanf（"
%d"
&
xunhuan）;
return0;
四、调试分析
1.函数调用。
函数调用是语言中一块十分重要部分，它可以把一个程序分成若干部分，然后进行配置，所以这块内容一定要学好。
2.栈和队列问题比较简单。
3.由于考虑不周，如果同样的字母出现时，规则会要求重复输入，最终以最后一个为准，这是一个失误，后来改正程序，过滤掉重复字母。
五、测试分析
1、当输入A时系统显示：
2、当输入B（ehnxgz）B是系统显示：
六、用户手册
1、本程序运行在DOS命令下
2、进入程序后即显示用户界面：
3、注意输入后即可得到相应的结果。
七、附录（代码源程序及注释）
structStack//定义栈
s）//构造栈
s,chare）//往栈中压入元素
=STACK_
升级会员 