06章 集合和搜索

《06章 集合和搜索》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构DataStructuresinC++南京邮电大学计算机学院陈慧南第6章集合和搜索南京邮电大学计算机学院陈慧南6.1基本概念6.2顺序搜索6.3二分搜索南京邮电大学计算机学院陈慧南6.1基本概念南京邮电大学计算机学院陈慧南6.1.1集合和搜索的概念在数学上，集合是不同对象的无序汇集，集合的对象称为元素或成员，每个元素仅出现一多重集是元素的无序汇集，其中，每个元素可出现一次或多次。例如，多重集{1,1,2,3}与{1,2,3,1}相同，但与{1,2,3}不同。通常用大括号表示无序集。一个有序集是元素的汇集，其中，每个元素可以出现一次

2、或多次，并且它们的出现次序是重要的（如同向量一样）。通常用圆括号表示有序集，例如，（2，1，3）。南京邮电大学计算机学院陈慧南集合结构（简称集合）作为一种数据结构，我们将它视为同类型数据元素的汇集。集合的数据元素之间除了“同属于一个集合”的联系之外没有其它关系。一般地，我们假定所讨论的集合不包含相同元素。数据结构意义上的集合通常是动态的，在集合中可以插入和删除元素，因而被称为动态集。南京邮电大学计算机学院陈慧南元素类型templatestructE{operatorK()const{returnkey;}Kk

3、ey;Ddata;};其中，K和D是用户定义的数据类型，K被称为关键字类型，key是关键字，我们要求类型K是C/C++语言允许的，可以比较大小的类型。除关键字外的其它数据项归入data域部分，D可以是简单类型，也可以是结构类型。南京邮电大学计算机学院陈慧南关键字是用以标识一个数据元素的某个数据项。若此关键字可以惟一标识一个元素，则称此关键字为主关键字。集合中，不同数据元素有不同的主关键字值。称可用以识别若干数据元素的关键字为次关键字。当数据元素是初等数据类型时，其关键字值即数据元素值。在本章讨论中，若非特殊说明，都假定被搜索的关键字为主关

4、键字。南京邮电大学计算机学院陈慧南搜索：根据给定的某个值，在表中确定一个关键字值等于给定值的数据元素，若表中存在这样的元素，则称搜索成功，搜索结果可以返回整个数据元素，也可指示该元素在表中的地址；若表中不存在关键字值等于给定值的元素，则称搜索不成功（也称搜索失败）。南京邮电大学计算机学院陈慧南搜索算法分类搜索算法可以按元素是否全部在内存分为：内搜索和外搜索。我们将对表的搜索称为内搜索，而对文件的搜索称为外搜索。如果一个搜索算法只是单纯搜索一个元素，称为静态搜索，如果在搜索不成功时，需将被搜索的元素插入表中，这样的搜索被称为动态搜索，这种将

5、搜索和插入结合起来的算法常称为符号表算法，被编译程序用于构造标识符表。搜索算法还可以根据算法中是否以关键字值间的比较为基础，或由关键字值直接计算元素地址，分为基于关键字比较的搜索和基于计算地址的搜索，本章和第9章的搜索属于前者，第10章的散列表搜索属于后者南京邮电大学计算机学院陈慧南6.1.2动态集ADTADTDynamicSet{数据：同类元素的有限汇集，其最大允许长度为MaxSetSize。元素由关键字标识，集合的元素各不相同。运算：Create();创建一个空集合。Destroy()：撤消一个集合。IsEmpty():若集合为空，则

6、返回true，否则返回false。IsFull():若集合满，则返回true，否则返回false。南京邮电大学计算机学院陈慧南Search(x):在表中搜索与x的关键字值相同的元素。如果存在该元素，则将其值赋给x，并且函数返回Success；否则返回NotPresent。Insert(x):在表中搜索与x的关键字值相同的元素。若表中存在该元素，则将其值赋给x，函数返回Duplicate。否则，若表已满，则函数返回Overflow；若表未满，则在表中插入值为x的元素，函数返回Success。Remove(x):在表中搜索与x的关键字值相同的

7、元素。如果存在该元素，则将其值赋给x，并从表中删除之，函数返回Success；否则返回NotPresent。}函数返回类型为：enumResultCode{Underflow,Overflow,Success,Duplicate,NotPresent,...};南京邮电大学计算机学院陈慧南templateclassDynamicSet{public:virtualResultCodeSearch(T&x)const=0;virtualResultCodeInsert(T&x)=0;virtualResultCodeRemo

8、ve(T&x)=0;virtualboolIsEmpty()const=0;virtualboolIsFull()const=0;};南京邮电大学计算机学院陈慧南6.1.3集合的表示templ