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

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 "iost

4、ream" /标准输入输出流库文件#include "windows.h" /cmd窗口设置函数头文件#include "ADT.h" /数据结构中相关结构体类型定义及相关数据类型定义#include "DataStructure_LinearList.h" /数据结构第二章线性表中相关函数的定义及声明using namespace std;void print(void);int main(void)system("title 数据结构实验 实验三：栈和队列及其应用（I） "); /设置cmd窗口标题

5、system("color F1"); /设置控制台窗口的背景色和前景色 system("date /T"); /输出当前的日期print();cout << "实验内容一：采用顺序存储结构，实现栈的存储和基本操作" << endl;SqStack S;SElemType e;InitStack_Sq(S); /构造一个空栈Sint count;cout << "请输入需入栈的元素个数：N = "cin >> count;cout << "请输入

6、元素："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 <<

7、 "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); /销毁

8、栈Scout << endl;print();cout << "实验内容二：采用顺序存储结构，实现队列的存储和基本操作" << endl;SqQueue Q;QElemType data;InitQueue_Sq(Q); /构造一个空队列Qcout << "请输入需入队列的元素个数：N = "cin >> count;cout << "请输入元素："for (int i = 0; i < count; i+)cin >> data;EnQueue

9、_Sq(Q, data);GetHead_Sq(Q, data);cout << " 队首元素：" << data << endl;cout << " 出队列："while (DeQueue_Sq(Q, data)cout << data << " "cout << endl;print();cout << endl;void print(void)cout << endl << "*" <

10、< 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 int Status; /函数结果状态类型typedef int _bool; /bool状态类型/* 数 据 结 构 类 型 定 义*/*栈 和 队 列*/* -栈数

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

12、e; /顺序表中元素的数据类型/* -队列动态存储分配初始常量预定义- */#define QUEUE_INIT_SIZE 100 /队列存储空间的初始分配量#define QUEUEINCREMENT 10 /队列存储空间的分配增量#define MAXQUEUESIZE 100 /循环队列最大长度/* -队列顺序存储结构类型定义- */typedef structQElemType *base; /队列初始化动态分配存储空间int front; /对头指针向量，队列不空，指向队头元素int rear; /队尾指针向量，队列不空，指向队尾下一个位置SqQueue; /顺序队列结构类型#end

13、if /* ADT_H_ */3.头文件"DataStructure_StackQueue.h"中部分函数定义如下：#include <stdio.h>#include <malloc.h>#include "ADT.h"/* 功 能 函 数 声 明 区*/* -栈- */栈的基本操作Status InitStack_Sq(SqStack &S); /构造一个空顺序栈SStatus GetTop_Sq(SqStack &S, SElemType &e); /返回栈顶元素eStatus StackEmpty_

14、Sq(SqStack &S); /判断栈S是否为空Status DestoryStack_Sq(SqStack &S); /销毁顺序栈SStatus Push_Sq(SqStack &S, SElemType e); /元素e压入顺序栈Status Pop_Sq(SqStack &S, SElemType &e); /元素e出栈/栈的应用Status DecToBin(void); /十进制数转换为二进制数void Hanoi(int n, char x, char y, char z); /实现Hanoi问题，借助y塔将x塔上的n个圆盘搬移到z塔上/*

15、 -队 列- */队列的基本操作Status InitQueue_Sq(SqQueue &Q); /构造一个空的顺序队列QStatus GetHead_Sq(SqQueue &Q, QElemType &e); /返回顺序队列的队头元素eStatus EnQueue_Sq(SqQueue &Q, QElemType e); /将元素e插入到队列Q中Status DeQueue_Sq(SqQueue &Q, QElemType &e); /将元素e从顺序队列中删除并返回Status InverseQueue_Sq(SqQueue &Q);

16、/实现队列的逆置/* 功 能 函 数 定 义 区*/*栈 结 构 函 数 定 义*/* 函数原型：Status InitStack_Sq(SqStack &S) * 函数功能：构造一个空栈S* 入口参数：SqStack类型的结构体变量S的引用&S* 出口参数：返回函数结果状态*/Status InitStack_Sq(SqStack &S)S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType);if (!S.base) return(OVERFLOW);S.top = S.base;S.stack

17、size = STACK_INIT_SIZE;return OK; /InitStack_Sq/* 函数原型：Status DestoryStack_Sq(SqStack &S)* 函数功能：销毁栈S* 入口参数：SqStack类型的结构体变量S的引用&S* 出口参数：返回函数结果状态*/Status DestoryStack_Sq(SqStack &S)SElemType *p;while (S.base != S.top)p = -S.top;free(p);return OK; /DestoryStack_Sq/* 函数原型：Status Push_Sq(SqSt

18、ack &S, SElemType e)* 函数功能：将元素e入栈* 入口参数：SqStack类型的结构体变量S的引用&S,SElemType类型元素e* 出口参数：返回函数结果状态*/Status Push_Sq(SqStack &S, SElemType e)SElemType *newbase;if (S.top - S.base >= S.stacksize)newbase = (SElemType *)realloc(S.base, (STACKINCREMENT + S.stacksize)*sizeof(SElemType);if (!newbase

19、)return OVERFLOW;S.base = newbase;S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+ = e;return OK; /Push_Sq/* 函数原型：Status Pop_Sq(SqStack &S, SElemType &e)* 函数功能：将元素e出栈* 入口参数：SqStack类型的结构体变量S的引用&S,SElemType类型元素e的引用&e* 出口参数：返回函数结果状态*/Status Pop_Sq(SqStack &S, SElem

20、Type &e)if (S.top = S.base)return ERROR;e = * -S.top;return OK; /Pop_Sq/* 函数原型：Status DecToBin(void)* 函数功能：将十进制数转换为二进制* 入口参数：void* 出口参数：返回函数结果状态*/Status DecToBin(void)LinkStack S;SElemType e;long data;printf(" 请输入待转换的十进制数：");scanf_s("%d", &data);InitStack_L(S);while (data

21、)Push_L(S, data % 2);data = data / 2;printf(" 转换后的二进制数：");while (S->next)Pop_L(S, e);printf("%d", e);printf("n");return OK; /DecToBin/*队 列 结 构 函 数 定 义*/* 函数原型：Status InitQueue_Sq(SqQueue &Q)* 函数功能：构造一个空队列Q* 入口参数：SqQueue类型的结构体变量Q的引用 &Q* 出口参数：返回函数结果状态*/Status I

22、nitQueue_Sq(SqQueue &Q)Q.base = (QElemType *)malloc(QUEUE_INIT_SIZE * sizeof(QElemType);if (!Q.base)return(OVERFLOW);Q.front = Q.rear = 0;return OK; /InitQueue_Sq/* 函数原型：Status GetHead_Sq(SqQueue &Q, QElemType &e)* 函数功能：若队列不空，则返回队头元素e,并返回函数结果状态OK，否则返回ERROR* 入口参数：SqQueue类型的结构体变量Q的引用&Q

23、,QElemType类型元素e的引用&e* 出口参数：返回函数结果状态*/Status GetHead_Sq(SqQueue &Q, QElemType &e)if (Q.front = Q.rear)return ERROR;e = Q.baseQ.rear - 1; /队尾指针向量指向下一个元素return OK; /GetHead_Sq/* 函数原型：Status EnQueue_Sq(SqQueue &Q, QElemType e)* 函数功能：将元素e插入到队列Q中* 入口参数：SqQueue类型的结构体变量Q的引用&Q,QElemType类型元素e* 出口参数：返回函数结果状态*/Status EnQueue_Sq(SqQueue &Q, QElemType e)QElemType *newbase;if (Q.front - Q.rear >= QUEUE_INIT_SIZE)newbase = (QElemType *)realloc(Q.base, (STACKINCREMENT + QUEUE_INIT_SIZE)*siz