应用数据结构实验报告

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

实验四综合算法设计实验日期2014年5月26日实验者专业班级信管实验类型综合型实验目的、意义掌握查找的含义掌握基本查找操作的算法和实现掌握动态查找算法的实现、应用场合与优缺点能够针对具体问题，灵活选用适宜的查找算法掌握排序的基本概念，对排序的稳定性及排序的时间复杂度有深刻的认识对比折半插入排序和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方式写入新文件中。实验方案或技术路线（只针对综合型和设计型实验）通过在程序中对结构体中指针的定义、赋值和引用从而完成对链表中特定数据的引用，结合文件的使用、函数的调用，自行选择排序算法、编制算法完成指定程序的编制、调试和执行，并通过观测程序输出结果验证程序设计的正确性。实验过程总结如下：选定一种排序算法，对该算法实现的思路进行分析（2）编程实现选定的算法

（3）对所编写的程序进行调试

（4）对程序运行的结果进行截图

（5）对实验结果进行分析实验原始记录（可附加页）（程序设计类实验：包括原程序、输入数据、运行结果、实验过程发现的问题及解决办法等；分析与设计、软件工程类实验：编制分析与设计报告，要求用标准的绘图工具绘制文档中的图表。系统实施部分要求记录核心处理的方法、技巧或程序段；其他实验：包括实验输入数据，处理模型、输出数据及结果分析）我选择的球队是火箭队，存放在文件read.txt文件中的内容如下：源程序如下：#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstructMatchData{ charname[20];//球员 floattime;//时间 floatshoot;//投篮 floatthreepoint;//三分 floatfreethrow;//罚球 floatpreviousRebounds;//前篮板 floatbackRebounds;//后篮板 floattotalRebounds;//总篮板 floatassist;//助攻 floatsteal;//抢断 floatblockshot;//盖帽 floatturnover;//失误 floatfoul;//犯规 floatscore;//得分}MatchData;intLineNumStat(FILE*fp);voidInitialPlayers(MatchData*players,intplayersNumber);voidInputPlayersData(FILE*fp,MatchData*players,intplayersNumber);voidShowMenu();voidSortPlayersData(MatchData*players,intplayersNumber,intsortType);voidSortByTime(MatchData*players,intplayersNumber);voidSortByShoot(MatchData*players,intplayersNumber);voidSortByThreepoint(MatchData*players,intplayersNumber);voidSortByFreethrow(MatchData*players,intplayersNumber);voidSortByPreviousRebounds(MatchData*players,intplayersNumber);voidSortByBackRebounds(MatchData*players,intplayersNumber);voidSortByTotalRebounds(MatchData*players,intplayersNumber);voidSortByAssist(MatchData*players,intplayersNumber);voidSortBySteal(MatchData*players,intplayersNumber);voidSortByBlockshot(MatchData*players,intplayersNumber);voidSortByTurnover(MatchData*players,intplayersNumber);voidSortByFoul(MatchData*players,intplayersNumber);voidSortByScore(MatchData*players,intplayersNumber);voidOutputPlayersData(FILE*fp,MatchData*players,intplayersNumber);intmain(){ MatchData*players; FILE*fpin,*fpout;//输入文件和输出文件指针 intlineNumber;//行数 intplayersNumber;//球员的人数 charinputFileName[256]; charoutputFileName[256]; intchoice; printf("请输入存储输入数据的文件名：\n"); scanf("%s",inputFileName); if((fpin=fopen(inputFileName,"r"))==NULL) { printf("打开输入文件出错！\n"); exit(1); } printf("请输入存储输出数据的文件名：\n"); scanf("%s",outputFileName); if((fpout=fopen(outputFileName,"wb"))==NULL) { printf("打开输出文件出错！\n"); exit(2); } lineNumber=LineNumStat(fpin); rewind(fpin);//文件位置指针回到文件头 playersNumber=lineNumber; players=(MatchData*)malloc(playersNumber*sizeof(MatchData)); InitialPlayers(players,playersNumber); InputPlayersData(fpin,players,playersNumber); ShowMenu(); scanf("%d",&choice); SortPlayersData(players,playersNumber,choice); OutputPlayersData(fpout,players,playersNumber); free(players); fclose(fpin); fclose(fpout); return0;}//统计文本文件的行数intLineNumStat(FILE*fp){ intlinenum=0; charbuffer[100]; while(!feof(fp)) { fgets(buffer,100,fp); linenum++; } returnlinenum;}//初始化球员的数据voidInitialPlayers(MatchData*players,intplayersNumber){ inti; MatchData*p; for(i=0;i<playersNumber;i++) { p=&players[i]; strcpy(p->name,""); p->time=0; p->shoot=0; p->threepoint=0; p->freethrow=0; p->previousRebounds=0; p->backRebounds=0; p->totalRebounds=0; p->assist=0; p->steal=0; p->blockshot=0; p->turnover=0; p->foul=0; p->score=0; }}//输入球员数据voidInputPlayersData(FILE*fp,MatchData*players,intplayersNumber){ inti; MatchData*p; for(i=0;i<playersNumber;i++) { p=&players[i]; fscanf(fp,"%s%f%f%%%f%%%f%%%f%f%f%f%f%f%f%f%f",p->name,&p->time,&p->shoot,&p->threepoint,&p->freethrow,&p->previousRebounds,&p->backRebounds, &p->totalRebounds,&p->assist,&p->steal,&p->blockshot,&p->turnover,&p->foul,&p->score); }}//显示菜单voidShowMenu(){ printf("请选择排序方式：\n"); printf("1.按时间排序\n"); printf("2.按投篮排序\n"); printf("3.按三分排序\n"); printf("4.按罚球排序\n"); printf("5.按前篮板排序\n"); printf("6.按后篮板排序\n"); printf("7.按总篮板排序\n"); printf("8.按助攻排序\n"); printf("9.按抢断排序\n"); printf("10.按盖帽排序\n"); printf("11.按失误排序\n"); printf("12.按犯规排序\n"); printf("13.按得分排序\n"); printf("请输入选项:");}//排序球员数据voidSortPlayersData(MatchData*players,intplayersNumber,intsortType){switch(sortType) { case1:SortByTime(players,playersNumber); break; case2:SortByShoot(players,playersNumber); break; case3:SortByThreepoint(players,playersNumber); break; case4:SortByFreethrow(players,playersNumber); break; case5:SortByPreviousRebounds(players,playersNumber); break; case6:SortByBackRebounds(players,playersNumber); break; case7:SortByTotalRebounds(players,playersNumber); break; case8:SortByAssist(players,playersNumber); break; case9:SortBySteal(players,playersNumber); break; case10:SortByBlockshot(players,playersNumber); break; case11:SortByTurnover(players,playersNumber); break; case12:SortByFoul(players,playersNumber); break; case13:SortByScore(players,playersNumber); break; default:printf("排序方式选择错误，程序即将退出。\n"); break; }}//按时间排序voidSortByTime(MatchData*players,intplayersNumber){ inti,j; MatchDatatemp; for(i=playersNumber-1;i>=1;i--) { for(j=0;j<i;j++) { if(players[j].time<players[j+1].time) { temp=players[j]; players[j]=players[j+1]; players[j+1]=temp; } } }}//按投篮排序voidSortByShoot(MatchData*players,intplayersNumber){ inti,j; MatchDatatemp; for(i=playersNumber-1;i>=1;i--) { for(j=0;j<i;j++) { if(players[j].shoot<players[j+1].shoot) { temp=players[j]; players[j]=players[j+1]; players[j+1]=temp; } } }}//按三分排序voidSortByThreepoint(MatchData*players,intplayersNumber){ inti,j; MatchDatatemp; for(i=playersNumber-1;i>=1;i--) { for(j=0;j<i;j++) { if(players[j].threepoint<players[j+1].threepoint) { temp=players[j]; players[j]=players[j+1]; players[j+1]=temp; } } }}//按罚球排序voidSortByFreethrow(MatchData*players,intplayersNumber){ inti,j; MatchDatatemp; for(i=playersNumber-1;i>=1;i--) { for(j=0;j<i;j++) { if(players[j].freethrow<players[j+1].freethrow) { temp=players[j]; players[j]=players[j+1]; players[j+1]=temp; } } }}//按前篮板排序voidSortByPreviousRebounds(MatchData*players,intplayersNumber){ inti,j; MatchDatatemp; for(i=playersNumber-1;i>=1;i--) { for(j=0;j<i;j++) { if(players[j].previousRebounds<players[j+1].previousRebounds) { temp=players[j]; players[j]=players[j+1]; players[j+1]=temp; } } }}//按后篮板排序voidSortByBackRebounds(MatchData*players,intplayersNumber){ inti,j; MatchDatatemp; for(i=playersNumber-1;i>=1;i--) { for(j=0;j<i;j++) { if(players[j].backRebounds<players[j+1].backRebounds) { temp=players[j]; players[j]=players[j+1]; players[j+1]=temp; } } }}//按总篮板排序voidSortByTotalRebounds(MatchData*players,intplayersNumber){ inti,j; MatchDatatemp; for(i=playersNumber-1;i>=1;i--) { for(j=0;j<i;j++) { if(players[j].totalRebounds<players[j+1].totalRebounds) { temp=players[j]; players[j]=players[j+1]; players[j+1]=temp; } } }}//按助攻排序voidSortByAssist(MatchData*players,intplayersNumber){ inti,j; MatchDatatemp; for(i=playersNumber-1;i>=1;i--) { for(j=0;j<i;j++) { if(players[j].assist<players[j+1].assist) { temp=players[j]; players[j]=players[j+1]; players[j+1]=temp; } } }}//按抢断排序voidSortBySteal(MatchData*players,intplayersNumber){ inti,j; MatchDatatemp; for(i=playersNumber-1;i>=1;i--) { for(j=0;j<i;j++) { if(players[j].steal<players[j+1].steal) { temp=players[j]; players[j]=players[j+1]; players[j+1]=temp; } } }}//按盖帽排序voidSortByBlockshot(MatchData*players,intplayersNumber){ inti,j; MatchDatatemp; for(i=playersNumber-1;i>=1;i--) { for(j=0;j<i;j++) { if(players[j].blockshot<players[j+1].blockshot) { temp=players[j]; players[j]=players[j+1]; players[j+1]=temp; } } }}//按失误排序voidSortByTurnover(MatchData*players,intplayersNumber){ inti,j; MatchDatatemp; for(i=playersNumber-1;i>=1;i--) { for(j=0;j<i;j++) { if(players[j].turnover<players[j+1].turnover) { temp=players[j]; players[j]=players[j+1]; players[j+1]=temp; } } }}//按犯规排序voidSortByFoul(MatchData*players,intplayersNumber){ inti,j; MatchDatatemp; for(i=playersNumber-1;i>=1;i--) { for(j=0;j<i;j++) { if(players[j].foul<players[j+1].foul) { temp=players[j]; players[j]=players[j+1]; players[j+1]=temp; } } }}//按得分排序voidSortByScore(MatchData*players,intplayersNumber){ inti,j; MatchDatatemp; for(i=playersNumber-1;i>=1;i--) { for(j=0;j<i;j++) { if(players[j].score<players[j+1].score) { temp=players[j]; players[j]=players[j+1]; players[j+1]=temp; } } }}//输出球员数据voidOutputPlayersData(FILE*fp,MatchData*players,intplayersNumber){ inti; MatchData*p; for(i=0;i<playersNumber;i++) { p=&players[i]; if(strlen(p->name)>8) printf("%s\t%.3g\t%.3g%%\t%.3g%%\t%.3g%%\t%.3g\t%.3g\t%.3g\t%.3g\t%.3g\t%.3g\t%.3g\t%.3g\t%.3g\n",p->name,p->time,p->shoot,p->threepoint,p->freethrow,p->previousRebounds,p->backRebounds, p->totalRebounds,p->assist,p->steal,p->blockshot,p->turnover,p->foul,p->score); else printf("%s\t\t%.3g\t%.3g%%\t%.3g%%\t%.3g%%\t%.3g\t%.3g\t%.3g\t%.3g\t%.3g\t%.3g\t%.3g\t%.3g\t%.3g\n",p->name,p->time,p->shoot,p->threepoint,p->freethrow,p