笔记|数据结构实验报告3————栈和队列及其应用笔记|数据结构

实验内容

（1）栈的定义、基本操作的实现，以及典型应用
①编程实现顺序栈/链栈的基本操作（如：栈的初始化、判断栈空、求栈的长度、取栈顶、入栈、出栈等），并设计菜单调用。（必做）
②利用栈结构，实现将任意的十进制整数N转成r（2≤r≤16）进制并输出。（选做）
③利用栈结构，对键盘输入任意字符串，判断其中的括号是否匹配。（选做）
④编写算法对键盘输入的整数序列a1a2 …an进行如下操作：当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈(1≤i≤n)。(习题2.3，P85)（选做）
⑤编程实现汉诺塔问题的递归求解，并分析hanio(3,'A','B','C')的执行过程，以及结果分析。（选做）
注：选做题②~⑤中，至少选做1题。
（2）队列的定义、基本操作的实现
编程实现循环队列/链队列的基本操作（如：初始化空队列、判断队空、求队列的长度、取队首、入队列、出队列等），并设计菜单调用。（必做）

1. 栈的定义、基本操作的实现，以及典型应用
【笔记|数据结构实验报告3————栈和队列及其应用】（1）编程实现顺序栈的基本操作
核心代码：
①comdef.h
#include
#include
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;

②spstackdef.H
#define MAXSIZE 100
typedef int SElemType;
typedef struct{
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //栈可用的最大容量
}SqStack;

③spstackapp.H
//栈的初始化
Status InitStack(SqStack &S)
{
//构造一个空栈
S.base=new SElemType[MAXSIZE]; //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
if(!S.base)//存储分配失败
exit (OVERFLOW);
S.top=S.base; //top初始为base,空栈
S.stacksize=MAXSIZE;
return OK;
}
//判断栈空
Status StackElemType(SqStack S)
{
return (S.base==S.top);
}
//求栈的长度
int StackLength(SqStack S)
{
return S.top-S.base;

}
//取栈顶
SElemType GetTop(SqStack S)
{
if(S.top!=S.base)
return *(S.top-1);
}
//出栈
Status Pop(SqStack &S,SElemType &e)
{
//删除栈顶元素，用e返回其值
if(S.top==S.base)
return ERROR;
else
{
e=*--S.top;
return OK;
}
}
//入栈
Status Push(SqStack &S,SElemType e)
{
if(S.top-S.base>=S.stacksize)//栈满
return ERROR;
else
{
*S.top++=e; //元素e压入栈顶，栈顶指针加一
return OK;
}
}
//输出栈
void StackTraverse(SqStack S)
{
SElemType *p=S.top-1;
while(p>=S.base)
{
cout<<"\n"<<*p;
p--;
}
}
//清空栈
void ClearStack(SqStack &S)
{
S.base=S.top;
}
//栈的销毁
bool DestroyStack(SqStack &S)
{
delete []S.base;
S.base=NULL;
S.top=NULL;
S.stacksize=0;
return true;
}
④main.CPP
#include "comdef.h"
#include "sqstackdef.h"
#include "sqstackapp.h"
int main(){
SqStack S;
SElemType e;
int choice,n,i;
cout<<"\n建立顺序栈：";
if (InitStack(S)==OVERFLOW){
cout<<"顺序栈空间分配失败,程序退出！";
return 0;
}
else{
cout<<"\n数据个数=";
cin>>n;
cout<<"\n输入"<for(int j=0; j{
cin>>i;
Push(S,i);
}
cout<<"顺序栈建立成功，顺序栈为：";
StackTraverse(S);
}
do {
cout<<"\n\n===================================";
cout<<"\n顺序栈的基本操作";
cout<<"\n===================================";
cout<<"\n1:判断栈空" ;
cout<<"\n2:求栈的长度" ;
cout<<"\n3:取栈顶" ;
cout<<"\n4:出栈" ;
cout<<"\n5:入栈" ;
cout<<"\n6:输出栈" ;
cout<<"\n7:清空栈" ;
cout<<"\n0:操作结束" ;
cout<<"\n===================================";
cout<<"\n请输入你的选择:";
cin>>choice;
switch (choice)
{
case 1:if(StackElemType(S))
cout<<"\n数据表为空表";
else
cout<<"\n数据表为非空表";
break;
case 2:cout<<"\n数据栈的长度为："case 3:if(StackElemType(S))
cout<<"\n栈为空，栈顶元素不存在！";
else
{
cout<<"\n栈顶元素为："<}
break;
case 4:if(!Pop(S,e))
{
cout<<"\n栈为空，栈顶元素不存在！";
}
else
{
cout<<"\n栈顶出栈成功！"<<"\n出栈后的栈为：";
StackTraverse(S);
}
break;
case 5:cout<<"入栈元素为：";
cin>>e;
Push(S,e);
cout<<"\n入栈成功！"<<"\n入栈后的栈为：";
StackTraverse(S);
break;
case 6: cout<<"顺序栈为：";
StackTraverse(S);
break;
case 7: ClearStack(S);
cout<<"成功清空！"<<"\n栈中无元素：";
StackTraverse(S);
break;
case 0:break;
default:cout<<"\n输入错误,重新输入！";
}
} while (choice) ;
DestroyStack(S);
return 0;
}
2. 队列的定义、基本操作的实现
编程实现循环队列的基本操作
核心代码：

comdef.h
#include
#include
#include
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
SqQueuedef.h
typedef int QElemType;
//队列的顺序存储结构
#define MAXQSIZE 100
typedef struct {
QElemType *base; //存储空间的基地址
int front; //头指针
int rear; //尾指针
}SqQueue;
SqQueueapp.h
//初始化空队列
Status InitQueue(SqQueue &Q)
{
//构造空队列
Q.base=new QElemType[MAXQSIZE]; //为队列分配一个最大容量为MAXQSIZE的数组空间
if(!Q.base) exit(OVERFLOW);
Q.front=Q.rear=0; //头指针和尾指针置空，队列为空
return OK;
}
//打印队列
void OutputQueue(SqQueue Q,int n)
{
if(Q.front==Q.rear) cout<<"队列为空";
while(Q.front!=Q.rear)
{
cout<Q.front=(Q.front+1)%(n+1);
}

}
//判断队空
Status QueueEmpty(SqQueue Q)
{
return (Q.front==Q.rear);
}
//求队列的长度
int QueueLength(SqQueue Q)
{
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
//取队首
Status GetHead(SqQueue Q,QElemType &e)
{
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front]; //返回队头元素的值，队头元素不变
return OK;
}
//出队列
Status DeQueue(SqQueue &Q,QElemType &e)
{
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front]; //保存队头元素
Q.front=(Q.front+1)%MAXQSIZE; //队头指针加一
return OK;
}
//入队列
Status EnQueue(SqQueue &Q,QElemType e)
{
//插入e为新的队尾元素
if((Q.rear+1)%MAXQSIZE==Q.front)
//尾指针在循环意义上加一，表明存储空间已满
return ERROR;
Q.base[Q.rear]=e; //新元素为队尾
Q.rear=(Q.rear+1)%MAXQSIZE; //队尾指针加一
return OK;
}
//队列的销毁
Status DestoryQueue(SqQueue &Q)
{
free(Q.base);
Q.base=NULL;
Q.front=Q.rear=0;

return OK;
}
main.CPP
#include "comdef.h"
#include "SqQueuedef.h"
#include "SqQueueapp.h"
int main(){
SqQueue Q;
QElemType e;
int choice,n,i;
cout<<"\n建立循环队列：";
if (InitQueue(Q)==OVERFLOW){
cout<<"队列空间分配失败,程序退出！";
return 0;
}
else{
cout<<"\n元素个数=";
cin>>n;
cout<<"\n输入"<for(int j=0; j{
cin>>i;
EnQueue(Q,i);
}
cout<<"顺序队列建立成功，队列为：";
OutputQueue(Q,n);
}
do {
cout<<"\n\n===================================";
cout<<"\n循环队列的基本操作";
cout<<"\n===================================";
cout<<"\n1:判断队列空" ;
cout<<"\n2:求队列的长度" ;
cout<<"\n3:取队首" ;
cout<<"\n4:出队列" ;
cout<<"\n5:入队列" ;
cout<<"\n6:打印队列" ;
cout<<"\n0:操作结束" ;
cout<<"\n===================================";
cout<<"\n请输入你的选择:";
cin>>choice;
switch (choice){
case 1:if(!QueueEmpty)
cout<<"此队列为空队列！";
else
cout<<"此队列非空！";
break;
case 2:cout<<"此队列的长度为"<break;
case 3:GetHead(Q,e);
cout<<"队首为："<break;
case 4:DeQueue(Q,e);
cout<<"出队列的元素为："<OutputQueue(Q,n);
break;
case 5:cout<<"需要入队列的元素为：";
cin>>e;
EnQueue(Q,e);
cout<<"\n当前队列为：";
OutputQueue(Q,n+1);
break;
case 6:
cout<<"\n队列为：";
OutputQueue(Q,n);
break;
case 0:break;
default:cout<<"\n输入错误,重新输入！";
}
} while (choice) ;
DestoryQueue(Q);
return 0;
}