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

上传人:b****2 文档编号:490295 上传时间:2023-04-29 格式:DOCX 页数:27 大小:464.65KB
下载 相关 举报
应用数据结构实验报告.docx_第1页
第1页 / 共27页
应用数据结构实验报告.docx_第2页
第2页 / 共27页
应用数据结构实验报告.docx_第3页
第3页 / 共27页
应用数据结构实验报告.docx_第4页
第4页 / 共27页
应用数据结构实验报告.docx_第5页
第5页 / 共27页
应用数据结构实验报告.docx_第6页
第6页 / 共27页
应用数据结构实验报告.docx_第7页
第7页 / 共27页
应用数据结构实验报告.docx_第8页
第8页 / 共27页
应用数据结构实验报告.docx_第9页
第9页 / 共27页
应用数据结构实验报告.docx_第10页
第10页 / 共27页
应用数据结构实验报告.docx_第11页
第11页 / 共27页
应用数据结构实验报告.docx_第12页
第12页 / 共27页
应用数据结构实验报告.docx_第13页
第13页 / 共27页
应用数据结构实验报告.docx_第14页
第14页 / 共27页
应用数据结构实验报告.docx_第15页
第15页 / 共27页
应用数据结构实验报告.docx_第16页
第16页 / 共27页
应用数据结构实验报告.docx_第17页
第17页 / 共27页
应用数据结构实验报告.docx_第18页
第18页 / 共27页
应用数据结构实验报告.docx_第19页
第19页 / 共27页
应用数据结构实验报告.docx_第20页
第20页 / 共27页
亲,该文档总共27页,到这儿已超出免费预览范围,如果喜欢就下载吧!
下载资源
资源描述

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

《应用数据结构实验报告.docx》由会员分享,可在线阅读,更多相关《应用数据结构实验报告.docx(27页珍藏版)》请在冰点文库上搜索。

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

应用数据结构实验报告

学生实验报告书

实验课程名称

应用数据结构

开课学院

管理学院

指导教师姓名

燕翔

学生姓名

学生专业班级

信息管理与信息系统

学生学号

2013—2014学年第2学期

实验四

实验项目名称

综合算法设计

实验日期

2014年5月26日

实验者

专业班级

信管

实验类型

综合型

一、实验目的、意义

1)掌握查找的含义

2)掌握基本查找操作的算法和实现

3)掌握动态查找算法的实现、应用场合与优缺点

4)能够针对具体问题,灵活选用适宜的查找算法

5)掌握排序的基本概念,对排序的稳定性及排序的时间复杂度有深刻的认识

6)对比折半插入排序和Shell排序的异同

7)掌握选择排序中堆排序的基本思想和算法实现

8)掌握快速排序的基本思想和算法实现

9)了解归并排序算法的基本思想和程序实现

10)了解基数排序算法的基本思想和程序实现

11)掌握Hash排序算法的基本思想和程序实现

在前面实验内容的基础上,根据实际问题选择相应算法。

二、实验基本原理与方法

本实验涉及各类查找和排序算法。

静态查找,折半查找的思想为:

设查找表中的元素存放在数组r中,数据元素的下标范围为[low,high],要查找的关键字值为key,中间元素的下标为mid=|_(low+high)/2_|(向下取整),令key与r[mid]的关键字比较:

1若key=r[mid].key,查找成功,下标为m的记录即为所求,返回mid。

2若key

3若key>r[mid].key,所要找的记录只能在右半部分记录中,再对右半部分使用折半查找法继续进行查找,搜索区间缩小了一半。

重复上述过程,直到找到查找表中某一个数据元素的关键字的值等于给定的值key,说明查找成功;或者出现low的值大于high的情况,说明查找不成功。

动态查找,编程实现一个开放式的高校本科招生最低录取分数线的查询系统,供师生和家长等查询,高校自愿放入该校的信息,可能随时有高校加入。

要求实现的查询功能有:

①查询等于用户给定分数的高校;

②查询大于(或小于)用户给定分数的高校③查询最低录取分数线在用户给定的分数段中的高校。

直接插入排序:

将当前无序区的第一个记录插入到有序区中适当位置。

折半查找法:

在有序表中进行,先确定表的中点位置,再通过比较确定下一步查找哪个半区。

Shell排序:

先取定一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组,所有距离为d1倍数的记录放在同一个组中,在各组内进行直接插入排序;然后取第二个增量重复上述分组和排序,直至所取的增量dt=1(dt

堆排序是利用大顶堆(或小顶堆)来选取当前无序区中关键字最大(或最小)的记录实现排序。

快速排序是对冒泡法的改进,其基本思想是:

通过一趟排序将待排文件分割成独立的两部分,其中一部分记录的关键字值均比另一部分记录的关键字小,然后分别对这两部分进行排序,以达到整个序列有序。

归并的思想:

将两个或两个以上的有序表合并成一个有序表。

利用归并的思想实现排序,假设初始的序列含有n个记录,可以看成n个有序的子序列,每个子序列的长度为m,然后把i(≥2)个子序列归并,得到n/i个长度为i的子序列;再继续归并,如此重复直到得到一个长度为n的有序序列为止。

通常使用的是i=2的二路归并法。

基数排序的基本思想是采用多关键字的排序。

设记录关键字R[i]由d个分量ki1,ki2,…,kid组成,设每个分量的取值范围为{ti|i=1,2,…,m,且t1

准备m个箱子,先按低位分箱再按序号一次将各个非空箱子里的记录收集起来,再对新收集起来的元素依次按较高的位分箱,直到最高位。

分箱即将第s个关键字等于ti的全部记录装入第i个箱子里。

按最高位分箱后,按序号一次将各个非空箱子里的记录收集起来,得到的元素序列就是有序的。

Hash排序是在Hash查找的基础上演变而来。

对待排序列采用单调的Hash函数,并用链地址法处理冲突,最后用一定规则收集存储好的数据从而得到有序序列。

三、实验内容及要求

访问

首先设法将网站上的数据导入一个文本文件,然后用程序去读取该文件中的数据,对数据的处理可以自行选择排序算法。

用菜单选择排序依据(如输入A按上场时间排序,输入B按投篮率排序……),处理后的数据用fwrite方式写入新文件中。

四、实验方案或技术路线(只针对综合型和设计型实验)

通过在程序中对结构体中指针的定义、赋值和引用从而完成对链表中特定数据的引用,结合文件的使用、函数的调用,自行选择排序算法、编制算法完成指定程序的编制、调试和执行,并通过观测程序输出结果验证程序设计的正确性。

实验过程总结如下:

(1)选定一种排序算法,对该算法实现的思路进行分析

(2)编程实现选定的算法 

(3)对所编写的程序进行调试 

(4)对程序运行的结果进行截图 

(5)对实验结果进行分析

五、实验原始记录(可附加页)

(程序设计类实验:

包括原程序、输入数据、运行结果、实验过程发现的问题及解决办法等;

分析与设计、软件工程类实验:

编制分析与设计报告,要求用标准的绘图工具绘制文档中的图表。

系统实施部分要求记录核心处理的方法、技巧或程序段;

其他实验:

包括实验输入数据,处理模型、输出数据及结果分析)

1、我选择的球队是火箭队,存放在文件read.txt文件中的内容如下:

2、源程序如下:

#include

#include

#include

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

{

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

{

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

{

if(players[j].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

{

if(players[j].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

{

if(players[j].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

{

if(players[j].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

{

if(players[j].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

{

if(players[j].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

{

if(players[j].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

{

if(players[j].assist

{

temp=players[j];

players[j]=players[j+1];

players[j+1]=temp;

}

}

}

}

//按抢断排序

voidSortBySteal(MatchData*players,intplayersNumber)

{

inti,j;

MatchDatat

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 工程科技 > 能源化工

copyright@ 2008-2023 冰点文库 网站版权所有

经营许可证编号:鄂ICP备19020893号-2