字典，又被称为映射或关联数组，也是一种数据结构类型。
字典中包含关键码和属性的二元组称作关联。
与字典相关的基本操作包括：
1.插入具有给定关键码及对应属性的元素；
2.在字典中寻找具有给定关键码的元素；
3.从字典中删除具有给定关键码的元素；
实现字典树一般都需要借助于本书前面所介绍过的各种树形搜索结构。比如选择红黑树，AVL树或者字典树。
首先先是词条类的源代码：
class Item {
string english;
string chinese;
Item* link;
public:
Item(): link(nullptr) {}
Item(string en, string ch): link(nullptr), english(en), chinese(ch) {}
~Item(){};
void SetLink(Item* next);
Item* GetLink();
string GetIndex();
string GetValue();
};
void Item::SetLink(Item *next) {
link = next;
}
Item* Item::GetLink() {
return link;
}
string Item::GetIndex() {
return english;
}
string Item::GetValue() {
return chinese;
}
字典的结构体代码如下：
class Dictionary{
Item* head;
Item* tail;
public:
Dictionary();
virtual ~Dictionary();
bool Add(string en, string ch);
bool Del(string en);
string Search(string en);
int GetCount();
void RemoveAll();
};
Dictionary::Dictionary() {
head = new Item();
tail = head;
tail->SetLink(nullptr);
}
Dictionary::~Dictionary() {
RemoveAll();
delete head;
}
bool Dictionary::Add(string en, string ch) {
Item* add = new Item(en, ch);
tail -> SetLink(add);
tail = tail->GetLink();
tail -> SetLink(nullptr);
if(tail != nullptr) return true;
else return false;
}
bool Dictionary::Del(string en) {
Item* cur, *curPre;
cur = head;
curPre = cur -> GetLink();
while(cur != nullptr) {
if(curPre -> GetIndex() == en) break;
cur = cur -> GetLink();
if(cur != nullptr) curPre = curPre -> GetLink();
}
if(tail == curPre) tail = cur;
cur -> SetLink(curPre -> GetLink());
delete curPre;
if(curPre != nullptr) return true;
else return false;
}
string Dictionary::Search(string en) {
Item* cur;
cur = head -> GetLink();
while(cur != nullptr) {
if(en == cur -> GetIndex()) break;
cur = cur -> GetLink();
}
if (cur != nullptr) return cur -> GetValue();
else return "Cannot Find!";
}
int Dictionary::GetCount() {
int count = 0;
Item* current = head -> GetLink();
while(current != nullptr) {
++count;
current = current -> GetLink();
}
return count;
}
void Dictionary::RemoveAll() {
Item* cur;
while (head -> GetLink() != nullptr) {
cur = cur -> GetLink();
head -> SetLink(cur -> GetLink());
delete cur;
}
tail = head; // 置表尾于表头处
}
搜索方法
接下来介绍几种在字典当中比较常见的搜索方法：
1.顺序搜索
顺序搜索是一种最简单、普遍的搜索方法。
接下来给出定义：
template <class T>
class Item{
int key;
T data;
public:
Item():key(-1) {}
Item(int keyInput, T value): key(keyInput), data(value){assert(key >= 0);}
int GetKey(){return key;}
T GetData(){return data;}
friend ostream&operator<<(ostream& stream, Item<T>& item);
};
template <class T>
class OrderSearch{
Item<T>* contain;
int size;
public:
OrderSearch(): contain(nullptr), size(0) {}
OrderSearch(int maxSize);
void Add(Item<T> add);
int GetSize() {return size;}
Item<T>* GetContain() {return contain;}
Item<T>& Search(int k);
friend ostream&operator<<(ostream& stream, OrderSearch<T>& set);
};
我们在定义OrderSearch之前先定义了一个二元组类Item，其中有两个数据成员，分贝为关键码key和属性data。
在类OrderSearch中定义了两个私有成员变量contain和size，其中contain是一个指向静态数据的指针，变量size记录字典中最多可以存放的二元组数目，也就是数据contain的长度。
具体函数的实现如下：
template <class T>
OrderSearch<T>::OrderSearch(int maxSize) {
contain = new Item<T>[maxSize];
size = maxSize;
for(int i=0; i < maxSize; i++)
{
Item<T> ini;
contain[i] = ini;
}
}
template <class T>
void OrderSearch<T>::Add(Item<T> add) {
assert(add.GetKey() >= 0 && add.GetKey() <= size);
contain[add.GetKey()] = add;
}
template <class T>
Item<T>& OrderSearch<T>::Search(int k) {
assert(k >= 0 && k < size);
return contain[k];
}
template <class T>
ostream& operator<<(ostream& stream, OrderSearch<T>& set) {
for(int i=0; i < set.GetSize(); i++) {
if(set.GetContain()[i].GetKey() != -1) {
cout << "key:" << set.GetContain()[i].GetKey() << "\t";
cout << "data:" << set.GetContain()[i].GetData() << end;
}
}
return stream;
}
顺序搜索最大的缺点是这种方法仅适用于字典比较小的情况。而且，这种方法的时间复杂度是非常不稳定的，因为很有可能第一次我就找到了我想要的内容，也有可能要全部遍历完才能找到我想要的东西，因此是很不稳定的。
2.折半搜索
接下来再介绍一下折半搜索，与顺序搜索相比，这是一种更加快速的搜索方法。这种方法对集合中元素的个数没有限制，即时是很大的集合，也能迅速地找出特定元素。
代码和排序中的折半搜索是一样的，因此在这里就不再赘述。
网友评论