篇一：数据结构查找方法及原理
【数据结构】查找：线性表的查找
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值，逐步确定待查记录所在区间，每次将搜索空间减少一半（折半），
直到查找成功或失败为止
《数据结构查找》
由：免费论文网互联网用户整理提供,链接地址：
http://m.csmayi.cn/show/133061.html
转载请保留,谢谢!
- 上一篇：俩学一做查摆问题征求意见表