数据结构实验报告二、栈

数据结构实验报告二、栈"/>

数据结构实验报告二、栈

实验二 栈的应用

一、实验目的及要求

1.实验目的

1）掌握栈的概念、抽象数据类型和特点，掌握栈的顺序存储或者链式存储结构的存储思想及其程序实现，掌握栈对应存储结构的基本操作。

2.实验要求

1）用结构体类型描述栈的存储结构，对可能出现的问题预先分析，确定调试步骤和测试方法，编写源程序，尽可能考虑算法的健壮性，对实验中出现的问题进行分析、总结，完成实验报告。

2）上机过程中要遵守实验室的各项规章制度,爱护实验设备，保持环境卫生。

3）本课程的实验过程中，不得进行游戏、上网等操作。

二、实验环境（工具、配置等）

​ 1.硬件要求：计算机一台。

​ 2.软件要求：Windows11操作系统，使用C++语言，编译环境Dev-C++。

​ 3.数据结构与算法分析书一本，采用C++11标准。

三、实验内容（实验方案、实验步骤、设计思路等）

​ 1.实验方案：根据课本和老师课堂中讲解的内容，将编好的链式栈代码上机进行检验，再通过调用栈的弹出，进行数制转换相应的操作。

​ 2.实验步骤：在书上或网上找到相关算法，进行修改，上机检验，纠错。

​ 1）先编写自定义的栈，实现栈的弹出，查看栈顶，销毁栈，栈的插入，栈的遍历等功能，然后进行调试。

​ 2）通过手写的栈实现数的进制转换。

​ 3.设计思路：手写一个链式存储的栈，先定义栈的节点，再编写相应的函数，实现栈的基本功能，最后通过手写栈的弹出，实现数的进制转换。

四、实验结果与分析

1.测试手写栈的功能，若手写栈输出了结果，且符合预期要求，则说明手写栈符合需求，效果如图4-1：

​图4-1 链栈输出结果

2.使用编译软件编写程序实现数制转换，运行结果如图4-2：

​ 图4-2 程序输出结果

实验分析：

1.实验遇到的问题：

1）编写的栈编译未出错，但无法正常插入元素。

2）编写数制转换函数时，出现死循环问题。

3）未搞清楚链式栈的清空与销毁的区别

2.问题解决的方法：

1）针对遇到的问题，经过调试后发现是在编写入栈函数时先将指针加一未先赋值在加一，纠正后程序正常运行。

2）针对遇到的问题，调试后发现在编写数制转换函数时，未将循环条件更改造成死循环，改正后，程序正常运行。

3）针对遇到的问题，链式栈销毁和清空的区别是，清空时多了初始化，其余跟销毁差不多。

五、源程序

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;//    链栈节点 
typedef struct Stack_Node{int data;struct Stack_Node *next;
}Stack_Node,*Link_stack;//初始化链栈 
int Init_stack(Link_stack &L){    //构造一个空栈，让其指向空 L=NULL;return 1;
}//向栈插入元素 
int Push_stack(Link_stack &L,int e){Stack_Node *p;p=new Stack_Node;             //生成新节点 p->data=e;p->next=L;L=p;return 1;
}//弹出栈顶 
int Pop_stack(Link_stack &L){if(L==NULL){cout<<"栈空！";return 0;}int e = L->data;Stack_Node *p=L;L=L->next;delete p;return e;
}//查看栈顶元素 
int Top_stack(Link_stack &L){if(L==NULL){cout<<"栈空！";return 0; }return L->data;
}//实现数制转换 
Link_stack Numexchange(int m,int x){Link_stack p;Init_stack(p);            //初始化栈 while(m){Push_stack(p,m%x);    //将数字存入栈 m/=x;}return p;
}//栈的遍历 
void Travel_stack(Link_stack &L){Stack_Node *p=L;vector<int> a;while(p){a.push_back(p->data);p=p->next;}reverse(a.begin(),a.end());for(auto x:a){cout<<x<<' ';}cout<<'\n';
}//销毁栈 
void Destroy_stack(Link_stack &L){Stack_Node *p;while(L!=NULL){p=L;L=L->next;delete p;}
}//判断栈是否为空 
void Isempty_stack(Link_stack &L){if(L!=NULL){cout<<"非空";}else{cout<<"栈空";}
}int main(){Link_stack L;Init_stack(L);int n;cout << "请输入你要入栈的数" << endl;cin >> n;cout<<"请输入元素："<<'\n';for(int i=0;i<n;i++){int x;cin>>x;Push_stack(L,x);}cout<<"栈为：";Travel_stack(L);cout<<"弹出栈顶：";int e1=Pop_stack(L);cout<<e1<<'\n'; cout<<"弹出栈顶：";int e2=Pop_stack(L);cout<<e2<<'\n';cout<<"栈为："; Travel_stack(L);cout<<"栈顶元素为：";int e3=Top_stack(L);cout<<e3<<'\n';cout<<"栈为：";Travel_stack(L);cout<<"销毁栈"<<'\n'; Destroy_stack(L);cout<<"判断栈是否为空：";Isempty_stack(L);int m,x;cout<<"请输入你要转化的数，及转换的进制：";cin>>m>>x;Link_stack q=Numexchange(m,x);cout<<"转换后为：";while(q!=NULL){int l=Pop_stack(q);cout<<l;}
}