清华 殷人昆C++数据结构课件数据结构第7章.doc

《清华 殷人昆C++数据结构课件数据结构第7章.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第7章集合与搜索一、复习要点集合是最基本的抽象数据类型之一。本章讨论了集合的三种存储表示：位数组表示、有序链表表示、并查集。在本章的后半部分，讨论了与集合相关的搜索方法和简单的性能分析方法，包括适用于静态搜索表的顺序搜索和折半搜索及代表动态搜索表的二叉搜索树和AVL树。可以使用扩充的二叉搜索树描述顺序搜索和折半搜索，从而推导出估算搜索效率的公式。静态搜索表在整个程序的运行期间结构不会变化，其搜索效率随着表中对象的个数n不断增长。动态搜索表因各个对象的输入顺序不同，得到的搜索表的形态不同，典型的是二叉搜索树。在具有n个对象的二叉搜索树中，搜索效率最高的是高度

2、最低的二叉搜索树。为确保二叉搜索树始终保持搜索效率最高，必须在输入新的对象时判断二叉搜索树是否“失去平衡”，并进行适当的平衡旋转，使二叉搜索树的高度降到最低。这就是AVL树。在AVL树的讨论中，4种平衡旋转，选择参加平衡旋转的3个结点是关键，必须加以注意。本章复习的要点是：1、基本知识点必须理解集合及其表示方法，包括位数组表示、有序链表表示及其相关操作的实现算法集合及其表示。理解并查集实现的方法。理解搜索的概念，理解静态搜索表结构，掌握静态搜索表的顺序搜索和折半搜索算法及其性能分析方法。掌握二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法，掌握AVL

3、树的构造、插入、删除时的调整方法及其性能分析，重点是AVL树的定义、平衡化旋转、AVL树的插入和删除、AVL树的高度。2、算法设计Ø用有序链表表示集合时的求集合的并、交、差的算法Ø并查集中的构造函数、求根及合并算法Ø并查集中根据树的高度和根据树中结点个数进行合并的算法Ø设置监视哨的顺序搜索算法和不设监视哨的顺序搜索算法Ø有序顺序表的顺序搜索算法Ø有序顺序表的折半搜索的递归算法和非递归算法Ø二叉搜索树的搜索、插入和删除算法Ø计算AVL树中指定结点高度的递归算法及利用此算法计算结点平衡因子的算法二、难点和重点1、集合的概念：集合的基本运算、集合的存储表示Ø用位

4、数组表示集合时集合基本运算的实现Ø用有序链表表示集合时集合基本运算的实现2、并查集：并查集定义、并查集的三种基本运算的实现3、基本搜索方法Ø对一般表的顺序搜索算法(包括有监视哨和没有监视哨)Ø对有序顺序表的顺序搜索算法，包括递归和非递归算法Ø用判定树(即扩充二叉搜索树)描述有序顺序表的顺序搜索，以及平均搜索长度(成功与不成功)的计算。Ø对有序顺序表的折半搜索算法、包括递归和非递归算法Ø用判定树(即扩充二叉搜索树)描述有序顺序表的折半搜索，以及平均搜索长度(成功与不成功)的计算。4、二叉搜索树Ø动态搜索树与静态搜索树的特性Ø二叉搜索树的定义、二叉搜索树上的递

5、归和非递归搜索算法Ø二叉搜索树搜索时的平均搜索长度(成功与不成功)的计算Ø二叉搜索树的插入与删除算法Ø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={

6、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试编写一个算法，打印一个有穷集合中的所有成员。要求使用集合抽象数据类型中的基本操作。如果集合中包含有子集合，各个子集合之间没有重复的元素，采用什么结构比较合适。【解答】集合抽象数据类型的部分内容templateclassSet{//对

7、象:零个或多个成员的聚集。其中所有成员的类型是一致的,但没有一个成员是相同的。intContains(constTypex);//判元素x是否集合this的成员intSubSet(Set&right);//判集合this是否集合right的子集intoperator==(Set&right);//判集合this与集合right是否相等intElemtype();//返回集合元素的类型TypeGetData();//返回集合原子元素的值charGetName();//返回集合this的集合名Set*GetSubSet();

8、//返回集合this的子集合地址Set*GetNext