数据结构实验三——栈和队列的基本操作
程序员文章站
2024-01-26 13:41:10
**一、实验内容**1. 实验目的编程实现顺序栈和链栈的基本操作：建栈，取栈顶元素，入栈，出栈；编程实现循环队列和链队列的基本操作：建队列，取队头元素，入队，出队。2. 基本要求掌握栈的顺序存储结构、链式存储结构及其基本操作；掌握队列的顺序存储结构、链式存储结构及其基本操作。4. 支撑的课程目标本实验项目可以支撑“目标1. 理解数据结构的基本概念、计算机内部数据对象的表示和特性。掌握线性表、树、图等数据逻辑结构、存储结构及其差异以及各种操作的实现。”、和“目标2能够针对实际问题选...
栈和队列
一、实验内容
1.实验目的
- 编程实现顺序栈和链栈的基本操作：建栈，取栈顶元素，入栈，出栈；
- 编程实现循环队列和链队列的基本操作：建队列，取队头元素，入队，出队。
2. 基本要求
- 掌握栈的顺序存储结构、链式存储结构及其基本操作；
- 掌握队列的顺序存储结构、链式存储结构及其基本操作。
3. 支撑的课程目标
本实验项目可以支撑“目标1. 理解数据结构的基本概念、计算机内部数据对象的表示和特性。掌握线性表、树、图等数据逻辑结构、存储结构及其差异以及各种操作的实现。”、和“目标2能够针对实际问题选择合适的数据结构和方法设计出结构清晰、正确易读、复杂性较优的算法，同时掌握对算法进行时间、空间复杂度分析的基本技能。”。
本实验通过验证方式引导学生掌握顺序栈和链栈的基本操作，循环队列和链队列的基本 操作，为后续学习打下基础，以便更好地达成后续更高层次的课程目标。
二、实验过程
1. 顺序栈的建栈、入栈、出栈、取栈顶元素
/*
*title:顺序栈的基本操作
*writer:weiyuexin
*data:2020-10-11
*/
#include<iostream>
using namespace std;
#define SElemType int
typedef struct{
SElemType *base; //定义栈底指针
SElemType *top; //定义栈顶指针
int stacksize;
}SqStack;
void InitStack(SqStack &S,int maxsize){ //初始化栈
S.base = new SElemType[maxsize];
if(!S.base){
cout<<"创建栈失败!"<<endl;
}
S.top = S.base; //top初始化为base,是空栈
S.stacksize = maxsize;
cout<<"成功创建了一个最大容量为"<<S.stacksize<<"的顺序栈!"<<endl;
}
void Display(SqStack S){ //打印顺序栈
cout<<"该顺序栈为:"<<endl;
cout<<"栈底=>";
for(int i=0;i<S.stacksize;i++){
cout<<*S.base++<<" ";
if(!*S.base || S.top == S.base){
break;
}
}
cout<<"<=栈顶"<<endl;
}
void Push(SqStack &S,SElemType e){ //入栈
if(S.top - S.base == S.stacksize){
cout<<"栈已满，无法插入!"<<endl;
return;
}
*S.top++=e;
}
SElemType Pop(SqStack &S){ //出栈
if(S.top == S.base){
cout<<"栈空!"<<endl;
}
SElemType e;
e = *--S.top;
cout<<e<<" ";
}
SElemType GetTop(SqStack S){
if(S.top != S.base){
return *(S.top-1);
}
}
int main(){
SqStack S;
int maxsize;
cout<<"实验3_1-------------------顺序栈的基本操作"<<endl<<endl;
cout<<"请输入对应数字选择操作："<<endl;
cout<<"1------------------建栈"<<endl;
cout<<"2------------------入栈"<<endl;
cout<<"3------------------出栈"<<endl;
cout<<"4------------------打印顺序栈"<<endl;
cout<<"5------------------取栈顶元素"<<endl;
cout<<"0------------------结束程序运行"<<endl;
int operation;
while(cin>>operation){
switch(operation){
case 0 :
cout<<"程序运行结束!"<<endl;
return 0;
break;
case 1 :
cout<<"请输入栈的最大容量:"<<endl;
cin>>maxsize;
InitStack(S,maxsize);
cout<<"请输入对应数字选择操作："<<endl;
break;
case 2 :
cout<<"请输入数据元素,当输入-1时结束:"<<endl;
int e;
while(cin>>e){
if(e == -1){
break;
}
Push(S,e);
}
cout<<"入栈成功!"<<endl;
Display(S);
cout<<"请输入对应数字选择操作："<<endl;
break;
case 3 :
cout<<"请输入出栈元素的个数:"<<endl;
int m;
cin>>m;
cout<<"出栈的元素为:"<<endl;
for(int i= 0;i<m;i++){
Pop(S);
}
cout<<"(先出->后出)"<<endl;
Display(S);
cout<<"请输入对应数字选择操作："<<endl;
break;
case 4 :
Display(S);
cout<<"请输入对应数字选择操作："<<endl;
break;
case 5 :
cout<<"栈顶元素为: "<<GetTop(S)<<endl;
cout<<"请输入对应数字选择操作："<<endl;
break;
default :
cout<<"您选择的操作不存在，请重新选择:"<<endl;
cout<<"请输入对应数字选择操作："<<endl;
break;
}
}
return 0;
}
1. 链栈的建栈、入栈、出栈、及取栈顶元素
/*
*title:链栈的基本操作
*writer:weiyuexin
*data:2020-10-11
*/
#include<iostream>
using namespace std;
#define ElemType int
typedef struct StackNode{
ElemType data;
struct StackNode *next;
}StackNode,*LinkStack;
void InitStack(LinkStack &S){ //初始化链栈
S = NULL;
cout<<"栈S初始化成功!"<<endl;
}
void Display(LinkStack S){
LinkStack p = S;
cout<<"该链栈为:"<<endl;
cout<<"栈顶=> ";
while(p){
cout<<p->data<<" ";
p = p->next;
}
cout<<" <=栈底"<<endl;
}
ElemType Pop(LinkStack &S,ElemType ee){
if(S == NULL){
cout<<"栈已空，无法在进行删除操作!"<<endl;
return 0;
}
StackNode *p = new StackNode();
ee = S->data;
p = S;
S = S->next;
delete p;
return ee;
}
void Push(LinkStack &S,ElemType e){ //入栈
StackNode *p = new StackNode();
p ->data = e;
p ->next = S;
S = p;
}
int main(){
LinkStack S;
cout<<"实验3_2-------------------链栈的基本操作"<<endl<<endl;
cout<<"请输入对应数字选择操作："<<endl;
cout<<"1------------------初始化链栈"<<endl;
cout<<"2------------------入栈"<<endl;
cout<<"3------------------出栈"<<endl;
cout<<"4------------------打印链栈"<<endl;
cout<<"5------------------取栈顶元素"<<endl;
cout<<"0------------------结束程序运行"<<endl;
int operation;
while(cin>>operation){
switch(operation){
case 0 :
cout<<"程序运行结束!"<<endl;
return 0;
break;
case 1 :
InitStack(S);
cout<<"请输入对应数字选择操作："<<endl;
break;
case 2 :
cout<<"请输入数据元素,当输入-1时结束:"<<endl;
ElemType e;
while(cin>>e){
if(e == -1){
break;
}
Push(S,e);
}
cout<<"入栈成功!"<<endl;
Display(S);
cout<<"请输入对应数字选择操作："<<endl;
break;
case 3 :
cout<<"请输入出栈元素的个数:"<<endl;
int n;
cin>>n;
cout<<"出栈的元素依次为: ";
for(int i=0;i<n;i++){
ElemType ee;
cout<<Pop(S,ee)<<" ";
}
cout<<endl;
Display(S);
cout<<"请输入对应数字选择操作："<<endl;
break;
case 4 :
Display(S);
cout<<"请输入对应数字选择操作："<<endl;
break;
case 5 :
cout<<"栈顶元素为:"<<S->data<<endl;
cout<<"请输入对应数字选择操作："<<endl;
break;
default :
cout<<"您选择的操作不存在，请重新选择:"<<endl;
cout<<"请输入对应数字选择操作："<<endl;
break;
}
}
return 0;
}
3.循环队列的建立、入队、出队及取队头元素
/*
*title: 循环队列的基本操作
*writer:weiyuexin
*data:2020-10-11
*/
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define QElemType int
typedef struct{
QElemType *base; //存储空间基地址
int front; //头指针
int rear; //尾指针
}SqQueue;
void InitQueue(SqQueue &Q){ //初始化循环队列
Q.base = new QElemType[MAXSIZE];
if(!Q.base){
cout<<"队列初始化失败!"<<endl;
return;
}
Q.front = Q.rear = 0;
cout<<"循环队列初始化成功!"<<endl;
}
void EnQueue(SqQueue &Q,QElemType e){ //入队
if((Q.rear + 1)%MAXSIZE == Q.front){
cout<<"该队列已满无法插入!"<<endl;
return;
}
Q.base[Q.rear] = e; //新元素插入对尾
Q.rear = (Q.rear + 1)%MAXSIZE; //队尾指针加一
}
QElemType DeQueue(SqQueue &Q,QElemType &ee){
if(Q.front == Q.rear){
cout<<"该循环队列已空!"<<endl;
return 0;
}
ee = Q.base[Q.front]; //保存队首指针
Q.front = (Q.front + 1)%MAXSIZE; //队首指针加一
return ee;
}
void Display(SqQueue Q){ //打印循环队列
cout<<"该循环队列为: "<<endl;
cout<<"队首=>";
for(int i=Q.front;i<MAXSIZE;i++){
if(!Q.base[i]){
break;
}
cout<<Q.base[i]<<" ";
}
cout<<"<=队尾"<<endl;
}
QElemType GetHead(SqQueue Q){ //去队首元素
if(Q.front != Q.rear){ //队列非空
return Q.base[Q.front];
}else{
cout<<"队列中没有元素!"<<endl;
return 0;
}
}
int QueueLength(SqQueue Q){ //求队列的长度
return (Q.rear - Q.front +MAXSIZE)%MAXSIZE;
}
int main(){
SqQueue Q;
cout<<"实验3_3---------------------循环队列的基本操作"<<endl<<endl;
cout<<"请输入对应数字选择您想要的操作:"<<endl;
cout<<"1----------------建立循环队列"<<endl;
cout<<"2----------------入队"<<endl;
cout<<"3----------------出队"<<endl;
cout<<"4----------------取队头元素"<<endl;
cout<<"5----------------打印循环队列"<<endl;
cout<<"6----------------求队列长度"<<endl;
cout<<"0----------------结束程序"<<endl;
int operation;
while(cin>>operation){
switch(operation){
case 0 :
cout<<"程序运行结束!"<<endl;
return 0;
break;
case 1 :
InitQueue(Q); //初始化队列
cout<<"请输入对应数字选择您想要的操作:"<<endl;
break;
case 2 :
int e;
cout<<"请输入想要入队的元素，以-1为截止符:"<<endl;
while(cin>>e){
if(e == -1){
break;
}
EnQueue(Q,e);
}
cout<<"入队成功!"<<endl;
Display(Q);
cout<<"请输入对应数字选择您想要的操作:"<<endl;
break;
case 3 :
cout<<"请输入想要出队的元素个数:"<<endl;
int n;
cin>>n;
cout<<"出队的元素依次为: ";
for(int i=0;i<n;i++){
QElemType ee;
cout<<DeQueue(Q,ee)<<" ";
}
cout<<endl;
Display(Q);
cout<<"请输入对应数字选择您想要的操作:"<<endl;
break;
case 4 :
cout<<"队首元素为:"<<GetHead(Q)<<endl;
cout<<"请输入对应数字选择您想要的操作:"<<endl;
break;
case 5 :
Display(Q);
cout<<"请输入对应数字选择您想要的操作:"<<endl;
break;
case 6 :
cout<<"该循环链表的长度为:"<<QueueLength(Q)<<endl; //求队列长度
cout<<"请输入对应数字选择您想要的操作:"<<endl;
break;
default :
cout<<"您选择的操作不存在，请重新选择:"<<endl;
break;
}
}
return 0;
}
**
4.链队的创建、入队、出队及取队头元素
**
/*
*title:链队的基本操作
*writer:weiyuexin
*data:2020-10-11
*/
#include<iostream>
using namespace std;
#define QElemType int
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
void InitQueue(LinkQueue &Q){ //初始化链队
Q.front = Q.rear = new QNode; //生成新结点作为头结点，队头和队尾指针指向此节点
Q.front->next = NULL; //头结点的指针域置空
cout<<"链队初始化成功!"<<endl;
}
void EnQueue(LinkQueue &Q,QElemType e){ //入队
QNode *p = new QNode();
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
}
QElemType DeQueue(LinkQueue &Q){ //出队
if(Q.front == Q.rear){
cout<<"该链队已空!"<<endl;
return 0;
}
QElemType e;
QNode *p = new QNode();
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if(Q.rear == p){
Q.rear = Q.front;
}
delete p;
return e;
}
QElemType GetHead(LinkQueue Q){ //取队首值
if(Q.front != Q.rear){ //队列非空
return Q.front->next->data; //返回队首值
}else{
cout<<"该链队为空！"<<endl;
return 0;
}
}
void Display(LinkQueue Q){ //打印链队元素
QNode *p = new QNode();
p = Q.front->next;
cout<<"该链队为: 队首=> ";
while(p != NULL){
cout<<p->data<<" ";
p = p->next;
}
cout<<"<=队尾"<<endl;
}
int main(){
LinkQueue Q;
cout<<"实验3_4---------------------链队列的基本操作"<<endl<<endl;
cout<<"请输入对应数字选择您想要的操作:"<<endl;
cout<<"1----------------建立链队列"<<endl;
cout<<"2----------------入队"<<endl;
cout<<"3----------------出队"<<endl;
cout<<"4----------------取队头元素"<<endl;
cout<<"5----------------打印链队列"<<endl;
cout<<"0----------------结束程序"<<endl;
int operation;
cout<<"请输入对应的数字选择你想要进行的操作:"<<endl;
while(cin>>operation){
switch(operation){
case 0 :
cout<<"程序运行结束!"<<endl;
return 0;
case 1 :
InitQueue(Q);
cout<<"请输入对应的数字选择您想要进行的操作:"<<endl;
break;
case 2 :
cout<<"请输入要入队的元素个数；"<<endl;
int n;
cin>>n;
cout<<"请输入要入队的元素:"<<endl;
for(int i=0;i<n;i++){
QElemType e;
cin>>e;
EnQueue(Q,e);
}
cout<<n<<"个元素入队成功!"<<endl;
Display(Q);
cout<<"请输入对应的数字选择您想要进行的操作:"<<endl;
break;
case 3 :
cout<<"请输入要出栈的元素的个数:"<<endl;
int m;
cin>>m;
cout<<"出栈的元素依次为: ";
for(int i=0;i<m;i++){
cout<<DeQueue(Q)<<" ";
}
cout<<endl;
Display(Q);
cout<<"请输入对应的数字选择您想要进行的操作:"<<endl;
break;
case 4 :
cout<<"该链队队首值为: "<<GetHead(Q)<<endl;
cout<<"请输入对应的数字选择您想要进行的操作:"<<endl;
break;
case 5 :
Display(Q);
cout<<"请输入对应的数字选择您想要进行的操作:"<<endl;
break;
default :
cout<<"您选择的操作不存在，请重新选择:"<<endl;
break;
}
}
return 0;
}
本文地址：https://blog.csdn.net/weixin_46353366/article/details/109016587