Chương trình C ++ để triển khai các bảng băm với phép dò tuyến tính

Bảng băm là một cấu trúc dữ liệu được sử dụng để lưu trữ các cặp khóa-giá trị. Hàm băm được sử dụng bởi bảng băm để tính toán một chỉ mục vào một mảng trong đó một phần tử sẽ được chèn hoặc tìm kiếm.

Thăm dò tuyến tính là một kỹ thuật giải quyết xung đột trong các bảng băm bổ sung được mở. Trong phương pháp này, mỗi ô của bảng băm lưu trữ một cặp khóa-giá trị duy nhất. Nếu xung đột xảy ra bằng cách ánh xạ một khóa mới tới một ô của bảng băm đã bị khóa khác chiếm giữ. Phương pháp này tìm kiếm vị trí trống gần nhất sau đây trên bảng và chèn khóa mới vào đó.

Đây là một chương trình C ++ để triển khai các bảng băm với phép dò tuyến tính.

Thuật toán

Đối với Chèn:

 Bắt đầu Khai báo Hàm Chèn (int k, int v) int hash_val =HashFunc (k) intialize init =-1 intialize Delindex =-1 while (hash_val! =init and (ht [hash_val] ==DelNode ::getNode ( ) hoặc ht [hash_val]! =NULL và ht [hash_val] -> k! =k)) if (init ==-1) init =hash_val if (ht [hash_val] ==DelNode ::getNode ()) Delindex =hash_val hash_val =HashFunc (hash_val + 1) if (ht [hash_val] ==NULL || hash_val ==init) if (Delindex! =-1) ht [Delindex] =new HashTable (k, v) else ht [hash_val] =new HashTable (k, v) if (init! =hash_val) if (ht [hash_val]! =DelNode ::getNode ()) if (ht [hash_val]! =NULL) if (ht [hash_val] -> k ==k) ht [hash_val] -> v =v else ht [hash_val] =new HashTable (k, v) End. 

Để tìm kiếm một khóa:

 Begin Khai báo Hàm SearchKey (int k) int hash_val =HashFunc (k) int init =-1 while (hash_val! =init and (ht [hash_val] ==DelNode ::getNode () or ht [hash_val]! =NULL và ht [hash_val] -> k! =K)) if (init ==-1) init =hash_val hash_val =HashFunc (hash_val + 1) if (ht [hash_val] ==NULL or hash_val ==init) return - 1 khác trả về ht [hash_val] -> vEnd. 

Để xóa:

 Begin Khai báo Hàm Remove (int k) int hash_val =HashFunc (k) intialize init =-1 while (hash_val! =init and (ht [hash_val] ==DelNode ::getNode () or ht [hash_val]! =NULL và ht [hash_val] -> k! =K)) if (init ==-1) init =hash_val hash_val =HashFunc (hash_val + 1) if (hash_val! =Init &&ht [hash_val]! =NULL) xóa ht [hash_val] ht [hash_val] =DelNode ::getNode () End 

Mã mẫu

 #include  #include  #include  using namespace std; const int T_S =5; class HashTable {public:int k; trong TV; HashTable (int k, int v) {this-> k =k; this-> v =v; }}; class DelNode:public HashTable {private:static DelNode * en; DelNode ():HashTable (-1, -1) {} public:static DelNode * getNode () {if (en ==NULL) en =new DelNode (); return en; }}; DelNode * DelNode ::en =NULL; class HashMapTable {private:HashTable ** ht; public:HashMapTable () {ht =new HashTable * [T_S]; for (int i =0; i  k! =k)) {if (init ==-1 ) init =hash_val; if (ht [hash_val] ==DelNode ::getNode ()) Delindex =hash_val; hash_val =HashFunc (hash_val + 1); } if (ht [hash_val] ==NULL || hash_val ==init) {if (Delindex! =-1) ht [Delindex] =new HashTable (k, v); else ht [hash_val] =new HashTable (k, v); } if (init! =hash_val) {if (ht [hash_val]! =DelNode ::getNode ()) {if (ht [hash_val]! =NULL) {if (ht [hash_val] -> k ==k) ht [hash_val] -> v =v; }} else ht [hash_val] =new HashTable (k, v); }} int SearchKey (int k) {int hash_val =HashFunc (k); int init =-1; while (hash_val! =init &&(ht [hash_val] ==DelNode ::getNode () || ht [hash_val]! =NULL &&ht [hash_val] -> k! =k)) {if (init ==-1 ) init =hash_val; hash_val =HashFunc (hash_val + 1); } if (ht [hash_val] ==NULL || hash_val ==init) return -1; khác trả về ht [hash_val] -> v; } void Remove (int k) {int hash_val =HashFunc (k); int init =-1; while (hash_val! =init &&(ht [hash_val] ==DelNode ::getNode () || ht [hash_val]! =NULL &&ht [hash_val] -> k! =k)) {if (init ==-1 ) init =hash_val; hash_val =HashFunc (hash_val + 1); } if (hash_val! =init &&ht [hash_val]! =NULL) {xóa ht [hash_val]; ht [hash_val] =DelNode ::getNode (); }} ~ HashMapTable () {xóa [] ht; }}; int main () {Hàm băm HashMapTable; int k, v; int c; while (1) {cout <<"1.Chèn phần tử vào bảng" <> c; switch (c) {case 1:cout <<"Nhập phần tử cần chèn:"; cin>> v; cout <<"Nhập khóa tại đó phần tử sẽ được chèn:"; cin>> k; hash.Insert (k, v); phá vỡ; case 2:cout <<"Nhập khóa của phần tử cần tìm:"; cin>> k; if (hash.SearchKey (k) ==-1) {cout <<"Không tìm thấy phần tử nào trong khoá" <> k; hash.Remove (k); phá vỡ; case 4:exit (1); default:cout <<"\ nNhập đúng tùy chọn \ n"; }} trả về 0;} 

Đầu ra

 1.Chèn phần tử vào bảng2. Tìm kiếm phần tử từ khóa3. Xóa phần tử tại một khóa4. Tìm kiếm phần tử từ key3. Xóa phần tử tại một khóa4 .ExitEnter sự lựa chọn của bạn:1Nhập phần tử sẽ được chèn:7 Nhập khóa tại đó phần tử sẽ được chèn:61.Chèn phần tử vào bảng2. .ExitEnter your choice:1Enter phần tử sẽ được chèn:4Enter key tại đó phần tử sẽ được chèn:51.Chêm phần tử vào bảng2.Search phần tử từ key3.Xóa phần tử tại key4 12 Nhập khóa tại đó phần tử sẽ được chèn:31. Chèn phần tử vào bảng2. Tìm kiếm phần tử từ khóa3 .Xóa phần tử tại một khóa4. tại một key4 .ExitEnter sự lựa chọn của bạn:1Enter phần tử sẽ được chèn:15 Nhập khóa tại đó phần tử sẽ được chèn:81. Chèn phần tử vào bảng2. Tìm kiếm phần tử từ khóa3 .Xóa phần tử tại một khóa4. ThoátNhập khóa của bạn:2Nhập khóa của phần tử cần tìm:6Phần tử tại khóa 6:71 Chèn phần tử vào bảng 2. Tìm kiếm phần tử từ khóa3. Xóa phần tử tại một khóa4 .ExitNhập khóa của bạn:3Nhập khóa của phần tử cần xóa:21.Chèn phần tử vào bảng2. Tìm kiếm phần tử từ khóa3. Xóa phần tử tại khóa4.ExitEnter your choice:2Nhập khóa của phần tử cần tìm kiếm:2No phần tử được tìm thấy tại khóa 21.Chèn phần tử vào bảng2. trước>