当前位置:   article > 正文

学习记录day19——数据结构 查找算法

学习记录day19——数据结构 查找算法

概念

        在给定数据元素的某个值,在查找表中确定一个其关键字等于给定值的数据元素的操作,叫做查找

查找的分类

        顺序查找:将待查找数据,进行全部遍历一遍,直到找到要查找的元素

        折半查找:每次都去除一半的查找范围的查找方式,叫做折半查找

        哈希查找:利用哈希表和哈希函数完成的查找方式(效率最高)

折半查找

        使用前提:

                1、在顺序表中进行查找

                2、数据必须是有序的

        原理:

                1、在顺序存储的有序列表中,通过逐次减半查找范围,最终确定要查找的值的算法

         算法:

  1. int half_search(int *arr,int n,int key)
  2. {
  3. int low = 0;
  4. int high = n-1;
  5. int mid = -1;
  6. while(low<=high)
  7. {
  8. mid = (low+high)/2;
  9. if (arr[mid] == key)
  10. {
  11. return mid;
  12. }else if (arr[mid]>key)
  13. {
  14. high = mid-1;
  15. }else
  16. {
  17. low = mid +1;
  18. }
  19. }
  20. return -1;
  21. }

哈希查找

1、相关概念

        1)哈希表是借助哈希函数将序列存储于连续存储空间的查找表

       

         2)哈希函数是根据关键字确定存储位置的函数

        3)哈希冲突是不同关键字由哈希函数得到相同存储位置的现象

 2、构造哈希函数的方法:


                直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法

        5)除留余数法:取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址的                                     方法

              序列长度n:待查找数据的个数

              哈希表表长m:一般为大于n的值,n/(3/4)

              要被除的值p:小于或等于表长的最大素数

3、常用的处理冲突的方法

4、代码实现

00.h

  1. #ifndef DAY19_HASH_H
  2. #define DAY19_HASH_H
  3. #include <myhead.h>
  4. #define N 13 //哈希表长度
  5. //定义数据类型
  6. typedef int datatype;
  7. typedef struct Node
  8. {
  9. datatype data;
  10. struct Node *next;
  11. }Node,*NodePtr;
  12. void init_hash(NodePtr *hash);
  13. void insert_hash(NodePtr *hash,datatype e);
  14. void show_hash(NodePtr *hash);
  15. int search_hash(NodePtr *hash,datatype key);
  16. #endif // !DAY19_HASH_H

00.c

  1. #include "00.h"
  2. void init_hash(NodePtr *hash)
  3. {
  4. for (int i = 0; i < N; i++)
  5. {
  6. hash[i] = NULL;
  7. }
  8. printf("初始化成功\n");
  9. }
  10. void insert_hash(NodePtr *hash,datatype e)
  11. {
  12. int pos = e%N;
  13. NodePtr p = (NodePtr)malloc(sizeof(Node));
  14. if (NULL ==p)
  15. {
  16. return ;
  17. }
  18. p->data = e;
  19. p->next = NULL;
  20. p->next = hash[pos];
  21. hash[pos] = p;
  22. printf("插入成功\n");
  23. }
  24. void show_hash(NodePtr *hash)
  25. {
  26. for (int i = 0; i < N; i++)
  27. {
  28. printf("%d:",i);
  29. NodePtr q = hash[i];
  30. while(q != NULL)
  31. {
  32. printf("%d-->",q->data);
  33. q = q->next;
  34. }
  35. printf("NULL\n");
  36. }
  37. }
  38. int search_hash(NodePtr *hash,datatype key)
  39. {
  40. int pos = key%N;
  41. NodePtr q = hash[pos];
  42. while (q && q->data != key)
  43. {
  44. q = q->next;
  45. }
  46. if (NULL == q)
  47. {
  48. return -1;
  49. }
  50. else
  51. {
  52. return 0;
  53. }
  54. }

main.c

  1. #include "00.h"
  2. int main(int argc, char const *argv[])
  3. {
  4. int arr[10] = {25,51,8,22,26,67,11,16,54,41};
  5. //定义一个哈希表
  6. NodePtr hash[N]; //指针数组
  7. //初始化哈希表
  8. init_hash(hash);
  9. for (int i = 0; i < 10; i++)
  10. {
  11. insert_hash(hash,arr[i]);
  12. }
  13. show_hash(hash);
  14. int res = search_hash(hash,22);
  15. if (res == -1)
  16. {
  17. printf("不存在r\n");
  18. }
  19. else
  20. {
  21. printf("存在\n");
  22. }
  23. int res1 = search_hash(hash,500);
  24. if (res1 == -1)
  25. {
  26. printf("不存在\n");
  27. }
  28. else
  29. {
  30. printf("存在\n");
  31. }
  32. return 0;
  33. }

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号