聲明：本文為學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法分析(第三版) Clifford A.Shaffer 著的學(xué)習(xí)筆記，代碼有參考該書的示例代碼。

字典

碎碎語：其實(shí)我一直對這個(gè)數(shù)據(jù)結(jié)構(gòu)不是很了解。
字典 (Dictionary) 作為數(shù)據(jù)庫的一個(gè)簡單接口，提供在數(shù)據(jù)庫中存儲(chǔ)、查詢和刪除記錄的可能。
字典中有定義關(guān)鍵碼 （search key）的概念。而關(guān)鍵碼則必須是可比的
字典的ADT如下：

template<typename Key, typename E> class Dictionary {Dictionary(const Dictionary& ) {}Dictionary& operator= (const Dictionary&) {}public:Dictionary() {}virtual ~Dictionary() {}virtual void clear() = 0;virtual void insert(const Key&, const E&) = 0;virtual E remove(const Key&) = 0;virtual E removeAny() = 0;virtual E find(const Key&) const = 0;virtual int length() const = 0; };

insert 函數(shù)和 find 函數(shù)是這個(gè)類的核心。find 函數(shù)接受一個(gè)任意的關(guān)鍵碼，從字典中找出這個(gè)關(guān)鍵碼，并且將相關(guān)的記錄返回。如果有多條記錄匹配，則返回任意一條。
removeAny 函數(shù)提供了用戶隨意選擇一條記錄，并進(jìn)行操作。

應(yīng)用舉例

假如實(shí)現(xiàn)了一個(gè)工資記錄的字典。Payroll 類有很多域，每個(gè)域都可以作為搜索關(guān)鍵碼。
下面展示了對Payroll 的存儲(chǔ)，一個(gè)是對ID進(jìn)行檢索，一個(gè)對name進(jìn)行檢索。

class Payroll {int ID;string name;string address;public:Payroll(int inID, string inname, string inaddr):ID(inID), name(inname), address(inaddr) {}~Payroll() {}int getID() { return ID; }string getname() { return name; }string getaddr() { return address; } };int main() {Udict<int, Payroll*> dict;Udict<string, Payroll*> namedict;Payroll *foo1, *foo2, *findfoo1, *findfoo2;foo1 = new Payroll(5, "Joe", "Anytown");foo2 = new Payroll(10, "John", "Mytown");dict.insert(foo1->getID(), foo1);dict.insert(foo2->getID(), foo2);namedict.insert(foo1->getname(), foo1);namedict.insert(foo2->getname(), foo2);findfoo1 = dict.find(5);if(findfoo1!=nullptr)cout<<findfoo1<<endl;elsecout<<"nullptr"<<endl;findfoo2 = namedict.find("John");if(findfoo2 != nullptr)cout<<findfoo2<<endl;elsecout<<"nullptr"<<endl; }

Key-Value 實(shí)現(xiàn)

一般情況下，將關(guān)鍵碼和值存儲(chǔ)成相關(guān)聯(lián)的關(guān)系。字典中任何一條基本元素包含了一條記錄，以及與該記錄相關(guān)的關(guān)鍵碼。這就是所謂的鍵-值對。實(shí)現(xiàn)如下：

template<typename Key, typename E> class KVpair {Key k;E e;public:KVpair() {}KVpair(Key key, E value):k(key), e(value) {}KVpair(const KVpair& pair){k = pair.key();e = pair.value();}KVpair& operator= (const KVpair& pair){k = pair.key();e = pair.value();return *this;}Key key() const { return k; }E value() const { return e; }void setKey(Key ink) { k = ink; }void set(Key ink, E ine) { k = ink, e = ine; }bool operator>(const KVpair& o) const{return k>o.key();}bool operator< (const KVpair& o) const{return k<o.k;} };

* 與課本不同的是，
* 重載< 和 > 號(hào)是為了便利 SList 中 insert 函數(shù)的實(shí)現(xiàn)。其中 SList 在List.h 中單獨(dú)實(shí)現(xiàn)，采用鏈表的方式，這是為了能夠使得 SList 成為一個(gè)可以重用的模板類

有序字典和無序字典

書本給出了有序字典和無序字典的實(shí)現(xiàn)，無序字典使用了線性表的數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)比較簡單。
而有序字典根據(jù)關(guān)鍵碼進(jìn)行排序插入，另外實(shí)現(xiàn)了一個(gè)有序線性表，實(shí)現(xiàn)如下：

template<typename E> class SList:protected LList<E> {public:SList(int size): LList<E>(size) {}SList() {}~SList() {}void insert (const E& it){if(length()==0){LList<E>::insert(it); return;}moveToStar();int left = 0, right = length()-1;int mid;auto get = [&](int pos) -> const E&{moveToPos(pos);return getValue();};auto f = [&]() -> bool{if(left>=right){if(get(left)<it)next();return false;}mid = left + (right-left)/2;const E& temp = get(mid);if(it<temp){right = mid-1;return true;}else{return false;}};while( f() ) ;LList<E>::insert(it);}using LList<E>::moveToStar;using LList<E>::prev;using LList<E>::next;using LList<E>::length;using LList<E>::moveToPos;using LList<E>::getValue;using LList<E>::currPos;using LList<E>::clear;using LList<E>::moveToEnd;using LList<E>::remove; };

其中，涉及到關(guān)鍵碼的比較，但是我將整個(gè)鍵值對封裝為E的模板了，所以鍵值對中是需要定義實(shí)現(xiàn)重載大于、小于號(hào)的。
同時(shí)，在鍵值對的類中，應(yīng)該使用指針指向相應(yīng)的記錄，再將指針與關(guān)鍵碼關(guān)聯(lián)起來

關(guān)于二分查找的一點(diǎn)點(diǎn)小問題

實(shí)現(xiàn)有序字典的話，二分查找?guī)缀跏切枰氖褂眉寄芰恕?
在實(shí)現(xiàn)的過程中，我先按照自己的想法，實(shí)現(xiàn)如下：

/* 因?yàn)?find 函數(shù)被修飾成 const 了，并不能調(diào)用類中其他非 const 的 函數(shù)，即使類中有SList 成員，也不能調(diào)用 SList 成員的非const 函數(shù)。 這時(shí)候就需要用到指針，使用 SList 指針，就可以成功在 find 函數(shù)中調(diào) 用 SList 的非const成員函數(shù)了 */ E find(const Key& k) const {if(length()==0)return nullptr;int l = 0, r = length()-1, mid;while(l>=r){mid = l+(r-l)/2;//get(int) 會(huì)返回在mid處的值auto temp = get(mid);if(temp.key()>k)l = mid+1;else if(temp.key()<k)r = mid-1;elsebreak;}if(get(left).key()==k)return get(left).value();elsereturn nullptr; }

很明顯，我的代碼略長，實(shí)現(xiàn)也不算很完美，然后參考了書上的代碼 ，修改如下：

E find(const Key& k) const {int l = -1, r = length();while(l+1!=r){int i = l+(r-l)/2;auto temp = get(i);if(temp.key()>k) l = i;else if(temp.key()<k) r = i;else return temp.value();}return nullptr; }

簡潔明了，同時(shí)避免了需要增加判斷字典為空時(shí)的狀態(tài)

所有實(shí)現(xiàn)代碼均可以在本人github上找到：
xiaosa233
–END–

總結(jié)

以上是生活随笔為你收集整理的数据结构：字典的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。