admin 管理员组

文章数量: 887021


2024年2月6日发(作者:怎么把指令汇编)

数据结构课程设计

设计说明书

堆排序的算法的实现

学生姓名

学班成号

指导教师

计算机科学与技术系

2011年3月4 日

数据结构课程设计评阅书

题目

学生姓名

堆排序原理的算法的实现

学号

指导教师评语

成绩: 指导教师签名: 年 月 日

答辩教师评语

成绩: 答辩教师签名: 年 月 日

教研室意见

成绩: 室主任签名: 年 月 日

注:指导教师成绩60%,答辩成绩40%,总成绩合成后按五级制记入。

课程设计任务书

2010 —2011 学年第 二 学期

专业: 学号: 姓名:

课程设计名称: 数据结构课程设计

设计题目: 堆排序算法的实现

完成期限:自 2011年 2 月 19 日至 2011 年 3 月 4 日共 2 周

设计依据、要求及主要内容(可另加附页):

堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。如关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1)和(2),故它们均是堆。

大根堆和小根堆:根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆,又称最小堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆,又称最大堆。注意:①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆(Binary Heap),

大根堆排序的基本思想:

① 先将初始文件]建成一个大根堆,此堆为初始的无序区。

② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区-1]和有序区R[n],且满足-1].keys≤R[n].key。

③由于交换后新的根R[1]可能违反堆性质,故应将当前无序区-1]调整为堆。然后再次将-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区-2]和有序区],且仍满足关系-2].keys≤].keys,同样要将-2]调整为堆。

要求 :(1)给出一个符合堆序列的一组数,能够建立大根堆和小根堆。

(2)界面友好,可操作性强。

(3)能够实现数据个数的变化输入,并建立相应的堆。

指导教师(签字): 教研室主任(签字):

批准日期: 年 月 日

摘 要

设计了一个堆排序算法实现的程序,此程序具有排序的功能,能够对输入的任何数字进行处理之后,有序的输出。在设计之前,首先要明白什么是堆,以及堆排序的原理,明白了原理之后,结合之前所掌握的C++编程知识,分部分进行编译,最后再进行组合,完成此程序之后,可视化界面比较清晰,操作比较简单,易于为用户接受。

关键词:堆排序;大顶堆;筛选

目 录

1. 课题描述 .............................................................. 1

2. 问题分析和任务定义 .................................................... 2

3. 逻辑设计 .............................................................. 3

4. 程序编码 .............................................................. 6

5. 结果分析 .............................................................. 8

6. 总结 .................................................................

参考文献 .................................................................

10

11

1. 课题描述

本课题是利用堆排序的算法原理对数据进行排序,使所输入的数据以递减或者递增的方式输出,主要是利用堆排序算法进行设计,设计筛选函数,和排序函数,以及对这些函数的综合运用。1

2. 问题分析和任务定义

本次程序设计,主要设计的问题是如何利用堆排序原理进行设计,应该结合书本所含有的理论,结合一些程序实例,进行完成,本次设计的任务是,编一个能够实现堆排序算法的程序,并设计一个可视化界面,此次程序设计过程中,有两大模块,一个是筛选函数,另一个是排序函数。2

3. 逻辑设计

运用数据结构中所学的函数进行流程图设计。

堆排序主函数

beginintarray[100]={0};inti=0i

结束

3.1堆排序主函数流程图yNY++k

3

大顶堆筛选函数

begininttmp=p[r];j=2*r+1j<=len-1Nj=p[j]Side by Sidep[r]=p[j];j=2*j+1p[r]=tmp;

结束

3.2堆排序筛选函数

YNY

4

大顶堆排序函数

begininti,j;i=len/2-1i>=0N BigHeapAdjust(p,I,len);p[0]^=p[len-1];j=len-1j>1BigHeapAdjust(p,0,j); 结束Y--iNY--j

3.3堆排序排序函数5

4. 程序编码

#include

#include

using namespace std;

void BigHeapAdjust(int *p, int r, int len);

void BigHeapSort(int *p, int len);

int main()

{

int array[1000] = {0};

int n;

printf("请输入排序元素的个数:");

scanf("%d", &n);

printf("请输入要排序的元素:");

for(int i=0; i

scanf("%d", array+i);

BigHeapSort(array, n);

printf("结果是:");

for(int k=0; k

printf("%d ", array[k]);

getchar();

getchar();

getchar();

return 0;

}

void BigHeapAdjust(int *p, int r, int len)

{

int tmp = p[r];

int j;

for(j=2*r+1; j<=len-1; j=2*j+1)

{

if(j=p[j])

++j;

if(tmp >= p[j])

break;

p[r] = p[j];

r = j;

6

}

p[r] = tmp;

}

void BigHeapSort(int *p, int len)

{

int i,j;

for(i=len/2-1; i>=0; --i)

BigHeapAdjust(p, i, len);

p[0] ^= p[len-1];

p[len-1] ^= p[0];

p[0] ^= p[len-1];

for(j=len-1; j>1; --j)

{

BigHeapAdjust(p, 0, j);

p[0] ^= p[j-1];

p[j-1] ^= p[0];

p[0] ^= p[j-1];

}

}

7

5. 结果分析

5.1.输入界面

5.1输入要排序的函数个数

5.2输入元素的个数

5.2输入所要排序的函数

8

5.3 程序运行结果

5.3函数结果输出

5.4函数异常输入

5.4函数异常输出结果

9

6. 总结

在本次程序设计中,运用了堆排序的基本原理,在首先了解什么事堆的情况下,然后结合所学的知识进行编程,在编程的过程中,首先要了解大顶堆,小顶堆的定义,以及如何利用堆排序的原理进行排序,在设计程序之前,应先画出流程图,在画图的过程中,应该正确了解各个图形的意义,不能错用,对于经常使用的选择,判断等的特殊图形要正确使用,以及箭头所指的方向,都要仔细,在完成了对流程图的设计后,就要根据流程图进行编程,在编程的时候,首先要明白程序的主题函数,先从主函数开始,结合流程图进行编译,正确使用特殊语句,以及关键字,在这过程要用到for循环语句,最重要的就是要写出正确的判断语句,搞清楚程序的结束的点,在完成主函数的编译之后,就要进行子函数的编译,次函数包括两个子函数,一个是大顶堆的筛选,另一个是大顶堆的排序,在大顶堆的筛选的时候,要明白堆排序的实质,就是从最后一个非叶子节点开始,从它的左右子树开始比较,顺着子树较大的方向往父节点平移,最后和序列的最后一个数据进行交换,把它放置在闲置的空间内,在进行大顶堆的排序的时候,对上面的交换完成之后,先找出一个最大的,然后对其余的数据进行重复的比较,方法和大顶堆的筛选一样,直至待排序的数据按顺序输出。在编程的完成之后,要进行仔细的检验,找出错误,进行多次验证,确保此程序准确无误,并且要使程序简单明了,便于操作者使用方便。在进行了此次程序设计之后,明白了如何利用堆排序原理进行对数据的排序,对以前所学的知识进行了巩固,增加了实践的经验。

10

参考文献

[1] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2002

[2] 李春葆.数据结构(C语言版)习题与解析[M]. 北京:清华大学出版社,2002

[3] 钱能.C++程序设计教程[M]. 北京:清华大学出版社,2003

[4] 谭浩强.C程序设计教程.北京:清华大学出版社2007

[5] 李建忠. 大学计算机基础. 西北大学出版社2005

[6] 罗建军 朱丹军 刘路放.C++程序设计教程(第2版).北京:高等教育出版社

11


本文标签: 进行 程序 函数 设计 排序