实验2 栈和队列的应用-算术表达式求值

实验二 栈和队列实现四则运算一、实验目的及要求：1、掌握栈和队列的基本操作：建立、插入、删除、查找、合并2、掌握用栈和队列的储存3、熟悉C 语言上机编程环境4、掌握编译、调试程序的方法二、实验内容：采用栈进行表达式的求值，表达式求值是程序设计语言编译中的一个最基本问题。

它的实现是栈应用的又一个典型例子，本报告使用的是“算符优先法”求表达式的值。

要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。

若要正确翻译则首先要了解算术四则运算的规则。

即：（1）、先乘除，后加减； （2）、从左算到右； （3）、先括号内后括号外。

任何一个表达式都是由操作数、运算符和界限符组成的，我们称它们为单词。

一般地，操作数既可以是常数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符3类；基本界限符有左右括号和表达式结束符等。

为了叙述的简洁，我们仅讨论简单算术表达式的求值问题。

这种表达式只包含加、减、乘、除4种运算符。

我们把运算符和界限符统称为算符，它们构成的集合命名为OP 。

根据上述3条运算规则，在运算的每一步中，任意两个相继出现的算符1θ和2θ之间的优先级之多是以下3种关系之一：12θθ< 1θ的优先级低于2θ 12θθ= 1θ的优先级等于2θ 12θθ> 1θ的优先级高于2θ根据实际情况推导出如下的优先关系算符间的优先关系表有规则（3），+、-、*和/为1θ时优先性均低于“（”但高于“），”由规则（2），当12θθ=时，令12θθ>，“#”是表达式的结束符。

为了算法简洁，在表达式左右括号的最左边也虚设了一个“#”构成整个表达式的一对括号。

表中的“（”=“）”表示当左右括号相遇时，括号内的运算已经完成。

同理，“#”=“#”表示整个表达式求值完毕。

“）”与“（、“#”与“）”以及“（”与“#”之间无优先级，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现语法错误。

实验二栈和队列的操作一、实验目的1．熟悉栈和队列的存储结构；2．熟悉栈和队列的相关操作；3．利用栈和队列求解一些常见问题。

二、实验内容1、表达式求值任何一个算术表达式都是由操作数(operand) 、运算符(operator) 和界限符(edlimiter) 组成的。

为了简化问题．这里假设算术表达式中的操作数为单个数字表示的变量：运算符有加“ + ”、减“—”、乘“ * ”、除“／”和括号，表达式以“#”结束。

运算法则是括号优先级最高，先乘除，后加减，同级运算自左至右。

程序设计时需设置两个工作栈。

一个称为运算符栈，用OP 表示，用于存放表达式中的运算符：另一个称为操作数栈，用S 表示，用于存放操作数或运算结果。

这两个栈的初始状态均为空。

计算机从左至右扫描表达式，凡遇操作数一律进S 栈；若遇运算符，则要把它的优先数和栈顶运算符的优先数进行比较：若前者大，则该运算符进OP 栈；否则，栈顶运算符退栈、并进行计算，运算对象为S 栈顶上的两个元素，且先退栈的元素在运算量的右侧，后退栈的在运算量的左侧。

试编写一程序，先输入一个表达式，再求表达式的值。

2、数制转换假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。

从计算过程可见，这八进制的各个数位产生的顺序是从低位到高位的，而打印输出的顺序，一般来说应从高位到低位，这恰好和计算过程相反。

因此，需要先保存在计算过程中得到的八进制数的各位，然后逆序输出，因为它是按“后进先出”的规律进行的，所以用栈最合适。

试编写一个程序，实现将十进制数转换成八进制数并输出。

三、主要任务1、完成算法设计和程序设计，并分析算法时间复杂度和空间复杂度；2、写出程序运行情况，写出输入数据及运行结果；3、撰写实验报告，写出算法设计小结和心得。

四、思考题1、为什么说栈是一种特殊线性表？它的操作与线性表有什么不同？2、对于数制转换算法，如果不用栈如何实现？。

浙江大学城市学院实验报告课程名称数据结构与算法实验项目名称实验二栈的应用---算术表达式的计算实验成绩指导老师（签名）日期一.实验目的和要求1．进一步掌握栈的基本操作的实现。

2．掌握栈在算术表达式的计算方面的应用。

二. 实验内容1. 编写程序利用栈将中缀表达式转换成后缀表达式，即从键盘输入任一个中缀表达式（字符串形式），转换成后缀表达式后，将后缀表达式输出。

假设：中缀表达式包含圆括号( ) 及双目运算符+、-、*、/、^（乘方）。

要求：把栈的基本操作的实现函数存放在头文件stack1.h中（栈元素的类型为char），在主文件test6_2.cpp中包含将中缀表达式S1转换成后缀表达式S2的转换函数void Change( char *S1, char *S2 )及主函数，在主函数中进行输入输出及转换函数的调用。

2. 选做：编写利用栈对后缀表达式进行求值的函数double Compute(char *str)，以计算从前述程序得到的后缀表达式的值。

要求：把栈的基本操作的实现函数存放在头文件stack2.h中（栈元素的类型为double），在主文件test6_2.cpp中添加后缀表达式求值函数，并在主函数中增加调用求值函数及输出结果值的语句。

3. 填写实验报告，实验报告文件取名为report2.doc。

4. 上传实验报告文件report2.doc与源程序文件stack1.h、stack2.h（若有）及test6_2.cpp到Ftp服务器上你自己的文件夹下。

二.函数的功能说明及算法思路（算法思路见源程序的注释部分）//栈的顺序存储结构定义struct Stack{ElemType *stack;int top;int MaxSize;};//初始化栈S为空void InitStack(Stack &S)//元素item进栈，即插入到栈顶void Push(Stack &S,ElemType item)//删除栈顶元素并返回ElemType Pop(Stack &S)//读取栈顶元素的值ElemType Peek(Stack &S)//判断S是否为空，若是则返回true，否则返回false bool EmptyStack(Stack &S)//清除栈S中的所有元素，释放动态存储空间void ClearStack(Stack &S)//将中缀算术表达式转换为后缀算术表达式void Change(char *S1,char *&S2)//返回运算符op所对应的优先级数值int Precedence(char op)//计算由str所指字符串的后缀表达式的值double Compute(char *str)四. 实验结果与分析五. 心得体会【附录----源程序】test6_2.cpp#include<iostream.h>#include<stdlib.h>#include<math.h>#include"stack1.h"#include"stack2.h"void main(){char x[30],y[30];double r;while(1){cout<<"请输入一个中缀算术表达式：";cin.getline(x,sizeof(x));Change(x,y);cout<<"对应的后缀算术表达式为：";cout<<y<<endl;r=Compute(y);cout<<"后缀算术表达式值为："<<r<<endl<<endl;}}stack1.htypedef char ElemType1;struct Stack1{ElemType1 *stack;int top;int MaxSize;};void InitStack(Stack1 &S){S.MaxSize=10;S.stack=new ElemType1[S.MaxSize];if(!S.stack){cerr<<"动态储存分配失败"<<endl;exit(1);}S.top=-1;}void Push(Stack1 &S,ElemType1 item)if(S.top==S.MaxSize-1){int k=sizeof(ElemType1);S.stack=(ElemType1*)realloc(S.stack,2*S.MaxSize*k);S.MaxSize=2*S.MaxSize;}S.top++;S.stack[S.top]=item;}ElemType1 Pop(Stack1 &S){if(S.top==-1){cerr<<"Stack is empty! "<<endl;exit(1);}S.top--;return S.stack[S.top+1];}ElemType1 Peek(Stack1 &S){if(S.top==-1){cerr<<"Stack is empty! "<<endl;exit(1);}return S.stack[S.top];}bool EmptyStack(Stack1 &S){return S.top==-1;}void ClearStack(Stack1 &S){if(S.stack){delete []S.stack;S.stack=0;}S.top=-1;S.MaxSize=0;}//返回运算符op所对应的优先级数值int Precedence(char op){switch(op){case'+':case'-':return 1;case'*':case'/':return 2;case'^':return 3;case'(':case'@':default:return 0;}}//将中缀算术表达式转换为后缀算术表达式void Change(char *S1,char *S2){Stack1 R;InitStack(R);Push(R,'@');int i=0,j=0;char ch=S1[i];while(ch!='\0'){//对于空格字符不做任何处理，顺序读取下一个字符if(ch==' ')ch=S1[++i];//对于左括号，直接进栈else if(ch=='('){Push(R,ch);ch=S1[++i];}//对于右括号，使括号内的仍停留在栈中的运算符依次出栈并写入S2else if(ch==')'){while(Peek(R)!='(')S2[j++]=Pop(R);Pop(R);//删除栈顶的左括号ch=S1[++i];}//对于运算符，使暂存于栈顶且不低于ch优先级的运算符依次出栈并写入S2else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='^'){char w=Peek(R);while(Precedence(w)>=Precedence(ch)){S2[j++]=w;Pop(R);w=Peek(R);}Push(R,ch);//把ch运算符写入栈中ch=S1[++i];}else{if((ch<'0'||ch>'9')&&ch!='.'){cout<<"中缀表达式表示错误！"<<endl;exit(1);}while((ch>='0'&&ch<='9')||ch=='.'){S2[j++]=ch;ch=S1[++i];}S2[j++]=' ';}}//把暂存在栈中的运算符依次退栈并写入到S2中ch=Pop(R);while(ch!='@'){if(ch=='('){cerr<<"expression error!"<<endl;exit(1);}else{S2[j++]=ch;ch=Pop(R);}}S2[j++]='\0';}stack2.htypedef double ElemType2;struct Stack2{ElemType2 *stack;int top;int MaxSize;};void InitStack(Stack2 &S){S.MaxSize=10;S.stack=new ElemType2[S.MaxSize];if(!S.stack){cerr<<"动态储存分配失败"<<endl;exit(1);}S.top=-1;}void Push(Stack2 &S,ElemType2 item){if(S.top==S.MaxSize-1){int k=sizeof(ElemType2);S.stack=(ElemType2*)realloc(S.stack,2*S.MaxSize*k);S.MaxSize=2*S.MaxSize;}S.top++;S.stack[S.top]=item;}ElemType2 Pop(Stack2 &S){if(S.top==-1){cerr<<"Stack is empty! "<<endl;exit(1);}S.top--;return S.stack[S.top+1];}ElemType2 Peek(Stack2 &S){if(S.top==-1){cerr<<"Stack is empty! "<<endl;exit(1);}return S.stack[S.top];}bool EmptyStack(Stack2 &S){return S.top==-1;}void ClearStack(Stack2 &S){if(S.stack){delete []S.stack;S.stack=0;}S.top=-1;S.MaxSize=0;}//计算由str所指字符串的后缀表达式的值double Compute(char *str){Stack2 S;InitStack(S);double x,y;int i=0;while(str[i]){if(str[i]==' '){i++;continue;}switch(str[i]){case '+':x=Pop(S)+Pop(S);i++;break;case'-':x=Pop(S);x=Pop(S)-x;i++;break;case'*':x=Pop(S)*Pop(S);i++;break;case'/':x=Pop(S);if(x!=0)x=Pop(S)/x;else{cerr<<"Divide by 0!"<<endl;exit(1);}i++;break;case'^':x=Pop(S);x=pow(Pop(S),x);i++;break;default:x=0;while(str[i]>=48&&str[i]<=57){x=x*10+str[i]-48;i++;}if(str[i]=='.'){i++;y=0;double j=10.0;while(str[i]>=48&&str[i]<=57){y=y+(str[i]-48)/j;i++;j*=10;}x+=y;}}Push(S,x);}if(EmptyStack(S)){cerr<<"expression error!"<<endl;exit(1);}x=Pop(S);if(EmptyStack(S))return x;else{cerr<<"expression error!"<<endl;exit(1);}ClearStack(S);}（注：可编辑下载，若有不当之处，请指正，谢谢!）。

实验二栈和队列本文档旨在介绍实验二的目的和背景，以及本实验的重要性。

实验二主要涉及栈和队列的相关概念和操作。

栈和队列是常用的数据结构，它们在计算机科学和软件开发中起着重要的作用。

栈是一种先进后出（Last In First Out，LIFO）的数据结构，类似于我们平常堆放书籍的行为。

队列是一种先进先出（First In First Out，FIFO）的数据结构，类似于排队等待的情景。

通过本实验，我们将研究如何使用栈和队列来解决各种问题。

掌握栈和队列的基本原理和操作，对于提高程序的效率和优化算法都具有重要意义。

同时，栈和队列的概念也是许多其他数据结构和算法的基础，理解栈和队列将有助于我们更深入地研究和应用其他数据结构和算法。

本实验将引导我们通过实际的编程练来加深对栈和队列的理解和应用。

我们将实现栈和队列的基本操作，例如入栈、出栈、入队、出队等，并通过一系列的例子和问题来巩固对这些概念的理解。

通过完成本实验，我们将掌握栈和队列的基本概念和操作，加深对其应用场景的理解和掌握，并培养解决问题的逻辑思维能力和编程实践能力。

让我们开始实验二的研究，进一步探索栈和队列的奥秘吧！本实验的目标是研究和理解栈和队列数据结构的基本概念和操作。

本实验主要涉及栈和队列的定义、基本操作及其应用。

栈的定义栈是一种具有后进先出（Last-In-First-Out，简称LIFO）特性的线性数据结构。

栈只允许在表尾（称为栈顶）进行插入和删除操作，且最后插入的元素最先删除。

栈的基本操作栈的基本操作包括：Push：将元素插入到栈顶。

Pop：删除栈顶的元素，并返回被删除的元素。

IsEmpty：判断栈是否为空。

Top：返回栈顶的元素，但不删除栈顶元素。

栈的应用栈在计算机科学中有广泛的应用，包括但不限于：函数调用（函数调用时的局部变量保存在栈中）。

表达式求值（后缀表达式计算等）。

浏览器的页面回退功能。

队列的定义队列是一种具有先进先出（First-In-First-Out，简称FIFO）特性的线性数据结构。

栈和队列的应用实验报告栈和队列的应用实验报告引言：栈和队列是计算机科学中常用的数据结构，它们在各种算法和应用中都有广泛的应用。

本实验报告旨在探讨栈和队列的基本概念、特性以及它们在实际应用中的具体使用。

一、栈的基本概念和特性栈是一种特殊的数据结构，它遵循“先进后出”的原则。

栈有两个基本操作：压栈（push）和弹栈（pop）。

压栈将元素添加到栈的顶部，弹栈则将栈顶元素移除。

栈还具有一个重要的特性，即它的访问方式是受限的，只能访问栈顶元素。

在实际应用中，栈可以用于实现递归算法、表达式求值、括号匹配等。

例如，在递归算法中，当函数调用自身时，需要将当前状态保存到栈中，以便在递归结束后能够恢复到正确的状态。

另外，栈还可以用于实现浏览器的“后退”功能，每次浏览新页面时，将当前页面的URL压入栈中，当用户点击“后退”按钮时，再从栈中弹出最近访问的URL。

二、队列的基本概念和特性队列是另一种常见的数据结构，它遵循“先进先出”的原则。

队列有两个基本操作：入队（enqueue）和出队（dequeue）。

入队将元素添加到队列的尾部，出队则将队列头部的元素移除。

与栈不同的是，队列可以访问头部和尾部的元素。

在实际应用中，队列经常用于任务调度、消息传递等场景。

例如，在操作系统中，任务调度器使用队列来管理待执行的任务，每当一个任务执行完毕后，从队列中取出下一个任务进行执行。

另外，消息队列也是一种常见的应用，它用于在分布式系统中传递消息，保证消息的顺序性和可靠性。

三、栈和队列在实际应用中的具体使用1. 栈的应用栈在计算机科学中有广泛的应用。

其中一个典型的应用是表达式求值。

当计算机遇到一个复杂的表达式时，需要将其转化为逆波兰表达式，然后使用栈来进行求值。

栈的特性使得它非常适合处理这种情况，可以方便地保存运算符和操作数的顺序，并按照正确的顺序进行计算。

另一个常见的应用是括号匹配。

在编程语言中，括号是一种常见的语法结构，需要保证括号的匹配性。

数据结构实验报告实验名称：实验2——栈和队列1 实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力2 实验内容利用栈结构实现八皇后问题。

八皇后问题19世纪著名的数学家高斯于1850年提出的。

他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。

请设计算法打印所有可能的摆放方法。

提示：1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析主程序：#include<iostream>using namespace std;const int StackSize=8; //皇后的个数int num=0;template <class T>class SeqStack //定义顺序栈模板类{public:SeqStack(){top=-1;} //构造函数，初始化空栈void Push(T x); //入栈操作void Pop();//出栈操作void PlaceQueen(int row); //放置皇后bool Judgement();//判断是否符合条件void Print();//输出符合条件的皇后排列bool Empty(){if(top==-1) return true;else return false;}; //判断栈是否为空private:T data[StackSize]; //定义数组int top; //栈顶指针};template <class T>void SeqStack<T>::Push(T x) //入栈操作{if(top>=StackSize-1) throw"上溢";top++;//栈顶指针上移data[top]=x;}template <class T>void SeqStack<T>::Pop()//出栈操作{if(Empty()) throw"下溢";top--;//栈顶指针下移}template <class T>bool SeqStack<T>::Judgement()//判断该位置是否合适{for(int i=0;i<top;i++)if(data[top]==data[i]||(abs(data[top]-data[i]))==(top-i))//判断是否满足任意两个皇后不在同列同一斜线return false;return true;}template <class T>void SeqStack<T>::PlaceQueen(int row) //放置皇后{for (int i=0;i<StackSize;i++){Push(i); //入栈if (Judgement())//判断位置是否合适{if (row<StackSize-1)PlaceQueen(row+1); //如果合适满足条件则放置一个皇后,递归调用else{num++;//不满足条件则到下一行Print();//输出符合条件的皇后}}Pop();//出栈}}template <class T>void SeqStack<T>::Print()//输出皇后函数{cout<<"NO."<<num<<":"<<endl; for(int i=0;i<StackSize;i++){for(int j=0;j<data[i];j++){cout<<"□";}cout<<"■";for(int j=StackSize-1;j>data[i];j--){cout<<"□";}cout<<endl;}cout<<endl;}void main(){SeqStack<int> Queen;Queen.PlaceQueen(0);cout<<"总共有"<<num<<"种摆放方法。

实验二栈与队列操作实验题目实验二栈与队列操作实验目的：(1)理解栈与队列的结构特征和运算特征，以便在实际问题背景下灵活运用。

(2)了解复杂问题的递归算法设计。

本次实验中，下列实验项目选做一。

1、顺序栈的基本操作[问题描述]设计算法，实现顺序栈的各种基本操作[基本要求]（1）初始化栈s。

（2）从键盘输入10个字符以$结束，建立顺序栈。

（3）从键盘输入1个元素，执行入栈操作。

（4）将栈顶元素出栈。

（5）判断栈是否为空。

（6）输出从栈顶到栈底元素。

要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。

2、链栈的基本操作[问题描述]设计算法，实现链栈的各种基本操作[基本要求]（1）初始化栈s。

（2）从键盘输入10个字符以$结束，建立带头结点的链栈。

（3）从键盘输入1个元素，执行入栈操作。

（4）完成出栈操作。

（5）判断栈是否为空。

（6）输出从栈顶到栈底元素。

（7）输出链栈的长度。

要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。

3、循环队列的基本操作[问题描述]设计算法，实现循环顺序队列的建立、入队、出队等操作。

[基本要求]（1）从键盘输入10个字符以$结束，建立循环队列，并显示结果。

（2）从键盘输入1个元素，执行入队操作，并显示结果。

（3）将队头元素出队，并显示结果。

（4）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。

4、只用尾指针表示的循环链表队列的综合操作[问题描述]假设以带头结点的的循环链表表示队列，并且只设一个指针指向队尾元素的结点（注意不设头指针），试编写队列初始化、入队、出队函数。

[基本要求及提示]（1）首先定义链表结点类型。

（2）编写带头结点的循环链表的初始化函数，只用尾指针表示。

（3）编写入队函数、出队函数。

（4）在主函数中编写菜单（1.初始化；2.入队；3.出队；4.退出），调用上述功能函数。

2011-2012学年第一学期数据结构课内实验报告实验名:栈和队列的应用：表达式的求值姓名：学号：班级：指导老师:日期：实验题目：1、实验目的：通过此实验进一步理解栈和队列，提高运用理论解决实际问题的能力。

2、实验内容:例如，输入9-（2+4*7）/5+3# ，并按回车键，即可输出结果如下：表达式的运算结果是：6表达式的后缀表达式为：9 2 4 7 * +5/-3+3、数据结构及算法思想:表达式计算是实现程序设计逻辑语言的基本问题之一，也是栈和队列应用的一个典型的例子。

该设计是先通过栈将中缀表达式转换为后缀表达式，在转换过程中又用到了队列的操作。

而在得到后缀表达式之后，又用到队列的操作对生成的后缀表达式进行计算。

在整个设计的实现过程中，用到的都是栈和队列的概念。

4、模块化分:本程序分为2个模块：（1）中缀表达式转换为后缀表达式；（2）求后缀表达式5、详细设计及运行结果:(1)中缀表达式转换为后缀表达式void CTPostExp(SeqQueue *Q){SeqStack S; //运算符栈char c,t;InitStack(&S); //初始化栈Push(&S,'#'); //压入栈底元素‘#’do { //扫描中缀表达式c=getchar();switch(c){case ' ':break; //去除空格符case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9': EnQueue(Q,c);break;case '(':Push(&S,c);break;case ')':case '#':do{t=Pop(&S);if(t!='('&&t!='#') EnQueue(Q,t);}while(t!='('&&S.top !=-1);break;case '+':case '-':case '*':case '/':while(Priority(c)<=Priority(GetTop(S))){t=Pop(&S);EnQueue(Q,t);}Push(&S,c);break;}}while(c!='#'); //以'#'号结束表达式扫描}(2)后缀表达式的计算DataType CPostExp(SeqQueue Q) {SeqStack S;char ch;int x,y;InitStack(&S);while(!QueueEmpty(Q)){ch=DeQueue(&Q);if(ch>='0' &&ch<='9')Push(&S,ch);else{y=Pop(&S)-'0';x=Pop(&S)-'0';switch(ch){case '+':Push(&S,(char)(x+y+'0'));break;case '-':Push(&S,(char)(x-y+'0'));break;case '*':Push(&S,(char)(x*y+'0'));break;case '/':Push(&S,(char)(x/y+'0'));break;}}}return GetTop(S);}输入9-（2+4*7）/5+3# ，并按回车键，输出：表达式的运算结果是：6表达式的后缀表达式为：9 2 4 7 * +5/-36、调试情况，设计技巧及体会：表达式是由运算对象、运算符、括号组成的有意义的式子。

实验报告课程名称数据结构实验项目实验二--栈和队列实验系别___ _计算机学院 _ ______专业___ _计算机科学与技术___班级/学号__学生姓名 ____________实验日期成绩_______________________指导教师实验题目：实验二-----栈和队列实验一、实验目的1)掌握栈的顺序存储结构及队列的链式存储结构；2)验证栈的顺序存储结构的操作的实现；3)验证队列的链式存储结构的操作的实现；4)理解算法与程序的关系，能够将算法转换为对应程序。

二、实验内容1)建立一个顺序存储的空栈，并以此分别实现入栈、出栈、取栈顶元素；2)建立一个链式结构的空队列，并以此分别实现入队、出队、取队头等基本操作；3)尝试利用栈和队列的算法解决一些实际的应用问题。

设计与编码1)实验题目主要需求说明2)设计型题目：表达式求值（要求利用栈结构和运算符优先约定表，输入一个表达式，并计算求值）3)结合题目，说明利用栈或队列解决问题的基本算法描述4)程序源码#include<iostream>using namespace std;const int InitSize=100;const int IncreastSize=10;template<class datatype>class SqStack {private:datatype *base;datatype *top;int stacksize;public:SqStack();void DestroyStack();void ClearStack();int StackLength();bool IsEmpty();bool GetTop(datatype &e);bool Pop(datatype &e);bool Push(datatype e);};template<class datatype>SqStack<datatype>::SqStack(){base=new datatype[InitSize];if(!base)exit(1);top=base;stacksize=InitSize;}template<class datatype>void SqStack<datatype>::DestroyStack() {delete[] base;base=top=NULL;stacksize=0;}template<class datatype>void SqStack<datatype>::ClearStack() {top=base;}template<class datatype>int SqStack<datatype>::StackLength() {return top-base;}template<class datatype>bool SqStack<datatype>::IsEmpty() {if(top==base)return fasle;else return true;}template<class datatype>bool SqStack<datatype>::GetTop(datatype &e){if(top==base)return false;e=*(top-1);return true;}template<class datatype>bool SqStack<datatype>::Pop(datatype &e){if(top==base)return false;e=*(top-1);top--;return true;}template<class datatype>bool SqStack<datatype>::Push(datatype e){if(top-base>=stacksize){base=(datatype *)realloc( base , (stacksize+IncreastSize)*sizeof(int) ); if(!base)exit(1);top=base+stacksize;stacksize+=IncreastSize;}*(top)=e;top++;return true;}int com(char m,char t){if(t=='(') return -1;else if(t==')'){if(m=='+'||m=='-'||m=='*'||m=='/') return 1; else if(m=='(') return 0;else return -2;}else if(t=='*'||t=='/'){if(m=='+'||m=='-'||m=='#'||m=='(') return -1; else return 1;}else if(t=='+'||t=='-'){if(m=='#'||m=='(') return -1;else return 1;}else{if(m=='#')return 0;else if(m=='+'||m=='-'||m=='*'||m=='/') return 1; else return -2;}}void main(){SqStack <char> op;SqStack <double> re;char t,m;double result,flag=1;op.Push('#');t=getchar();while(true){if(t>='0'&&t<='9'){double s=0;s=s*10+t-'0';t=getchar();while(t>='0'&&t<='9' ){s=s*10+t-'0';t=getchar();}re.Push(s);}else if(t=='+'||t=='-'||t=='*'||t=='/'||t=='('||t==')'||t=='\n') { op.GetTop(m);while(com(m,t)==1 ){double x1,x2;op.Pop(m);if(re.Pop(x2)&&re.Pop(x1)){if(m=='+') re.Push(x1+x2);else if(m=='-') re.Push(x1-x2);else if(m=='*') re.Push(x1*x2);else if(m=='/') {if(x2!=0)re.Push(x1/x2); else flag=0;} }else flag=0;op.GetTop(m);}if(com(m,t)==-1)op.Push(t);else if(com(m,t)==0)op.Pop(m);else flag=0;if(!op.GetTop(m)) break;t=getchar();}else t=getchar();}if(re.GetTop(result)&&flag)cout<<result<<endl;else cout<<"Input error!\n";}5)运行结果三、总结与心得。

《数据结构》实验报告一软件1321徐蜀实验二栈和队列的基本操作及其应用一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。

2、掌握栈和队列的特点，即后进先出和先进先出的原则。

3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。

二、实验内容1．回文判断三、实验要求1、按照数据结构实验任务书，提前做好实验预习与准备工作。

2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。

3、严格按照数据结构实验报告模板和规范，及时完成实验报告。

四、实验步骤（说明：依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（函数）的伪码算法、函数实现、程序编码、调试与分析。

附流程图与主要代码）㈠、数据结构与核心算法的设计描述（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）1、栈的初始长度与需要再增加的长度#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef char SElemType;//定义SElemType为char型2、栈的顺序存储表示typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;3、队列的链式表示方法typedef struct QNode{SElemType data;struct QNode *next;} QNode, *QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;4、初始化栈/* 函数功能：对栈进行初始化参数：栈（SqStack &S）成功返回1，否则返回0 */int InitStack(SqStack &S){S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));//申请内存if(!S.base) //判断有无申请到空间return ERROR; //没有申请到内存，返回0S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}5、入栈操作/* 函数功能：将元素入栈参数：栈（SqStack &S）,插入元素e插入成功返回1，否则返回0 */int Push(SqStack &S, SElemType e){if(S.top - S.base >= S.stacksize) //判断栈顶与栈底的差是否大于栈的//容量{S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType)); //栈满了，重新申请内存if(!S.base) //判断是否申请成功return ERROR; //不成功返回0S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;return OK;}6、出栈操作/* 函数功能：将栈中的元素弹出参数：栈(SqStack &S),记录元素e */int Pop(SqStack &S, SElemType &e){if(S.top == S.base) //判断栈是否为空return ERROR;e = *(--S.top) ;return OK;}7、初始化队列/* 函数功能：初始化队列参数：队列（LinkQueue &Q）成功返回1，否则返回0 */int InitQueue(LinkQueue &Q){Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));//申请结点的内存if(!Q.front) //判断有无申请到空间return ERROR; //没有返回0Q.front ->next = NULL;return OK;}8.在队列队尾插入元素/* 函数功能：在队列队尾插入元素参数：队列（LinkQueue &Q），插入元素e成功返回1，否则返回0 */ int EnQueue(LinkQueue &Q, QElemType e){p = (QueuePtr)malloc(sizeof(QNode)); //申请新的结点if(!p)return ERROR;p -> data = e;p -> next = NULL;Q.rear -> next = P;Q.rear = p;return OK;}9.删除队头元素/* 函数功能：删除对头元素参数：队列（LinkQueue &Q），记录值e成功返回1，否则返回0 */ int DeQueue(LinkQueue &Q, QElemType &e){if(Q.front == Q.rear) //判断队列是否为空return ERROR;p = Q.front -> next;e = p -> data;Q.front -> next = p -> next;if(Q.rear == p)Q.rear = Q.front;free(p);return OK;}10、主函数int main(){SqStack S; //声明一个栈LinkQueue Q; //声明一个队列char m,k,c;int n=0,i,j,t=0,z=0;while(!t){cout << "请输入你要判断回文的字符串，输入@结束：";InitQueue (Q);InitStack (S);while((c=getchar())!='@')//对字符的判断不断输入字符{EnQueue (Q,c);Push (S,c);n++;}for( j=1;j<=n;j++){OutQueue (Q,m);Pop (S,k);if(m!=k)break;}if(j>n) //如果j > n则说明全部相等cout << "这个字符串不是回文字符串" << endl;elsecout << "这个字符串是回文字符串" << endl;}return 0;}说明：通过调用序列号不同的函数进行各种操作。

实验二栈和队列其应用题目：利用栈的深度优化进行迷宫求解一、需求分析1、进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。

2、掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。

3、掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。

1、使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。

2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。

3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。

栈和队列其应用目的在于使读者深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对这两种结构的构造方法的掌握，接触较复杂问题的递归算法设计。

（1）：算术表达式转波兰表达式和逆波兰表达式（2）：栈列操作的验证（建栈、入栈、出栈、销毁栈）（3）：判断表达式中括弧是否正确配对（4）：队列元素倒置（5）：判断字符串是否回文（6）：字符串的基本操作（5个基本函数实现）二、概要设计栈和队列及其应用目的在于使读者深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对这两种结构的构造方法的掌握，接触较复杂问题的递归算法设计ADT Stack 的表示和实现#include<malloc.h>#define STACK_INIT_SIZE 30#define STACKINCREMENT 5typedef struct {char * base;char* top;int stacksize;}sqstack;void InitStack(sqstack &s) {s.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));// if(!s.base) exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;}void push(sqstack &s,char &c) {if(s.top-s.base>=s.stacksize) {s.base=(char *) realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char));// if(!s.base) exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=c;}void pop(sqstack &s,char &c){if(!(s.top==s.base))c=*--s.top;int stackEmpty(sqstack s){if(s.base==s.top) return(1);return(0);}算术表达式转波兰表达式和逆波兰表达式#include <stdio.h>#include <ctype.h>void transform(char *str,int a[][2],int *n) {int i;*n=1;a[0][0]=1;a[0][1]='(';for (i=0;str[i];){if (isdigit(str[i])){a[*n][0]=0;a[*n][1]=0;while (isdigit(str[i])){a[*n][1]=a[*n][1]*10+str[i]-'0';i++;}}else{if (str[i]=='(') a[*n][0]=1;else if (str[i]==')') a[*n][0]=2;else if (str[i]=='*') a[*n][0]=3;else if (str[i]=='/') a[*n][0]=4;else if (str[i]=='+' || str[i]=='-'){if (i==0 || (!isdigit(str[i-1]) && str[i-1]!=')'))a[*n][0]=0;a[*n][1]=0;(*n)++;}if (str[i]=='+') a[*n][0]=5;else a[*n][0]=6;}a[*n][1]=str[i];i++;}(*n)++;}a[*n][0]=2;a[*n][1]=')';(*n)++;}void poland(int a[][2],int n,int p[][2],int *m) { int i;int stack[1000];//转化所用的栈int depth;//栈的深度depth=0;*m=0;for (i=0;i<n;i++){if (a[i][0]==0) stack[depth++]=i;else if (a[i][0]==1) stack[depth++]=i;else if (a[i][0]==2){while (a[stack[depth-1]][0]!=1){depth--;p[*m][0]=a[stack[depth]][0];p[*m][1]=a[stack[depth]][1];(*m)++;}depth--;}else if (a[i][0]==3 || a[i][0]==4){while (a[stack[depth-1]][0]==0 || a[stack[depth-1]][0]==3 || a[stack[depth-1]][0]==4){depth--;p[*m][0]=a[stack[depth]][0];p[*m][1]=a[stack[depth]][1];(*m)++;}stack[depth++]=i;}else if (a[i][0]==5 || a[i][0]==6){while (a[stack[depth-1]][0]!=1){depth--;p[*m][0]=a[stack[depth]][0];p[*m][1]=a[stack[depth]][1];(*m)++;}stack[depth++]=i;}}}void print_poland(int p[][2],int m) {int i;for (i=0;i<m;i++){if (p[i][0]==0) printf("%d",p[i][1]);else printf("%c",p[i][1]);}putchar('\n');}double evaluate(int p[][2],int m) {double stack[1000];//求值所用的栈int depth;//栈的深度int i;depth=0;for (i=0;i<m;i++){if (p[i][0]==0) stack[depth++]=p[i][1];else{double a,b;b=stack[--depth];a=stack[--depth];if (p[i][0]==3) stack[depth++]=a*b;else if (p[i][0]==4) stack[depth++]=a/b;else if (p[i][0]==5) stack[depth++]=a+b;else stack[depth++]=a-b;}}return stack[0];}int a[1000][2];int n;int p[1000][2];int m;main(){printf("5*(8-2)+9\n");transform("5*(8-2)+9",a,&n);poland(a,n,p,&m);print_poland(p,m);printf("The result of the expression is %lf\n",evaluate(p,m)); return;}判断表达式中括弧是否正确配对#include<iostream.h>#include"sqstack.h"void cmp(sqstack &s,char y,int &state1,int &state2){char x;pop(s,x); //cout<<x;if(s.top==s.base) state1=0;if(x==y) state2=1;else if(x!=y) state2=0;}void main() {sqstack s;InitStack(s);int state1=1,state2;int j=0,flag=1;char n,d[15];for(int i=0;i<15&& state1;i++) {cin>>n;if(int(n)==19) { flag=0;break;}else d[i]=n;char c=d[i];switch(c){case'<': push(s,c);break;case'{': push(s,c);break;case'[': push(s,c);break;case'(': push(s,c);break;case'>': cmp(s,'<',state1,state2); break;case'}': cmp(s,'{',state1,state2); break;case')': cmp(s,'(',state1,state2); break;case']': cmp(s,'[',state1,state2); break;}}if(state2==1) cout<<"good match\n";else cout<<"error match\n";}判断字符串是否回文#include<iostream.h>#include<string.h>#include"qnode.h"#include"sqstack.h"int n=0;void scan(linkqueue &q,sqstack &s){ char k;cin>>k;while(k!='#'){enqueue(q,k);push(s,k);cin>>k;n=n+1;}}void ko(linkqueue &q,sqstack &s){ char c,d;int a,i=1;for(n;n>0;n--){a=daqueue(q,c);pop(s,d);if(c!=d) i=0;}if(i==0) cout<<"no"<<endl;else cout<<"yes"<<endl;}void main(){linkqueue q;sqstack s;initqueue(q);initstack(s);scan(q,s);ko(q,s);}字符串的基本操作#include<stdio.h>#include <string.h>void main (){char s[200];char left[200],right[200];int L,i,j;int N,m=0;char cc[2];printf("Please enter the string\n");fgets(s,199,stdin);L = strlen(s);printf("string L=%d\n",L);printf("Please enter N \n");scanf("%d",&N);if (N < L){strncpy(left,s,N); left[N]='\0';strncpy(right, &s[L-N-1],N); right[N]='\0';printf("left: %s\n",left);printf("right: %s\n",right);} else {printf("left,right: %s\n",s);}printf("Please enter begin location m and N\n");scanf("%d %d",&m,&N);if (m>L) m=0;strncpy(right, &s[m],N); right[N]='\0';printf("mid: %s\n",right);printf("enter a letter:\n");scanf("%s",&cc[0]);printf("Locations: ");for (i=0;i<L;i++) if (s[i]==cc[0]) printf("%d ",i+1);printf("\n");for(i=L-1;i>=0;i--) printf("%c",s[i]);printf("\n");for (i=0;i<L;i++) if (s[i] >= 'a' && s[i] <= 'z') s[i]=s[i]-'a'+'A'; printf("%s\n",s);}栈列操作的验证#include <iostream.h>#include <stdlib.h>typedef int priority;typedef int Status;#define TRUE 1;#define FALSE 0;typedef char elemtype;/*栈元素类型,用链表连接*/ typedef struct node{elemtype chdata;struct node *next;}*pnode;/*定义栈*/typedef struct stack{pnode top;int length;}chstack;/*初始化栈*/void InitStack(stack &s){s.top=NULL; s.length=0;}/*栈不为空,出*/Status Push(stack &s,elemtype e){pnode tem;tem=new node;if(!tem)return FALSE;tem->chdata=e;tem->next=s.top;s.top=tem;s.length++;return TRUE;}/*栈不为空,入*/Status Pop(stack &s,elemtype &e){pnode del;e=s.top->chdata;del=s.top;s.top=s.top->next;delete del;s.length--;return TRUE;}/*做第一个'#'*/void Fstack(stack &s){elemtype e;e='#';if(!Push(s,e))exit(0);}/*取得栈顶元素,e带回*/bool Gettop(stack &s,elemtype &e){ if(s.length>=1) {e=s.top->chdata;return true;} return false;}/*定义优先级,返回*/priority chpri(char e){switch (e) {case '(': return 0;case ')': return 0; case '+': return 1;case '-': return 1;case '*': return 2;case '#': return -1;case '/': return 2;}}bool IsOperator(char e){switch (e) {case '(': break;case ')': break;case '+': break;case '-': break;case '*': break;case '/': break;default: return false;} return true;}/*返回a>=b为真*/bool PriCom(char a,char b){int ai;int bi;ai=chpri(a);bi=chpri(b);return (ai>=bi? true:false);}/*不包括空格,主要转换部分*/void conver(char suff[],char chconver[]){ stack s;char *p;char *psuff;char stacktop;char stackout;InitStack(s);Fstack(s);psuff=suff;p=chconver;while(p!='\0') {if(!IsOperator(*p))*psuff++=*p;else {switch (*p){ case'(': Push(s,*p); break;case')': do{ Gettop(s,stackout);*psuff++=stackout;}while(stacktop!='(');Gettop(s,stackout);*psuff++=stackout;break;default: Gettop(s,stacktop);if( PriCom(*p,stacktop ) )Push(s,*p);while( !PriCom(*p,stacktop) ){ Pop(s,stackout);*psuff++=stackout; }Push(s,*p);}//endswitch}//endelsep++; }//endwhilewhile(stackout!='#') {Gettop(s,stackout);*psuff++=stackout;}}三、详细设计任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；#include <iostream>#include <fstream>#include <conio.h>using namespace std;struct step //定义一个栈{int x,y,n; //x，y表示步子坐标，n表示步数};void change(char **maze,int hang,int lie){for(int i=0;i<hang+2;i++){for(int j=0;j<lie+2;j++)switch(maze[i][j]){case '1': maze[i][j]='#';break;case '+':case '0':case '.': maze[i][j]=' ';break;}}}void step_to_step(char **maze,step *Step,int hang,int lie,int n){ //单步输出for(int k=0;k<=n;k++){for(int i=0;i<hang+2;i++){for(int j=0;j<lie+2;j++){if(Step[k].x==i&&Step[k].y==j)cout<<"."<<" ";else cout<<maze[i][j]<<" ";}cout<<endl;}cout<<"这是第"<<k+1<<"步"<<endl<<endl;getch();}}void out(char **maze,int hang,int lie,int i,int j) //输出所走的路程{if(i==1&&j==1) //若回到原点则表明无出路{cout<<endl;cout<<"************************************************************" <<endl;cout<<"|-------------此迷宫没有出路，所走路线如下图---------------|"<<endl;cout<<"************************************************************" <<endl;}else //否则有出路{cout<<endl;cout<<"************************************************************" <<endl;cout<<"|----------------找到迷宫出路，如图所示--------------------|"<<endl;cout<<"************************************************************" <<endl;}for(i=0;i<hang+2;i++) //输出步子{for(j=0;j<lie+2;j++)cout<<maze[i][j]<<" ";cout<<endl;}}void cure(char **maze,int hang,int lie){int i=1,j=0,n=-1;char Q;step *Step; //定义一个存储路程的栈Step=new step [hang*lie]; //事先给其分配一定的空间，[hang*lie]表示空间足够if(maze[1][1]=='1'){cout<<"555..我进不去!!!"<<endl<<endl;getch();exit(0);}else while(maze[hang][lie]!='.') //由右、下、左、上的顺序判断是否走通{ //'1'表示走不通，'+'表示已经走过但不通又回来的步子，'.'表示已经走过并通了的步子if(maze[i][j+1]!='1'&&maze[i][j+1]!='.'&&maze[i][j+1]!='+'){if(i==1&&j==0){cout<<"入口"<<endl;}elsecout<<"右"<<endl;maze[i][j+1]='.';j=j+1;n++;Step[n].x=i;Step[n].y=j;cout<<i<<","<<j;}else if(maze[i+1][j]!='1'&&maze[i+1][j]!='.'&&maze[i+1][j]!='+'){cout<<"下"<<endl;maze[i+1][j]='.';i=i+1;n++;Step[n].x=i;Step[n].y=j;cout<<i<<","<<j;}else if(maze[i][j-1]!='1'&&maze[i][j-1]!='.'&&maze[i][j-1]!='+'){cout<<"左"<<endl;maze[i][j-1]='.';j=j-1;n++;Step[n].x=i;Step[n].y=j;cout<<i<<","<<j;}else if(maze[i-1][j]!='1'&&maze[i-1][j]!='.'&&maze[i-1][j]!='+') {cout<<"上"<<endl;maze[i-1][j]='.';i=i-1;n++;Step[n].x=i;Step[n].y=j;cout<<i<<","<<j;}else //若走不通则返回上一步{if(i==1&&j==1) //当回到入口时，说明无通路，结束循环break;else{maze[i][j]='+'; //将走不通的点置为+n--;i=Step[n].x; //返回上一个点j=Step[n].y;cout<<"返回"<<endl<<i<<","<<j; //输出返回信息}}if(i==hang&&j==lie)cout<<"(出口)"<<" "<<"(共"<<n+1<<"步"<<")";}out(maze,hang,lie,i,j);cout<<endl<<endl<<endl;cout<<"是否单步输出(y/n):";cin>>Q;cout<<endl<<endl;if(Q=='y'){change(maze,hang,lie);step_to_step(maze,Step,hang,lie,n);}}int main(){char **maze; //定义一个迷宫，空间可动态int hang,lie,i,j;char Q;cout<<"希望手动输入还是文件读入(s:手动输入,w:文件读入):";cin>>Q;cout<<endl<<endl;if(Q=='s'){cout<<"请输入矩阵的行列"<<endl;cout<<"行数:";cin>>hang;cout<<"列数:";cin>>lie;cout<<endl;maze=new char *[hang+2]; //分配连续空间给迷宫for(i=0;i<hang+2;i++)maze[i]=new char [lie+2];cout<<"请输入迷宫，0表示通路，1表示墙"<<endl;for(i=1;i<=hang;i++)for(j=1;j<=lie;j++)cin>>maze[i][j];}else if(Q=='w'){ifstream infile("F:\\migong.txt",ios::in); //可用文件外部输入infile>>hang;infile>>lie;maze=new char *[hang+2]; //分配连续空间给迷宫for(i=0;i<hang+2;i++)maze[i]=new char [lie+2];for(i=1;i<=hang;i++)for(j=1;j<=lie;j++)infile>>maze[i][j];cout<<"文件读取成功！"<<endl;}for(i=0;i<hang+2;i++) maze[i][0]='1';for(i=0;i<lie+2;i++) maze[0][i]='1';for(i=0;i<lie+2;i++) maze[hang+1][i]='1';for(i=0;i<hang+2;i++) maze[i][lie+1]='1';cout<<endl<<endl;cout<<"********************您输入的迷宫为******************************"<<endl;cout<<"行数："<<hang<<" "<<"列数："<<lie;cout<<" "<<"入口："<<"1,1"<<" "<<"出口："<<hang<<","<<lie<<endl;for(i=0;i<hang+2;i++){for(j=0;j<lie+2;j++)cout<<maze[i][j]<<" ";cout<<endl;}cout<<endl<<endl<<"所走的步骤如下:"<<endl;cure(maze,hang,lie);cout<<endl<<endl<<endl; getch();return 0;}四、运行结果图1运行程序，可以选择输入迷宫的方式：有手动输入和文件输入两种方法可供选择。

2007级数据结构实验报告实验名称：实验二栈和队列日期：2008年11月15日1．实验要求实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力实验内容2.1题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。

要求：1、实现一个共享栈2、实现一个链栈3、实现一个循环队列4、实现一个链队列编写测试main()函数测试线性表的正确性。

2. 程序分析2.1 存储结构存储结构：特殊线性表：栈，队列栈顶 栈底 链栈2.2 关键算法分析共享栈的入栈算法伪码（Push ）： 1．如果栈满，抛出上溢异常。

2．判断是插在栈1还是栈2：2.1如果在栈1插入，则栈顶指针top1加1，在top1处填入元素x ； 2.2如果在栈2插入，则栈顶指针top2加1，在top2处填入元素x 。

共享栈的出栈算法伪码（Pop ）：1. 判断是在栈1删除还是在栈2删除。

2. 若是在栈1删除，则2.1 若栈1为空栈，抛出下溢异常； 2.2 删除并返回栈1的栈顶元素；3. 若是在栈2删除，则3.1 若栈2为空栈，抛出下溢异常； 3.2 删除并返回栈2的栈顶元素。

非空链队列 空链队列共享栈的取栈顶元素算法伪码（GetTop）：1．判断是在栈1取还是栈2取；2．如果在栈1取，则2.1 若栈1不空，返回栈顶元素的值，不删除；2.2 若栈1空，返回0；3．如果在栈2取，则3.1 若栈2不空，返回栈顶元素的值，不删除；3.2 若栈2空，返回0。

链栈的入栈算法伪码（Push）：1．申请一个新的结点，数据域为x；2．将新结点插在栈顶；3．栈顶指针重新指向栈顶元素。

链栈的出栈算法伪码（Pop）：1．如果栈空，抛出下溢异常；2．暂存栈顶元素；3．将栈顶结点摘链；4．删除该结点，返回该元素的值。

链栈的取栈顶元素算法的伪码（GetTop）：1．如果栈非空，返回栈顶元素的值，不删除。

数据结构实验二——算术表达式求值实验报告算术表达式求值实验报告一、引言算术表达式求值是计算机科学中一个重要的基础问题，它涉及到了数据结构和算法的应用。

本实验旨在通过实现一个算术表达式求值的程序，加深对数据结构中栈的理解和应用，并掌握算术表达式的求值过程。

二、实验目的1. 理解算术表达式的基本概念和求值过程；2. 掌握栈的基本操作和应用；3. 实现一个能够正确求解算术表达式的程序；4. 进一步熟悉编程语言的使用。

三、实验内容1. 设计并实现一个栈的数据结构；2. 实现算术表达式求值的算法；3. 编写测试用例，验证程序的正确性；4. 进行性能测试，分析算法的时间复杂度。

四、实验方法与步骤1. 设计栈的数据结构在本实验中，我们选择使用数组来实现栈的数据结构。

栈的基本操作包括入栈（push）、出栈（pop）、判断栈空（isEmpty）和获取栈顶元素（top）等。

2. 算术表达式求值算法算术表达式求值的一种常用算法是通过后缀表达式进行求值。

具体步骤如下： - 将中缀表达式转换为后缀表达式；- 通过栈来求解后缀表达式；- 返回最终的计算结果。

3. 编写测试用例编写一系列测试用例，包括不同类型的算术表达式，以验证程序的正确性。

例如：- 简单的四则运算表达式：2 + 3 * 4 - 5；- 包含括号的表达式：(2 + 3) * (4 - 5)；- 包含多位数的表达式：12 + 34 * 56；- 包含浮点数的表达式：3.14 + 2.71828。

4. 性能测试和时间复杂度分析针对不同规模的输入数据，进行性能测试，记录程序的运行时间。

同时，分析算法的时间复杂度，验证算法的效率。

五、实验结果与分析我们设计并实现了一个栈的数据结构，并成功地完成了算术表达式求值的程序。

通过对一系列测试用例的验证，我们发现程序能够正确地求解各种类型的算术表达式，并返回正确的计算结果。

在性能测试中，我们对不同规模的输入数据进行了测试，并记录了程序的运行时间。

实验二栈与队列的基本操作与实现一、实验目的：利用高级程序设计语言来实现抽象数据类型栈与队列，进一步熟悉其表示和实现方法，用已经实现的操作来组合新的操作，为以后的利用栈和队列分析和解决问题打下基础。

1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。

2、掌握栈和队列的特点，即后进先出和先进先出的原则。

3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。

二、实验要求：1、定义栈的抽象数据类型，并用顺序栈或链栈实现其基本操作：初始化，判断栈空、栈满，出栈、入栈，取栈顶元素等2、定义队列的抽象数据类型，构造循环队列实现其基本操作：初始化，判断队空、队满，出队、入队等3、编写和调试完成程序4、保存和打印程序的运行结果三、测试数据字符的序列为ABCDEFG执行进出栈的次序为：XXYXXYYXXXY（其中X表示进栈，Y表示出栈）栈中的元素为：AEF执行进出队的次序为：XXYXXYYXXXY（其中X表示进队，Y表示出队）栈中的元素为：EFG四、实现提示：1、栈与队列可以用数组进行存储，并定义为全局变量，以减少函数调用时参数的传递。

（即在函数体外面定义变量，全局变量可以为本文件中其他函数所共用，其有效范围为从定义变量的位置开始到本源文件结束）栈：#define MAXN 26char stack[MAXN];int top=0;队列：#define MAXN 26char q[MAXN];int head = 0, tail = 0;2、主控函数示例：void main(){int n,x1,x2,select;char x,y;printf("input a stack length(1<=n<=26)):\n");scanf("%d",&n);printf("select 1:Display()\n");//显示栈中的元素printf("select 2:Push()\n");//进栈printf("select 3:Pop()\n");//出栈printf("select 4:StackTop()\n");//取出栈顶的元素，但并不出栈printf("select 0:exit\n");//退出printf("input a your select(0-4):\n");scanf("%d",&select);while(select!=0){switch(select){ case 1: Display();break;case 2: printf("input a push a value:\n");scanf("%c",&x);scanf("%c",&y);Push(x);break;case 3: x1=Pop();printf("x1->%d\n",x1);break;case 4: x2=StackTop();printf("x2->%d",x2);break;}printf("select 1:Display()\n");printf("select 2:Push()\n");printf("select 3:Pop()\n");printf("select 4:StackTop()\n");printf("select 0:exit");printf("input a your select(0-4):\n");scanf("%d",&select);}}3、队列基本操作的实现与栈类似，可以分开写，也可以写在一个主函数中。

一、实验名称：栈和队列的应用
二、实验目的和要求：
1．掌握栈和队列的概念和特点
2．掌握栈和队列在顺序和链式存储结构下的插入、删除算法
3．认真分析项目实例中的内容，将相关程序在计算机上运行实现
三、上机实验内容一：表达式求值问题
1．求一个数学表达式的值：用户输入一个包含正整数、括号和四则运算符（“+”、“—”、“*”、“/”）的算术表达式，计算其结果。

2．设计分析
首先置操作数栈为空栈，表达式起始符“#”为运算符栈底元素；依次读入表达式中每个字符，若是操数则进操作数栈，若是操作符则和操作符栈顶的运算符进行比较优先权后作相应的操作，直到整个表达式求值完毕（即操作符栈顶元素和当前读入的字符均为“#”）
3．结点结构类型描述如下
typedef struct
{
char *base,*top;
int stacksize;
}sqstack;
四、上机实验内容二：迷宫求解问题
1.迷宫是一个m行n列的矩阵，其中0表示无障碍，1表示有障碍。

设入口为（1，1），出口为（m,n），即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直到出口为止。

2.迷宫的功能
要求随机生成一个m行n列的矩阵，为了操作方便可以在矩阵外围生成一圏障碍，设置东南西北四个方向，采用链栈进行操作。

最后迷宫如不是通路给出
“此迷宫元解”，如是通路要求输出所走过的路径。

3．结点结构类型描述如下
typedef struct node
{ int row;
int col;
struct node *next;
};。

实验二：栈与队列的应用学时：4学时实验目的：掌握栈与队列的基本结构和操作方法，并能利用其解决实际问题。

实验内容： (任选一题，有能力的同学可以两题都做)一、输入一个表达式(4+2*4#),利用栈求表达式的值。

（只对整数求值，目前只考虑操作数为个位数的情况，即24+34*34这种情况不考虑）提示：1，先实现栈的基本操作：初始化，入栈，出栈等。

2，首先将一个中缀式变成后缀式，然后，对后缀式求值。

3，可用顺序栈或者链栈实现。

二、编写一个程序，反映病人到医院看病排队看医生的情况，在病人排队过程中，主要重复两件事：（1）病人到达诊室，将病历交给护士，排到等待队列中侯诊（2）护士从等待队列中取出下一位病人的病历，改病人进入诊室就诊要求：模拟病人等待就诊这一过程，程序采用菜单式，其选项和功能说明如下：（1）排队——输入排队病人的病历号，加入到病人排队队列中（2）就诊——病人排队队列中最前面的病人就诊，将其从队列中删除（3）查看排队——从队首到队尾理出所有的排队病人的病历号（4）不在排队，余下依次就诊——从队首到队尾列出所有的排队病人的病历号，并退出运行（5）下班——退出运行（6）上班——初始化排队队列。

提示：1，先实现队列的基本操作：初始化，入队，出队等。

2，在main（）程序中，模拟病人看病这个过程。

给出菜单选择，进行相应的操作3，可用顺序队列或者链队列实现。

可参考如下代码：顺序栈的实现ch32_sstack.c#include "stdio.h"#define StackSize 100typedef int ElemType;typedef struct {ElemType elem[StackSize];int top;}SqStack;InitStack(SqStack *pS){pS->top=0; /* top指向栈顶的上一个元素*/}int Push(SqStack *pS,ElemType e){if (pS->top==StackSize-1) /* 栈满*/return 0;pS->elem[pS->top]=e;pS->top=pS->top+1;return 1;}int Pop(SqStack *pS,ElemType* pe){if (pS->top==0) /* 栈空*/return 0;pS->top = pS->top - 1;*pe = pS->elem[pS->top];return 1;}main(){SqStack S;ElemType e;int N;InitStack(&S);N=1348;while(N){e = N % 8;Push(&S,e);N = N/8;}while(Pop(&S,&e)){printf("%d",e);}getch();}链栈的实现ch3_lstack.c #include "stdio.h"/* 数据元素的类型*/typedef int ElemType;/* 节点的类型（包括头节点）*/typedef struct Node{ElemType elem;struct Node *next;}SNode;/* 初始化，头节点*/InitStack(SNode* pS){pS->next=NULL;}/* 入栈：在头节点之后插入一个新节点*/Push(SNode* pS,ElemType e){SNode* node;node = (SNode*)malloc(sizeof(SNode));node->elem = e;node->next = pS->next;pS->next = node;}int Pop(SNode* pS,ElemType* pe){SNode* node;if (pS->next==NULL){return 0;}*pe = pS->next->elem;node=pS->next;pS->next=node->next;free(node);return 1;}main(){SNode S; ElemType e;int N;InitStack(&S);N=1348;while(N){e = N % 8;Push(&S,e);N = N/8;}while(Pop(&S,&e)){printf("%d",e);}getch();}队列的顺序实现（循环队列）ch3_squeue.c/*队列的顺序实现（循环队列）author: Shirleydate: 2011.3*/#define MaxSize 100typedef int ElemType;typedef struct {ElemType elem[MaxSize];int front,rear;}SqQueue;InitQueue(SqQueue* pQ){pQ->front=pQ->rear=0;}int EnQueue(SqQueue* pQ,ElemType e){if ((pQ->rear+1)%MaxSize == pQ->front) /* 队满*/ return 0;pQ->elem[pQ->rear] = e;pQ->rear = (pQ->rear+1)%MaxSize;return 1;}int DeQueue(SqQueue* pQ,ElemType* pe){if (pQ->rear == pQ->front) /* 队空*/return 0;*pe = pQ->elem[pQ->front];pQ->front = (pQ->front+1)%MaxSize;return 1;}main(){SqQueue Q;ElemType e;InitQueue(&Q);e=2;EnQueue(&Q,e);e=5;EnQueue(&Q,e);e=3;EnQueue(&Q,e);while(DeQueue(&Q,&e)){printf("\n%d",e);}getch();}队列的链式实现ch3_lqueue.c /*队列的链式实现author: Shirleydate: 2011.3*/#include "stdio.h"#define MaxSize 100typedef int ElemType;typedef struct QNode{ElemType elem;struct QNode * next;}QNode;typedef struct {QNode* front;QNode* rear;}LinkQueue;InitQueue(LinkQueue* pQ){QNode* node;node=(QNode*)malloc(sizeof(QNode)); /*分配一个头节点*/ node->next = NULL;pQ->front=pQ->rear=node;}int EnQueue(LinkQueue* pQ,ElemType e){QNode* node;node=(QNode*)malloc(sizeof(QNode));node->elem = e;node->next = NULL;pQ->rear->next = node;pQ->rear = node;return 1;}int DeQueue(LinkQueue* pQ,ElemType* pe){QNode* node;if (pQ->rear == pQ->front) /* 队空*/return 0;node = pQ->front->next;*pe = node->elem;pQ->front->next = node->next;/* 注意有个头节点，当最后一个元素出队时，记得更新尾指针*/ if (pQ->rear==node)pQ->rear=pQ->front;free(node);return 1;}DestoryQueue(LinkQueue* pQ){while(pQ->front){pQ->rear=pQ->front->next;free(pQ->front);pQ->front = pQ->rear;}}main(){LinkQueue Q;ElemType e;InitQueue(&Q);e=2;EnQueue(&Q,e);e=5;EnQueue(&Q,e);e=3;EnQueue(&Q,e);while(DeQueue(&Q,&e)){printf("\n%d",e);}DestoryQueue(&Q);getch();}。

实验报告
算法描述：可以用自然语言、伪代码或流程图等方式
将十进制数N转换为r进制得数，其转换方法采用逐次除以基数r取余法，直至商等于0为止。

采用这种方法，转换所得的r禁制数将按低位到高位的顺序产生，而通常数的输出形式是从高位到低位进行的，恰好与计算机过程相反，因此过程转换过程中每得到以为r进制数则进栈保存，转换完毕后依次出栈，这样正好是转换结果。

算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等
2．算术表达式求值算法
数据结构定义
采用栈作为数据结构进行设计。

算法设计思路简介
本程序主要分为六个模块（主要算法模块图见图1.1）：栈的顺序存储模块、进栈模块、出栈模块、运算模块、判断优先级模块、处理表达式主体模块。

栈的顺序存储模块：分别建立两个栈，第一个用来存储运算符，第二个是用来存储数字。

算法描述：可以用自然语言、伪代码或流程图等方式
算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等。

文档根源为 :从网络采集整理.word 版本可编写 .支持.实验二栈和行列及其应用一、实验目的1.掌握栈和行列这两种抽象数据种类的特色，并能在相应的应用问题中正确采用它们。

2.娴熟掌握栈种类的两种实现方法。

3.娴熟掌握循环行列和链行列的基本操作实现算法。

二、实验内容用行列求解迷宫问题[ 问题描绘 ]以一个 M*N的长方阵表示迷宫， 0 和 1 分别表示迷宫中的通路和墙壁。

设计一个程序，对随意设定的迷宫，求出一条从进口到出口的通路，或得出没有通路的结论。

[ 基本要求 ]实现一个以次序储存构造的行列种类，而后编写一个求解迷宫的非递归途序。

求得的通路以三元组（ i ，j ，pre）的形式输出，此中：（ i， j）指示迷宫中的一个坐标，pre 表示本路径中上一个方块在行列中的下标。

[ 测试数据 ]由学生随意指定。

三、源代码# include <stdio.h>#define M 5// 行数#define N 5// 列数#define MaxSize 100// 队最多元素个数int mg[M+2][N+2]={// 一个迷宫 , 其周围要加上均为 1 的外框 {1,1, {1,1,1,1,1,1,1},{1,0,0,0,0,0,1},{1,0,1,0,0,1,1},文档根源为 :从网络采集整理.word 版本可编写 .支持.{1,0,1,0,0,1,1},{1,0,1,0,1,0,1},{1,0,0,0,0,0,1},{1,1,1,1,1,1,1}};typedef struct{int i,j;int pre;}Box;typedef struct{Box data[MaxSize];int front, rear;}QuType;void mgpath1(int xi,int yi,int xe,int ye) // 搜寻路径为：（ xi ，yi ） ->(xe,ye){void print (QuType qu, int front );int i,j,find=0,di;QuType qu;//定义次序队qu.front=qu.rear=-1;qu.rear++;qu.data[qu.rear].i=xi; //(xi,yi)进队qu.data[qu.rear].j=yi;qu.data[qu.rear].pre=-1;mg[xi][yi]=-1;while(qu.front!=qu.rear&&!find){qu.front++;i=qu.data[qu.front].i;j=qu.data[qu.front].j;if(i==xe&&j==ye){find=1;print(qu,qu.front);}for(di=0;di<4;di++){switch(di){case0:i=qu.data[qu.front].i-1;j=qu.data[qu.front].j;break;case1:i=qu.data[qu.front].i;j=qu.data[qu.front].j+1;break;case2:i=qu.data[qu.front].i+1;j=qu.data[qu.front].j+1;break;case3:i=qu.data[qu.front].i;j=qu.data[qu.front].j-1;break;}if(mg[i][j]==0){find=1;qu.rear++;qu.data[qu.rear].i=i; qu.data[qu.rear].j=j;qu.data[qu.rear].pre=qu.front;mg[i][j]=-1;}}}}void print (QuType qu, int front ){int k=front,j,ns=0;printf("\n");do{j=k;k=qu.data[k].pre;qu.data[j].pre=-1;}while (k!=0);printf(" 迷宫路径以下： \n");k=0;while(k<MaxSize){if(qu.data[k].pre==-1){ns++;printf("\t(%d,%d)",qu.data[k].i,qu.data[k].j);if(ns%5==0)printf("\n");}k++;}printf("\n");}void main(){ mgpath1(1,1,M,N);printf("迷宫全部路径以下 :\n");}四、测试结果：五、心得领会做实验第一要掌握大批的理论知识，而后仔细去达成实验。