第六章集合与字典.ppt

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

1、第六章 集合与字典,赵建华 南京大学计算机系,内容,集合及其表示 并查集与等价类 字典 跳表 散列,集合的基本概念,具有某种共同性质”的若干不同的对象合在一起构成集合。 在算法与数据结构中所遇到的集合中所有成员具有相同的数据类型。 例如： colour = red, orange, yellow, green, black, blue, purple, white ,一些说明,作为数据结构中的集合 在概念上讲，元素之间是无序的。 但是可能为了效率，在实现中将元素之间的某个序关系和元素的存储方式对应起来； 不同的表示方法： 保存实际数据值 保存下标或者reference 在父集中存放指示信息，表

2、示是否在子集合内。 允许相同元素多次出现的称为多重集合或者包。,集合的运算,还包括： 判断一个元素是否在集合中 集合是否为空 A是否为B的子集 以及添加/删除元素等操作 遍历所以元素 求满足某个条件的所有元素组成的子集,AB 或 A+B AB 或 AB A-B,A,A,A,B,B,B,集合（Set）的抽象数据类型,template class Set public: virtual Set() = 0; /构造函数 virtual makeEmpty() = 0; /置空集合 virtual bool addMember (const T x) = 0; virtual bool delMem

3、ber (const T x) = 0; virtual Set intersectWith (Set,集合的位向量实现,当集合是全集合 0,1,2,n 的一个子集，且n是不大的整数时，可用位(0,1)向量来实现集合。 对于每个i，有一个二进位；取值1或0分别表示在集合与不在集合中。 如果n小于32，可以直接用32位整数表示； 否则可以使用整数数组表示。 当全集合是由有限个可枚举的成员组成时，可建立全集合成员与整数0,1,2,的一一对应关系，然后用位向量来表示该集合的子集。 如果全集用数组表示，那么其子集也可以用位向量表示。但是，此时需要保证全集不改变。,位向量集合的类定义,#include

4、#include const int DefaultSize = 50; class bitSet /用位向量来存储集合元素, 集合元素的范围在0到 /setSize-1之间。数组采用16位无符号短整数实现 int setSize; /集合大小 int vecterSize; /位数组大小 unsigned short *bitVector; /bitVectori的第j位为0/1表示第i*16+j个元素是否在此集合内。,位向量集合的类定义（二）,public: bitSet (int sz = DefaultSize); /构造函数 bitSet (const bitSet /删除老成员x,

5、位向量集合的类定义（三）,bitSet /输出 ,构造函数的实现,bitSet:bitSet (int sz) : setSize (sz) /构造函数 assert (setSize 0); /检查参数的合理性 vectorSize = (setSize+15) /16; /vectorSize*16必须大于setSize bitVector = new int vectorSize; /分配空间 assert (bitVector != NULL); /检查存储分配是否成功 for (int i = 0; i vectorSize; i+) bitVectori = 0; /初始化为空集

6、;,复制构造函数,bitSet:bitSet (const bitSet,getMember,/判断x是否在这个集合中 int bitSet:getMember (const int x) int ad = x/16, id = x%16； /计算数组元素下标 unsigned short elem = bitVector ad; /取x所在数组元素 return int (elem (15-id) 注：第x个元素存放在bitVector的第x/16个元素的（从高位起）第x%16位上。,0,1,1,0,0,0,1,0,0,1,0,0,0,1,0,0,putMember,/如v为1，将x加入集合

7、；（如果x在集合中，操作无效果） /否则将x从集合中删除；（如果x不在集合中，操作无效果） void bitSet:putMember (const int x, int v) /将值v送入集合元素x int ad = x/16, id = x%16; /计算数组元素下标 unsigned short elem = bitVector ad; /取x所在数组元素 int temp = elem (15-id); /右移,该位移至末尾 elem = elem (id+1); /送回 ;,0,1,1,0,0,0,1,0,0,1,0,0,0,1,0,0,设：id=2；,右移后，temp为000000

8、0000000011 elem左移后为：0001001000100000,Add/delete member,bool bitSet:addMember (const int x) assert (x = 0 ,另一种实现位集合的方法,设立数组：bitArray16= 0x8000, 0x4000, 0x2000, 0x1000, 0x0800, 0x0400, 0x0200, 0x0100, 0x0080, 0x0040, 0x0020, 0x0010, 0x0008, 0x0004, 0x0002, 0x0001 判断bitVector的第i个元素的第j位是否为1 bitArrayj ,集

9、合的并运算,bitSet bitSet: /求集合this与R的并 operator + (const bitSet,集合的交运算,/求集合this与R的交 bitSet bitSet:operator * (const bitSet /按位求“与”, 由第三个集合返回 ,集合的差运算,/求集合this与R的差 bitSet bitSet:operator - (const bitSet,集合的并,集合的交,集合的差,集合的子集判断,/判this是否R的子集 bool bitSet:subSet (bitSet,判断集合相等,template bool bitSet:operator = (b

10、itSet,用有序链表实现集合,链表的每个结点存放集合的一个成员。 各结点所表示的成员 e0, e1, , en 在链表中按某种顺序排列，即 e0 e1 en。 有序链表可以表示无穷全集的子集，集合中的元素个数也没有限制； 本课程内使用带有表头结点的有序链表，也可以使用其它的链表形式。,集合的有序链表类的定义 （链表结点）,template struct SetNode /集合的结点类定义 T data; /每个成员的数据 SetNode *link; /链接指针 SetNode() : link (NULL); /构造函数 SetNode (const T 注意：可参照带表头的链表的实现方式

11、,集合的有序链表类的定义（链表）,template class LinkedSet /集合的类定义 private: SetNode *first, *last; /有序链表表头指针, 表尾指针 public: LinkedSet () first = last = new SetNode; LinkedSet (LinkedSet,加入一个元素的操作,template bool LinkedSet:addMember (const T,d1,d2,pre,data,s,插入时，必然有d1datad2,删除一个元素,template bool LinkedSet:delMember (cons

12、t T,集合的合并（1）,template LinkedSet LinkedSet: operator + (LinkedSet /end of else if (pa-data data) ，待续,集合的合并（2）,else /R集合元素值小 pc-link = new SetNode(pb-data); pb = pb-link; /end of else pc = pc-link; /扫尾处理 if (pa != NULL) p = pa; /this集合未扫完 else p = pb; /或R集合未扫完 while (p != NULL) /向结果链逐个复制 pc-link = new

13、 SetNode(p-data); pc = pc-link; p = p-link; /end of while pc-link = NULL; temp.last = pc; /链表收尾 return temp; ；,回忆一下以前的多项式合并算法： 1、一元多项式被表示成为不同次数的项的集合， 2、每个项包括系数、指数，且从小到大排列；,请考虑几个问题： 1、得到的集合仍然是从小到大排列吗？ 2、既在A中，又在B中的元素会重复出现在并集中吗？,集合并运算的例子,判断集合相等,bool LinkedSet: operator = (LinkedSet,内容,集合及其表示 并查集与等价类 字典

14、 跳表 散列,等价关系/等价类,若用符号“”表示集合上的等价关系，则对于该集合中的任意对象x, y, z，下列性质成立： 自反性：x x (即等于自身)。 对称性：若 x y, 则 y x。 传递性：若 x y且 y z, 则 x z。 从数学上看，等价类是对象（或成员）的集合，在一个等价类中的各个元素满足等价关系。 一个集合上的等价关系将该集合划分成为互不相交的子集。,并查集（disjoint set）,问题 高效地建立和表示某个集合上有一个等价关系 建立过程如下： 已知一个集合S，并且已知一个关系r。这个关系r通过一个二元组集合来表示； 等价关系R是r的自反/传递/对称闭包； 我们通过逐个

15、读入r中的二元组，高效建立起等价关系R。,用途,主要用于按照某些已知的等价关系事实，将一个集合中的元素分划成为互不相交的子集。 由已知事实推导出等价的两个元素一定在同一子集中。,等价关系建立的例子,给定集合 S = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 , 已知: 0 4, 3 1, 6 10, 8 9, 7 4, 6 8, 3 5, 2 11, 11 0 归并过程： 初始0,1,2,3,4,5,6,7,8,9,10,11 0 4 0,4,1,2,3,5,6,7,8,9,10,11 3 1 0,4,1,3,2,5,6,7,8,9,10,11 6 10 0,4

16、,1,3,2,5,6,10,7,8,9,11 8 9 0,4,1,3,2,5,6,10,7,8,9,11 7 4 0,4,7,1,3,2,5,6,10,8,9,11 6 8 0,4,7,1,3,2,5,6,8,9,10,11 3 5 0,4,7,1,3,5,2,6,8,9,10,11 2 11 0,4,7,1,3,5,2,11,6,8,9,10 11 0 0,2,4,7,11,1,3,5,6,8,9,10,并查集 (Union-Find Sets),并查集支持一个有穷集合上的某些操作 并查集支持以下三种操作： Union (Root1, Root2) /合并操作 Find (x) /查找操作

17、UFSets (s) /构造函数 对于并查集来说，分划的每个子集用一棵树表示。也可以用树的根结点来代表子集。 子树采用双亲表示法。 全集本身可以使用其它数据结构表示。这里我们使用数组表示，用下标指示元素。,S=0,1,2,3,4,5,6,7,8,9 S1= 0, 6, 7, 8, S2= 1, 4, 9, S3= 2, 3, 5,为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合。,0,1,2,3,4,5,6,7,8,9,4,4,3,2,3,2,0,0,0,4,初始时, 用构造函数 UFSets(s) 构造一个森林, 每棵树只有一个结点, 表示集合中各元素自成一个子集合。 Find(

18、i)：寻找集合元素 i所在子树的根。 Find(i) = Find(j)表明i和j在同一个子集中 Union(i, j)：将 i 和 j 所在的子集合并,S1,下标 parent,集合 S1, S2 和 S3 的双亲表示,-4 4 -3 2 -3 2 0 0 0 4,0 1 2 3 4 5 6 7 8 9,S2,S3,S1 S2的可能的表示方法,下标 parent,集合 S1 S2 和 S3 的双亲表示,-7 4 -3 2 0 2 0 0 0 4,0 1 2 3 4 5 6 7 8 9,0,7,6,8,4,1,9,4,1,9,0,8,7,6,-7,-7,0,0,0,0,4,4,4,4,4,0,

19、0,0,用双亲表示实现并查集的类定义,const int DefaultSize = 10; class UFSets /集合中的各个子集合互不相交 public: UFSets (int sz = DefaultSize); /构造函数 UFSets() delete parent; /析构函数 UFSets,UFSets:UFSets (int sz) /构造函数：sz 是集合元素个数，双亲数组的 /范围为parent0parentsize-1。 size = sz; /集合元素个数 parent = new intsize; /创建双亲数组 for (int i = 0; i size;

20、 i+) parenti = -1; /每个自成单元素集合 ;,并查集操作的算法 查找,-5,0,1,2,3,0,1,2,3,4,Find (4),Find (3),Find (2),Find (1),Find (0),-5 0 返回 0,int UFSets:Find (int x) /函数搜索并返回包含元素x的树的根。 /递归版本 if (parentx 0) return x; /根的parent值小于0 else return (Find (parentx); ;,Find的非递归版本,int UFSets:Find (int x) /函数搜索并返回包含元素x的树的根。 while (

21、parentx 0) x=parentx; return x; ;,这两个版本都有待改进,Union的实现,void UFSets:Union (int Root1, int Root2) /求两个不相交集合Root1与Root2的并 parentRoot1 += parentRoot2; /注意，root1和root2都是根结点 /-parentRoot1表示集合的元素总数 parentRoot2 = Root1; /将Root2连接到Root1下面 ;,下标 parent,-7 4 -3 2 0 2 0 0 0 4,0 1 2 3 4 5 6 7 8 9,0,7,6,8,4,1,9,-7,

22、0,0,0,0,4,4,下标 parent,-4 4 -3 2 -3 2 0 0 0 4,0 1 2 3 4 5 6 7 8 9,退化情况及其改进,Union操作可能引起退化情况： 假设最初 n 个元素构成 n 棵树组成的森林，parenti = -1。做处理Union(n-2, n-1), , Union(1, 2), Union(0, 1)后，将产生退化的树。 此时进行Find的话，平均需要n/2次查询。 改进的方法：尽量使得树变矮 按树的结点个数合并 按树的高度合并 压缩元素的路径长度,朴素合并,-1,-1,-1,-1,-1,0,2,3,4,-3,-5,0,3,2,1,3,3,4,1,3

23、,3,2,2,0,2,3,1,4,Union(0,1),-2,3,-4,1,4,2,1,2,3,4,Union(1,2),Union(2,3),Union(3,4),按树结点个数合并 结点个数多的树的根结点作根,-1,-1,-1,-1,-1,0,1,2,3,4,-1,-1,0,-7,2,5,6,-5,-2,2,2,3,3,2,0,1,3,4,5,6,2,3,3,0,2,0,5,6,2,3,1,4,Union(2, 0),void UFSets : WeightedUnion (int Root1, int Root2) /按Union的加权规则改进的算法 int temp = parentRo

24、ot1 + parentRoot2; if (parentRoot2 parentRoot1) parentRoot1 = Root2; /Root2中结点数多 parentRoot2 = temp; /Root1指向Root2 else parentRoot2 = Root1; /Root1中结点数多 parentRoot1 = temp; /Root2指向Root1 ;,按树高度合并 高度高的树的根结点作根,-1,-1,-1,-1,-1,0,1,2,3,4,-1,-1,0,-3,2,5,6,-3,-2,2,2,3,3,2,0,1,3,4,5,6,2,3,3,0,2,0,5,6,2,3,1,

25、4,Union(2, 0),按高度合并,注意：在根结点中记录高度，而不是元素个数。,void UFSets : WeightedUnion (int Root1, int Root2) /按Union的加权规则改进的算法，但是按照高度合并 if (parentRoot2 parentRoot1) parentRoot1 = Root2; /Root2更高，高度不变； else parentroot1 += (parentRoot2 = parentRoot1)?-1:0; /如果两棵树一样高，那么得到的树高度加1。 parentRoot2 = Root1; /Root1更高，或者一样高； ;,

26、Find操作的折叠规则,进一步改进性能，使用如下折叠规则来“压缩路径”。 即：如果 j 是从 i 到根的路径上的一个结点，且parentj rootj，则把 parentj 置为 rooti。,int UFSets:CollapsingFind (int i) /使用折叠规则的搜索算法 for (int j = i; parentj = 0; j = parentj); /让 j 循双亲指针走到根 while (parenti != j) /换 parenti 到 j int temp = parenti; parenti = j; i = temp; return j; ,实际例子,ML语言

27、的类型推理系统 是一个函数式语言。 ML语言不需要声明值的类型，且是强类型的。 通过合一的方法推导出各个值的类型。 x=head(l) 得出l是list类型，x是这个list类型的元素类型； m=tail(l)； 得出m和l的类型相同； y=x 得出y和x是相同的类型； y=2 得出y是整数类型，从而推导出x是整数类型；,内容,集合及其表示 并查集与等价类 字典 跳表 散列,字典（Dictionary）,字典是一些元素的集合，每个元素有一个称作关键码（key）的域，不同元素的关键码互不相同。 通常以文件（File）或者表格（Table）的方式出现。 在讨论字典抽象数据类型时，把字典定义为对的集

28、合。根据问题的不同，可以为名字和属性赋予不同的含义。 从抽象的角度看，字典是一个从名字（或者说Key）到属性的映射（MAP）。,字典的典型操作,确定一个指定的名字是否在字典中； 搜索出该名字的属性； 修改该名字的属性； 插入一个新的名字及其属性； 删除一个名字及其属性。,字典的抽象数据类型,const int DefaultSize = 26; template class Dictionary /对象: 一组对, 其中, 名字是唯一的 public: Dictionary (int size = DefaultSize); /构造函数 bool Member(Name name); /判na

29、me是否在字典中 Attribute *Search (Name name); /在字典中搜索关键码与name匹配的表项,字典的抽象数据类型（续）,void Insert (Name name, Attribute attr); /若name在字典中, 则修改相应对 /的attr项; 否则插入到字典中 void Remove (Name name); /若name在字典中, 则在字典中删除相应的 /对。否则无操作 ;,索引项,用文件记录（record）或表格的表项（entry）来表示单个元素时，可以使用 （key，记录或表项位置adr） 构成搜索某一指定记录或表项的索引项。 可以通过索引项提高

30、查找效率。,具有重复元素的字典,字典中的元素可以具有相同的关键码（Key）。 可能有多个元素具有相同的关键码， 需要制定规则消除歧义，使得Find, Remove可以无歧义地执行； 也可以Find/Remove所有的元素;,字典的线性表描述,保存在线性序列 (e1,e2,) 中，其中ei 是字典中的元素，其关键码从左到右依次增大。 可以使用有序链表（有序顺序表）结构； 每个结点表示字典中的一个元素 各个结点按照结点中保存的数据值非递减链接。,#include #include “SeqList.h” const int defaultSize = 50; template class Sort

31、edList : public SeqList public: int Search (K k1) const; /搜索 void Insert (const K k1, E,有序顺序表的类定义,基于有序顺序表的顺序搜索算法,template int SortedList:Search (K k1) const /顺序搜索关键码为x的数据对象 for (int i = 1; i k1) break; return 0; /顺序搜索失败, 返回失败信息 ; 算法中的“=”和“”都是重载函数，在定义E时定义它们的实现。,有序顺序表顺序搜索的时间代价,搜索算法的时间效率的衡量标准 在搜索过程中关键码

32、平均比较次数，也称为平均搜索长度ASL (Average Search Length)，通常它是字典中元素总数 n 的函数。 设搜索第 i 个元素的概率为 pi, 搜索到第 i 个元素所需比较次数为 ci, 则搜索成功的平均搜索长度：（只考虑了搜索成功的情况）,在顺序搜索情形，搜索第 i (1in) 个元素需要比较 i 次，假定按等概率搜索各元素： 这与一般顺序表情形相同。但搜索不成功时不需一直比较到表尾，只要发现下一个元素的值比给定值大，就可断定搜索不成功。,基于有序顺序表的折半搜索,设 n 个元素存放在一个有序顺序表中。 折半搜索时, 先求位于搜索区间正中的元素的下标mid，用其关键码与给

33、定值 x 比较: datamid.key = x，搜索成功； datamid.key x，把搜索区间缩小到表的前半部分，继续折半搜索； datamid.key x，把搜索区间缩小到表的后半部分，继续折半搜索。 如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败。,template int SortedList:BinarySearch (K k1, const int low, const int high ) const /折半搜索的递归算法，用到E的重载操作“” int mid = 0; /元素序号从1开始 if (low k1) mid = BinarySearch (k1

34、, low, mid -1); return mid; ; 注：这个递归算法是一个尾递归，可以转化为迭代,字典的有序链表实现,#include template struct ChainNode /链表结点类定义 E data; ChainNode *link; ChainNode() : link (NULL) ; /构造函数 ChainNode (E,template class SortedChain /有序链表类定义 private: ChainNode *first; /链表的头指针 public: SortedChain () /构造函数 first = new ChainNode

35、; assert (first != NULL); ; SortedChain (); /析构函数,ChainNode *Search (K k1); /搜索 void Insert (const K k1, E,搜索算法,template ChainNode *SortedChain: Search (const K k1) const ChainNode *p = first-link; while (p != NULL ,类似于前面讲过的用链表实现集合时，判断一个值x是否在集合中的方法,template void SortedChain:Insert (const K k1, E,插入算

36、法,类似于前面讲过的用链表实现集合时，在集合中加入一个值x的方法,template bool SortedChain: Remove (const K k1, E,类似于前面讲过的用链表实现集合时，在集合中删除一个值x的方法,散列表（Hash Table）,在元素存储位置与其关键码之间建立一个确定的对应函数关系 Hash()，即散列函数， 使得每个关键码与结构中某个唯一的存储位置相对应： Address Hash(key) 在插入时，依此函数计算存储位置并按此位置存放。 在搜索时对元素的关键码进行同样的计算，把求得的函数值当做元素存储位置，在结构中按此位置搜索。 通常多个Key对应于多个Add

37、ress。,优点： 不必进行多次关键码的比较, 搜索速度比较快, 可以直接到达或快速逼近具有此关键码的表项的实际存放地址。 散列冲突： 关键码集合比散列表地址集合大得多。因此必然会把某些不同的关键码映射到同一个散列地址上，这就产生了冲突。 这些散列地址相同的不同关键码被称为同义词。 冲突的例子： 有一组表项，其关键码分别是 12361, 07251, 03309, 30976 采用的散列函数是 hash(x) = x % 73 + 13420 则有 hash(12361) = hash(07250) = hash(03309) = hash(30976) = 13444。,由于关键码集合通常比

38、地址集合大得多, 冲突很难避免。 所以对于散列方法, 需要讨论以下两个问题： 对于给定的一个关键码集合，选择一个计算简单且地址分布比较均匀的散列函数，避免或尽量减少冲突； 解决冲突的方案。,被用于根据关键码计算得到存储地址 构造散列函数时的几点要求： 散列函数应是简单的，能在较短的时间内计算出结果。 散列函数的定义域必须包括需要存储的全部关键码；值域必须是存储地址的全集。 散列函数计算出来的地址应能均匀分布在整个地址空间中 : 若 key 是从关键码集合中随机抽取的一个关键码, 散列函数应能以同等概率取0 到 m-1 中的每一个值。,散列函数,直接定址法 取关键码的某个线性函数值作为散列地址：

39、 Hash(key) = a*key+b a, b为常数 这类散列函数是一对一的映射，一般不会产生冲突。 但它要求散列地址空间的大小与关键码集合的大小相同。,散列函数的例子（1）,示例：有一组关键码如下： 942148, 941269, 940527, 941630, 941805, 941558, 942047, 940001 。散列函数为 Hash(key) = key-940000 Hash (942148) = 2148 Hash (941269) = 1269 Hash (940527) = 527 Hash (941630) = 1630 Hash (941805) = 1805

40、Hash (941558) = 1558 Hash (942047) = 2047 Hash (940001) = 1 可以按计算出的地址存放记录。 但是要求数组的大小为最大key值-940000,散列函数的例子（2）,除留余数法 设散列表中允许地址数为m，取一个不大于 m，但最接近于或等于 m 的质数 p 作为除数，用以下函数把关键码转换成散列地址： hash (key) = key % p p m 要求这时的质数 p 不接近 2 的幂。 示例: 散列表大小 m = 25，p = 23。关键码962148的散列地址为 hash(962148) = 962148 % 23 = 12。 23、2

41、4 这几个地址实际上不能用散列函数计算出来，但是可以在处理冲突时达到这些地址。,数字分析法 设有 n 个 d 位数, 每一位可能有 r 种不同的符号。这 r 种不同符号在各位上出现的频率不一定相同。根据散列表的大小, 选取其中各种符号分布均匀的若干位作为散列地址。 计算各位数字中符号分布均匀度k的公式： 其中， 表示第 i 个符号在第 k 位上出现的次数，n/r 表示各种符号在 n 个数中均匀出现的期望值。,计算出的 k 值越小，表明在该位 (第 k 位) 各种符号分布得越均匀。 9 4 2 1 4 8 位， 1 = 57.60 9 4 1 2 6 9 位， 2 = 57.60 9 4 0 5

42、 2 7 位， 3 = 17.60 9 4 1 6 3 0 位， 4 = 5.60 9 4 1 8 0 5 位， 5 = 5.60 9 4 1 5 5 8 位， 6 = 5.60 9 4 2 0 4 7 9 4 0 0 0 1 ,若散列表地址范围有 3 位数字, 取各关键码的 位做为记录的散列地址。 数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。,平方取中法 它首先计算构成关键码的标识符的内码的平方, 然后按照散列表的大小取中间的若干位作为散列地址。 设标识符可以用一个计算机字长的内码表示。因为内码平方数的

43、中间几位一般是由标识符所有字符决定, 所以对不同的标识符计算出的散列地址大多不相同。 在平方取中法中, 一般取散列地址为2的某次幂。例如, 若散列地址总数取为 m = 8r，则对内码的平方数取中间的 r 位。,标识符的八进制内码表示及其平方值和散列地址,折叠法 此方法把关键码自左到右分成位数相等的几部分, 每一部分的位数应与散列表地址位数相同, 只有最后一部分的位数可以短一些。 把这些部分的数据叠加起来, 就可以得到具有该关键码的记录的散列地址。 有两种叠加方法： 移位法：把各部分最后一位对齐相加； 分界法：各部分不折断，沿各部分的分界来回折叠, 然后对齐相加。,示例: 设给定的关键码为 ke

44、y = 23938587841, 若存储空间限定 3 位, 则划分结果为每段 3 位。 上述关键码可划分为 4 段： 239 385 878 41 把超出地址位数的最高位删去, 仅保留最低的3 位，做为可用的散列地址。,移 位 法,385,878,41,1543,41,239,239,385,878,1714,分 界 法,一般当关键码的位数很多，而且关键码每一位上数字的分布大致比较均匀时，可用这种方法得到散列地址。 假设地址空间为HT400，利用以上函数计算，取其中3位，取值范围在0999，可能超出地址空间范围，为此必须将0999压缩到0399。可将计算出的地址乘以一个压缩因子0.4，把计算出

45、的地址压缩到允许范围。,散列冲突的处理,任何散列函数都不能避免产生冲突，因此好的解决冲突的方法十分重要。 对散列表的假定 若设散列表HT有 m 个地址, 将其看作 m 个桶。第 i (0i =1)个表项, 这些表项的关键码互为同义词。 两个不同表项的关键码用散列函数计算得到同一个散列地址，即产生冲突. 它们被放在同一个桶内。当同存放不下时，就需要解决冲突。,闭散列也叫做开地址法。 所有的桶都直接放在散列表数组中。每个桶只有一个表项 ( s = 1 )。 冲突的解决方法： 若设散列表中各桶的编址为 0 到 m-1, 当要加入一个表项 R2 时, 通过散列函数 hash (R2.key) 计算得到

46、的桶号 j中已经有另一个表项，就需要把 R2 存放到表中“下一个”空桶中。 寻找下一个空桶的方法 线性探查法 二次探查法 双散列法,闭散列方法（开地址法）,需要搜索或加入一个表项时，首先使用散列函数计算桶号作为初始地址： H0 = hash (key) 一旦发生冲突，在表中顺次向后寻找“下一 个”空桶 Hi 的递推公式为： Hi = (Hi-1+1) % m， i =1, 2, , m-1 即用以下的线性探查序列在表中寻找“下一 个”空桶的桶号： H0+1, H0 +2, , m-1, 0, 1, 2, , H0-1 亦可写成如下的通项公式： Hi = (H0 + i) % m， i =1, 2, , m-1 当发生冲突时探查下一个桶。 当循环 m-1次后就会回到开始探查时的位置，说明待查关键码不在表内且表已满，不能再插入新关键码。,线性探查法 (Linear Probing),散列中的元素的删除： 假设一个元素的Hash值是