Hash表的实现

 1 #include "stdafx.h"
 2 #include <iostream>
 3 #include <exception>
 4 using namespace std;
 5 
 6 /*散列表查找实现
 7 散列表如果没有冲突,查找效率就非常高的.时间复杂度是O(1);但是实际应用中,冲突是不可避免的.
 8 那么散列表的平均查找长度取决于
 9 1.散列函数是否均匀.
10 2.处理冲突的方法.
11 3.散列表的装填因子.a = 填入表中的记录个数 / 散列表的长度.当a越大,产生冲突的可能性就越大.
12 用空间来换取时间
13 */
14 const int success = 1;
15 const int unSuccess = 0 ;
16 const int hashSize = 12;
17 const int nullKey = -32768;
18 const int ok = 1;
19 typedef struct
20 {
21     int *elem;
22     int count;
23 }HashTable;
24 int m = 0;
25 
26 /*初始化散列表*/
27 int InitHashTable(HashTable *H)
28 {
29     int i ;
30     m = hashSize;
31     H->count = m;
32     H->elem = (int *)malloc(sizeof(int));
33     for(int i = 0;i!=m;++i)
34         H->elem[i]=nullKey; //所有元素初始化
35     return ok;
36 }
37 
38 /*散列函数*/
39 int Hash(int key)
40 {
41     return key%m; //除留余数法
42 }
43 
44 /*插入关键字进散列表*/
45 void InsertHash(HashTable *H,int key)
46 {
47     int addr = Hash(key);
48     while(H->elem[addr]!=nullKey)
49     {
50         addr = (addr+1)%m;
51     }
52     H->elem[addr] = key;
53 }
54 
55 /*散列表查找关键字*/
56 int SearchHash(HashTable H,int key,int *addr)
57 {
58     *addr = Hash(key);
59     while(H.elem[*addr]!=key)
60     {
61         *addr=(*addr+1)%m;
62         if(H.elem[*addr] == nullKey|| *addr ==Hash(key))
63         {
64             return unSuccess;
65         }
66     }
67     return success;
68 }
69 int _tmain(int argc, _TCHAR* argv[])
70 { 
71     
72 
73     return 0 ;
74 }