数据结构课程设计

实习报告。

2003学年-2004学年第二学期。

班级：计算机科学与技术***班。

姓名：刘靓。

学号：021***

完成日期：2004.6.28

实习报告。题目：假设定义堆为满足如下性质的完全三叉树：

（1）空树为堆；（2）根结点的值不小于所有子树根的值，且所有子树均为堆。编写利用上述定义的堆进行排序的算法，并分析推导算法的时间复杂度。

班级：计算机***班姓名：刘靓学号：021完成日期：04.6.28

一，需求分析。

1，程序功能。

利用定义的堆进行堆排序，定义的堆为满足如下性质的完全三叉树：（1）空树为堆；（2）根结点的值不小于所有子树根的值，且所有子树均为堆。输入一组数据，可以按照大顶堆的方式排序输出的到一组新的数据。

2，执行方式及结果。

先将初始文件r[1..n]建成一个大根堆，此堆为初始的无序区。

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

keys≤r[n].key

由于交换后新的根r[1]可能违反堆性质，故应将当前无序区r[1..n-1]调整为堆。然后再次将r[1..

n-1]中关键字最大的记录r[1]和该区间的最后一个记录r[n-1]交换，由此得到新的无序区r[1..n-2]和有序区r[n-1..n]，且仍满足关系r[1..

n-2].keys≤r[n-1..n].

keys，同样要将r[1..n-2]调整为堆。

直到无序区只有一个元素为止。

待排序的数据元素的关键字为整数。用三叉树的堆排序和不同乱序程度的不同数据做测试比较。

3，程序执行的命令。

① 初始化操作：将r[1..n]构造为初始堆；

每一趟排序的基本操作：将当前无序区的堆顶记录r[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。

演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”下，用户可由键盘输入待排序表的表长（1-20）和不同测试数据。每次测试完毕，列表显示各种比较指标值。

4，测试数据。

程序执行过程中输入一组整形数据即可。

二，概要设计。

1，抽象数据类型定义。

adt orderablelist

数据关系：r1=

基本操作：initlist(n)

操作结果：构造一个长度为n，元素值依次为1,2,…,n的有序表。

randomizelist(d,isinverseorder)

操作结果：首先根据isinverseorder为true或false，将表置为逆序或正序，然后将表进行d(0≤d≤8)级随机打乱。d为0时表不打乱，d越大，打乱程度越高。

recalllist()

操作结果：恢复最后一次用randomizelist随打乱得到的可排序表。

listlength()

操作结果：返回可排序表的长度。

listempty()

操作结果：若可排序表为空表，则返回true ，否则返回false 。

bubblesort(&c,&s)

操作结果：进行起泡排序，返回关键字比较次数c和移动次数s。

insertsort(&c,&s)

操作结果：进行插入排序，返回关键字比较次数c和移动次数s。

selectsort(&c,&s)

操作结果：进行选择排序，返回关键字比较次数c和移动次数s。 quicksort(&c,&s)

操作结果：进行快速排序，返回关键字比较次数c和移动次数s。

shellsort(&c,&s)

操作结果：进行希尔排序，返回关键字比较次数c和移动次数s。

heapsort(&c,&s)

操作结果：进行堆排序，返回关键字比较次数c和移动次数s。

listtr**erse(visit())

操作结果：依次对l中的每个元素调用函数visit()。

adt orderablelist

2，单元模块。

本程序包含两个模块：

1）主程序模块：

void main()

2)可排序表单元模块——实现可排序表的抽象数据类型；

3，各模块之间的关系如下：

主程序模块。

可排序单元模块。

三，详细设计。

1，各种类型定义。

my 声明文件。

heapsort(seqiast r) /对r[1..n]进行堆排序，不妨用r[0]做暂存单元/

buildheap(r将r[1-n]建成初始堆。

sift(int a,int n,int m)

heapsort(int a,int n)

堆排序的算法。

void heapsort(seqiast r)

//endfor

} /heapsort

buildheap和heapify函数的实现。

因为构造初始堆必须使用到调整堆的操作，先讨论heapify的实现。

heapify函数思想方法。

每趟排序开始前r[l..i]是以r[1]为根的堆，在r[1]与r[i]交换后，新的无序区r[1..i-1]中只有r[1]的值发生了变化，故除r[1]可能违反堆性质外，其余任何结点为根的子树均是堆。

因此，当被调整区间是r[low..high]时，只须调整以r[low]为根的树即可。

筛选法"调整堆。

r[low]的左、右子树(若存在)均已是堆，这两棵子树的根r[2low]和r[2low+1]分别是各自子树中关键字最大的结点。若r[low].key不小于这两个孩子结点的关键字，则r[low]未违反堆性质，以r[low]为根的树已是堆，无须调整；否则必须将r[low]和它的两个孩子结点中关键字较大者进行交换，即r[low]与r[large](r[large].

key=max(r[2low].key，r[2low+1].key))交换。

交换后又可能使结点r[large]违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以r[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。

因此，有人将此方法称为"筛选法"。

buildheap的实现。

要将初始文件r[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。

显然只有一个结点的树是堆，而在完全二叉树中，所有序号的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为， 1，…，1的结点作为根的子树都调整为堆即可。

利用三叉树形式的堆进行排序的部分操作的伪码算法。

void triheap_sort(heap &h)//利用三叉树形式的堆进行排序的算法。

for(i=>0;i--)

heap_adjust(h,i,for(i=>1;i--)

heap_adjust(h,1,i-1);

//triheap_sort

void heap_adjust(heap &h,int s,int m)//顺序表h中，到已经是堆，把插入并调整成堆。

rc=for(j=3*s-1;j<=m;j=3*j-1)

if(j2，实现**。

#include

using namespace std标准命名空间。

#define null 0空地址常量。

const int list_init_size = 100线性表存储空间的初始分配量。

enum status{ok,error,overflow,underflow状态枚举变量。

typedef int elemtype;

typedef struct sqlist{

elemtype *elem存储空间基址。

int length当前表长。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了