数据结构课程设计报告

沈阳航空航天大学

课 程 设 计 报 告

课程设计名称：数据结构课程设计 课程设计题目：应用堆实现一个优先队列

院（系）：计算机学院 专 业：计算机科学与技术 班 级：14010103 学 号：2011040101137 姓 名： 张宝祥 指导教师： 郑志勇

沈阳航空航天大学课程设计报告

目 录

第一章 题目功能要求和题目分析 .......................................................................... - 1 - 1.1 题目要求 .......................................................................................................... - 1 - 1.2 基本功能要求 .................................................................................................. - 1 - 1.3 题目分析 ............................................................................................................ - 1 - 第二章 程序设计 ...................................................................................................... - 2 - 2.1 概要设计 .......................................................................................................... - 2 - 2.1.1总体模块图 .................................................................................................. - 2 - 2.1.2 主要模块功能说明 ..................................................................................... - 2 - 2.2 详细设计 .......................................................................................................... - 3 - 2.2.1 数据结构 ..................................................................................................... - 3 - 2.2.2 数据结构用法说明 ..................................................................................... - 3 - 2.2.3函数描述及流程图 ...................................................................................... - 5 - 第三章 程序测试/运行的结果 ............................................................................... - 10 - 参考文献 .................................................................................................................... - 13 - 附 录（关键部分程序清单） .............................................................................. - 14 -

I

沈阳航空航天大学课程设计报告

第一章 题目功能要求和题目分析

1.1 题目要求

设计要求以堆作为辅助结构实现一个优先队列。要将堆结构嵌入到队列结构中，以作为其数据组织的以部分。此处由于要用堆实现队列，所以堆结构的储存表示要求用数组。

要求：

1. 设计并实现优先队列的数据结构，包括其上的基本操作；

2. 以堆结构为辅助结构实现优先队列的储存并实现其上的基本操作； 3. 实现优先队列的出队、入队操作；

4. 给出动态演示过程（选作）；

1.2 基本功能要求

1. Insert(S,x)：将元素x插入到集合S（本题为数组A），并且把A调整为小头

椎。

2. Minimum(S)：返回S中的最小元素，并且将A调整为小顶椎。 3. Extract_Min(S)：删除S中的最小关键字。

1.3 题目分析

题目要求应用对实现一个优先队列。优先队列是不同于先进先出队列的另一种队列，每次从队列中取出的是具有最高优先权的元素，它可以用于很多场合的数据结构。这个程序可以用整型数组作为储存结构，通过堆排序对储存好的数进行排序，生成一个小顶堆实现优先队列的功能，并且该程序满足对优先队列进行入队、出队以及返回队列最小值的操作。

- 1 -

沈阳航空航天大学课程设计报告

第二章 程序设计

2.1 概要设计

2.1.1总体模块图

应用对实现一个优先队列 创建队列功能模块 1.插入功能模块： 2. 删除功能模块： 3. 输出功能模块： 4. 创建队列功能模块：

插入（入队）功能模块删除（出队）功能模块返回最小值功能模输出队列功能模块

2.1.2 主要模块功能说明

Insert(A,x) 将元素x插入到数组A，并且把A调整为小顶椎。

Extract_Min(A)，删除数组A中的最小关键字，并且将A调整为小顶椎。

Print(A)把集合S中的元素按小顶堆输出。

CreateHeap(A) 对于数组A中元素创建小顶椎。 5. 返回最小值功能模块：

图1系统功能模块结构图

- 2 -

沈阳航空航天大学课程设计报告

Minimun(A) 返回集合A中最小的值。

2.2 详细设计

2.2.1 数据结构

优先队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素，按照题意可知，建立了小顶堆，元素越小优先级越高。

堆的定义：若含n个元素的序列 {k1,k2 ,…,kn } ，满足下列关系时称作\小顶堆\或\大顶堆\。\堆顶\元素为序列中的\最小值\或\最大值\。

?ki??k2i(i?1,2,...n/2)??ki??k2i?1

堆举例：{12,36,24,85,47,30,53,91}

图2 小顶堆

可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值 结合题目要求

2.2.2 数据结构用法说明

从无序序列的第[n/2]个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选。

例如：无序序列建成一个小顶堆{49，38，65，97，76，13，27，49}

- 3 -

本文来源：https://www.bwwdw.com/article/zcbh.html