C/C++一个简单的哈希表实现

  1 #ifndef _HASHTABLE_H_
  2 #define _HASHTABLE_H_
  3 #include <iostream>
  4 #include <cstdlib>
  5 using namespace std;
  6 
  7 typedef
  8 enum {
  9     Empty, Active, Deleted
 10 }kindofitem;
 11 
 12 typedef struct
 13 {
 14     int key;
 15 }datatype;
 16 
 17 typedef struct{
 18     datatype data;
 19     kindofitem info;
 20 }hashitem;
 21 
 22 typedef struct{
 23     hashitem* arr;
 24     int table_size;
 25     int current_size;
 26 }hashtable;
 27 
 28 int initiate(hashtable* hash, int size);//初始化哈希表
 29 int find(hashtable* hash, datatype x);//查找x元素对应的关键字
 30 int insert(hashtable* hash, datatype x);//像哈希表中插入数组元素x，及设置它对应的关键字
 31 int deleted(hashtable* hash, datatype x);//从哈希表中删除x数据元素
 32 void destroy(hashtable* hash);//撤销函数
 33 /*
 34 int main()
 35 {
 36 
 37 system("pause");
 38 return 0;
 39 }
 40 */
 41 int initiate(hashtable* hash, int size)
 42 {
 43     hash->arr = (hashitem*)malloc(sizeof(hashitem)*size);//初始化，该数组
 44     hash->table_size = size;
 45     if (hash->arr == NULL)
 46     {
 47         cout << "初始化失败" << endl;
 48         return 0;
 49     }
 50     else
 51     {
 52         hash->current_size = 0;
 53         return 1;
 54     }
 55 }
 56 
 57 int find(hashtable* hash, datatype x)//查找x元素对应的关键字
 58 {
 59     int i = x.key%hash->table_size;
 60     int j = i;
 61     while (hash->arr[j].info == Active&&hash->arr[j].data.key != x.key)
 62     {
 63         j = (j + 1)&hash->table_size;//用哈希冲突方法继续查找
 64         if (j == i)
 65         {
 66             cout << "遍历此哈希表，没有找到" << endl;
 67             return -hash->table_size;
 68         }
 69     }
 70     if (hash->arr[j].info == Active)
 71     {
 72         return j;
 73     }
 74     else{
 75         return -j;
 76     }
 77 }
 78 
 79 int insert(hashtable* hash, datatype x)
 80 {
 81     int i = find(hash, x);
 82     if (i > 0)
 83     {
 84         cout << "该数据元素已经存在了！" << endl;
 85         return 0;
 86     }
 87 
 88     else if (i != -hash->table_size)
 89     {
 90         hash->arr[-i].data = x;
 91         hash->arr[-i].info = Active;
 92         hash->current_size++;
 93         return 1;
 94     }
 95     else{
 96         return 0;
 97     }
 98 }
 99 
100 int deleted(hashtable* hash, datatype x)
101 {
102     int i = find(hash, x);
103     if (i > 0)
104     {
105         hash->arr[i].info = Deleted;
106         hash->current_size--;
107         return 1;
108     }
109     else{
110         cout << "没有这个元素，无法删除!" << endl;
111         return 0;
112     }
113 }
114 
115 void destroy(hashtable* hash)
116 {
117     delete[]hash->arr;
118 }
119 #endif

hashtable.h

 1 #include <iostream>
 2 using namespace std;
 3 #include "hashtable.h"
 4 void main()
 5 {
 6     hashtable myhashtable;
 7     datatype a[] = { 180, 750, 600, 430, 541, 900, 460 }, item = { 430 };
 8     int n = 7, m = 13;
 9     initiate(&myhashtable, m);
10     for (int i = 0; i < n; i++)
11     {
12         insert(&myhashtable, a[i]);
13     }
14     for (int i = 0; i < n; i++)
15     {
16         int j = find(&myhashtable, a[i]);
17         cout << "j = " << j << " " << "arr[] = " << myhashtable.arr[j].data.key << endl;
18     }
19     int k = find(&myhashtable, item);
20     if (k>0){
21         cout << "查找成功，元素" << item.key << "的哈希地址是:" << k << endl;
22     }
23     else{
24         cout << "查找失败" << endl;
25     }
26     deleted(&myhashtable, item);
27     k = find(&myhashtable, item);
28     if (k >= 0){
29         cout << "删除失败！" << endl;
30     }
31     else
32     {
33         cout << "删除成功！" << endl;
34     }
35     destroy(&myhashtable);
36     system("pause");
37     return ;
38 }

main.cpp

设计说明：（1）哈希表的长度m不同，因此存放哈希表的数组采用动态数组最为方便。初始化函数的参数msize即为哈希表的长度。（2）哈希表的操作主要有查找，插入，删除。其中，插入和删除都要查找数据元素是否在哈希表中存在。查找函数一共有三种情况：查找到，返回数据元素的哈希地址（正）；未查找到，返回一个负值（插入操作可在哈希表的改返回值的绝对值位置，插入数据元素）；未查找到，且哈希表已满无法继续插入（此时返回值为-tablesize）

（3）插入函数首先调用查找函数，当返回值（i）为负（说明数据元素不存在）且返回值不等于-tablesize（说明哈希表未满时候），在哈希表的-i位置插入数据元素。