字典(dictionary)是一些元素的集合。每個元素有一個稱作key 的域,不同元素的key 各不相同。有關字典的操作有:插入具有給定關鍵字值的元素、在字典中尋找具有給定關鍵字值的元素、刪除具有給定關鍵字值的元素。
基本介紹
- 中文名:字典
- 外文名:dictionary
- 實質 : 一些元素的集合
- 操作:插入元素、尋找元素、刪除元素
- 訪問方式: 隨機訪問、順序訪問
- 套用學科:計算機科學、測繪科學、控制科學
抽象數據類型描述
重複元素字典
套用實例
學生成績
符號表
線性表描述
類定義
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(); // 不存在相匹配的元素}