数据结构基础查找算法（一）

我不是女神ヾ 2022-08-05 11:16 148阅读 0赞

1. 顺序查找

顺序查找就是从序列的第一个元素开始，从头到尾逐个查找，直到找到所需的数据或搜索完整个序列。

程序设计如下：

\#include <stdio.h>

\#pragma hdrstop

\#include <tchar.h>

\#pragma argsused

int search(int \*,int,int);

int \_tmain(int argc, \_TCHAR\* argv\[\])

inti,a\[10\],n,x;

printf("请输入10个数字：\\n");

for(i=0;i<10;i++)

scanf("%d",a+i);

printf("\\n");

printf("请输入要查找的数：\\n");

scanf("%d",&x);

n=search(a,10,x);

if(n<=0)

printf("没有找到你想找得数！");

else

printf("你想找的数 %d 在数列的第 %d 个位置。",x,n);

return0;

int search(int \*a,int num,int value)

intresult=0;

inti;

for(i=0;i<num;i++)

if(value==a\[i\])

result=i+1;

break;

return(result);

2. 折半查找

折半查找是将有序数列不断的缩小一半，直到找到该元素或折半区域的首元素位置高于尾元素位置为止。

程序如下：

\#include <stdio.h>

\#pragma hdrstop

\#include <tchar.h>

\#pragma argsused

int search(int \*,int,int);

int \_tmain(int argc, \_TCHAR\* argv\[\])

inti,a\[10\],n,x;

printf("请输入10个数字：\\n");

for(i=0;i<10;i++)

scanf("%d",a+i);

printf("\\n");

printf("请输入要查找的数：\\n");

scanf("%d",&x);

n=search(a,10,x);

if(n<=0)

printf("没有找到你想找得数！");

else

printf("你想找的数 %d 在数列的第 %d 个位置。",x,n);

return0;

int search(int \*a,int num,int value)

intlow,mid,high;

low=0;high=num-1;

while(low<=high)

mid=(low+high)/2;

if(a\[mid\]==value)

returnmid+1;

elseif(a\[mid\]>value)

high=mid-1;

else

low=mid+1;

return-1;

该查找算法需要数列是有序的数列。折半查找是一种有效的查找方法，它将查找的范围不断的缩小一半，因此可以明显的减少比较次数。

3. 分块查找

分块查找又称为索引顺序查找，是介于顺序查找和二分查找之间的一种查找方法，它是顺序查找的一种方法。

程序设计如下：

\#include <stdio.h>

\#pragma hdrstop

\#include <tchar.h>

\#pragma argsused

typedef struct\{

int key;

int start;

int end;

\}Index;

int search(int \*,int);

Index index\[2\];

int \_tmain(int argc, \_TCHAR\* argv\[\])

inti,a\[10\],n,x,j=-1;

printf("请输入10个数字：\\n");

for(i=0;i<10;i++)

scanf("%d",a+i);

printf("请输入要查找的数：\\n");

scanf("%d",&x);

for(i=0;i<2;i++)

index\[i\].start=j+1;

j=j+1;

index\[i\].end=j+4;

j=j+4;

index\[i\].key=j;

n=search(a,x);

if(n<=0)

printf("没有找到你想找得数！");

else

printf("你想找的数 %d 在数列的第 %d 个位置。",x,n);

return0;

int search(int \*a,int value)

inti,j;

i=0;

while((i<2)&&(value>a\[index\[i\].key\]))

i++;

if(i>=2)

return-1;

j=index\[i\].start;

while(j<=index\[i\].end&&a\[j\]!=value)

j++;

if(j>index\[i\].end)

j=-1;

returnj;

需要注意的是：分块查找中块的大小可根据表的特征进行分块不一定要将线性表分为大小相等的若干块，各块可放在不同的向量中，也可将每一块存放在一个

分块查找的优点：

（1） 在表中插入或删除一个记录中，只要找到该记录所属的块，就在该块内进行插入或删除运算。

（2） 因块内记录的存放是任意的，所以插入和删除比较容易，无需移动大量的记录。

而这种方法的主要代价就是增加了一个辅助数组的内存空间。

4. 哈希查找

哈希查找是通过计算机数据元素的存储地址进行查找的一种方法。其操作步骤为：

（1） 用给定的哈希函数构造哈希表

（2） 根据选择的冲突处理方法解决地址冲突

（3） 在哈希表的基础上执行哈希查找

建立哈希表的步骤：

（1） 取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的存储空间还没有被占用，则将该元素存入，否则执行（2）解决冲突。

（2） 根据选择的冲突处理方法，计算关键字key的下一个存储地址，若下一个地址仍被占用，则继续执行步骤（2），直到找到能用的存储地址为止。

设哈希表为\[0~m-1\]，哈希函数取H(key)，解决冲突的方法是R(x)，则哈希查找的步骤如下：

（1） 给定K值，计算哈希地址Di=H(k)；若HST为空，则查找失败，若HST=k，则查找成功。否则执行步骤（2）。

（2） 重复计算处理冲突的下一个存储地址Dk=R(Dk-1)，直到HST\[Dk\]为空，或HST\[Dk\]=k为止。若HST\[Dk\]=k，则查找成功，否则查找失败。

在应用哈希查找时，用先设定一个哈希函数和一个冲突处理的方法。

哈希函数的构造有以下几种方法：

（1） 直接定址法

取关键字或者关键字的某个线性函数值为哈希地址。即：

H(key)=key或H(key)=a\*key+b；其中，a,b为常数，这种哈希函数叫做自身函数。

（2） 数字分析法

假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

（3） 平方取中法

取关键字平方后的中间几位为哈希地址。这是一种较常用的构造哈希函数的方法。通常在选定哈希函数时不一定能知道关键字的全部情况。取其中哪几位也不合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到哈希地址也是随机的，取得位数由表长决定。

（4） 折叠法

将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（含去进位）作为哈希地址，这种方法称为折叠法。关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到哈希地址。

（5） 除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即：

H(key)=key MOD p, p<=m

这是一种最简单，最常用的构造哈希函数的方法，它不仅可以对关键字直接取模也可以在折叠，平方取中等运算之后取模。

（6） 随机数法

选择一个随机函数，取关键字的随机函数值为哈希地址，即H(key)=random(key)。其中，random为随机函数，通常，当关键字长度不等时采用此法构造呼吸函数较恰当。

处理冲突的方法：

（1） 开放定址法

Hi=(H(key)+di) MOD m i=1,2,3,…,k(k<=m-1)

其中，H(key)为哈希函数，m为哈希表表长，di为增量序列

（2） 再哈希法

RHi均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生“聚集”，但增加了计算的时间。

（3） 链地址法

将所有关键字为同义词的记录存储在同一线性链表中，假设哈希函数所产生的地址在\[0,m-1\]上，则设立一个指针型向量。Chain ChainHash\[m\];其每个分量的初始状态都是空指针。凡哈希地址为i的记录都插入到头指针为ChainHash\[i\]的链表中。在链表的插入位置可以在表头或表尾，也可以在中间，以保持同义词在同一线性表中按关键字有序。

（4） 建立一个公共溢出区

这是处理冲突的一种方法，假设哈希函数的值域\[0,m-1\]，则设向量HashTable\[0..m-1\]为基本表，每个分量存放一个记录，另设立向量OverTable\[0..v\]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。

程序设计如下：

\#include <stdio.h>

\#include <alloc.h>

\#pragma hdrstop

\#include <tchar.h>

//---------------------------------------------------------------------------

\#pragma argsused

\#define MAX 5

//定义结点元素

typedef struct

intnum;

charname\[20\];

\}ElemType;

//定义哈希表

typedef struct

ElemType\*elem;

intcount;

intsizeindex;

\}HashTable;

//定义哈希函数

int Hash(int num)

return(num%5);

//创建哈希表

void InitHash(HashTable \*H)

inti;

H->elem=(ElemType\*)malloc(MAX\*sizeof(ElemType));

H->count=0;

H->sizeindex=MAX;

for(i=0;i<MAX;i++)

H->elem\[i\].num=0;

//查找函数

int SearchHash(HashTable H,int key, int \*p)

int c=0;

\*p=Hash(key);

while(H.elem\[\*p\].num!=key&&H.elem\[\*p\].num!=0)

c=c+1;

if(c%2==1)

\*p=\*p+(c+1)\*(c+4)/4;

else

\*p=\*p-(c\*c)/4;

if(H.elem\[\*p\].num==key)

return1;

else

return 0;

//插入函数

void InsertHash(HashTable \*H,ElemType e)

intp;

SearchHash(\*H,e.num,&p);

H->elem\[p\]=e;

\++H->count;

int \_tmain(int argc, \_TCHAR\* argv\[\])

HashTableH;

intp,key,i;

ElemTypee;

InitHash(&H);

for(i=0;i<MAX;i++)

loop: printf("输入第 %d 个学生学号\\n",i+1);

scanf("%d",&e.num);

if(!SearchHash(H,e.num,&p))

printf("输入第 %d 个学生姓名\\n",i+1);

scanf("%s",e.name);

InsertHash(&H,e);

else

printf("该学号已经存在\\n");

gotoloop;

printf("请输入您要查找的学生学号；\\n");

scanf("%d",&key);

if(SearchHash(H,key,&p))

printf("查找成功，学生的姓名是%s\\n",H.elem\[p\].name);

printf("该学生所在的位置是 %d\\n",p);

else

printf("查找失败！您要找的学生不存在。");

return0;

哈希查找是通过计算数据元素的存储位置进行查找的一种方法。一般的线性表，树中，记录在结构中的相对位置时随机的，即和记录的关键字之间不存在确定关系，在结构中查找记录时需进行一系列和关键字的比较。这一类方法建立在“比较”的基础上，查找的效率与比较的次数密切相关。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和其关键词之间建立一个确定的对应关系f，使得每个关键字和结构中一个唯一的存储位置相对应。

因此，查找时只需根据这个对应关系f找到给定值K的对应项f(K).若结构体中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此不需要进行比较便可以直接取得所查记录，在此称对应关系f为哈希函数，这种思想建立的表称为哈希表。

哈希表不可避免的冲突现象：对不同的关键字可能得到同一哈希地址，即K1!=K2，而f(K1)=f(K2)。具有相同函数的关键字对该哈希函数来说称为同义词。

高效的数据存储和查找均可以用哈希表。