姓名学号
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, 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 int Status; //函数结果状态类型
typedef int_bool; //bool状态类型
/************************************************************
* 数据结构类型定义
************************************************************/
/************************栈和队列*************************/
/* ------栈数据类型定义------ */
typedef int SElemType; //顺序表中元素的数据类型
/* ------栈动态存储分配初始常量预定义------ */
#define STACK_INIT_SIZE 100 //栈表存储空间的初始分配量
#define STACKINCREMENT 10 //栈表存储空间的分配增量
/* ------顺序栈结构类型定义------ */
typedef struct
{
SElemType * base; //栈底指针
SElemType * top; //栈顶指针
int stacksize; //当前以分配的存储空间
}SqStack; //顺序栈结构类型
/* ------队列数据类型定义------ */
typedef int QElemType; //顺序表中元素的数据类型
/* ------队列动态存储分配初始常量预定义------ */
#define QUEUE_INIT_SIZE 100 //队列存储空间的初始分配量
#define QUEUEINCREMENT 10 //队列存储空间的分配增量
#define MAXQUEUESIZE 100 //循环队列最大长度
/* ------队列顺序存储结构类型定义------ */
typedef struct
{
QElemType *base; //队列初始化动态分配存储空间
int front; //对头指针向量，队列不空，指向队头元素int rear; //队尾指针向量，队列不空，指向队尾下一个位置
}SqQueue; //顺序队列结构类型
#endif/* ADT_H_ */
3.头文件"DataStructure_StackQueue.h"中部分函数定义如下：
#include<stdio.h>
#include<malloc.h>
#include"ADT.h"
/************************************************************
* 功能函数声明区
************************************************************/
/* ---------栈--------- */
//栈的基本操作
Status InitStack_Sq(SqStack &S); //构造一个空顺序栈S
Status GetTop_Sq(SqStack &S, SElemType &e); //返回栈顶元素e
Status StackEmpty_Sq(SqStack &S); //判断栈S是否为空
Status DestoryStack_Sq(SqStack &S); //销毁顺序栈S
Status 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塔上
/* ---------队列--------- */
//队列的基本操作
Status InitQueue_Sq(SqQueue &Q); //构造一个空的顺序队列Q Status GetHead_Sq(SqQueue &Q, QElemType &e); //返回顺序队列的队头元素e Status EnQueue_Sq(SqQueue &Q, QElemType e); //将元素e插入到队列Q中
Status DeQueue_Sq(SqQueue &Q, QElemType &e); //将元素e从顺序队列中删除并返回
Status InverseQueue_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(SElemType));
if (!S.base)
return(OVERFLOW);
S.top = S.base;
S.stacksize = 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(SqStack &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)
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, SElemType &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)
{
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 InitQueue_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,QElemType类型元素e的引用&e * 出口参数：返回函数结果状态
*/
Status GetHead_Sq(SqQueue &Q, QElemType &e)
{
if (Q.front == Q.rear)
return ERROR;
e = Q.base[Q.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)*sizeof(QElemType));
if (!newbase)
return OVERFLOW;
Q.base = newbase;
}
Q.base[Q.rear++] = e;
return OK;
} //EnQueue_Sq
/*
* 函数原型：Status DeQueue_Sq(SqQueue &S, QElemType &e)
* 函数功能：将元素e从队列中删除并返回
* 入口参数：SqQueue类型的结构体变量Q的引用&Q,QElemType类型元素e的引用&e
* 出口参数：返回函数结果状态
*/
Status DeQueue_Sq(SqQueue &Q, QElemType &e)
{
if (Q.front == Q.rear)
return ERROR;
e = Q.base[Q.front++];
return OK;
} //DeQueue_Sq
运行结果
实验总结1、此次实验完成了对顺序存储结构的栈和队列的基本操作及简单应用，加深了对课本知识的理解和掌握。
此次实验相对较容易，但却是很基础的，
在以后的二叉树、图等高级数据结构都需要用到它，所以栈和队列是非常重
要的，有些细节部分是值得高度重视的，也是容易出错的地方。
2、栈顶指针指向的是栈顶元素的下一个位置，在进行出栈操作时，应先
将栈顶指针向量自减，指向栈顶元素，才能保证栈中元素正确出栈。
当进行
连续入队列操作时，要改变的是队尾指针的指向，而不是队头指针；虽然初
始状态下队头指针和队尾指针都指向头一个元素，所以做第一个插入时关系
不大，但第二次开始就一定要改变尾指针。
3．因为栈是希望当有需要进行入栈操作时就一定能够入栈，一般来说，初始化顺序空栈时，不应限定栈的最大容量，但在顺序结构当中存储空间是
由程序员需要时事先指定分配的，一个合理的做法就是：先为栈分配一个基
本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。
