数据结构7搜索结构

《数据结构7搜索结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章搜索结构本章要点：静态搜索表的顺序搜索与折半搜索二叉搜索树的表示、搜索、插入、删除算法AVL树的平衡化及相应算法静态搜索表搜索(Search)的概念所谓搜索，就是在数据集合中寻找满足某种条件的数据对象。搜索的结果通常有两种可能：搜索成功，即找到满足条件的数据对象。这时，作为结果，可报告该对象在结构中的位置，还可进一步给出该对象中的具体信息。搜索不成功，或搜索失败。作为结果，也应报告一些信息，如失败标志、失败位置等。通常称用于搜索的数据集合为搜索结构，它是由同一数据类型的对象(或记录)组成。在每一个对象中有若干属性，其中应当有一个属性，其值可唯一地标识这个对象。它称为

2、关键码。使用基于关键码的搜索，搜索结果应是唯一的。但在实际应用时，搜索条件是多方面的，这样，可以使用基于属性的搜索方法，但搜索结果可能不唯一。实施搜索时有两种不同的环境。静态环境，搜索结构在执行插入和删除等操作的前后不发生改变。静态搜索表动态环境，为保持较高的搜索效率，搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。动态搜索表静态搜索表结构templateclassdataList;templateclassNode{friendclassdataList;public:Node(const

3、Type&value):key(value){}TypegetKey()const{returnkey;}voidsetKey(Typek){key=k;}private:Typekey;other;};templateclassdataList{public:dataList(intsz=10):ArraySize(sz),Element(newNode[sz]){}virtual~dataList(){delete[]Element;}friendostream&operator<<(ostream&OutStream,constda

4、taList&OutList);friendistream&operator>>(istream&InStream,dataList&InList);protected:Type*Element;intArraySize,CurrentSize;};templateclasssearchList:publicdataList{//作为派生类的静态搜索表的类定义public:searchList(intsz=10):dataList(sz){}virtual~searchList(){}virtualin

5、tSearch(constType&x)const;};templateistream&operator>>(istream&InStream,dataList&InList){//从输入流对象InStream输入数据到数据表InListcout<<“输入数组当前大小:”;Instream>>InList.CurrentSize;cout<<“输入数组元素值:”;for(inti=0;i>InList.Element[i];}re

6、turnInStream;}templateostream&operator<<(ostream&OutStream,constdataList&OutList){//将数据表OutList内容输出到输出流对象OutStreamOutStream<<“数组内容:”;for(inti=0;i

7、turnOutStream;}衡量一个搜索算法的时间效率的标准是：在搜索过程中关键码的平均比较次数或平均读写磁盘次数(只适合于外部搜索)，这个标准也称为平均搜索长度ASL(AverageSearchLength)，通常它是搜索结构中对象总数m或文件结构中物理块总数n的函数。另外衡量一个搜索算法还要考虑算法所需要的存储量和算法的复杂性等问题。在静态搜索表中，数据对象存放于数组中，利用数组元素的下标作为数据对象的存放地址。搜索算法根据给定值x，在数组中进行搜索。直到找到x在数组中的存放位置或可确定在数组中找不到x为止。顺序搜索(S