リストヘッドでチェーンするハッシュテーブルを実装するC++プログラム
ハッシュテーブルは、キーと値のペアを格納するために使用されるデータ構造です。ハッシュ関数は、要素が挿入または検索される配列へのインデックスを計算するためにハッシュテーブルによって使用されます。
これは、リストヘッドを使用してチェーンするハッシュテーブルを実装するためのC++プログラムです。
アルゴリズム
挿入の場合：
Begin Declare function Insert(int k, int v) int hash_v = HashFunc(k) if (ht[hash_v] == NULL) ht[hash_v] = new ListHead(k, v) else ListHead *en = ht[hash_v] while (en->n != NULL) en = en->n if (en->k == k) en->v = v else en->n= new ListHead(k, v) End.
Seachのキー値：
Begin Decla Function SearchKey(int k) int hash_v = HashFunc(k) if (ht[hash_v] == NULL) return -1 else ListHead *en = ht[hash_v] while (en != NULL and en->k != k) en= en->n if (en== NULL) return -1 else return en->v End
削除の場合：
Begin Declare Function Remove(int k) int hash_v = HashFunc(k) if (ht[hash_v] != NULL) ListHead *en = ht[hash_v]; ListHead *p= NULL; while (en->n != NULL and en->k != k) p = en en = en->n if (en->k== k) if (p == NULL) ListHead *n= en->n delete en; ht[hash_v] = n else ListHead *n= en->n delete en p->n = n End.
サンプルコード
#include <iostream>
using namespace std;
const int T_S = 20;
class ListHead {
public:
int k, v;
ListHead *n;
ListHead(int k, int v) {
this->k = k;
this->v = v;
this->n = NULL;
}
};
class HashMapTable {
private:
ListHead **ht;
public:
HashMapTable() {
ht = new ListHead*[T_S];
for (int i = 0; i < T_S; i++) {
ht[i] = NULL;
}
}
int HashFunc(int k){
return k % T_S;
}
void Insert(int k, int v) {
int hash_v = HashFunc(k);
if (ht[hash_v] == NULL)
ht[hash_v] = new ListHead(k, v);
else {
ListHead *en = ht[hash_v];
while (en->n != NULL)
en = en->n;
if (en->k == k)
en->v = v;
else
en->n= new ListHead(k, v);
}
}
int SearchKey(int k) {
int hash_v = HashFunc(k);
if (ht[hash_v] == NULL)
return -1;
else {
ListHead *en = ht[hash_v];
while (en != NULL && en->k != k)
en= en->n;
if (en == NULL)
return -1;
else
return en->v;
}
}
void Remove(int k) {
int hash_v = HashFunc(k);
if (ht[hash_v] != NULL) {
ListHead *en = ht[hash_v];
ListHead *p = NULL;
while (en->n != NULL && en->k != k) {
p = en;
en = en->n;
}
if (en->k == k) {
if (p == NULL) {
ListHead *n= en->n;
delete en;
ht[hash_v] = n;
}
else {
ListHead *n = en->n;
delete en;
p->n = n;
}
}
}
}
~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;
if (hash.SearchKey(k) == -1)
cout<<"No element found at key "<<k<<endl;
else {
cout<<"Elements at key "<<k<<" : ";
cout<<hash.SearchKey(k)<<endl;
}
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>k;
if (hash.SearchKey(k) == -1)
cout<<"Key "<<k<<" is empty"<<endl;
else {
hash.Remove(k);
cout<<"Entry Removed"<<endl;
}
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: 1 Enter key at which element to be inserted: 2 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: 10 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: 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: 12 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: 30 Enter correct option 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: 30 Enter key at which element to be inserted: 5 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 Elements 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: 3 Enter key of the element to be deleted: 1 Entry Removed 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 Elements 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: 4
-
隣接リストを実装するC++プログラム
グラフの隣接リスト表現は、リンクリスト表現です。この表現では、リストの配列があります。配列のサイズはVです。ここで、Vは頂点の数です。つまり、V個の異なるリストを格納する配列があると言えます。リストヘッダーが頂点uの場合、uの隣接するすべての頂点を保持することを意味します。 隣接リスト表現の複雑さ この表現は、無向グラフの場合はO（V + 2E）を取り、有向グラフの場合はO（V + E）を取ります。エッジの数を増やすと、必要なスペースも増えます。 入力 ： 出力 ： アルゴリズム add_edge（adj_list、u、v） 入力 ：エッジ{u、v}のuとv、およ
-
単一リンクリストを実装するC++プログラム
単一リンクリストは、自己参照構造を使用して作成されたノードで構成されるデータ構造の一種です。これらの各ノードには、データと次のリストノードへの参照という2つの部分が含まれています。リンクリスト全体にアクセスするには、最初のリストノードへの参照のみが必要です。これは頭として知られています。リストの最後のノードは何も指していないため、その部分にNULLが格納されます。 単一リンクリストを実装するためのプログラムは次のとおりです。 例 #include <iostream> using namespace std; struct Node { int da