《数据结构——使用C++语言描述 第2版 普通高等教育“十一五”国家级规划教材 江苏省高等学校精品教材 教学课件 ppt 作者 陈慧南 《数据结构A》第06章》由会员分享，可在线阅读，更多相关《数据结构——使用C++语言描述 第2版 普通高等教育“十一五”国家级规划教材 江苏省高等学校精品教材 教学课件 ppt 作者 陈慧南 《数据结构A》第06章（35页珍藏版）》请在金锄头文库上搜索。
1、南京邮电大学计算机学院 陈慧南 2006年9月,数据结构,Data Structures in C+,南京邮电大学计算机学院 陈慧南 2006年9月,第6章 集合和搜索,南京邮电大学计算机学院 陈慧南 2006年9月,6.1 基本概念 6.2 顺序搜索 6.3 二分搜索,南京邮电大学计算机学院 陈慧南 2006年9月,6.1 基本概念,南京邮电大学计算机学院 陈慧南 2006年9月,6.1.1 集合和搜索的概念,在数学上，集合 是不同对象的无序汇集 ，集合的对象称为元素或成员，每个元素仅出现一 多重集 是元素的无序汇集，其中，每个元素可出现一次或多次。例如， 多重集 1, 1, 2, 3 与
2、1, 2, 3, 1相同，但与 1, 2, 3不同。 通常用大括号表示无序集。 一个有序集是元素的汇集，其中，每个元素可以出现一次或多次，并且它们的出现次序是重要的（如同向量一样）。通常用圆括号表示有序集，例如，（2，1，3）。,南京邮电大学计算机学院 陈慧南 2006年9月,集合结构（简称集合）作为一种数据结构，我们将它视为同类型数据元素的汇集。集合的数据元素之间除了“同属于一个集合”的联系之外没有其它关系。一般地，我们假定所讨论的集合不包含相同元素。数据结构意义上的集合通常是动态的，在集合中可以插入和删除元素，因而被称为动态集 。,南京邮电大学计算机学院 陈慧南 2006年9月,元素类型
3、template struct E operator K ()const return key; K key; D data; ; 其中，K和D是用户定义的数据类型，K被称为关键字类型，key是关键字，我们要求类型K是C/C+语言允许的，可以比较大小的类型。除关键字外的其它数据项归入data域部分，D可以是简单类型，也可以是结构类型。,南京邮电大学计算机学院 陈慧南 2006年9月,关键字是用以标识一个数据元素的某个数据项。 若此关键字可以惟一标识一个元素，则称此关键字为主关键字。集合中，不同数据元素有不同的主关键字值。 称可用以识别若干数据元素的关键字为次关键字。当数据元素是初等数据类型时，
4、其关键字值即数据元素值。 在本章讨论中，若非特殊说明，都假定被搜索的关键字为主关键字。,南京邮电大学计算机学院 陈慧南 2006年9月,搜索：根据给定的某个值，在表中确定一个关键字值等于给定值的数据元素，若表中存在这样的元素，则称搜索成功，搜索结果可以返回整个数据元素，也可指示该元素在表中的地址；若表中不存在关键字值等于给定值的元素，则称搜索不成功（也称搜索失败）。,南京邮电大学计算机学院 陈慧南 2006年9月,搜索算法分类 搜索算法可以按元素是否全部在内存分为：内搜索 和外搜索。我们将对表的搜索称为内搜索，而对文件的搜索称为外搜索。 如果一个搜索算法只是单纯搜索一个元素，称为静态搜索，如果
5、在搜索不成功时，需将被搜索的元素插入表中，这样的搜索被称为动态搜索，这种将搜索和插入结合起来的算法常称为符号表算法，被编译程序用于构造标识符表。 搜索算法还可以根据算法中是否以关键字值间的比较为基础，或由关键字值直接计算元素地址，分为基于关键字比较的搜索和基于计算地址的搜索，本章和第9章的搜索属于前者，第10章的散列表搜索属于后者,南京邮电大学计算机学院 陈慧南 2006年9月,6.1.2 动态集ADT,ADT DynamicSet 数据： 同类元素的有限汇集，其最大允许长度为MaxSetSize。元素由关键字标识，集合的元素各不相同。 运算： Create();创建一个空集合。 Destro
6、y()：撤消一个集合。 IsEmpty():若集合为空，则返回true，否则返回false。 IsFull():若集合满，则返回true，否则返回false。,南京邮电大学计算机学院 陈慧南 2006年9月,Search(x):在表中搜索与x的关键字值相同的元素。如果存在该元素，则将其值赋给x，并且函数返回Success；否则返回NotPresent。 Insert(x):在表中搜索与x的关键字值相同的元素。若表中存在该元素，则将其值赋给x，函数返回Duplicate。否则，若表已满，则函数返回Overflow；若表未满，则在表中插入值为x的元素，函数返回Success。 Remove(x):
7、在表中搜索与x的关键字值相同的元素。如果存在该元素，则将其值赋给x，并从表中删除之，函数返回Success；否则返回NotPresent。 函数返回类型为： enum ResultCode Underflow,Overflow,Success, Duplicate,NotPresent, . ;,南京邮电大学计算机学院 陈慧南 2006年9月,template class DynamicSet public: virtual ResultCode Search(T,南京邮电大学计算机学院 陈慧南 2006年9月,6.1.3 集合的表示,template class ListSet:public
8、 DynamicSet public: ListSet(int mSize); ListSet()delete l; bool IsEmpty()constreturn n=0; bool IsFull()constreturn n=maxSize; ResultCode Search(T,南京邮电大学计算机学院 陈慧南 2006年9月,private: T *l; /指针l指向一个一维数组 int maxSize; int n; ;,南京邮电大学计算机学院 陈慧南 2006年9月,6.2 顺序搜索,南京邮电大学计算机学院 陈慧南 2006年9月,6.2.1 无序表的顺序搜索,template
9、 ResultCode ListSet:Search(T /搜索失败 ,南京邮电大学计算机学院 陈慧南 2006年9月,6.2.2 有序表的顺序搜索,template ResultCode ListSet:Search(T /搜索失败 ,/ lix & in,南京邮电大学计算机学院 陈慧南 2006年9月,6.2.3 平均搜索长度,搜索中所需的关键字值之间的比较次数的期望值，被称为搜索算法的平均搜索长度( average search length ASL) 。,南京邮电大学计算机学院 陈慧南 2006年9月,求成功搜索的平均搜索长度，需要给定表中元素ai被搜索的概率pi。设表长为n，假定每个
10、元素的搜索概率是相等的，即pi=1/n，则程序6.3 在搜索成功时的平均搜索长度为：,南京邮电大学计算机学院 陈慧南 2006年9月,设有序表为（a0,a1,an1），通常可以假定待查元素的值位于a0之前，a0与a1之间，a1与a2之间,an-2与an1之间以及 an1之后的共n+1个区间内的概率是相等的。程序6.4搜索失败的平均搜索长度为：,南京邮电大学计算机学院 陈慧南 2006年9月,6.3 二分搜索,南京邮电大学计算机学院 陈慧南 2006年9月,6.3.1 二分搜索算法,设有一个长度为n的有序表： （a0，a1，an-1） 要求在表中搜索与给定元素x有相同关键字值的元素。 若n=0，
11、则显然搜索失败；若n0，则可将有序表分解成若干个子表，最简单的做法是分成两个子表。 以元素am为划分点，将表分成如下两个子表： （a0，am-1）和（am1，an-1） 将am的关键字值与指定元素x的关键字值作比较，比较结果有三种可能性：,南京邮电大学计算机学院 陈慧南 2006年9月,（续） （1）当xam时，若与x相同关键字值的元素在表中，则必定在子表（am+1,am+2,an1）中，可以在该子表中继续进行搜索。,南京邮电大学计算机学院 陈慧南 2006年9月,对半搜索的例子：“”=low, “”=high (1) key=66，搜索成功 21 30 36 41 52 54 66 72 8
12、3 97 21 30 36 41 52 54 66 72 83 97 21 30 36 41 52 54 66 72 83 97 21 30 36 41 52 54 66 72 83 97 (2) key=35，搜索失败 21 30 36 41 52 54 66 72 83 97 21 30 36 41 52 54 66 72 83 97 21 30 36 41 52 54 66 72 83 97 21 3036 41 52 54 66 72 83 97,南京邮电大学计算机学院 陈慧南 2006年9月,私有函数BSearch定义如下： int ListSet:BSearch(T& x, int
13、 low,int high)const 在范围为low,high的表中搜索与x有相同关键字值的元素；如果存在该元素，则函数返回该元素在表中的位置，否则函数返回1，表示搜索失败。,南京邮电大学计算机学院 陈慧南 2006年9月,template int ListSet:BSearch(T /搜索失败 ,南京邮电大学计算机学院 陈慧南 2006年9月,template ResultCode ListSet:Search( T ,南京邮电大学计算机学院 陈慧南 2006年9月,template ResultCode ListSet:Search(T /搜索失败 ,南京邮电大学计算机学院 陈慧南 20
14、06年9月,6.3.3 二叉判定树,二叉判定树: （1）指定元素x的关键字值与表中元素lm的关键字值之间的一次比较操作，表现为二叉判定树中的一个内结点，用一个圆形结点表示，并用m标识。如果x=lm，则算法在该结点处成功终止。 （2）二叉判定树的根结点，代表算法中首先与x比较的元素lm，用m标识。 （3）结点m的左孩子是当xlm时,算法接下去与x比较的元素下标。,南京邮电大学计算机学院 陈慧南 2006年9月,（4）如果根据算法，在x与lm比较之后有xlm，且算法终止，那么，结点m的右孩子用一个方形结点表示，结点标号为m。方形结点称为外结点。换句话说，如果算法在方形结点m处终止，这意味着： （a
15、）当0mln-1。 （5）从根结点到每个内结点的一条路径代表成功搜索的一条比较路径。如果搜索成功，则算法在内结点处终止，否则算法在外结点处终止。,南京邮电大学计算机学院 陈慧南 2006年9月,南京邮电大学计算机学院 陈慧南 2006年9月,定理6.1 对半搜索算法在成功搜索的情况下，关键字值之间的比较次数不超过log2n+1。对于不成功的搜索，算法需要作log2n或log2n+1次比较。 由定理6.1容易知道， （1）对半搜索算法的成功搜索和搜索失败的最坏情况时间复杂度分别为 Ws(n)=Wu(n)=O(log2n)， （2）搜索失败的平均情况时间复杂度为 Au(n)= O(log2n)。,南京邮电大学计算机学院 陈慧南 2006年9月,定理6.2 对半搜索算法在搜索成功时的平均时间复杂度为O(log2n)。 对于成功搜索，假定查找表中任何一个元素的概率是相等的，为1/n。 对于失败搜索，假定待查元素x的值落在区间（lm，lm+1），0mln-1，总共 n+1个区间中的概率是相等的。,南京邮电大学计算机学院 陈慧南 2006年9月,那么， As(n)=(I+n)/n=I/n+1，Au(n)=E/(n+1)=O(log2n) 这里，I是二叉判定树的内路径长度，E是外路径长度。从定理71可知，E=I+2n，因此， As(n)=(1+
