实验三 栈和队列及其应用(I) - 图文
更新时间:2024-03-02 11:06:01 阅读量: 综合文库 文档下载
- 实验三中推荐度:
- 相关推荐
电子信息工程学院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
正在阅读:
实验三 栈和队列及其应用(I) - 图文03-02
人事管理的医院营销思路探索08-19
2019秋德育处前半期工作总结03-05
公园说明书08-10
2015年浙江省造价员计价考试真题01-06
2017年中国健身房市场调研及发展现状分析(目录)07-06
新型肥料推广要找对三个好方法03-12
最新日本料理营销策略大全汇编05-02
医技科室为临床一线服务的规定01-27
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 队列
- 及其
- 实验
- 图文
- 应用
- labview大作业
- 材料物理
- 魅族mx3和小米3对比 - 图文
- 扎实开展主题教育实践活动,进一步明确执业使命
- 动画运动规律,结课考试复习范围总结
- 机械制造考试模拟习题3
- 米亚罗九年一贯制学校2013-2014学年度下期教师培训计划
- 40108面设计说明书(全)
- 芳纶蜂窝项目可行性研究报告
- 门机拆除安装方案DOC - 图文
- “90后”消费市场的体育品牌观
- 2010届高考政治二轮热点复习7
- 2t燃气锅炉成本分析
- 西方经济学单选题
- 3DSMAX书上思考题和一些简答题
- 2018届安徽省皖南八校高三第二次联考化学试题及答案
- 期权的波动率及波动率交易
- 2016-2017学年福建省泉州市南安市七年级数学上期末教学质量监测
- 中国农业大学植物营养学 知识点
- 党风廉政建设和反腐败工作暨惩防体系工作总结