HashTable的C++实现

由哈希表的定义，采用C++完成了一个学生成绩存储系统，分析过程如下：

由于哈希表是按KEY值存储，我们假设KEY值为一个字符串。hash算法为字符串的前两位大写字母所对应的数字对一个质数的模运算。

int Hash(KeyType c)
{
    int n = c[0] - 'A'+c[1]-'A'+2;
    return n % Mod;
}

哈希表的类定义如下

class HashTable
{
public:
//    HashTable();
    HashTable(int len);
    ~HashTable();
    bool SearchHash(KeyType K, int &p, int &c,int &s);
    bool InsertHash(ElemType e);
private:
    ElemType * elem;
    int count;
    int sizeindex;
};

搜索函数SearchHash

bool HashTable::SearchHash(KeyType K, int &p, int &c,int &s)
{
    c = 0;
    p = Hash(K);
    std::string NULLKey = "None";
    while (this->elem[p].key != NULLKey && K != this->elem[p].key)
    {
        p++;
        c++;//冲突次数++
    }
//    cout << "after,p = " << p << endl;
    if (K == this->elem[p].key)
    {
        s = elem[p].score;
        return true;
    }
    else
        return false;
}

View Code

插入函数InsertHash

bool HashTable::InsertHash(ElemType e)
{
    int c = 0;//c为冲突次数
    int p,s;
    if (SearchHash(e.key, p, c,s))
        return false;
    else if (c < Hashsize[this->sizeindex] / 2)
    {
        this->elem[p] = e;
        this->count++;
        return true;
    }
    else
    {
        HashTable();
        return false;
    }
}

View Code

任务源代码如下：

哈希表元素类

 1 //ElemType.h
 2 
 3 #ifndef ELEMTYPE_H
 4 #define ELEMTYPE_H
 5 #include<string>
 6 typedef std::string KeyType;
 7 class ElemType
 8 {
 9 public:
10     KeyType key;
11     int score;
12 };
13 #endif

哈希表类

 1 //HashTable.h
 2 
 3 #ifndef HASHTABLE_H
 4 #define HASHTABLE_H
 5 #include"ElemType.h"
 6 
 7 class HashTable
 8 {
 9 public:
10 //    HashTable();
11     HashTable(int len);
12     ~HashTable();
13     bool SearchHash(KeyType K, int &p, int &c,int &s);
14     bool InsertHash(ElemType e);
15 private:
16     ElemType * elem;
17     int count;
18     int sizeindex;
19 };
20 
21 
22 #endif

哈希表的操作函数

 1 //HashTable.cpp
 2 
 3 #include"HashTable.h"
 4 #include<iostream>
 5 using namespace std;
 6 const int Mod = 19;//质数模
 7 int Hashsize[] = { 47,71,97,133 };
 8 int Hash(KeyType c)
 9 {
10     int n = c[0] - 'A'+c[1]-'A'+2;
11     return n % Mod;
12 }
13 
14 HashTable::HashTable(int len=20)
15 {
16     elem = new ElemType[len];
17     for (int i = 0; i < len; i++)
18     {
19         elem[i].key = "None";
20     }
21     count = 0;
22     sizeindex = 0;
23 }
24 
25 HashTable::~HashTable()
26 {
27     delete[] elem;
28     count = 0;
29     sizeindex = 0;
30 }
31 
32 bool HashTable::SearchHash(KeyType K, int &p, int &c,int &s)
33 {
34     c = 0;
35     p = Hash(K);
36     std::string NULLKey = "None";
37     while (this->elem[p].key != NULLKey && K != this->elem[p].key)
38     {
39         p++;
40         c++;//冲突次数++
41     }
42 //    cout << "after,p = " << p << endl;
43     if (K == this->elem[p].key)
44     {
45         s = elem[p].score;
46         return true;
47     }
48     else
49         return false;
50 }
51 
52 bool HashTable::InsertHash(ElemType e)
53 {
54     int c = 0;//c为冲突次数
55     int p,s;
56     if (SearchHash(e.key, p, c,s))
57         return false;
58     else if (c < Hashsize[this->sizeindex] / 2)
59     {
60         this->elem[p] = e;
61         this->count++;
62         return true;
63     }
64     else
65     {
66         HashTable();
67         return false;
68     }
69 }

信息存储的实现

 1 //Main.cpp
 2 
 3 #include"HashTable.h"
 4 #include<iostream>
 5 using namespace std;
 6 int main()
 7 {
 8     HashTable* H = new HashTable(100);
 9     ElemType e;
10     int p,c;
11     int i=1;
12     KeyType k;
13     int score;
14     while (i != 0)
15     {
16         switch (i)
17         {
18         case 1:
19             cout << "***______HashTable_____***" << endl;
20             cout << "***___1.Display menu___***" << endl;
21             cout << "***___2.Insert_________***" << endl;
22             cout << "***___3.Search_________***" << endl;
23             cout << "***___0.Exit___________***" << endl;
24             break;
25         case 2:
26             cout << "input name with A~Z: ";
27             cin >> k;
28             e.key = k;
29             cout << "input score with number: ";
30             cin >> score;
31             e.score = score;
32             H->InsertHash(e);
33             break;
34         case 3:
35             cout << "input name with A~Z: ";
36             cin >> k;
37             if (H->SearchHash(k, p, c, score))
38             {
39                 cout << k << "'s score is " << score << endl;;
40             }
41             else
42                 cout << "can't found" << endl;
43             break;
44 
45         }
46         cout << "输入选项：";
47         cin >> i;
48     }
49     system("pause");
50     return 0;
51 }

效果如下

***______HashTable_____***
***___1.Display menu___***
***___2.Insert_________***
***___3.Search_________***
***___0.Exit___________***
输入选项：2
input name with A~Z: DSG
input score with number: 99
输入选项：2
input name with A~Z: QWER
input score with number: 70
输入选项：3
input name with A~Z: DSG
DSG's score is 99
输入选项：2
input name with A~Z: OOP
input score with number: 100
输入选项：3
input name with A~Z: QWER
QWER's score is 70
输入选项：3
input name with A~Z: OOP
OOP's score is 100
输入选项：0
请按任意键继续. . .