基本查找和哈希查找（C语言）

文章目录

• 查找
• • 概述
• 经典查找代码
• 折半查找代码
• 哈希查找
• • 理论
  • 开放定址法代码
  • 链地址法代码

查找

概述

查找：一堆数据，找想要的结果，找到返回索引号(指针索引)，没找到返回-1 (NULL)

如何设计查找算法：动态查找 静态查找

关键字

在查找表查找某个特定元素时，前提是需要知道这个元素的一些属性。例如，每个人上学的时候都会有自己唯一的学号，因为你的姓名、年龄都有可能和其他人是重复的，唯独学号不会重复。而学生具有的这些属性（学号、姓名、年龄等）都可以称为关键字。 关键字又细分为主关键字和次关键字。若期个关键字可以唯一地识别一个数据元素时，称这个关键字为主关键字，例如学生的学号就真有唯一性；反之，像学生姓名、年龄这类的关键字，由于不具有唯一性，称为次关键字。

经典查找代码

在数组的头部（索引0位置）设置一个监视哨，这样从后往前查找时，即使找不到目标元素，也会在监视哨处停止，避免每次循环都要检查是否越界

#include<stdio.h>
#include<stdlib.h>

typedef int Elemtype;
typedef struct {
Elemtype* data;
int length;
}STable;

STable* initSTable(int n) {
STable* a = malloc(sizeof(STable));
if (a == NULL)return NULL;

a->data = malloc((n+1) * sizeof(int));// 多分配一个位置作为监视哨
if (a->data == NULL)return NULL;

a->length = n;

return a;

}

//找到返回索引 找不到返回0
//在0位置放哨兵
int SearchElem(STable* a, int k) {
int findpos = a->length;
a->data[0] = k;//放哨兵
while (a->data[findpos]!=k) {
findpos—;
}

return findpos;
}

int main() {

int n;
scanf("%d", &n);

STable* arr = initSTable(n);

for (int i = 1; i <= n; i++)
{
scanf("%d", &arr->data[i]);

}
int k;
printf("输入查找的数\\n");
scanf("%d", &k);

if (SearchElem(arr, k)==0) {
printf("未找到\\n");
}
else {
printf("%d找到了\\n", k);
}

return 0;
}

折半查找代码

二分查找又叫做折半查找，其查找过程为：先确定待查记录所在的范围（区间），然后逐步缩小范围知道找到或者找不到该记录为止。注意二分查找是在有序表上进行的，且二分查找也是分治思想的很好例证。

#include<stdio.h>
int n;
int a[105];
int k;

//[left,right] 有序数组
bindarySerach() {
int left = 0;
int right = n;
int mid ;

while (left <= right) {
mid = (left + right) / 2;
if (k==a[mid]) {
return k;
}
else if (k < a[mid]) {
right = mid – 1;//往左边找
}
else if (k > a[mid]) {
left = mid + 1;//右边找
}
}

return –1;
}
int main() {

scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);

}
printf("输入查找的数\\n");
scanf("%d", &k);

int result=bindarySerach();
if (result == –1) {
printf("没找到\\n");
}
else {
printf("%d找到了\\n", k);
}

return 0;
}

哈希查找

理论

哈希查找是一种通过哈希函数将关键字映射到存储位置，从而实现快速查找的算法。通过一个函数（哈希函数）将数据的值（关键字）映射到存储地址。

传统查找（顺序查找）：
问图书管理员："我想找《算法导论》"
管理员从第一本书开始，一本本翻看，直到找到为止
→ 慢！O(n)

哈希查找：
问图书管理员："我想找《算法导论》"
管理员说："这本书编号是HS-789"
直接走到H书架第7层第89格，取书
→ 快！O(1)

核心思想

• 建立关键字与存储地址之间的直接映射关系
• 理想情况下时间复杂度可达 O(1)

⼀个好的哈希函数应该满⾜四个条件：

什么是Hash碰撞

由于哈希函数的原理是将输入空间的一个较大的值映射成hash空间内一个较小的值，那么就会 出现两个不同的输入值被映射到了同一个较小的输出值。当一个新插入的值被哈希函数映射到了哈希表中一个已经被占用的槽，就认为产生了Hash 碰撞（冲突）。

冲突只能缓解，不可避免。

Hash 碰撞的解决方案

1.开放地址法

直接定址法 H (key)= index 或者 (key)=a *key + b

（1）线性探测法 设 Hash（key）表示关键字 key 的哈希值，表示哈希表的槽位数（哈希表的大小）。线性探测法则可以表示为：

• 如果Hash(x）M 已经有数据，则尝试（Hash(x）+1）M ;
• 如果（Hash(x）+1）M 也有数据了，则尝试（Hash(x）+2）M;
• 如果（Hash(x）＋2）M 也有数据了，则尝试（Hash(x）+3）M;

​ 我们同样以哈希函数 H(key）=key MOD7（除数取余法）对［50，700，76，85，92，73，101]进行映射，来理解线性探测法处理Hash 碰撞。 ​ 依次计算507= 1、700 7 =0及76 7 = 6，均没有发生冲突（碰撞），则直接放入相应的位置：

（2）平方探测法（二次探测法） 所谓 Quadratic Probing，就是每次向下探测的宽度变成了i的平方，其中的i表示迭代次数。

设 Hash（key）表示关键字 key 的哈希值，M表示哈希表的槽位数（哈希表的大小）。

平方探测法则可以表示为：

• 如果Hash(x）M 已经有数据，则尝试（Hash(x）+1＊1）M；
• 如果（Hash(x）＋1＊1）%M 也有数据了，则尝试（Hash(x）+2＊2）M;
• 如果（Hash(x）＋2＊2）M 也有数据了，则尝试（Hash(x）＋3＊3）M;

2.链地址法

• 数组hash[size]只存储指针
• 所有数据都存储在动态分配的链表节点中
• 数组本身不存储数据，只存储链表头指针

链地址法的思想就是将所有发生碰撞的元素用⼀个单链表串起来。

开放定址法代码

#include<stdio.h>
#include<stdlib.h>
#define SIZE 13
#define NUL –1

typedef struct {
int* data;//哈希数组
int len;//哈希表长度
}hashTable;

hashTable* createHTable( ) {
hashTable* t = malloc(sizeof(hashTable));
if (t == NULL)return NULL;

t->data = malloc(sizeof(int) * SIZE);
if (t->data == NULL)return NULL;
for (int i = 0; i < SIZE; i++)
{
t->data[i] = NUL;
}
t->len = SIZE;
return t;
}

static int Hash(hashTable* t, int k) {
return k % t->len;
}

//找到元素插入哈希表的位置
//考虑哈希冲突
static int findpos(hashTable* t, int k) {
int index = Hash(t, k);

if (t->data[index] == NUL) {
return index;
}
int d = 1;//找下一个位置
int newindex = index + d;
while (t->data[newindex]!=NUL&&d<t->len) {
d++;
newindex = (index + d)%t->len;
}
if (d == t->len) {//一般保证插入元素个数小于SIZE
printf("表满了\\n");
return –1;
}

return newindex;
}

void insert(hashTable* t,int k) {
int index = findpos(t,k);
t->data[index] = k;
}

//找到打印元素 找不到打印信息
void searchHash(hashTable* t, int findElem) {
int j = Hash(t, findElem);//可能的位置
if (t->data[j] == findElem) {
printf("在%d索引找到了%d\\n", j, findElem);
return;
}
int d = 1;
int newj = d + j;//找其他位置
while (t->data[newj] != findElem&&newj!=j) {
d++;
newj = (d + j)%t->len;//循环查找
}

if (newj == j) {
printf("没找到\\n");

}
else if(t->data[newj] == findElem) {
printf("在%d索引找到了%d\\n", newj, findElem);
}
}

int mainhaop() {
int n;//插入哈希表数据个数
scanf("%d", &n);
int k;

hashTable* table = createHTable( );
for (int i = 0; i < n; i++)
{
scanf("%d", &k);
insert(table,k);
}

printf("输入要查找的元素：\\n");
int k1;
scanf("%d", &k1);
searchHash(table, k1);

printf("验证哈希表:\\n");
for (int i = 0; i < n; i++)
{
if (table->data[i] == NUL)
{
printf("%d索引没有元素\\n",i);
continue;
}
searchHash(table, table->data[i]);
}
return 0;
}
/*
12
19 74 23 1 68 20 84 27 5 11 10 79
13
19 74 23 1 68 20 84 27 5 11 10 79 13
*/

链地址法代码

• 数组hash[size]只存储指针
• 所有数据都存储在动态分配的链表节点中
• 数组本身不存储数据，只存储链表头指针

头指针数组

#include<stdio.h>
#include<stdlib.h>
#define size 13
#define nul –1
typedef struct node
{
int data;
struct node* next;
}Hnode,*Hlink;

//哈希函数
int Hash(int k)
{
return k%13;
}

void Insert(Hlink hash[],int k)
{
int i=Hash(k);
Hnode* p=(Hnode*)malloc(sizeof(Hnode));
//if()
p->data=k;
//头插到以hash[i]为头指针的链表中
p->next=hash[i];
hash[i]=p;

}
void find_key(Hlink hash[],int k)
{
int i=Hash(k);
Hnode* p=hash[i];
while(p!=NULL)
{
if(p->data==k)
{
printf("%d\\n",i);
break;
}
p=p->next;
}
if(p==NULL)
{
printf("不存在\\n");
}

}
int main()
{
int n,k;//n<=m
Hlink hash[size];//头指针数组 但是指向第一个元素
for(int i=0;i<size;i++)
{
hash[i]=NULL;
}
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&k);
Insert(hash,k);
}

//查找数据k
scanf("%d",&k);
find_key(hash,k);

return 0;
}
/*
12
19 74 23 1 68 20 84 27 5 11 10 79
13
19 74 23 1 68 20 84 27 5 11 10 79 13
*/

头节点数组

#include<stdio.h>
#include<stdlib.h>
#define SIZE 13
#define NUL –1

typedef struct nodeL{
int data;//哈希数组
struct nodeL* next;//下一个节点
}node,*linklist;

// 头节点数组 数据域不存东西
linklist createHTableL() {
linklist t = malloc(sizeof(node) * SIZE);
if (t == NULL)return NULL;

for (int i = 0; i < SIZE; i++)
{
t[i].data= NUL;
t[i].next = NULL;
}

return t;
}

static int Hash(int k) {
return k % SIZE;
}

void insertL(linklist t,int k) {
int insertIndex = Hash(k);
//无论有没有冲突 头插法
node* pnew = malloc(sizeof(node));
if (pnew == NULL)return;

pnew->data = k;
pnew->next = t[insertIndex].next;
t[insertIndex].next = pnew;

}

void searchHashL(linklist t, int k) {
int findIndex = Hash(k);

//当前节点没有数据
if (t[findIndex].next == NULL) {
printf("没找到\\n");
return;
}

//有数据
node* p = t[findIndex].next;//首元节点
while (p&&p->data!=k) {
p = p->next;
}

//循环后要么没找到要么找到了
if (p == NULL) {
printf("没找到\\n");
}
else if(p->data==k){
printf("%d找到了\\n", k);
}

}

int main() {
int n;//插入哈希表数据个数
scanf("%d", &n);
int k;

linklist table = createHTableL();
for (int i = 0; i < n; i++)
{
scanf("%d", &k);
insertL(table, k);
}

printf("输入要查找的元素：\\n");
int k1;
scanf("%d", &k1);
searchHashL(table, k1);

printf("验证哈希表:\\n");
for (int i = 0; i < n; i++)
{
if (table[i].next != NULL) {
node* p = table[i].next;
printf("索引%d是\\n",i);
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\\n\\n");
}
else {
printf("索引%d没有元素\\n\\n",i);
}
}

return 0;
}
/*
12
19 74 23 1 68 20 84 27 5 11 10 79
13
19 74 23 1 68 20 84 27 5 11 10 79 13
*/