内容发布更新时间 : 2024/5/10 18:17:34星期一 下面是文章的全部内容请认真阅读。
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
//定义一些常量 #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;