数据结构查找与排序报告Word格式文档下载.docx
《数据结构查找与排序报告Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数据结构查找与排序报告Word格式文档下载.docx（10页珍藏版）》请在冰点文库上搜索。
软件工程
实验成绩
实验名称
查找和排序
实验类型
验证
实验学时
2+8
一、实验目的和要求
1．掌握静态表查找存储结构和算法；
2．掌握动态表查找存储结构和算法
3．掌握折半查找算法和二叉排序树查找算法。
4．掌握常用的排序方法及实现；
5．深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用
实验要求：
了解掌握查找算法的基本思想和算法的实现；
了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。
二、实验环境（实验设备）
硬件:
微型计算机P5
软件:
WindowsXP+MicrosoftVisualC++6.0
三、实验原理及内容
实验题目:
给出n个学生的考试成绩表，每条信息由姓名和分数组成，试完成下列操作：
1.输入n个学生的姓名和成绩，保存于考试成绩表中（可用结构体数组）；
2.排序：
使用直接插入排序算法对学生的分数按升序排列，结果保存在原考试成绩表中。
3.输出：
按一行一个学生信息的方式输出n个这生考试成绩表。
4.查找：
对于经步骤2排序好的考试成绩表，请使用二分查找算法查找分数为x的学生，若存在则输出学生的姓名和分数，否则输出“查无此人”信息。
5．根据1中输入的成绩表，实现下列算法：
1）建立二叉排序树；
2）使用中序遍历算法输出遍历序列；
3）在二叉排序树中查找成绩为x的学生，若存在输出该学生信息，否则输出未找到信息。
6.将考试成绩表分别使用希尔排序、堆排序对分数进行升序和降序排列并输出。
实验前完成1，3；
实验中完成2，4题；
实验后完成：
5,6
实验解答：
1.学生考试成绩表的结构体定义
structmessage
{
intkey;
stringname;
floatscore;
message*lchild,*rchild;
};
2.学生考试成绩表的定义
messagem[max+1];
3.n个学生录入的算法代码
voidstudent:
:
Input（）
stringn;
floats;
cout<
<
"
请输入学生的信息"
endl;
for（inti=0;
;
i++）
{
cout<
请输入学生的星系和成绩：
cin>
>
n;
if（n=="
0"
）
break;
s;
m[i].key=i+1;
m[i].name=n;
m[i].score=s;
length++;
if（length>
=max）
{
cout<
表格已满，不能再输入"
}
}
}
4．按分数进行直接插入排序算法的代码
voidstudent:
InsertOrder（messagem[]）
messaget;
for（inti=1;
i<
length;
t=m[i];
intj,k;
for（j=0;
j<
i;
j++）
if（t.score<
m[j].score）
{
break;
}
for（k=i;
k>
j;
k--）
m[k]=m[k-1];
m[k]=t;
5.n个学生考试成绩表的输出算法
voidstudent:
Print（）
学生成绩表如下：
姓名：
m[i].name<
成绩：
m[i].score<
6．n个学生按分数进行二分查找算法。
intstudent:
BinarySearch（intlow,inthigh,floats）
intt=（low+high）/2;
if（low<
=high）
if（s==m[t].score）
查找的数据在"
t+1<
位置"
returnt;
if（s>
m[t].score）
low=t+1;
if（s<
high=t-1;
BinarySearch（low,high,s）;
else
数据查找失败"
return-1;
return-1;
7．按成绩建立二叉排序树算法
message*student:
BinarySortInsert（message*t,message*s）
if（t==NULL）
t=s;
elseif（s->
score<
t->
score）
t->
lchild=BinarySortInsert（t->
lchild,s）;
else
rchild=BinarySortInsert（t->
rchild,s）;
returnt;
BinarySort（）
message*s;
inti;
for（i=0;
s=newmessage;
s->
key=m[i].key;
name=m[i].name;
score=m[i].score;
lchild=NULL;
rchild=NULL;
root=BinarySortInsert（root,s）;
二t叉?
树º
¡
Â
遍À
¨
¦
历¤
²
数º
y列¢
D：
ê
o"
InterVisit（root）;
SearchStudent（）;
8．按成绩进行二叉排序树查找算法
SearchStudent（message*p,floats,int&
i）
if（p!
=NULL）
SearchStudent（p->
lchild,s,i）;
rchild,s,i）;
if（p->
score==s）
i++;
查找学生的姓名：
p->
name<
成绩：
9．你准备用于测试的数据表
姓名成绩
张山87
朱路65
唐凤76
梅丽67
郭阳89
刘基100
10.写出测试数据在直接插入排序时各趟的结果
第一趟：
6587766789100；
第二趟：
6576876789100；
第三趟：
6567768789100；
11.用于测试查找的分数
二分查找：
（1）用于查找成功的分数数据
100
（2）用于查找失败的分数数据
10
二叉排序树查找：
12.如果将你用于测试的学生分数构建小堆，则初始小堆是：
13.画出你用于测试的学生成绩表建立的二叉排序树
四、实验小结
1．直接插入排序的平均比较和平均移动次数分别是什么？
平均比较次数:
n平均移动次数:
n
2.静态和动态查找的区别是什么？
静态和动态查找区别是静态查找可以查找指定下标的数据，而动态查找则每次都需要循环。
3.通过本次实验，你有些什么收获？
有什么不足？
通过本次实验，我了解了排序和查找的基础用法，能够较熟练地运用他们来查读数据进行排序和查询。
但不足之处是，还不能对这些算法运用自如。
五、指导教师评语
成绩
批阅人
日期
升级会员 