数据结构集合与字典

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

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);};第6页，共67页，2023年，2月20日，星期六用位向量实现集合时部分操作的实现构造函数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页，共67页，2023年，2月20日，星期六插入元素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页，共67页，2023年，2月20日，星期六集合复制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页，共67页，2023年，2月20日，星期六集合交运算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页，共67页，2023年，2月20日，星期六判断元素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页，共67页，2023年，2月20日，星期六若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页，共67页，2023年，2月20日，星期六使用示例

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页，共67页，2023年，2月20日，星期六用有序链表实现集合的抽象数据类型用带表头结点的有序链表表示集合用有序链表来表示集合时，链表中的每个结点表示集合的一个成员。各结点所表示的成员e0,e1,…,en

在链表中按升序排列，即e0<e1<…<en。在一个有序链表中寻找一个集合成员时，一般不用搜索整个链表，搜索效率可以提高很多。集合成员可以无限增加。因此，用有序链表可以表示无穷全集合的子集。第14页，共67页，2023年，2月20日，星期六集合的有序链表类的定义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页，共67页，2023年，2月20日，星期六SetList();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(); }第16页，共67页，2023年，2月20日，星期六

集合的搜索、加入和删除操作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页，共67页，2023年，2月20日，星期六将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页，共67页，2023年，2月20日，星期六删除集合中的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页，共67页，2023年，2月20日，星期六用有序链表表示集合时的几个重载函数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页，共67页，2023年，2月20日，星期六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→link=pa;pa=pa→link;pb=pb→link;}elseif(pa→data<pb→data){pc→link=pa;pa=pa→link;}else第21页，共67页，2023年，2月20日，星期六{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页，共67页，2023年，2月20日，星期六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;}第23页，共67页，2023年，2月20日，星期六

while(pa!=NULL){pc→link=pa→link;deletepa;pa=pc→link;}last=pc;return*this;}第24页，共67页，2023年，2月20日，星期六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→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;}第25页，共67页，2023年，2月20日，星期六判断集合相等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页，共67页，2023年，2月20日，星期六并查集(Union-FindSets)把每一个对象看作是一个单元素集合，然后按一定顺序将属于同一等价类的元素所在的集合合并。在此过程中将反复地使用一个搜索运算，确定一个元素在哪一个集合中。能够完成这种功能的集合就是并查集。它支持以下三种操作：

Union(Root1,Root2)

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

Find(x)

//搜索操作；

UFSets(s)

//构造函数。第27页，共67页，2023年，2月20日，星期六

对于并查集来说，每个集合用一棵树表示。集合中每个元素的元素名分别存放在树的结点中，此外，树的每一个结点还有一个指向其双亲结点的指针。为此，需要有两个映射：集合元素到存放该元素名的树结点间的对应；集合名到表示该集合的树的根结点间的对应。设S1={0,6,7,8}，S2={1,4,9}，S3={2,3,5}第28页，共67页，2023年，2月20日，星期六第29页，共67页，2023年，2月20日，星期六为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合。如果我们确定了元素i在根为j的树中，而且j有一个指向集合名字表中第k项的指针，则集合名即为name[k]。为此，采用树的双亲表示作为集合存储表示。集合元素的编号从0到n-1。其中n是最大元素个数。在双亲表示中，第i个数组元素代表包含集合元素i的树结点。根结点的双亲为-1，表示集合中的元素个数。为了区别双亲指针信息(0)，集合元素个数信息用负数表示。第30页，共67页，2023年，2月20日，星期六第31页，共67页，2023年，2月20日，星期六constintDefaultSize=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;};第32页，共67页，2023年，2月20日，星期六UFSets::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}第33页，共67页，2023年，2月20日，星期六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次搜索需要的总时间将达到第34页，共67页，2023年，2月20日，星期六Union操作的加权规则为避免产生退化的树，改进方法是先判断两集合中元素的个数，如果以i为根的树中的结点个数少于以j为根的树中的结点个数，即parent[i]>parent[j]，则让j成为

i的双亲，否则，让i成为j的双亲。此即Union的加权规则。parent[0](==-4)<parent[4](==-3)第35页，共67页，2023年，2月20日，星期六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

}}第36页，共67页，2023年，2月20日，星期六使用加权规则得到的树第37页，共67页，2023年，2月20日，星期六字典及其抽象数据类型考虑的问题是数据的存储和检索（查询），就像在新华字典里字词的组织和查找一个字的相关解释等•

存储和检索是计算过程中最重要的基本操作•

本章主要讨论基于关键码的数据存储和检索，需要根据某些线索找出相关的数据•

支持这种操作的数据结构，通常称为字典或查找表•

不是介绍一种结构，而是介绍计算中最重要的一种问题的许多不同解决方式，以及各种相关性质•

将用到前面讨论过的许多结构。包括各种线性结构、树性结构及其各种组合，涉及在这些结构上操作的许多算法38第38页，共67页，2023年，2月20日，星期六抽象模型设有关键码集合KEY和值（或称属性）集合VALUE关联(Association)是二元组（k,v）∈KEYxVALIUE字典：以关联为元素的有穷集合（key不相同）关键码到值的有穷函数：key->value主要字典操作：•

检索(search)•

插入元素(insert)•

删除元素(delete)•

修改某key对应的值p269字典的抽象数据结构39第39页，共67页，2023年，2月20日，星期六最主要也是使用最频繁的操作是检索（也称查找）检索效率是字典实现中最重要的考虑因素静态字典：建立后保持不变的字典动态字典：内容经常动态变动的字典静态字典的基本操作就是检索。实现中主要考虑检索效率动态字典除检索外还有插入和删除，实现中还需要考虑：•

插入删除操作的效率•

插入删除可能导致字典结构变化，动态变化中能否保证检索效率？（使字典性能不随操作的进行而逐渐恶化）40第40页，共67页，2023年，2月20日，星期六•

存储和检索是计算机信息处理中最基本的工作•

字典就是实现存储和检索的结构•

需要存储和检索的信息有许多具体情况，因此要考虑各种不同的字典实现技术。•

这里的基本问题是空间利用率和操作效率检索效率的评价标准：检索过程中关键码的平均比较次数，即平均检索长度ASL（averagesearchlength），定义为：ASL=Σni=1picici

和pi

分别为元素i的检索长度和概率。若各元素的检索概率相等，就有pi=1/n。ASL=1/nΣci

。字典的组织方法很多，如：顺序、跳表、散列、二叉树和B树等。41第41页，共67页，2023年，2月20日，星期六线性表表示线性表可以保存信息，因此可以作为字典的实现基础关联在线性表里顺序排列，形成关联的序列检索就是在线性表里查找关键码合适的元素数据元素的插入删除都是很平常的线性表操作顺序表表示链表表示（p270）42第42页，共67页，2023年，2月20日，星期六顺序检索算法/*在字典中顺序检索关键码为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第43页，共67页，2023年，2月20日，星期六平均检索长度分析

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页，共67页，2023年，2月20日，星期六二分法检索算法如果字典元素之间有关系，就可能利用它加快检索速度。最常见的关系是关键码有序，这时将元素按序排列（从小到大或从大到小）排列，就可以快速检索（二分法）二分法检索基本过程（假设元素按关键码升序排列）：1.初始时，考虑范围是整个字典（顺序表）2.取考虑范围中位于中间的元素，用这个元素的关键码与检索关键码比较。如果相等则检索结束；否则3.如果检索关键码较大，把检索范围改为位置高的一半；如果检索关键码较小，把检索范围改为低一半4.如果范围里已经无元素，检索失败结束，否则回到245第45页，共67页，2023年，2月20日，星期六/*在字典中用二分法检索关键码为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第46页，共67页，2023年，2月20日，星期六分析每次比较将范围缩小一半，第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页，共67页，2023年，2月20日，星期六二分法检索（排序顺序字典）：–

优点是检索速度快，O(logn)–

插入时需要维护元素顺序，O(n)操作（检索插入位置可以用二分法，O(logn)）–

删除可用二分法查找元素，但需移动后面元素，O(n)–

只能用于元素按关键码排序的字典，只适合顺序存储结构总结：排序表实现字典，检索效率高。为保持元素顺序，插入删除操作效率低。因此不适合用于实现大的动态字典48第48页，共67页，2023年，2月20日，星期六跳表在一个使用有序链表描述的具有n个元素的字典中进行搜索，至多需进行n次比较。如果在链中部节点加一个指针，则比较次数可以减少到n/2+1。搜索时，首先将欲搜索元素与中间元素进行比较。如果欲搜索的元素较小，则仅需搜索链表的左半部分，否则，只要在链表右半部分进行比较即可。49第49页，共67页，2023年，2月20日，星期六50第50页，共67页，2023年，2月20日，星期六通常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第51页，共67页，2023年，2月20日，星期六跳表的插入和删除在图中可以看到，一个指针的元素有n/2个，两个指针的元素有n/4个，三指针的元素有n/8，有i指针的元素有n/2i个。他们处在i级的链上。在进行插入和删除时，要想保持跳表结构，必须耗时O(n)。跳表是用空间+插入和删除上的时间来换取搜索上的时间。这是一种处理方法，但不是很好。52第52页，共67页，2023年，2月20日，星期六散列(Hashing)前面讲的字典数据结构（算法）中，元素的存储位置与元素的关键码之间不存在直接对应关系，因此查找关键码需要一系列的比较。搜索的效率取决于比较的次数。散列表与散列方法

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

Address=Hash(Rec.key)53第53页，共67页，2023年，2月20日，星期六散列方法：在存放表项时，通过相同函数计算存储位置，并按此位置存放，这种方法称为散列方法。

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

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

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

54第54页，共67页，2023年，2月20日，星期六对于散列方法需要讨论两个问题

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

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

散列函数

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

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

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

(3)散列函数应是简单的。55第55页，共67页，2023年，2月20日，星期六1.直接定址法

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

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

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

56第56页，共67页，2023年，2月20日，星期六2.数字分析法

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

其中，表示第I个符号在第k位上出现的次数，n/r表示各种符号在n个数中均匀出现的期望值。计算值越小，表明在该位各种符号分布的越均匀。57第57页，共67页，2023年，2月20日，星期六3.除留余数法

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

hash(key)=key%pp≤m

其中，“%”是整数除法取余的运算，要求这时的质数p不是接近2的幂。58第58页，共67页，2023年，2月20日，星期六4.平方取中法

先计算构成关键码的表示符的内码的平方，然后按照散列表的大小取中间的若干位作为散列