第6章集合与字典.ppt

《第6章集合与字典.ppt》由会员分享，可在线阅读，更多相关《第6章集合与字典.ppt（46页珍藏版）》请在三一文库上搜索。

1、第六章 集合与字典 n从逻辑结构上看，集合和字典都是最简单的数据 结构，它们的元素之间没有任何确定的依赖关系 。字典是关联的集合。 n作为抽象数据类型，集合和字典之间的主要区别 ，在于它们的操作。 n集合主要考虑集合之间的并、交和差操作；字典 主要关心其元素的检索、插入和删除。 6.1 集合及其抽象数据类型 6.1.1 基本概念 n数学中集合是一些互不相同元素的无序汇集。这些元素称为 该集合的成员。集合中的成员可以是一个原子（不可再分解 ）；也可以是一个结构，甚至又是一个集合。集合中的各个 元素应该是互不相同的。 n元素是或不是集合A的成员，可表示为 n列举法：定义一个有穷集，可以将成员放在一

2、对花括号中， 成员之间用逗号隔开。 例如，2， n谓词描述法: n集合的大小: 集合中所包含的元素的个数。 n空集不包含任何元素的集合，记作。 n数据结构中讨论的集合，一般有以下限制：数据结构讨论的 集合总限制为有穷集；假定集合中所有元素属同一类型；并 且假设元素之间存在一个小于关系“”，也称为有序集。 6.1.2 主要运算 n集合可以定义测试一个元素是否存在于集合中、增加一个元 素、删除一个元素等运算，但集合更加关心下面的一些运算 。 n求并集： n求交集： n求差集： n子集： A是B的子集 n如果集合A是B的子集，反过来也称集合B是A的超集。 n相等：两个集合互为子集，则称它们相等。 n

3、例如：若，则有 ， ，。另外，不等于，同时和相互都不是子集关 系。 ADT Set is operations Set createEmptySet ( void ) 创建一个空集合。 int member（Set ，DataType ） 当时返回真值，否则取假值。 int insert（Set ，DataType ） 使作为的一个成员,如果本来就是的成员，则不变。 int delete（Set ，DataType ） 将从中删除，如果本来就不在中，则不改变。 int union（Set ，Set ，Set ） 求集合和的并集，结果在集合中。 int intersection （Set ，Se

4、t ，Set ） 求集合和的交集，结果在集合中。 int difference（Set ，Set ，Set ） 求集合和的差集，结果在集合中。 int subset（Set ，Set ） 当且仅当是的子集时，函数值才为真。 end ADT Set 6.1.3 抽象数据类型 6.2 集合的实现 6.2.1 位向量表示 n在实际应用中的许多集合，往往都存在一个公认的超集。例 如，ASCII码字符集是各种算机能够表示的字符集的超集；所 有大小写英文字母的集合是各种字母集合的超集。 n 对于字母集合，如果按集合中每个字符的ASCII码将它们存储 到一个字符数组中，则集合将占用较多的存储空间（最多需 要

5、8*26*2=416bit）。 n如果英文字母超集中的每个字母对应1-56中的一个数值，则字 母集可以表示为一个有52个分量的向量，每个分量的1或0表 示相应数值的字母是否在该集合中。这样每个字母集合只占 用很少的存储空间（52bit）。 n位向量是一种每个元素都是二进制位（即0/1值）的数组。当 表示的集合存在某个不太大的公共超集时，采用位向量的方 式来表示这种集合往往十分有效。 存储结构 n假设需要表示的集合的公共超集中，共有个不同的元素 ，为叙述的方便，不妨假设这些元素就是整数0， ，-1等。 n每个集合可以采用一个有位的位向量来表示。若整数 是这个集合的一个元素，则位向量中对应的位为（

6、真） ，否则为0（假）。 n由于C语言中无法直接定义位数组，要定义位向量需要借助 其它方式。一种比较自然的方式，是用长度为n/8的字符数 组表示长度为n的字位数组。一个字符用8位二进制编码， 它实际上包含了8个二进制位。 typedef struct int size;/字符数组的长度 char * array; /位向量空间。每一数组元素保存8位。 BitSet; n假设n是为向量的位数，因为n不一定是8的整数倍，所以由 表达式（n+7）/8计算出来的是能保证容纳下所有的位向量 的最少字节数。 n为了便于操作的实现，位向量的下标在字符的8位中应该从 右至左递增排列。 n如图给出了公共超集从0

7、到9的整数集合采用位向量表示的 存储结构示意图，以及集合S=1,3,5,7,9的实际存储。 n当用位向量表示集合时，所占空间的大小与公共超集的大 小成正比，而与要表示的集合的大小无关。 算法实现 n以位向量表示集合，只有两个集合都是某个公共 集合的子集时，它们互相运算才是有效的。由于 在位向量定义里并没有关于集合元素的实际信息 ，只能要求参与运算的两个位向量长度相同。 n位运算 n假设x和y都是8位的字符，其值分别是： X= 01010111 Y= 11011010 对x和y做各种字位运算，得到的结果如下： nx 10101000 nx typedef struct Node *PNode;

8、struct Node DataType info; PNode link; ; typedef struct Node *LinkSet; 集合0，1，2，n-1采用带表头结点的有序链表表示 ： n求单链表表示集合的交集 int intersectionLink (LinkSet s0,LinkSet s1,LinkSet s2） 在有序链表表示的集合中，在s1中找到第一个与s0 中相同元素后，其它共同元素不需要从头开始比较 ，只要从刚才比较成功所结束的位置继续向后检索 。 因此，只要用两个指针，沿s0和s1从头至尾扫描一 遍即可完成。当这两个表的长度为和时， 算法的时间总花费最多为（）。

9、程序实现 算法实现 n集合的赋值 int assignLink (LinkSet s0,LinkSet s1) 赋值运算将集合s0拷贝成集合s1，注意这一运算不能简单 地将s0的表头结点置成s1的表头结点，因为若这样处理， 则对s1的改变将会带来s0的改变。 程序实现 n插入运算 int insertLink (LinkSet s0,DataType x) 插入运算首先要找到适当的插入位置，它有两个参数：一 个是被插入元素的信息x；另一个则是被插入的集合s0。 程序实现 6.3 字典及其抽象数据类型 6.3.1基本概念 n字典是一种集合，其中每个元素由两部分组成，分别称为关键码 和属性(或称为

10、值)。这种包含关键码和属性的二元组称作关联 (Association)。 n抽象地看，一个关联是一个有序对，它可以看成是由关键码值k 到属性(值)v的一个对应。字典就是由关键码集合到值集合的二元 关系。 n字典中的元素之间能够根据其关键码进行比较大小，对字典元素 的插入、删除和检索等操作一般也以关键码为依据进行。如英文 字典。 n在实践中使用较多的字典里所有的关键码互不相同，这种关键码 具有唯一性的字典，在数学中称为映射(mapping)，数据结构里讲 的就是这种字典。 n字典关心的最主要的运算是检索。衡量一个字典检索算法效率的 主要标准是检索过程中对关键码的平均比较次数以及算法的空间 开销、

11、算法是否易于理解等因素。平均比较次数 6.3.2 抽象数据类型 n假设用Dictionary表示抽象数据类型字典，用DicElement表 示字典元素类型，用KeyType 来表示元素中关键码的类型 ，用Position表示字典中元素的位置。 ADT Dictionary is operations Dictionary createEmptyDictionary ( void ) 创建一个空字典。 int search(Dictionary dic, KeyType key, Position p) 在字典dic中检索关键码为key的关联的位置p。 int insert(Dictionary

12、 dic, DicElement ele) 在字典dic中插入关联ele。 int delete(Dictionary dic, KeyType key) 在字典dic中删除关键码为key的关联。 end ADT Dictionary 6.4 字典的顺序表示 6.4.1 存储结构 n从逻辑结构出发，字典中的元素是无序的，但为了实现的 方便，可以把字典中的元素按关键码的大小组织成一个顺 序表。 typedef intKeyType; typedef intDataType; typedef struct KeyType key;/字典元素的关键码字段 DataType value; / 字典元素

13、的属性字段 DicElement; typedef struct int MAXNUM ; /字典中元素的个数上界 int n;/为字典中实际元素的个数 DicElement *element.; /存放字典中的元素 SeqDictionary; 6.4.2 算法的实现 n检索的基本思想是从字典的一端开始顺序扫描，将字典中元 素的关键码和给定值比较，如果相等，则检索成功；当扫描 结束时，还未找到关键码等于给定值的元素，则检索失败。 这称为顺序检索算法。 int seqSearch(SeqDictionary * pdic, KeyType key, int * position) n在不考虑检

14、索失败的情况下，顺序检索的平均检索长度为: ASL=1P1+2P2+nPn n假设每个元素的检索概率相等，即Pi=1/n，则平均检索长度 为 ASL=（1+n）/2。 n成功检索的平均比较次数约为字典长度的一半。若字典中不 存在关键码为key的元素，则需进行n次比较。检索时间为O(n) 。 n顺序检索的优点是算法简单且适应面广。无论字典中元素是 否有序均可使用。缺点是平均检索长度较大，特别是当n很大 时，检索效率较低。 n一般情况下，字典中各元素的检索概率不相等。则当 P1P2Pn时，平均检索长度最小。 n因此，如果已知各元素的检索概率，则应将字典中元素按检 索概率由大到小排序，以便提高检索效

15、率。 6.4.3 有序顺序表与二分法检索 n一种提高检索效率的方法是将字典元素按关 键码递增(或者递减)的顺序排序，这种按照 关键码大小排序的顺序表称为有序顺序表。 n对于有序顺序表，可还采用顺序检索的方法 进行查找，当检索到元素的关键码大于(或者 小于)给定值时，就可以返回检索失败的信息 。 n二分法检索是专门为有序顺序表设计的一种 检索方法。 二分法检索 n二分法检索又称折半检索，是一种效率较高的检 索方法，使用这种方法检索时，要求字典的元素 在顺序表中按关键码排序。 n基本思想：首先将给定值key与数组中间位置上元 素的关键码比较，如果相等，则检索成功；否则 ，若key小，则在数组前半部

16、分中继续进行二分法 检索，否则在数组后半部分中继续进行二分法检 索。这样，经过一次比较就缩小一半的查找区间 ，如此进行下去，直到能够确定检索成功或检索 失败为止。 int binarySearch(SeqDictionary * pdic, KeyType key, int *position) 分析 n二分法检索每经过一次比较就将检索范围缩 小一半，第i次比较可能比较的元素数如下表: 比较次数 可能比较的元素个数 1 1=20 2 2=21 3 4=22 j 2j-1 n若字典元素个数n刚好为20+21+2j-1=2j-1则 最大检索长度为j； n若2j-11时碰撞就不可避免。 n用散列法表

17、示的字典称为散列表（hash table）。主要应解 决两个问题： n一个是根据字典中元素的特点，选择适当的散列函数，使得散列地 址的分布尽可能均匀地分布在基本区域之中； n一个是根据存储空间的条件，设计具体的处理（同义词）碰撞的方 法。 6.5.2 散列函数 n散列函数也称杂凑函数。要提高散列表的 检索效率，散列函数的选取是关键。 n一般而言，散列函数的选取应根据具体问 题具体分析的原则，针对具体字典元素关 键码集合的特性，加上用户的需求和空间 、时间的条件，去构造相对理想的散列函 数。使散列函数计算出的地址尽可能均匀 地分布在希望的地址空间中。 n同时，为了提高关键码到地址的转换速度 ，散

18、列函数应该尽可能简单。 n数字分析法 常常有这样的情况，关键码位数比基本区的地址 码位数多，这时可以对关键码的各位进行分析， 丢掉分布不均匀的位留下均匀的位作为地址。 key h(key) 000319426326 000718309709 000629443643 000758615715 000919697997 000310329329 n折叠法 n如果关键码的位数比地址位数多，且各位分布较均 匀，不适于用数字分析法，则可以考虑折叠法。 n折叠法将关键码从某些地方断开，分为几部分，其 中最大部分的长度等于地址码的长度，再加上其余 部分，舍弃进位。 n例如关键码为key=582422241

19、，要求转换为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 1 h1(key)=1064, h2(key)=2721, n中平方法 n先求出关键码的平方，然后取中间几位作为地址。 n例如：关键码key=4731，47312=22382361。如果地址长度为 3位，则可以取第三位到第五位作为散列地址，即有 h1(4731)=382，当然也可以取46位，即有h2(4731)= 823。 n基数转换法 n把关键码

20、看作是另一个进制的表示，然后再转换成原来进 制的数，最后用数字分析法取其中几位作为散列地址。一 般转换基数大于原基数，且两个基数最好互素。 n例如key=(236075)10是十进制数，把它看作十三进制数 (236075)13，再转换成十进制数 (236075)13=2135+3134+6133+713+5 =(841547)10 n然后参考其它关键码的分布和地址空间大小，通过数字分 析法，选择其中几位。假设选择了第二位到第五位，则 h(236075)=4154。 除余法 n选择一个适当的正整数P，用P去除关键码，余数 作为散列地址，即h(key)=key%P。这个方法的关 键是选取适当的P。

21、 n一般P为不大于基本区域长度m的最大素数比较好 。 例如m=8,16,32,64,128,256,512,1024 可以取：p=7,13,31,61,127,251,503,1019 n除余法地址计算公式非常简单。但是对于动态字 典和关键码没有规律出现的情况，经常采用。 6.5.3 碰撞的处理-开地址法、拉链法 n设给定一个元素，其关键码为key，首先使 用选择的散列函数h,计算出散列地址h(key) 。 n如何执行插入? n如何执行检索? n散列法要解决碰撞的问题：开地址法和拉 链法 n在基本区域内形成一个同义词的探查序列，沿着探查序 列逐个查找，直到找到查找的元素或碰到一个未被占用 的地

22、址为止。若插入元素，则碰到空的地址单元就存放 要插入的同义词。若检索元素，则需要碰到空的地址单 元后，才能说明表中没有待查的元素(检索失败)。 n采用开地址法解决碰撞，是在基本区域内存放同义词， 负载因子必须小于1，否则，一定有些元素无处存放。负 载因子越小，碰撞的可能性越小，查找速度越快，当然 空间开销也越大。 n产生探查序列的最简单方法是线性探查，即将基本存储 区看作一个循环表。若在地址为d=h(key)的单元发生碰撞 ，则依次探查下述地址单元d+1,d+2,m-1,0,1,d-1 (m 为基本存储区的长度)。直到找到一个空单元或查找到关 键码为key的元素为止。如果从单元d开始探查，查找

23、一遍 后，又回到地址d，则表示基本存储区已经溢出。 碰撞的处理方法一：开地址法 n已知关键码集合K=18，73，10，5，68，99，27， 41，51，32，25，设散列表基本区域用数组element 表示，大小为m(m=13)，散列函数h(key)=key%13， 用线性探查法解决碰撞。 n按散列函数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 n最后的散列表为： 线性探查法例子 typedef in

24、tKeyType; typedef intDataType; typedef struct KeyType key;/* 字典元素的关键码字段*/ DataType value;/* 字典元素的属性字段*/ DicElement; typedef struct int m;/* m为基本区域长度 */ DicElement *element; HashDictionary; /*DicElement是字典中元素类型*/ 存储结构 算法 n创建空散列表 PHashDictionary createEmptyDictionary (int m ) 创建空散列表的实现与算法2.1类似,主要差别在于m

25、在这里代 替了MAXNUM的作用;另外,后面算法中假设所有有效的关键 码都是大于0的整数，所以当创建一个空字典时，所有元素的 关键码初始化为一个不可能作为关键码的整数值0。程序实现 n检索算法 int linearSearch(HashDictionary * phash, KeyType key, int *position) 在检索算法中，返回1表示检索成功，*position为找到的元素 在散列表中element数组元素的下标值；返回0表示检索失败， 这时如果散列表中还有可插入的空间，则*position给出合适的 插入位置，否则*position中为1。 n插入算法 int linea

26、rInsert(HashDictionary *phash, DicElememt ele) 在插入算法中，首先调用检索算法，如果检索失败，再根据 提供的位置信息将元素ele插入。 n在上例中，h(32)=6，h(5)=5，32和5不是同义 词，但是在解决5与18的碰撞时，5已经存入 element6，使得在插入32时，32与5本来不冲 突的两个非同义词之间发生了碰撞。用线性 探查法解决碰撞时，两个同义词子表结合在 一起的现象称为堆积。 n为了减少堆积的产生，可以改进线性探查方 法，使探查序列跳跃式地分布在表中。下面 介绍的双散列函数法可以提供参考。 n根本的减少堆积现象的方法是适当增加基本

27、区域的空间。 堆积问题 节点的删除 n开地址法构造散列标，删除节点时，不能简单地 将要删除的节点空间设置为初始状态0，因为0的 关键码是检索失败的依据，这样删除一个节点会 破坏已经建立的同义词链接关系，从而影响其他 节点的检索（删除多个同义词的前面关键词时， 导致后面的无法检索）。 n只能在被删除的节点上作标记（如将关键码改为 负值），不能真正删除。 n多次删除后形式上散列表是满的，但实际却很空 ，为了重新利用这些已经删除的节点空间，可改 进插入算法：插入时利用做了删除标记的地址空 间。 双散列函数法 n双散列函数法要选择两个散列函数h1和h2，它们均以关键码 为自变量，h1产生一个0到m-1

28、之间的数作为散列地址。h2产 生一个1到m-1之间的且和m互素的数作为对地址的增量。要 求产生的数与m互素是为了使得到的存储地址探查序列能够 分布在整个基本区域内。 n例如，当 基本区域的长度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, n已知关键码集合K=18,73,10,5,68,99,27,41,51,32,25,用双散列 函数法解决碰撞。设散列表基本区域用数组element表

29、示，大 小为m(m=13)，则h1(key)=key%13， h2(key)= key%11+1 。 碰撞的处理方法二：拉链法 n设基本区域长度为m，使用拉链 法需要建立m条链表，所有散列 地址相同的元素存放在同一条链 表中。 n设给定字典元素的关键码为key ，首先根据散列函数h计算出 h(key)，即确定是在第h(key)条链 表中，然后在该链表中进行插入 、删除及检索操作。 n已知关键码集合K=18，73，10 ，5，68，99，27，41，51，32， 25，m取13，设散列函数为 h(key)=key%13，用拉链法得到的 散列表如图所示。 n适用于散列表长度无法确定的情 况；不会导

30、致堆积，检索较快， 且节点删除方便。 6.5.4 散列文件 读写文件时，为了节省外存的存取时间，需尽量减少 访外的次数。减少访外次数的有效方法是精心设计文 件的结构，使每次访外能够存取更多应用程序中需要 的逻辑记录的信息。 散列文件是一种存储在外存的大型字典的存储结构， 它把前面介绍的散列表的思想用于外存之上。通过散 列函数作用到记录的关键码，来确定记录在外存的存 储地址，在处理同义词时，常常使用适合外存分块存 取的拉链法。 下面介绍一种常见的构造散列文件的方法：按桶散列 。 n基本思想 按桶散列的文件由若干桶和一个桶目录表构成。一个 桶由0个或多个外存的页块通过指针的链接而构成。散 列函数值

31、相同的记录存放在同一个桶里。桶目录表是一 些指针的序列，通常存储在内存中，每个指针指向一个 桶的首页块。 如果有个桶，其编号为至-，有些桶可能是 空桶，空桶在桶目录表中对应一个空指针。下页图表示 一个按桶散列的文件结构示意图。 设给定字典元素的关键码为key，首先根据散列函数 h计算出h(key)，即是该记录所在的桶号，然后在该桶中 进行插入、删除及检索操作。 n文件的操作 检索： 要查找关键码值为key的记录，首先计算 （key）。设（key），查阅桶目录表的第 项，得到第个桶的首页块地址，读入首页块，在 块上进行顺序查找。找到关键码为key的记录则结束 ，否则根据块之间的链指针读入下一块，

32、继续查找 ，直到找到或者找遍全桶时结束。 插入：要插入关键码为key的记录，先按上述方 法进行查找。找到时，说明本次插入是错误的或 多余的。若找不到，则此时读到内存中的页块恰 好是新记录应插入的桶的最后一块。在这个页块 的空位置上填入新记录，并写回外存。如果此页 块已满，则申请一个新页块，其地址填入前一块 的指针位置，在新页块上填入新记录并把指针置 空，然后把两个页块都写回外存。 n桶数的选择和扩充 在设计按桶散列时，桶的多少要适当。太少时使桶中 的页块较多，存取时增大访外次数。太多时会造成浪 费。主要的浪费在那些不空的但只存放很少几个记录 的桶，它们各自占用一个页块但只利用其一小部分。 桶的

33、数目，可以按下述经验的方法设定：使桶数与文 件所能填满的页块数大致相等。即,若文件有个记录 ，每个页块能容纳个记录，则取桶数B.按照 这种取法,如果散列函数不太糟,则大多数桶中不超过 个页块。检索时平均只需要次访外，同时，每 个页块中平均放入的记录数能使空间利用率达到半满 的程度。 散列文件在初建时，往往难以准确地估计其大小。随 着文件的不断插入，我们可能发现各个桶中的页块太 多了，检索效率严重下降。此时可以对桶数来一次扩 充。 为此，必须重新构造整个散列文件。具体方法可以是 ：创建一个桶数较多的新散列文件，并相应地定义新 的散列函数；把旧文件每个桶中的记录逐个散列到新 文件上，同时归还旧文件

34、所占的页块。 设文件有个记录，则插入新文件的访外次数为* ，其中是在新文件中插入一个记录的平均访外次 数()。 小结 n从逻辑结构上看，集合和字典属于两种最简单的数 据结构，它们的元素之间没有任何确定的依赖关系 。然而，正是这个原因，使得在具体表示集合和字 典时，可以选择多种不同的存储结构。 n字典是关联的集合，它与一般集合的主要区别在于 它们的操作。具体地讲，集合主要考虑不同集合之 间的并、交和差操作；而字典强调其元素的检索。 n集合的实现方法很多，当讨论的集合都是某个更大 的公共超集的子集，并且这个公共超集不很大时， 可以采用位向量的方式来表示。集合也可以用链接 方式来表示，链表中的每个结点表示集合中的一个 元素。将集合中的所有元素排序，可以提高集合的 某些运算的效率。 n字典的每个元素是一个二元组：分别称为 关键码和属性，这种二元组称作关联。字 典就是以关联为元素的集合。本章介绍了 字典顺序表示和顺序检索；有序顺序表表 示和二分法检索；各种散列表示（例如： 开地址法、拉链法等）和检索等。 n本章还介绍了散列法，包括基本思想和一 些常用的散列函数，以及，解决碰撞问题 的两种方法：开地址法和拉链法。散列文 件把散列表的思想用于外存之上。