算法与数据结构(c语言)第6章集合与字典.ppt

第六章 集合与字典,从逻辑结构上看，集合和字典都是最简单的数据结构，它们的元素之间没有任何确定的依赖关系。字典是关联的集合。作为抽象数据类型，集合和字典之间的主要区别，在于它们的操作。集合主要考虑集合之间的并、交和差操作；字典主要关心其元素的检索、插入和删除。,目录,6.1集合及其抽象数据类型 基本概念 主要运算 抽象数据类型6.2集合的实现 集合的位向量表示 集合的单链表表示6.3字典及其抽象数据类型 基本概念 抽象数据类型,6.4字典的顺序表示 存储结构 算法的实现 有序顺序表 与二分法检索6.5字典的散列表示 基本概念 散列函数 碰撞的处理 散列文件,6.1 集合及其抽象数据类型6.1.1 基本概念,集合是数学中最基本的概念，也是一种基本数据结构。在数学中，集合是一些互不相同元素的无序汇集。这些元素称为该集合的成员。集合中的成员可以是一个原子（不可再分解）；也可以是一个结构，甚至又是一个集合。集合中的各个元素应该是互不相同的。,列举法:定义一个有穷集，可以将成员放在一对花括号中，成员之间用逗号隔开。例如，2，谓词描述法:集合的大小:集合中所包含的元素的个数。空集 子集 超集 数据结构中讨论的集合，一般有以下限制：1）数据结构讨论的集合总限制为有穷集；2）假定集合中所有元素属同一类型；并且假设元素之间存在一个小于关系“”，也称为有序集。,6.1.2 主要运算,集合也可以定义测试一个元素是否存在于集合中、增加一个元素、删除一个元素等运算，但集合更加关心下面的一些运算。求并集：求交集：求差集：子集：A是B的子集如果集合A是B的子集，反过来也称集合B是A的超集。相等：例如：若，则有，。另外，不等于，同时和相互都不是子集关系。,上面集合间的运算，都可以通过增加元素、删除元素和成员测试等运算来实现。,例如：已知集合A和B，求它们的并集，只要以集合A（或B）为基础，把集合B（或A）的元素逐个插入。如果要求两个集合的交集，只要从A（或B）出发，检查各元素是否在B（或A）中出现，把那些也在另一个集合里出现的元素插入（初态为空集）的集合中即可。求A与B的差集AB时，只要以A为基础，对每个B中的元素做删除运算即可。,6.1.3 抽象数据类型,ADT Set isoperationsSet createEmptySet(void)创建一个空集合。int member（Set，DataType）当时返回真值，否则取假值。int insert（Set，DataType）使作为的一个成员,如果本来就是的成员，则不变。,int delete（Set，DataType）将从中删除，如果本来就不在中，则不改变。int union（Set，Set，Set）求集合和的并集，结果在集合中。int intersection（Set，Set，Set）求集合和的交集，结果在集合中。int difference（Set，Set，Set）求集合和的差集，结果在集合中。int subset（Set，Set）当且仅当是的子集时，函数值才为真。end ADT Set,6.2 集合的实现,位向量表示 单链表表示,6.2.1 位向量表示,位向量是一种每个元素都是二进制位（即0/1值）的数组。当表示的集合存在某个不太大的公共超集时，采用位向量的方式来表示这种集合往往十分有效。,假设需要表示的集合的公共超集中，共有个不同的元素，为叙述的方便，不妨假设这些元素就是整数0，-1等。每个集合可以采用一个有位的位向量来表示。若整数是这个集合的一个元素，则位向量中对应的位为（真），否则为0（假）。,存储结构,由于在C语言中无法直接定义位数组，要定义位向量，需要借助其它方式。一种比较自然的方式，是用长度为n/8的字符数组表示长度为n的字位数组。一个字符用8位二进制编码，它实际上包含了8个二进制位。,位向量表示集合的存储结构：typedef struct int size;/*字符数组的长度*/char*array;/*位向量空间。每一数组元素保存8位。*/BitSet;,下图给出了一个公共超集是从0到9的整数集合，采用位向量表示的存储结构示意图。从图中可以看出每个整数所对应的二进制位的位置。当集合S=1,3,5,7,9时,它的实际存储状态如图（b）所示(注意其中元素的排列方法)。用位向量表示集合时，所占空间的大小与公共超集的大小成正比，而与要表示的集合的大小无关。,算法实现,以位向量表示集合，只有两个集合都是某个公共集合的子集时，它们互相运算才是有效的。由于在位向量定义里并没有关于集合元素的实际信息，只能要求参与运算的两个位向量长度相同。,位运算,假设x和y都是8位的字符，其值分别是：X=01010111Y=11011010。对x和y做各种字位运算，得到的结果如下：x 10101000 x&y 01010010 x y 10001101x|y 11011111x 5 00000110,空集合的创建 与空顺序表的的创建类似，不同之处在于这里省略了每个集合中实际元素个数的变量:BitSet*createEmptySet(int n)将整数index的元素插入集合 将值为index的元素插入集合S的过程，通过将位向量中下标为index的位置为1来完成：int insert(BitSet*s,int index),将整数index的元素从集合中删除 通过将位向量中下标为index的位置为0来完成：int delete(BitSet*s,int index)判断整数index的元素是否属于集合 通过判断位向量中下标为index的位是否为1来完成：int member(BitSet*s,int index),集合与集合的并利用按位的“或”运算实现:int union(BitSet*s0,BitSet*s1,BitSet*s2)集合与集合的交 这个运算很容易通过位“与”操作实现。int intersection(BitSet*s0,BitSet*s1,BitSet*s2),集合与集合的差 将第一个集合与第二个集合的逆做与运算，就可以达到这个目的。int difference(BitSet*s0,BitSet*s1,BitSet*s2),6.2.2 单链表表示,链接表示方式下，在链表中存放的是集合中元素的实际数值，而不是元素是否属于集合的标记。,存储结构,链表中的每个结点表示集合中的一个元素，具体方式与第二章单链表的结点struct Node类似。不同之处在于：线性表的单链表中，link字段表示线性表元素之间的逻辑后继关系，而在这里仅仅是把属于同一集合的所有元素链接成一个整体。因为我们讨论的是有序集，如果将集合中的所有元素按“”关系排序构造有序链表，给集合的某些运算会带来方便。,struct Node;typedef struct Node*PNode;struct Node DataType info;PNode link;typedef struct Node*LinkSet;,集合0，1，2，n-1采用带表头结点的有序链表表示时，如图所示：,求单链表表示集合的交集,int intersectionLink(LinkSet s0,LinkSet s1,LinkSet s2）在有序链表表示的集合中，在s1中找到第一个与s0中相同元素后，其它共同元素不需要从头开始比较，只要从刚才比较成功所结束的位置继续向后检索。因此，只要用两个指针，沿s0和s1从头至尾扫描一遍即可完成。当这两个表的长度为和时，算法的时间总花费最多为（）。程序实现,算法实现,集合的赋值 int assignLink(LinkSet s0,LinkSet s1)赋值运算将集合s0拷贝成集合s1，注意这一运算不能简单地将s0的表头结点置成s1的表头结点，因为若这样处理，则对s1的改变将会带来s0的改变。程序实现,插入运算 int insertLink(LinkSet s0,DataType x)插入运算首先要找到适当的插入位置，它有两个参数：一个是被插入元素的信息x；另一个则是被插入的集合s0。程序实现,6.3 字典及其抽象数据类型 基本概念,字典是一种集合，其中每个元素由两部分组成，分别称为关键码和属性(或称为值)。这种包含关键码和属性的二元组称作关联(Association)。抽象地看，一个关联是一个有序对，它可以看成是由关键码值k到属性(值)v的一个对应。字典就是由关键码集合到值集合的二元关系。字典中的元素之间能够根据其关键码进行比较大小，对字典元素的插入、删除和检索等操作一般也以关键码为依据进行。,在实践中使用较多的字典里所有的关键码互不相同，这种关键码具有唯一性的字典，在数学中称为映射(mapping)，数据结构里讲的就是这种字典。字典关心的最主要的运算是检索。衡量一个字典检索算法效率的主要标准是检索过程中对关键码的平均比较次数：以及算法的空间开销、算法是否易于理解等因素。,6.3.2 抽象数据类型,假设用Dictionary表示抽象数据类型字典，用DicElement表示字典元素类型，用KeyType 来表示元素中关键码的类型，用Position表示字典中元素的位置。,ADT Dictionary isoperationsDictionary createEmptyDictionary(void)创建一个空字典。int search(Dictionary dic,KeyType key,Position p)在字典dic中检索关键码为key的关联的位置p。int insert(Dictionary dic,DicElement ele)在字典dic中插入关联ele。int delete(Dictionary dic,KeyType key)在字典dic中删除关键码为key的关联。end ADT Dictionary,6.4 字典的顺序表示 6.4.1 存储结构,从逻辑结构出发，字典中的元素是无序的，但为了实现的方便，可以把字典中的元素按关键码的大小组织成一个顺序表。,typedef intKeyType;typedef intDataType;typedef struct KeyType key;/*字典元素的关键码字段*/DataType value;/*字典元素的属性字段*/DicElement;typedef struct int MAXNUM;/*字典中元素的个数上界*/int n;/*为字典中实际元素的个数*/DicElement*element.;/*存放字典中的元素*/SeqDictionary;,6.4.2 算法的实现,检索的基本思想是从字典的一端开始顺序扫描，将字典中元素的关键码和给定值比较，如果相等，则检索成功；当扫描结束时，还未找到关键码等于给定值的元素，则检索失败。这称为顺序检索算法。程序实现：int seqSearch(SeqDictionary*pdic,KeyType key,int*position),在不考虑检索失败的情况下，顺序检索的平均检索长度为:ASL=1P1+2P2+nPn 假设每个元素的检索概率相等，即Pi=1/n，则平均检索长度为 ASL=（1+n）/2。成功检索的平均比较次数约为字典长度的一半。若字典中不存在关键码为key的元素，则需进行n次比较。检索时间为O(n)。,算法代价,顺序检索的优点是算法简单且适应面广。无论字典中元素是否有序均可使用。缺点是平均检索长度较大，特别是当n很大时，检索效率较低。一般情况下，字典中各元素的检索概率不相等。则当P1P2Pn时，平均检索长度最小。因此，如果已知各元素的检索概率，则应将字典中元素按检索概率由大到小排序，以便提高检索效率。,讨论,6.4.3 有序顺序表与二分法检索,一种提高检索效率的方法是将字典元素按关键码递增(或者递减)的顺序排序，这种按照关键码大小排序的顺序表称为有序顺序表。对于有序顺序表，可以还采用顺序检索的方法进行查找，当检索到元素的关键码大于(或者小于)给定值时，就可以返回检索失败的信息。下面介绍的另外一种检索方法，称为二分法检索，是专门为有序顺序表设计的。,二分法检索又称折半检索，是一种效率较高的检索方法，使用这种方法检索时，要求字典的元素在顺序表中按关键码排序。基本思想：首先将给定值key与数组中间位置上元素的关键码比较，如果相等，则检索成功；否则，若key小，则在数组前半部分中继续进行二分法检索，否则在数组后半部分中继续进行二分法检索。这样，经过一次比较就缩小一半的查找区间，如此进行下去，直到能够确定检索成功或检索失败为止。int binarySearch(SeqDictionary*pdic,KeyType key,int*position),二分法检索,分析二分法检索每经过一次比较就将检索范围缩小一半，第i次比较可能比较的元素个数如下表比较次数 可能比较的元素个数 1 1=20 2 2=21 3 4=22 j 2j-1若字典元素个数n刚好为20+21+2j-1=2j-1则最大检索长度为j；若2j-1n2j+1-1，则最大检索长度为j+1。所以，二分法检索的最大检索长度为。,设检索每个元素的概率相同，则平均检索长度为(设字典元素个数n=2j-1),6.5 字典的散列表示最大优点是：在散列表示的字典中执行元素的检索运算平均可能达到常数的时间。6.5.1 基本概念,散列法（hashing）又称为杂凑法或关键码地址转换法。它的基本思想是：选择一个从关键码到地址的映射函数h(称为散列函数)，对于每个关键码为key的元素，计算出h(key)，期望把对应的元素存储到h(key)指示的地址(称为散列地址)上。如果两个不相等的关键码key1和key2，用散列函数h计算得到相同的散列地址(即h(key1)=h(key2)，这种现象称为碰撞。发生碰撞的两个(或多个)关键码称为同义词(相对于函数h而言)。为了实现散列法必须解决同义词的存储问题。,散列函数h的定义域应该是所有关键码的集合，h(key)的值域应该是可以使用的整个地址空间，称为基本区域。发生碰撞时，同义词可以存放在基本区域中未被占用的单元，也可以放到基本区域以外另开辟的区域(称溢出区)。下面引入散列法的一个重要概念负载因子()，其定义为 显然，当1时碰撞就不可避免。,主要应解决两个问题：一个是根据字典中元素的特点，选择适当的散列函数，使得散列地址的分布尽可能均匀地分布在基本区域之中；另一个是根据存储空间的条件，设计具体的处理（同义词）碰撞的方法。用散列法表示的字典称为散列表（hash table）。,字典的散列表示,6.5.2 散列函数,散列函数也称杂凑函数。一般而言，散列函数的选取应根据具体问题具体分析的原则，针对具体字典元素关键码集合的特性，加上用户的需求和空间、时间的条件，去构造相对理想的散列函数。使散列函数计算出的地址尽可能均匀地分布在希望的地址空间中。同时，为了提高关键码到地址的转换速度，散列函数应该尽可能简单。,数字分析法,常常有这样的情况，关键码位数比基本区的地址码位数多，这时可以对关键码的各位进行分析，丢掉分布不均匀的位留下均匀的位作为地址。key h(key)000319426326000718309709000629443643000758615715000919697997000310329329,折叠法,如果关键码的位数比地址位数多，且各位分布较均匀，不适于用数字分析法，则可以考虑折叠法。折叠法将关键码从某些地方断开，分为几部分，其中最大部分的长度等于地址码的长度，再加上其余部分，舍弃进位。例如关键码为key=582422241，要求转换为4位的地址码。下面两种折叠方法都是可行的：,58|2422|241 58|2422|241 移位折叠相加 移位相加 8 5 5 8 1 4 2 2 4 1 2 4 2 2 2 4 2 2 1 1 0 6 4 2 7 2 1h1(key)=1064,h2(key)=2721,中平方法,先求出关键码的平方，然后取中间几位作为地址。例如：关键码key=4731，47312=22382361。如果地址长度为3位，则可以取第三位到第五位作为散列地址，即有h1(4731)=382，当然也可以取46位，即有h2(4731)=823。,把关键码看作是另一个进制的表示，然后再转换成原来进制的数，最后用数字分析法取其中几位作为散列地址。一般转换基数大于原基数，且两个基数最好互素。例如key=(236075)10是十进制数，把它看作十三进制数(236075)13，再转换成十进制数(236075)13=2135+3134+6133+713+5=(841547)10然后参考其它关键码的分布和地址空间大小，通过数字分析法，选择其中几位。假设选择了第二位到第五位，则h(236075)=4154。,基数转换法,选择一个适当的正整数P，用P去除关键码，余数作为散列地址，即h(key)=key%P。这个方法的关键是选取适当的P。一般P为不大于基本区域长度m的最大素数比较好。例如m=8,16,32,64,128,256,512,1024可以取：p=7,13,31,61,127,251,503,1019除余法地址计算公式非常简单。但是对于动态字典和关键码没有规律出现的情况，经常采用。,除余法,6.5.3 碰撞的处理-开地址法、拉链法,设给定一个元素，其关键码为key，首先使用选择的散列函数h,计算出散列地址h(key)。如何执行插入?如何执行检索?,碰撞的处理方法一：开地址法,在基本区域内形成一个同义词的探查序列，沿着探查序列逐个查找，直到找到查找的元素或碰到一个未被占用的地址为止。若插入元素，则碰到空的地址单元就存放要插入的同义词。若检索元素，则需要碰到空的地址单元后，才能说明表中没有待查的元素(检索失败)。采用开地址法解决碰撞，是在基本区域内存放同义词，负载因子必须小于1，否则，一定有些元素无处存放。负载因子越小，碰撞的可能性越小，查找速度越快，当然空间开销也越大。,产生探查序列的最简单方法是线性探查，即将基本存储区看作一个循环表。若在地址为d=h(key)的单元发生碰撞，则依次探查下述地址单元d+1,d+2,m-1,0,1,d-1(m为基本存储区的长度)直到找到一个空单元或查找到关键码为key的元素为止。如果从单元d开始探查，查找一遍后，又回到地址d，则表示基本存储区已经溢出。,例子：已知关键码集合K=18，73，10，5，68，99，27，41，51，32，25，设散列表基本区域用数组element表示，大小为m(m=13)，散列函数为h(key)=key%13，用线性探查法解决碰撞。按散列函数d=key%13计算每个元素的散列地址如下：h(18)=5,h(73)=8,h(10)=10,h(5)=5,h(68)=3,h(99)=8 h(27)=1,h(41)=2,h(51)=12,h(32)=6,h(25)=12最后的散列表为：,存储结构,typedef intKeyType;typedef intDataType;typedef struct KeyType key;/*字典元素的关键码字段*/DataType value;/*字典元素的属性字段*/DicElement;typedef struct int m;/*m为基本区域长度*/DicElement*element;HashDictionary;/*DicElement是字典中元素类型*/,算法创建空散列表,PHashDictionary createEmptyDictionary(int m)创建空散列表的实现与算法2.1类似,主要差别在于m在这里代替了MAXNUM的作用;另外,后面算法中假设所有有效的关键码都是大于0的整数，所以当创建一个空字典时，所有元素的关键码初始化为一个不可能作为关键码的整数值0。程序实现,int linearSearch(HashDictionary*phash,KeyType key,int*position)在检索算法中，返回1表示检索成功，*position为找到的元素在散列表中element数组元素的下标值；返回0表示检索失败，这时如果散列表中还有可插入的空间，则*position给出合适的插入位置，否则*position中为1。程序实现,检索算法,int linearInsert(HashDictionary*phash,DicElememt ele)在插入算法中，首先调用检索算法，如果检索失败，再根据提供的位置信息将元素ele插入。程序实现,插入算法,堆积问题,在上例中，h(32)=6，h(5)=5，32和5不是同义词，但是在解决5与18的碰撞时，5已经存入element6，使得在插入32时，32与5本来不冲突的两个非同义词之间发生了碰撞。用线性探查法解决碰撞时，两个同义词子表结合在一起的现象称为堆积。为了减少堆积的产生，可以改进线性探查方法，使探查序列跳跃式地分布在表中,下面介绍的双散列函数法可以提供参考。根本的减少堆积现象的方法是适当增加基本区域的空间。,双散列函数法,双散列函数法要选择两个散列函数h1和h2，它们均以关键码为自变量，h1产生一个0到m-1之间的数作为散列地址。h2产生一个1到m-1之间的并和m互素的数作为对地址的增量。要求产生的数与m互素是为了使得到的存储地址探查序列能够分布在整个基本区域内。例如两个散列函数可以为h1(key)=key%m和h2(key)=key%(m-2)+1。如果d=h1(key)发生碰撞，则再计算h2(key)，得到探查序列为(d+h2(key)%m,(d+2h2(key)%m,(d+3h2(key)%m,碰撞的处理方法二：拉链法,设基本区域长度为m，使用拉链法需要建立m条链表，所有散列地址相同的元素存放在同一条链表中。设给定字典元素的关键码为key，首先根据散列函数h计算出h(key)，即确定是在第h(key)条链表中，然后在该链表中进行插入、删除及检索操作。已知关键码集合K=18，73，10，5，68，99，27，41，51，32，25，m取13，设散列函数为h(key)=key%13，用拉链法得到的散列表如下图所示。,6.5.4 散列文件,读写文件时，为了节省外存的存取时间，需尽量减少访外的次数。减少访外次数的有效方法是精心设计文件的结构，使每次访外能够存取更多应用程序中需要的逻辑记录的信息。散列文件是一种存储在外存的大型字典的存储结构，它把前面介绍的散列表的思想用于外存之上。通过散列函数作用到记录的关键码，来确定记录在外存的存储地址，在处理同义词时，常常使用适合外存分块存取的拉链法。下面介绍一种常见的构造散列文件的方法：按桶散列。,基本思想,按桶散列的文件由若干桶和一个桶目录表构成。一个桶由0个或多个外存的页块通过指针的链接而构成。散列函数值相同的记录存放在同一个桶里。桶目录表是一些指针的序列，通常存储在内存中，每个指针指向一个桶的首页块。如果有个桶，其编号为至-，有些桶可能是空桶，空桶在桶目录表中对应一个空指针。下页图表示一个按桶散列的文件结构示意图。设给定字典元素的关键码为key，首先根据散列函数h计算出h(key)，即是该记录所在的桶号，然后在该桶中进行插入、删除及检索操作。,文件的操作,检索：要查找关键码值为key的记录，首先计算（key）。设（key），查阅桶目录表的第项，得到第个桶的首页块地址，读入首页块，在块上进行顺序查找。找到关键码为key的记录则结束，否则根据块之间的链指针读入下一块，继续查找，直到找到或者找遍全桶时结束。,插入：要插入关键码为key的记录，先按上述方法进行查找。找到时，说明本次插入是错误的或多余的。若找不到，则此时读到内存中的页块恰好是新记录应插入的桶的最后一块。在这个页块的空位置上填入新记录，并写回外存。如果此页块已满，则申请一个新页块，其地址填入前一块的指针位置，在新页块上填入新记录并把指针置空，然后把两个页块都写回外存。,桶数的选择和扩充,在设计按桶散列时，桶的多少要适当。太少时使桶中的页块较多，存取时增大访外次数。太多时会造成浪费。主要的浪费在那些不空的但只存放很少几个记录的桶，它们各自占用一个页块但只利用其一小部分。桶的数目，可以按下述经验的方法设定：使桶数与文件所能填满的页块数大致相等。即,若文件有个记录，每个页块能容纳个记录，则取桶数B.按照这种取法,如果散列函数不太糟,则大多数桶中不超过个页块。检索时平均只需要次访外，同时，每个页块中平均放入的记录数能使空间利用率达到半满的程度。,散列文件在初建时，往往难以准确地估计其大小。随着文件的不断插入，我们可能发现各个桶中的页块太多了，检索效率严重下降。此时可以对桶数来一次扩充。为此，必须重新构造整个散列文件。具体方法可以是：创建一个桶数较多的新散列文件，并相应地定义新的散列函数；把旧文件每个桶中的记录逐个散列到新文件上，同时归还旧文件所占的页块。设文件有个记录，则插入新文件的访外次数为*，其中是在新文件中插入一个记录的平均访外次数()。,小结,从逻辑结构上看，集合和字典属于两种最简单的数据结构，它们的元素之间没有任何确定的依赖关系。然而，正是这个原因，使得在具体表示集合和字典时，可以选择多种不同的存储结构。字典是关联的集合，它与一般集合的主要区别在于它们的操作。具体地讲，集合主要考虑不同集合之间的并、交和差操作；而字典强调其元素的检索。,集合的实现方法很多，当讨论的集合都是某个更大的公共超集的子集，并且这个公共超集不很大时，可以采用位向量的方式来表示。集合也可以用链接方式来表示，链表中的每个结点表示集合中的一个元素。将集合中的所有元素排序，可以提高集合的某些运算的效率。,字典的每个元素是一个二元组：分别称为关键码和属性，这种二元组称作关联。字典就是以关联为元素的集合。本章介绍了字典顺序表示和顺序检索；有序顺序表表示和二分法检索；各种散列表示（例如：开地址法、拉链法等）和检索等。本章还介绍了散列法，包括基本思想和一些常用的散列函数，以及，解决碰撞问题的两种方法：开地址法和拉链法。散列文件把散列表的思想用于外存之上。,