电子信息工程学院2013级《数据结构》实验报告
姓名
学号
实验项目 实验内容 栈和队列及其应用（I） 1．采用顺序存储结构，实现栈的存储和基本操作。 栈的抽象数据类型定义参见教材第45页。 栈的顺序存储结构定义参见教材第46页。 2．采用顺序存储结构，实现队列的存储和基本操作 队列的抽象数据类型定义参见教材第59页。 队列的顺序存储结构定义参见教材第64页。 算法设计与程序实现： 算法分析 本次实验主函数采用顺序结构，主函数调用自己编写的头文件DataStructure_LinearList.h中的相关功能函数，完成实验要求。 程序实现步骤： 1、顺序栈结构的基本操作：首先初始化一个顺序栈结构，然后输入需入栈的元素个数N，通过一个循环依次输入N个元素，在输入的同时调用入栈函数,这样就完成了N个元素的入栈操作，随后调用返回栈顶元素的函数，返回栈顶元素，接着通过循环调用出栈函数完成出栈操作，最后销毁栈结构。当然在进行入栈和出栈操作时，会使用判断栈是否为空、对栈进行遍历等操作，这样就实现了对栈的基本操作。 2、栈结构的基本应用：（1）将输入的十进制数转换为二进制数。首先初始化一个栈结构，构造一个空栈，然后输入十进制数N，根据十进制转换为二进制的方法（除二取余法）通过循环判断将每次除二求模的数入栈，接着通过判断栈空条件，依次将栈中的元素出栈，然后输出这样就实现了十进制对二进制的转换，当然其他进制之间的也是如此。（2）Hanoi问题的实现。其主要思想就是递归，在进行递归调用函数本身的时候，参数的传递、变量保存以及函数返回都使用了栈结构（操作系统建立）。 3、顺序队列的基本操作：首先初始化一个空的顺序结构队列，然后输入需入队列的元素个数N，通过一个循环依次输入N个元素，输入的同时调用入队列函数,完成了N个元素的入队列操作，接着调用返回队头元素的函数，返回队头元素，接着通过循环调用出队列函数完成出队列操作，最后销毁顺序队列结构，这样就实现了对栈的基本操作。 此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在主函数中文件包含部分的注释处，核心程序如下： 1.主函数如下： #include \标准输入输出流库文件 #include \ //cmd窗口设置函数头文件 #include \ //数据结构中相关结构体类型定义及相关数据类型定义 #include \ //数据结构第二章线性表中相关函数的定义及声明 using namespace std; 核心程序 电子信息工程学院2013级《数据结构》实验报告
void print(void); int main(void) {
system(\数据结构实验 实验三：栈和队列及其应用（I） \); //设置cmd窗口标题
system(\); //设置控制台窗口的背景色和前景色 system(\); //输出当前的日期
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++) { }
GetTop_Sq(S, e);
cout << \栈顶元素：\ << e << endl; cout << \出栈：\; while ((Pop_Sq(S, e)))
cout << e << \;
cout << endl << \栈的应用：\ << endl << \将十进制数转换为二进制数\ << DecToBin(); //将十进制数转换为二进制数 cout << \汉罗塔问题\ << 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 << \实验内容二：采用顺序存储结构，实现队列的存储和基本操作\ << SqQueue Q; QElemType data;
InitQueue_Sq(Q); //构造一个空队列Q cout << \请输入需入队列的元素个数：N = \;
cin >> e; Push_Sq(S, e);
endl;
endl;
电子信息工程学院2013级《数据结构》实验报告
}
void print(void) { }
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状态类型
/************************************************************ * 数 据 结 构 类 型 定 义
************************************************************/
cout << endl <<
\ << endl;
cin >> count;
cout << \请输入元素：\;
for (int i = 0; i < count; i++) { }
GetHead_Sq(Q, data);
cout << \队首元素：\ << data << endl; cout << \出队列：\; while (DeQueue_Sq(Q, data))
cout << data << \; cout << endl; print(); cout << endl;
cin >> data;
EnQueue_Sq(Q, data);
电子信息工程学院2013级《数据结构》实验报告
/************************栈 和 队 列*************************/ /* ------栈数据类型定义------ */
typedef int SElemType; //顺序表中元素的数据类型
/* ------栈动态存储分配初始常量预定义------ */
#define STACK_INIT_SIZE 100 //栈表存储空间的初始分配量 #define STACKINCREMENT 10 //栈表存储空间的分配增量
/* ------顺序栈结构类型定义------ */ typedef struct {
/* ------队列数据类型定义------ */
typedef int QElemType; //顺序表中元素的数据类型
/* ------队列动态存储分配初始常量预定义------ */
#define QUEUE_INIT_SIZE 100 //队列存储空间的初始分配量 #define QUEUEINCREMENT 10 //队列存储空间的分配增量 #define MAXQUEUESIZE 100 //循环队列最大长度
/* ------队列顺序存储结构类型定义------ */ typedef struct {
QElemType *base; //队列初始化动态分配存储空间
int front; //对头指针向量，队列不空，指向队头元素 int rear; //队尾指针向量，队列不空，指向队尾下一个SElemType * base; //栈底指针 SElemType * top; //栈顶指针
int stacksize; //当前以分配的存储空间
}SqStack; //顺序栈结构类型
位置
}SqQueue; //顺序队列结构类型
#endif /* ADT_H_ */
3.头文件\中部分函数定义如下： #include
/************************************************************ * 功 能 函 数 声 明 区
************************************************************/ /* ---------栈--------- */
电子信息工程学院2013级《数据结构》实验报告
//栈的基本操作
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) { /*
* 函数原型：Status DestoryStack_Sq(SqStack &S) * 函数功能：销毁栈S
* 入口参数：SqStack类型的结构体变量S的引用&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