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