实验三 栈和队列及其应用(I)要点.doc

姓名 学号 实验项目 栈和队列及其应用（I） 实验内容 1．采用顺序存储结构，实现栈的存储和基本操作。 栈的抽象数据类型定义参见教材第45页。 栈的顺序存储结构定义参见教材第46页。 2．采用顺序存储结构，实现队列的存储和基本操作 队列的抽象数据类型定义参见教材第59页。 队列的顺序存储结构定义参见教材第64页。 算法设计与程序实现： 算法分析 本次实验主函数采用顺序结构主函数调用自己编写的DataStructure_LinearList.h中的相关功能函数 程序实现步骤 1、顺序栈结构的基本操作：首先初始化一个顺序栈结构然后输入需入栈的元素个数通过一个循环依次输入,这样就完成了 2、栈结构的基本应用：（1）将输入的十进制数转换为二进制数。首先初始化一个栈结构，构造一个空栈，然后输入十进制数N，根据十进制转换为二进制的方法（除二取余法）通过循环判断将每次除二求模的数入栈，接着通过判断栈空条件，依次将栈中的元素出栈，然后输出这样就实现了十进制对二进制的转换，当然其他进制之间的也是如此。（2）Hanoi问题的实现 3、顺序队列的基本操作：首先初始化一个空的顺序结构队列，然后输入需入队列的元素个数通过一个循环依次输入,完成了 核心程序 此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在主函数中文件包含部分的注释处，核心程序如下： 1.主函数如下： #include iostream //标准输入输出流库文件 #include windows.h //cmd #include ADT.h //数据结构中相关结构体类型定义及相关数据类型定义 #include DataStructure_LinearList.h //数据结构第二章线性表中相关函数的定义及声明 using namespace std; void print(void); int main(void) { system(title 数据结构实验 实验三：栈和队列及其应用（I） ); //设置cmd窗口标题 system(color F1); //设置控制台窗口的背景色和前景色 system(date /T); //输出当前的日期 print(); cout 实验内容一：采用顺序存储结构，实现栈的存储和基本操作 endl; SqStack S; SElemType e; InitStack_Sq(S); //构造一个空栈S int count; cout 请输入需入栈的元素个数：N = ; cin count; 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.将十进制数转换为二进制数 endl; DecToBin(); //将十进制数转换为二进制数 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 endl; print(); cout 实验内容二：采用顺序存储结构，实现队列的存储和基本操作 endl; SqQueue Q; QElemType data; InitQueue_Sq(Q); //构造一个空队列Q cout 请输入需入队列的元素个数：N = ; cin count; cout 请输入元素：; for (int i = 0; i count; i++) { cin data; EnQueue_Sq(Q, data); } GetHead_Sq(Q, data); cout 队首元素： data endl; cout 出队列：; while (DeQueue_Sq(Q, d