首页 数据结构实验报告-查找最高分与次高分

数据结构实验报告-查找最高分与次高分

举报
开通vip

数据结构实验报告-查找最高分与次高分数据结构与程序设计实验 实  验  报  告 课程名称 数据结构与程序设计实验 课程编号 0906550 实验项目名称 查找最高分与次高分 学号   年级   姓名   专业 计算机科学与技术 学生所在学院 计算机学院 指导教师 杨静 实验室名称地点 21B276           哈尔滨工程大学 实验报告六 实验课名称:数据结构与程序设计实验 实验名称:查找最高分与次高分 班级...

数据结构实验报告-查找最高分与次高分
数据结构与程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 实验 实  验  报  告 课程名称 数据结构与程序设计实验 课程编号 0906550 实验项目名称 查找最高分与次高分 学号   年级   姓名   专业 计算机科学与技术 学生所在学院 计算机学院 指导教师 杨静 实验室名称地点 21B276           哈尔滨工程大学 实验 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 六 实验课名称:数据结构与程序设计实验 实验名称:查找最高分与次高分 班级: 学号: 姓名: 时间:2016.05.05 一、问 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 描述 有 512 人参与玩某游戏,从 1~512 给每个人分配一个编号,每个人的游戏得 分在 0~999 之间,现要用不同方法查找出游戏参与者的最高分和次高分。要求: a. 自行产生 512 个的随机整数作为所有游戏参与者的得分。 b. 输出所有游戏参与者(用编号表示)及其得分。 c. 用顺序查找方法查找出其中取得最高分和次高分者及其分数,并输出。 d. 锦标赛法查找出其中取得最高分和次高分者及其分数,并输出。 e. 通过无序序列建堆和堆调整得到取得最高分者和次高分者及其分数,并输出。 f. 比较不同方法的查找效率和各自的特点。 二、数据结构设计 1.使用结构体People存储序号和得分,表示个体 typedef struct{ int num; int score; }People; 2.设置MIN表示People数据类型的最小值,用于竞标赛查找 #define IN_MAX (int)(((unsigned)(~((int)0)))>>1) #define IN_MIN (-IN_MAX-1) const People MIN={513, IN_MIN}; 3.使用结构体Peoples作为顺序表,存储每个个体 typedef struct{ People *base; int length; }Peoples; 三、算法设计 1.顺序查找 int search(Peoples *p){ People bigger = p->base[1]; People biggest = p->base[1]; int n; for(n=1; n<=512; n++){ if(p->base[n].score > biggest.score){ bigger = biggest; biggest = p->base[n]; }else if(p->base[n].score > bigger.score){ bigger = p->base[n]; } if(p->base[n].num != biggest.num && p->base[n].score == biggest.score){ printf("第%d人和第%d人的分数一样大\n", p->base[n].num, biggest.num); } } printf("第%d人的的分数最大:%d\n", biggest.num, biggest.score); printf("第%d人的的分数次大:%d\n", bigger.num, bigger.score); return 0; } 2.锦标赛查找 (a). 每次将最大值选择至树根后调整树 void Adjust(Peoples *p, int x, int n) { int l = x * 2; //左子树 int r = l + 1; //右子树 if(l >= n){ //x为叶子节点 p->base[x] = MIN; return; }else if(r >= n){ //x有左子树,无右子树 p->base[x] = p->base[l]; return; } if(p->base[l].num == p->base[x].num){ Adjust(p, l, n); }else{ Adjust(p, r, n); } p->base[x] = max(p->base[l], p->base[r]); } (b). 初始树并依次查找最大值与最大值 void GameSort(Peoples *a, int n) { int i, len; Peoples *b; b = (Peoples *)malloc(sizeof(Peoples)); len = 1; while(len < n){ len <<= 1; //len为偶数 //printf("len:%d ",len); } len = 2 * len; //printf("len:%d\n",len); b->base = (People *)malloc(sizeof(People)*len); b->length = len; for(i=len/2; ibase[i] = (i-len/2base[i-len/2]) : (MIN); } for(i=len/2-1; i>=1; i--){ //在双亲存放左右最大值 b->base[i] = max(b->base[2 * i], b->base[2 * i + 1]); } for(i=1; i<=2; i++){ //只调整前两个顺序,依次将树根前置 a->base[i] = b->base[1]; Adjust(b, 1, len); } printf("第%d人的的分数最大:%d\n", a->base[1].num, a->base[1].score); printf("第%d人的的分数次大:%d\n", a->base[2].num, a->base[2].score); free(b); } 3.通过无序序列建堆和堆调整得到取得最高分者和次高分者及其分数 (a). 筛选: 除p->base[s]外均满足堆定义,调整p->base[s],将p->base[s,m]建立为大顶堆 int HeapAdjust(Peoples *p, int s, int m){ People rc = p->base[s]; int j; for(j=2*s; j<=m; j*=2){ if(jbase[j].score < p->base[j+1].score)){ ++j; //j指向较大的孩子节点 } if(!(rc.score < p->base[j].score)){ break; } p->base[s] = p->base[j]; s=j; } p->base[s] = rc; return 0; } (b). 对p->base[1..512]建堆,进行堆调整取得最高分和次高分者,并输出 int HeapSort(Peoples *p){ int i; for(i=(p->length)/2; i>0; --i){ //从最后一个非叶子节点开始,建立大顶堆 HeapAdjust(p, i, p->length); } for(i=p->length; i>510; --i){ //只将最大和次大的得分交换到末尾 swap(p->base[1], p->base[i]); HeapAdjust(p, 1, i-1); } printf("第%d人的的分数最大:%d\n", p->base[512].num, p->base[512].score); printf("第%d人的的分数次大:%d\n", p->base[511].num, p->base[511].score); return 0; } 四、运行测试与 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 1.开始运行后,自行产生 512 个的随机整数作为所有游戏参与者的得分,并输出所有游戏参与者(用编号表示)及其得分。 2.省略中间部分,余下输出 3.输出顺序查找,锦标赛查找,堆排序查找的结果 五、实验收获与思考 通过本次实验,巩固了关于查找算法的知识,同时在编程过程中发现了自己的不足,遇到了很多语法错误及逻辑错误,通过不断的调试解决问题,使我对编程有了更加深入的体会和认识。 顺序查找,锦标赛查找,堆查找的效率及特点: 如果有n个待查找元素,顺序查找每次查找均需进行n-1次比较,但不需额外存储空间。锦标赛排序构成的树是满的完全二叉树,深度为log2n+1,除第一次选择具有最大关键码的 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 需要进行 n-1 次比较外, 重构树选择具有次小、再次小关键码记录所需的比较次数均为O(log2n),但这种选择方法虽然减少了许多查找时间,但是使用了较多的附加存储。堆查找的运行时间主要耗费在初始和调整堆时进行的反复筛选上,堆查找仅需记录一个大小供交换的辅助存储空间,每个记录仅占有一个存储空间。 六、源代码 #include #include #include #define max(x, y) ( ((x.score)>(y.score)?(x):(y))) #define IN_MAX (int)(((unsigned)(~((int)0)))>>1) #define IN_MIN (-IN_MAX-1) typedef struct{ int num; int score; }People; typedef struct{ People *base; int length; }Peoples; const People MIN={513, IN_MIN}; People _; #define swap(x, y) { _=x; x=y; y=_; } int init_all_people(Peoples *p){ int n; srand((unsigned)time(NULL)); //设置每个人的成绩为随机值 for(n=1; n<=512; n++){ p->base[n].num = n; p->base[n].score = rand()%1000; } p->length = 512; return 0; } int copy_people(Peoples *p1, Peoples *p2){ int n; for(n=1; n<=512; n++){ p2->base[n].num = p1->base[n].num; p2->base[n].score = p1->base[n].score; } p2->length = p1->length; return 0; } int display(Peoples *p){ int n; for(n=1; n<=512; n++){ printf("第%3d个人的分数是%3d ", p->base[n].num, p->base[n].score); if(n%2 == 0) printf("\n"); } return 0; } //顺序查找 int search(Peoples *p){ People bigger = p->base[1]; People biggest = p->base[1]; int n; for(n=1; n<=512; n++){ if(p->base[n].score > biggest.score){ bigger = biggest; biggest = p->base[n]; }else if(p->base[n].score > bigger.score){ bigger = p->base[n]; } if(p->base[n].num != biggest.num && p->base[n].score == biggest.score){ printf("第%d人和第%d人的分数一样大\n", p->base[n].num, biggest.num); } } printf("第%d人的的分数最大:%d\n", biggest.num, biggest.score); printf("第%d人的的分数次大:%d\n", bigger.num, bigger.score); return 0; } //锦标赛排序 -- 输出后调整 int Adjust(Peoples *p, int x, int n) { int l = x * 2; //左子树 int r = l + 1; //右子树 if(l >= n){ //x为叶子节点 p->base[x] = MIN; return 0; }else if(r >= n){ //x有左子树,无右子树 p->base[x] = p->base[l]; return 0; } if(p->base[l].num == p->base[x].num){ Adjust(p, l, n); }else{ Adjust(p, r, n); } p->base[x] = max(p->base[l], p->base[r]); return 0; } int GameSort(Peoples *a, int n) { int i, len; Peoples b; len = 1; while(len < n){ len <<= 1; //len为偶数 } len = 2 * len; //printf("len:%d\n",len); b.base = (People *)malloc(sizeof(People)*len); b.length = len; for(i=len/2; ibase[i-len/2]) : (MIN); } for(i=len/2-1; i>=1; i--){ //在双亲存放左右最大值 b.base[i] = max(b.base[2 * i], b.base[2 * i + 1]); } for(i=1; i<=2; i++){ //只调整前两个顺序,依次将树根前置 a->base[i] = b.base[1]; Adjust(&b, 1, len); } printf("第%d人的的分数最大:%d\n", a->base[1].num, a->base[1].score); printf("第%d人的的分数次大:%d\n", a->base[2].num, a->base[2].score); return 0; } /* * 堆排序--筛选 * 只有p->base[s]不符合规定, 将p->base[s,m]建立为大顶堆 */ int HeapAdjust(Peoples *p, int s, int m){ People rc = p->base[s]; int j; for(j=2*s; j<=m; j*=2){ if(jbase[j].score < p->base[j+1].score)){ ++j; //j指向较大的孩子节点 } if(!(rc.score < p->base[j].score)){ break; } p->base[s] = p->base[j]; s=j; } p->base[s] = rc; return 0; } /* * 对p->base[1..512]进行堆排序,只将最大和次大交换到末尾 */ int HeapSort(Peoples *p){ int i; for(i=(p->length)/2; i>0; --i){ //从最后一个非叶子节点开始,建立大顶堆 HeapAdjust(p, i, p->length); } for(i=p->length; i>510; --i){ //只将最大和次大的得分交换到末尾 swap(p->base[1], p->base[i]); HeapAdjust(p, 1, i-1); } printf("第%d人的的分数最大:%d\n", p->base[512].num, p->base[512].score); printf("第%d人的的分数次大:%d\n", p->base[511].num, p->base[511].score); return 0; } int main(){ Peoples p1; p1.base = (People *)malloc(sizeof(People)*513); Peoples p2; p2.base = (People *)malloc(sizeof(People)*513); Peoples p3; p3.base = (People *)malloc(sizeof(People)*513); init_all_people(&p1); copy_people(&p1, &p2); copy_people(&p1, &p3); display(&p1); printf("\n顺序查找:\n"); search(&p1); printf("\n锦标赛查找:\n"); GameSort(&p2, 513); printf("\n堆排序查找:\n"); HeapSort(&p3); free(p1.base); free(p2.base); free(p3.base); return 0; } 教师评分: 教师签字:        
本文档为【数据结构实验报告-查找最高分与次高分】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_531654
暂无简介~
格式:doc
大小:43KB
软件:Word
页数:0
分类:互联网
上传时间:2019-08-27
浏览量:27