数据结构7搜索结构.ppt

第七章搜索结构静态搜索表在每一个对象中有若干属性，其中应当有一个属性，其值可唯一地标识这个对象。它称为关键码。使用基于关键码的搜索，搜索结果应是唯一的。但在实际应用时，搜索条件是多方面的，这样，可以使用基于属性的搜索方法，但搜索结果可能不唯一。
实施搜索时有两种不同的环境。
静态环境，搜索结构在执行插入和删除等操作的前后不发生改变。静态搜索表
动态环境，为保持较高的搜索效率，搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。动态搜索表
静态搜索表结构template<classType>classdataList{
public:
dataList(intsz=10):ArraySize(sz),
Element(newNode<Type>[sz]){}
virtual~dataList(){delete[]Element;}
friendostream&operator<<(ostream&
OutStream,constdataList<Type>&OutList);
friendistream&operator>>(istream&
InStream,dataList<Type>&InList);
protected:
Type*Element;
intArraySize,CurrentSize;
};
template<classType>classsearchList:
publicdataList<Type>{
//作为派生类的静态搜索表的类定义
public:
searchList(intsz=10):dataList<Type>(sz){}
virtual~searchList(){}
virtualintSearch(constType&x)const;
};

template<classType>istream&operator>>
(istream&InStream,dataList<Type>&InList){
//从输入流对象InStream输入数据到数据表InList
cout<<“输入数组当前大小:”;
Instream>>InList.CurrentSize;
cout<<“输入数组元素值:\n”;
for(inti=0;i<InList.CurrentSize;i++){
cout<<“元素”<<i<<“:”;
InStream>>InList.Element[i];
}
returnInStream;
}
template<classType>ostream&operator<<
(ostream&OutStream,constdataList<Type>
&OutList){
//将数据表OutList内容输出到输出流对象OutStream
OutStream<<“数组内容:\n”;
for(inti=0;i<OutList.CurrentSize;i++)
OutStream<<OutList.Element[i]<<‘’;
OutStream<<endl;
OutStream<<“数组当前大小:”<<
OutList.CurrentSize<<endl;
returnOutStream;
}
衡量一个搜索算法的时间效率的标准是：在搜索过程中关键码的平均比较次数或平均读写磁盘次数(只适合于外部搜索)，这个标准也称为平均搜索长度ASL(AverageSearchLength)，通常它是搜索结构中对象总数m或文件结构中物理块总数n的函数。
另外衡量一个搜索算法还要考虑算法所需要的存储量和算法的复杂性等问题。
在静态搜索表中，数据对象存放于数组中，利用数组元素的下标作为数据对象的存放地址。搜索算法根据给定值x，在数组中进行搜索。直到找到x在数组中的存放位置或可确定在数组中找不到x为止。顺序搜索(SequentialSearch)template<classType>intsearchList<Type>::
Search(constType&x)const{
//顺序搜索的迭代算法，0号元素为监视哨
Element[0].setKey(x);inti=CurrentSize;
while(Element[i].getKey()!=x)i--;
returni;
}

template<classType>intearchList<Type>::
Search(constType&x,int&loc)const{
//顺序搜索的递归算法
if(loc>=CurrentSize)return-1;
elseif(Element[loc].getKey()==x)returnloc;
elsereturnSearch(x,loc+1);
}
constintSiz