字典

字典（dictionary）是一些元素的集合。每个元素有一个称作key 的域，不同元素的key 各不相同。有关字典的操作有：插入具有给定关键字值的元素、在字典中寻找具有给定关键字值的元素、删除具有给定关键字值的元素。

抽象数据类型描述抽象数据类型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

}1

重复元素字典有重复元素的字典（dictionary with duplicates）与上面定义的字典相似，只是它允许多个

元素有相同的关键字。在有重复元素的字典中，在进行搜索和删除时需要一个规则来消除岐义。也就是说，如果要搜索(或删除)关键字为k的元素，在有些字典应用中，可能需要删除在某个时间以后插入的所有元素。1

应用实例学生成绩一个班中注册学习数据结构课程的学生构成了一个字典。当有一个新学生注册时，就要在字典中插入与该学生相关的元素(记录)。当有人要放弃这门课程时，则删除他的记录。在上课过程中，老师可以查询字典以得到与某特定学生相关的记录或修改记录(例如，加入或修改考试成绩)。学生的姓名域可作为关键字。

符号表在编译器中定义用户描述符的符号表（symbol table）就是一个有重复元素的字典。当定义一个描述符时，要建立一个记录并插入到符号表中。记录中包括作为关键字的描述符以及其他信息，如描述符类型( i n t，float等)和(相关的)存储其值的内存地址。因为同样的描述符名可以定义多次(在不同的程序块中)，所以符号表中必然存在有多个记录具有相同的关键字，搜索结果应是最新插入的元素。只有在程序块的结尾才能进行删除，所有在开始插入的元素最终都要被删除掉。1

线性表描述字典可以保存在线性序列(e1, e2,⋯)中，其中ei是字典中的元素，其关键字从左到右依次增大。为了适应这种描述方式，可以定义两个类SortedList和Sorted Chain。前者采用公式化描述的线性表，如Linear List类，而后者则采用链表描述，如Chain类。1

类定义templateclass SortedChain{public : SortedChain() {first =0;} ~ SortedChain( ) ; bool IsEmpty() const {return first ==0;} int Length() const; bool Search(const K& k , E& e) const; SortedChain& Delete(const K& k , E& e); SortedChain& Insert(const E& e); SortedChain& DistinctInsert(const E& e);private: SortedChainNode *first;} ;成员函数searchtemplatebool SortedChain::Search(const K& k, E& e) const{// 搜索与k匹配的元素，结果放入e// 如果没有匹配的元素，则返回f a l s e SortedChainNode *p = first;// 搜索与k相匹配的元素 for (; p && p->data link);// 验证是否与k匹配 if (p && p->data == k) // 与k相匹配 {e = p->data; return true;} return false; // 不存在相匹配的元素}成员函数deletetemplateSortedChain& SortedChain::Delete(const K& k, E& e){// 删除与k相匹配的元素// 并将被删除的元素放入e// 如果不存在匹配元素，则引发异常BadInput SortedChainNode *p = first, *tp = 0; //跟踪p// 搜索与k相匹配的元素 for (; p && p->data 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(); // 不存在相匹配的元素}本词条内容贡献者为:

王伟 - 副教授 - 上海交通大学