实验三栈和队列及其应用

1、学号某某实验项目栈和队列与其应用1实验内容1.采用顺序存储结构，实现栈的存储和根本操作。栈的抽象数据类型定义参见教材第45页。栈的顺序存储结构定义参见教材第46页。2.采用顺序存储结构，实现队列的存储和根本操作队列的抽象数据类型定义参见教材第59页。队列的顺序存储结构定义参见教材第64页。算法设计与程序实现:算法分析函数，完成实验要求。程序实现步骤：1、顺序栈结构的根本操作： 首先初始化一个顺序栈结构，然后输入需入栈的兀素个数 N,通过一个循环依次输入N个兀素，在输入的冋时调用入栈函数这样就完成了N个兀素的入栈操作，随后调用返回栈顶兀素的函数，返回栈顶兀素，接着通过循环调用出栈函数完成出栈操作

2、，最后销毁栈结构。当然在进展入栈和出栈操作时，会使用判断栈是否为空、对栈进展遍历等操J作，这样就实现了对栈的根本操作。2、栈结构的根本应用：1将输入的十进制数转换为二进制数。首本次实验主函数采用顺序结构， 主函数调用自己编写的头文件 中的相关功能先初始化一个栈结构，构造一个空栈，然后输入十进制数N,根据十进制转换为二进制的方法除二取余法通过循环判断将每次除二求模的数入栈， 接着通过判断栈空条件，依次将栈中的元素出栈，然后输出这样就实现了十 进制对二进制的转换，当然其他进制之间的也是如此。2Hanoi问题的实现。其主要思想就是递归，在进展递归调用函数本身的时候，参数的传递、 变量保存以与函数返回

3、都使用了栈结构操作系统建立。3、顺序队列的根本操作：首先初始化一个空的顺序结构队列，然后输入需入队列的元素个数 N,通过一个循环依次输入N个元素，输入的同时调用入队列函数，完成了 N个元素的入队列操作，接着调用返回队头元素的函 数，返回队头元素，接着通过循环调用出队列函数完成出队列操作，最后销 毁顺序队列结构，这样就实现了对栈的根本操作。核心程序此程序中用到的自己编写的头文件以在下面给出，而头文件的说明如此 在主函数中文件包含局部的注释处，核心程序如下：1.主函数如下：#inelude "iostream" II标准输入输岀流库文件#include "window

4、s.h" I/cmd 窗口设置函数头文件#inelude "ADT.h"/数据结构中相关结构体类型定义与相关数据类型定义#inelude "DataStructure_LinearList.h"/数据结构第二章线性表中相关函数的定义与声明usingn amespace std;void print( void );int main( void )system( "title数据结构实验实验三：栈和队列与其应用I" );/设置cmd窗口标题system( "color F1" );/设置控制台窗口的背景色和

5、前景色system( "date /T" );/输岀当前的日期pri nt();cout << "实验内容一：采用顺序存储结构，实现栈的存储和根本操作"<< endl;SqStack S;SEIemTypee;InitStack Sq(S);/ 构造一个空栈 Sint count;cout << "请输入需入栈的元素个数：N ="cin >> cou nt;cout << "请输入元素：”；for (int i = 0; i < count; i+)cin &

6、gt;> 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();/将十

7、进制数转换为二进制数cout << "2.汉罗塔问题"<< endl <<"请输入圆盘个数："nt n;/圆盘个数char x = 'A' , y ='B' , z = C ; |cin >> n;cout << "圆盘移动步骤："Hanoi(n, x, y, z);DestoryStack Sq(S);/ 销毁栈 Scout << en dl;pri nt();cout << "实验内容二：采用顺序存储结构，

8、实现队列的存储和根本操作"<<en dl;SqQueueQ;QElemTypedata;InitQueue_Sq(Q);/ 构造一个空队列 Qcout << "请输入需入队列的元素个数：N ="cin >> cou nt;cout << "请输入元素：”；for ( int i = 0; i < count; i+)cin >> data;En Queue Sq(Q, data);GetHead_Sq(Q, data);cout << " 队首元素："<

9、;< data << endl;cout << "岀队列："while (DeQueue_Sq(Q, data)cout << data <<""cout << en dl;pri nt();cout << en dl;void print( void )cout << endl <<<< en dl;I *“2.头文件"ADT.h"的局部程序如下:#ifndef ADT_H_#define ADT_H_/*常量和数据类型

10、预定义*/*函数结果状态代码 */#define TRUE1#define FALSE0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/*数据类型预定义 */typedefint Status ;/函数结果状态类型typedefint _bool ;/bool 状态类型*/数据结构类型定义*/*栈和队列*/*栈数据类型定义 */typedefi nt SEIemType顺序表中元素的数据类型/*栈动态存储分配初始常量预定义*/#define STACK_INIT_SIZE100/栈表存储空间的初始分配量#d

11、efine STACKINCREMENT/栈表存储空间的分配增量/*顺序栈结构类型定义 */typedefstructSEIemType* base;/ 栈底指针SEIemType* top;/ 栈顶指针nt stacksize;/当前以分配的存储空间SqStack;/顺序栈结构类型/*队列数据类型定义 */typedefi nt QEIemType顺序表中元素的数据类型/*队列动态存储分配初始常量预定义 */#define QUEUE_INIT_SIZE100/队列存储空间的初始分配量#define QUEUEINCREMENT/队列存储空间的分配增量#define MAXQUEUESIZE

12、100/循环队列最大长度/*队列顺序存储结构类型定义-*/typedefstructQEIemType*base;/队列初始化动态分配存储空间int front;/对头指针向量，队列不空，指向队头元素int rear;/队尾指针向量，队列不空，指向队尾下一个位置SqQueue顺序队列结构类型#endif /* ADT H */"DataStructure_StackQueue.h"中局部函数定义如下:#incIude <stdio.h>#incIude <maIIoc.h>#incIude "ADT.h"/*功能函数声明区*/*

13、栈*/栈的根本操作Status InitStack_Sq( SqStack &S);/ 构造一个空顺序栈 SStatusGetTop_Sq( SqStack &S, SEIemType&e);/返回栈顶元素 eStatusStackEmpty_Sq( SqStack &S);/判断栈 S是否为空StatusDestoryStack_Sq( SqStack &S);/销毁顺序栈 SStatusPush_Sq( SqStack &S, SElemTypee);/元素 e压入顺序栈StatusPop_Sq( SqStack &S, SElemT

14、ype&e);/元素 e岀栈II栈的应用Status DecToBin( void );II十进制数转换为二进制数void Hanoi( int n, char x, char y, char z); II 实现 Hanoi问题，借助 y塔将x塔 上的n个圆盘搬移到z塔上I* 队列*III队列的根本操作Status InitQueue_Sq( SqQueue&Q);II 构造一个空的顺序队列 QStatus GetHead_Sq( SqQueue&Q, QEIemType&e); II 返回顺序队列的队头元素 eStatus EnQueue_Sq(SqQueue

15、&Q, QEIemTypee); II 将元素 e插入到队列 Q中Status DeQueue_SqSqQueue&Q, QEIemType&e); II 将元素 e从顺序队列中删除并返 回Status InverseQueue_Sq( SqQueue&Q);II 实现队列的逆置/*功能函数定义区*/I*栈结构函数定义 *II*函数原型Status In itStack_Sq(SqStack &S)*函数功能构造一个空栈S*入口参数SqStack类型的结构体变量S的引用&S*出口参数返回函数结果状态*IStatus InitStack_Sq( S

16、qStack &S) Sbase = ( SEIemType *)malloc( STACK_INIT_SIZE* sizeof (SEIemType); if (! Sbase)return (OVERFLOWStop = S.base;S stacksize = STACK_INIT_SIZEreturn OK /Ini tStack_SqI*函数原型Status DestoryStack Sq(SqStack &S)*函数功能销毁栈S*入口参数SqStack类型的结构体变量S的引用&S*出口参数返回函数结果状态Status DestoryStack_Sq( SqS

17、tack &S) SEIemType*p;while ( S.base !=S.top)p = - S.top;free(p);return OKDestoryStack_Sq/*/Status Push_Sq( SqStack &S, SElemType)SElemType* newbase;if ( S.top -S.base >= S.stacksize)newbase = ( SElemType*)realloc(S.base, ( STACKINCREMENTSstacksize)* sizeof (SElemTypg);f (!newbase)return O

18、VERFLOWSbase = n ewbase;Stop = S.base + S.stacksize;S stacksize += STACKINCREMENT*Stop+ = e;return OKPush_Sq/*/Status Pop_Sq( SqStack &S SElemType&e) if ( S.top = Sbase)return ERRORe = * - Stop; return OKPop_Sq/*函数原型Status DecToBi n( void)*函数功能将十进制数转换为二进制*入口参数void*出口参数返回函数结果状态*/Status DecToB

19、in( void )LinkStack S;SElemTypee;long data;printf("请输入待转换的十进制数：");scanf s( "%d", &data);In itStack_L(S);while (data)Push_L(S, data % 2); data = data / 2;pri ntf("转换后的二进制数：")；while (S->next)Pop_L(S, e); printf( "%d", e);printf( "n");return OK/*

20、 /DecToBin*函数原型Status InitQueue Sq(SqQueue &Q)*函数功能构造一个空队列Q*入口参数SqQueue类型的结构体变量C的引用&Q*出口参数返回函数结果状态队列结构函数定义*/Status InitQueue_Sq( SqQueue&Q Qbase = ( QElemType*)malloc( QUEUE_INIT_SIZE sizeof (QElemType); if (! Qbase)return (OVERFLOWQfront =Qrear = 0;return OKl ni tQueue_Sq/return OKEn Qu

21、eue_Sq/* 函数原型：Status DeQueue_Sq(SqQueue &S, QElemType &e) 1、此次实验完成了对顺序存储结构的栈和队列的根本操作与简单应用， 加深了对课本知识的理解和掌握。此次实验相对较容易，但却是很根底的， 在以后的二叉树、图等高级数据结构都需要用到它，所以栈和队列是非常重 要的，有些细节局部是值得高度重视的，也是容易出错的地方。2、 栈顶指针指向的是栈顶元素的下一个位置，在进展出栈操作时，应先 将栈顶指针向量自减，指向栈顶元素，才能保证栈中元素正确出栈。当进展 连续入队列操作时，要改变的是队尾指针的指向，而不是队头指针；虽然初 始状态

22、下队头指针和队尾指针都指向头一个元素，所以做第一个插入时关系不大，但第二次开始就一定要改变尾指针。3 因为栈是希望当有需要进展入栈操作时就一定能够入栈，一般来说， 初始化顺序空栈时，不应限定栈的最大容量，但在顺序结构当中存储空间是 由程序员需要时事先指定分配的，一个合理的做法就是：先为栈分配一个根 本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。* 函数原型：Status GetHead_Sq(SqQueue &Q, QElemType &e)*函数功能：假如队列不空，如此返回队头元素e,并返回函数结果状态OK否如此返回ERROR*入口参数：SqQueue类型的结构体变量C的引用&Q,QEIemTyp类型元素e的引用&e*岀口参数：返回函数结果状态*/Status GetHead_Sq(SqQueue& Q QElemType&e)if ( Qfront = Qrear)return ERRORe = Qbase Qrear - 1;/队尾指针向量指向下一个元素return OK /GetHead_Sq/*|*函数原型Status En Queue_Sq(SqQueue &Q, QElemType e)*函数功能将元素e插入到队列Q中|*入口参数SqQueue类