《【6】集合、字典与散列》由会员分享，可在线阅读，更多相关《【6】集合、字典与散列（105页珍藏版）》请在金锄头文库上搜索。
1、数据结构,2013年秋季,第六章 集合与字典,本章教学内容,集合 字典 搜索（Search）概述 散列方法 散列函数构造方法 冲突解决方法 散列应用,集合及其表示,集合是成员(元素)的一个群集。集合中的成员可以是原子(单元素)，也可以是集合。 集合的成员必须互不相同。 在算法与数据结构中所遇到的集合，其单元素通常是整数、字符、字符串或指针，且同一集合中所有成员具有相同的数据类型。 例：colour = red, orange, yellow, green, black, blue, purple, white ,集合基本概念,集合中的成员一般是无序的，但在表示它时，常写在一个序列里。 常设定集
2、合中的单元素具有线性有序关系，此关系可记作“”，表示“优先于”。 整数、字符和串都有一个自然线性顺序。指针也可依据其在序列中安排的位置给予一个线性顺序。 在某些集合中保存实际数据值，某些集合中保存标示元素是否在集合中的指示信息。如学校开设的所有课程的编码属于前者，一个学期开设的课程构成的集合属于后者。,template class Set public:virtual Set() = 0; /构造函数virtual makeEmpty() = 0; /置空集合virtual bool addMember (const T x) = 0;virtual bool delMember (const
3、 T x) = 0;virtual Set intersectWith (Set,集合（Set）的抽象数据类型,用位向量实现集合抽象数据类型,当集合是全集合 0, 1, 2, , n 的一个子集，且 n 是不大的整数时，可用位(0, 1)向量来实现集合。 当全集合是由有限个可枚举的成员组成时，可建立全集合成员与整数 0, 1, 2, 的一一对应关系，用位向量来表示该集合的子集。 一个二进位两个取值1或0，分别表示在集合与不在集合。如果采用16位无符号短整数数组bitVector 作为集合的存储，就要考虑如何求出元素 i 在bitVector数组中的相应位置。,集合的位向量(bit Vector
4、)类的定义,#include #include const int DefaultSize = 50; class bitSet /用位向量来存储集合元素, 集合元素的范围在0到 /setSize-1之间。数组采用16位无符号短整数实现 public:bitSet (int sz = DefaultSize); /构造函数bitSet (const bitSet /取集合元素x,void putMember (const T x, int v); /改集合元素xvoid makeEmpty () /置空集合for (int i = 0; i /判x是否集合this的成员,bool subSet
5、 (bitSet,使用示例,Set s1, s2, s3, s4, s5; int index, equal; for (int k = 0; k 10; k+) /集合赋值s1.AddMember (k);s2.AddMember(k+7); /s1: 0, 1, 2, , 9, s2: 7, 8, 9, , 16s3 = s1+s2; /求s1与s2的并 0, 1, , 16s4 = s1*s2; /求s1与s2的交 7, 8, 9 s5 = s1-s2; /求s1与s2的差 0, 1, , 6,/s1: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9index = s1.Sub
6、Set (s4); /判断s1是否为s4子集cout index endl; /结果，index = 0/s1: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9/s4: 7, 8, 9equal = s1 = s2; /集合s1与s2比较相等cout equal 0); /检查参数的合理性vectorSize = (setSize+15) 4; /存储数组大小bitVector = new int vectorSize; /分配空间assert (bitVector != NULL); /检查存储分配是否成功for (int i = 0; i (16-id) % 1);/取第id位的
7、值 ;,template void bitSet:putMember (const T x, int v) /将值v送入集合元素xint ad = x/16, id = x%16; /计算数组元素下标unsigned short elem = bitVector ad;/取x所在数组元素int temp = elem (16-id); /右移,该位移至末尾if (temp%2 = 0 ,template bool bitSet:addMember (const T x) assert (x = 0 ,if (getMember(x) = 1) putMember(x, 0);return tr
8、ue;return false; ;template bitSet bitSet: /求集合this与R的并 operator + (const bitSet,for (int i = 0; i bitSet bitSet: /求集合this与R的交 operator * (const bitSet,template bitSet bitSet: /求集合this与R的差 operator - (const bitSet,集合的并,集合的交,集合的差,template bool bitSet:subSet (bitSet,template bool bitSet:operator = (bit
9、Set,用带表头结点的有序链表表示集合,用有序链表实现集合抽象数据类型,用有序链表来表示集合时，链表中的每个结点表示集合的一个成员。 各结点所表示的成员 e0, e1, , en 在链表中按升序排列，即 e0 e1 link = new SetNode(pb-data);pb = pb-link;pc = pc-link;if (pa != NULL) p = pa; /this集合未扫完else p = pb; /或R集合未扫完while (p != NULL) /向结果链逐个复制pc-link = new SetNode(p-data);pc = pc-link; p = p-link;p
10、c-link = NULL; temp.last = pc; /链表收尾return temp; ；,bool LinkedSet: operator = (LinkedSet,字典（Dictionary）,字典是一种特殊的集合，其元素是（关键字，属性值）二元组； 关键字必须是互不相同的（在一个字典之内）； 字典的主要操作是依据关键字来存储和析取值，可用于组织简单的数据库，提供存储、查找和删除记录的功能； 字典的实现方式很多，如有序线性表、跳表、字符树等； 用散列方法实现的字典具有非常高效的检索性能。,字典是一些元素的集合。每个元素有一个称作key（关键字）的域，不同元素的key各不相同。,字
11、典的抽象数据类型,const int DefaultSize = 26; template class Dictionary /对象: 一组对, 其中, 名字是唯一的 public:Dictionary (int size = DefaultSize); /构造函数bool Member (Name name);/判name是否在字典中Attribute *Search (Name name); /在字典中搜索关键码与name匹配的表项 void Insert (Name name, Attribute attr); /若name在字典中, 则修改相应对/的attr项; 否则插入到字典中voi
12、d Remove (Name name);/若name在字典中, 则在字典中删除相应的/对 ;,用文件记录（record）或表格的表项（entry）来表示单个元素时，用：（关键码key，记录或表项位置指针adr） 构成搜索某一指定记录或表项的索引项。,字典的线性表描述,字典可以保存在线性序列 (e1,e2,) 中，其中ei 是字典中的元素，其关键码从左到右依次增大。为了适应这种描述方式，可以定义有序顺序表和有序链表。 用有序链表来表示字典时，链表中的每个结点表示字典中的一个元素，各个结点按照结点中保存的数据值非递减链接，即e1e2 。因此，在一个有序链表中寻找一个指定元素时，一般不用搜索整个链表。,#include #include “SeqList.h” const int defaultSize = 50; template class SortedList : public SeqList public:int Search (K k1) const; /搜索void Insert (const K k1, E,
