数据结构7搜索结构.ppt

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

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

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

3、aList;public:Node(constType&value):key(value){}TypegetKey()const{returnkey;}voidsetKey(Typek){key=k;}private:Typekey;other;};4templateclassdataList{public:dataList(intsz=10):ArraySize(sz),Element(newNode[sz]){}virtual~dataList(){delete[]Element;}friendo

4、stream&operator<<(ostream&OutStream,constdataList&OutList);friendistream&operator>>(istream&InStream,dataList&InList);protected:Type*Element;intArraySize,CurrentSize;};5templateclasssearchList:publicdataList{//作为派生类的静态搜索表的类定义public:searchList(ints

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

6、ist.CurrentSize;i++){cout<<“元素”<>InList.Element[i];}returnInStream;}7templateostream&operator<<(ostream&OutStream,constdataList&OutList){//将数据表OutList内容输出到输出流对象OutStreamOutStream<<“数组内容:”;for(inti=0;i

7、ist.Element[i]<<‘’;OutStream<

8、利用数组元素的下标作为数据对象的存放地址。搜索算法根据给定值x，在数组中进行搜索。直到找到x在数组中的存放位置或可确定在数组中找不到x为