数据结构第7章集合与搜索

136第7章集合与搜索一、复习要点集合是最基本的抽象数据类型之一。本章讨论了集合的三种存储表示：位数组表示、有序链表表示、并查集。在本章的后半部分，讨论了与集合相关的搜索方法和简单的性能分析方法，包括适用于静态搜索表的顺序搜索和折半搜索及代表动态搜索表的二叉搜索树和AVL树。可以使用扩充的二叉搜索树描述顺序搜索和折半搜索，从而推导出估算搜索效率的公式。静态搜索表在整个程序的运行期间结构不会变化，其搜索效率随着表中对象的个数n不断增长。动态搜索表因各个对象的输入顺序不同，得到的搜索表的形态不同，典型的是二叉搜索树。在具有n个对象的二叉搜索树中，搜索效率最高的是高度最低的二叉搜索树。为确保二叉搜索树始终保持搜索效率最高，必须在输入新的对象时判断二叉搜索树是否“失去平衡”，并进行适当的平衡旋转，使二叉搜索树的高度降到最低。这就是AVL树。在AVL树的讨论中，4种平衡旋转，选择参加平衡旋转的3个结点是关键，必须加以注意。本章复习的要点是：1、基本知识点必须理解集合及其表示方法，包括位数组表示、有序链表表示及其相关操作的实现算法集合及其表示。理解并查集实现的方法。理解搜索的概念，理解静态搜索表结构，掌握静态搜索表的顺序搜索和折半搜索算法及其性能分析方法。掌握二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法，掌握AVL树的构造、插入、删除时的调整方法及其性能分析，重点是AVL树的定义、平衡化旋转、AVL树的插入和删除、AVL树的高度。2、算法设计用有序链表表示集合时的求集合的并、交、差的算法并查集中的构造函数、求根及合并算法并查集中根据树的高度和根据树中结点个数进行合并的算法设置监视哨的顺序搜索算法和不设监视哨的顺序搜索算法有序顺序表的顺序搜索算法有序顺序表的折半搜索的递归算法和非递归算法二叉搜索树的搜索、插入和删除算法计算AVL树中指定结点高度的递归算法及利用此算法计算结点平衡因子的算法二、难点和重点1、集合的概念：集合的基本运算、集合的存储表示用位数组表示集合时集合基本运算的实现用有序链表表示集合时集合基本运算的实现2、并查集：并查集定义、并查集的三种基本运算的实现3、基本搜索方法对一般表的顺序搜索算法(包括有监视哨和没有监视哨)对有序顺序表的顺序搜索算法，包括递归和非递归算法用判定树(即扩充二叉搜索树)描述有序顺序表的顺序搜索，以及平均搜索长度(成功与不成功)的计算。对有序顺序表的折半搜索算法、包括递归和非递归算法用判定树(即扩充二叉搜索树)描述有序顺序表的折半搜索，以及平均搜索长度(成功137与不成功)的计算。4、二叉搜索树动态搜索树与静态搜索树的特性二叉搜索树的定义、二叉搜索树上的递归和非递归搜索算法二叉搜索树搜索时的平均搜索长度(成功与不成功)的计算二叉搜索树的插入与删除算法AVL树结点上的平衡因子、AVL树的平衡旋转方法高度为h的AVL树上的最少结点个数与最多结点个数AVL树的搜索方法、插入与删除方法(不要求算法)三、教材中习题的解析7-1设A={1,2,3},B={3,4,5}，求下列结果：(1)A+B(2)A*B(3)A-B(4)A.Contains(1)(5)A.AddMember(1)(6)A.DelMember(1)(7)A.Min()【解答】(1)集合的并A+B={1,2,3,4,5}(2)集合的交A*B={3}(3)集合的差A-B={1,2}(4)包含A.Contains(1)=1，表示运算结果为True(5)增加A.AddMember(1)，集合中仍为{1,2,3}，因为增加的是重复元素，所以不加入(6)删除A.DelMember(1)，集合中为{2,3}(7)求最小元素A.Min()，结果为17-2试编写一个算法，打印一个有穷集合中的所有成员。要求使用集合抽象数据类型中的基本操作。如果集合中包含有子集合，各个子集合之间没有重复的元素，采用什么结构比较合适。【解答】集合抽象数据类型的部分内容templateclassTypeclassSet{//对象:零个或多个成员的聚集。其中所有成员的类型是一致的,但没有一个成员是相同的。intContains(constTypex);//判元素x是否集合this的成员intSubSet(SetType&right);//判集合this是否集合right的子集intoperator==(SetType&right);//判集合this与集合right是否相等intElemtype();//返回集合元素的类型TypeGetData();//返回集合原子元素的值charGetName();//返回集合this的集合名SetType*GetSubSet();//返回集合this的子集合地址SetType*GetNext();//返回集合this的直接后继集合元素intIsEmpty();//判断集合this空否。空则返回1,否则返回0};138ostream&operator(ostream&out,SetTypet){//友元函数,将集合t输出到输出流对象out。t.traverse(out,t);returnout;}voidtraverse(ostream&out,SetTypes){//友元函数,集合的遍历算法if(s.IsEmpty()==0){//集合元素不空if(s.Elemtype()==0)outs.GetName()‘{’;//输出集合名及花括号elseif(s.Elemtype()==1){//集合原子元素outs.GetData();//输出原子元素的值if(s.GetNext()!=NULL)out‘,’;}else{//子集合traverse(s.GetSubSet());//输出子集合if(s.GetNext()!=NULL)out‘,’;}traverse(s.GetNext());//向同一集合下一元素搜索}elseout‘}’;}如果集合中包含有子集合，各个子集合之间没有重复的元素，采用广义表结构比较合适。也可以使用并查集结构。7-3当全集合可以映射成1到N之间的整数时，可以用位数组来表示它的任一子集合。当全集合是下列集合时，应当建立什么样的映射？用映射对照表表示。(1)整数0,1,…,99(2)从n到m的所有整数，nm(3)整数n,n+2,n+4,…,n+2k(4)字母‘a’,‘b’,‘c’,…,‘z’(5)两个字母组成的字符串,其中，每个字母取自‘a’,‘b’,‘c’,…,‘z’。【解答】(1)i→i的映射关系，i=0,1,2,…,99(2)i→n-i的映射关系，i=n,n+1,n+2,…,m012m-nnn+1n+2…m(3)i→(i-n)/2的映射关系，i=n,n+2,n+4,…,n+2k012knn+2n+4…n+2k(4)ord(c)→ord(c)-ord('a')的映射关系，c='a','b','c',…,'z'01225'a''b''c'…'z'(5)(ord(c1)-ord('a'))*26+ord(c2)-ord('a')的映射关系，c1=c2='a','b','c',…,'z'139012675'aa''ab''ba'…'zz'7-4试证明：集合A是集合B的子集的充分必要条件是集合A和集合B的交集是A。【证明】必要条件：因为集合A是集合B的子集，有AB，此时，对于任一xA，必有xB，因此可以推得xA∩B，就是说，如果A是B的子集，一定有A∩B=A。充分条件：如果集合A和集合B的交集A∩B是A，则对于任一xA，一定有xA∩B，因此可以推得xB，由此可得AB，即集合A是集合B的子集。7-5试证明：集合A是集合B的子集的充分必要条件是集合A和集合B的并集是B。【证明】必要条件：因为集合A是集合B的子集，有AB，此时，对于任一xA，必有xB，它一定在A∪B中。另一方面，对于那些x'A,但x'B的元素，它也必在A∪B中，因此可以得出结论：凡是属于集合B的元素一定在A∪B中，A∪B=B。充分条件：如果存在元素xA且xB，有xA∪B，但这不符合集合A和集合B的并集A∪B是B的要求。集合的并A∪B是集合B的要求表明，对于任一xA∪B，同时应有xB。对于那些满足x'A的x'，既然x'A∪B，也应当x'B，因此，在此种情况下集合A应是集合B的子集。7-6设+、*、-是集合的或、与、差运算，试举一个例子，验证A+B=(A-B)+(B-A)+A*B【解答】若设集合A={1,3,4,7,9,15}，集合B={2,3,5,6,7,12,15,17}。则A+B={1,2,3,4,5,6,7,9,12,15,17}又A*B={3,7,15},A–B={1,4,9},B–A={2,5,6,12,17}则(A–B)+(B–A)+A*B={1,2,3,4,5,6,7,9,12,15,17}有A+B=(A–B)+(B–A)+A*B。7-7给定一个用无序链表表示的集合，需要在其上执行operator+(),operator*(),operator-(),Contains(x),AddMember(x),DelMember(x),Min()，试写出它的类声明，并给出所有这些成员函数的实现。【解答】下面给出用无序链表表示集合时的类的声明。templateclassTypeclassSet;//用以表示集合的无序链表的类的前视定义templateclassTypeclassSetNode{//集合的结点类定义friendclassSetListType;private:Typedata;//每个成员的数据SetNodeType*link;//链接指针public:SetNode(constType&item):data(item),link(NULL);//构造函数};templateclassTypeclassSet{//集合的类定义private:140SetNodeType*first,*last;//无序链表的表头指针,表尾指针public:SetList(){first=last=newSetNodeType(0);}//构造函数~SetList(){MakeEmpty();deletefirst;}//析构函数voidMakeEmpty();//置空集合intAddMember(constType&x);//把新元素x加入到集合之中intDelMember(constType&x);//把集合中成员x删去SetType&operator=(SetType&right);//复制集合right到this。SetTypeoperator+(SetType&right);//求集合this与集合right的并SetTypeoperator*(SetType&right);//求集合this与集合right的交SetTypeoperator-(SetType&right);//求集合this与集合right的差intContains(constType&x);//判x是否集合的成员intoperator==(SetType&right);//判集合this与集合right相等Type&Min();//返回集合中的最小元素的值}(1)operator+()templateclassTypeSetTypeSetType::operator+(SetType&right){//求集合this与集合right的并,计算结果通过临时集合temp返回，this集合与right集合不变。SetNodeType*pb=right.first-link;//right集合的链扫描指针SetNodeType*pa,*pc;//this集合的链扫描指针和结果链的存放指针SetTypetemp;pa=first-link;pc=t