2019 北京师范大学数据结构教学资料 第7章――搜索结构ppt课件.ppt

《2019 北京师范大学数据结构教学资料 第7章――搜索结构ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1静态搜索表二叉搜索树AVL树散列第七章搜索结构2搜索(Search)的概念静态搜索表所谓搜索，就是在数据集合中寻找满足某种条件的数据对象。搜索的结果通常有两种可能：搜索成功，即找到满足条件的数据对象。这时，作为结果，可报告该对象在结构中的位置,还可给出该对象中的具体信息。搜索不成功，或搜索失败。作为结果，应报告一些信息,如失败标志、位置等。3通常称用于搜索的数据集合为搜索结构，它是由同一数据类型的对象(或记录)组成。在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。称为关键码。使用基于关键码的搜索，搜索结果应是唯一

2、的。但在实际应用时，搜索条件是多方面的，可以使用基于属性的搜索方法，但搜索结果可能不唯一。实施搜索时有两种不同的环境。静态环境，搜索结构在插入和删除等操作的前后不发生改变。静态搜索表4动态环境，为保持较高的搜索效率,搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。动态搜索表在静态搜索表中，数据元素存放于数组中，利用数组元素的下标作为数据元素的存放地址。搜索算法根据给定值k，在数组中进行搜索。直到找到k在数组中的存放位置或可确定在数组中找不到k为止。静态搜索表5数据表与搜索表的类定义#include

3、ream.h>#includeconstintdefaultSize=100;templateclassdataList;//数据表类的前视定义templateclassdataNode{//数据表中结点类的定义friendclassdataList;//声明其友元类为dataListpublic:6dataNode(constKx):key(x){}//构造函数KgetKey()const{returnkey;}//读取关键码voidsetK

4、ey(Kx){key=x;}//修改关键码private:Kkey;//关键码域Eother;//其他域（视问题而定）};templateclassdataList{//数据表类定义public:7dataList(intsz=defaultSize):ArraySize(sz),CuurentSize(0){Element=newdataNode[sz];assert(Element!=NULL);}dataList(dataList&R);//复制构造函数virtual～data

5、List(){delete[]Element;}//析构函数virtualintLength(){returnCurrentSize;}//求表的长度virtualKgetKey(inti)const{//提取第i（1开始）元素值8assert(i>0

6、

7、i<=CurrentSize);returnElement[i-1].key;}virtualvoidsetKey(Kx,inti){//修改第i（1开始）元素值assert(i>0

8、

9、i<=CurrentSize);Element[i-1].key=x;}virtualintSe

10、qSearch(constKx)const;//搜索virtualboolInsert(E&e1);//插入virtualboolRemove(Kx,E&e1);//删除friendostream&operator<<(ostream&out,constdataList&OutList);//输出9friendistream&operator>>(istream&in,dataList&InList);//输入protected:dataNode*Element;//数据表存储数组intArraySiz

11、e,CurrentSize;//数组最大长度和当前长度};templatebooldataList::Insert(E&e1){//在dataList的尾部插入新元素,若插入失败函数返//回false,否则返回true.10if(CurrentSize==ArraySize)returnfalse;Element[CurrentSize]=e1;//插入在尾端CurrentSize++;returntrue;};templatebooldataList:

12、:Remove(Kx,E&e1){//在dataList中删除关键码为x的元素,通过e1返回。//用尾元素填补被删除元素。if(CurrentSize==0)returnfalse;for(inti==0;i