概念
在给定数据元素的某个值，在查找表中确定一个其关键字等于给定值的数据元素的操作，叫做查找
查找的分类
顺序查找:将待查找数据，进行全部遍历一遍，直到找到要查找的元素
折半查找:每次都去除一半的查找范围的查找方式，叫做折半查找
哈希查找:利用哈希表和哈希函数完成的查找方式(效率最高)
折半查找
使用前提：
1、在顺序表中进行查找
2、数据必须是有序的
原理：
1、在顺序存储的有序列表中，通过逐次减半查找范围，最终确定要查找的值的算法
算法：
int half_search(int *arr,int n,int key)
{int low = 0;int high = n-1;int mid = -1;while(low<=high){mid = (low+high)/2;if (arr[mid] == key){return mid;}else if (arr[mid]>key){high = mid-1;}else{low = mid +1;}}return -1;
}哈希查找
1、相关概念
1）哈希表是借助哈希函数将序列存储于连续存储空间的查找表
2）哈希函数是根据关键字确定存储位置的函数
3）哈希冲突是不同关键字由哈希函数得到相同存储位置的现象
2、构造哈希函数的方法:
直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法
5）除留余数法：取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址的 方法
序列长度n:待查找数据的个数
哈希表表长m:一般为大于n的值，n/(3/4)
要被除的值p:小于或等于表长的最大素数
3、常用的处理冲突的方法
4、代码实现
00.h
#ifndef DAY19_HASH_H
#define DAY19_HASH_H#include <myhead.h>
#define N 13 //哈希表长度 //定义数据类型
typedef int datatype;
typedef struct Node
{datatype data;struct Node *next;
}Node,*NodePtr;void init_hash(NodePtr *hash);void insert_hash(NodePtr *hash,datatype e);void show_hash(NodePtr *hash);int search_hash(NodePtr *hash,datatype key);
#endif // !DAY19_HASH_H00.c
#include "00.h"void init_hash(NodePtr *hash)
{for (int i = 0; i < N; i++){hash[i] = NULL;}printf("初始化成功\n");
}void insert_hash(NodePtr *hash,datatype e)
{int pos = e%N;NodePtr p = (NodePtr)malloc(sizeof(Node));if (NULL ==p){return ;}p->data = e;p->next = NULL;p->next = hash[pos];hash[pos] = p;printf("插入成功\n");
}void show_hash(NodePtr *hash)
{for (int i = 0; i < N; i++){printf("%d:",i);NodePtr q = hash[i];while(q != NULL){printf("%d-->",q->data);q = q->next;}printf("NULL\n");}}int search_hash(NodePtr *hash,datatype key)
{int pos = key%N;NodePtr q = hash[pos];while (q && q->data != key){q = q->next;}if (NULL == q){return -1;}else{return 0;}}
main.c
#include "00.h"
int main(int argc, char const *argv[])
{int arr[10] = {25,51,8,22,26,67,11,16,54,41};//定义一个哈希表NodePtr hash[N]; //指针数组//初始化哈希表init_hash(hash);for (int i = 0; i < 10; i++){insert_hash(hash,arr[i]);}show_hash(hash);int res = search_hash(hash,22);if (res == -1){printf("不存在r\n");}else{printf("存在\n");}int res1 = search_hash(hash,500);if (res1 == -1){printf("不存在\n");}else{printf("存在\n");}return 0;
}
