魔王语言解释实验报告.docx

魔王语言解释实验报告西安郵電學院数据结构设计报告题目:编制一个魔王语言解释的程序院系名称:通信与信息工程学院班级:学生姓名: 学号:指导教师: 设计起止时间:XX年5月1日~,可以使得我们对于栈和队列的操作更加熟练。这些操作包括栈的抽象数据定义、初始化栈、进栈、出栈。还有就是理解栈的操作只能在栈顶,先进后出;队列的操作在两端,队头删除队尾插入,先进先出等特点。①[问题描述]有一个魔王总是使用自己的一种非常精练而抽象的语言讲话,没人能听的懂。但他的语言是可以逐步解释成人能懂的语言,因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的:α->β1β2...βn (θδ1δ2...δn)->θδnθδ n-1...θδ1θ在这两种形式中,从左到右均表示解释;从右到左表示抽象。试写一个魔王解释系统,把他的话解释成人能听懂的话。②[基本要求] 用下述两条具体规则和上述规则形式实现。设大写字母表示魔王语言的词汇;小写字母表示人的语言词汇;希腊字母表示可以用大写或小写字母代换的变量。魔王语言可含人的词汇。B->tAdAA->sae③[测试数据]BB 解释成:tsaedsaeezegexenehetsaedsae 若将小写字母与汉字建立下表所示的对应关系,则魔王说的话是“天上一个 1、栈的抽象数据定义ADTStack 数据元素:可以是任意类型的数据,但必须属于同一个数据对象。结论关系:栈中数据元素之间是线性关系。基本操作: (1)InitStack(S)初始化栈(2)ClearStack(S)将栈S置成空栈(3)StackEmpty(S)判断栈是否为空(4)Push(S,e)在栈的顶部插入元素e (5)Pop(S,e)在栈的顶部删除元素用e带出2、队列的抽象数据定义ADTQueue 数据元素:可以是任意类型的数据,但必须属于同一个数据对象。结论关系:队列中数据元素之间是线性关系。基本操作: (1)InitQueue(Q)初始化队列(2)QueueEmpty(Q)判断队列是否为空(3)EnQueue(Q,e)在队列的队尾插入元素e (4)DeQueue(Q,e)在队列的顶部删除元素用e带出3、主函数模块intmain() {定义字符数组A[]="sae"定义字符数组B[]="tsaedsae" charflag='0';//flag用来标记处理括号初始化栈和队列用字符数组MoWang[100]="\0"接受魔王语言把魔王语言压入栈while(栈不为空) {进行栈和队列的操作}while(栈不为空) {边处理边进栈并用队列处理括号内元素}while(栈不为空) {依次出栈输出处理后的元素后然元素进队}while(队列不为空){输出对应汉字} 1、定义变量#defineSTACK_INIT_SIZE100 #defineSTACK_INCREMENT10 2、栈的类型和基本操作 structStack {char*base;char*top; intstacksize;}; voidInitStack(structStack&s){//构造栈=(char*)malloc(STACK_INIT_SIZE*sizeof(char));=; =STACK_INIT_SIZE;} voidPush(structStack&s,chare){//压入元素 if(>=STACK_INIT_SIZE) {=(char*)realloc(,(+STACK_INCREMENT)*sizeof(char));=+;+=STACK_INCREMENT;} *()=e;++;} voidPop(structStack&s,char&e){//取出元素e=*--;} intStackEmpty(structStacks){//栈是否为空if(==){ return1;}else{ return0;}} voidClearStack(structStack&s){ =;} 3、队列的类型和基本操作 structQueue{chardata; structQueue*next;}; structLinkQueue {structQueue*front;structQueue*rear;}; voidInitQueue(structLinkQueue&q){//构造队==(structQueue*)malloc(sizeof(structQueue));>next=NULL;} voidEnQueue(structLinkQueue&q,chare){//元素入队 structQueue*p; p=(structQueue*)malloc(sizeof(structQueue));p->data=