应用数据结构实验报告.docx

1、应用数据结构实验报告学 生 实 验 报 告 书实验课程名称应用数据结构开 课 学 院管理学院指导教师姓名学 生 姓 名学生专业班级信息管理与信息系统学 生 学 号2013 2014 学年 第 2 学期实 验 四实验项目名称综合算法设计实验日期2014年5月26 日实 验 者专业班级信管实验类型综合型一、 实验目的、意义1) 掌握查找的含义2) 掌握基本查找操作的算法和实现3) 掌握动态查找算法的实现、应用场合与优缺点4) 能够针对具体问题，灵活选用适宜的查找算法5) 掌握排序的基本概念，对排序的稳定性及排序的时间复杂度有深刻的认识6) 对比折半插入排序和Shell排序的异同7) 掌握选择排序中

2、堆排序的基本思想和算法实现8) 掌握快速排序的基本思想和算法实现9) 了解归并排序算法的基本思想和程序实现10) 了解基数排序算法的基本思想和程序实现11) 掌握Hash排序算法的基本思想和程序实现在前面实验内容的基础上，根据实际问题选择相应算法。二、 实验基本原理与方法本实验涉及各类查找和排序算法。静态查找，折半查找的思想为：设查找表中的元素存放在数组r中，数据元素的下标范围为low, high，要查找的关键字值为key，中间元素的下标为mid=|_(low + high) /2_|（向下取整），令key与rmid的关键字比较：1 若key=rmid.key，查找成功，下标为m的记录即为所求

3、，返回mid。2 若keyrmid.key，所要找的记录只能在右半部分记录中，再对右半部分使用折半查找法继续进行查找，搜索区间缩小了一半。重复上述过程，直到找到查找表中某一个数据元素的关键字的值等于给定的值key，说明查找成功；或者出现low的值大于high的情况，说明查找不成功。动态查找，编程实现一个开放式的高校本科招生最低录取分数线的查询系统，供师生和家长等查询，高校自愿放入该校的信息，可能随时有高校加入。要求实现的查询功能有：查询等于用户给定分数的高校；查询大于（或小于）用户给定分数的高校查询最低录取分数线在用户给定的分数段中的高校。直接插入排序：将当前无序区的第一个记录插入到有序区中适

4、当位置。折半查找法：在有序表中进行，先确定表的中点位置，再通过比较确定下一步查找哪个半区。Shell排序：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量重复上述分组和排序，直至所取的增量dt=1(dtdt-1d2d1)，即所有记录放在同一组中进行直接插入排序为止。堆排序是利用大顶堆（或小顶堆）来选取当前无序区中关键字最大（或最小）的记录实现排序。快速排序是对冒泡法的改进，其基本思想是：通过一趟排序将待排文件分割成独立的两部分，其中一部分记录的关键字值均比另一部分记录的关键字小，然后分别对

5、这两部分进行排序，以达到整个序列有序。归并的思想：将两个或两个以上的有序表合并成一个有序表。利用归并的思想实现排序，假设初始的序列含有n个记录，可以看成n个有序的子序列，每个子序列的长度为m，然后把i(2)个子序列归并，得到n/i个长度为i的子序列；再继续归并，如此重复直到得到一个长度为n的有序序列为止。通常使用的是i=2的二路归并法。基数排序的基本思想是采用多关键字的排序。设记录关键字Ri由d个分量ki1, ki2, , kid组成，设每个分量的取值范围为ti|i=1, 2, , m，且t1t2tm。准备m个箱子，先按低位分箱再按序号一次将各个非空箱子里的记录收集起来，再对新收集起来的元素依

6、次按较高的位分箱，直到最高位。分箱即将第s个关键字等于ti的全部记录装入第i个箱子里。按最高位分箱后，按序号一次将各个非空箱子里的记录收集起来，得到的元素序列就是有序的。Hash排序是在Hash查找的基础上演变而来。对待排序列采用单调的Hash函数，并用链地址法处理冲突，最后用一定规则收集存储好的数据从而得到有序序列。三、 实验内容及要求访问首先设法将网站上的数据导入一个文本文件，然后用程序去读取该文件中的数据，对数据的处理可以自行选择排序算法。用菜单选择排序依据（如输入A按上场时间排序，输入B按投篮率排序），处理后的数据用fwrite方式写入新文件中。四、 实验方案或技术路线（只针对综合型和

7、设计型实验）通过在程序中对结构体中指针的定义、赋值和引用从而完成对链表中特定数据的引用，结合文件的使用、函数的调用，自行选择排序算法、编制算法完成指定程序的编制、调试和执行，并通过观测程序输出结果验证程序设计的正确性。实验过程总结如下：（1）选定一种排序算法，对该算法实现的思路进行分析（2）编程实现选定的算法（3）对所编写的程序进行调试（4）对程序运行的结果进行截图（5）对实验结果进行分析五、 实验原始记录（可附加页）（程序设计类实验：包括原程序、输入数据、运行结果、实验过程发现的问题及解决办法等； 分析与设计、软件工程类实验：编制分析与设计报告，要求用标准的绘图工具绘制文档中的图表。系统实施

8、部分要求记录核心处理的方法、技巧或程序段； 其他实验：包括实验输入数据，处理模型、输出数据及结果分析）1、我选择的球队是火箭队，存放在文件read.txt文件中的内容如下：2、源程序如下：#include#include#includetypedef struct MatchData char name20; /球员 float time; /时间 float shoot; /投篮 float threepoint; /三分 float freethrow; /罚球 float previousRebounds; /前篮板 float backRebounds; /后篮板 float tota

9、lRebounds; /总篮板 float assist; /助攻 float steal; /抢断 float blockshot; /盖帽 float turnover; /失误 float foul; /犯规 float score; /得分MatchData;int LineNumStat(FILE *fp);void InitialPlayers(MatchData *players,int playersNumber);void InputPlayersData(FILE *fp,MatchData *players,int playersNumber);void ShowMenu

10、();void SortPlayersData(MatchData *players,int playersNumber,int sortType);void SortByTime(MatchData *players,int playersNumber);void SortByShoot(MatchData *players,int playersNumber);void SortByThreepoint(MatchData *players,int playersNumber);void SortByFreethrow(MatchData *players,int playersNumbe

11、r);void SortByPreviousRebounds(MatchData *players,int playersNumber);void SortByBackRebounds(MatchData *players,int playersNumber);void SortByTotalRebounds(MatchData *players,int playersNumber);void SortByAssist(MatchData *players,int playersNumber);void SortBySteal(MatchData *players,int playersNum

12、ber);void SortByBlockshot(MatchData *players,int playersNumber);void SortByTurnover(MatchData *players,int playersNumber);void SortByFoul(MatchData *players,int playersNumber);void SortByScore(MatchData *players,int playersNumber);void OutputPlayersData(FILE *fp,MatchData *players,int playersNumber)

13、;int main() MatchData *players; FILE *fpin,*fpout; /输入文件和输出文件指针 int lineNumber; /行数 int playersNumber; /球员的人数 char inputFileName256; char outputFileName256; int choice; printf(请输入存储输入数据的文件名：n); scanf(%s,inputFileName); if(fpin=fopen(inputFileName,r)=NULL) printf(打开输入文件出错！n); exit(1); printf(请输入存储输出数

14、据的文件名：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); InputPlayersD

15、ata(fpin,players,playersNumber); ShowMenu(); scanf(%d,&choice); SortPlayersData(players,playersNumber,choice); OutputPlayersData(fpout,players,playersNumber); free(players); fclose(fpin); fclose(fpout); return 0;/统计文本文件的行数int LineNumStat(FILE *fp) int linenum=0; char buffer100; while(!feof(fp) fgets

16、(buffer,100,fp); linenum+; return linenum;/初始化球员的数据void InitialPlayers(MatchData *players,int playersNumber) int i; MatchData *p; for(i=0;iname,); 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-tu

17、rnover=0; p-foul=0; p-score=0; /输入球员数据void InputPlayersData(FILE *fp,MatchData *players,int playersNumber) int i; MatchData *p; for(i=0;iname,&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

18、); /显示菜单void ShowMenu() 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(请输入选项:);/

19、排序球员数据void SortPlayersData(MatchData *players,int playersNumber,int sortType)switch(sortType) case 1:SortByTime(players,playersNumber); break; case 2:SortByShoot(players,playersNumber); break; case 3:SortByThreepoint(players,playersNumber); break; case 4:SortByFreethrow(players,playersNumber); break

20、; case 5:SortByPreviousRebounds(players,playersNumber); break; case 6:SortByBackRebounds(players,playersNumber); break; case 7:SortByTotalRebounds(players,playersNumber); break; case 8:SortByAssist(players,playersNumber); break; case 9:SortBySteal(players,playersNumber); break; case 10:SortByBlocksh

21、ot(players,playersNumber); break; case 11:SortByTurnover(players,playersNumber); break; case 12:SortByFoul(players,playersNumber); break; case 13:SortByScore(players,playersNumber); break; default:printf(排序方式选择错误，程序即将退出。n); break; /按时间排序void SortByTime(MatchData *players,int playersNumber) int i,j;

22、MatchData temp; for(i=playersNumber-1;i=1;i-) for(j=0;ji;j+) if(playersj.time=1;i-) for(j=0;ji;j+) if(playersj.shoot=1;i-) for(j=0;ji;j+) if(playersj.threepoint=1;i-) for(j=0;ji;j+) if(playersj.freethrow=1;i-) for(j=0;ji;j+) if(playersj.previousRebounds=1;i-) for(j=0;ji;j+) if(playersj.backRebounds=1;i-) for(j=0;ji;j+) if(playersj.totalRebounds=1;i-) for(j=0;ji;j+) if(playersj.assistplayersj+1.assist) temp=playersj; playersj=playersj+1; playersj+1=temp; /按抢断排序void SortBySteal(MatchData *players,int playersNumber) int i,j; MatchData tem