篇一:数据结构查找方法及原理
【数据结构】查找:线性表的查找
2010-09-03 13:01:26| 分类: 数据结构 |字号大中小订阅
本章简介
由于查找运算的使用频率很高,几乎在任何一个计算机系统软件和应用软件中都会涉及到,所以当问题所涉及的数据量相当大时,查找方法的效率就显得格外重要。在一些实时查询系统中尤其如此。因此,本章将系统地讨论各种查找方法,并通过对它们的效率分析来比较各种查找方法的优劣。
查找的基本概念
1、查找表和查找
一般,假定被查找的对象是由一组结点组成的表(Table)或文件,而每个结点则由若干个数据项组成。并假设每个结点都有一个能惟一标识该结点的关键字。
查找(Searching)的定义是:给定一个值K,在含有n个结点的表中找出关键字等于给定值K的结点。若找到,则查找成功,返回该结点的信息或该结点在表中的位置;否则查找失败,返回相关的指示信息。
2、查找表的数据结构表示
(1)动态查找表和静态查找表
若在查找的同时对表做修改操作(如插入和删除),则相应的表称之为动态查找表。否则称之为静态查找表。
(2)内查找和外查找
和排序类似,查找也有内查找和外查找之分。若整个查找过程都在内存进行,则称之为内查找;反之,若查找过程中需要访问外存,则称之为外查找。
3、平均查找长度ASL
查找运算的主要操作是关键字的比较,所以通常把查找过程中对关键字需要执行的 平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。
平均查找长度 ASL(Average Search Length)定义为:
其中:
①n是结点的个数;
②Pi是查找第i个结点的概率。若不特别声明,认为每个结点的查找概率相等,即
pl=p2…=pn=1/n
③ci是找到第i个结点所需进行的比较次数。
注意:
为了简单起见,假定表中关键字的类型为整数:
typedef int KeyType; //KeyType应由用户定义
顺序查找(Sequential Search)
在表的组织方式中,线性表是最简单的一种。顺序查找是一种最简单的查找方法。
1、顺序查找的基本思想
基本思想是:从表的一端开始,顺序扫描线性表,依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等,则查找成功;若扫描结束后,仍未找到关键字等于K的结点,则查找失败。
2、顺序查找的存储结构要求
顺序查找方法既适用于线性表的顺序存储结构,也适用于线性表的链式存储结构(使用单链表作存储结构时,扫描必须从第一个结点开始)。
3、基于顺序结构的顺序查找算法
(1)类型说明
typedef struct{
KeyType key;
InfoType otherinfo; //此类型依赖于应用
}NodeType;
typedef NodeType SeqList[n+1]; //0号单元用作哨兵
(2)具体算法
int SeqSearch(Seqlist R,KeyType K)
{ //在顺序表R[1..n]中顺序查找关键字为K的结点,
//成功时返回找到的结点位置,失败时返回0
int i;
R[0].key=K; //设置哨兵
for(i=n;R[i].key!=K;i--); //从表后往前找
return i; //若i为0,表示查找失败,否则R[i]是要找的结点
} //SeqSearch
注意:
监视哨设在高端的顺序查找【参见练习】
(3)算法分析
① 算法中监视哨R[0]的作用
为了在for循环中省去判定防止下标越界的条件i≥1,从而节省比较的时间。
②成功时的顺序查找的平均查找长度:
在等概率情况下,pi=1/n(1≤i≤n),故成功的平均查找长度为
(n+…+2+1)/n=(n+1)/2
即查找成功时的平均比较次数约为表长的一半。
若K值不在表中,则须进行n+1次比较之后才能确定查找失败。
③表中各结点的查找概率并不相等的ASL
顺序查找演示过程【动画演示】
【例】在由全校学生的病历档案组成的线性表中,体弱多病同学的病历的查找概率必然高于健康同学的病历,由于上式的ASLsq在pn≥pn-1≥…≥p2≥p1时达到最小值。
若事先知道表中各结点的查找概率不相等和它们的分布情况,则应将表中结点按查找概率由小到大地存放,以便提高顺序查找的效率。
为了提高查找效率,对算法SeqSearch做如下修改:每当查找成功,就将找到的结点和其后继(若存在)结点交换。这样,使得查找概率大的结点在查找过程中不断往后移,便于在以后的查找中减少比较次数。
④顺序查找的优点
算法简单,且对表的结构无任何要求,无论是用向量还是用链表来存放结点,也无论结点之间是否按关键字有序,它都同样适用。
⑤顺序查找的缺点
查找效率低,因此,当n较大时不宜采用顺序查找。
二分查找
1、二分查找(Binary Search)
二分查找又称折半查找,它是一种效率较高的查找方法。
二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。
2、二分查找的基本思想
二分查找的基本思想是:(设R[low..high]是当前的查找区间)
篇二:数据结构查找方法
常用查找算法:
二分查找(Binary Search)
二分查找又称折半查找,它是一种效率较高的查找方法。
二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。
二分查找的基本思想
二分查找的基本思想是:(设R[low..high]是当前的查找区间)
(1)首先确定该区间的中点位置:
(2)然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,具体方法如下:
①若R[mid].key>K,则由表的有序性可知R[mid..n].keys均大于K,因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R[1..mid-1]中,故新的查找区间是左子表R[1..mid-1]。
②类似地,若R[mid].key<K,则要查找的K必在mid的右子表R[mid+1..n]中,即新的查找区间是右子表R[mid+1..n]。下一次查找是针对新的查找区间进行的。
因此,从初始的查找区间R[1..n]开始,每经过一次与当前查找区间的中点位置上的结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点,或者直至当前的查找区间为空(即查找失败)时为止。
篇三:数据结构查找
南京信息工程大学 实验(实习)报告
一、实验目的
查找(顺序查找、折半查找)
二、实验内容
解和掌握静态查找表的查找过程;
掌握顺序查找算法;
掌握折半查找算法
要求完成静态查找表的顺序查找和折半查找算法的实现。
三、实验步骤
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define N 10
typedef int DataType;//定义比较的元素类型
//静态查找表的顺序存储结构
typedef struct{
DataType * data;//数据元素存储空间基址,按实际长度分配,0号单元留空
//建表时按实际长度分配,0 号单元留空int length;//表长度
}SSTable;
//创建一个静态表,内容为20以内的随机数
void createST(SSTable* ST,int n){
int i;
time_t t;
if(ST!=NULL){
ST->data=(DataType*)calloc(n+1,sizeof(DataType));if(ST->data!=NULL){
srand((unsigned) time(&t));
for(i=1;i<=n;i++){
ST->data[i]=rand() ;//产生20以内的随机数 }
ST->length=n;
}
}
}
//创建一个静态表,内容按从小到大排列,以便折半查找 void createST_binary(SSTable* ST,int n){
int i,j=0;
time_t t;
if(ST!=NULL){
ST->data=(DataType*)calloc(n+1,sizeof(DataType));
if(ST->data!=NULL){
for(i=1;i<=n;i++){
ST->data[i]=j;
j+=4;
}
ST->length=n;
}
}
}
//打印出静态表的内容
void print_SSTable(SSTable* ST){
int i,n=ST->length;
if(ST!=NULL){
for(i=1;i<=n;i++){
printf("%d ",ST->data[i]);
}
printf("\n");
}
}int search_seq(SSTable ST,DataType key){
int i;
if(ST.data==NULL)return 0;
ST.data[0]=key;//设置监视哨。目的在于免去查找过程中每一步都要检测整
//个表是否查找完毕,是一个很有效的程序设计技巧 。监视
//哨也可以设在高下标处。
for(i=ST.length;ST.data[i]!=key;i--);
return i;
}
int search_binary(SSTable ST,DataType key){
int low,high,mid;
low=1;
high=ST.length;
while(low<=high){//当表空间存在时
mid=(low+high)/2;
if(ST.data[mid]==key){
return mid;//查找成功,返回mid
}
if(key<ST.data[mid]){
high=mid-1;//继续在前半区间查找
}else{
low=mid+1;//继续在后半区间查找
}
}
return 0;//查找失败
}
int main(){
int n=20;//在20个数中查找,方便看结果,不要设置得太大
SSTable ST,ST_binary;//分别用于顺序查找和折半查找的静态表index indtb[n+1];//索引表,用于分块查找
createST(&ST,n);//创建一个随机静态表
createST_binary(&ST_binary,n);//创建一个从小到大顺序排列的静态表
//采用顺序查找
printf("原始数据:");
print_SSTable(&ST);
printf("顺序查找5的结果:%d\n",search_seq(ST,5));
printf("顺序查找10的结果:%d\n",search_seq(ST,10));
printf("顺序查找12的结果:%d\n",search_seq(ST,12));
printf("顺序查找15的结果:%d\n",search_seq(ST,15));
printf("顺序查找20的结果:%d\n",search_seq(ST,20));
printf("--------------------------------------------\n"); //采用折半查找
printf("原始数据:");
print_SSTable(&ST_binary);
printf("折半查找5的结果:%d\n",search_binary(ST_binary,5)); printf("折半查找10的结果:%d\n",search_binary(ST_binary,10)); printf("折半查找12的结果:%d\n",search_binary(ST_binary,12)); printf("折半查找15的结果:%d\n",search_binary(ST_binary,15)); printf("折半查找20的结果:%d\n",search_binary(ST_binary,20)); system("pause");//暂停一下,看看结果
free(ST.data);//不要忘了释放堆空间
return 0;
}
四、实验结果
五、实验小结
顺序查找
思路:从表中最后一个记录开始,逐个进行记录的关键字和
给定值的比较,若某个记录的关键字和给定值比较相等,则
返回返回记录所在的位置,或查找完所有记录后还没有发现
符合的记录,则查找失败。
折半查找(Binary Search):
当记录的key按关系有序时可以使用折半查找
思路:对于给定key值,逐步确定待查记录所在区间,每次将搜索空间减少一半(折半),
直到查找成功或失败为止