云南大学数据结构实验3

实验难度： A □ B C □学期：2017秋季学期任课教师: 储星实验题目: 栈和队列及其应用组员及组长:承担工作：联系电话:电子邮件:完成提交时间： 2018 年 11 月 18 日一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析）魔王语言的解释规则：B →tAdA；A→ sae；(ehnxgz) → ezegexenehe 则魔王语言B(ehnxgz)B解释成tsaedsaeezegexenehetsaedsae大写字母表示魔王语言的词汇，小写字母表示人的词汇语言,魔王语言中可以包含括号，魔王语言的产生式规则在程序中给定，当接收用户输入的合法的魔王语言时，通过调用魔王语言翻译函数来实现翻译。

在 A 的基础上，（根据产生式）自定义规则，将一段魔王的话翻译为有意义的人类语言（中文）：字母-汉字对应表:"t d s a e z g x n h""天地上一个鹅追赶下蛋恨"运用了离散数学的一些基本知识及程序设计知识。

二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等）为实现上述程序功能，应以栈和队列来表示。

1.设定栈的抽象数据类型定义为：typedef struct stack{char *base; // 顺序栈的栈底指针char *top; // 顺序栈的栈顶int stacksize; // 栈元素空间的大小}stack; // 结构体类型顺序栈基本操作：ListInitiate (&S) 构造一个空栈S。

StackEmpty（S）栈S已经存在。

若栈S为空栈，则返回TRUE，否则返回FALSE。

Push（&S,e）栈S已经存在。

在栈S的栈顶插入新的栈顶元素e。

Pop（&S,&e）栈S已经存在。

删除S的栈顶元素，并以e返回其值。

2. 设定队列的抽象数据类型定义为：typedef struct QNode{char data;struct QNode *next;}*LinkQueueNode;typedef struct{LinkQueueNode front;LinkQueueNode rear;}LinkQueue;/*结构体队列类型*/基本操作：ListInitiate (&Q) 构造一个空队列Q。

StackEmpty（Q）队列Q已经存在。

若队列Q为空，则返回TRUE，否则返回FALSE。

EnQueue（&Q,e）队列Q已经存在。

插入元素e为Q的新的队尾元素。

DeQueue（&Q,&e）队列Q已经存在。

删除Q的队头元素，并以e返回其值。

2.程序包含四个模块：1）主程序模块：Void main(){初始化；For（）{接受处理命令；}接受处理；}2）栈模块——实现栈的抽象数据类型；3）队列模块——实现队列的抽象数据类型。

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

各模块的之间的调用关系如下：主程序模块魔王语言解释模块栈模块队列模块三、【实现（Implement）】(30%)（本部分应包括：抽象数据类型各操作的具体实现代码、关键操作的具体算法实现、函数实现，主程序实现等，并给出关键算法的时间复杂度分析。

如有界面则需包括界面的关键实现方法等。

）栈的基本操作：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 StackEmpty(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;}队列的基本操作：int InitQueue(LinkQueue &Q)// 初始化空队列{Q.front = Q.rear = (LinkQueueNode)malloc(sizeof(LinkQueueNode));if (!Q.front)exit(-1);Q.front->next = NULL;return 1;}int QueueEmpty(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;}魔王语言解释的具体实现：void checke(char e)// 翻译列表根据弹栈字母转化为汉字并打印void transmite(stack s)// 翻译模块{LinkQueue q;InitQueue(q);char c, e;printf("魔王是说：");while (!StackEmpty(s))// 若栈不为空则开始翻译{pop(s, e);checke(e);if (e == '(')// 括号处理{while (pop(s, e) && e != ')')// 括号匹配EnQueue(q, e);push(s, e);DeQueue(q, c);while (!QueueEmpty(q)){DeQueue(q, e);push(s, c);push(s, e);}push(s, c);while (!StackEmpty(s)){pop(s, e);if (e == ')')break;else checke(e);}}}printf("\n");}四、【测试结果（Testing）】(10%)（本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析，可附截图）五、【实验总结】(10%)（本部分应包括：自己在实验中完成的任务，及存在的问题，所完成实验过程中的具体经验总结、心得）问题关键：1. 栈的初始化，入栈出栈操作，栈为空的判断条件，队列的初始化，入队和出队操作，队列为空的判断。

以及队列中最后一个元素被删除后尾指针的修改。

2. 一些细节处理，比如数组操作等。

3.将魔王语言作为一个字符串读入进来，首先检查括号是否匹配，如果不匹配就无法解释。

如果匹配，然后将字符串从尾到头依次压入栈 S中，将栈 S中的内容依次弹出压入栈 S2中，直至遇到右括号，将其压入栈 S1中，并将栈 S2弹出依次压入栈 S1中，直至遇到左括号压入栈 S1中，这样栈 S1中存放的内容就是匹配的第一个内重括号，将栈 S1 栈顶元素左括号弹出，将左括号下面的那个元素保存在 e1 变量中，然后将其他元素弹出依次压入栈 S3中，在将 e1与栈 S3中依次弹出的元素压入栈S2 中，重复这个过程，直至将魔王语言中所有的括号都处理完为止，所以这个思路可以处理多重括号嵌套的问题。

六、思考题或【项目运作描述（Operate）】(10%)（注：选择C难度的才需要填写“项目运作描述”，其他难度的只需完成思考题）（项目运作描述应包括：项目的成本效益分析，应用效果等的分析。

）1. 栈：特点就是一个先进后出的结构。

主要用途：函数调用和返回，数字转字符，表达式求值，走迷宫等等。

在 CPU内部栈主要是用来进行子程序调用和返回，中断时数据保存和返回。

在编程语言中：主要用来进行函数的调用和返回。

可以说在计算机中，只要数据的保存满足先进后出的原理，都优先考虑使用栈，所以栈是计算机中不可缺的机制。

队列：特点就是一个先进先出的结构。

只要满足数据的先进先出原理就可以使用队列。

2. 可以采用顺序存储结构和链式存储结构，因为他们都是线性表，就像一排站在一条线上的人，位置关系是一个挨一个的，这样的顺序不会改变，而改变点都在头或者尾，仍然保持形态不变的。

七、【代码】(10%)（本部分应包括：完整的代码及充分的注释。

注意纸质的实验报告无需包括此部分。

格式统一为，字体: Georgia , 行距: 固定行距12，字号: 小五）#include<iostream>#include<stdlib.h>using namespace std;typedef struct stack{char *base; // 顺序栈的栈底指针char *top; // 顺序栈的栈顶int stacksize; // 栈元素空间的大小}stack; // 结构体类型顺序栈typedef struct QNode{char data;struct QNode *next;}*LinkQueueNode;typedef struct{LinkQueueNode front;LinkQueueNode rear;}LinkQueue;/*结构体队列类型*/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 StackEmpty(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;}int InitQueue(LinkQueue &Q)// 初始化空队列{Q.front = Q.rear = (LinkQueueNode)malloc(sizeof(LinkQueueNode));if (!Q.front)exit(-1);Q.front->next = NULL;return 1;}int QueueEmpty(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;}void checke(char e)// 翻译列表{if (e == 'B')printf("天上一只鹅地上一只鹅");else if (e == 'A')printf("上一只鹅");else if (e == 't')printf("天");else if (e == 'd')printf("地");else if (e == 's')printf("上");else if (e == 'a')printf("一只");else if (e == 'e')printf("鹅");else if (e == 'z')printf("追");else if (e == 'g')printf("赶");else if (e == 'x')printf("下");else if (e == 'n')printf("蛋");else if (e == 'h')printf("恨");else if (e != '(' && e != ')')printf("%c", e);}void transmite(stack s)// 翻译模块{LinkQueue q;InitQueue(q);char c, e;printf("魔王是说：");while (!StackEmpty(s))// 若栈不为空则开始翻译{pop(s, e);checke(e);if (e == '(')// 括号处理{while (pop(s, e) && e != ')')// 括号匹配EnQueue(q, e);push(s, e);DeQueue(q, c);while (!QueueEmpty(q)){DeQueue(q, e);push(s, c);push(s, e);}push(s, c);while (!StackEmpty(s)){pop(s, e);if (e == ')')break;else checke(e);}}}printf("\n");}void main(){stack s;Initstack(s);char a[100];cout <<"规则:"<< endl;cout <<"α->β1β2...βn"<< endl;cout <<"(θδ1δ2...δn)->θδnθδn-1...θδ1θ"<< endl;cout <<""<< endl;cout <<"字母-汉字对应表:"<< endl;cout <<"t d s a e z g x n h"<< endl;cout <<"天地上一个鹅追赶下蛋恨"<< endl;cout <<""<< endl;cout <<"魔王说：";int i = 0;cin >> a;while (a[i])i++;for (int k = i; k >= 0; k--)push(s, a[k]);transmite(s);system("pause");}。