算法基础===》==》=》查找 - 好文

一些基本的查找算法：

* 静态查找表
* 哈希表（Hash）查找
静态查找表：

* 顺序查找
* 折半查找
顺序查找：
int search_seq(seqTable ST,int key) { int i; ST.elem [0].key=key;//"哨兵" for(i=
ST.len;ST.elem[i].key!=key;i--);//从后往前查找 /*ST.elem [ST.len ].key=key;--"哨兵"
for(i=0;ST.elem[i].key!=key;i++);--从前往后查找*/ if(i<ST.len ) return i; else return
-1; }
------》源代码：
#include<iostream> using namespace std; #define MAXSIZE 100 //1.结构描述： typedef
struct { int key;//关键字域 }SElemType; typedef struct { SElemType *elem;
//数据元素存储空间地址 int len;//表长度 }seqTable; //2.顺序查找： int search_seq(seqTable ST,int
key) { int i; ST.elem [0].key=key;//"哨兵" for(i=ST.len;ST.elem[i].key!=key;i--);
//从后往前查找 /*ST.elem [ST.len ].key=key;--"哨兵"
for(i=0;ST.elem[i].key!=key;i++);--从前往后查找*/ if(i<ST.len ) return i; else return
-1; } int main() { seqTable ST; int key; int index; SElemType Data[MAXSIZE]={34,
44,43,12,53,55,73,64,77}; ST.elem =Data; ST.len =9; cout<<"请输入代查找的关键字："; cin>>
key; index=search_seq(ST,key); if(index==-1) cout<<"找不到关键字为"<<key<<"的元素！"<<endl;
else cout<<"关键字为"<<key<<"的元素在查找表索引号为："<<index<<endl;; return 0; }
*ps:顺序查找法既实用于线性表的顺序存储结构，也适用于线性表的链式存储结构。使用单链表作为存储时，在扫描过程中必须从第一个
结点开始往后进行扫描。在顺序查找的过程中可以设置“哨兵“来提高效率。虽然顺序查找的算法结构简单，但效率比较低。特别是当数据量较大时，必须采用更优的查找方法。

折半查找：
int search_Bin(seqTable ST,int key) { int low,high,mid; low=0;high=ST.len-1;
//置区间初值。 while(low<=high) { mid=(low+high)/2; if(key==ST.elem[mid].key) return
mid;//找到待查元素 else if(key<ST.elem[mid].key) high=mid-1;//继续在前半区查找 else low=mid+1;
//继续在后半区查找 } return -1;//表中不存在待查元素。 }
------》源代码：
#include<iostream> using namespace std; #define MAXSIZE 100 //1.结构描述： typedef
struct { int key;//关键字域 }SElemType; typedef struct { SElemType *elem;
//数据元素存储空间地址 int len;//表长度 }seqTable; //2.折半查找： int search_Bin(seqTable ST,int
key) { int low,high,mid; low=0;high=ST.len-1;//置区间初值。 while(low<=high) { mid=(
low+high)/2; if(key==ST.elem[mid].key) return mid;//找到待查元素 else if(key<ST.elem[
mid].key) high=mid-1;//继续在前半区查找 else low=mid+1;//继续在后半区查找 } return -1;
//表中不存在待查元素。 } int main() { seqTable ST; int key; int index; SElemType Data[
MAXSIZE]={34,44,43,12,53,55,73,65,77}; ST.elem =Data; ST.len =9; cout<<
"请输入代查找的关键字："; cin>>key; index=search_Bin(ST,key); if(index==-1) cout<<"找不到关键字为"
<<key<<"的元素！"<<endl; else cout<<"关键字为"<<key<<"的元素在查找表索引号为："<<index<<endl;;
return 0; }
*ps:
折半查找，又称二分查找(一般采用递归顺序)，它是一种效率较高的查找方式，但二分查找有一定的条件限制：要求线性表必须采用顺序存储结构，并且表中元素必须按关键字有序排列。

哈希表（Hash）查找：
int HashAddr(Student hashTab[],Student stu,int m) { int hr; hr=atoi(stu.tel+9)%
3; return hr; } void FillHashTable(Student hashTab[],int n,int m)//n代表了学生的数量 {
int i,hr; for(i=0;i<n;i++) { hr=HashAddr(hashTab,stu[i],m); while(strcmp(hashTab
[hr].tel,"")) hr=(hr+1)%m; hashTab[hr]=stu[i]; } } void DispHashTab(Student
hashTab[],int m) { int i=0; for(i=0;i<m;i++) cout<<hashTab[i].tel<<endl; cout<<
endl; } void HashSearch(Student hashTab[],int m,char tel[]) { Student s;int hr;
strcpy(s.tel,tel); hr=HashAddr(hashTab,s,m); while(strcmp(hashTab[hr].tel,"")&&
strcmp(hashTab[hr].tel,tel)) hr++; if(strcmp(hashTab[hr].tel,"")) cout<<"Find
it!"<<'\t'<<hashTab[hr].name<<'\t'<<hashTab[hr].age<<'\t'<<hashTab[hr].tel<<endl
; else cout<<"Not find!"<<endl; }
------》源代码：
#include <iostream> #include <string.h> using namespace std; //1.结构描述： typedef
struct{ char name[10]; int age; char tel[12]; }Student; //2.初始化结构体： Student stu[
]= { {"Tom",23,"12173873213"}, {"Rob",21,"13345612284"}, {"Yin",19,"42332133213"
} }; //3.建立哈希表（Hash）地址： int HashAddr(Student hashTab[],Student stu,int m) { int
hr; hr=atoi(stu.tel+9)%3; return hr; } //4.填充哈希表： void FillHashTable(Student
hashTab[],int n,int m)//n代表了学生的数量 { int i,hr; for(i=0;i<n;i++) { hr=HashAddr(
hashTab,stu[i],m); while(strcmp(hashTab[hr].tel,"")) hr=(hr+1)%m; hashTab[hr]=
stu[i]; } } //5.显示哈希表： void DispHashTab(Student hashTab[],int m) { int i=0; for(
i=0;i<m;i++) cout<<hashTab[i].tel<<endl; cout<<endl; } //6.哈希表搜索
telephonenumber： void HashSearch(Student hashTab[],int m,char tel[]) { Student s
;int hr; strcpy(s.tel,tel); hr=HashAddr(hashTab,s,m); while(strcmp(hashTab[hr].
tel,"")&&strcmp(hashTab[hr].tel,tel)) hr++; if(strcmp(hashTab[hr].tel,"")) cout
<<"Find it!"<<'\t'<<hashTab[hr].name<<'\t'<<hashTab[hr].age<<'\t'<<hashTab[hr].
tel<<endl; else cout<<"Not find!"<<endl; } void main() { //初始化工作： Student
hashTab[3]; for(int i=0;i<3;i++) strcpy(hashTab[i].tel,""); //Hash表的填充与显示
FillHashTable(hashTab,3,3); DispHashTab(hashTab,3); //Hash 搜索 telephonenumber
HashSearch(hashTab,3,"13345612284"); }
*ps:哈希表查找是一种较高级的查找方式，Hash表在海量数据处理中有着广泛应用。

Hash优缺点:
优点：不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即0(1）【时间复杂度】的时间级。实际上，这只需要几条机器指令。

哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。
如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

缺点：它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。

查找Tips：

***无论是顺序查找、二分查找，还是哈希表查找，都有各自的优势。要根据情景特点，选择最合适的查找算法。顺序查找不一定效率最低，有时甚至会优于二分查找，所以具体情况要具体应对。

热门工具换一换