应用数据结构实验报告

学生实验报告书实验课程名称应用数据结构开课学院管理学院指导教师姓名学生姓名学生专业班级学生学号2014—2015学年第2学期

实验四综合算法设计实验日期2015年6月17日实验者专业班级实验类型综合型实验目的、意义掌握查找的含义掌握基本查找操作的算法和实现掌握动态查找算法的实现、应用场合与优缺点能够针对具体问题，灵活选用适宜的查找算法掌握排序的基本概念，对排序的稳定性及排序的时间复杂度有深刻的认识对比折半插入排序和Shell排序的异同掌握选择排序中堆排序的基本思想和算法实现掌握快速排序的基本思想和算法实现了解归并排序算法的基本思想和程序实现了解基数排序算法的基本思想和程序实现掌握Hash排序算法的基本思想和程序实现在前面实验内容的基础上，根据实际问题选择相应算法。实验基本原理与方法本实验涉及各类查找和排序算法。静态查找，折半查找的思想为：设查找表中的元素存放在数组r中，数据元素的下标范围为[low,high]，要查找的关键字值为key，中间元素的下标为mid=|_(low+high)/2_|（向下取整），令key与r[mid]的关键字比较：若key=r[mid].key，查找成功，下标为m的记录即为所求，返回mid。若key<r[mid].key，所要找的记录只能在左半部分记录中，再对左半部分使用折半查找法继续进行查找，搜索区间缩小了一半。若key>r[mid].key，所要找的记录只能在右半部分记录中，再对右半部分使用折半查找法继续进行查找，搜索区间缩小了一半。重复上述过程，直到找到查找表中某一个数据元素的关键字的值等于给定的值key，说明查找成功；或者出现low的值大于high的情况，说明查找不成功。动态查找，编程实现一个开放式的高校本科招生最低录取分数线的查询系统，供师生和家长等查询，高校自愿放入该校的信息，可能随时有高校加入。要求实现的查询功能有：①查询等于用户给定分数的高校；②查询大于（或小于）用户给定分数的高校③查询最低录取分数线在用户给定的分数段中的高校。直接插入排序：将当前无序区的第一个记录插入到有序区中适当位置。折半查找法：在有序表中进行，先确定表的中点位置，再通过比较确定下一步查找哪个半区。Shell排序：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量重复上述分组和排序，直至所取的增量dt=1(dt<dt-1<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。堆排序是利用大顶堆（或小顶堆）来选取当前无序区中关键字最大（或最小）的记录实现排序。快速排序是对冒泡法的改进，其基本思想是：通过一趟排序将待排文件分割成独立的两部分，其中一部分记录的关键字值均比另一部分记录的关键字小，然后分别对这两部分进行排序，以达到整个序列有序。归并的思想：将两个或两个以上的有序表合并成一个有序表。利用归并的思想实现排序，假设初始的序列含有n个记录，可以看成n个有序的子序列，每个子序列的长度为m，然后把i(≥2)个子序列归并，得到n/i个长度为i的子序列；再继续归并，如此重复直到得到一个长度为n的有序序列为止。通常使用的是i=2的二路归并法。基数排序的基本思想是采用多关键字的排序。设记录关键字R[i]由d个分量ki1,ki2,…,kid组成，设每个分量的取值范围为{ti|i=1,2,…,m，且t1<t2<…<tm}。准备m个箱子，先按低位分箱再按序号一次将各个非空箱子里的记录收集起来，再对新收集起来的元素依次按较高的位分箱，直到最高位。分箱即将第s个关键字等于ti的全部记录装入第i个箱子里。按最高位分箱后，按序号一次将各个非空箱子里的记录收集起来，得到的元素序列就是有序的。Hash排序是在Hash查找的基础上演变而来。对待排序列采用单调的Hash函数，并用链地址法处理冲突，最后用一定规则收集存储好的数据从而得到有序序列。实验内容及要求访问/players.php?dpc=1，任选一个球队，将该队所有队员最近5个赛季的各项数据（时间、投篮、三分、罚球、前篮板、后篮板、总篮板、助攻、抢断、盖帽、失误、犯规、得分）进行统计平均，然后根据计算结果按各项指标排序。首先设法将网站上的数据导入一个文本文件，然后用程序去读取该文件中的数据，对数据的处理可以自行选择排序算法。用菜单选择排序依据（如输入A按上场时间排序，输入B按投篮率排序……），处理后的数据用fwrite方式写入新文件中。实验方案或技术路线（只针对综合型和设计型实验）方案：先将网站上需要的相关数据复制到文本文档，命名为data。在C源程序中定义结构体数组，用于后续存储球员信息。然后读取文件内容，将其存储进结构体中。在对每个球员5个赛季的各项数据求平均值，存储进新的结构体中。设计菜单，当使用者选择某项时，将球员信息按该项数据排序并进行显示。最后选择是否将排序后的信息写入新文件中。技术路线：由于球员数目和赛季数大于1，因此需使用结构体数组或结构体指针来进行存储。因为存储的数据又有球员和赛季两个维度，因此要用二维数组或指向指针的指针（本人采用二维数组，因为指针容易出错）。本实验可分三步来写。第一步，构造好存储球员相关数据的结构体二维数组。并编写函数将文件中需要的内容读取并存储；第二步，求出每个球员5个赛季各项数据的平均值，并将其存储进新的结构体数组中；第三步，根据用户的选择，按照某项数据（平均值）将球员排序，并写入文本文件。可能用到的函数和方法：fscanf,fopen,fclose,fwrite.、字符串函数、宏定义、快速排序法或是冒泡排序法、循环体、switch函数等。实验原始记录（可附加页）（程序设计类实验：包括原程序、输入数据、运行结果、实验过程发现的问题及解决办法等；分析与设计、软件工程类实验：编制分析与设计报告，要求用标准的绘图工具绘制文档中的图表。系统实施部分要求记录核心处理的方法、技巧或程序段；其他实验：包括实验输入数据，处理模型、输出数据及结果分析）相关流程图（较简略）第一步开始开始用用fprintf函数读取文件第一个字符串并复制给结构体中的“姓名”成员str=“时间str=“时间”？strstr为字符指针，fprintf第三个参数，文件中字符串输出的目标地址。NNYYN这个步骤循环N这个步骤循环16次，以跳过无用信息从文件中读取字符串从文件中读取字符串从文件中读取字符串，将其付给结构体相关信息NN×4×4从文件中读取字符串本循环本循环是否做够5次？因为每个因为每个球员有5个赛季的数据YY球员数球员数是否超出范围？结束结束第二步开始开始x为x为二维数组行下标，球员序号，n为球员数目xx<n?YYNx++;对Nx++;对球员各项数据求平均，并放入一个新的结构体数组中结束结束第三步排序采用冒泡法，为了将排序方法写为一个可被结构体调用并排序的函数（因为每次调用用来比较的成员都不同），此处加入宏定义以及取消宏定义。由于写入txt时用的是fwrite函数，用二进制写入，因此文件内容显示为乱码。实验源代码//头文件“ks.h”，包含了结构体的定义和冒泡排序法#include"stdio.h"#defineTTtimetypedefstructHoopster{ charname[40]; doubletime; doubleshoot; doublethree_point; doublepenalty_shot; doublefront; doubleback; doubleall; doubleassisting; doublesteal; doubleblock; doublemuff; doublefoul; doublescore; }Player;voidQuicksort(Playerl[],intn){ Playerb; inti=0,j=0; for(;i<n-1;i++) for(j=i+1;j<n-1-i;j++) if(l[j].TT>l[j+1].TT) { b=l[j]; l[j]=l[j+1]; l[j+1]=b; }}//源码#include"ks.h"//调用ks.h头文件#include"stdlib.h"#include"conio.h"#include"string.h"#defineMM50#defineNN500intset(double*a,char*str,FILE*fp)//用来赋值的函数 { fscanf(fp,"%s",str); *a=atof(str);//将字符串转换为double并赋值 return0; }voidOutp(inta,intb,Playerp[])//输出函数{for(a=0;a<b;a++) printf("球员姓名：%s时间：%lf投篮：%lf三分：%lf罚球：%lf前篮板：%lf后篮板：%lf总篮板：%lf助攻：%lf抢断：%lf盖帽：%lf失误：%lf犯规：%lf得分：%lf\n" ,p[a].name,p[a].time,p[a].shoot,p[a].three_point,p[a].penalty_shot,p[a].front,p[a].back,p[a].all,p[a].assisting,p[a].steal,p[a].block,p[a].muff,p[a].foul,p[a].score);}intmain(void){ charch; intj,x=-1,n; FILE*fp=NULL; char*filename=(char*)malloc(MM*sizeof(char)); char*str=(char*)malloc(NN*sizeof(char)); Playerplayer[10][5]; Playerp_average[10]; printf("请输入球员信息所在的文件名：\n"); scanf("%s",filename); strcat(filename,".txt"); if((fp=fopen(filename,"rb"))==NULL) { printf("Openthefilefail!\n"); system("PAUSE"); exit(1); } do { inti; x++; j=0; if(fscanf(fp,"%s",str)!=1)break; for(i=0;i<5;i++) strcpy(player[x][i].name,str); while(strcmp(str,"时间")!=0) { fscanf(fp,"%s",str); } for(i=0;i<16;i++) { fscanf(fp,"%s",str); } do { set(&player[x][j].time,str,fp); set(&player[x][j].shoot,str,fp); set(&player[x][j].three_point,str,fp); set(&player[x][j].penalty_shot,str,fp); set(&player[x][j].front,str,fp); set(&player[x][j].back,str,fp); set(&player[x][j].all,str,fp); set(&player[x][j].assisting,str,fp); set(&player[x][j].steal,str,fp); set(&player[x][j].block,str,fp); set(&player[x][j].muff,str,fp); set(&player[x][j].foul,str,fp); set(&player[x][j].score,str,fp); j++; if(j==5)break; for(i=0;i<4;i++) { if(fscanf(fp,"%s",str)!=1)break; } } while(j<5); } while(j=5&&x<10); free(str);//第一步结束，释放内存 n=x; for(x=0;x<n;x++) { strcpy(p_average[x].name,player[x][0].name); p_average[x].time=(player[x][0].time+player[x][1].time+player[x][2].time+player[x][3].time+player[x][4].time)/5; p_average[x].shoot=(player[x][0].shoot+player[x][1].shoot+player[x][2].shoot+player[x][3].shoot+player[x][4].shoot)/5; p_average[x].three_point=(player[x][0].three_point+player[x][1].three_point+player[x][2].three_point+player[x][3].three_point +player[x][4].three_point)/5; p_average[x].penalty_shot=(player[x][0].penalty_shot+player[x][1].penalty_shot+player[x][2].penalty_shot+player[x][3].penalty_shot +player[x][4].penalty_shot)/5; p_average[x].front=(player[x][0].front+player[x][1].front+player[x][2].front+player[x][3].front+player[x][4].front)/5; p_average[x].back=(player[x][0].back+player[x][1].back+player[x][2].back+player[x][3].back+player[x][4].back)/5; p_average[x].all=(player[x][0].all+player[x][1].all+player[x][2].all+player[x][3].all+player[x][4].all)/5; p_average[x].assisting=(player[x][0].assisting+player[x][1].assisting+player[x][2].assisting+player[x][3].assisting+player[x][4].assisting)/5; p_average[x].steal=(player[x][0].steal+player[x][1].steal+player[x][2].steal+player[x][3].steal+player[x][4].steal)/5; p_average[x].block=(player[x][0].block+player[x][1].block+player[x][2].block+player[x][3].block+player[x][4].block)/5; p_average[x].muff=(player[x][0].muff+player[x][1].muff+player[x][2].muff+player[x][3].muff+player[x][4].muff)/5; p_average[x].foul=(player[x][0].foul+player[x][1].foul+player[x][2].foul+player[x][3].foul+player[x][4].foul)/5; p_average[x].score=(player[x][0].score+player[x][1].score+player[x][2].score+player[x][3].score+player[x][4].score)/5; }//第二步结束 printf("请选择需要进行的操作：\n"); printf("A.显示球员平均成绩\n"); printf("B.将球员平均成绩按时间排序\n"); printf("C.将球员平均成绩按投篮排序\n"); printf("D.将球员平均成绩按三分排序\n"); printf("E.将球员平均成绩按罚球排序\n"); printf("F.将球员平均成绩按前篮板排序\n"); printf("G.将球员平均成绩按后篮板排序\n"); printf("H.将球员平均成绩按总篮板排序\n");printf("I.将球员平均成绩按助攻排序\n"); printf("J.将球员平均成绩按抢断排序\n"); printf("K.将球员平均成绩按盖帽排序\n"); printf("L.将球员平均成绩按失误排序\n"); printf("M.将球员平均成绩按犯规排序\n"); printf("N.将球员平均成绩按得分排序\n"); printf("O.退出\n"); getchar(); scanf("%c",&ch); switch(ch) {case'A':Outp(x,n,p_average); break;case'B':#undefTT#defineTTtime Quicksort(p_average,n); Outp(x,n,p_average);break;case'C': #undefTT#defineTTshoot Quicksort(p_average,n); Outp(x,n,p_average);break;case'D': #undefTT#defineTTthree_point Quicksort(p_average,n); Outp(x,n,p_average);break;case'E': #undefTT#defineTTpenalty_shot Quicksort(p_average,n); Outp(x,n,p_average);break;case'F': #undefTT#defineTTfront Quicksort(p_average,n); Outp(x,n,p_average);break;case'G': #undefTT#defineTTback Quicksort(p_average,n); Outp(x,n,p_average);break;case'H': #undefTT#defineTTall Quicksort(p_average,n); Outp(x,n,p_average);break;case'I': #undefTT#defineTTassisting Quicksort(p_average,n); Outp(x,n,p_average);break;case'J': #undefTT#defineTTsteal Quicksort(p_average,n); Outp(x,n,p_average);break;case'K': #undefTT#defineTTblock Quicksort(p_average,n); Outp(x,n,p_average);break;case'L': #undefTT#defineTTmuff Quicksort(p_average,n); Outp(x,n,p_average);break;case'M': #undefTT#d