实验三栈和队列及其应用讲解

1、姓名学号实验项目栈和队列及其应用（I）1采用顺序存储结构，实现栈的存储和基本操作。栈的抽象数据类型定义参见教材第45页。栈的顺序存储结构定义参见教材第46页。2. 采用顺序存储结构，实现队列的存储和基本操作队列的抽象数据类型定义参见教材第59页。队列的顺序存储结构定义参见教材第64页。算法设计与程序实现:算法分析本次实验主函数采用顺序结构，主函数调用自己编写的头文件 DataStructure_Li nearList.h中的相关功能函数，完成实验要求。程序实现步骤：1顺序栈结构的基本操作：首先初始化一个顺序栈结构，然后输入需入栈的元素个数 N,通过一个循环依次输入N个元素，在输入的同时调用入栈

2、函数，这样就完成了 N个元素的入栈操作，随后调用返回栈顶元素的函数， 返回栈顶元素，接着通过循环调用出栈函数完成出栈操作，最后销毁栈结构。当然在进行入栈和出栈操作时，会使用判断栈是否为空、对栈进行遍历等操 作，这样就实现了对栈的基本操作。2、 栈结构的基本应用：（1）将输入的十进制数转换为二进制数。首 先初始化一个栈结构，构造一个空栈，然后输入十进制数N,根据十进制转 换为二进制的方法（除二取余法）通过循环判断将每次除二求模的数入栈，接着通过判断栈空条件，依次将栈中的元素出栈，然后输出这样就实现了十 进制对二进制的转换，当然其他进制之间的也是如此。（2） Hanoi问题的实现。其主要思想就是递

3、归，在进行递归调用函数本身的时候，参数的传递、 变量保存以及函数返回都使用了栈结构（操作系统建立）。3、 顺序队列的基本操作：首先初始化一个空的顺序结构队列，然后输入需入队列的元素个数N,通过一个循环依次输入N个元素，输入的同时调用入队列函数，完成了 N个元素的入队列操作，接着调用返回队头元素的函核心程序数，返回队头元素，接着通过循环调用出队列函数完成出队列操作，最后销 毁顺序队列结构，这样就实现了对栈的基本操作。此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在 主函数中文件包含部分的注释处，核心程序如下：1.主函数如下：#i ncludeiostream /标准输入输出流库文件

4、#i ncludewi ndows.hcmd窗口设置函数头文件#i ncludeADT.h/数据结构中相关结构体类型定义及相关数据类型定义#i ncludeDataStructure_LinearList.h/数据结构第一章线性表中相关函数的疋义及声明using namespacestd;void print( void );nt main( void )system( title数据结构实验实验三：栈和队列及其应用(I ) );/设置cmd窗口标题system( color F1 );/设置控制台窗口的背景色和前景色system( date /T );/输岀当前的日期pri nt();cou

5、t 实验内容一：采用顺序存储结构，实现栈的存储和基本操作 endl;SqStack S;SEIemTypee;InitStack Sq(S);/ 构造一个空栈 Sint count;cout cou nt;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.将十进制数转换为二进制数“ en dl;DecToBi n();/将十进制数转换为二进制数cout 2.汉罗塔问题

6、endl n;cout 圆盘移动步骤：;|Hanoi(n, x, y, z);DestoryStack_Sq(S);/ 销毁栈 Scout en dl;pri nt();cout 实验内容二：采用顺序存储结构，实现队列的存储和基本操作en dl;SqQueueQ;QElemTypedata;InitQueue Sq(Q);/ 构造一个空队列 Qcout cou nt;cout 请输入元素：”；for ( int i = 0; i data;En Queue Sq(Q, data);GetHead_Sq(Q, data);cout 队首元素： data endl; cout 岀队列：;while

7、 (DeQueue_Sq(Q, data)cout data ;cout en dl;pri nt();cout en dl;void print( void ) en dl;cout endl 2.头文件”ADT.h”的部分程序如下：#ifndef ADT_H_#defi ne ADT_H/*常量和数据类型预定义*/*函数结果状态代码 */#defi ne TRUE1#defi ne FALSE0#defi ne OK1#defi ne ERROR 0#defi ne INFEASIBLE -1#defi ne OVERFLOW -2/*数据类型预定义 */栈禾口歹列 */*栈数据类型定义

8、*/typedef int SEIemType顺序表中元素的数据类型/*顺序栈结构类型定义 */typedef structSElemType* base;/栈底指针SElemType* top;/栈顶指针int stacksize;/当前以分配的存储空间SqStack;/顺序栈结构类型/*队列数据类型定义 */typedef int QEIemType/顺序表中元素的数据类型/*队列动态存储分配初始常量预定义 */#define QUEUE_INIT_SIZE100/队列存储空间的初始分配量#define QUEUEINCREMENCT/队列存储空间的分配增量#define MAXQUEUE

9、SIZE1CC/循环队列最大长度/*队列顺序存储结构类型定义-*/typedef structQElemType*base;/队列初始化动态分配存储空间int front;/对头指针向量，队列不空，指向队头元素int rear;/队尾指针向量，队列不空，指向队尾下一个位置SqQueue顺序队列结构类型#endif /* ADT_H_ */3.头文件DataStructure StackQueue.h中部分函数定义如下:#i nclude #i nclude #i nclude ADT.h*功能函数声明区/栈的基本操作Status InitStack_Sq( SqStack &S);/构造一个空

10、顺序栈SStatus GetTop_Sq( SqStack &S, SElemType&e);/返回栈顶元素eStatus StackEmpty_Sq( SqStack &S);/判断栈S是否为空Status DestoryStack_Sq( SqStack &S);/销毁顺序栈SStatus Push Sq( SqStack &S, SElemTypee);/元素e压入顺序栈Status Pop_Sq(SqStack &S, SEIemType&e);/ 元素 e岀栈/栈的应用Status DecToBin( void );/十进制数转换为二进制数void Hanoi( int n, cha

11、r x, char y, char z);/ 实现 Hanoi问题，借助 y塔将x塔上的n个圆盘搬移到z塔上/* 队列*/队列的基本操作Status InitQueue_Sq( SqQueue&Q);/ 构造一个空的顺序队列 QStatus GetHead_Sq( SqQueue&Q, QElemType&e); / 返回顺序队列的队头元素 eStatus EnQueue_Sq(SqQueue&Q, QElemTypee); / 将元素 e插入到队列 Q中Status DeQueue_SqSqQueue&Q, QElemType&e); / 将元素 e从顺序队列中删除并返 回Status In

12、verseQueue_Sq( SqQueue&Q);/ 实现队列的逆置/*/功能函数定义区*/*栈 纟结 构 函定 义 */* 函数原型：Status InitStack Sq(SqStack &S)*函数功能：构造一个空栈S*入口参数：SqStack类型的结构体变量S的引用&S*岀口参数：返回函数结果状态Status InitStack_Sq( SqStack &S)S.base = ( SElemType*)malloc( STACK INIT SIZE* sizeof (SElemTyp。); if (! S.base)return (OVERFLOWS.top = S.base;S.

13、stacksize =STACK INIT SIZEreturn OK /Ini tStack_Sq*/Status DestoryStack_Sq( SqStack &S) SEIemType*p;while ( Sbase != Stop)p = - S.top;free(p);return OKDestoryStack_SqSElemType* newbase;if ( S.top -S.base = S.stacksize)newbase = ( SElemType*)realloc(S.base, ( STACKINCREMENTSstacksize)* sizeof (SElemT

14、ypg);if (!newbase)return OVERFLOW*Stop+ = e;return OKStatus Pop_Sq( SqStack &S SElemType&e) if ( S.top = S.base)return ERROR e = * - Stop;return OKPop Sq*函数原型Status DecToBi n( void)*函数功能将十进制数转换为二进制*入口参数void*出口参数返回函数结果状态*/Status DecToBin( void )LinkStack S;SElemTypee;long data;printf(请输入待转换的十进制数：);sc

15、anf s( %d, &data);In itStack_L(S); while (data)prin tf(转换后的二进制数：); while (S-next)Pop L(S, e);printf( %d, e);printf(n);Qbase = ( QElemType*)malloc( QUEUE INIT SIZE sizeof (QElemType);if (! Qbase)return (OVERFLOWQfront = Qrear = 0; return OK /Ini tQueue_Sq/*fi*函数原型Status GetHead_Sq(SqQueue &Q, QElemTy

16、pe &e)*函数功能若队列不空，则返回队头元素e,并返回函数结果状态OK否则返回ERRO*入口参数SqQueue类型的结构体变量C的引用&Q,QElemTyp类型元素e的引用&e*出口参数返回函数结果状态*/Status GetHead_Sq(SqQueue& Q QElemType&e)if ( Qfront = Qrear)returnERRO Re = Qbase Qrear - 1;/队尾指针向量指向下一个元素return OK/*/GetHead_Sq函数原型：Status En Queue_Sq(SqQueue &Q, QElemType e)*函数功能：将元素e插入到队列Q中*

17、入口参数：SqQueue类型的结构体变量C的引用&Q,QEIemTyp类型元素e*岀口参数：返回函数结果状态*/Status EnQueue_Sq(SqQueue& Q QElemType e)QElemType* newbase;if ( Qfront -Qrear = QUEUE_INIT_SIZEnewbase = ( QElemType*)realloc( Qbase, ( STACKINCREMENT QUEUE_INIT_SIZE* sizeof (QElemType);if (!newbase)return OVERFLOWQbase = n ewbase;Qbase Qrear

18、+ = e;return OKEn Queue_Sq/* 函数原型：Status DeQueue_Sq(SqQueue &S, QElemType &e)*函数功能：将元素e从队列中删除并返回*入口参数：SqQueu类型的结构体变量 Q勺引用&Q,QEIemTyp类型元素e的引用&e *岀口参数：返回函数结果状态Status DeQueue_Sq(SqQueue& Q QEIemType&e) if ( Qfront = Qrear)return ERRO Re = Qbase Qfront+;return OKDeQueue_Sq运行结果斂IE结呦实验实验三：摒和臥列及共应用（I2Mlb/lZ/WB眉_严緊魅萨黔鬲储结构-实现桟的存fit和基本操作111111100010111圆豊移动步勲5 N -丄0；31 32 40 65 234 C 32 3 C5 7忙為蓋于徽t 3flC AB CB ACB-A BMJftC二畫=W17V一冏冋,h r tn r hn 尸r 4rr rn_r jti ;实现珈列的存储和棊本操乍实验总结1、此次实验完成了对顺序存储结构的栈和队列的基本操作及简单应用, 加深了对课本知识的理解和掌握。此次实验相对较容易，但却是很基础的， 在以后的二叉树、图等高级数据结构都需要用到它，所以栈和队列是非常重 要的，有些细节部分是值得高度重