数据结构实习报告-魔王语言.doc

数据结构实习报告

题目：设计一个魔王语言解释系统
班级：信息管理与信息系统11-1
姓名：崔佳
学号：201101050903
完成日期：2013.06.02

0

一、需求分析
1. 本演示程序中，魔王语言限制在小写字母‘a’-‘z’之间且必须限制在括号内以及大写字母A和B。出现的重复字符或非法字符，程序运用时自动过滤去，输出的结果中将不含重复字符和非法字符。
2. 魔王语言遵守如下规则：
1) （θδ1δ2δ3…δn） θδnθδn-1…θδ1θ
2) B tAdA A sae
3. 演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。
4. 程序的执行命令包括：
1）选择操作
2）任意键结束
二、概要设计
为实现上述功能，需要栈和队列两个抽象数据类型。
1. 栈抽象数据类型定义

ADT stack{
数据对象：D={ai|ai∈Elemset,i=1,2,3,…n,n>=0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2, … n}
基本操作：
InitStack(&s)
操作结果：构造一个空栈s。
Push(&s, e)
初始条件：栈s已存在。
操作结果：插入元素e为新的栈顶元素。
Pop(&s, &e)
初始条件：栈s已存在且非空。
操作结果：删除栈s的栈顶元素，并用e返回其值。
StackLenth(&s)
初始条件：栈s已存在。
操作结果：返回s的元素个数，即栈的长度。
ClearStack(&s)
初始条件：栈s已存在。
操作结果：将s清为空栈。
DestoryStack(&s)
初始条件：栈s已存在。
操作结果：栈s被销毁。
StackEmpty(&s)
初始条件：栈s已存在。
操作结果：若是为空栈，则返回TRUE,否则返回FALSE。
Traverse(&s,void(*visit)())
初始条件：栈s已存在。
操作结果：依次遍历栈s中的元素，依次调用函数，一旦失败，则操作失败。
}ADT stack

2. 队列抽象数据类型定义

ADT Queue{
数据对象：D={ai|ai∈Elemset,i=1,2,3,…n,n>=0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2, … n}
基本操作：
InitQueue(&q)
操作结果：构造一个空队列Q。
EnQueue(&q, e)
初始条件：队列Q已存在。
操作结果：插入元素e为Q的新的队尾元素。
QueueLenth(&q)
初始条件：队列已存在。
操作结果：返回Q的元素个数，即队列的长度。
DeQueue(&q, &e)
初始条件：队列已存在。
操作结果：删除Q的队尾元素，并用e返回其值。
QueueEmpty(&q)
初始条件：队列Q已存在。
操作结果：若Q为空队列，则返回TRUE，否则返回FALSE.
ClearQueue(&q)
初始条件：队列Q已存在。
操作结果：清空队列Q。
DestoryQueue(&q)
初始条件：队列Q已存在。
操作结果：队列Q被销毁。不再存在。
QueueTraverse(&q,Status(*visit)())
初始条件：队列Q已存在。
操作结果：依次遍历队列Q的元素，依次调用函数，一旦失败，则操作失败。
}ADT Queue

2.本程序包括四个模块：
1） 主函数模块

void main() {
while() {
初始化；
接受命令；
处理命令；
}
}

2） 栈单元模块——实现栈的抽象数据类型
3） 队列单元模块——实现队列的抽象数据类型
4） 翻译函数模块——定义翻译函数的结构
3. 各模块之间的调用关系：

主程序模块
翻译函数模块
栈模块
队列模块

三、详细设计
1.栈类型
Typedef struct {
SElemType *base;
SElemType *top;
Int stacksize;
}SqStack;
2.队列类型
Typedef struct QNode{
QElemType data;
Struct QNode *next;
}QNode,*QueuePtr;
Typedef struct {
QueuePtr front;//队头指针
QueuePtr front;//队尾指针
}LinkQueue；

3.栈的基本操作

int Initstack(stack &s)
{ //初始化栈
s.base=(char*)malloc(100*sizeof(char));
if(!s.base)exit(0);
s.top=s.base;
s.stacksize=100;
return 1;
}
int IsEmpty(stack s)
{ //判空
if(s.top==s.base)return 1;
return 0;
}
void push(stack &s,char e)
{ //压栈
if(s.top-s.base>=s.stacksize)
{
s.base=(char*)realloc(s.base,(s.stacksize+10)*sizeof(char));
if(!s.base)exit(0);
s.top=s.base+s.stacksize;
s.stacksize+=10;
}
*s.top++=e;
}
int pop(stack &s,char &e)
{ //出栈

if(s.top==s.base)exit(0);
e=*--s.top;
return 1;
}
4.队列的基本操作
int initQueue(LinkQueue &Q)
{//初始化队列
Q.front=Q.rear=(LinkQueueNode)malloc(sizeof(LinkQueueNode));
if(!Q.front)exit(-1);
Q.front->next=NULL;
return 1;
}
int Isempty(LinkQueue Q)
{//判空
if(Q.front==Q.rear)return 1;
return 0;
}
int EnQueue(LinkQueue &Q,char e)
{//入队列
LinkQueueNode p;
p=(LinkQueueNode)malloc(sizeof(QNode));
if(!p)exit(-1);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return 1;
}
char DeQueue(LinkQueue &Q,char &e)
{//出队列
LinkQueueNode p;
if(Q.front==Q.rear)return 0;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return e;
}
3.求魔王语言解释的伪码算法：
void transmite(stack S)
{
LinkQueue Q;
initQueue(Q);
char c,e,ch;
char A[3]={'s','a','e'};
char B[8]={'t','s','a','e','d','s','a','e'};
printf("魔王要说的话是：");
while(!IsEmpty(S))
{
pop(S,e);
if(e=='B')
printf("tsaedsae");
else if(e=='A')
printf("sae");
else if(e=='(')
{
while(pop(S,e)&&e!=')')
{
EnQueue(Q,e);
}
push(S,e);
DeQueue(Q,c);
while(!Isempty(Q))
{
DeQueue(Q,e);
push(S,c);
push(S,e);
}
push(S,c);

while(!IsEmpty(S))
{
pop(S,e);
if(e==')')break;
else if(e=='B')
printf("tsaedsae");
else if(e=='A')
printf("sae");
else
printf("%c",e);
}
}
else
printf("%c",e);
}
printf("\n");
}

4.主函数和其他函数的算法：
void main()
{

bool flag=1;
char str,c;
while(flag==1)
{
stack S;
Initstack(S);
char a[100];
printf("魔王说话了：");
int i=0;
cin>>a;
while(a[i]) i++;
for(int k=i;k>=0;k--)
push(S,a[k]);
transmite(S);
printf("\n是否需要继续？是的话请按y: ");
scanf("%c",&str);
if(str=='y')flag=1;
else flag=0;
c=getchar();
}
}
5. 函数的调用关系图反映了演示程序的层次结构：

Main

Initiate transmite

Initiate pop push EnQueue DeQueue Isempty

四．调试分析
1.对栈和队列的结构特种和主要使用方向有了更加清楚的认识
2.函数调用是语言中一块十分重要部分，它可以把一个程序分成若干部分，然后进行配置。
五． 用户手册
本程序的运行结果为windows操作系统，执行文件为Mtranslation.exe。
进入程序后需要按规则输入魔王说的话，则程序给出翻译结果，可执行多条语句，用户界面如下：
六、测试结果
输入测试数据：B(exnxgz)B，则得到的翻译结果如下所示：

若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。
t
d
s
a
e
z
g
x
n
h
天
地
上
一只
鹅
追
赶
下
蛋
恨

11
11