实验8查找与排序算法的实现和应用.docx
《实验8查找与排序算法的实现和应用.docx》由会员分享，可在线阅读，更多相关《实验8查找与排序算法的实现和应用.docx（20页珍藏版）》请在冰点文库上搜索。
实验8查找与排序算法的实现和应用
班级学号姓名实验组别
实验日期室温报告日期成绩
报告内容：
（目的和要求、原理、步骤、数据、计算、小结等）
实验名称：
查找与排序算法的实现和应用
实验目的：
1.掌握顺序表中查找的实现及监视哨的作用。
2.掌握折半查找所需的条件、折半查找的过程和实现方法。
3.掌握二叉排序树的创建过程，掌握二叉排序树查找过程的实现。
4.掌握哈希表的基本概念，熟悉哈希函数的选择方法，掌握使用线性探测法和链地址法进行冲突解决的方法。
5.掌握直接插入排序、希尔排序、快速排序算法的实现。
实验环境（硬/软件要求）：
Windows2000,VisualC++6.0
实验内容：
通过具体算法程序，进一步加深对各种查找算法的掌握，以及对实际应用中问题解决方法的掌握。
各查找算法的输入序列为：
265371611159154819输出要求：
查找关键字37，给出查找结果。
对于给定的某无序序列，分别用直接插入排序、希尔排序、快速排序等方法进行排序，并输出每种排序下的各趟排序结果。
各排序算法输入的无序序列为：
265371611159154819。
实验要求：
一、查找法
1.顺序查找
首先从键盘输入一个数据序列生成一个顺序表，然后从键盘上任意输入一个值，在顺序表中进行查找。
2.折半查找
任意输入一组数据作为个数据元素的键值，首先将此序列进行排序，然后再改有序表上使用折半查找算法进一
对给定值key的查找。
3.二叉树查找
任意输入一组数据作为二叉排序树中节点的键值，首先创建一颗二叉排序树，然后再次二叉排序树上实现对一
定k的查找过程。
4.哈希表查找
任意输入一组数值作为个元素的键值，哈希函数为Hash（key）=key%11,用线性探测再散列法解决冲突问题。
二、排序算法
编程实现直接插入排序、希尔排序、快速排序各算法函数；并编写主函数对各排序函数进行测试。
实验原理：
1.顺序查找：
在一个已知无（或有序）序队列中找出与给定关键字相同的数的具体位置。
原理是让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
2.哈希查找：
哈希查找的操作步骤：
⑴用给定的哈希函数构造哈希表；⑵根据选择的冲突处理方法解决地址冲突；⑶在哈希表的基础上执行哈希查找。
哈希查找的本质是先将数据映射成它的哈希值。
哈希查找的核心是构造一个哈希函数，它将原来直观、整洁的数据映射为看上去似乎是随机的一些整数。
哈希查找的产生有这样一种背景——有些数据本身是无法排序的（如图像），有些数据是很难比较的（如图像）。
如果数据本身是无法排序的，就不能对它们进行比较查找。
如果数据是很难比较的，即使采用折半查找，要比较的次数也是非常多的。
因此，哈希查找并不查找数据本身，而是先将数据映射为一个整数（它的哈希值），并将哈希值相同的数据存放在同一个位置一即以哈希值为索引构造一个数组。
在哈希查找的过程中，只需先将要查找的数据映射为它的哈希值，然后查找具有这个哈希值的数据，这就大大减少了查找次数。
如果构造哈希函数的参数经过精心设计，内存空间也足以存放哈希表，查找一个数据元素所需的比较次数基本上就接近于一次。
3.排序算法:
排序（Sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。
流程图：
是
否
实验代码：
一、查找法
1、顺序查找
#include
#defineMAX100
typedefintkeytype;
typedefstruct
{keytypekey;
}elemtype;
typedefstruct
{elemtypeelem[MAX+1];
intlength;
}SStable;
voidcreate_seq（SStable*list）;
intseq_search（SStable*list,keytypek）;
voidmain（）
{SStable*list,table;
keytypekey;
inti;
list=&table;
printf（"请输入顺序表的长度：
"）;
scanf（"%d",&list->length）;
create_seq（list）;
printf（"创建的顺序表内容：
\n"）;
for（i=0;ilength;i++）
printf（"list.elem[%d].key=%d\n",i+1,list->elem[i].key）;
printf（"输入查找关键字：
"）;
scanf（"%d",&key）;
seq_search（list,key）;
}
voidcreate_seq（SStable*list）
{inti;
printf（"请输入顺序表的内容：
\n"）;
for（i=0;ilength;i++）
{printf（"list.elem[%d].key=",i+1）;
scanf（"%d",&list->elem[i].key）;
}
}
intseq_search（SStable*list,keytypek）
{inti=0,flag=0;
while（ilength）
{if（list->elem[i].key==k）
{printf（"查找成功.\n"）;
flag=1;
printf（"list.elem[%d].key=%d\n",i+1,k）;
}
i++;
}
if（flag==0）
printf（"没有找到数据%d!
\n",k）;
return（flag）;
}
2、折半查找
#include
#defineMAX100
typedefstruct
{intelem[MAX+1];
intlength;
}Stable;
voidcreat_seq（Stable*list）;
intsort_seq（Stable*list）;
intbin_search（Stable*list,intk,intlow,inthigt）;
voidmain（）
{Stable*list,table;
inti,key;
list=&table;
printf（"请输入线性表的长度：
"）;
scanf（"%d",&list->length）;
creat_seq（list）;
sort_seq（list）;
printf（"排列后的数据\n"）;
for（i=1;i<=list->length;i++）
printf（"list.elem[%d].key=%d\n",i,list->elem[i]）;
printf（"\n请输入查找的值:
"）;
scanf（"%d",&key）;
bin_search（list,key,1,list->length）;
}
voidcreat_seq（Stable*list）
{inti;
printf（"请输入顺序表的内容:
\n"）;
for（i=1;i<=list->length;i++）
{printf（"list.elem[%d].key=",i）;
scanf（"%d",&list->elem[i]）;
}
}
intsort_seq（Stable*list）
{inti,j,flag;
for（i=1;ilength;i++）
{flag=0;
for（j=1;jlength-i+1;j++）
if（list->elem[j]>list->elem[j+1]）
{list->elem[0]=list->elem[j+1];
list->elem[j+1]=list->elem[j];
list->elem[j]=list->elem[0];
flag=1;
}
if（flag==0）return1;
}
}
intbin_search（Stable*list,intk,intlow,inthigh）
{intmid;
if（low>high）
{printf（"没有找到要查找的值\n"）;
return（0）;
}
mid=（low+high）/2;
if（list->elem[mid]==k）
{printf（"查找成功\n"）;
printf（"list[%d]=%d\n",mid,k）;
return（mid）;
}
else
if（list->elem[mid]return（bin_search（list,k,mid+1,high））;
else
return（bin_search（list,k,low,mid-1））;
}
3、二叉树查找
#include
#include
typedefstructbitnode
{
intkey;
structbitnode*lchild;
structbitnode*rchild;
}bnode;
voidins_bitree（bnode*p,intk）
{
bnode*q;
if（p->key>k&&p->lchild）
ins_bitree（p->lchild,k）;
else
if（p->key<=k&&p->rchild）
ins_bitree（p->rchild,k）;
else
{
q=（bnode*）malloc（sizeof（bnode））;
q->key=k;
q->lchild=NULL;
q->rchild=NULL;
if（p->key>k）
p->lchild=q;
else
p->rchild=q;
}
}
voidbit_search（bnode*p,intk）
{
if（p->key>k&&p->lchild）
bit_search（p->lchild,k）;
else
if（p->keyrchild）
bit_search（p->rchild,k）;
else
if（p->key==k）
printf（"查找成功!
\n"）;
else
printf（"%d不存在!
\n"）;
}
voidinorder（bnode*p）
{
if（p）
{
inorder（p->lchild）;
printf（"%4d",p->key）;
inorder（p->rchild）;
}
}
voidmain（）
{intk;
bnode*p;
p=NULL;
printf（"请输入二叉树结点的值，输入0结束:
\n"）;
scanf（"%d",&k）;
p=（bnode*）malloc（sizeof（bnode））;
p->key=k;
p->lchild=NULL;
p->rchild=NULL;
scanf（"%d",&k）;
while（k>0）
{
ins_bitree（p,k）;
scanf（"%d",&k）;
}
printf（"\n"）;
printf（"二叉树排序的结果:
"）;
inorder（p）;
printf（"\n请输入查找的值:
\n"）;
scanf（"%d",&k）;
bit_search（p,k）;
}
4、哈希表查找
#include
#defineMAX11
voidins_hash（inthash[],intkey）
{
intk,k1,k2;
k=key%MAX;
if（hash[k]==0）
{
hash[k]=key;
return;
}
else
{k1=k+1;
while（k1=0）
k1++;
if（k1{
hash[k1]=key;
return;
}
k2=0;
while（k2=0）
k2++;
if（k2{
hash[k2]=key;
return;
}
}
}
voidout_hash（inthash[]）
{
inti;
for（i=0;iif（hash[i]）
printf（"hash[%d]=%d\n",i,hash[i]）;
}
voidhash_search（inthash[],intkey）
{
intk,k1,k2,flag=0;
k=key%MAX;
if（hash[k]==key）
{
printf（"hash[%d]=%d",k,key）;
flag=1;
}
else
{
k1=k+1;
while（k1=key）
k1++;
if（k1{printf（"hash[%d]=%d",k1,key）;
flag=1;}
k2=0;
if（!
flag）
{while（k2=key）
k2++;
if（k2{printf（"hash[%d]=%d",k2,key）;
flag=1;}
}
if（flag）
{printf（"查找成功！
\n"）;
return;
}else
{printf（"查找失败！
\n"）;
return;}
}
}
voidmain（）
{inti,key,k,sum=0;
inthash[MAX];
for（i=0;ihash[i]=0;
printf（"请输入数据，以0结束：
\n"）;
scanf（"%d",&key）;
sum++;
while（key&&sum{ins_hash（hash,key）;
scanf（"%d",&key）;
sum++;
}
printf（"\n"）;
out_hash（hash）;
printf（"\n"）;
printf（"请输入查找的值：
"）;
scanf（"%d",&k）;
hash_search（hash,k）;
printf（"\n"）;
}
二、排序算法
#include
#include
#definesize11
typedefchardatatype;
typedefstruct
{intkey;
datatypeothers;
}rectype;
voidINSERTSORT（rectypeR[]）
{inti,j;
for（i=2;i<=size;i++）
{R[0]=R[i];
j=i-1;
while（R[0].key{R[j+1]=R[j];j--;}
R[j+1]=R[0];}
}
voidSHELLSORT（rectypeR[],intn）
{inti,j,h;
rectypetemp;
h=n/2;
while（h>0）
{for（j=h;j<=n-1;j++）
{temp=R[j];
i=j-h;
while（（i>=0）&&temp.key{R[i+h]=R[i];
i=i-h;}
R[i+h]=temp;}
h=h/2;}
}
intPARTITION（rectypeR[],intl,inth）
{inti,j;
rectypetemp;
i=1;j=h;temp=R[i];
do
{while（（R[j].key>=temp.key）&&（ij--;
if（iwhile（（R[i].key<=temp.key）&&（ii++;
if（iwhile（i!
=j）;
R[i]=temp;
returni;
}
voidQUICKSORT（rectypeR[],ints1,intt1）
{inti;
if（s1{i=PARTITION（R,s1,t1）;
QUICKSORT（R,s1,i-1）;
QUICKSORT（R,i+1,t1）;
}
}
voidmain（）
{rectypeR[size];
inti;
printf（"请输入使用插入算法排序的10个数据\n"）;
for（i=1;iprintf（"\n插入排序之前\n"）;
for（i=1;iINSERTSORT（R）;
printf（"\n插入排序之后\n"）;
for（i=1;iprintf（"\n请输入使用希尔顿算法排序的10个数据\n"）;
for（i=0;iprintf（"\n希尔排序之前\n"）;
for（i=0;iSHELLSORT（R,10）;
printf（"\n希尔排序之后\n"）;
for（i=0;iprintf（"请输入使用快速算法排序的10个数据\n"）;
for（i=1;iprintf（"\n快速排序之前\n"）;
for（i=1;iQUICKSORT（R,1,10）;
printf（"\n快速排序之后\n"）;
for（i=1;i}
实验结果
顺序查找：
折半查找：
二叉树查找：
哈希表查找：
排序：
实验小结：
此次操作证明可以用编程实现查找与排序，实验结果正确。
通过本次实验，我对查找排序与二分查找、哈希查找、二叉树查找等有了更加深刻的了解。
练习了指针，查找等操作，熟练掌握树的操作。
对各种算法有了更加深刻的理解。
通过这次写实验报告，我深切的理解了这门课的本质。
刚开始学这门课时，当时还不清楚这门课程的目的，现在，我真正的理解了：
数据结构像是身体的骨骼，而C语言是填充这骨骼的肉体，二者相结合才能使整个程序更加完整，健全。
数据结构是个框架，模型，抽象数据类型中列举了各种操作，而所用的C语言，将各种操作描述出来构成算法。
数据结构+算法=程序设计。
在这次设计的过程中，我还遇到了，很多的问题。
顺序表是按顺序存储的，用了一维数组来存储，又结合C语言的程序设计，但是，在执行时出现了问题。
后来问同学，指出我的错误，不过获益不少。
我又重新整理思路，把顺序表的基本操作写好了。
虽然走了很多弯路，但是让我认识到，一定要创新，大胆，不能按照旧的思路去干新的事情。
但是细节上出了问题。
比如说，有些变量的重复定义，有些变量又没有定义，在调用函数，就直接复制过来，没有改参数……通过修改，我深刻理解到：
细节决定成败，在以后，不管做任何事情都要认真，细心。
升级会员 