Đây là chương trình C++ triển khai Bảng địa chỉ trực tiếp (Direct Addressing Tables). Bảng địa chỉ trực tiếp được dùng khi mỗi phần tử có khóa (key) lấy từ tập phổ quát S = {0, 1, ..., n-1} với n không quá lớn và mỗi khóa là duy nhất. Nó hỗ trợ chèn, tìm kiếm và xóa nhanh chóng.
Các hàm và mã giả
Bắt đầu
insert():
Nhận tham số bảng word và key.
T[x.key] = x, trong đó x là giá trị key.
delete():
Nhận tham số bảng word và key.
T[x.key] = tab(0, "")
search():
Trả về T[key]
Kết thúc
Ví dụ mã nguồn
#include <iostream>
#include <cstdlib>
#include <string>
#include <cstdio>
using namespace std;
struct tab {
// khai báo biến của bảng
string word;
int key;
tab() {}
tab(int k, string w) // constructor khởi tạo biến
{
word = w;
key = k;
}
};
void INSERT(tab T[], tab x) {
T[x.key] = x;
}
void DELETE(tab T[], tab x) {
T[x.key] = tab(0, "");
}
tab SEARCH(tab T[], int key) {
return T[key];
}
int main() {
int i, k, c;
string str;
tab T[65536]; // khởi tạo kích thước bảng
tab x;
for (i = 0; i < 65536; i++)
T[i] = tab(0, "");
while (1) {
cout << "1. Chèn phần tử vào khóa" << endl;
cout << "2. Xóa phần tử khỏi bảng" << endl;
cout << "3. Tìm kiếm phần tử trong bảng" << endl;
cout << "4. Thoát" << endl;
cout << "Nhập lựa chọn: ";
cin >> c;
switch (c) {
case 1: {
string str1 = "";
cout << "Nhập giá trị khóa: ";
cin >> k;
cout << "Nhập chuỗi cần chèn: ";
cin.ignore();
getline(cin, str);
INSERT(T, tab(k, str));
break;
}
case 2:
cout << "Nhập khóa phần tử cần xóa: ";
cin >> k;
x = SEARCH(T, k);
DELETE(T, x);
break;
case 3:
cout << "Nhập khóa phần tử cần tìm: ";
cin >> k;
x = SEARCH(T, k);
if (x.key == 0) {
cout << "Không có phần tử nào tại khóa này" << endl;
continue;
}
cout << "Phần tử tại khóa " << k << " là-> ";
cout << "\"" << x.word << "\"" << endl;
break;
case 4:
exit(1);
default:
cout << "Lựa chọn sai" << endl;
}
}
return 0;
}
Kết quả
1. Chèn phần tử vào khóa 2. Xóa phần tử khỏi bảng 3. Tìm kiếm phần tử trong bảng 4. Thoát Nhập lựa chọn: 1 Nhập giá trị khóa: 1 Nhập chuỗi cần chèn: hi 1. Chèn phần tử vào khóa 2. Xóa phần tử khỏi bảng 3. Tìm kiếm phần tử trong bảng 4. Thoát Nhập lựa chọn: 1 Nhập giá trị khóa: 2 Nhập chuỗi cần chèn: tutorials 1. Chèn phần tử vào khóa 2. Xóa phần tử khỏi bảng 3. Tìm kiếm phần tử trong bảng 4. Thoát Nhập lựa chọn: 1 Nhập giá trị khóa: 3 Nhập chuỗi cần chèn: point 1. Chèn phần tử vào khóa 2. Xóa phần tử khỏi bảng 3. Tìm kiếm phần tử trong bảng 4. Thoát Nhập lựa chọn: 3 Nhập khóa phần tử cần tìm: 1 Phần tử tại khóa 1 là-> "hi" 1. Chèn phần tử vào khóa 2. Xóa phần tử khỏi bảng 3. Tìm kiếm phần tử trong bảng 4. Thoát Nhập lựa chọn: 3 Nhập khóa phần tử cần tìm: 4 Không có phần tử nào tại khóa này 1. Chèn phần tử vào khóa 2. Xóa phần tử khỏi bảng 3. Tìm kiếm phần tử trong bảng 4. Thoát Nhập lựa chọn: 2 Nhập khóa phần tử cần xóa: 1 1. Chèn phần tử vào khóa 2. Xóa phần tử khỏi bảng 3. Tìm kiếm phần tử trong bảng 4. Thoát Nhập lựa chọn: 3 Nhập khóa phần tử cần tìm: 1 Không có phần tử nào tại khóa này 1. Chèn phần tử vào khóa 2. Xóa phần tử khỏi bảng 3. Tìm kiếm phần tử trong bảng 4. Thoát Nhập lựa chọn: 4