数据结构6集合与字典课件

第六章集合与字典本章要点：集合的基本概念及表示方法利用并查集实现集合的方法字典跳表散列

1第六章集合与字典本章要点：1集合及其表示集合基本概念集合是成员(对象或元素)的一个群集。集合中的成员可以是原子(单元素)，也可以是集合。集合的成员必须互不相同。在算法与数据结构中所遇到的集合，其单元素通常是整数、字符、字符串或指针，且同一集合中所有成员具有相同的数据类型。colour={red,orange,yellow,green,black,blue,purple,white}name={“An”,“Cao”,“Liu”,“Ma”,“Peng”,“Wang”,“zhang”}2集合及其表示集合基本概念2集合中的成员一般是无序的，没有先后次序关系。但在表示它时，常常写在一个序列里。我们常设定集合中的单元素具有线性有序关系，此关系可记作“<”，表示“优先于”。若a,b是集合中的两个单元素，则a<b,a==b,a>b三者必居其一；若a,b,c是集合中的三个单元素，且a>b,b>c，则a>c。(传递性)整数、字符和字符串都有一个自然的线性顺序。而指针也可以依据其在序列中安排的位置给予一个线性顺序。集合操作有求集合的并、交、差、判存在等。3集合中的成员一般是无序的，没有先后次序关系。但在表示它时，常集合运算的文氏(Venn)图用位向量实现集合抽象数据类型当集合是全集合{0,1,2,…,n}的一个子集，且n是不大的整数时，可用位(0,1)向量来实现集合。当全集合是由有限的可枚举的成员组成的集合时，可建立全集合成员与整数0,1,2,…的一一对应关系，用位向量来表示该集合的子集4集合运算的文氏(Venn)图用位向量实现集合抽象数据类型4集合的位向量(bitVector)类的定义#include<assert.h>constint

DefaultSize=100;classSet{private:int*bitVector;

int

MaxSize;public:

Set(intMaxSetSize=DefaultSize);~Set(){delete[]bitVector;}

void

MakeEmpty(){for(int

i=0;

i<MaxSize;

i++)

bitVector[i]=0;

}

5集合的位向量(bitVector)类的定义#include

intAddMember(constintx);

int

DelMember(constintx);

Set&operator=(Set

&right);

Set&operator+(Set

&

right);

Set&operator*(Set

&

right);Set&operator

-(Set

&

right);

int

Contains(constint

x);

int

SubSet(Set

&

right);

intoperator==(Set

&right);};6intAddMember(constintx)用位向量实现集合时部分操作的实现构造函数Set::Set(int

MaxSetSize):

MaxSize(MaxSetSize){

assert(MaxSize>0);

bitVector=newint[MaxSize];

assert(bitVector!=0);for(int

i=0;

i<MaxSize;

i++)bitVector[i]=0;}7用位向量实现集合时部分操作的实现构造函数7插入元素XintSet::Addmember(constint

x){

assert(x>=0&&

x<MaxSize);

if(!bitVector[x]){

bitVector[x]=1;

return1;

}

return0;}删除元素Xint

Set::DelMember(constint

x){

assert(x>=0&&

x<MaxSize);

if(bitVector[x]){

bitVector[x]=0;

return1;

}

return0; }8插入元素X8集合复制Set&

Set::operator=(Set&

right){

assert(MaxSize==right.MaxSize);for(int

i=0;

i<MaxSize;

i++)

bitVector[i]=right.bitVector[i]; return*this;}集合并运算Set&

Set::operator+(Set&

right){

assert(MaxSize==right.MaxSize);

for(int

i=0;

i<MaxSize;

i++)

bitVector[i]=bitVector[i]||right.bitVector[i];return*this;}9集合复制9集合交运算Set&

Set::operator*(Set

&right){

assert(MaxSize==right.MaxSize);

for(inti=0;

i<MaxSize;

i++)

bitVector[i]=bitVector[i]&&

right.bitVector[i];return*this;}集合差运算Set&

Set::operator

-(Set&

right){

assert(MaxSize==right.MaxSize);

for(inti=0;

i<MaxSize;

i++)

bitVector[i]=bitVector[i]&&!right.bitVector[i];return*this;}10集合交运算10判断元素X是否在集合中int

Set::Contains(constint

x){

assert(x>=0&&x<MaxSize);

returnbitVector[x]; }判断两个集合是否相等intSet::operator

==(Set&

right){

assert(MaxSize==right.MaxSize);

for(inti=0;

i<MaxSize;i++)

if(bitVector[i]!=right.bitVector[i])return0;

return1;}11判断元素X是否在集合中11若This集合是right的子集则返回1否则为0int

Set::SubSet(Set&

right){

assert(MaxSize==right.MaxSize);

for(int

i=0;

i<MaxSize;i++)

if(bitVector[i]!＝right.bitVector[i])

return0;

return1;

}12若This集合是right的子集则返回1否则为012使用示例

Sets1,s2,s3,s4,s5;

intindex,equal;

//构造集合

for(int

k=0;

k<10;

k++)//集合赋值

{

s1.AddMember(k);

s2.AddMember(k+7);}

//s1:{0,1,2,…,9},s2:{7,8,9,…,16}s3=s1+s2;//求s1与s2的并{0,1,…,16}

s4=s1*s2;//求s1与s2的交{

7,8,9}

s5=s1-

s2;

//求s1与s2的差{0,1,2,3,4,5,6}

index=s1.SubSet(s4);

//求s4在s1中首次匹配

cout<<index<<endl;//位置，index=7

equal=s1==s2;

//集合s1与s2比较相等

cout<<equal<<endl;

//equal为0,两集合不等13使用示例13用有序链表实现集合的抽象数据类型用带表头结点的有序链表表示集合用有序链表来表示集合时，链表中的每个结点表示集合的一个成员。各结点所表示的成员e0,e1,…,en

在链表中按升序排列，即e0<e1<…<en。在一个有序链表中寻找一个集合成员时，一般不用搜索整个链表，搜索效率可以提高很多。集合成员可以无限增加。因此，用有序链表可以表示无穷全集合的子集。14用有序链表实现集合的抽象数据类型用带表头结点的有序链表表示集集合的有序链表类的定义template<classType>classSetList;template<classType>classSetNode{ friendclassSetList<Type>;public:SetNode(constType&item):data(item),link(NULL); private:Typedata; SetNode<Type>*link;};template<classType>classSetList{private:SetNode<Type>*first,*last;public:15集合的有序链表类的定义template<classTypSetList();voidMakeEmpty();intAddMember(constType&x);intDelMember(constType&x);SetList<Type>&operator=(SetList<Type>&right);SetList<Type>&operator+(SetList<Type>&right);SetList<Type>&operator*(SetList<Type>&right);SetList<Type>&operator-(SetList<Type>&right);intContains(constType&x);

intoperator==(SetList<Type>&right); Type&Min(); Type&Max(); }16SetList();16

集合的搜索、加入和删除操作template<classType>判断X是否为集合成员intSetList<Type>::Contains(constType&

x){

SetNode<Type>*temp=first→link;

while(temp!=NULL

&&

temp→data<x)

temp=temp→link;

if(temp!=NULL

&&

temp→data==x)

return1;

elsereturn0;}17集合的搜索、加入和删除操作17将X插入到集合中template<classType>intSetList<Type>::AddMember(constType&x){SetNode<Type>*p=first→link,*q=first;while(p!=NULL&&p→data<x){q=p;p=p→link;} if(p!=NULL&&p→data==x)return0;SetNode<Type>*s=newSetNode(x);s→link=p;q→link=s;if(p==NULL)last=s; return1;}18将X插入到集合中18删除集合中的Xtemplate<classType>intSetList<Type>::DelMember(constType&x){SetNode<Type>*p=first→link,*q=first;while(p!=NULL&&p→data<x){q=p;p=p→link;}if(p!=NULL&&p→data==x){ q→link=p→link; if(p==last)last=q; deletep;return1;}elsereturn0;}19删除集合中的X19用有序链表表示集合时的几个重载函数template<classType>复制集合SetList<Type>&SetList<Type>::operator=(SetList<Type>&

right){

SetNode<Type>*pb=right.first→link;

SetNode<Type>*pa=first=newSetNode<Type>;

while(pb!=NULL){

pa→link=new

SetNode<Type>(pb→data);

pa=pa→link;

pb=pb→link;

}

pa→link=NULL;

last=pa;return*this; }20用有序链表表示集合时的几个重载函数20template<classType>集合并SetList<Type>&SetList<Type>::operator+(SetList<Type>&right){SetNode<Type>*pb=right.first→link; SetNode<Type>*pa=first→link; SetNode<Type>*pc=first;

while(pa!=NULL&&pb!=NULL){if(pa→data==pb→data){pc→link=pa;pa=pa→link;pb=pb→link;}elseif(pa→data<pb→data){pc→link=pa;pa=pa→link;}else21template<classType>集合并{pc→link=newSetNode<Type>(pb→data);pb=pb→link;}pc=pc→link;}if(pa!=NULL)pc→link=pa;else{while(pb!=NULL){pc→link=newSetNode<Type>(pb→data);pc=pc→link;pb=pb→link;}pc→link=NULL;last=pc;}return*this;}22{pc→link=newSetNode<Type>template<classType>集合交SetList<Type>&SetList<Type>::operator*(SetList<Type>&right){SetNode<Type>*pb=right.first→link;SetNode<Type>*pa=first→link;SetNode<Type>*pc=first;while(pa!=NULL&&pb!=NULL){if(pa→data==pb→data) {pc=pc→link;pa=pa→link;pb=pb→link;} elseif(pa→data<pb→data) {pc→link=pa→link;deletepa;pa=pc→link;} elsepb=pb→link;}23template<classType>集合交23

while(pa!=NULL){pc→link=pa→link;deletepa;pa=pc→link;}last=pc;return*this;}24while(pa!=NULL){24template<classType>集合差SetList<Type>&SetList<Type>::operator-(SetList<Type>&right){SetNode<Type>*pb=right.first→link; SetNode<Type>*pa=first→link;SetNode<Type>*pc=first; while(pa!=NULL&&pb!=NULL){if(pa→data==pb→data) {pc→link=pa→link;deletepa;pa=pc→link;pb=pb→link;}elseif(pa→data<pb→data) {pc=pc→link;pa=pa→link;}elsepb=pb→link;}if(pa==NULL)last=pc;return*this;}25template<classType>判断集合相等template<classType>intSetList<Type>::operator==(SetList<Type>&right){SetNode<Type>*pb=right.first→link;SetNode<Type>*pa=first→link; while(pa!=NULL&&pb!=NULL)if(pa→data==pb→data) {pa=pa→link;pb=pb→link;}elsereturn0;if(pa!=NULL||pb!=NULL)return0;return1;}26判断集合相等26并查集(Union-FindSets)把每一个对象看作是一个单元素集合，然后按一定顺序将属于同一等价类的元素所在的集合合并。在此过程中将反复地使用一个搜索运算，确定一个元素在哪一个集合中。能够完成这种功能的集合就是并查集。它支持以下三种操作：

Union(Root1,Root2)

//并操作；要求两个集合互不相交

Find(x)

//搜索操作；

UFSets(s)

//构造函数。27并查集(Union-FindSets)把每一个对象看作是

对于并查集来说，每个集合用一棵树表示。集合中每个元素的元素名分别存放在树的结点中，此外，树的每一个结点还有一个指向其双亲结点的指针。为此，需要有两个映射：集合元素到存放该元素名的树结点间的对应；集合名到表示该集合的树的根结点间的对应。设S1={0,6,7,8}，S2={1,4,9}，S3={2,3,5}28对于并查集来说，每个集合用一棵树表示。282929为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合。如果我们确定了元素i在根为j的树中，而且j有一个指向集合名字表中第k项的指针，则集合名即为name[k]。为此，采用树的双亲表示作为集合存储表示。集合元素的编号从0到n-1。其中n是最大元素个数。在双亲表示中，第i个数组元素代表包含集合元素i的树结点。根结点的双亲为-1，表示集合中的元素个数。为了区别双亲指针信息(0)，集合元素个数信息用负数表示。30为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合3131constintDefaultSize=10;class

UFSets{

//并查集的类定义public:

UFSets(int

s=DefaultSize); ~UFSets(){

delete[]parent;}

constUFSets

&

operator=(UFSets

const&

Value);

void

Union(intRoot1,intRoot2);

intFind(int

x);

voidUnionByHeight(int

Root1,int

Root2); private:

int*parent;

intsize;};32constintDefaultSize=10;32UFSets::UFSets(int

s){

//构造函数

size=s;

parent=newint[size+1];

for(int

i=0;

i<=size;

i++)parent[i]=-1;

}unsignedint

UFSets::Find(int

x){

//搜索操作

if(parent[x]<=0)return

x;

elsereturnFind(parent[x]);}void

UFSets::Union(int

Root1,int

Root2){//并

parent[Root2]=Root1;

//Root2指向Root1}33UFSets::UFSets(ints){Find和Union操作性能不好。假设最初n个元素构成

n棵树组成的森林，parent[i]=-1。做处理Union(n-2,n-1),…,Union(1,2),Union(0,1)后，将产生如图所示的退化的树。执行一次Union操作所需时间是O(1)，n-1次Union操作所需时间是O(n)。若再执行Find(0),Find(1),…,Find(n-1),

若被搜索的元素为i，完成Find(i)

操作需要时间为O(i)，完成n次搜索需要的总时间将达到34Find和Union操作性能不好。假设最初n个元素构成执Union操作的加权规则为避免产生退化的树，改进方法是先判断两集合中元素的个数，如果以i为根的树中的结点个数少于以j为根的树中的结点个数，即parent[i]>parent[j]，则让j成为

i的双亲，否则，让i成为j的双亲。此即Union的加权规则。parent[0](==-4)<parent[4](==-3)35Union操作的加权规则为避免产生退化的树，改进方法是先判断void

UFSets::WeightedUnion(intRoot1,intRoot2){//按Union的加权规则改进的算法

inttemp=parent[Root1]+parent[Root2];if(parent[Root2]<parent[Root1]){

parent[Root1]=Root2;//Root2中结点数多

parent[Root2]=temp;//Root1指向Root2}

else{

parent[Root2]=Root1;//Root1中结点数多

parent[Root1]=temp;//Root2指向Root1

}}36voidUFSets::36使用加权规则得到的树37使用加权规则得到的树37字典及其抽象数据类型考虑的问题是数据的存储和检索（查询），就像在新华字典里字词的组织和查找一个字的相关解释等•存储和检索是计算过程中最重要的基本操作•本章主要讨论基于关键码的数据存储和检索，需要根据某些线索找出相关的数据•支持这种操作的数据结构，通常称为字典或查找表•不是介绍一种结构，而是介绍计算中最重要的一种问题的许多不同解决方式，以及各种相关性质•将用到前面讨论过的许多结构。包括各种线性结构、树性结构及其各种组合，涉及在这些结构上操作的许多算法38字典及其抽象数据类型考虑的问题是数据的存储和检索（查询），抽象模型设有关键码集合KEY和值（或称属性）集合VALUE关联(Association)是二元组（k,v）∈KEYxVALIUE字典：以关联为元素的有穷集合（key不相同）关键码到值的有穷函数：key->value主要字典操作：•检索(search)•插入元素(insert)•删除元素(delete)•修改某key对应的值p269字典的抽象数据结构39抽象模型设有关键码集合KEY和值（或称属性）集合VALUE3最主要也是使用最频繁的操作是检索（也称查找）检索效率是字典实现中最重要的考虑因素静态字典：建立后保持不变的字典动态字典：内容经常动态变动的字典静态字典的基本操作就是检索。实现中主要考虑检索效率动态字典除检索外还有插入和删除，实现中还需要考虑：•插入删除操作的效率•插入删除可能导致字典结构变化，动态变化中能否保证检索效率？（使字典性能不随操作的进行而逐渐恶化）40最主要也是使用最频繁的操作是检索（也称查找）40•存储和检索是计算机信息处理中最基本的工作•字典就是实现存储和检索的结构•需要存储和检索的信息有许多具体情况，因此要考虑各种不同的字典实现技术。•这里的基本问题是空间利用率和操作效率检索效率的评价标准：检索过程中关键码的平均比较次数，即平均检索长度ASL（averagesearchlength），定义为：ASL=Σni=1picici和pi分别为元素i的检索长度和概率。若各元素的检索概率相等，就有pi=1/n。ASL=1/nΣci。字典的组织方法很多，如：顺序、跳表、散列、二叉树和B树等。41•存储和检索是计算机信息处理中最基本的工作41线性表表示线性表可以保存信息，因此可以作为字典的实现基础关联在线性表里顺序排列，形成关联的序列检索就是在线性表里查找关键码合适的元素数据元素的插入删除都是很平常的线性表操作顺序表表示链表表示（p270）42线性表表示线性表可以保存信息，因此可以作为字典的实现基础顺序检索算法/*在字典中顺序检索关键码为key的元素*/intseqSearch(SeqDic*pdic,KeyTypekey,int*position){inti;for(i=0;i<pdic->n;i++)/*从头开始向后扫描*/if(pdic->element[i].key==key){*position=i;returnTRUE;/*检索成功*/}*position=-1;returnFALSE;/*检索失败*/}失败时由position设置一个特殊值。43顺序检索算法/*在字典中顺序检索关键码为key的元素*/43平均检索长度分析ASL=1*p1+2*p2+…+n*pn=(1+2+…+n)/n(pi=1/n时)=(n+1)/2=O(n)优点：数据结构和算法简单，元素是否有序均可使用缺点：平均检索长度大，n很大时检索耗时太多不适合动态变化频繁的字典删除元素需顺序检索，O(n)，可能大量移动数据插入元素（关联）时可保存在已有元素之后，O(1)操作；若要防止出现重复关键码，就需要检查所有元素，O(n)动态变化中字典的检索效率不变（已经是最低效的）44平均检索长度分析44二分法检索算法如果字典元素之间有关系，就可能利用它加快检索速度。最常见的关系是关键码有序，这时将元素按序排列（从小到大或从大到小）排列，就可以快速检索（二分法）二分法检索基本过程（假设元素按关键码升序排列）：1.初始时，考虑范围是整个字典（顺序表）2.取考虑范围中位于中间的元素，用这个元素的关键码与检索关键码比较。如果相等则检索结束；否则3.如果检索关键码较大，把检索范围改为位置高的一半；如果检索关键码较小，把检索范围改为低一半4.如果范围里已经无元素，检索失败结束，否则回到245二分法检索算法45/*在字典中用二分法检索关键码为key的元素*/intbiSearch(SeqDic*pdic,KeyTypekey,int*position){intlow=0,high=pdic->n-1,mid;while(low<=high){mid=(low+high)/2;/*当前检索的中间位置*/if(pdic->element[mid].key==key){/*检索成功*/*position=mid;returnTRUE;}elseif(pdic->element[mid].key>key)high=mid-1;/*要检索的元素在左半区*/elselow=mid+1;/*要检索的元素在右半区*/}*position=-1;returnFALSE;/*检索失败*/}46/*在字典中用二分法检索关键码为key的元素*/46分析每次比较将范围缩小一半，第i次可能比较的元素个数∶比较次数可能比较的元素个数11=2022=2134=22┇┇n2j-1若元素个数n刚好为20+21+……+2j-1=2j-1则最大检索长度为j；若2j-1<n≤2j+1-1，则最大检索长度为j+1。所以，二分法的最大检索长度为log2(n+1)47分析47二分法检索（排序顺序字典）：–优点是检索速度快，O(logn)–插入时需要维护元素顺序，O(n)操作（检索插入位置可以用二分法，O(logn)）–删除可用二分法查找元素，但需移动后面元素，O(n)–只能用于元素按关键码排序的字典，只适合顺序存储结构总结：排序表实现字典，检索效率高。为保持元素顺序，插入删除操作效率低。因此不适合用于实现大的动态字典48二分法检索（排序顺序字典）：48跳表在一个使用有序链表描述的具有n个元素的字典中进行搜索，至多需进行n次比较。如果在链中部节点加一个指针，则比较次数可以减少到n/2+1。搜索时，首先将欲搜索元素与中间元素进行比较。如果欲搜索的元素较小，则仅需搜索链表的左半部分，否则，只要在链表右半部分进行比较即可。49跳表在一个使用有序链表描述的具有n个元素的字典中进行搜索，5050通常0级链包括n个元素，1级链包括n/2个元素，2级链包括n/4个元素，而每2i个元素有一个i级链指针。当且仅当一个元素在0～i级链上，但不在i+1级（若该链存在）链上时，我们就说该元素是i级链元素。在图中，40是2级链上唯一的元素而75是1级链元素。20、30、60、80是0级链元素。图所示的结构为跳表（skiplist）。在该结构中有一组有层次的链。0级链是包含所有元素的有序链表，1级链是0级链的一个子集。i级链所包含的元素是i-1级链的子集。图中，i级链上所有的元素均在i-1级链上。51通常0级链包括n个元素，1级链包括n/2个元素，2级链跳表的插入和删除在图中可以看到，一个指针的元素有n/2个，两个指针的元素有n/4个，三指针的元素有n/8，有i指针的元素有n/2i个。他们处在i级的链上。在进行插入和删除时，要想保持跳表结构，必须耗时O(n)。跳表是用空间+插入和删除上的时间来换取搜索上的时间。这是一种处理方法，但不是很好。52跳表的插入和删除在图中可以看到，一个指针的元素有n/2个，两散列(Hashing)前面讲的字典数据结构（算法）中，元素的存储位置与元素的关键码之间不存在直接对应关系，因此查找关键码需要一系列的比较。搜索的效率取决于比较的次数。散列表与散列方法

散列方法在表项的存储位置与它的关键码之间建立一个确定的对应函数关系Hash(),使每个关键码与结构中的唯一存储位置相对应：

Address=Hash(Rec.key)53散列(Hashing)前面讲的字典数据结构（算法）中，元素的散列方法：在存放表项时，通过相同函数计算存储位置，并按此位置存放，这种方法称为散列方法。

散列函数：在散列方法中使用的函数。

散列表：按上述方法构造出来的表称为散列表。

通常关键码集合比散列表地址集合大的多，因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上。称这些散列地址相同的不同关键码为同义词。

54散列方法：在存放表项时，通过相同函数计算存储位置，并按此位置对于散列方法需要讨论两个问题

(1)对于给定的一个关键码集合，选择一个计算简单且地址分布比较均匀的散列函数，避免或尽量减少冲突。

(2)拟订解决冲突的方案。

散列函数

构造散列函数应注意以下几个问题：

(1)散列函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址，其值域必须在1～m-1之间。

(2)散列函数计算出来的地址应能均匀分布在整个地址空间中。

(3)散列函数应是简单的。55对于散列方法需要讨论两个问题

(1)对于给定的一1.直接定址法

此类方法取关键码的某个线形函数值作为散列地址：

Hash(key)=a*key+b{其中a,b为常数}

这类散列函数是一对一的映射，一般不会产生冲突。但是，它要求散列地址空间的大小与关键码集合的大小相同，这种要求一般很难实现。

561.直接定址法

此类方法取关键码的某个线形函数2.数字分析法

设有n个d位数，每一位可能有r种不同的符号。这r种不同的符号在各位上出现的频率不一定相同。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。计算各位数字中符号分布均匀度

其中，表示第I个符号在第k位上出现的次数，n/r表示各种符号在n个数中均匀出现的期望值。计算值越小，表明在该位各种符号分布的越均匀。572.数字分析法

设有n个d位数，每一位可能有r3.除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或等于m的质数p，或选取一个不含有小于20的质因子的合数作为除数。这样的散列函数为：

hash(key)=key%pp≤m

其中，“%”是整数除法取余的运算，要求这时的质数p不是接近2的幂。583.除留余数法

设散列表中允许的地址数为m，取4.平方取中法

先计算构成关键码的表示符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址。在平方取中法中，一般取散列地址为2的某次幂。594.平方取中法

先计算构成关键码的表示符的内码5.折叠法

有两种方法：

(1)移位法----把各部分的最后一位对齐相加。

(2)分界法----各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当作散列地址。605.折叠法

有两种方法：

(1)移位法----把各部分处理冲突的闭散列方法

若设散列表有m个地址，将其改为m个桶。其桶号与散列地址一一对应。每个桶可存放s个表项。如果对不同的关键码用散列函数计算得到同一个散列地址，就产生了冲突，它们可以放到桶内的不同位置，只有当桶内所s个表项都放满后才会产生冲突。

61处理冲突的闭散列方法

若设散列表有m个地址，将其改处理冲突的一种常用的方法就是闭散列，也叫开地址法。所有的桶都直接放在散列表数组中。因此，每一个桶只有一个表项。如果在存放表项时发现，该位置已被别的表项占据，则在整个表中查找新的位置，如果表未被装满，则在允许的范围内必定有新的位置。查找的主要方法有3种。

1.线形探测法

方法为：一旦发生冲突，在表中顺序向后寻找“下一个”空桶Hi的递推公式为:Hi=(Hi-1+1)%mi=1,2,….,m-1或

Hi=(H0+I)%mI=1,2,….,m-162处理冲突的一种常用的方法就是闭散列，也叫开地址法。所有的桶都实例:已知关键码Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht,Ederly

散列函数为:Hash(x)=ord(x)-ord(‘a’)

可得:Hash(Burke)=1,Hash(Ekers)=4,Hash(Broad)=1,

Hash(Blum)=1,Hash(Attlee)=0,Hash(Alton)=0,

Hash(Hecht)=7,Hash(Ederly)=4

01234567AttleBurkBroaBlumEkerAltoEderHech63实例:已知关键码Burke,Ekers,Broad,Blum二次探查法

线形探查法容易产生“堆积”的问题,即不同探查序列的关键码占据可利用的空桶,使得为寻找某一关键码需要经历土同的探查序列的元素,导致搜索时间增加.

使用二次探查法,在表中寻找“下一个”空桶的公式为:

Hi=(H0+i2)%m,Hi=(H0-i2)%m,I=1,2,3,…,(m-1)/2

式中H0=hash(x)是通过某一个散列函数hash()对表项的关键码x进行计算得到的桶号,它是一个非负整数.m是表的大小,它应是64二次探查法

线形探查法容易产生“堆积”的问题,一个值为4k+3的质数,其中k是一个整数.

实例:若设表的长度为Tablesize=31,根据线形探查结果利用二次探查法所得到的结果为:

01234567BlumBurkBroaEkerEderlHech2122232425262730AltonAttle设散列表的桶数为m,待查表项的关键码为x,第一次通过散列函数计算出来的桶号为H0=hash(x).当发生冲突时,第i-1次和第i次次计算出来的“下一个”桶号为:65一个值为4k+3的质数,其中k是一个整数.

实例:若设表的长将上述两式相加可以得到:从上述式子可以知道,只要知道上一次桶号Hi-1就可以知道下一个桶号Hi.66将上述两式相加可以得到:从上述式子可以知道,只要知道上一次桶3.双散列法

使用散列方法时,需要使用两个散列函数.第一个散列函数Hash()按表项的关键码key计算表项所在的桶号.一旦发生冲突,利用第二个散列函数ReHash()计算该表项“下一个”桶的移位量.处理冲突的开散列方法----链地址法

链地址法处理冲突的方法是,将通过散列函数计算出来地址相同的关键码通过链表链接起来,各链表表头结点组成一个向量.向量的元素个数与桶数一致表头.673.双散列法

使用散列方法时,需要使用两个散列第六章集合与字典本章要点：集合的基本概念及表示方法利用并查集实现集合的方法字典跳表散列

68第六章集合与字典本章要点：1集合及其表示集合基本概念集合是成员(对象或元素)的一个群集。集合中的成员可以是原子(单元素)，也可以是集合。集合的成员必须互不相同。在算法与数据结构中所遇到的集合，其单元素通常是整数、字符、字符串或指针，且同一集合中所有成员具有相同的数据类型。colour={red,orange,yellow,green,black,blue,purple,white}name={“An”,“Cao”,“Liu”,“Ma”,“Peng”,“Wang”,“zhang”}69集合及其表示集合基本概念2集合中的成员一般是无序的，没有先后次序关系。但在表示它时，常常写在一个序列里。我们常设定集合中的单元素具有线性有序关系，此关系可记作“<”，表示“优先于”。若a,b是集合中的两个单元素，则a<b,a==b,a>b三者必居其一；若a,b,c是集合中的三个单元素，且a>b,b>c，则a>c。(传递性)整数、字符和字符串都有一个自然的线性顺序。而指针也可以依据其在序列中安排的位置给予一个线性顺序。集合操作有求集合的并、交、差、判存在等。70集合中的成员一般是无序的，没有先后次序关系。但在表示它时，常集合运算的文氏(Venn)图用位向量实现集合抽象数据类型当集合是全集合{0,1,2,…,n}的一个子集，且n是不大的整数时，可用位(0,1)向量来实现集合。当全集合是由有限的可枚举的成员组成的集合时，可建立全集合成员与整数0,1,2,…的一一对应关系，用位向量来表示该集合的子集71集合运算的文氏(Venn)图用位向量实现集合抽象数据类型4集合的位向量(bitVector)类的定义#include<assert.h>constint

DefaultSize=100;classSet{private:int*bitVector;

int

MaxSize;public:

Set(intMaxSetSize=DefaultSize);~Set(){delete[]bitVector;}

void

MakeEmpty(){for(int

i=0;

i<MaxSize;

i++)

bitVector[i]=0;

}

72集合的位向量(bitVector)类的定义#include

intAddMember(constintx);

int

DelMember(constintx);

Set&operator=(Set

&right);

Set&operator+(Set

&

right);

Set&operator*(Set

&

right);Set&operator

-(Set

&

right);

int

Contains(constint

x);

int

SubSet(Set

&

right);

intoperator==(Set

&right);};73intAddMember(constintx)用位向量实现集合时部分操作的实现构造函数Set::Set(int

MaxSetSize):

MaxSize(MaxSetSize){

assert(MaxSize>0);

bitVector=newint[MaxSize];

assert(bitVector!=0);for(int

i=0;

i<MaxSize;

i++)bitVector[i]=0;}74用位向量实现集合时部分操作的实现构造函数7插入元素XintSet::Addmember(constint

x){

assert(x>=0&&

x<MaxSize);

if(!bitVector[x]){

bitVector[x]=1;

return1;

}

return0;}删除元素Xint

Set::DelMember(constint

x){

assert(x>=0&&

x<MaxSize);

if(bitVector[x]){

bitVector[x]=0;

return1;

}

return0; }75插入元素X8集合复制Set&

Set::operator=(Set&

right){

assert(MaxSize==right.MaxSize);for(int

i=0;

i<MaxSize;

i++)

bitVector[i]=right.bitVector[i]; return*this;}集合并运算Set&

Set::operator+(Set&

right){

assert(MaxSize==right.MaxSize);

for(int

i=0;

i<MaxSize;

i++)

bitVector[i]=bitVector[i]||right.bitVector[i];return*this;}76集合复制9集合交运算Set&

Set::operator*(Set

&right){

assert(MaxSize==right.MaxSize);

for(inti=0;

i<MaxSize;

i++)

bitVector[i]=bitVector[i]&&

right.bitVector[i];return*this;}集合差运算Set&

Set::operator

-(Set&

right){

assert(MaxSize==right.MaxSize);

for(inti=0;

i<MaxSize;

i++)

bitVector[i]=bitVector[i]&&!right.bitVector[i];return*this;}77集合交运算10判断元素X是否在集合中int

Set::Contains(constint

x){

assert(x>=0&&x<MaxSize);

returnbitVector[x]; }判断两个集合是否相等intSet::operator

==(Set&

right){

assert(MaxSize==right.MaxSize);

for(inti=0;

i<MaxSize;i++)

if(bitVector[i]!=right.bitVector[i])return0;

return1;}78判断元素X是否在集合中11若This集合是right的子集则返回1否则为0int

Set::SubSet(Set&

right){

assert(MaxSize==right.MaxSize);

for(int

i=0;

i<MaxSize;i++)

if(bitVector[i]!＝right.bitVector[i])

return0;

return1;

}79若This集合是right的子集则返回1否则为012使用示例

Sets1,s2,s3,s4,s5;

intindex,equal;

//构造集合

for(int

k=0;

k<10;

k++)//集合赋值

{

s1.AddMember(k);

s2.AddMember(k+7);}

//s1:{0,1,2,…,9},s2:{7,8,9,…,16}s3=s1+s2;//求s1与s2的并{0,1,…,16}

s4=s1*s2;//求s1与s2的交{

7,8,9}

s5=s1-

s2;

//求s1与s2的差{0,1,2,3,4,5,6}

index=s1.SubSet(s4);

//求s4在s1中首次匹配

cout<<index<<endl;//位置，index=7

equal=s1==s2;

//集合s1与s2比较相等

cout<<equal<<endl;

//equal为0,两集合不等80使用示例13用有序链表实现集合的抽象数据类型用带表头结点的有序链表表示集合用有序链表来表示集合时，链表中的每个结点表示集合的一个成员。各结点所表示的成员e0,e1,…,en

在链表中按升序排列，即e0<e1<…<en。在一个有序链表中寻找一个集合成员时，一般不用搜索整个链表，搜索效率可以提高很多。集合成员可以无限增加。因此，用有序链表可以表示无穷全集合的子集。81用有序链表实现集合的抽象数据类型用带表头结点的有序链表表示集集合的有序链表类的定义template<classType>classSetList;template<classType>classSetNode{ friendclassSetList<Type>;public:SetNode(constType&item):data(item),link(NULL); private:Typedata; SetNode<Type>*link;};template<classType>classSetList{private:SetNode<Type>*first,*last;public:82集合的有序链表类的定义template<classTypSetList();voidMakeEmpty();intAddMember(constType&x);intDelMember(constType&x);SetList<Type>&operator=(SetList<Type>&right);SetList<Type>&operator+(SetList<Type>&right);SetList<Type>&operator*(SetList<Type>&right);SetList<Type>&operator-(SetList<Type>&right);intContains(constType&x);

intoperator==(SetList<Type>&right); Type&Min(); Type&Max(); }83SetList();16

集合的搜索、加入和删除操作template<classType>判断X是否为集合成员intSetList<Type>::Contains(constType&

x){

SetNode<Type>*temp=first→link;

while(temp!=NULL

&&

temp→data<x)

temp=temp→link;

if(temp!=NULL

&&

temp→data==x)

return1;

elsereturn0;}84集合的搜索、加入和删除操作17将X插入到集合中template<classType>intSetList<Type>::AddMember(constType&x){SetNode<Type>*p=first→link,*q=first;wh