赞
踩
在给定数据元素的某个值,在查找表中确定一个其关键字等于给定值的数据元素的操作,叫做查找
顺序查找:将待查找数据,进行全部遍历一遍,直到找到要查找的元素
折半查找:每次都去除一半的查找范围的查找方式,叫做折半查找
哈希查找:利用哈希表和哈希函数完成的查找方式(效率最高)
使用前提:
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)哈希表是借助哈希函数将序列存储于连续存储空间的查找表
2)哈希函数是根据关键字确定存储位置的函数
3)哈希冲突是不同关键字由哈希函数得到相同存储位置的现象
直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法
5)除留余数法:取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址的 方法
序列长度n:待查找数据的个数
哈希表表长m:一般为大于n的值,n/(3/4)
要被除的值p:小于或等于表长的最大素数
- #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_H

00.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;
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。