实验编号：3四川师大《数据结构》实验报告2016年10月29日实验三栈和队列及其应用_一．实验目的及要求（1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们；（2）本实验训练的要点是“栈”的观点及其典型用法；（3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。

二．实验内容（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）；（2）应用栈的基本操作，实现数制转换（任意进制）；（3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）；（4）利用栈实现任一个表达式中的语法检查（括号的匹配）。

（5）利用栈实现表达式的求值。

注：（1）～（3）必做，（4）～（5）选做。

三．主要仪器设备及软件（1）PC机（2）Dev C++ ,Visual C++, VS2010等四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）；A.顺序储存：➢代码部分：//Main.cpp:#include"SStack.h"int main(){SqStack S;SElemType e;int elect=1;InitStack(S);cout << "已经创建一个存放字符型的栈" << endl;while (elect){Muse();cin >> elect;cout << endl;switch (elect){case 1:cout << "input data:";cin >> e;Push(S, e);break;case 2:if(Pop(S, e)){cout << e <<" is pop"<< endl; }else{cout<<"blank"<<endl;}break;case 3:if (StackEmpty(S)){cout << "栈空" << endl;}else{cout << "栈未空" << endl;}break;case 4:GetTop(S, e);cout << "e is " << e << endl;break;case 5:StackLength(S);break;case 0:break;}}DestroyStack(S);return OK;}//SStack.cpp:#include"SStack.h"//输出菜单void Muse(){cout << "请选择功能：" << endl;cout << " 1.入栈" << endl;cout << " 2.出栈" << endl;cout << " 3.判栈空" << endl;cout << " 4.返回栈顶部数据" << endl;cout << " 5.栈长" << endl;cout << " 0.退出系统" << endl;cout << "你的选择是：" ;}//创建栈Status InitStack(SqStack &S){S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));if (!S.base) exit(ERROR);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}//得到顶部数据Status GetTop(SqStack S, SElemType &e){if (S.base == S.top) return ERROR;e = *(S.top - 1);return OK;}//入栈Status Push(SqStack &S, SElemType &e){if (S.top - S.base >= STACK_INIT_SIZE){S.base = (SElemType *)realloc(S.base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(SElemType));if (!S.base) exit(ERROR);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;return OK;}//出栈Status Pop(SqStack &S, SElemType &e) {if (S.base == S.top){return ERROR;}e = *--S.top;cout<<"pop succeed"<<endl;return OK;}//判栈空Status StackEmpty(SqStack S){if (S.top == S.base){return ERROR;}return OK;}//销毁栈Status DestroyStack(SqStack &S){free(S.base);S.top=NULL;S.stacksize = 0;cout << "栈已销毁" << endl;return OK;}int StackLength(SqStack S){cout << "StackLength is "<<S.top-S.base << endl;return OK;}//SStack.h:#include<iostream>#include<stdlib.h>using namespace std;const int STACK_INIT_SIZE = 100;const int STACKINCREMENT = 10;const int ERROR = 0;const int OK = 1;typedef char SElemType;typedef int Status;typedef struct {SElemType *base;SElemType *top;int stacksize;}SqStack;Status InitStack(SqStack &S);//创建顺序存储的栈Status GetTop(SqStack S, SElemType &e);//得到栈顶数据Status Push(SqStack &S, SElemType &e);//入栈Status Pop(SqStack &S, SElemType &e);//出栈void Muse();//输出菜单界面Status StackEmpty(SqStack S);//判断栈是否为空Status DestroyStack(SqStack &S);//销毁栈int StackLength(SqStack S);//计算栈的长度➢运行结果：B. 链式储存：➢代码部分：//Main.cpp#include"Lstack.h"int main(){Lq_Stack L;if(InintStack (L)){cout<<"build stack succeed"<<endl;}else exit (ERROR);int e=0;Menu(L,e);DestroyStack(L);return 0;}//Lstack.cpp#include"Lstack.h"Status InintStack(Lq_Stack &L){//创建栈L=(LqStack *)malloc(sizeof(LqStack));if(!L) exit(ERROR);L->data=0;L->next=NULL;return OK;}Status push (Lq_Stack &L,SElemType e){ //入栈LqStack *p;p=(LqStack *)malloc(sizeof(LqStack));if(!p) exit(ERROR);p->data=e;L->data++;p->next=L->next;L->next=p;return OK;Status pop (Lq_Stack &L,SElemType &e){ //出栈LqStack *p;if(L->next==NULL) return ERROR;p=L->next;e=p->data;L->next=p->next;L->data--;free(p);return OK;}Status GetTop(Lq_Stack L, SElemType &e){ //得到栈顶数据if(L->next==NULL) return ERROR;e=L->next->data;return OK;}Status StackEmpty(Lq_Stack L){//判断栈是否为空if(L->next==NULL){return ERROR;}else return OK;int StackLength(Lq_Stack L){//计算栈的长度return L->data;}Status DestroyStack(Lq_Stack &L){//销毁栈LqStack *p;while(!L){L=p;L=L->next;free(p);}return OK;}void Menu(Lq_Stack &L,SElemType e){//输出菜单选择执行的功能int select=1;while(select){cout<<"————————————"<<endl;cout<<"请选择功能"<<endl;cout<<"——————1.入栈"<<endl;cout<<"——————2.出栈"<<endl;cout<<"——————3.得到顶部数据"<<endl; cout<<"——————4.判断栈是否为空"<<endl; cout<<"——————5.输出栈的长度"<<endl; cout<<"——————0.退出程序"<<endl;cout<<"你的选择是：";cin>>select;switch (select){case 0:break;case 1:cout<<"push data:";cin>>e;if(push(L,e)){cout<<"push succeed"<<endl;}else cout<<"push failed"<<endl;break;case 2:if(pop(L,e)){cout<<"data "<<e<<" is pop"<<endl;}else cout<<"pop failed"<<endl;break;case 3:if(GetTop(L,e)){cout<<"head data "<<e<<" is pop"<<endl;}else cout<<"Get failed"<<endl;break;case 4:if(StackEmpty(L)){cout<<"stack is not NULL"<<endl;}else cout<<"stack is NULL"<<endl;break;case 5:cout<<"this stack length is "<<StackLength(L)<<endl;break;}}}//Lstack.h#include<iostream>#include<stdlib.h>using namespace std;const int OK=1;const int ERROR=0;typedef int SElemType;typedef int Status;typedef struct LqStack{SElemType data;struct LqStack *next;}LqStack,*Lq_Stack;Status InintStack (Lq_Stack &L);//创建栈Status push (Lq_Stack &L,SElemType e);//入栈Status pop (Lq_Stack &L,SElemType &e);//出栈Status GetTop(Lq_Stack L, SElemType &e);//得到栈顶数据Status StackEmpty(Lq_Stack L);//判断栈是否为空int StackLength(Lq_Stack L);//计算栈的长度Status DestroyStack(Lq_Stack &L);//销毁栈void Menu(Lq_Stack &L,SElemType e);//输出菜单选择执行的功能➢运行结果：（2）应用栈的基本操作，实现数制转换（任意进制）；；➢代码部分：//Main.cpp#include"SStack.h"int main(){int number;cout<<"要将数值转换为多少进制";cin>>number;conversion(number);return 0;}SStack.cpp#include"SStack.h"Status InitStack(SStack &S){//创建栈S.dase=(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));if (!S.dase) exit(ERROR);S.top=S.dase;S.stacksize=STACK_INIT_SIZE;return OK;}Status push(SStack &S,ElemType e){//入栈if(S.top-S.dase >= S.stacksize){//栈满追加空间S.dase=(ElemType *)realloc(S.dase,(STACK_INIT_SIZE+STACKINCREMENT) * sizeof(ElemType));if(!S.dase) exit(ERROR);S.top=S.dase+STACK_INIT_SIZE;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}Status pop(SStack &S,ElemType &e){//出栈if(S.top== S.dase) return ERROR;e=*--S.top;return OK;}Status StackEmpty(SStack &S){//判断栈是否为空if(S.dase==S.top) return ERROR;return OK;}void conversion(int number){//转换为e进制并输出SStack S;int N,e;if(InitStack(S)){cout<<"栈创建成功"<<endl;}cout<<"输入待转换的数：";cin>>N;while(N){push(S,N%number);N=N/number;}while(StackEmpty(S)){pop(S,e);cout<<e;}cout<<endl;}//SStack.h#ifndef SSTACK_H#define SSTACK_H#include<iostream>#include<stdlib.h>using namespace std;const int STACK_INIT_SIZE=100; const int STACKINCREMENT=10; const int OK=1;const int ERROR=0;typedef int Status;typedef int ElemType;typedef struct {ElemType *dase;ElemType *top;int stacksize;}SStack;Status InitStack(SStack &S);//创建栈Status push(SStack &S,ElemType e);//入栈Status push(SStack &S,ElemType &e);//出栈Status StackEmpty(SStack &S);//判断栈是否为空void conversion(int number);//转换为number进制并输出#endif➢运行结果：（3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）。