1.查找算法概述
查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。
（1）查找定义
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
（2）查找算法分类
1）静态查找和动态查找
注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
2）无序查找和有序查找
无序查找：被查找数列有序无序均可；
有序查找：被查找数列必须为有序数列。
（3）查找算法分析
平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。
对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。
Pi：查找表中第i个数据元素的概率。
Ci：找到第i个数据元素时已经比较过的次数。
2.哈希查找
（1）什么是哈希表（Hash）？
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。
（2）什么是哈希函数？
哈希函数的规则是：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。
算法思想：哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
（3）哈希查找算法流程
1）用给定的哈希函数构造哈希表；
2）根据选择的冲突处理方法解决地址冲突；
常见的解决冲突的方法：拉链法和线性探测法。
3）在哈希表的基础上执行哈希查找。
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。
（4）复杂度分析
单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。
使用Hash，我们付出了什么？
我们在实际编程中存储一个大规模的数据，最先想到的存储结构可能就是map，也就是我们常说的KV pair，经常使用Python的博友可能更有这种体会。使用map的好处就是，我们在后续处理数据处理时，可以根据数据的key快速的查找到对应的value值。map的本质就是Hash表，那我们在获取了超高查找效率的基础上，我们付出了什么？
Hash是一种典型以空间换时间的算法，比如原来一个长度为100的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是byte类型数据，那么该数组占用100byte空间。现在我们采用Hash算法，我们前面说的Hash必须有一个规则，约束键与存储位置的关系，那么就需要一个固定长度的hash表，此时，仍然是100byte的数组，假设我们需要的100byte用来记录键与位置的关系，那么总的空间为200byte,而且用于记录规则的表大小会根据规则，大小可能是不定的。
（5）Hash算法和其他查找算法的性能对比：
Hash算法和其他查找算法的性能对比
（6）常用的Hash哈希算法函数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ /** * 常用的Hash哈希算法函数总结 */ #define M 249997 #define M1 1000001 #define M2 0xF0000000 // RS Hash Function unsigned int RSHash(char*str) { unsigned int b=378551 ; unsigned int a=63689 ; unsigned int hash=0 ; while(*str) { hash=hash*a+(*str++); a*=b ; } return(hash % M); } // JS Hash Function unsigned int JSHash(char*str) { unsigned int hash=1315423911 ; while(*str) { hash^=((hash<<5)+(*str++)+(hash>>2)); } return(hash % M); } // P. J. Weinberger Hash Function unsigned int PJWHash(char*str) { unsigned int BitsInUnignedInt=(unsigned int)(sizeof(unsigned int)*8); unsigned int ThreeQuarters=(unsigned int)((BitsInUnignedInt*3)/4); unsigned int OneEighth=(unsigned int)(BitsInUnignedInt/8); unsigned int HighBits=(unsigned int)(0xFFFFFFFF)<<(BitsInUnignedInt-OneEighth); unsigned int hash=0 ; unsigned int test=0 ; while(*str) { hash=(hash<<OneEighth)+(*str++); if((test=hash&HighBits)!=0) { hash=((hash^(test>>ThreeQuarters))&(~HighBits)); } } return(hash % M); } // ELF Hash Function unsigned int ELFHash(char*str) { unsigned int hash=0 ; unsigned int x=0 ; while(*str) { hash=(hash<<4)+(*str++); if((x=hash&0xF0000000L)!=0) { hash^=(x>>24); hash&=~x ; } } return(hash % M); } // BKDR Hash Function unsigned int BKDRHash(char*str) { unsigned int seed=131 ;// 31 131 1313 13131 131313 etc.. unsigned int hash=0 ; while(*str) { hash=hash*seed+(*str++); } return(hash % M); } // SDBM Hash Function unsigned int SDBMHash(char*str) { unsigned int hash=0 ; while(*str) { hash=(*str++)+(hash<<6)+(hash<<16)-hash ; } return(hash % M); } // DJB Hash Function unsigned int DJBHash(char*str) { unsigned int hash=5381 ; while(*str) { hash+=(hash<<5)+(*str++); } return(hash % M); } // AP Hash Function unsigned int APHash(char*str) { unsigned int hash=0 ; int i ; for(i=0;*str;i++) { if((i&1)==0) { hash^=((hash<<7)^(*str++)^(hash>>3)); } else { hash^=(~((hash<<11)^(*str++)^(hash>>5))); } } return(hash % M); } /** * Hash算法大全<br> * 推荐使用FNV1算法 * @algorithm None * @author Goodzzp 2006-11-20 * @lastEdit Goodzzp 2006-11-20 * @editDetail Create */ public class HashAlgorithms { /** * 加法hash * @param key 字符串 * @param prime 一个质数 * @return hash结果 */ public static int additiveHash(String key, int prime) { int hash, i; for (hash = key.length(), i = 0; i < key.length(); i++) hash += key.charAt(i); return (hash % prime); } /** * 旋转hash * @param key 输入字符串 * @param prime 质数 * @return hash值 */ public static int rotatingHash(String key, int prime) { int hash, i; for (hash=key.length(), i=0; i<key.length(); ++i) hash = (hash<<4)^(hash>>28)^key.charAt(i); return (hash % prime); // return (hash ^ (hash>>10) ^ (hash>>20)); } // 替代： // 使用：hash = (hash ^ (hash>>10) ^ (hash>>20)) & mask; // 替代：hash %= prime; /** * MASK值，随便找一个值，最好是质数 */ static int M_MASK = 0x8765fed1; /** * 一次一个hash * @param key 输入字符串 * @return 输出hash值 */ public static int oneByOneHash(String key) { int hash, i; for (hash=0, i=0; i<key.length(); ++i) { hash += key.charAt(i); hash += (hash << 10); hash ^= (hash >> 6); } hash += (hash << 3); hash ^= (hash >> 11); hash += (hash << 15); // return (hash & M_MASK); return hash; } /** * Bernstein's hash * @param key 输入字节数组 * @param level 初始hash常量 * @return 结果hash */ public static int bernstein(String key) { int hash = 0; int i; for (i=0; i<key.length(); ++i) hash = 33*hash + key.charAt(i); return hash; } // //// Pearson's Hash // char pearson(char[]key, ub4 len, char tab[256]) // { // char hash; // ub4 i; // for (hash=len, i=0; i<len; ++i) // hash=tab[hash^key[i]]; // return (hash); // } //// CRC Hashing，计算crc,具体代码见其他 // ub4 crc(char *key, ub4 len, ub4 mask, ub4 tab[256]) // { // ub4 hash, i; // for (hash=len, i=0; i<len; ++i) // hash = (hash >> 8) ^ tab[(hash & 0xff) ^ key[i]]; // return (hash & mask); // } /** * Universal Hashing */ public static int universal(char[]key, int mask, int[] tab) { int hash = key.length, i, len = key.length; for (i=0; i<(len<<3); i+=8) { char k = key[i>>3]; if ((k&0x01) == 0) hash ^= tab[i+0]; if ((k&0x02) == 0) hash ^= tab[i+1]; if ((k&0x04) == 0) hash ^= tab[i+2]; if ((k&0x08) == 0) hash ^= tab[i+3]; if ((k&0x10) == 0) hash ^= tab[i+4]; if ((k&0x20) == 0) hash ^= tab[i+5]; if ((k&0x40) == 0) hash ^= tab[i+6]; if ((k&0x80) == 0) hash ^= tab[i+7]; } return (hash & mask); } /** * Zobrist Hashing */ public static int zobrist( char[] key,int mask, int[][] tab) { int hash, i; for (hash=key.length, i=0; i<key.length; ++i) hash ^= tab[i][key[i]]; return (hash & mask); } // LOOKUP3 // 见Bob Jenkins(3).c文件 // 32位FNV算法 static int M_SHIFT = 0; /** * 32位的FNV算法 * @param data 数组 * @return int值 */ public static int FNVHash(byte[] data) { int hash = (int)2166136261L; for(byte b : data) hash = (hash * 16777619) ^ b; if (M_SHIFT == 0) return hash; return (hash ^ (hash >> M_SHIFT)) & M_MASK; } /** * 改进的32位FNV算法1 * @param data 数组 * @return int值 */ public static int FNVHash1(byte[] data) { final int p = 16777619; int hash = (int)2166136261L; for(byte b:data) hash = (hash ^ b) * p; hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; return hash; } /** * 改进的32位FNV算法1 * @param data 字符串 * @return int值 */ public static int FNVHash1(String data) { final int p = 16777619; int hash = (int)2166136261L; for(int i=0;i<data.length();i++) hash = (hash ^ data.charAt(i)) * p; hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; return hash; } /** * Thomas Wang的算法，整数hash */ public static int intHash(int key) { key += ~(key << 15); key ^= (key >>> 10); key += (key << 3); key ^= (key >>> 6); key += ~(key << 11); key ^= (key >>> 16); return key; } /** * RS算法hash * @param str 字符串 */ public static int RSHash(String str) { int b = 378551; int a = 63689; int hash = 0; for(int i = 0; i < str.length(); i++) { hash = hash * a + str.charAt(i); a = a * b; } return (hash & 0x7FFFFFFF); } /* End Of RS Hash Function */ /** * JS算法 */ public static int JSHash(String str) { int hash = 1315423911; for(int i = 0; i < str.length(); i++) { hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2)); } return (hash & 0x7FFFFFFF); } /* End Of JS Hash Function */ /** * PJW算法 */ public static int PJWHash(String str) { int BitsInUnsignedInt = 32; int ThreeQuarters = (BitsInUnsignedInt * 3) / 4; int OneEighth = BitsInUnsignedInt / 8; int HighBits = 0xFFFFFFFF << (BitsInUnsignedInt - OneEighth); int hash = 0; int test = 0; for(int i = 0; i < str.length();i++) { hash = (hash << OneEighth) + str.charAt(i); if((test = hash & HighBits) != 0) { hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits)); } } return (hash & 0x7FFFFFFF); } /* End Of P. J. Weinberger Hash Function */ /** * ELF算法 */ public static int ELFHash(String str) { int hash = 0; int x = 0; for(int i = 0; i < str.length(); i++) { hash = (hash << 4) + str.charAt(i); if((x = (int)(hash & 0xF0000000L)) != 0) { hash ^= (x >> 24); hash &= ~x; } } return (hash & 0x7FFFFFFF); } /* End Of ELF Hash Function */ /** * BKDR算法 */ public static int BKDRHash(String str) { int seed = 131; // 31 131 1313 13131 131313 etc.. int hash = 0; for(int i = 0; i < str.length(); i++) { hash = (hash * seed) + str.charAt(i); } return (hash & 0x7FFFFFFF); } /* End Of BKDR Hash Function */ /** * SDBM算法 */ public static int SDBMHash(String str) { int hash = 0; for(int i = 0; i < str.length(); i++) { hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash; } return (hash & 0x7FFFFFFF); } /* End Of SDBM Hash Function */ /** * DJB算法 */ public static int DJBHash(String str) { int hash = 5381; for(int i = 0; i < str.length(); i++) { hash = ((hash << 5) + hash) + str.charAt(i); } return (hash & 0x7FFFFFFF); } /* End Of DJB Hash Function */ /** * DEK算法 */ public static int DEKHash(String str) { int hash = str.length(); for(int i = 0; i < str.length(); i++) { hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i); } return (hash & 0x7FFFFFFF); } /* End Of DEK Hash Function */ /** * AP算法 */ public static int APHash(String str) { int hash = 0; for(int i = 0; i < str.length(); i++) { hash ^= ((i & 1) == 0) ? ( (hash << 7) ^ str.charAt(i) ^ (hash >> 3)) : (~((hash << 11) ^ str.charAt(i) ^ (hash >> 5))); } // return (hash & 0x7FFFFFFF); return hash; } /* End Of AP Hash Function */ /** * JAVA自己带的算法 */ public static int java(String str) { int h = 0; int off = 0; int len = str.length(); for (int i = 0; i < len; i++) { h = 31 * h + str.charAt(off++); } return h; } /** * 混合hash算法，输出64位的值 */ public static long mixHash(String str) { long hash = str.hashCode(); hash <<= 32; hash |= FNVHash1(str); return hash; } |
（7）Hash查找算法C语言源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ #include "stdio.h" #include "stdlib.h" #define HASHSIZE 7 // 定义散列表长为数组的长度 #define NULLKEY -32768 typedef int Status; typedef struct{ int *elem; // 数据元素存储地址，动态分配数组 int count; // 当前数据元素个数 }HashTable; // 散列表表长，全局变量 int m = 0; //初始化一个空的哈希表 void InitHashTable(HashTable *hashTable){ m = HASHSIZE; hashTable->elem = (int *)malloc(m * sizeof(int)); //申请内存 hashTable->count = m; for(int i = 0;i < m;i++){ hashTable->elem[i] = NULLKEY; } } //哈希函数(除留余数法) Status Hash(int key){ return key % m; } //插入 void Insert(HashTable *hashTable,int key){ /** * 根据每一个关键字，计算哈希地址hashAddress； */ int hashAddress = Hash(key); //求哈希地址 /** * 发生冲突，表示该位置已经存有数据 */ while(hashTable->elem[hashAddress] != NULLKEY){ //利用开放定址的线性探测法解决冲突 hashAddress = (hashAddress + 1) % m; } //插入值 hashTable->elem[hashAddress] = key; } //查找 Status Search(HashTable *hashTable,int key){ //求哈希地址 int hashAddress = Hash(key); //发生冲突 while(hashTable->elem[hashAddress] != key){ //利用开放定址的线性探测法解决冲突 hashAddress = (hashAddress + 1) % m; if (hashTable->elem[hashAddress] == NULLKEY || hashAddress == Hash(key)){ return -1; } } //查找成功 return hashAddress; } //打印结果 void DisplayHashTable(HashTable *hashTable){ for (int i = 0;i < hashTable->count;i++){ printf("%d ",hashTable->elem[i]); } printf("\n"); } int main(int argc, const char * argv[]) { int result; HashTable hashTable; int arr[HASHSIZE] = {13,29,27,28,26,30,38}; //初始化哈希表 InitHashTable(&hashTable); /** * 向哈希表中插入数据; 也就是把元素使用哈希函数映射到哈希表中； */ for (int i = 0;i < HASHSIZE;i++){ Insert(&hashTable,arr[i]); } //数据已存到哈希表中，打印观察哈希表，元素的位置和原数组是完全不一样的 DisplayHashTable(&hashTable); //查找数据 result = Search(&hashTable,30); if (result == -1){ printf("没有找到！"); }else{ printf("在哈希表中的位置是:%d\n",result); } return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ /* * 题目：给定一个全部由字符串组成的字典， * 字符串全部由大写字母构成。 * 其中为每个字符串编写密码， * 编写的方式是对于 n 位字符串， * 给定一个 n 位数， * 大写字母与数字的对应方式按照电话键盘的方式： * 2: A,B,C 5: J,K,L 8: T,U,V * 3: D,E,F 6: M,N,O 9: W,X,Y,Z * 4: G,H,I 7: P,Q,R,S * 题目给出一个1--12位的数，找出在字典中出现且密码是这个数的所有字符串。 * 字典中字符串的个数不超过5000。 * * 思路：1.回溯法找出所有可能的字符串 * 2..在字典中查找此字符串是否存在。（字典存储采用哈希表存储） * */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define HASHTABLE_LENGTH 5001 //哈希表长度 #define STRING_LENGTH 13 //单词最大长度 //字符串 typedef struct { char str[STRING_LENGTH]; int length; }HString; HString string={'\0',0}; //暂存可能的字符串 HString hashTable[HASHTABLE_LENGTH]; //哈希表 //hash函数,构造哈希表 void createHashTable(char *str) { int i,key,step=1; i=key=0; while(str[i]){ key+=str[i++]-'A'; } key%=HASHTABLE_LENGTH; while(1){ if(hashTable[key].length==0){ hashTable[key].length=strlen(str); strcpy(hashTable[key].str,str); break; } key=(key+step+HASHTABLE_LENGTH)%HASHTABLE_LENGTH; //处理冲突，线性探测再散列 if(step>0) step=-step; else{ step=-step; step++; } } } //从文件中读字典 void readString() { int i; char str[STRING_LENGTH]; char ch; FILE *fp; if((fp=fopen("document/dictionary.txt","r"))==NULL){ printf("can not open file!\n"); exit(0); } i=0; while((ch=getc(fp))!=EOF){ if(ch=='\n'){//读完一个字符串 str[i]='\0'; createHashTable(str); i=0; continue; } str[i++]=ch; } if(fclose(fp)){ printf("can not close file!\n"); exit(0); } } //在哈希表中查找是否存在该字符串,存在返回1，不存在返回0 int search(char *str) { int i,key,step=1; i=key=0; while(str[i]){ key+=str[i++]-'A'; } key%=HASHTABLE_LENGTH; while(1){ if(hashTable[key].length==0) return 0; if(strcmp(hashTable[key].str,str)==0){ return 1; } key=(key+step+HASHTABLE_LENGTH)%HASHTABLE_LENGTH; //处理冲突，线性探测再散列 if(step>0) step=-step; else{ step=-step; step++; } } return 0; } //求所有可能的字符串 void getString(char* num) { int i,digit,max; if(*num==0){//递归出口，字符串已到末尾 string.str[string.length]='\0'; if(search(string.str))//这个字符串存在于字典中，输出 puts(string.str); return; } digit=*num-'0';//取第一位字符，转成数字 if(digit>=2&&digit<=6){ i=(digit-2)*3+'A'; max=(digit-2)*3+'A'+3; } else if(digit==7){ i='P'; max='P'+4; } else if(digit==8){ i='T'; max='T'+3; } else if(digit==9){ i='W'; max='W'+4; } for(i;i<max;i++){ string.str[string.length++]=i; getString(num+1); //递归 string.length--; } } void main() { char num[STRING_LENGTH]; //由于输入的数字超出了unsigned long的范围，所以用字符串来存储 readString(); //把字典从文件中读入内存 printf("please inputer an number(1--12位,不能有0或1)\n"); scanf("%s",num); getString(num); } |
（8）Hash查找算法C++源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ // Hash哈希查找模板类 2017-04-23 16:15 #ifndef _HASH_H_ #define _HASH_H_ #define SEARCH_KEY_NOT_FOUND -1 enum FlagType { //哈希表元素标记 FLAG_WITH_DATA, //已经有元素 FLAG_WITH_DELETED, //该元素被删除 FLAG_WITH_EMPTY, //没有元素，空地址 }; ////////////////////////////////////////////////////////////////////////////// // 哈希表模板类 template< class ElemType, class KeyType> class HashTable { public: HashTable (int tableSize, int prime);//构造哈希表,参数为表长和哈希函数用质数 ~HashTable ( );//销毁表 void Clear();//清空哈希表 int Search(const KeyType& key);//查找元素 bool Insert(const ElemType& e, KeyType key); //插入关键字为key的元素e bool Delete(const KeyType& key);//删除元素 int GetElementCount ();//当前元素个数 int GetSize ();//表长 void Display ();//显示哈希表 private: ElemType *m_HT;//保存哈希表的数组 FlagType *m_pFlags;//元素标志 int m_size;//哈希表大小 int m_elementCount;//哈希表中已用单元个数 int m_prime;//质数 int m_current;//当前地址,线性探测再哈希用 int _Hash(const ElemType key);//哈希函数 int _LinearProbe ();//线性探测再散列获得下一地址 }; ////////////////////////////////////////////////////////////////////////////// //实际应用中可能需要重载ElemType和KeyType==运算 //构造哈希表,参数为表长和哈希函数用质数 template< class ElemType, class KeyType> HashTable<ElemType,KeyType>::HashTable (int tableSize, int prime) { m_size = tableSize; m_elementCount = 0; m_prime = prime; m_HT = new ElemType[m_size]; m_pFlags = new FlagType[m_size]; for (int i=0; i< m_size; i++) m_pFlags[i] = FLAG_WITH_EMPTY; } //析构函数 template< class ElemType, class KeyType> HashTable<ElemType,KeyType>::~HashTable () { delete []m_HT; delete []m_pFlags; } //清空哈希表 template< class ElemType, class KeyType> void HashTable<ElemType,KeyType>::Clear () { for (int i = 0; i< m_size; i++) m_pFlags[i] = FLAG_WITH_EMPTY; m_elementCount = 0; } //哈希函数 template< class ElemType, class KeyType> int HashTable<ElemType,KeyType>::_Hash(const ElemType key) { m_current = key % m_prime; return m_current; } //线性探测再哈希获得下一地址 template< class ElemType, class KeyType> int HashTable<ElemType,KeyType>::_LinearProbe() { m_current = (m_current + 1) % m_size; return m_current; } //初始条件：给定待查找元素的关键字 //返回结果：查找该元素在哈希表中是否存在，若存在返回其地址，否则返回-1 template< class ElemType, class KeyType> int HashTable<ElemType,KeyType>::Search (const KeyType& key) { int i = _Hash(key);//根据key获得初始哈希地址 int firstIndex = i; while (1) { if (FLAG_WITH_EMPTY == m_pFlags[i]) //该地址为空，查找失败 return SEARCH_KEY_NOT_FOUND; if (FLAG_WITH_DATA == m_pFlags[i] && m_HT[i] == key) //该地址正在使用且存放元素值为给定值，查找成功 return i; i = _LinearProbe (); //线性探测再散列获得下一地址 if (i == firstIndex) break; } return SEARCH_KEY_NOT_FOUND; } //初始条件：插入关键字为key的元素e //返回结果：若成功插入哈希表则返回True,否则返回False template< class ElemType, class KeyType> bool HashTable<ElemType,KeyType>::Insert(const ElemType& e, KeyType key) { int i = _Hash(key);//根据key获得初始哈希地址 int firstIndex = i; while (1) { if (FLAG_WITH_EMPTY == m_pFlags[i] || //该地址为空或该位置元素已删除 FLAG_WITH_DELETED == m_pFlags[i] ) { m_pFlags[i] = FLAG_WITH_DATA; m_HT[i] = e; m_elementCount ++; return true; } i = _LinearProbe (); //线性探测再散列获得下一地址 if (i == firstIndex) break; } return false; } //初始条件：给定待删除元素key //返回结果：若成功删除，返回True，否则返回False template< class ElemType, class KeyType> bool HashTable<ElemType,KeyType>::Delete(const KeyType& key) { int i = Search(key); if (SEARCH_KEY_NOT_FOUND != i) { m_pFlags[i] = FLAG_WITH_DELETED; m_elementCount--; return true; } return false; } //返回哈希表元素个数 template< class ElemType, class KeyType> int HashTable<ElemType,KeyType>::GetElementCount () { return m_elementCount; } template< class ElemType, class KeyType> int HashTable<ElemType,KeyType>::GetSize() { return m_size; } template< class ElemType, class KeyType> void HashTable<ElemType,KeyType>::Display() { int i, data; FlagType flag; cout<<"哈希表表长："<<GetSize()<<" 哈希表内容为: "; if (0 == GetElementCount ()) { cout<<"空"<<endl<<endl; return; } cout<<endl; for (i=0; i<GetSize(); i++) { flag = m_pFlags[i]; if (FLAG_WITH_DATA == flag) { data = m_HT[i]; cout<<"HT["<<i<<"]="<<data<<" "; } else { if (FLAG_WITH_DELETED == flag) cout<<"HT["<<i<<"]=删除 "; else cout<<"HT["<<i<<"]=空 "; } if ( 4 == (i % 5) ) cout<<endl; } cout<<endl<<endl; return; } #endif |
