《集合与字典 (2)精选文档.ppt》由会员分享，可在线阅读，更多相关《集合与字典 (2)精选文档.ppt（74页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、集合与字典本讲稿第一页，共七十四页算法与数据结构29.19.1集合及其运算集合及其运算集合及其运算集合及其运算集合是一个基本数学概念，也是一种基本数据结构。集合是一个基本数学概念，也是一种基本数据结构。集合是一个基本数学概念，也是一种基本数据结构。集合是一个基本数学概念，也是一种基本数据结构。抽象地说集合是一些个体（值）的无序汇集；而在实用中抽象地说集合是一些个体（值）的无序汇集；而在实用中抽象地说集合是一些个体（值）的无序汇集；而在实用中抽象地说集合是一些个体（值）的无序汇集；而在实用中作为数据结构的集合可以有多种形式，例如：作为数据结构的集合可以有多种形式，例如：作为数据结构的集合可以有多
2、种形式，例如：作为数据结构的集合可以有多种形式，例如：本讲稿第二页，共七十四页算法与数据结构3集合的抽象定义明确说其中的元素是无顺序的。这样，集合的抽象定义明确说其中的元素是无顺序的。这样，集合的抽象定义明确说其中的元素是无顺序的。这样，集合的抽象定义明确说其中的元素是无顺序的。这样，只有对集合中所有的值进行比较之后，才能判断两个集只有对集合中所有的值进行比较之后，才能判断两个集只有对集合中所有的值进行比较之后，才能判断两个集只有对集合中所有的值进行比较之后，才能判断两个集合是否相等。为了提高效率，集合的许多实现中规定了合是否相等。为了提高效率，集合的许多实现中规定了合是否相等。为了提高效率，
3、集合的许多实现中规定了合是否相等。为了提高效率，集合的许多实现中规定了在元素之间可以进行比较和按顺序存储。在元素之间可以进行比较和按顺序存储。在元素之间可以进行比较和按顺序存储。在元素之间可以进行比较和按顺序存储。本讲稿第三页，共七十四页算法与数据结构4一些集合中保存的是实际的数据值，而另一些集合保一些集合中保存的是实际的数据值，而另一些集合保一些集合中保存的是实际的数据值，而另一些集合保一些集合中保存的是实际的数据值，而另一些集合保存的是元素是否存在于集合中的指示信息。存的是元素是否存在于集合中的指示信息。存的是元素是否存在于集合中的指示信息。存的是元素是否存在于集合中的指示信息。例如，如果
4、一个集合的元素是字符型或取值范围不太例如，如果一个集合的元素是字符型或取值范围不太例如，如果一个集合的元素是字符型或取值范围不太例如，如果一个集合的元素是字符型或取值范围不太大的整数型，那么只要保存指示信息就足够了，因为，大的整数型，那么只要保存指示信息就足够了，因为，大的整数型，那么只要保存指示信息就足够了，因为，大的整数型，那么只要保存指示信息就足够了，因为，如果需要的话，整个值的集合很容易被重新建立起来；如果需要的话，整个值的集合很容易被重新建立起来；如果需要的话，整个值的集合很容易被重新建立起来；如果需要的话，整个值的集合很容易被重新建立起来；但是如果集合包含的是学生记录学生记录或浮点
5、数数但是如果集合包含的是学生记录学生记录或浮点数数但是如果集合包含的是学生记录学生记录或浮点数数但是如果集合包含的是学生记录学生记录或浮点数数据，由于这些值不容易重建，所以这些元素的实际数据，由于这些值不容易重建，所以这些元素的实际数据，由于这些值不容易重建，所以这些元素的实际数据，由于这些值不容易重建，所以这些元素的实际数据值必须保存在集合里。据值必须保存在集合里。据值必须保存在集合里。据值必须保存在集合里。本讲稿第四页，共七十四页算法与数据结构5在集合的抽象概念实际要求每个元素只在集合中出现一次。在集合的抽象概念实际要求每个元素只在集合中出现一次。在集合的抽象概念实际要求每个元素只在集合中
6、出现一次。在集合的抽象概念实际要求每个元素只在集合中出现一次。但有些实际应用却需要允许元素的重复出现。但有些实际应用却需要允许元素的重复出现。但有些实际应用却需要允许元素的重复出现。但有些实际应用却需要允许元素的重复出现。比如一个班级里的所有学生姓名的集合，实际上无法排除同比如一个班级里的所有学生姓名的集合，实际上无法排除同比如一个班级里的所有学生姓名的集合，实际上无法排除同比如一个班级里的所有学生姓名的集合，实际上无法排除同学之间重名的可能性。这时可以使用集合的一种变体：称为学之间重名的可能性。这时可以使用集合的一种变体：称为学之间重名的可能性。这时可以使用集合的一种变体：称为学之间重名的可
7、能性。这时可以使用集合的一种变体：称为多重集合。多重集合。多重集合。多重集合。多重集合（多重集合（多重集合（多重集合（multisetmultiset，或称为包，或称为包，或称为包，或称为包bagbag）是一种类似集）是一种类似集）是一种类似集）是一种类似集合的结构，其基本性质与集合类似，但允许元素的重合的结构，其基本性质与集合类似，但允许元素的重合的结构，其基本性质与集合类似，但允许元素的重合的结构，其基本性质与集合类似，但允许元素的重复出现。复出现。复出现。复出现。本讲稿第五页，共七十四页算法与数据结构6如果在集合实现时采用的是保存实际数据值的方法，如果在集合实现时采用的是保存实际数据值的
8、方法，如果在集合实现时采用的是保存实际数据值的方法，如果在集合实现时采用的是保存实际数据值的方法，只要加上一个相关值出现次数的计数器就可以用于实只要加上一个相关值出现次数的计数器就可以用于实只要加上一个相关值出现次数的计数器就可以用于实只要加上一个相关值出现次数的计数器就可以用于实现包；现包；现包；现包；如果集合用记录元素是否存在的指示信息的方式实现，如果集合用记录元素是否存在的指示信息的方式实现，如果集合用记录元素是否存在的指示信息的方式实现，如果集合用记录元素是否存在的指示信息的方式实现，要改做包的实现就比较困难。要改做包的实现就比较困难。要改做包的实现就比较困难。要改做包的实现就比较困难
9、。本讲稿第六页，共七十四页算法与数据结构79.1.19.1.1集合运算集合运算集合运算集合运算 与前面讲到的许多数据结构类似，对一个集合也与前面讲到的许多数据结构类似，对一个集合也与前面讲到的许多数据结构类似，对一个集合也与前面讲到的许多数据结构类似，对一个集合也可以定义增加一个元素，删除一个元素，或者测可以定义增加一个元素，删除一个元素，或者测可以定义增加一个元素，删除一个元素，或者测可以定义增加一个元素，删除一个元素，或者测试一个元素是否已在集合中等运算，但集合作为试一个元素是否已在集合中等运算，但集合作为试一个元素是否已在集合中等运算，但集合作为试一个元素是否已在集合中等运算，但集合作为
10、一种抽象数据类型，其定义的特点应体现在涉及一种抽象数据类型，其定义的特点应体现在涉及一种抽象数据类型，其定义的特点应体现在涉及一种抽象数据类型，其定义的特点应体现在涉及两个（或多个）集合之间的一些运算。这些运算两个（或多个）集合之间的一些运算。这些运算两个（或多个）集合之间的一些运算。这些运算两个（或多个）集合之间的一些运算。这些运算主要有：主要有：主要有：主要有：本讲稿第七页，共七十四页算法与数据结构8并集：两个集合的并集定义为由两个集合的所有并集：两个集合的并集定义为由两个集合的所有并集：两个集合的并集定义为由两个集合的所有并集：两个集合的并集定义为由两个集合的所有元素形成的集合。元素形成
11、的集合。元素形成的集合。元素形成的集合。交集：两个集合的交集由同时在两个集合中出现的那交集：两个集合的交集由同时在两个集合中出现的那交集：两个集合的交集由同时在两个集合中出现的那交集：两个集合的交集由同时在两个集合中出现的那些元素组成。些元素组成。些元素组成。些元素组成。差集：求两个集合的差集与求交集相反。差集由第一差集：求两个集合的差集与求交集相反。差集由第一差集：求两个集合的差集与求交集相反。差集由第一差集：求两个集合的差集与求交集相反。差集由第一个集合中的所有不在第二个集合里出现的元素组成。个集合中的所有不在第二个集合里出现的元素组成。个集合中的所有不在第二个集合里出现的元素组成。个集合
12、中的所有不在第二个集合里出现的元素组成。子集：一个集合称为是另一个集合的子集，如果这个集子集：一个集合称为是另一个集合的子集，如果这个集子集：一个集合称为是另一个集合的子集，如果这个集子集：一个集合称为是另一个集合的子集，如果这个集合的所有元素都出现在另一个集合里。合的所有元素都出现在另一个集合里。合的所有元素都出现在另一个集合里。合的所有元素都出现在另一个集合里。相等：两个集合相等，指的是第一个集合的元素相等：两个集合相等，指的是第一个集合的元素相等：两个集合相等，指的是第一个集合的元素相等：两个集合相等，指的是第一个集合的元素都出现在第二个集合里，而第二个集合的元素也都出现在第二个集合里，
13、而第二个集合的元素也都出现在第二个集合里，而第二个集合的元素也都出现在第二个集合里，而第二个集合的元素也都出现在第一个集合里。这个概念的另一种表述都出现在第一个集合里。这个概念的另一种表述都出现在第一个集合里。这个概念的另一种表述都出现在第一个集合里。这个概念的另一种表述是：若两个集合互为子集则称这两个集合相等。是：若两个集合互为子集则称这两个集合相等。是：若两个集合互为子集则称这两个集合相等。是：若两个集合互为子集则称这两个集合相等。本讲稿第八页，共七十四页算法与数据结构9从抽象的观点考查上述定义的集合与集合之间的运算，我从抽象的观点考查上述定义的集合与集合之间的运算，我从抽象的观点考查上述
14、定义的集合与集合之间的运算，我从抽象的观点考查上述定义的集合与集合之间的运算，我们发现这些运算可以通过简单地增加元素，检测成员，删们发现这些运算可以通过简单地增加元素，检测成员，删们发现这些运算可以通过简单地增加元素，检测成员，删们发现这些运算可以通过简单地增加元素，检测成员，删除元素等运算定义。除元素等运算定义。除元素等运算定义。除元素等运算定义。已知集合已知集合已知集合已知集合A A和和和和B B，求它们的并集，求它们的并集，求它们的并集，求它们的并集,只要以集合只要以集合只要以集合只要以集合A A（或（或（或（或B B）为基）为基）为基）为基础，把集合础，把集合础，把集合础，把集合B B
15、（或（或（或（或A A）中的元素逐个插入。）中的元素逐个插入。）中的元素逐个插入。）中的元素逐个插入。在求两个集合的交集时，只要从在求两个集合的交集时，只要从在求两个集合的交集时，只要从在求两个集合的交集时，只要从A A（或（或（或（或B B）集出发，检查）集出发，检查）集出发，检查）集出发，检查它的每个元素是否在它的每个元素是否在它的每个元素是否在它的每个元素是否在B B（或（或（或（或A A）集中出现，若是，则把该元）集中出现，若是，则把该元）集中出现，若是，则把该元）集中出现，若是，则把该元素插入到结果集合（初态为空集）中即可。素插入到结果集合（初态为空集）中即可。素插入到结果集合（初态
16、为空集）中即可。素插入到结果集合（初态为空集）中即可。求求求求A A与与与与B B的差集的差集的差集的差集A-B A-B 时，只要以时，只要以时，只要以时，只要以A A集为基础，对每个集为基础，对每个集为基础，对每个集为基础，对每个B B集中集中集中集中的元素做删除运算即可。的元素做删除运算即可。的元素做删除运算即可。的元素做删除运算即可。本讲稿第九页，共七十四页算法与数据结构10如果我们用如果我们用如果我们用如果我们用a a，i i，和，和，和，和r r分别代表分别代表分别代表分别代表增加元素，检测元素，增加元素，检测元素，增加元素，检测元素，增加元素，检测元素，删除元素运算的执行时间，删除
17、元素运算的执行时间，删除元素运算的执行时间，删除元素运算的执行时间，并假定集合中的元素为并假定集合中的元素为并假定集合中的元素为并假定集合中的元素为n n个。个。个。个。依集合运算的抽象实现，可以估算出这些运算操作依集合运算的抽象实现，可以估算出这些运算操作依集合运算的抽象实现，可以估算出这些运算操作依集合运算的抽象实现，可以估算出这些运算操作的时间上限：的时间上限：的时间上限：的时间上限：求求求求两个集合的并时间为两个集合的并时间为两个集合的并时间为两个集合的并时间为O(a n);O(a n);求差集的运行时间为求差集的运行时间为求差集的运行时间为求差集的运行时间为O(r n);O(r n)
18、;求交集的运行时间为求交集的运行时间为求交集的运行时间为求交集的运行时间为O(i+a)n)O(i+a)n)。本讲稿第十页，共七十四页9.1.2集合类集合类我们可以定义一个集合类。定义这个类主我们可以定义一个集合类。定义这个类主要是为了说明各种实现集合的数据结构都要是为了说明各种实现集合的数据结构都应当具有的操作。这个类里没有为集合的应当具有的操作。这个类里没有为集合的实现而设置的内部数据结构，因此也就不实现而设置的内部数据结构，因此也就不需要构造函数和析构函数。需要构造函数和析构函数。本讲稿第十一页，共七十四页templateclasssetpublic:virtualintisEmpty(v
19、oid)const=0;virtualintincludes(constTval)const=0;virtualvoidadd(constTval)=0;virtualvoidremove(constTval)=0;voidintersectWith(constset&);voidunionWith(constset&);voiddifferenceFrom(constset&);intsubset(constset&)return0;intoperator=(constset&)return0;类类9.1集合类集合类本讲稿第十二页，共七十四页我们无法把我们无法把set中的方法都定义为纯虚函数
20、，因为在中的方法都定义为纯虚函数，因为在实现集合操作的成员函数里都包含了对集合类的实实现集合操作的成员函数里都包含了对集合类的实例对象的引用参数。这种情况下函数不能定义为纯例对象的引用参数。这种情况下函数不能定义为纯虚的。这里为每个函数虚构了一个函数体，它们是虚的。这里为每个函数虚构了一个函数体，它们是永远不会被真正使用的。永远不会被真正使用的。这里还有一个新情况，在这里还有一个新情况，在set类的定义里面直接写出类的定义里面直接写出intersectWith等成员函数的定义，而不是只写它们的等成员函数的定义，而不是只写它们的原型。原型。C+允许这样做。当成员函数很短小时，为紧允许这样做。当成
21、员函数很短小时，为紧凑或消除过多重复描述，常采用这种写法凑或消除过多重复描述，常采用这种写法本讲稿第十三页，共七十四页举一个例子讨论上面提出的问题。假设我们把举一个例子讨论上面提出的问题。假设我们把unionWith定义为纯虚函数，函数在类规范里的原定义为纯虚函数，函数在类规范里的原型应该是：型应该是：virtualvoidunionWith(constset&)=0;在在set的实际子类中就必须给出的实际子类中就必须给出unionWith的实现，的实现，而实际上我们无法给出具有同样函数原型的函数的实而实际上我们无法给出具有同样函数原型的函数的实际实现。际实现。本讲稿第十四页，共七十四页为说明
22、这个问题，假设我们要把为说明这个问题，假设我们要把setA定义为定义为set的非抽象的子类，现在考虑它的定义以及其中的非抽象的子类，现在考虑它的定义以及其中纯虚函数纯虚函数unionWith的规范。按照需要，我们应的规范。按照需要，我们应该写：该写：templateclasssetA:publicset.virtualvoidunionWith(constsetA&s);.本讲稿第十五页，共七十四页但是，在这样定义好类规范并建立的但是，在这样定义好类规范并建立的setA所有成员函数所有成员函数之后，会发现仍然无法建立之后，会发现仍然无法建立setA的实例对象。的实例对象。例如，如果我们写出下面
23、的变量定义例如，如果我们写出下面的变量定义setAs1;程序编译时会发生错误，系统将告诉我们：在建立程序编译时会发生错误，系统将告诉我们：在建立setA的实例时，遇到了没有给出定义的纯虚函数的实例时，遇到了没有给出定义的纯虚函数voidunionWith(constset&)。因为在上面因为在上面setA里定义的里定义的unionWith函数的参数类型与函数的参数类型与set里里unionWith的参数不同，这将被认为是对原函数的参数不同，这将被认为是对原函数名的另一个重载定义，而原来的纯虚函数仍然没有定名的另一个重载定义，而原来的纯虚函数仍然没有定义。义。本讲稿第十六页，共七十四页显然，在显
24、然，在setA里把里把unionWith定义为：定义为：virtualvoidunionWith(constset&s);是没有意义的，不会有抽象类的实例成为实际参数，是没有意义的，不会有抽象类的实例成为实际参数，因为根本没有这种实例。因为根本没有这种实例。上述问题是可能通过其他途径绕过去的，但那将使问上述问题是可能通过其他途径绕过去的，但那将使问题大大的复杂化，给出的定义很费事，理解起来也比较困题大大的复杂化，给出的定义很费事，理解起来也比较困难。这里选择的是一种较自然方便的做法。难。这里选择的是一种较自然方便的做法。本讲稿第十七页，共七十四页算法与数据结构189.3 9.3 集合的表实现集
25、合的表实现集合的表实现集合的表实现本讲稿第十八页，共七十四页算法与数据结构19在这节里，我们将考虑利用表实现集合的方法，也就在这节里，我们将考虑利用表实现集合的方法，也就在这节里，我们将考虑利用表实现集合的方法，也就在这节里，我们将考虑利用表实现集合的方法，也就是说，在集合对象中用一个表数据成分，借助它存储是说，在集合对象中用一个表数据成分，借助它存储是说，在集合对象中用一个表数据成分，借助它存储是说，在集合对象中用一个表数据成分，借助它存储集合的元素。根据这个想法定义的集合的元素。根据这个想法定义的集合的元素。根据这个想法定义的集合的元素。根据这个想法定义的setListsetList见类见
26、类见类见类9.59.5。本讲稿第十九页，共七十四页算法与数据结构20template class setList:public settemplate class setList:public set protected:protected:list slist;list slist;public:public:setList();setList();/构造函数构造函数构造函数构造函数 setList(const setList&);setList(const setList&);virtual inline int isEmpty()const return slist.isEmpty();
27、virtual inline int isEmpty()const return slist.isEmpty();virtual inline int includes(T val)const slist.includes(val)virtual inline int includes(T val)const slist.includes(val)virtual void add(T val);virtual void add(T val);/往集合里增加新元素往集合里增加新元素往集合里增加新元素往集合里增加新元素 virtual void remove(T);virtual void rem
28、ove(T);/删除删除删除删除 void unionWith(const setList&);void unionWith(const setList&);/求并求并求并求并 void intersectWith(const setList&);void intersectWith(const setList&);/求交求交求交求交 void differenceFrom(const setList&);void differenceFrom(const setList&);/求差求差求差求差 int subset(const setList&)const;int subset(const
29、setList&)const;/子集判断子集判断子集判断子集判断 int operator=(const setList&)const;int operator=(const setList&)const;/相等判断相等判断相等判断相等判断 void deleteAllValues()slist.deleteAllValues();void deleteAllValues()slist.deleteAllValues();friend class setListIterator;friend class setListIterator;类类类类9.5 setList9.5 setList类的规
30、范说明类的规范说明类的规范说明类的规范说明 本讲稿第二十页，共七十四页算法与数据结构21类类类类setListsetList的构造函数非常自然。其中的无参构造函的构造函数非常自然。其中的无参构造函的构造函数非常自然。其中的无参构造函的构造函数非常自然。其中的无参构造函数建立空集合，也就是说，建立一个有着空表数建立空集合，也就是说，建立一个有着空表数建立空集合，也就是说，建立一个有着空表数建立空集合，也就是说，建立一个有着空表slistslist的集合；复制构造函数建立一个相同的集合，实际上的集合；复制构造函数建立一个相同的集合，实际上的集合；复制构造函数建立一个相同的集合，实际上的集合；复制构
31、造函数建立一个相同的集合，实际上就是在建立集合时做一次表的复制。这些函数很容易就是在建立集合时做一次表的复制。这些函数很容易就是在建立集合时做一次表的复制。这些函数很容易就是在建立集合时做一次表的复制。这些函数很容易利用表的构造函数实现。利用表的构造函数实现。利用表的构造函数实现。利用表的构造函数实现。本讲稿第二十一页，共七十四页算法与数据结构22由于集合对元素有唯一性要求，在向一个集合里增加由于集合对元素有唯一性要求，在向一个集合里增加由于集合对元素有唯一性要求，在向一个集合里增加由于集合对元素有唯一性要求，在向一个集合里增加元素前，必须首先检查它是否已经存在于表元素前，必须首先检查它是否已
32、经存在于表元素前，必须首先检查它是否已经存在于表元素前，必须首先检查它是否已经存在于表slistslist中。向中。向中。向中。向集合里插入元素的函数实现如下：集合里插入元素的函数实现如下：集合里插入元素的函数实现如下：集合里插入元素的函数实现如下：本讲稿第二十二页，共七十四页算法与数据结构23 template void setList:add(T val)template void setList:add(T val)/仅当元素不在集合中时作插入仅当元素不在集合中时作插入仅当元素不在集合中时作插入仅当元素不在集合中时作插入 if(!slist.includes(val)slist.add(
33、val);if(!slist.includes(val)slist.add(val);本讲稿第二十三页，共七十四页算法与数据结构24由于在插入前要检查存在性，所以这个增加新元素的操由于在插入前要检查存在性，所以这个增加新元素的操由于在插入前要检查存在性，所以这个增加新元素的操由于在插入前要检查存在性，所以这个增加新元素的操作也具有线性时间的复杂性。作也具有线性时间的复杂性。作也具有线性时间的复杂性。作也具有线性时间的复杂性。本讲稿第二十四页，共七十四页算法与数据结构25要实现在集合中删除一个元素的运算，需要借助于表要实现在集合中删除一个元素的运算，需要借助于表要实现在集合中删除一个元素的运算，
34、需要借助于表要实现在集合中删除一个元素的运算，需要借助于表遍历器，通过它找到被删除元素，然后执行实际删除遍历器，通过它找到被删除元素，然后执行实际删除遍历器，通过它找到被删除元素，然后执行实际删除遍历器，通过它找到被删除元素，然后执行实际删除动作。动作。动作。动作。本讲稿第二十五页，共七十四页算法与数据结构26template void setList:remove(T val)template void setList:remove(T val)listIterator itr(slist);listIterator itr(slist);for(itr.init();!itr;+itr)f
35、or(itr.init();!itr;+itr)if(itr()=val)if(itr()=val)itr.removeCurrent();itr.removeCurrent();return;return;本讲稿第二十六页，共七十四页算法与数据结构27removeCurrentremoveCurrent是是是是listIteratorlistIterator里定义的方法。显然，函里定义的方法。显然，函里定义的方法。显然，函里定义的方法。显然，函数数数数removeremove的时间代价也是的时间代价也是的时间代价也是的时间代价也是O(n)O(n)。本讲稿第二十七页，共七十四页算法与数据结构2
36、8下面看求并集操作的实现。应该注意，下面看求并集操作的实现。应该注意，下面看求并集操作的实现。应该注意，下面看求并集操作的实现。应该注意，setListsetList类的成员类的成员类的成员类的成员函数函数函数函数unionWithunionWith要求它的参数必须是同类型的，也就是说，要求它的参数必须是同类型的，也就是说，要求它的参数必须是同类型的，也就是说，要求它的参数必须是同类型的，也就是说，参数集合的元素必须与接受集合的元素具有同样类型，是参数集合的元素必须与接受集合的元素具有同样类型，是参数集合的元素必须与接受集合的元素具有同样类型，是参数集合的元素必须与接受集合的元素具有同样类型，
37、是用同一个用同一个用同一个用同一个T T类型定义的。如果不是同样类型，本操作没类型定义的。如果不是同样类型，本操作没类型定义的。如果不是同样类型，本操作没类型定义的。如果不是同样类型，本操作没有定义。有定义。有定义。有定义。本讲稿第二十八页，共七十四页算法与数据结构29template void setList:unionWith(const template void setList:unionWith(const setList&s)setList&s)listIterator itr(s.slist);listIterator itr(s.slist);for(itr.init();!i
38、tr;+itr)for(itr.init();!itr;+itr)add(itr();add(itr();本讲稿第二十九页，共七十四页算法与数据结构30由前面分析中已知由前面分析中已知由前面分析中已知由前面分析中已知addadd的执行时间为的执行时间为的执行时间为的执行时间为O(n)O(n)，所以，所以，所以，所以unionWithunionWith的执行时间为的执行时间为的执行时间为的执行时间为O(nO(n2 2)。用类似的方式可以实现。用类似的方式可以实现。用类似的方式可以实现。用类似的方式可以实现intersectWithintersectWith和和和和differenceWithdi
39、fferenceWith等运算。下面给出子集测试方法的实现，这等运算。下面给出子集测试方法的实现，这等运算。下面给出子集测试方法的实现，这等运算。下面给出子集测试方法的实现，这里是按照子集概念直接给出的实现。里是按照子集概念直接给出的实现。里是按照子集概念直接给出的实现。里是按照子集概念直接给出的实现。本讲稿第三十页，共七十四页算法与数据结构31template int setList:subset(const template int setList:subset(const setList&s)constsetList&s)const listIterator itr(s.slist);l
40、istIterator itr(s.slist);for(itr.init();!itr;+itr)for(itr.init();!itr;+itr)if(!slist.includes(itr()return 0;if(!slist.includes(itr()return 0;return 1;return 1;本讲稿第三十一页，共七十四页算法与数据结构32集合相等性的测试通过调用两次子集测试实现。集合相等性的测试通过调用两次子集测试实现。集合相等性的测试通过调用两次子集测试实现。集合相等性的测试通过调用两次子集测试实现。template int setList:operator=(con
41、st template int setList:operator=(const setList&s)constsetList&s)const /两个集合互为子集时它们相等两个集合互为子集时它们相等两个集合互为子集时它们相等两个集合互为子集时它们相等 return subset(s)&s.subset(*this);return subset(s)&s.subset(*this);本讲稿第三十二页，共七十四页算法与数据结构33集合还可以采用其他很多实现方式。例如，用排序树实集合还可以采用其他很多实现方式。例如，用排序树实集合还可以采用其他很多实现方式。例如，用排序树实集合还可以采用其他很多实现方
42、式。例如，用排序树实现集合也很常见。用排序树作为基础数据表示方式，定现集合也很常见。用排序树作为基础数据表示方式，定现集合也很常见。用排序树作为基础数据表示方式，定现集合也很常见。用排序树作为基础数据表示方式，定义集合的方法与义集合的方法与义集合的方法与义集合的方法与setListsetList相似，这里就不再重复了。读者相似，这里就不再重复了。读者相似，这里就不再重复了。读者相似，这里就不再重复了。读者可以把这个问题作为自己的练习。可以把这个问题作为自己的练习。可以把这个问题作为自己的练习。可以把这个问题作为自己的练习。本讲稿第三十三页，共七十四页算法与数据结构349.4 9.4 关联与字典
43、关联与字典关联与字典关联与字典本讲稿第三十四页，共七十四页算法与数据结构35下面先讨论作为字典元素的关联，定义关联的类，然后下面先讨论作为字典元素的关联，定义关联的类，然后下面先讨论作为字典元素的关联，定义关联的类，然后下面先讨论作为字典元素的关联，定义关联的类，然后再讨论字典的有关问题。再讨论字典的有关问题。再讨论字典的有关问题。再讨论字典的有关问题。本讲稿第三十五页，共七十四页算法与数据结构36字典字典字典字典(dictionary)(dictionary)是一类特殊集合，其元素是一种二元是一类特殊集合，其元素是一种二元是一类特殊集合，其元素是一种二元是一类特殊集合，其元素是一种二元组，二
44、元组的两个成分分别被称为该元素的组，二元组的两个成分分别被称为该元素的组，二元组的两个成分分别被称为该元素的组，二元组的两个成分分别被称为该元素的“关键码关键码关键码关键码”和和和和“值值值值”，这种数据元素通常被称为，这种数据元素通常被称为，这种数据元素通常被称为，这种数据元素通常被称为“关联关联关联关联”。本讲稿第三十六页，共七十四页算法与数据结构37字典是关联的集合，那么一个字典就是由一组关键码字典是关联的集合，那么一个字典就是由一组关键码字典是关联的集合，那么一个字典就是由一组关键码字典是关联的集合，那么一个字典就是由一组关键码（一个集合）到一组值（另一个集合）的对应关系：（一个集合）
45、到一组值（另一个集合）的对应关系：（一个集合）到一组值（另一个集合）的对应关系：（一个集合）到一组值（另一个集合）的对应关系：如果一个字典里所有的关键码互不相同，那么它可以看作如果一个字典里所有的关键码互不相同，那么它可以看作如果一个字典里所有的关键码互不相同，那么它可以看作如果一个字典里所有的关键码互不相同，那么它可以看作是由关键码集合是由关键码集合是由关键码集合是由关键码集合K K到值集合到值集合到值集合到值集合V V的一个映射。在实践中使用较的一个映射。在实践中使用较的一个映射。在实践中使用较的一个映射。在实践中使用较多的就是这种关键码具有唯一性的字典。人们有时也把字典多的就是这种关键码
46、具有唯一性的字典。人们有时也把字典多的就是这种关键码具有唯一性的字典。人们有时也把字典多的就是这种关键码具有唯一性的字典。人们有时也把字典称为映射称为映射称为映射称为映射(mapping)(mapping)。本讲稿第三十七页，共七十四页算法与数据结构38以英汉词典为例，我们可以把其中的每个词条看作一以英汉词典为例，我们可以把其中的每个词条看作一以英汉词典为例，我们可以把其中的每个词条看作一以英汉词典为例，我们可以把其中的每个词条看作一个元素，词条的有关单词看作是该元素的关键码，词个元素，词条的有关单词看作是该元素的关键码，词个元素，词条的有关单词看作是该元素的关键码，词个元素，词条的有关单词看
47、作是该元素的关键码，词条中的其他信息（对单词的解释，例句等的总和）是条中的其他信息（对单词的解释，例句等的总和）是条中的其他信息（对单词的解释，例句等的总和）是条中的其他信息（对单词的解释，例句等的总和）是元素的值。元素的值。元素的值。元素的值。本讲稿第三十八页，共七十四页算法与数据结构39对字典元素的存取通过关键码进行，这一点与向量有类似对字典元素的存取通过关键码进行，这一点与向量有类似对字典元素的存取通过关键码进行，这一点与向量有类似对字典元素的存取通过关键码进行，这一点与向量有类似之处。存取字典元素可以看作是通过关键码这样的（广义）之处。存取字典元素可以看作是通过关键码这样的（广义）之处
48、。存取字典元素可以看作是通过关键码这样的（广义）之处。存取字典元素可以看作是通过关键码这样的（广义）“索引索引索引索引”进行元素访问，所以人们也把字典看作是一种索进行元素访问，所以人们也把字典看作是一种索进行元素访问，所以人们也把字典看作是一种索进行元素访问，所以人们也把字典看作是一种索引结构。与向量不同的是，字典中的关键码可以具有任意类引结构。与向量不同的是，字典中的关键码可以具有任意类引结构。与向量不同的是，字典中的关键码可以具有任意类引结构。与向量不同的是，字典中的关键码可以具有任意类型，而向量的型，而向量的型，而向量的型，而向量的“关键码关键码关键码关键码”只能是整数。为了实现字典的有
49、只能是整数。为了实现字典的有只能是整数。为了实现字典的有只能是整数。为了实现字典的有关功能，关键码也必须作为字典元素的一部分进行存储，关功能，关键码也必须作为字典元素的一部分进行存储，关功能，关键码也必须作为字典元素的一部分进行存储，关功能，关键码也必须作为字典元素的一部分进行存储，这一点也与向量不同这一点也与向量不同这一点也与向量不同这一点也与向量不同(在向量中只存储元素的值，下标并在向量中只存储元素的值，下标并在向量中只存储元素的值，下标并在向量中只存储元素的值，下标并不存储，由元素的位置隐含地规定不存储，由元素的位置隐含地规定不存储，由元素的位置隐含地规定不存储，由元素的位置隐含地规定)
50、。本讲稿第三十九页，共七十四页算法与数据结构40本小节首先介绍作为字典元素类型的关联类本小节首先介绍作为字典元素类型的关联类本小节首先介绍作为字典元素类型的关联类本小节首先介绍作为字典元素类型的关联类 association association(如类如类如类如类9.69.6描述描述描述描述)。一个关联中的关键码取某个确定值。一个关联中的关键码取某个确定值。一个关联中的关键码取某个确定值。一个关联中的关键码取某个确定值(具有具有具有具有KEYKEY类型类型类型类型)，一旦被设置后就不能再改变了。而元素的值，一旦被设置后就不能再改变了。而元素的值，一旦被设置后就不能再改变了。而元素的值，一旦被