-
字典
(數據結構中元素的集合)
鎖定
字典(dictionary)是一些元素的集合。每個元素有一個稱作key 的域,不同元素的key 各不相同。有關字典的操作有:插入具有給定關鍵字值的元素、在字典中尋找具有給定關鍵字值的元素、刪除具有給定關鍵字值的元素。
- 中文名
- 字典
- 外文名
- dictionary
- 實質
- 一些元素的集合
- 操 作
- 插入元素、尋找元素、刪除元素
- 訪問方式
- 隨機訪問、順序訪問
- 應用學科
- 計算機科學、測繪科學、控制科學
目錄
字典抽象數據類型描述
抽象數據類型Dictionary的描述如下所示。若僅按照一個字典元素本身的關鍵字來訪問該元素,則稱為隨機訪問(random access)。而順序訪問(sequential access)是指按照關鍵字的遞增順序逐個訪問字典中的元素。順序訪問需藉助於Begin (用來返回關鍵字最小的元素)和Next (用來返回下一個元素)等操作來實現。
抽象數據類型Dictionary {
實例
具有不同關鍵字的元素集合
操作
Create( ):創建一個空字典
Search(k, x):搜索關鍵字為k的元素,結果放入x;
如果沒找到,則返回f a l s e,否則返回t r u e
Insert (x):向字典中插入元素x
Delete (k, x):刪除關鍵字為k的元素,並將其放入x
字典重複元素字典
有重複元素的字典(dictionary with duplicates)與上面定義的字典相似,只是它允許多個
元素有相同的關鍵字。在有重複元素的字典中,在進行搜索和刪除時需要一個規則來消除岐義。也就是説,如果要搜索(或刪除)關鍵字為k的元素,在有些字典應用中,可能需要刪除在某個時間以後插入的所有元素。
[1]
字典應用實例
字典學生成績
一個班中註冊學習數據結構課程的學生構成了一個字典。當有一個新學生註冊時,就要在字典中插入與該學生相關的元素(記錄)。當有人要放棄這門課程時,則刪除他的記錄。在上課過程中,老師可以查詢字典以得到與某特定學生相關的記錄或修改記錄(例如,加入或修改考試成績)。學生的姓名域可作為關鍵字。
字典符號表
在編譯器中定義用户描述符的符號表(symbol table)就是一個有重複元素的字典。當定義一個描述符時,要建立一個記錄並插入到符號表中。記錄中包括作為關鍵字的描述符以及其他信息,如描述符類型( i n t,float等)和(相關的)存儲其值的內存地址。因為同樣的描述符名可以定義多次(在不同的程序塊中),所以符號表中必然存在有多個記錄具有相同的關鍵字,搜索結果應是最新插入的元素。只有在程序塊的結尾才能進行刪除,所有在開始插入的元素最終都要被刪除掉。
[1]
字典線性表描述
字典可以保存在線性序列(e1, e2,⋯)中,其中ei是字典中的元素,其關鍵字從左到右依次增大。為了適應這種描述方式,可以定義兩個類SortedList和Sorted Chain。前者採用公式化描述的線性表,如Linear List類,而後者則採用鏈表描述,如Chain類。
[1]
字典類定義
template<class E ,class K> class SortedChain{ public : SortedChain() {first =0;} ~ SortedChain( ) ; bool IsEmpty() const {return first ==0;} int Length() const; bool Search(const K& k , E& e) const; SortedChain<E ,K>& Delete(const K& k , E& e); SortedChain<E ,K>& Insert(const E& e); SortedChain<E ,K>& DistinctInsert(const E& e); private: SortedChainNode<E ,K> *first; } ;
字典成員函數search
template<class E, class K> bool SortedChain<E,K>::Search(const K& k, E& e) const {// 搜索與k匹配的元素,結果放入e // 如果沒有匹配的元素,則返回f a l s e SortedChainNode<E,K> *p = first; // 搜索與k相匹配的元素 for (; p && p->data < k; p = p->link); // 驗證是否與k匹配 if (p && p->data == k) // 與k相匹配 {e = p->data; return true;} return false; // 不存在相匹配的元素 }
字典成員函數delete
template<class E, class K> SortedChain<E,K>& SortedChain<E,K>::Delete(const K& k, E& e) {// 刪除與k相匹配的元素 // 並將被刪除的元素放入e // 如果不存在匹配元素,則引發異常BadInput SortedChainNode<E,K> *p = first, *tp = 0; //跟蹤p // 搜索與k相匹配的元素 for (; p && p->data < k; tp = p; p = p->link; } // 驗證是否與k匹配 if (p && p->data == k) {// 找到一個相匹配的元素 e = p->data; // 保存d a t a域 // 從鏈表中刪除p所指向的元素 if (tp) tp->link = p->link; else first = p->link; // p是鏈首節點 delete p; return *this;} throw BadInput(); // 不存在相匹配的元素 }