《实验三 栈和队列及其应用(I)》由会员分享,可在线阅读,更多相关《实验三 栈和队列及其应用(I)(10页珍藏版)》请在金锄头文库上搜索。
1、电子信息工程学院2013级数据结构实验报告姓名学号实验项目栈和队列及其应用(I)实验内容1采用顺序存储结构,实现栈的存储和基本操作。栈的抽象数据类型定义参见教材第45页。栈的顺序存储结构定义参见教材第46页。2采用顺序存储结构,实现队列的存储和基本操作队列的抽象数据类型定义参见教材第59页。队列的顺序存储结构定义参见教材第64页。算法设计与程序实现:算法分析 本次实验主函数采用顺序结构,主函数调用自己编写的头文件DataStructure_LinearList.h中的相关功能函数,完成实验要求。 程序实现步骤:1、顺序栈结构的基本操作:首先初始化一个顺序栈结构,然后输入需入栈的元素个数N,通过
2、一个循环依次输入N个元素,在输入的同时调用入栈函数,这样就完成了N个元素的入栈操作,随后调用返回栈顶元素的函数,返回栈顶元素,接着通过循环调用出栈函数完成出栈操作,最后销毁栈结构。当然在进行入栈和出栈操作时,会使用判断栈是否为空、对栈进行遍历等操作,这样就实现了对栈的基本操作。2、栈结构的基本应用:(1)将输入的十进制数转换为二进制数。首先初始化一个栈结构,构造一个空栈,然后输入十进制数N,根据十进制转换为二进制的方法(除二取余法)通过循环判断将每次除二求模的数入栈,接着通过判断栈空条件,依次将栈中的元素出栈,然后输出这样就实现了十进制对二进制的转换,当然其他进制之间的也是如此。(2)Hano
3、i问题的实现。其主要思想就是递归,在进行递归调用函数本身的时候,参数的传递、变量保存以及函数返回都使用了栈结构(操作系统建立)。3、顺序队列的基本操作:首先初始化一个空的顺序结构队列,然后输入需入队列的元素个数N,通过一个循环依次输入N个元素,输入的同时调用入队列函数,完成了N个元素的入队列操作,接着调用返回队头元素的函数,返回队头元素,接着通过循环调用出队列函数完成出队列操作,最后销毁顺序队列结构,这样就实现了对栈的基本操作。核心程序此程序中用到的自己编写的头文件以在下面给出,而头文件的说明则在主函数中文件包含部分的注释处,核心程序如下:1.主函数如下:#include iostream /
4、标准输入输出流库文件#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); /输出当前的日期
5、print();cout 实验内容一:采用顺序存储结构,实现栈的存储和基本操作 endl;SqStack S;SElemType e;InitStack_Sq(S); /构造一个空栈Sint count;cout count;cout 请输入元素:;for (int i = 0; i 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
6、2.汉罗塔问题 endl n;cout 圆盘移动步骤:;Hanoi(n, x, y, z);DestoryStack_Sq(S); /销毁栈Scout endl;print();cout 实验内容二:采用顺序存储结构,实现队列的存储和基本操作 endl;SqQueue Q;QElemType data;InitQueue_Sq(Q); /构造一个空队列Qcout count;cout 请输入元素:;for (int i = 0; i data;EnQueue_Sq(Q, data);GetHead_Sq(Q, data);cout 队首元素: data endl;cout 出队列:;while
7、 (DeQueue_Sq(Q, data)cout data ;cout endl;print();cout endl;void print(void)cout endl * endl;2.头文件”ADT.h”的部分程序如下:#ifndef ADT_H_#define ADT_H_/* 常 量 和 数 据 类 型 预 定 义*/* -函数结果状态代码- */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/* -数据类型预定义- */typedef i
8、nt Status; /函数结果状态类型typedef int _bool; /bool状态类型/* 数 据 结 构 类 型 定 义*/*栈 和 队 列*/* -栈数据类型定义- */typedef int SElemType; /顺序表中元素的数据类型/* -栈动态存储分配初始常量预定义- */#define STACK_INIT_SIZE 100 /栈表存储空间的初始分配量#define STACKINCREMENT 10 /栈表存储空间的分配增量/* -顺序栈结构类型定义- */typedef structSElemType * base; /栈底指针SElemType * top; /
9、栈顶指针int stacksize; /当前以分配的存储空间SqStack; /顺序栈结构类型/* -队列数据类型定义- */typedef int QElemType; /顺序表中元素的数据类型/* -队列动态存储分配初始常量预定义- */#define QUEUE_INIT_SIZE 100 /队列存储空间的初始分配量#define QUEUEINCREMENT 10 /队列存储空间的分配增量#define MAXQUEUESIZE 100 /循环队列最大长度/* -队列顺序存储结构类型定义- */typedef structQElemType *base; /队列初始化动态分配存储空间i
10、nt front; /对头指针向量,队列不空,指向队头元素int rear; /队尾指针向量,队列不空,指向队尾下一个位置SqQueue; /顺序队列结构类型#endif /* ADT_H_ */3.头文件DataStructure_StackQueue.h中部分函数定义如下:#include #include #include ADT.h/* 功 能 函 数 声 明 区*/* -栈- */栈的基本操作Status InitStack_Sq(SqStack &S); /构造一个空顺序栈SStatus GetTop_Sq(SqStack &S, SElemType &e); /返回栈顶元素eStatus StackEmpty_Sq(SqStack &S); /判断栈S是否为空Status DestoryStack_Sq(SqStack &S); /销毁顺序栈SStatus Push_Sq(SqStack &S, SElemType e); /元素e压入顺序栈Status Pop_Sq(S