实验三栈和队列及其应用(I).docxVIP

姓名 学号 姓名 学号 实验项目实验内容栈和队列及其应用（I 实验项目 实验内容 1采用顺序存储结构，实现栈的存储和基本操作。 TOC \o 1-5 \h \z 栈的抽象数据类型定义参见教材第 45页。 栈的顺序存储结构定义参见教材第 46页。 采用顺序存储结构，实现队列的存储和基本操作 队列的抽象数据类型定义参见教材第 59页。 队列的顺序存储结构定义参见教材第 64页。 算法设计与程序实现: 算法分析本次实验主函数采用顺序结构，主函数调用自己编写的头文件 DataStructure_Li nearList.h 中的相关功能函数，完成实验要求。 算法分析 程序实现步骤： 1顺序栈结构的基本操作： 首先初始化一个顺序栈结构， 然后输入需 入栈的元素个数 N,通过一个循环依次输入 N个元素，在输入的同时调用入 栈函数，这样就完成了 N个元素的入栈操作，随后调用返回栈顶元素的函数， 返回栈顶元素，接着通过循环调用出栈函数完成出栈操作， 最后销毁栈结构。 当然在进行入栈和出栈操作时，会使用判断栈是否为空、对栈进行遍历等操 作，这样就实现了对栈的基本操作。 2、 栈结构的基本应用：（1）将输入的十进制数转换为二进制数。首 先初始化一个栈结构，构造一个空栈，然后输入十进制数 N,根据十进制转 换为二进制的方法（除二取余法）通过循环判断将每次除二求模的数入栈， 接着通过判断栈空条件，依次将栈中的元素出栈，然后输出这样就实现了十 进制对二进制的转换，当然其他进制之间的也是如此。（ 2） Hanoi问题的实 现。其主要思想就是递归，在进行递归调用函数本身的时候，参数的传递、 变量保存以及函数返回都使用了栈结构（操作系统建立）。 3、 顺序队列的基本操作：首先初始化一个空的顺序结构队列， 然后输 入需入队列的元素个数 N,通过一个循环依次输入 N个元素，输入的同时调 用入队列函数，完成了 N个元素的入队列操作，接着调用返回队头元素的函 核心程序数，返回队头元素，接着通过循环调用出队列函数完成出队列操作，最后销 毁顺序队列结构，这样就实现了对栈的基本操作。 核心程序 此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在 主函数中文件包含部分的注释处，核心程序如下： 1.主函数如下： #i nclude iostream // 标准输入输出流库文件 #i nclude wi ndows.h 〃cmd窗口设置函数头文件 #i nclude ADT.h //数据结构中相关结构体类型定义及相关数据类型定义 #i nclude DataStructure_ LinearList.h //数据结构第一章线性表中相关函数的疋 义及声明 using namespacestd; void print( void ); nt main( void ) { system( title 数据结构实验 实验三：栈和队列及其应用(I ) ); // 设置cmd窗口标题 system( color F1 ); //设置控制台窗口的背景色和前景色 system( date /T ); //输岀当前的日期 pri nt(); cout 实验内容一：采用顺序存储结构，实现栈的存储和基本操作 endl; SqStack S; SEIemTypee; InitStack Sq(S); // 构造一个空栈 S int count; cout 请输入需入栈的元素个数： N =; cin cou nt; cout 请输入元素：”； for (int i = 0; i count; i++) { cin e; Push_Sq(S, e); } GetTop_Sq(S, e); cout 栈顶元素： e endl; cout 岀栈：; while ((Pop Sq(S, e))) cout e cout endl 栈的应用： endl 1.将十进制数转换为二进制数 en dl; DecToBi n(); //将十进制数转换为二进制数 cout 2.汉罗塔问题 endl 请输入圆盘个数：; int n; //圆盘个数 char x = A , y = B , z = C cin n; cout 圆盘移动步骤：“ Hanoi(n, x, y, z); DestoryStack_Sq(S); // 销毁栈 S cout en dl; pri nt(); cout 实验内容二：采用顺序存储结构，实现队列的存储和基本操作 en dl; SqQueueQ; QElemTypedata; InitQueue Sq(Q); // 构造一个空队列 Q cout 请输入需入队列的元素个数：N =; cin cou nt; cout 请输入元素: