2015广工数据结构实验报告堆设计

1.题目

采用顺序存储结构实现堆的筛选，建造，插入，删除，排序等操作。 ADT Heap{

基本操作： void MakeHeap(Heap &H, RcdType *E, int n, int size, int tag) 操作结果：构造一个堆； Destroy(&H)

初始条件：堆已存在。 操作结果：销毁堆H。 GetLength(H)

初始条件：堆H已存在。

操作结果：返回堆H中元素个数。 Get(L, i, &e)

初始条件：堆H已存在，1≤i≤LengthList(L)。 操作结果：用e返回堆H中第i个元素的值。 RemoveFirstHeap(H,e); 初始条件：堆H已存在

操作结果：删除第一个节点

insertHeap(H,e);

初始条件：堆H已存在，1≤i≤LengthList(L)+1。

操作结果：在H的第n个元素之后插入新的元素e，L的长度加1 showRcd(H.rcd,H.n);

初始条件：堆H已存在。

操作结果：依次输出H的每个元素。

} ADT Heap 2.存储结构定义

//引入系统头文件 #include #include #include

//定义一些常量 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define INFEASIBLE -1 #define OVERFLOW -2

//定义一些状态类型

typedef int Status;//用作函数类型，用作函数结果状态 typedef int ElemType; typedef int KeyType;

//定义一个记录类型 typedef struct{ KeyType key;//关键字 } RcdType;

//定义一个记录类型的顺序表 typedef struct{ RcdType *rcd;//rcd的0号单元闲置； int length; int size; int tag;//排序类型，1为升序，0为降序 int increament; } RcdSqList;

//定义堆的结构体类型 typedef struct{ RcdType *rcd;//堆的基址，0号单元不使用 int n; //堆长度 int size; //堆容量 int tag; //大根对与小根堆的标志 int (*prior)(KeyType,KeyType,int);//函数变量，用于关键字优先级比较 }Heap;//堆类型

3.算法设计

/******************************

这是一个比较关键字优先级的函数 参数说明：

a和b为需要比较的两个关键字 tag为排序的标识，1为升序，2为降序

*******************************/

Status prior(KeyType a,KeyType b,int tag){

if(tag == 1){

return (a > b) ? 1 : 0;

}else if(tag == 0){ } else{

return (b >= a) ? 1 : 0;

}

}

return 0;

/********************************************

初始化一个顺序表的函数 参数说明：

L为需要初始化的函数 size为顺序表的长度 tag为顺序表的排序类型

********************************************/ Status initSqList(RcdSqList &L, int size,int tag){

//将当前时间设置成随机函数的种子，所以每次产生的数都不一样 srand( (unsigned)time( NULL ) ); L.length = 0; L.tag = tag; L.size = size+11;

L.rcd = (RcdType*)malloc((size+11)*sizeof(RcdType)); if(L.rcd == NULL){ } else{ }

return 1;

for(int i = 1; i <= size; i++){ }

L.rcd[i].key = rand()0; L.length++; return 0;

}

/********************************

打印记录 参数说明：

rcd为需要打印的记录序列 length为序列的长度

********************************/ void showRcd(RcdType *rcd,int length){ }

/**********************************

交换节点、 参数说明：

H为需要交换节点的堆

i和j为需要交换的两个节点位置 int i;

for(i = 1; i <= length; i++){ }

printf(\

printf(\

**********************************/ Status swapHeapElem(Heap &H,int i,int j){

RcdType t;

if(i < 0 || j <0 || i > H.n || j > H.n){

return ERROR;

}else{

t = H.rcd[i];

}

}

H.rcd[i] = H.rcd[j]; H.rcd[j] = t;

return OK;

/**************************************

堆的筛选操作 参数说明： H为需要筛选的堆 pos为筛选的其实位置

**************************************/ void shiftDown(Heap &H,int pos){

int c,rc; //c是左孩子的位置，rc是右孩子的位置

while(pos <= H.n/2){ //当 pos > n/2 时是叶子节点，则循环结束

c = pos*2; rc = pos*2+1; //判断条件解释：

//rc <= H.n ,判断右孩子是否大于总长度。左孩子不用判断，因为

它必然小于右子树

//H.prior(H.rcd[rc].key,H.rcd[c],H.tag用于比较谁更优秀 if(rc

<=

H.n

&&

H.prior(H.rcd[rc].key,H.rcd[c].key,H.tag)){

}

//较优孩子再跟其双亲(即编号为pos节点)比较 //假如双亲比孩子优，则筛选结束；

c = rc;

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