《集合与字典》PPT课件.ppt

第六章 集合与字典,赵建华南京大学计算机系,内容,集合及其表示并查集与等价类字典跳表散列,集合的基本概念,具有某种共同性质”的若干不同的对象合在一起构成集合。在算法与数据结构中所遇到的集合中所有成员具有相同的数据类型。例如：colour=red,orange,yellow,green,black,blue,purple,white,一些说明,作为数据结构中的集合在概念上讲，元素之间是无序的。但是可能为了效率，在实现中将元素之间的某个序关系和元素的存储方式对应起来；不同的表示方法：保存实际数据值保存下标或者reference在父集中存放指示信息，表示是否在子集合内。允许相同元素多次出现的称为多重集合或者包。,集合的运算,还包括：判断一个元素是否在集合中集合是否为空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 delMember(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#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,位向量集合的类定义（三）,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;/初始化为空集;,复制构造函数,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加入集合；（如果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为0000000000000011elem左移后为：0001001000100000,Add/delete member,bool bitSet:addMember(const int x)assert(x=0,另一种实现位集合的方法,设立数组：bitArray16=0 x8000,0 x4000,0 x2000,0 x1000,0 x0800,0 x0400,0 x0200,0 x0100,0 x0080,0 x0040,0 x0020,0 x0010,0 x0008,0 x0004,0 x0002,0 x0001判断bitVector的第i个元素的第j位是否为1bitArrayj,集合的并运算,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=(bitSet,用有序链表实现集合,链表的每个结点存放集合的一个成员。各结点所表示的成员 e0,e1,en 在链表中按某种顺序排列，即 e0 e1 en。有序链表可以表示无穷全集的子集，集合中的元素个数也没有限制；本课程内使用带有表头结点的有序链表，也可以使用其它的链表形式。,集合的有序链表类的定义（链表结点）,template struct SetNode/集合的结点类定义 T data;/每个成员的数据 SetNode*link;/链接指针 SetNode():link(NULL);/构造函数 SetNode(const T注意：可参照带表头的链表的实现方式,集合的有序链表类的定义（链表）,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(const 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 elsepc=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;/end of whilepc-link=NULL;temp.last=pc;/链表收尾return temp;；,回忆一下以前的多项式合并算法：1、一元多项式被表示成为不同次数的项的集合，2、每个项包括系数、指数，且从小到大排列；,请考虑几个问题：1、得到的集合仍然是从小到大排列吗？2、既在A中，又在B中的元素会重复出现在并集中吗？,集合并运算的例子,判断集合相等,bool LinkedSet:operator=(LinkedSet,内容,集合及其表示并查集与等价类字典跳表散列,等价关系/等价类,若用符号“”表示集合上的等价关系，则对于该集合中的任意对象x,y,z，下列性质成立：自反性：x x(即等于自身)。对称性：若 x y,则 y x。传递性：若 x y且 y z,则 x z。从数学上看，等价类是对象（或成员）的集合，在一个等价类中的各个元素满足等价关系。一个集合上的等价关系将该集合划分成为互不相交的子集。,并查集（disjoint set）,问题高效地建立和表示某个集合上有一个等价关系建立过程如下：已知一个集合S，并且已知一个关系r。这个关系r通过一个二元组集合来表示；等价关系R是r的自反/传递/对称闭包；我们通过逐个读入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,110 4 0,4,1,2,3,5,6,7,8,9,10,113 1 0,4,1,3,2,5,6,7,8,9,10,116 10 0,4,1,3,2,5,6,10,7,8,9,118 9 0,4,1,3,2,5,6,10,7,8,9,117 4 0,4,7,1,3,2,5,6,10,8,9,116 8 0,4,7,1,3,2,5,6,8,9,10,113 5 0,4,7,1,3,5,2,6,8,9,10,112 11 0,4,7,1,3,5,2,11,6,8,9,1011 0 0,2,4,7,11,1,3,5,6,8,9,10,并查集(Union-Find Sets),并查集支持一个有穷集合上的某些操作并查集支持以下三种操作：Union(Root1,Root2)/合并操作 Find(x)/查找操作 UFSets(s)/构造函数对于并查集来说，分划的每个子集用一棵树表示。也可以用树的根结点来代表子集。子树采用双亲表示法。全集本身可以使用其它数据结构表示。这里我们使用数组表示，用下标指示元素。,S=0,1,2,3,4,5,6,7,8,9S1=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(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,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;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(parentx 0)x=parentx;returnx;,这两个版本都有待改进,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,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,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=parentRoot1+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,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更高，或者一样高；;,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语言的类型推理系统是一个函数式语言。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）的方式出现。在讨论字典抽象数据类型时，把字典定义为对的集合。根据问题的不同，可以为名字和属性赋予不同的含义。从抽象的角度看，字典是一个从名字（或者说Key）到属性的映射（MAP）。,字典的典型操作,确定一个指定的名字是否在字典中；搜索出该名字的属性；修改该名字的属性；插入一个新的名字及其属性；删除一个名字及其属性。,字典的抽象数据类型,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项;否则插入到字典中void Remove(Name name);/若name在字典中,则在字典中删除相应的/对。否则无操作;,索引项,用文件记录（record）或表格的表项（entry）来表示单个元素时，可以使用（key，记录或表项位置adr）构成搜索某一指定记录或表项的索引项。可以通过索引项提高查找效率。,具有重复元素的字典,字典中的元素可以具有相同的关键码（Key）。可能有多个元素具有相同的关键码，需要制定规则消除歧义，使得Find,Remove可以无歧义地执行；也可以Find/Remove所有的元素;,字典的线性表描述,保存在线性序列(e1,e2,)中，其中ei 是字典中的元素，其关键码从左到右依次增大。可以使用有序链表（有序顺序表）结构；每个结点表示字典中的一个元素各个结点按照结点中保存的数据值非递减链接。,#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,有序顺序表的类定义,基于有序顺序表的顺序搜索算法,template int SortedList:Search(K k1)const/顺序搜索关键码为x的数据对象 for(int i=1;i k1)break;return 0;/顺序搜索失败,返回失败信息;算法中的“=”和“”都是重载函数，在定义E时定义它们的实现。,有序顺序表顺序搜索的时间代价,搜索算法的时间效率的衡量标准在搜索过程中关键码平均比较次数，也称为平均搜索长度ASL(Average Search Length)，通常它是字典中元素总数 n 的函数。设搜索第 i 个元素的概率为 pi,搜索到第 i 个元素所需比较次数为 ci,则搜索成功的平均搜索长度：（只考虑了搜索成功的情况）,在顺序搜索情形，搜索第 i(1in)个元素需要比较 i 次，假定按等概率搜索各元素：这与一般顺序表情形相同。但搜索不成功时不需一直比较到表尾，只要发现下一个元素的值比给定值大，就可断定搜索不成功。,基于有序顺序表的折半搜索,设 n 个元素存放在一个有序顺序表中。折半搜索时,先求位于搜索区间正中的元素的下标mid，用其关键码与给定值 x 比较:datamid.key=x，搜索成功；datamid.key x，把搜索区间缩小到表的前半部分，继续折半搜索；datamid.key x，把搜索区间缩小到表的后半部分，继续折半搜索。如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败。,templateint SortedList:BinarySearch(K k1,const int low,const int high)const/折半搜索的递归算法，用到E的重载操作“”int mid=0;/元素序号从1开始 if(low k1)mid=BinarySearch(k1,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;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,插入算法,类似于前面讲过的用链表实现集合时，在集合中加入一个值x的方法,template bool SortedChain:Remove(const K k1,E,类似于前面讲过的用链表实现集合时，在集合中删除一个值x的方法,散列表（Hash Table）,在元素存储位置与其关键码之间建立一个确定的对应函数关系 Hash()，即散列函数，使得每个关键码与结构中某个唯一的存储位置相对应：Address Hash(key)在插入时，依此函数计算存储位置并按此位置存放。在搜索时对元素的关键码进行同样的计算，把求得的函数值当做元素存储位置，在结构中按此位置搜索。通常多个Key对应于多个Address。,优点：不必进行多次关键码的比较,搜索速度比较快,可以直接到达或快速逼近具有此关键码的表项的实际存放地址。散列冲突：关键码集合比散列表地址集合大得多。因此必然会把某些不同的关键码映射到同一个散列地址上，这就产生了冲突。这些散列地址相同的不同关键码被称为同义词。冲突的例子：有一组表项，其关键码分别是 12361,07251,03309,30976 采用的散列函数是 hash(x)=x%73+13420则有 hash(12361)=hash(07250)=hash(03309)=hash(30976)=13444。,由于关键码集合通常比地址集合大得多,冲突很难避免。所以对于散列方法,需要讨论以下两个问题：对于给定的一个关键码集合，选择一个计算简单且地址分布比较均匀的散列函数，避免或尽量减少冲突；解决冲突的方案。,被用于根据关键码计算得到存储地址构造散列函数时的几点要求：散列函数应是简单的，能在较短的时间内计算出结果。散列函数的定义域必须包括需要存储的全部关键码；值域必须是存储地址的全集。散列函数计算出来的地址应能均匀分布在整个地址空间中:若 key 是从关键码集合中随机抽取的一个关键码,散列函数应能以同等概率取0 到 m-1 中的每一个值。,散列函数,直接定址法取关键码的某个线性函数值作为散列地址：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)=1269Hash(940527)=527 Hash(941630)=1630Hash(941805)=1805 Hash(941558)=1558Hash(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、24 这几个地址实际上不能用散列函数计算出来，但是可以在处理冲突时达到这些地址。,数字分析法设有 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 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 位数字,取各关键码的 位做为记录的散列地址。数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。,平方取中法它首先计算构成关键码的标识符的内码的平方,然后按照散列表的大小取中间的若干位作为散列地址。设标识符可以用一个计算机字长的内码表示。因为内码平方数的中间几位一般是由标识符所有字符决定,所以对不同的标识符计算出的散列地址大多不相同。在平方取中法中,一般取散列地址为2的某次幂。例如,若散列地址总数取为 m=8r，则对内码的平方数取中间的 r 位。,标识符的八进制内码表示及其平方值和散列地址,折叠法此方法把关键码自左到右分成位数相等的几部分,每一部分的位数应与散列表地址位数相同,只有最后一部分的位数可以短一些。把这些部分的数据叠加起来,就可以得到具有该关键码的记录的散列地址。有两种叠加方法：移位法：把各部分最后一位对齐相加；分界法：各部分不折断，沿各部分的分界来回折叠,然后对齐相加。,示例:设给定的关键码为 key=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，把计算出的地址压缩到允许范围。,散列冲突的处理,任何散列函数都不能避免产生冲突，因此好的解决冲突的方法十分重要。对散列表的假定若设散列表HT有 m 个地址,将其看作 m 个桶。第 i(0i=1)个表项,这些表项的关键码互为同义词。两个不同表项的关键码用散列函数计算得到同一个散列地址，即产生冲突.它们被放在同一个桶内。当同存放不下时，就需要解决冲突。,闭散列也叫做开地址法。所有的桶都直接放在散列表数组中。每个桶只有一个表项(s=1)。冲突的解决方法：若设散列表中各桶的编址为 0 到 m-1,当要加入一个表项 R2 时,通过散列函数 hash(R2.key)计算得到的桶号 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值是i，实际上被存放在j中。那么在搜索这个元素时，需要从i逐个搜索到j。碰到空位是方可判定这个元素不在Hash表中。因此i、j之间的元素不能直接删除。因此在散列中只能通过做记号删除元素；容易形成堆积，导致搜索变慢。,线性探查法的性能衡量,假设给出一组表项，它们的关键码为 Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht,Ederly。采用的散列函数是：取其第一个字母在字母表中的位置。Hash(x)=ord(x)-ord(A)/ord()求内码函数,线性探查法的例子,可得 Hash(Burke)=1 Hash(Ekers)=4 Hash(Broad)=1 Hash(Blum)=1 Hash(Attlee)=0 Hash(Hecht)=7 Hash(Alton)=0 Hash(Ederly)=4设散列表 HT26,m=26。采用线性探查法处理冲突,则散列结果如图所示。,红色字体为搜索长度,在使用线性探查法对示例进行搜索时，搜索成功的平均搜索长度为：搜索不成功的平均搜索长度为：考虑前一页的例子中，执行以下各步的情况删除Burke搜索Broad插入Bike,用线性探查法组织的散列表的类定义,const int DefaultSize=100;enum KindOfStatus Active,Empty,Deleted;/元素分类(活动/空/删)template class HashTable/散列表类定义public:HashTable(const int d,int sz=DefaultSize);/构造函数 HashTable()delete ht;delete info;/析构函数HashTable/表赋值,bool Search(K k1,E,/构造函数templateHashTable:HashTable(int d,int sz)divitor=d;/除数TableSize=sz;n=0;/表长ht=new ETableSize;/表存储空间info=new KindOfstatusTableSize;for(int i=0;i TableSize;i+)infoi=empty;,template int HashTable:FindPos(K k1)const/搜索在一个散列表中关键码与k1匹配的元素，int i=k1%divitor;/计算初始桶号int j=i;/j是检测下一空桶下标do if(infoj=Empty|infoj=Active,使用线性探查法的搜索算法（1）,FindPos返回后的三种情况：infoj=Empty（没有找到）infoj！=Empty&htj!=k1（也没有找到）infoj=Active&htj=k1（找到）,bool HashTable:Search(K k1,E,FindPos返回后的三种情况：infoj=Emptyinfoj！=Empty&htj!=k1infoj=Active&htj=k1；,线性探查的插入操作,template bool HashTable:Insert(K k1,const E,FindPos返回后的三种情况：infoj=Emptyinfoj!=Empty&htj!=k1infoj=Active&htj=k1；,线性探查的插入操作（修改版）,template bool HashTable:MyInsert(K k1,const E,FindSlot的定义,template int HashTable:FindSlot(K k1)const/前提：k1不在散列中；/在散列表中查找适当的插入k1的位置；若表满则返回-1；/和findPos类似，但是只要查找第一个可插入的空位即可；int i=k1%divitor;/计算初始桶号int j=i;/j是检测下一空桶下标do if(infoj=Empty|infoj=Deleted)return j;/找到可用的桶号j=(j+1)%TableSize;/找下一个空桶 while(j!=i);return-1;/转一圈回到开始点,表已满,失败；;,若想删除一个表项,只能给它做一个删除标记deleted进行逻辑删除,不能把它真正删去。看FindPos函数可知，在探查时碰到Empty可返回False，探查时碰到Delete需要继续探查；一个元素在插入时可能探查多个位置，这些位置上的元素删除后不能设为Empty。否则可能探查不到原先插入的元素。逻辑删除的副作用在执行多次删除后，虽然许多位置没有存放元素，但是探查时仍然当这些位置存放了元素。template bool HashTable:Remove(K k1,E,使用线性探查法的删除操作,二次探查法首先通过某一个散列函数对表项的关键码 key 进行计算，得到桶号（非负整数）。H0=hash(key)然后