数据结构-实验三-栈和队列及其应用.doc

实验编号：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） 编程实现队列在两种存储结构中得基本操作（队列得初始化、判队列空、入队列、出队列）。
Ø 代码部分：
A:链式储存：
//Main、cpp:
#include"QNode、h"
int main(){
LinkQueue Q;
InitQueue(Q);
Menu(Q);
DestroyQueue(Q);
return 0;
}
//QNode、cpp:
#include"QNode、h"
Status InitQueue(LinkQueue &Q){
//构造空队列
Q、front=Q、rear=(QueuePrt)malloc(sizeof(QNode));
if(!Q、front) exit (ERROR);
Q、front->next=NULL;
return OK;
}
Status DestroyQueue(LinkQueue &Q){
//销毁队列Q
while(Q、front){
Q、rear=Q、front->next;
free(Q、front);
Q、front=Q、rear;
}
return OK;
}
Status EnQueue (LinkQueue &Q,QElemType e){
//插入元素a为Q得新得队尾元素
QNode *p;
p=(QueuePrt)malloc(sizeof(QNode));
if(!p) exit(ERROR);
p->data=e;p->next=NULL;
Q、rear->next=p;
Q、rear=p;
return OK;
}
Status DeQueue (LinkQueue &Q,QElemType &e){
//删除Q得队头元素，用e返回其值
QNode *p;
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;
}
Status QueueEmpty(LinkQueue Q){
//判断对就是否为空
if(Q、front==Q、rear)return ERROR;
return OK;
}
void Menu(LinkQueue &Q){
//输出选择界面
int select=1;
QElemType e;
while(select){
cout<<"--------------------"<<endl;
cout<<"请选择以下功能："<<endl;
cout<<"--------------1,入队"<<endl;
cout<<"--------------2,出队"<<endl;
cout<<"--------------3,判断队空"<<endl;
cout<<"--------------0,退出程序"<<endl;
cout<<"请输入您得选择";
cin>>select;
switch (select){
case 0:break;
case 1:
cout<<"输入入队数据"<<endl;
cin>>e;
if(EnQueue(Q,e)){
cout<<"入队成功"<<endl;
}
break;
case 2:
if(DeQueue(Q,e)){
cout<<e<<"出队"<<endl;
}
break;
case 3:
if(QueueEmpty(Q)) cout<<"此队不为空"<<endl;
else cout<<"此队为空"<<endl;
break;
}
}
}
//QNode、h
#ifndef QNODE_H
#define QNODE_H
#include<iostream>
#include<stdlib、h>
using namespace std;
const int OK=1;
const int ERROR=0;
typedef int QElemType;
typedef int Status;
typedef struct QNode{
QElemType data;
struct QNode * next;
}QNode,*QueuePrt;
typedef struct {
QueuePrt front;
QueuePrt rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q);//构造空队列
Status DestroyQueue(LinkQueue &Q);//销毁队列Q
Status EnQueue (LinkQueue &Q,QElemType e);//插入元素a为Q得新得队尾元素
Status DeQueue (LinkQueue &Q,QElemType &e);//删除Q得队头元素，用e返回其值
Status QueueEmpty(LinkQueue Q);//判断对就是否为空
void Menu(LinkQueue &Q);//输出选择界面
#endif
Ø 运行结果：

B顺序存储:
Ø 代码部分：
//main、cpp:
#include"SqQueue、h"
int main(){
SqQueue Q;
if(InitQueue(Q)){
cout<<"创建队成功"<<endl;
Menu(Q);
DestroyQueue(Q);
}
return 0;
}
//SqQueue、cpp:
#include"SqQueue、h"
Status InitQueue(SqQueue &Q){
//创建空队列
Q、base=(QElemType *)malloc(MAXSIZE * sizeof(QElemType));
if (!Q、base) exit(ERROR);
Q、front=Q、rear=0;
return OK;
}
Status EnQueue(SqQueue &Q,QElemType e){
//插入元素e为Q得新队尾元素
if(((Q、rear+1)% MAXSIZE) == Q、front) return ERROR;
Q、base[Q、rear]=e;
Q、rear=(Q、rear+1)%MAXSIZE;
return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e){
//删除Q得对头元素，用e返回其值。
if(Q、front == Q、rear) return ERROR;
e=Q、base[Q、front];
Q、front=(Q、front+1)%MAXSIZE;
return OK;
}
Status SqQueueEmpty(SqQueue Q){
//判断Q就是否为空
if(Q、front==Q、rear) return ERROR;
return OK;
}
Status DestroyQueue(SqQueue &Q){
//销毁栈
Q、front=Q、rear=0;
free(Q、base);
return OK;
}
void Menu(SqQueue &Q){
//输出选择菜单
int select=1;
QElemType e;
while (select){
cout<<"----------------------------------"<<endl;
cout<<"请选择一下功能:"<<endl;
cout<<" 1，入队"<<endl;
cout<<" 2，出队"<<endl;
cout<<" 3，判断就是否为空"<<endl;
cout<<" 0，退出程序"<<endl;
cout<<"您得选择就是：";
cin>>select;
switch (select){
case 0:break;
case 1:
cout<<"输入插入得数据:";
cin>>e;
if(EnQueue(Q,e)){
cout<<"入队成功"<<endl;
}
else cout<<"队满"<<endl;
break;
case 2:
if(DeQueue(Q,e)){
cout<<e<<"出队"<<endl;
}
else cout<<"队空"<<endl;
break;
case 3:
if(SqQueueEmpty(Q)){
cout<<"队未空"<<endl;
}
else cout<<"队空"<<endl;
break;
}
}
}
//SqQueue、h:
#ifndef SQQUEUE_H
#define SQQUEUE_H
#include<iostream>
#include<stdlib、h>
using namespace std;
const int MAXSIZE=100;
const int MORE=100;
const int OK=1;
const int ERROR=0;
typedef int QElemType;
typedef int Status;
typedef struct{
QElemType *base;
int front ;
int rear;
}SqQueue;
Status InitQueue(SqQueue &Q);//创建空队列
Status EnQueue(SqQueue &Q,QElemType e);//插入元素e为Q得新队尾元素
Status DeQueue(SqQueue &Q,QElemType &e);//删除Q得对头元素，用e返回其值。
Status SqQueueEmpty(SqQueue Q);//判断Q就是否为空
Status DestroyQueue(SqQueue &Q);//销毁栈
void Menu(SqQueue &Q);//输出选择菜单
#endif
Ø 运行结果：

（4） 利用栈实现任一个表达式中得语法检查（括号得匹配）。
Ø 代码部分：
//SqStack、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=0;
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);//出栈
//SqStack、cpp
#include"SqStack、h"
//创建栈
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;
return OK;
}
//main、cpp
#include"SqStack、h"
int main()
{
char c;
SElemType e;
SqStack S;
InitStack(S);
while((c=getchar())!='#')
{
switch(c)
{
case '(':
case '[':
case '{':
Push (S,c);
break;
case ')':
if (S、top==S、base)
{
break;
}
GetTop(S,e);
if (e=='(')
{
Pop(S,e);
}
break;
case ']':
if (S、top==S、base)
{
break;
}
GetTop(S,e);
if (e=='[')
{
Pop(S,e);
}
break;
case '}':
if (S、top==S、base)
{
break;
}
GetTop(S,e);
if (e=='{')
{
Pop(S,e);
}
break;
}
}
if (S、base==S、top)
{
cout<<"括号完全匹配"<<endl;
}
else
{
cout<<"括号不完全匹配"<<endl;
}
return OK;
}
Ø 运行结果：

（5） 利用栈实现表达式得求值。
Ø 代码部分：
//SqStack、h
#include<iostream>
#include<stdlib、h>
using namespace std;
typedef int Status;
typedef char SElemType;
typedef struct SqStack{
SElemType data;
struct SqStack * next;
}SqStack,*LinkStack;
const int OK=1;
const int ERROR=0;
Status