第1页 / 共49页
第2页 / 共49页
第3页 / 共49页
第4页 / 共49页
第5页 / 共49页
第6页 / 共49页
第7页 / 共49页
第8页 / 共49页
数据结构课程设计报告.docx
一．应用小大根交替堆实现双端优先队列
1.需求描述
1.1 问题描述
1.2 基本要求
1.3输入要求
1.3.1菜单选择
2.成绩查询功能选择
1.3.2测试小大根交替堆的基本操作
1.建立小大根交替堆
1.3.3根据成绩查询学生信息
1.查询最高/最低成绩的学生信息
1.4输出要求
1.4.1测试小大根交替堆的基本操作
3.删除最大值/最小值
4.得到最大值/最小值
1.4.2根据成绩查询学生信息
2.设计
2.1 结构设计
2.1.1系统模块结构
输出堆结构模块
2.1.2问题的整体思路
2.2 数据及数据类(型)定义
2.2.1类设计
1.双端优先队列抽象类
2.小大根交替堆类设计
3.学生信息类设计
2.2.2全局变量
2.2.3除类中成员函数以外的函数设计
2.3.算法设计及分析
2.3.1初始化模块
2.3.2菜单模块
2.3.3输入输出模块
2.3.4得到最值模块
2.3.5删除最值模块
2.3.6插入模块
2.3.7成绩查询模块
2.3.8输出堆结构模块
3. 测试结果
3.2得到最值模块测试结果
3.3删除最值模块测试结果
3.4插入模块测试结果
3.5成绩查询模块测试结果
4. 分析与探讨
5. 附录：实现源代码
二．虚拟文件目录系统
1.需求描述
1.1 问题描述
1.2基本要求
1.3输入要求
1.3.1菜单选择
1.3.2基本操作
1.4输出要求
1.4.1虚拟文件目录的基本操作
1.dir操作
2.cd 操作
3.cd str 操作
4.cd ..操作
5.mkdir str操作
在当前目录下创建一个名为str的子目录
6.mkfile str操作
在当前目录下创建一个名为str的文件
7.delete str
8.size操作
1.4.2虚拟文件目录保存与载入的操作
1.load *.dat 操作
2.save *.dat 操作
2.设计
2.1 结构设计
2.1.1系统模块结构
2.1.2问题的整体思路
2.2 数据及数据类(型)定义
2.2.1类设计
1.根节点结构
2.目录结构
2.2.2除类中成员函数以外的函数设计
2.3.算法设计及分析
2.3.1 Dir模块
2.3.2 Cd模块
2.3.3 Cd ..模块
2.3.4 Cd str模块
2.3.5 Mkdir模块
2.3.6 Mkfile模块
2.3.7 Delete模块
2.3.8 Save模块
3. 测试结果
4. 分析与探讨
5. 附录：实现源代码
结论与体会
山东大学计算机科学与技术学院
数据结构课程设计报告
日期：2017.4-2017.6
课程设计题目：应用小大根交替堆实现双端优先队列&&虚拟文件目录系统
上机学时：32
基本要求：
应用小大根交替堆实现双端优先队列：
1. 给出双端优先队列的 ADT 描述，包括优先队列的逻辑结构及基本操作；
2. 给出小大根交替堆的 ADT 描述，并实现该 ADT；
3. 以小大根交替堆为辅助结构实现双端优先队列的存储表示并实现基本操作；
4. 应用双端优先队列的 ADT 实现依据学生成绩对学生信息的查询；
5. 学生信息存放在文本文件中(格式自定，内容自行输入)。
虚拟文件目录系统：
1. 描述并实现 CatalogTree 的 ADT，包括其上的基本操作：如插入一个结点，寻找一
个节点，返回一个结点的最左儿子等(具体情况依据应用自定)；
2. 应用 CatalogTree 的 ADT 实现一个完成文件目录系统的 shell 应用程序；
3. 该 Shell 是一个不断等待用户输入命令的解释程序，根据用户输入的命令来完成相
关操作，直到退出(quit),命令名及其含义如上所述。
4. 目录树结构可以保存(save)到文件中，也可以从文件中读出(load *.dat);
5. Dir 命令的结果应能够区分是子目录还是文件；
6. 应对命令 4)-7)中的 str 区分是绝对路径还是相对路径。
硬件环境：
联想 PC s410
软件环境：
Windows 10 + Vistual Studio 2015
报告内容：
目录
一．应用小大根交替堆实现双端优先队列............................................................... 3
1.需求描述.................................................................................................................... 3
1.1 问题描述........................................................................................................ 3
1.2 基本要求........................................................................................................ 3
1.3 输入要求......................................................................................................... 3
1.3.1 菜单选择.............................................................................................. 3
1.3.2 测试小大根交替堆的基本操作.......................................................... 5
1.3.3 根据成绩查询学生信息...................................................................... 6
1.4 输出要求......................................................................................................... 8
1.4.1 测试小大根交替堆的基本操作.......................................................... 8
1.4.2 根据成绩查询学生信息.................................................................... 10
2.设计.......................................................................................................................... 11
2.1 结构设计...................................................................................................... 11
2.1.1 系统模块结构.................................................................................... 11
2.1.2 问题的整体思路................................................................................ 13
2.2 数据及数据类(型)定义................................................................................13
2.2.1 类设计................................................................................................ 13
2.2.2 全局变量............................................................................................ 16
2.2.3 除类中成员函数以外的函数设计.................................................... 16
2.3.算法设计及分析........................................................................................... 16
2.3.1 初始化模块........................................................................................ 16
2.3.2 菜单模块............................................................................................ 16
2.3.3 输入输出模块.................................................................................... 17
2.3.4 得到最值模块.................................................................................... 17
2.3.5 删除最值模块.................................................................................... 17
2.3.6 插入模块............................................................................................ 18
2.3.7 成绩查询模块.................................................................................... 19
2.3.8 输出堆结构模块................................................................................ 20
3. 测试结果................................................................................................................ 20
3.1 建堆模块测试结果...................................................................................... 20
3.2 得到最值模块测试结果............................................................................... 21
3.3 删除最值模块测试结果............................................................................... 21
3.4 插入模块测试结果....................................................................................... 22
3.5 成绩查询模块测试结果............................................................................... 22
4. 分析与探讨............................................................................................................ 26
5. 附录：实现源代码................................................................................................ 26
二．虚拟文件目录系统............................................................................................. 27
1.需求描述.................................................................................................................. 27
1.1 问题描述...................................................................................................... 27
1.2 基本要求....................................................................................................28
1.3 输入要求....................................................................................................... 28
1.3.1 菜单选择............................................................................................ 28
1.3.2 基本操作............................................................................................ 28
1.4 输出要求....................................................................................................... 33
1.4.1 虚拟文件目录的基本操作................................................................ 33
1.4.2 虚拟文件目录保存与载入的操作.................................................... 38
2.设计.......................................................................................................................... 39
2.1 结构设计...................................................................................................... 39
2.1.1 系统模块结构.................................................................................... 39
2.1.2 问题的整体思路................................................................................ 40
2.2 数据及数据类(型)定义................................................................................40
2.2.1 类设计................................................................................................ 40
2.2.2 除类中成员函数以外的函数设计.................................................... 41
2.3.算法设计及分析........................................................................................... 41
3. 测试结果................................................................................................................ 44
4. 分析与探讨............................................................................................................ 48
5. 附录：实现源代码................................................................................................ 48
结论与体会................................................................................................................. 49
一．应用小大根交替堆实现双端优先队列
1.需求描述
1.1 问题描述
双端优先队列是一个支持如下操作的数据结构：
Insert(S,x) – 将元素 x 插入集合 S
Extract-Min(S) – 删除 S 中最小关键字
Extract-Max(S) – 删除 S 中最大关键字
可用小大根交替堆来实现对上述三个操作的支持。小大根交替堆是一个满足如
下小大根交替条件的完全二叉树：如果该二叉树不空，那么其上的每个元素都有一
个称为关键字的域，且针对该关键字，二元树按层次形成了小大根交替的形式，即
对于小大根交替堆中的任何一个结点 x，如果 x 位于小根层次，那么 x 就是以 x 为
根节点的二元树中键值最小的结点，并称该结点为一个小根结点。同样的道理，如
果 x 位于大根层次，那么 x 就是以 x 为根节点的二元树中键值最大的节点，并称该
节点为大根结点。在小大根交替堆中根结点位于小根层次。
1.2 基本要求
1. 给出双端优先队列的 ADT 描述，包括优先队列的逻辑结构及基本操作；
2. 给出小大根交替堆的 ADT 描述，并实现该 ADT；
3. 以小大根交替堆为辅助结构实现双端优先队列的存储表示并实现基本操
作；
4. 应用双端优先队列的 ADT 实现依据学生成绩对学生信息的查询；
5. 学生信息存放在文本文件中(格式自定，内容自行输入)。
1.3 输入要求
1.3.1 菜单选择
1.菜单功能选择
输入形式：一个字符
输入数据例子：u
截图：
2.成绩查询功能选择
输入形式：一个数字（0~7）
输入数据例子：1
截图：
1.3.2 测试小大根交替堆的基本操作
1.建立小大根交替堆
输入形式：
任意数目的整数
输入数据例子：
建立小大根交替堆：
请输入关键值：
10 20 30 3 39 39 -2 23 3
截图：
.插入元素
输入形式：一个整数
输入数据例子：33
截图：
2
3.删除最大值/最小值
只需选择菜单选项即可
4.得到最大值/最小值
只需选择菜单选项即可
1.3.3 根据成绩查询学生信息
1.查询最高/最低成绩的学生信息
输入菜单选项即可
2.根据具体成绩对学生信息进行查询
输入一个整数（0~100） 例如： 76
3.查询第/前几名的学生信息
输入一个整数
例如：输入名次（-1 结束查询）：4
4.查询倒/后几名的学生信息
输入一个整数
例如：输入名次（-1 结束查询）： 4
1.4 输出要求
1.4.1 测试小大根交替堆的基本操作
1.建立小大根交替堆
输出形式：建立的堆结构
输出数据截图：
2.插入元素
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
