散列表

    散列表又叫哈希表，它是为了减少搜索空间，但又考虑到时间上设立的。
   
http://codeplayer.org/2013/11/210 参考网页
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. #define m           17
  5. //#define HASH(k)    k % m       //除法散列法
  6.  
  7. #define A           0.85
  8. //#define HASH(k)    (int)(m * (k * A - (int)(k * A)))         //乘法散列法
  9.  
  10. #define c1          7
  11. #define c2          5
  12. //#define h(k, i)     (HASH(k) + i) % m       //线性探查
  13. //#define h(k, i)     (HASH(i) + c1 * i + c2 * i * i) % m         //二次探查
  14.  
  15. #define h1(k)       k % m
  16. #define h2(k)       1 + (k % (m - 1))
  17. #define h(k, i)     (h1(k) + i * h2(k)) % m       //双重散列
  18.  
  19. #define DEL         -65535
  20.  
  21. int
  22. hash_insert(int *T, int k)
  23. {
  24.     /*
  25.      * 在散列表中插入一个元素，不断的探查
  26.      * 以找到一个空槽可以插入，或者探查了
  27.      * 整个散列表，输出错误信息并退出
  28.      */
  29.     int     i, j;
  30.  
  31.     for (i = 0; i != m; i++) {
  32.         j = h(k, i);
  33.         if (T[j] == NULL || T[j] == DEL) {
  34.             T[j] = k;
  35.             return(j);
  36.         }
  37.     }
  38.     fprintf(stderr, "hash table overflow
");
  39.     exit(1);
  40. }
  41.  
  42. int
  43. hash_search(int *T, int k)
  44. {
  45.     /*
  46.      * 在散列表中查找一个元素，不断进行
  47.      * 探查，直到找到该元素，或者探查到
  48.      * 了一个空槽，或者找遍了整个散列表
  49.      */
  50.     int     i, j;
  51.  
  52.     for (i = 0; i != m; i++) {
  53.         j = h(k, i);
  54.         if (T[j] == k) {
  55.             printf("found value: %d in key: %d
", k, j);
  56.             return(j);
  57.         } else if (T[j] == NULL) {
  58.             break;
  59.         }
  60.     }
  61.  
  62.     fprintf(stderr, "can't find value: %d
", k);
  63.     return(NULL);
  64. }
  65.  
  66. int
  67. hash_delete(int *T, int k)
  68. {
  69.     /*
  70.      * 删除一个元素的时候并不将它置为NULL，
  71.      * 因为这有可能会使得在查找的时候找不到
  72.      * 后续的元素，查找在删除的地方就中断了。
  73.      * 可以在删除的时候将其置为一个特殊的值，
  74.      * 以避免这种情况。这里用的是DEL。
  75.      */
  76.     int     i, j;
  77.  
  78.     for (i = 0; i != m; i++) {
  79.         j = h(k, i);
  80.         if (T[j] == k) {
  81.             T[j] = DEL;
  82.             return(0);
  83.         }
  84.     }
  85.  
  86.     fprintf(stderr, "can't find %d in hashtable
", k);
  87.     exit(1);
  88. }
  89.  
  90. void
  91. print_hash(int *T)
  92. {
  93.     int     i;
  94.  
  95.     printf("---------------hashtable---------------
");
  96.     for (i = 0; i < m; i++) {
  97.         if (T[i] != NULL && T[i] != DEL)
  98.             printf("key: %2d, value: %4d
", i, T[i]);
  99.         else
  100.             printf("key: %2d, value: NULL
", i);
  101.     }
  102.     printf("------------------end------------------

");
  103. }
  104.  
  105. int
  106. main(void)
  107. {
  108.     /*
  109.      * 用数组实现的简单的开放寻址法的散列表
  110.      */
  111.     int     i;
  112.     int     T[m];
  113.  
  114.     for (i = 0; i < m; i++) {
  115.         T[i] = NULL;
  116.     }
  117.     hash_insert(T, 28);
  118.     hash_insert(T, 438);
  119.     hash_insert(T, 923);
  120.     hash_insert(T, 239);
  121.     hash_insert(T, 29);
  122.     hash_insert(T, 31);
  123.     hash_insert(T, 32);
  124.     hash_insert(T, 39);
  125.     hash_insert(T, 2);
  126.     hash_insert(T, 24);
  127.     hash_insert(T, 432);
  128.     print_hash(T);
  129.     hash_delete(T, 239);
  130.     hash_delete(T, 31);
  131.     hash_delete(T, 28);
  132.  
  133.     printf("
after delete 239, 31, 28...

");
  134.  
  135.     print_hash(T);
  136.  
  137.     hash_search(T, 438);
  138.     hash_search(T, 239);
  139.  
  140.     exit(0);
  141. }
  1. #include<iostream>
  2. #include<string>
  4. #define m 17
  5. #define A 0.85
  6. #define c1 7
  7. #define c2 5
  8. #define h1(k) k%m
  9. #define h2(k) 1+(k%(m-1))
  10. #define h(k,i) (h1(k) + i * h2(k)) % m //#define h(k,i) (h1(k)+i)%m //这是一个一次线性查找。
  11. #define DEL -65535
  12. int hash_insert(int *T,int k){ //插入数据，得找位置进行插入。
  13. 	int i,j; 
  14. 	for(int i=0;i<m; i++){
  15. 		j=h(k,i); 
  16. 		if(T[j]==NULL||T[j]==DEL){ //因为如果中间我们删了一些数据，那么我们标为DEL了，于是我们就可以再在这里插入。
  17. 			T[j]=k; 
  18. 			return (j); 
  19. 		}
  20. 	}
  21. 	if(i==m){//如果数组越界，则结束。
  22. 		std::cout<<"error,out of range"<<std::endl;     
  23.         return DEL;  
  24. 	}
  25. }
  26. bool hash_search(int *T,int k){ //这里我们进行查找
  27. 	int i=0,j; 
  28. 	for(int i=0;i<m; i++){
  29.  		j=h(k,i); 
  30. 		if(T[j]==k){ //如果找到就可以了，找不到就返回
  31. 			std::cout<<j<<std::endl;
  32. 			return true; 
  33. 		}
  34. 		else if(T[j]=NULL){// 如果找到一个NULL，因为我们插入是“顺序”插入的，因此找到一个NULL，则后面也是没有了的。
  35. 			break; 
  36. 		}
  37. 	}
  38. 	if(i==m||T[j]==NULL){
  39. 		std::cout<<"not found"<<std::endl; 
  40. 		return false;
  41. 	}
  42. }
  43. bool delete_Hash(int *T,int k){
  44. 	int i,j; 
  45. 	for(int i=0;i<m; i++){
  46. 		j=h(k,i); 
  47. 		if(T[j]==k){
  48. 			T[j]=DEL; //用特殊符号进行标志，说明这里删除了一个数。
  49. 			return true;
  50. 		}
  51. 	}
  52. 	if(i==m){    //如果越界了，则说明数组完了。
  53. 		std::cout<<"not found"<<std::endl; 
  54. 		return false; 
  55. 	}
  56. }
  57. void hash_print(int *T){
  58. 	for(int i=0;i<m; i++){
  59. 		std::cout<<T[i]<<","; 
  60. 	}
  61. 	std::cout<<std::endl; 
  62. }
  63. int main(){
  64.     int     i;
  65.     int     T[m];
  66.     for (i = 0; i < m; i++) {
  67.         T[i] = NULL;
  68.     }
  69.     hash_insert(T, 28);
  70.     hash_insert(T, 438);
  71.     hash_insert(T, 923);
  72.     hash_insert(T, 239);
  73.     hash_insert(T, 29);
  74.     hash_insert(T, 31);
  75.     hash_insert(T, 32);
  76.     hash_insert(T, 39);
  77.     hash_insert(T, 2);
  78.     hash_insert(T, 24);
  79.     hash_insert(T, 432);
  80.     std::cout<<hash_search(T,2)<<std::endl; 
  81.     hash_print(T); 
  82.     hash_search(T,11); 
  83. }





【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/yml435/p/4655565.html