大数据结构实验三栈和队列及其应用.docx
《大数据结构实验三栈和队列及其应用.docx》由会员分享，可在线阅读，更多相关《大数据结构实验三栈和队列及其应用.docx（37页珍藏版）》请在冰点文库上搜索。
大数据结构实验三栈和队列及其应用
实验编号：
3师大《数据结构》实验报告2016年10月29日
实验三栈和队列及其应用_
一．实验目的及要求
（1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们；
（2）本实验训练的要点是“栈”的观点及其典型用法；
（3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。
二．实验容
（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）；
（2）应用栈的基本操作，实现数制转换（任意进制）；
（3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）；
（4）利用栈实现任一个表达式中的语法检查（括号的匹配）。
（5）利用栈实现表达式的求值。
注：
（1）～（3）必做，（4）～（5）选做。
三．主要仪器设备及软件
（1）PC机
（2）DevC++,VisualC++,VS2010等
四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）
（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）；
A.顺序储存：
Ø代码部分：
//Main.cpp:
#include"SStack.h"
intmain（）
{
SqStackS;
SElemTypee;
intelect=1;
InitStack（S）;
cout<<"已经创建一个存放字符型的栈"<while（elect）
{
Muse（）;
cin>>elect;
cout<switch（elect）
{
case1:
cout<<"inputdata:
";
cin>>e;
Push（S,e）;
break;
case2:
if（Pop（S,e））
{cout<else{cout<<"blank"<break;
case3:
if（StackEmpty（S））
{
cout<<"栈空"<}
else
{
cout<<"栈未空"<}
break;
case4:
GetTop（S,e）;
cout<<"eis"<break;
case5:
StackLength（S）;
break;
case0:
break;
}
}
DestroyStack（S）;
returnOK;
}
//SStack.cpp:
#include"SStack.h"
//输出菜单
voidMuse（）
{
cout<<"请选择功能：
"<cout<<"1.入栈"<cout<<"2.出栈"<cout<<"3.判栈空"<cout<<"4.返回栈顶部数据"<cout<<"5.栈长"<cout<<"0.退出系统"<cout<<"你的选择是：
";
}
//创建栈
StatusInitStack（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;
returnOK;
}
//得到顶部数据
StatusGetTop（SqStackS,SElemType&e）
{
if（S.base==S.top）returnERROR;
e=*（S.top-1）;
returnOK;
}
//入栈
StatusPush（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;
returnOK;
}
//出栈
StatusPop（SqStack&S,SElemType&e）
{
if（S.base==S.top）
{
returnERROR;
}
e=*--S.top;
cout<<"popsucceed"<returnOK;
}
//判栈空
StatusStackEmpty（SqStackS）
{
if（S.top==S.base）
{
returnERROR;
}
returnOK;
}
//销毁栈
StatusDestroyStack（SqStack&S）
{
free（S.base）;
S.top=NULL;
S.stacksize=0;
cout<<"栈已销毁"<returnOK;
}
intStackLength（SqStackS）
{
cout<<"StackLengthis"<returnOK;
}
//SStack.h:
#include
#include
usingnamespacestd;
constintSTACK_INIT_SIZE=100;
constintSTACKINCREMENT=10;
constintERROR=0;
constintOK=1;
typedefcharSElemType;
typedefintStatus;
typedefstruct{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
StatusInitStack（SqStack&S）;//创建顺序存储的栈
StatusGetTop（SqStackS,SElemType&e）;//得到栈顶数据
StatusPush（SqStack&S,SElemType&e）;//入栈
StatusPop（SqStack&S,SElemType&e）;//出栈
voidMuse（）;//输出菜单界面
StatusStackEmpty（SqStackS）;//判断栈是否为空
StatusDestroyStack（SqStack&S）;//销毁栈
intStackLength（SqStackS）;//计算栈的长度
Ø运行结果：
B.链式储存：
Ø代码部分：
//Main.cpp
#include"Lstack.h"
intmain（）{
Lq_StackL;
if（InintStack（L））{
cout<<"buildstacksucceed"<}
elseexit（ERROR）;
inte=0;
Menu（L,e）;
DestroyStack（L）;
return0;
}
//Lstack.cpp
#include"Lstack.h"
StatusInintStack（Lq_Stack&L）{
//创建栈
L=（LqStack*）malloc（sizeof（LqStack））;
if（!
L）exit（ERROR）;
L->data=0;
L->next=NULL;
returnOK;
}
Statuspush（Lq_Stack&L,SElemTypee）{
//入栈
LqStack*p;
p=（LqStack*）malloc（sizeof（LqStack））;
if（!
p）exit（ERROR）;
p->data=e;
L->data++;
p->next=L->next;
L->next=p;
returnOK;
}
Statuspop（Lq_Stack&L,SElemType&e）{
//出栈
LqStack*p;
if（L->next==NULL）returnERROR;
p=L->next;
e=p->data;
L->next=p->next;
L->data--;
free（p）;
returnOK;
}
StatusGetTop（Lq_StackL,SElemType&e）{
//得到栈顶数据
if（L->next==NULL）returnERROR;
e=L->next->data;
returnOK;
}
StatusStackEmpty（Lq_StackL）{
//判断栈是否为空
if（L->next==NULL）{returnERROR;}
elsereturnOK;
}
intStackLength（Lq_StackL）{
//计算栈的长度
returnL->data;
}
StatusDestroyStack（Lq_Stack&L）{
//销毁栈
LqStack*p;
while（!
L）
{
L=p;
L=L->next;
free（p）;
}
returnOK;
}
voidMenu（Lq_Stack&L,SElemTypee）{
//输出菜单选择执行的功能
intselect=1;
while（select）
{
cout<<"————————————"<cout<<"请选择功能"<cout<<"——————1.入栈"<cout<<"——————2.出栈"<cout<<"——————3.得到顶部数据"<cout<<"——————4.判断栈是否为空"<cout<<"——————5.输出栈的长度"<cout<<"——————0.退出程序"<cout<<"你的选择是：
";
cin>>select;
switch（select）{
case0:
break;
case1:
cout<<"pushdata:
";
cin>>e;
if（push（L,e））{
cout<<"pushsucceed"<}
elsecout<<"pushfailed"<break;
case2:
if（pop（L,e））{
cout<<"data"<elsecout<<"popfailed"<break;
case3:
if（GetTop（L,e））{
cout<<"headdata"<elsecout<<"Getfailed"<break;
case4:
if（StackEmpty（L））{
cout<<"stackisnotNULL"<elsecout<<"stackisNULL"<break;
case5:
cout<<"thisstacklengthis"<break;
}
}
}
//Lstack.h
#include
#include
usingnamespacestd;
constintOK=1;
constintERROR=0;
typedefintSElemType;
typedefintStatus;
typedefstructLqStack{
SElemTypedata;
structLqStack*next;
}LqStack,*Lq_Stack;
StatusInintStack（Lq_Stack&L）;//创建栈
Statuspush（Lq_Stack&L,SElemTypee）;//入栈
Statuspop（Lq_Stack&L,SElemType&e）;//出栈
StatusGetTop（Lq_StackL,SElemType&e）;//得到栈顶数据
StatusStackEmpty（Lq_StackL）;//判断栈是否为空
intStackLength（Lq_StackL）;//计算栈的长度
StatusDestroyStack（Lq_Stack&L）;//销毁栈
voidMenu（Lq_Stack&L,SElemTypee）;//输出菜单选择执行的功能
Ø运行结果：
（2）应用栈的基本操作，实现数制转换（任意进制）；；
Ø代码部分：
//Main.cpp
#include"SStack.h"
intmain（）{
intnumber;
cout<<"要将数值转换为多少进制";
cin>>number;
conversion（number）;
return0;
}
SStack.cpp
#include"SStack.h"
StatusInitStack（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;
returnOK;
}
Statuspush（SStack&S,ElemTypee）{
//入栈
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;
returnOK;
}
Statuspop（SStack&S,ElemType&e）{
//出栈
if（S.top==S.dase）returnERROR;
e=*--S.top;
returnOK;
}
StatusStackEmpty（SStack&S）{
//判断栈是否为空
if（S.dase==S.top）returnERROR;
returnOK;
}
voidconversion（intnumber）{
//转换为e进制并输出
SStackS;
intN,e;
if（InitStack（S））{
cout<<"栈创建成功"<}
cout<<"输入待转换的数：
";
cin>>N;
while（N）{
push（S,N%number）;
N=N/number;
}
while（StackEmpty（S））{
pop（S,e）;
cout<}
cout<}
//SStack.h
#ifndefSSTACK_H
#defineSSTACK_H
#include
#include
usingnamespacestd;
constintSTACK_INIT_SIZE=100;
constintSTACKINCREMENT=10;
constintOK=1;
constintERROR=0;
typedefintStatus;
typedefintElemType;
typedefstruct{
ElemType*dase;
ElemType*top;
intstacksize;
}SStack;
StatusInitStack（SStack&S）;//创建栈
Statuspush（SStack&S,ElemTypee）;//入栈
Statuspush（SStack&S,ElemType&e）;//出栈
StatusStackEmpty（SStack&S）;//判断栈是否为空
voidconversion（intnumber）;//转换为number进制并输出
#endif
Ø运行结果：
（3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）。
Ø代码部分：
A:
链式储存：
//Main.cpp:
#include"QNode.h"
intmain（）{
LinkQueueQ;
InitQueue（Q）;
Menu（Q）;
DestroyQueue（Q）;
return0;
}
//QNode.cpp:
#include"QNode.h"
StatusInitQueue（LinkQueue&Q）{
//构造空队列
Q.front=Q.rear=（QueuePrt）malloc（sizeof（QNode））;
if（!
Q.front）exit（ERROR）;
Q.front->next=NULL;
returnOK;
}
StatusDestroyQueue（LinkQueue&Q）{
//销毁队列Q
while（Q.front）{
Q.rear=Q.front->next;
free（Q.front）;
Q.front=Q.rear;
}
returnOK;
}
StatusEnQueue（LinkQueue&Q,QElemTypee）{
//插入元素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;
returnOK;
}
StatusDeQueue（LinkQueue&Q,QElemType&e）{
//删除Q的队头元素，用e返回其值
QNode*p;
if（Q.front==Q.rear）returnERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if（Q.rear==p）Q.rear=Q.front;
free（p）;
returnOK;
}
StatusQueueEmpty（LinkQueueQ）{
//判断对是否为空
if（Q.front==Q.rear）returnERROR;
returnOK;
}
voidMenu（LinkQueue&Q）{
//输出选择界面
intselect=1;
QElemTypee;
while（select）{
cout<<"--------------------"<cout<<"请选择以下功能：
"<cout<<"--------------1,入队"<cout<<"--------------2,出队"<cout<<"--------------3,判断队空"<cout<<"--------------0,退出程序"<cout<<"请输入你的选择";
cin>>select;
switch（select）{
case0:
break;
case1:
cout<<"输入入队数据"<cin>>e;
if（EnQueue（Q,e））{
cout<<"入队成功"<}
break;
case2:
if（DeQueue（Q,e））{
cout<}
break;
case3:
if（QueueEmpty（Q））cout<<"此队不为空"<elsecout<<"此队为空"<break;
}
}
}
//QNode.h
#ifndefQNODE_H
#defineQNODE_H
#include
#include
usingnamespacestd;
constintOK=1;
constintERROR=0;
typedefintQElemType;
typedefintStatus;
typedefstructQNode{
QElemTypedata;
structQNode*next;
}QNode,*QueuePrt;
typedefstruct{
QueuePrtfront;
QueuePrtrear;
}LinkQueue;
StatusInitQueue（LinkQueue&Q）;//构造空队列
StatusDestroyQueue（LinkQueue
升级会员 