C ++程序实现带有单链接列表的哈希表链接

哈希表是一种数据结构,用于存储键值对。哈希表使用哈希函数来计算要插入或搜索元素的数组的索引。

这是一个C ++程序,用于使用单个链接列表实现哈希表链接。

算法

对于插入:

Begin

   Declare Function Insert(int k, int v)

      int hash_v = HashFunc(k)

      HashTableEntry* p = NULL

      HashTableEntry* en = ht[hash_v]

      while (en!= NULL)

         p = en

         en= en->n

      if (en == NULL)

         en = new HashTableEntry(k, v)

         if (p == NULL)

            ht[hash_v] = en

         else

            p->n= en

      else

         en->v = v

End.

对于删除:

Begin

   Declare Function Remove(int k)

      int hash_v = HashFunc(k)

      HashTableEntry* en = ht[hash_v]

      HashTableEntry* p= NULL

      if (en == NULL or en->k != k)

         Print “No Element found at key”

         return

      while (en->n != NULL)

         p = en

         en = en->n

      if (p != NULL)

         p->n = en->n

      delete en

         Print “Element Deleted”

End.

对于搜索键值:

Begin

   Declare function SearchKey(int k)

      int hash_v = HashFunc(k)

      bool flag = false

      HashTableEntry* en = ht[hash_v]

      if (en != NULL)

         while (en != NULL)

            if (en->k == k)

               flag = true

            if (flag)

               Print “Element found at key”

               Print en->v

            en = en->n

      if (!flag)

         Print “No Element found at key”

End.

范例程式码

#include <iostream>

const int T_S = 200;

using namespace std;

struct HashTableEntry {

   int v, k;

   HashTableEntry *n;

   HashTableEntry *p;

   HashTableEntry(int k, int v) {

      this->k = k;

      this->v = v;

      this->n = NULL;

   }

};

class HashMapTable {

   public:

      HashTableEntry **ht, **top;

      HashMapTable() {

         ht = new HashTableEntry*[T_S];

         for (int i = 0; i < T_S; i++)

            ht[i] = NULL;

      }

      int HashFunc(int key) {

         return key % T_S;

      }

      void Insert(int k, int v) {

         int hash_v = HashFunc(k);

         HashTableEntry* p = NULL;

         HashTableEntry* en = ht[hash_v];

         while (en!= NULL) {

            p = en;

            en = en->n;

         }

         if (en == NULL) {

            en = new HashTableEntry(k, v);

            if (p == NULL) {

               ht[hash_v] = en;

            } else {

               p->n = en;

            }

         } else {

            en->v = v;

         }

      }

      void Remove(int k) {

         int hash_v = HashFunc(k);

         HashTableEntry* en = ht[hash_v];

         HashTableEntry* p = NULL;

         if (en == NULL || en->k != k) {

            cout<<"No Element found at key "<<k<<endl;

            return;

         }

         while (en->n != NULL) {

            p = en;

            en = en->n;

         }

         if (p != NULL) {

            p->n = en->n;

         }

         delete en;

         cout<<"Element Deleted"<<endl;

      }

      void SearchKey(int k) {

         int hash_v = HashFunc(k);

         bool flag = false;

         HashTableEntry* en = ht[hash_v];

         if (en != NULL) {

            while (en != NULL) {

               if (en->k == k) {

                  flag = true;

               }

               if (flag) {

                  cout<<"Element found at key "<<k<<": ";

                  cout<<en->v<<endl;

               }

               en = en->n;

            }

         }

         if (!flag)

            cout<<"No Element found at key "<<k<<endl;

      }

      ~HashMapTable() {

         delete [] ht;

      }

};

int main() {

   HashMapTable hash;

   int k, v;

   int c;

   while (1) {

      cout<<"1.Insert element into the table"<<endl;

      cout<<"2.Search element from the key"<<endl;

      cout<<"3.Delete element at a key"<<endl;

      cout<<"4.Exit"<<endl;

      cout<<"Enter your choice: ";

      cin>>c;

      switch(c) {

         case 1:

            cout<<"Enter element to be inserted: ";

            cin>>v;

            cout<<"Enter key at which element to be inserted: ";

            cin>>k;

            hash.Insert(k, v);

         break;

         case 2:

            cout<<"Enter key of the element to be searched: ";

            cin>>k;

            hash.SearchKey(k);

         break;

         case 3:

            cout<<"Enter key of the element to be deleted: ";

            cin>>k;

            hash.Remove(k);

         break;

         case 4:

            exit(1);

         default:

            cout<<"\nEnter correct option\n";

      }

   }

   return 0;

}

输出结果

1.Insert element into the table

2.Search element from the key

3.Delete element at a key

4.Exit

Enter your choice: 1

Enter element to be inserted: 2

Enter key at which element to be inserted: 1

1.Insert element into the table

2.Search element from the key

3.Delete element at a key

4.Exit

Enter your choice: 1

Enter element to be inserted: 3

Enter key at which element to be inserted: 4

1.Insert element into the table

2.Search element from the key

3.Delete element at a key

4.Exit

Enter your choice: 1

Enter element to be inserted: 7

Enter key at which element to be inserted: 6

1.Insert element into the table

2.Search element from the key

3.Delete element at a key

4.Exit

Enter your choice: 1

Enter element to be inserted: 8

Enter key at which element to be inserted: 9

1.Insert element into the table

2.Search element from the key

3.Delete element at a key

4.Exit

Enter your choice: 2

Enter key of the element to be searched: 6

Element found at key 6: 7

1.Insert element into the table

2.Search element from the key

3.Delete element at a key

4.Exit

Enter your choice: 2

Enter key of the element to be searched: 7

No Element found at key 7

1.Insert element into the table

2.Search element from the key

3.Delete element at a key

4.Exit

Enter your choice: 3

Enter key of the element to be deleted: 9

Element Deleted

1.Insert element into the table

2.Search element from the key

3.Delete element at a key

4.Exit

Enter your choice: 4

以上是 C ++程序实现带有单链接列表的哈希表链接 的全部内容, 来源链接: utcz.com/z/327238.html

回到顶部