应用数据结构实验报告Word文档下载推荐.docx
- 文档编号:622049
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:27
- 大小:464.65KB
应用数据结构实验报告Word文档下载推荐.docx
《应用数据结构实验报告Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《应用数据结构实验报告Word文档下载推荐.docx(27页珍藏版)》请在冰点文库上搜索。
二、实验基本原理与方法
本实验涉及各类查找和排序算法。
静态查找,折半查找的思想为:
设查找表中的元素存放在数组r中,数据元素的下标范围为[low,high],要查找的关键字值为key,中间元素的下标为mid=|_(low+high)/2_|(向下取整),令key与r[mid]的关键字比较:
1若key=r[mid].key,查找成功,下标为m的记录即为所求,返回mid。
2若key<
r[mid].key,所要找的记录只能在左半部分记录中,再对左半部分使用折半查找法继续进行查找,搜索区间缩小了一半。
3若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函数,并用链地址法处理冲突,最后用一定规则收集存储好的数据从而得到有序序列。
三、实验内容及要求
访问
首先设法将网站上的数据导入一个文本文件,然后用程序去读取该文件中的数据,对数据的处理可以自行选择排序算法。
用菜单选择排序依据(如输入A按上场时间排序,输入B按投篮率排序……),处理后的数据用fwrite方式写入新文件中。
四、实验方案或技术路线(只针对综合型和设计型实验)
通过在程序中对结构体中指针的定义、赋值和引用从而完成对链表中特定数据的引用,结合文件的使用、函数的调用,自行选择排序算法、编制算法完成指定程序的编制、调试和执行,并通过观测程序输出结果验证程序设计的正确性。
实验过程总结如下:
(1)选定一种排序算法,对该算法实现的思路进行分析
(2)编程实现选定的算法
(3)对所编写的程序进行调试
(4)对程序运行的结果进行截图
(5)对实验结果进行分析
五、实验原始记录(可附加页)
(程序设计类实验:
包括原程序、输入数据、运行结果、实验过程发现的问题及解决办法等;
分析与设计、软件工程类实验:
编制分析与设计报告,要求用标准的绘图工具绘制文档中的图表。
系统实施部分要求记录核心处理的方法、技巧或程序段;
其他实验:
包括实验输入数据,处理模型、输出数据及结果分析)
1、我选择的球队是火箭队,存放在文件read.txt文件中的内容如下:
2、源程序如下:
#include<
stdio.h>
stdlib.h>
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("
打开输入文件出错!
exit
(1);
}
请输入存储输出数据的文件名:
outputFileName);
if((fpout=fopen(outputFileName,"
wb"
打开输出文件出错!
exit
(2);
lineNumber=LineNumStat(fpin);
rewind(fpin);
//文件位置指针回到文件头
playersNumber=lineNumber;
players=(MatchData*)malloc(playersNumber*sizeof(MatchData));
InitialPlayers(players,playersNumber);
InputPlayersData(fpin,players,playersNumber);
ShowMenu();
%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;
shoot=0;
threepoint=0;
freethrow=0;
previousRebounds=0;
backRebounds=0;
totalRebounds=0;
assist=0;
steal=0;
blockshot=0;
turnover=0;
foul=0;
score=0;
//输入球员数据
voidInputPlayersData(FILE*fp,MatchData*players,intplayersNumber)
fscanf(fp,"
%s%f%f%%%f%%%f%%%f%f%f%f%f%f%f%f%f"
p->
name,&
p->
time,&
shoot,&
threepoint,&
freethrow,&
previousRebounds,&
backRebounds,
&
totalRebounds,&
assist,&
steal,&
blockshot,&
turnover,&
foul,&
score);
//显示菜单
voidShowMenu()
请选择排序方式:
1.按时间排序\n"
2.按投篮排序\n"
3.按三分排序\n"
4.按罚球排序\n"
5.按前篮板排序\n"
6.按后篮板排序\n"
7.按总篮板排序\n"
8.按助攻排序\n"
9.按抢断排序\n"
10.按盖帽排序\n"
11.按失误排序\n"
12.按犯规排序\n"
13.按得分排序\n"
请输入选项:
//排序球员数据
voidSortPlayersData(MatchData*players,intplayersNumber,intsortType)
switch(sortType)
case1:
SortByTime(players,playersNumber);
break;
case2:
SortByShoot(players,playersNumber);
case3:
SortByThreepoint(players,playersNumber);
case4:
SortByFreethrow(players,playersNumber);
case5:
SortByPreviousRebounds(players,playersNumber);
case6:
SortByBackRebounds(players,playersNumber);
case7:
SortByTotalRebounds(players,playersNumber);
case8:
SortByAssist(players,playersNumber);
case9:
SortBySteal(players,playersNumber);
case10:
SortByBlockshot(players,playersNumber);
case11:
SortByTurnover(players,playersNumber);
case12:
SortByFoul(players,playersNumber);
case13:
SortByScore(players,playersNumber);
default:
printf("
排序方式选择错误,程序即将退出。
//按时间排序
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)
if(players[j].shoot<
players[j+1].shoot)
//按三分排序
voidSortByThreepoint(MatchData*players,intplayersNumber)
if(players[j].threepoint<
players[j+1].threepoint)
//按罚球排序
voidSortByFreethrow(MatchData*players,intplayersNumber)
if(players[j].freethrow<
players[j+1].freethrow)
//按前篮板排序
voidSortByPreviousRebounds(MatchData*players,intplayersNumber)
if(players[j].previousRebounds<
players[j+1].previousRebounds)
//按后篮板排序
voidSortByBackRebounds(MatchData*players,intplayersNumber)
if(players[j].backRebounds<
players[j+1].backRebounds)
//按总篮板排序
voidSortByTotalRebounds(MatchData*players,intplayersNumber)
if(players[j].totalRebounds<
players[j+1].totalRebounds)
//按助攻排序
voidSortByAssist(MatchData*players,intplayersNumber)
if(players[j].assist<
players[j+1].assist)
//按抢断排序
voidSortBySteal(MatchData*players,intplayersNumber)
MatchDatat
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 应用 数据结构 实验 报告