集合与字典一课件.ppt

《集合与字典一课件.ppt》由会员分享，可在线阅读，更多相关《集合与字典一课件.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第1页，此课件共34页哦集合及其表示集合及其表示n集合是成员集合是成员(元素元素)的一个群集。集合中的成员可以是原子的一个群集。集合中的成员可以是原子(单元素单元素)，也可以是集合。，也可以是集合。n集合的成员必须互不相同集合的成员必须互不相同(注：多重集合注：多重集合multisetmultiset允许重允许重复元素复元素)。n在算法与数据结构中所遇到的集合，其单元素通常是整数、在算法与数据结构中所遇到的集合，其单元素通常是整数、字符、字符串或指针，且同一集合中所有成员具有相同的数字符、字符串或指针，且同一集合中所有成员具有相同的数据类型。据类型。n例：例：colour=red,orang

2、e,yellow,green,black,blue,purple,white 集合基本概念集合基本概念第2页，此课件共34页哦n集合中的成员一般是无序的，但在表示它时，集合中的成员一般是无序的，但在表示它时，常写在一个序列里。常写在一个序列里。n常设定集合中的元素具有线性有序关系，此关系常设定集合中的元素具有线性有序关系，此关系可记作可记作“”，表示，表示“优先于优先于”。n整数、字符和串都有一个自然线性顺序。指针也整数、字符和串都有一个自然线性顺序。指针也可依据其在序列中安排的位置给予一个线性顺序。可依据其在序列中安排的位置给予一个线性顺序。n在某些集合中保存实际数据值，某些集合中保在某些集

3、合中保存实际数据值，某些集合中保存标示元素是否在集合中的指示信息。如学校存标示元素是否在集合中的指示信息。如学校开设的所有课程的编码属于前者，一个学期开开设的所有课程的编码属于前者，一个学期开设的课程构成的集合属于后者。设的课程构成的集合属于后者。第3页，此课件共34页哦A B 或 A+B A B 或 A B A-BAAABBB集合（集合（SetSet）的抽象数据类型）的抽象数据类型template class Set public:virtual Set()=0;/构造函数 virtual makeEmpty()=0;/置空集合 virtual bool addMember(const T

4、x)=0;第4页，此课件共34页哦 virtual bool delMember(const T x)=0;virtual Set intersectWith(Set&R)=0;/集合的交运算 virtual Set unionWith(Set&R)=0;/集合的并运算 virtual Set differenceFrom(Set&R)=0;/集合的差运算 virtual bool Contains(T x)=0;virtual bool subSet(Set&R)=0;virtual bool operator=(Set&R)=0;/判集合是否相等;第5页，此课件共34页哦用位向量实现集合抽

5、象数据类型用位向量实现集合抽象数据类型n当集合是全集合当集合是全集合 0,1,2,n 的一个子集，的一个子集，且且 n 是不大的整数是不大的整数时，可用位时，可用位(0,1)向量来实向量来实现集合。现集合。n当全集合是由有限个可枚举的成员组成时，当全集合是由有限个可枚举的成员组成时，可建立全集合成员与整数可建立全集合成员与整数 0,1,2,的一一的一一对应关系，用位向量来表示该集合的子集。对应关系，用位向量来表示该集合的子集。n一个二进位两个取值一个二进位两个取值1或或0，分别表示在集，分别表示在集合与不在集合。合与不在集合。第6页，此课件共34页哦thisRtemp0 1 1 1 0 0 0

6、 0 1 1 00 0 1 0 0 1 0 1 0 1 00 1 1 1 0 1 0 1 1 1 0thisRtemp0 1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 0 1 0 0 0 0 0 0 1 0thisRtemp0 1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 1 0 1 0 0 0 0 1 0 0集合的并集合的并集合的交集合的交集合的差集合的差第7页，此课件共34页哦template bool bitSet:subSet(bitSet&R)/判this是否R的子集 assert(setSize=R.set

7、Size);for(int i=0;i vectorSize;i+)/按位判断 if(bitVectori&!R.bitVectori)return false;return true;thisR0 0 1 1 1 0 1 0 1 1 00 0 1 1 1 0 0 1 0 1 01 1 0 0 0 1 1 0 1 0 1 第8页，此课件共34页哦thisR0 0 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 0itemplate bool bitSet:operator=(bitSet&R)/判集合this与R相等 if(vectorSize!=R.vectorSi

8、ze)return false;for(int i=0;i vectorSize;i+)if(bitVectori!=R.bitVectori)return false;return true;/对应位全部相等;第9页，此课件共34页哦用带表头结点的有序链表表示集合用带表头结点的有序链表表示集合firstfirst081723354972用有序链表实现集合抽象数据类型用有序链表实现集合抽象数据类型n用有序链表来表示集合时，链表中的每个结点表示用有序链表来表示集合时，链表中的每个结点表示集合的一个成员。集合的一个成员。n各结点所表示的成员各结点所表示的成员 e0,e1,en 在链表中按升序在链表

9、中按升序排列，即排列，即 e0 e1 en。n集合成员可以无限增加。因此，用有序链表可以集合成员可以无限增加。因此，用有序链表可以表示无穷全集合的子集。表示无穷全集合的子集。第10页，此课件共34页哦集合的有序链表类的定义集合的有序链表类的定义template struct SetNode/集合的结点类定义 T data;/每个成员的数据 SetNode*link;/链接指针 SetNode():link(NULL);/构造函数 SetNode(const T&x,SetNode*next=NULL):data(x),link(next);/构造函数;template class Linked

10、Set/集合的类定义第11页，此课件共34页哦private:SetNode*first,*last;/有序链表表头指针,表尾指针public:LinkedSet()first=last=new SetNode;LinkedSet(LinkedSet&R);/复制构造函数 LinkedSet()makeEmpty();delete first;void makeEmpty();/置空集合 bool addMember(const T&x);bool delMember(const T&x);LinkedSet&operator=(LinkedSet&R);LinkedSet operator+

11、(LinkedSet&R);第12页，此课件共34页哦 LinkedSet operator*(LinkedSet&R);LinkedSet operator-(LinkedSet&R);bool Contains(const T x);/判x是否集合的成员 bool operator=(LinkedSet&R);/判集合this与R相等 bool Min(T&x);/返回集合最小元素的值 bool Max(T&x);/返回集合最大元素的值 bool subSet(bitSet&R);/判this是否R的子集;第13页，此课件共34页哦等价关系与等价类等价关系与等价类(Equivalence

12、Class)(Equivalence Class)等价类与并查集等价类与并查集n在求解实际应用问题时常会遇到等价类问题。在求解实际应用问题时常会遇到等价类问题。n从数学上看，等价类是对象（或成员）的集合，从数学上看，等价类是对象（或成员）的集合，在此集合中所有对象应满足等价关系。在此集合中所有对象应满足等价关系。n若用符号若用符号“”表示集合上的等价关系，则对于该表示集合上的等价关系，则对于该集合中的任意对象集合中的任意对象x,y,z，下列性质成立：，下列性质成立：u自反性：自反性：x x(即等于自身即等于自身)。u对称性：若对称性：若 x y,则则 y x。u传递性：若传递性：若 x y且且

13、 y z,则则 x z。第14页，此课件共34页哦n因此，等价关系是集合上的一个自反、对称、因此，等价关系是集合上的一个自反、对称、传递的关系。传递的关系。n“相相等等”(=)就就是是一一种种等等价价关关系系，它它满满足足上上述述的的三三个特性。个特性。n一一个个集集合合 S 中中的的所所有有对对象象可可以以通通过过等等价价关关系系划划分分为为若若干干个个互互不不相相交交的的子子集集 S1,S2,S3,，它它们们的的并并就是就是 S。这些子集即为等价类。这些子集即为等价类。n以下哪些是等价关系？室友、夫妻、师生、兄弟以下哪些是等价关系？室友、夫妻、师生、兄弟第15页，此课件共34页哦n给定集合

14、给定集合 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 0n进行归并的过程为：进行归并的过程为：初始初始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,11第16页，此课件共34页哦 0,4,7,1,

15、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第17页，此课件共34页哦并查集并查集 (Union-Find Sets)(Union-Find Sets)n并查集支持以下三种操作：并查集支持以下三种操作：Union(Root1,Root2)/合并操作合并操作 Find(x)/查找操作查找操作 UFSets(s)/构造函数构造函数n对于并查集来说，每个集合用一棵树表示。对于并

16、查集来说，每个集合用一棵树表示。n为此，采用为此，采用树的双亲表示树的双亲表示作为集合存储表示。集作为集合存储表示。集合元素的编号从合元素的编号从0到到 n-1。其中。其中 n 是最大元素个数。是最大元素个数。第18页，此课件共34页哦n在双亲表示中，第在双亲表示中，第 i 个数组元素代表包含个数组元素代表包含集合元素集合元素 i 的树结点。初始时，根结点的的树结点。初始时，根结点的双亲为双亲为-1，其绝对值表示集合中的元素，其绝对值表示集合中的元素个数。个数。n在同一棵树上所有结点所代表的集合元在同一棵树上所有结点所代表的集合元素在同一个子集合中。素在同一个子集合中。第19页，此课件共34页

17、哦n设设 S1=0,6,7,8,S2=1,4,9,S3=2,3,5n为为简简化化讨讨论论，忽忽略略实实际际的的集集合合名名，仅仅用用表表示示集集合合的树的根来标识集合。的树的根来标识集合。集合名集合名 指针指针0 S11 S22 S30427681935-4000-3-34422第20页，此课件共34页哦n初初始始时时,用用构构造造函函数数 UFSets(s)构构造造一一个个森森林林,每每棵棵树树只只有有一一个个结结点点,表表示示集集合合中中各各元元素素自自成成一一个个子子集合。集合。n用用 Find(i)寻寻找找集集合合元元素素 i 的的根根。如如果果有有两两个个集集合合元元素素 i 和和

18、j,Find(i)=Find(j),表表明明这这两两个个元元素素在在同同一个集合中，一个集合中，n如如果果两两个个集集合合元元素素 i 和和 j 不不在在同同一一个个集集合合中中,可可用用 Union(i,j)将它们合并到一个集合中。将它们合并到一个集合中。下标下标parent-1 -1 -1 -1 -1 -1 -1 -1 -1 -10 1 2 3 4 5 6 7 8 9第21页，此课件共34页哦S1下标下标下标下标parent集合集合 S S1 1,S S2 2 和和 S S3 3 的双亲表示的双亲表示-4 4 -3 2 -3 2 0 0 0 40 1 2 3 4 5 6 7 8 9S2S3

19、0768000-4419-344235-322第22页，此课件共34页哦S1 S2的可能的表示方法的可能的表示方法下标下标下标下标parent集合集合 S1 S2 和和 S3 的双亲表示的双亲表示-7 4 -3 2 0 2 0 0 0 40 1 2 3 4 5 6 7 8 907684194190876-7-7000044444000第23页，此课件共34页哦字典（字典（DictionaryDictionary）n字典是一些元素的集合，每个元素有一字典是一些元素的集合，每个元素有一个称作关键码（个称作关键码（key）的域，不同元素的关）的域，不同元素的关键码互不相同。键码互不相同。n在讨论字典

20、抽象数据类型时，把字典定义为在讨论字典抽象数据类型时，把字典定义为对的集合。对的集合。n根据问题的不同，可以为名字和属性（信息）根据问题的不同，可以为名字和属性（信息）赋予不同的含义。赋予不同的含义。第24页，此课件共34页哦n例如，在图书馆检索目录中，名字是书名，属性是例如，在图书馆检索目录中，名字是书名，属性是索书号及作者等信息；在计算机活动文件表中，名索书号及作者等信息；在计算机活动文件表中，名字是文件名，属性是文件地址、大小等信息。字是文件名，属性是文件地址、大小等信息。n一般来说，有关字典的操作有如下几种：一般来说，有关字典的操作有如下几种：1.确定一个指定的名字是否在字典中；确定一

21、个指定的名字是否在字典中；2.搜索出该名字的属性；搜索出该名字的属性；3.修改该名字的属性；修改该名字的属性；4.插入一个新的名字及其属性；插入一个新的名字及其属性；5.删除一个名字及其属性。删除一个名字及其属性。第25页，此课件共34页哦字典的抽象数据类型字典的抽象数据类型 const int DefaultSize=26;template class Dictionary/对象:一组对,其中,名字是唯一的public:Dictionary(int size=DefaultSize);/构造函数 bool Member(Name name);/判name是否在字典中 Attribute*Se

22、arch(Name name);/在字典中搜索关键码与name匹配的表项 第26页，此课件共34页哦 void Insert(Name name,Attribute attr);/若name在字典中,则修改相应对 /的attr项;否则插入到字典中 void Remove(Name name);/若name在字典中,则在字典中删除相应的 /对;n用文件记录（用文件记录（record）或表格的表项（）或表格的表项（entry）来）来表示单个元素时，用二元组：表示单个元素时，用二元组：（关键码（关键码key，记录或表项位置指针，记录或表项位置指针adr）n构成搜索某一指定记录或表项的索引项。构成搜索

23、某一指定记录或表项的索引项。第27页，此课件共34页哦字典的线性表描述字典的线性表描述 n字典可以保存在线性序列字典可以保存在线性序列(e1,e2,)中，其中中，其中ei 是字典中的元素，其是字典中的元素，其关键码从左到右依次增大关键码从左到右依次增大。为了适应这种描述方式，可以定义有序顺序表和为了适应这种描述方式，可以定义有序顺序表和有序链表。有序链表。n用有序链表来表示字典时，链表中的每个结点表用有序链表来表示字典时，链表中的每个结点表示字典中的一个元素，示字典中的一个元素，各个结点按照结点中保存各个结点按照结点中保存的数据值非递减链接的数据值非递减链接，即，即e1e2 。因此，在一。因此

24、，在一个有序链表中寻找一个指定元素时，一般不用搜索个有序链表中寻找一个指定元素时，一般不用搜索整个链表。整个链表。第28页，此课件共34页哦跳表（跳表（skip listskip list）n由前面讨论可知，在一个有序顺序表中进行折半由前面讨论可知，在一个有序顺序表中进行折半搜索，时间效率很高。但是在有序链表中进行搜搜索，时间效率很高。但是在有序链表中进行搜索，只能顺序搜索，需要执行索，只能顺序搜索，需要执行O(n)次关键码比较。次关键码比较。n如果在链表中部结点中增加一个指针，则比较次如果在链表中部结点中增加一个指针，则比较次数可以减少到数可以减少到 n/2+1。在搜索时，首先用要搜索元。在

25、搜索时，首先用要搜索元素与中间元素进行比较，如果要搜索元素小于中间素与中间元素进行比较，如果要搜索元素小于中间元素，则仅需搜索链表的前半部分，否则只要在链元素，则仅需搜索链表的前半部分，否则只要在链表的后半部分进行比较即可。表的后半部分进行比较即可。第29页，此课件共34页哦跳表的结构跳表的结构(a)带有表头结点和表尾结点的有序链表(b)在链表中部增加一个链接指针(c)在前半部分和后半部分中部各增加一个链接指针102030405060701020304050607010203040506070第30页，此课件共34页哦n在上面跳表的例子中有三条链：在上面跳表的例子中有三条链：0 级链级链就是图

26、就是图(a)中中的初始链表，包括了所有的初始链表，包括了所有 7个元素。个元素。1 级链级链包括包括 2、4、6 三个元素。三个元素。2 级链级链只包括第只包括第 4 个元素。个元素。n为了搜索值为为了搜索值为 30 的元素，首先搜索的元素，首先搜索 2 级链，与中级链，与中间元素间元素 40 进行比较，在进行比较，在 2 级链中只需比较级链中只需比较1次。由次。由于于30 20，可，可到到 0 级链继续搜索，与链表中元素进行比较。级链继续搜索，与链表中元素进行比较。n搜索搜索时间代价为时间代价为O(log2n)。第31页，此课件共34页哦n图图(c)就是跳表，有一组分层的链，就是跳表，有一组

27、分层的链，0级链级链是包含是包含所有元素的有序链表，有所有元素的有序链表，有n个元素。个元素。n0 级链的第级链的第21,2 21,3 21,个结点链接起来形成个结点链接起来形成1级链级链，故，故1级链是级链是0级链的子集。级链的子集。n1 级链的第级链的第22,2 22,3 22,个结点链接起来形成个结点链接起来形成2级链级链，依此类推，依此类推，第第i级链级链所包含的元素是所包含的元素是第第i-1级级链链的子集。的子集。n一个有一个有n个元素的跳表理想情况下的链级数为个元素的跳表理想情况下的链级数为 log2n，即跳表的最高级数为，即跳表的最高级数为 log2n-1。n若一个元素在若一个元

28、素在0i级链上，而不在级链上，而不在i+1级链（如果级链（如果存在）上时，就可称该元素是存在）上时，就可称该元素是i级链元素。级链元素。第32页，此课件共34页哦跳表的搜索算法跳表的搜索算法 n当需要搜索一个值为当需要搜索一个值为k1的元素时，可用成员函的元素时，可用成员函数数Search。若找到要搜索的元素，则将该元素返回到。若找到要搜索的元素，则将该元素返回到e1中。中。nSearch函数从最高级链（函数从最高级链（Levels级，仅含一个元素）级，仅含一个元素）的表头结点开始，沿着链搜索，遇到某一关键的表头结点开始，沿着链搜索，遇到某一关键码大于或等于要搜索的关键码，则下降到下一码大于或

29、等于要搜索的关键码，则下降到下一级，沿较低级链的指针搜索，逐步逼近要搜索级，沿较低级链的指针搜索，逐步逼近要搜索的元素，一直到的元素，一直到0级链。级链。n当从循环退出时，正处于要找元素左边。与当从循环退出时，正处于要找元素左边。与0级链下级链下一元素比较，就可知元素是否在表中。一元素比较，就可知元素是否在表中。第33页，此课件共34页哦n每当插入一个新的元素时，就为该元素分配一个级每当插入一个新的元素时，就为该元素分配一个级别，指明它属于第几级链的元素。一个结点的级别别，指明它属于第几级链的元素。一个结点的级别规定了该结点所包含的指针数目。规定了该结点所包含的指针数目。n为跳表结点分配级别是随机的。为跳表结点分配级别是随机的。n为避免可能为某个元素分配特别高的级别这种情为避免可能为某个元素分配特别高的级别这种情况，可以对况，可以对lev设定一个上限设定一个上限maxLevel，该上限值，该上限值应为应为 log2n-1，表明该跳表的最高级别。，表明该跳表的最高级别。跳表的插入算法跳表的插入算法第34页，此课件共34页哦