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

华 中 科 技 大 学 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告 课 程 设 计 报 告 题目： 基于堆的优先级队列 ADT实现及其应用 课程名称： 专业班级： 学 号： 姓 名： 指导教师： 报告日期： 2016年2月25日 计算机科学与技术学院 PAGE \* MERGEFORMAT II 任务书 设计内容 传统队列是一种符合先插入的元素必须先删除（FIFO）的处理逻辑，这不总是满足应用要求；很多时候需要优先级高的任务先处理（即后插入的可能先删除）。（1）基于堆的概念设计优先级队列(Priority Queue)抽象数据类型，至少包含Init_PriorityQue, Destroy_PriorityQue, Clear_PriorityQue，PriorityQue_Insert, PriorityQue_DeletMin, PriorityQue_Empty, PriorityQue_Full等操作；（2）选择适当的物理存储结构实现优先级队列ADT; (3)应用优先级队列ADT设计与实现一个医院门诊医师与病人看诊服务事件仿真程序，使医师服务效率尽量高。 设计要求 （1）仿真事件（如病人到达，病情复杂度/就诊时间，病人离开等）可根据某种概率分布或随机模型生成。 （2）要求对各种算法进行理论分析，同时也对实测结果进行统计分析。测试数据要求有一定规模。 （3）要求界面整洁、美观，操作方便。 参考文献 [1] 严蔚敏, 吴伟民. 数据结构（C语言版）. 北京: 清华大学出版社,1997 [2] 严蔚敏, 吴伟民, 米宁. 数据结构题集（C语言版）. 北京: 清华大学出版社,1999 [3] Mark Allen Weiss.Data Structures and Algorithm Analysis in C, 机械工业出版社，2010, 177-192 目录 任务书  = 1 \* ROMAN I 1引言 1 1.1课题背景与意义 1 1.2课程设计的主要研究工作 1 2系统需求分析与总体设计 2 2.1系统需求分析 2 2.2系统总体设计 2 3系统详细设计 3 3.1有关数据结构的定义 3 3.2主要算法设计 4 4系统实现与测试 11 4.1系统实现 11 4.2系统测试 14 5总结与展望 18 5.1全文总结 18 5.2工作展望 18 6体会 19 附录 20 华 中 科 技 大 学 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告 PAGE \* MERGEFORMAT- 30 - 1引言 1.1课题背景与意义 数据结构这门课对计算机专业的学生来说其重要性是毋庸置疑的。不管是在后续的学习还是在今后的工作中，都会经常用到各种数据结构类型，去存储和处理大量的数据。这次课程设计，意在让我们运用所学的数据结构知识，采用优先级队列数据结构去存储病人的就诊信息，模拟医院医生叫号的系统。本课程设计要求基于堆的概念，设计优先级队列抽象数据结构。要尽可能的仿真，更加趋近现实情况，充分考虑到病人病情复杂度和到达时间，并以此来确定就诊的优先级。通过这次实践相信自己能够更好的理解优先级队列这种数据结构，并对堆有更深切的体会，增强自己的实践能力。 1.2课程设计的主要研究工作 首先要写出基于堆的概念的优先级队列(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)判断队列是否为空、PriQueueFull(PriQueue * P)判断队列是否已满。除了这些，还有两个堆排序的函数，一个判断等待时间是否已经超过病人能够等待时间函数，一个删除病人的函数和一个系统定时生成病人信息并重新排列的函数。有了这些，就可以通过系统时间每隔一段时间自动生成病人的各项信息，包括：病情程度、到达时间和能够等待的时间，并通过这些来得到所有病人的优先级，然后按优先级进