পরিচয়
ডায়রেক্ট অ্যাড্রেসিং টেবিল একটি সিম্পল ডেটা স্ট্রাকচার যেখানে কী (key) সরাসরি অ্যারে ইনডেক্স হিসেবে ব্যবহার করা হয়। এটি তখন কার্যকর যখন কীরা ছোট একটি র্যাঞ্জে থাকে (যেমন ০ থেকে m-1) এবং সব কী ইউনিক থাকে। ইনসার্ট, ডিলিট, সার্চ সব O(1) টাইমে হয়।
অপারেশনসমূহ:
- Insert(T, x):
T[x.key] = x - Delete(T, x):
T[x.key] = NIL - Search(T, k):
return T[k]
উদাহরণ কোড
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Entry {
string word;
int key;
Entry() : word(""), key(0) {}
Entry(int k, string w) : key(k), word(w) {}
};
class DirectAddressTable {
vector<Entry> table;
int capacity;
public:
DirectAddressTable(int cap) : capacity(cap) {
table.resize(capacity);
}
void insert(Entry x) {
if (x.key >= 0 && x.key < capacity)
table[x.key] = x;
else
cout << "Invalid key!\n";
}
void remove(int key) {
if (key >= 0 && key < capacity)
table[key] = Entry();
else
cout << "Invalid key!\n";
}
Entry search(int key) {
if (key >= 0 && key < capacity)
return table[key];
return Entry();
}
void displayMenu() {
cout << "\n1. Insert\n2. Delete\n3. Search\n4. Exit\nChoice: ";
}
};
int main() {
DirectAddressTable dat(1000);
int choice, key;
string str;
while (true) {
dat.displayMenu();
cin >> choice;
if (choice == 1) {
cout << "Key: "; cin >> key;
cout << "String: "; cin.ignore(); getline(cin, str);
dat.insert(Entry(key, str));
} else if (choice == 2) {
cout << "Key to delete: "; cin >> key;
dat.remove(key);
} else if (choice == 3) {
cout << "Key to search: "; cin >> key;
Entry e = dat.search(key);
if (e.key == 0 && e.word.empty())
cout << "No element at key " << key << "\n";
else
cout << "Element at key " << key << " -> \"" << e.word << "\"\n";
} else if (choice == 4) {
break;
} else {
cout << "Wrong choice!\n";
}
}
return 0;
}আউটপুট উদাহরণ
1. Insert 2. Delete 3. Search 4. Exit Choice: 1 Key: 10 String: hello ... Choice: 3 Key: 10 Element at key 10 -> "hello"
ব্যাখ্যা
ডায়রেক্ট অ্যাড্রেসিং টেবিলে কী ভ্যালু সরাসরি অ্যারে ইনডেক্স হিসেবে কাজ করে। এই উদাহরণে `vector` ব্যবহার করা হয়েছে ফিক্সড সাইজ অ্যারের পরিবর্তে, যা আরও ফ্লেক্সিবল। কী র্যাঞ্জ বড় হলে (যেমন ৩২-বিট ইন্টিজার) এই পদ্ধতি মেমরি অপচয় করে, সেক্ষেত্রে হ্যাশ টেবিল ভালো।
