2015广工数据结构实验报告堆设计
更新时间:2023-10-26 08:32:01 阅读量: 综合文库 文档下载
- 广工数据结构实验堆推荐度:
- 相关推荐
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;
正在阅读:
2015广工数据结构实验报告堆设计10-26
状态机考卷练习11-05
张靓颖《我的梦》歌词中英文对照08-28
2012年度全国一级建造师执业资格考试《建设工程经济》试卷10-04
基于单片机的自动感应门设计05-25
《笨狼的故事》阅读测试题 (1)06-07
学习十七届六中全会精神心得体会03-04
专业技术人员职业道德考试单选题库03-08
废墟上的孩子作文600字07-11
- 《江苏省环境水质(地表水)自动监测预警系统运行管理办法(试行)》
- 安乐死合法化辩论赛立论稿(浙大新生赛)
- 公共科目模拟试卷公务员考试资料
- 我国固定资产投资FAI对GDP的影响
- 大学生创新创业训练计划项目申请书大创项目申报表
- 完美版—单片机控制步进电机
- 2013资阳中考化学试题
- 18.两位数减一位数退位(397道)
- 工程量计算规则
- 二年级操行评语(下)
- 第3章 流程控制语句
- 浅基桥墩加固技术
- 课题研究的主要方法
- 5100软件说明书 - 图文
- 车间技术员年终总结
- 关于印发《中铁建工集团开展项目管理实验室活动方案》的通知
- 经典诵读结题报告
- 地下水动力学习题答案
- 2018年全国各地高考数学模拟试题平面解析几何试题汇编(含答案解
- 街道办事处主任2018年度述职述廉报告
- 数据结构
- 实验
- 报告
- 设计
- 2015
- 衡水金卷2018年普通高等学校招生全国统一考试模拟(调研卷)试题(二)理综生物试题含答案
- 沉淀池设计计算(平流式,辐流式,竖流式,斜板)
- 心理健康主题班会课(共5篇)
- 杭州电子科技大学 大学物理习题集(下)详细解答
- 如何看待当前基层工作存在的问题
- 2016秋江苏省计算机基础理论题+答案1
- 基于JSP的网上银行管理系统论文(孙俊杰)
- 2010自然辩证法概论复习内容
- 后赤壁赋断句与翻译
- 企业文化案例分析 海底捞
- 《电子测量与仪器》陈尚松版的 - 课后答案1
- 广工大教字〔2013〕2号 关于公布2011~2012学年度教学
- 中国五矿集团公司总部及在京单位2016年接收毕业生情况公示
- 山西省公路学会志
- 90年代腐败大案回眸(二)首钢北钢原党委书记生活糜烂
- 五年级下学期期末复习题(修订版)
- 《计算机与程序设计基础》实验报告模板-2015
- 文言文阅读中常见表官职变动的实词Microsoft Word 文档
- 卫生经济学 重点整理
- 北师大版初中生物七下第四单元第12章第1节同步练习(有答案)