华中科技大学数据结构课程设计

《华中科技大学数据结构课程设计》由会员分享，可在线阅读，更多相关《华中科技大学数据结构课程设计（33页珍藏版）》请在金锄头文库上搜索。

1、华 中 科 技 大 学 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告课课 程程 设设 计计 报报 告告题目题目：基于堆的优先级队列基于堆的优先级队列ADT 实现及其应用实现及其应用课程名称：课程名称：专业班级：专业班级：学学号：号：姓姓名：名：指导教师：指导教师：报告日期：报告日期：2016 年年 2 月月 25 日日计算机科学与技术学院计算机科学与技术学院华 中 科 技 大 学 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告I任务书任务书设计内容设计内容传统队列是一种符合先插入的元素必须先删除（FIFO）的处理逻辑，这不总是满足应用要求；很多时候需要优先级高

2、的任务先处理（即后插入的可能先删除）。（1）基于堆的概念设计优先级队列(Priority Queue)抽象数据类型，至少包含 Init_PriorityQue, Destroy_PriorityQue, Clear_PriorityQue ， PriorityQue_Insert,PriorityQue_DeletMin, PriorityQue_Empty, PriorityQue_Full 等操作；（2）选择适当的物理存储结构实现优先级队列 ADT; (3)(3)应用优先级队列 ADT 设计与实现一个医院门诊医师与病人看诊服务事件仿真程序，使医师服务效率尽量高。设计要求设计要求（1）仿真事

3、件（如病人到达，病情复杂度/就诊时间，病人离开等）可根据某种概率分布或随机模型生成。（2）要求对各种算法进行理论分析，同时也对实测结果进行统计分析。测试数据要求有一定规模。（3）要求界面整洁、美观，操作方便。参考文献参考文献1 严蔚敏, 吴伟民. 数据结构（C 语言版）. 北京: 清华大学出版社,19972 严蔚敏, 吴伟民, 米宁. 数据结构题集（C 语言版）. 北京: 清华大学出版社,19993 Mark Allen Weiss.Data Structures and Algorithm Analysis in C, 机械工业出版社，2010, 177-192华 中 科 技 大 学 计 算

4、 机 科 学 与 技 术 学 院 课 程 设 计 报 告II目录目录任务书任务书.I1 1 引言引言. 11.1课题背景与意义11.2课程设计的主要研究工作12 系统需求分析与总体设计22.1系统需求分析22.2系统总体设计23系统详细设计系统详细设计 33.1有关数据结构的定义.33.2主要算法设计44系统实现与测试系统实现与测试.114.1系统实现.114.2系统测试.145总结与展望总结与展望185.1全文总结.185.2工作展望.186体会体会 19附录附录 20华 中 科 技 大 学 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告- 1 -1 引言引言1.1 课题背景

5、与意义课题背景与意义数据结构这门课对计算机专业的学生来说其重要性是毋庸置疑的。 不管是在后续的学习还是在今后的工作中，都会经常用到各种数据结构类型，去存储和处理大量的数据。这次课程设计，意在让我们运用所学的数据结构知识，采用优先级队列数据结构去存储病人的就诊信息，模拟医院医生叫号的系统。本课程设计要求基于堆的概念，设计优先级队列抽象数据结构。要尽可能的仿真，更加趋近现实情况， 充分考虑到病人病情复杂度和到达时间， 并以此来确定就诊的优先级。通过这次实践相信自己能够更好的理解优先级队列这种数据结构， 并对堆有更深切的体会，增强自己的实践能力。1.21.2 课程设计的主要研究工作课程设计的主要研究

6、工作首先要写出基于堆的概念的优先级队列(Priority Queue)抽象数据类型，包含InitPriQueue(PriQueue *P)构造优先级队列、DestroyPriQueue(PriQueue *P)销毁优先级队列、ClearPriQueue(PriQueue *P)清空优先级队列、PriQueueInsert(PriQueue*P)在队列中插入元素、DeletMin_PriQueue(PriQueue *P)输出队列中优先级最高元素、 Ergodic(PriQueue * P)遍历输出队列元素、 Status PriQueueEmpty(PriQueue *P)判断队列是否为空、

7、PriQueueFull(PriQueue* P)判断队列是否已满。 除了这些，还有两个堆排序的函数， 一个判断等待时间是否已经超过病人能够等待时间函数，一个删除病人的函数和一个系统定时生成病人信息并重新排列的函数。 有了这些，就可以通过系统时间每隔一段时间自动生成病人的各项信息，包括：病情程度、到达时间和能够等待的时间，并通过这些来得到所有病人的优先级，然后按优先级进行排序，通过叫号每次输出一个优先级最高的病人。剩余的病人会随时间增加优先级变大，以符合实际情况。当病人已等待时间超过他能够等待的时间时，会删除这个病人及其各项信息。随着时间流逝，病人不断增多，来模拟真实的就诊情景。华 中 科 技

8、 大 学 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告- 2 -2 系统需求分析与总体设计系统需求分析与总体设计2.1 系统需求分析系统需求分析我设计的这个系统如若成功，应该能够随时间变化，自动生成病人的初始优先级，到达时间和能够等待的时间。手动模拟医生叫号，这时优先级最高的病人出队列，并能够随时查询当前的就诊信息，把每个病人的信息依次输出，还能够统计已经就诊的病人和未就诊就离开的病人及其比例， 还能够清空当前产生的所有的病人信息。程序运行时，每隔 10 秒不断产生新的病人及其信息，按下 1 手动叫号，按下 2 查询当前还在排队的病人信息， 按下 3 统计所有就诊病人和未就诊

9、离开的病人比例，按下 4 清空当前所有排队的病人，按下 0 退出系统。2.2 系统系统总体设计总体设计我设计的这个程序中，用户只是承担一个医生叫号的角色，病人的产生过程直接让计算机代替实现了，并模拟地产生了病人的病情优先级（也是随机的），每过一段时间， 在队列中的病人的优先级会呈线性增长， 来模拟现实中等待越久，优先级越高的情景，而且还有病人最多能够等待的一个时间限制（随机产生），当他实际等待的时间超过这个限值，就会在队列中删除他，并把他算入未就诊就离开的人中，以便在统计就诊信息功能中更好地进行统计。总体来说，我设计的这个系统中计算机扮演的角色偏多，既产生病人，又产生各个病人的各项信息，还让他

10、们的优先级随时间发生变化。用户只负责叫号和查询的功能。具体见下图：查询叫号用户计算机产生数据存储数据处理数据华 中 科 技 大 学 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告- 3 -3 系统详细设计系统详细设计3.1 有关数据结构的定义有关数据结构的定义主要的数据结构类型定义：整个系统的病人用一个优先级队列存储， 相当于所有病人及其信息都包含在如下PriQueue结构当中，其中info又是一个结构，每个病人的所有信息都是info类型的结构。typedef struct int front;/头指针int rear;/尾指针info *base;/分配内存基地址int fi

11、nish_cure;/治疗完成的人数int no_cure;/未治疗离开的人数PriQueue;typedef struct float key;/病情复杂度优先级标记int num;/病人编号time_t ari_time;/病人到达时间int wai_time;/病人等待时间info;当要统计所有病人信息的时候， 要用到PriQueue这个结构里面的front、 rear指针；finish_cure；no_cure数据项。当要对单个病人的优先级进行改变和其它操作时， 要用到info这个结构里面的key；num；ari_time；wai_time数据项。华 中 科 技 大 学 计 算 机 科

12、 学 与 技 术 学 院 课 程 设 计 报 告- 4 -3.2 主要算法设计主要算法设计( (给出部分复杂流程图给出部分复杂流程图) )（1）InitPriQueue(PriQueue *P)/*函数名称：InitPriQueue操作结果：构造一个空优先级队列 P。*/流程图：（2）DestroyPriQueue(PriQueue *P)/*函数名称：DestroyPriQueue初始条件：优先级队列 P 存在。操作结果：将优先级队列 P 销毁，不再存在。*/（3）ClearPriQueue(PriQueue *P)/*函数名称：ClearPriQueue初始条件：优先级队列 P 存在。操作

13、结果：将优先级队列 P 清为空队列。华 中 科 技 大 学 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告- 5 -*/流程图：（4）PriQueueInsert(PriQueue *P)/*函数名称：PriQueueInsert初始条件：优先级队列 P 存在。操作结果：插入病人信息到优先级队列 P 中。*/流程图：（5）DeletMin_PriQueue(PriQueue *P)/*华 中 科 技 大 学 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告- 6 -函数名称：DeletMin_PriQueue(PriQueue *P)初始条件：优先级队列 P 存在

14、并且非空。操作结果：叫号，输出优先级最高的病人信息。*/流程图：（6）Ergodic(PriQueue * P)/*函数名称：Ergodic初始条件：优先级队列 Q 存在。操作结果：查询并显示当前所有排队病人。*/（7）cure_Info(PriQueue * P)/*函数名称：cure_Info华 中 科 技 大 学 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告- 7 -初始条件：优先级队列 Q 存在。操作结果：统计当前就诊信息。*/（8）PriQueueEmpty(PriQueue * P)/*函数名称：PriQueueEmpty初始条件：优先级队列 Q 存在。操作结果：

15、若优先级队列 Q 为空队列，返回 TRUE，否则返回 FALSE。*/（9）PriQueueFull(PriQueue* P)/*函数名称：PriQueueFull初始条件：优先级队列 P 存在。操作结果：若优先级队列 P 为满队列，返回 TRUE，否则返回 FALSE。*/（10）HeapSort(PriQueue * P)/*函数名称：HeapSort初始条件：优先级队列 P 存在。操作结果：对队列 P 进行堆排序。*/流程图：华 中 科 技 大 学 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告- 8 -（11）HeapAdjust(PriQueue * P,int s,

16、int m)/*函数名称：HeapAdjust初始条件：优先级队列 P 存在。操作结果：使 P.basesm成为一个小顶堆。*/华 中 科 技 大 学 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告- 9 -流程图：华 中 科 技 大 学 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告- 10 -（12）Judge_Wait(PriQueue * P)/*函数名称：Judge_Wait初始条件：优先级队列P存在。操作结果：判断病人等待时间是否已过。*/流程图：（13）Leave(PriQueue * P,int i)/*函数名称：Leave初始条件：优先级队列P存在。操作结果：删除病人信息。*/华 中 科 技 大 学 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告- 11 -4 系统实现与测试系统实现与测试4.1 系统实现系统实现4.1.14.1.1 系统实现环境系统实现环境硬件环境：CPU：intel 酷睿 i5-4210U。内存：4GB。硬盘：500GB。软