实验二、栈及其应用

《实验二、栈及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、栈和队列及其应用上机实验报告课程名称：数据结构班级:实验日期：姓名：学号：指导教师：实验序号：实验成绩：一、实验名称：魔王语言解释二、实验目的及要求问题描述有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）α－>β1β2…βm（2）（θδ1δ2…δn)－>θδnθδn－1…θδ1θ在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。基本要求用下述两条具体规则和上述规则形式（2）实现

2、。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。（1）B－>tAdA（2）A－>sae三、实验环境VisualC++6.0四、实验过程(1)以一维数组demon[i]表示魔王语言．(2)魔王语言由用户输入,初始保存在demon[i]中．(3)魔王语言与人类语言对应关系固化在程序中．(4)实现过程：A：初始，魔王语言接收后存放在demon[i]中．B：初次遍历数组，将数组中括号内的元素入栈，同时插入相应首字母；C：再次遍历数组，将数组元素依次入队。（小写字母直接入队；大写字

3、母经翻译成相应字符后入队；遇到括号，将栈中保存的元素依次出栈入队）在翻译过程中，如果依旧包含大写字母，则置flag为1，否则为0。D：将队列中元素赋值给demon[i]。如果此时flag=1，则再次重复C过程。直至所有元素为人类语言。E：输出demon[i]。此时数组中元素为对应的人类语言。注：如果程序中没有相应的对应关系，则翻译成“?”五、程序源代码#include#include#include#include#include#include

4、.h>#include#defineTRUE1#defineFALSE0typedefstructnode/*定义链栈存储魔王语言*/{chardata1;structnode*next;}LinkStackNode;typedefLinkStackNode*LinkStack;typedefstructresult/*定义链表存储翻译结果*/{chardata1[20];structresult*next;}RESULT;typedefstructNode/*定义链队列*/{chardata1;structNode*next;}

5、LinkQueueNode;typedefstruct{LinkQueueNode*front;LinkQueueNode*rear;}LinkQueue;typedefstructrule/*定义链表存储规则*/{chardata1;chardata2[20];structrule*next;}RULE;typedefstructmean/*定义链表存储字母含义*/{chardata1;chardata2[20];structmean*next;}MEAN;voidInitStack(LinkStacktop)/*链栈的初始化*/{top->nex

6、t=NULL;}intPush(LinkStacktop,charx)/*进栈操作*/{LinkStacktemp;temp=(LinkStack)malloc(sizeof(LinkStackNode));if(temp==NULL)returnFALSE;/*申请空间失败*/temp->data1=x;temp->next=top->next;top->next=temp;/*修改当前栈顶指针*/returnTRUE;}intPop(LinkStacktop,char*x)/*出栈操作*/{LinkStacktemp;temp=top->next

7、;if(temp==NULL)returnFALSE;/*栈为空*/top->next=temp->next;*x=temp->data1;free(temp);/*释放存储空间*/returnTRUE;}intInitQueue(LinkQueue*q)/*链队列初始化*/{q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(q->front!=NULL){q->rear=q->front;q->front->next=NULL;returnTRUE;}elsereturnFALSE;

8、}intEnterQueue(LinkQueue*q,charx)/*入队操作*/{LinkQueueNod