清华数据结构课件

集合及其表示等价类与并查集静态搜索表二叉搜索树最佳二叉搜索树AVL树第七章集合与搜索集合基本概念集合及其表示集合是成员(对象或元素)的一个群集。集合中的成员可以是原子(单元素)，也可以是集合。集合的成员必须互不相同。在算法与数据结构中所遇到的集合，其单元素通常是整数、字符、字符串或指针，且同一集合中所有成员具有相同的数据类型。

colour

={red,orange,yellow,green,black,blue,purple,white}

name

={“An”,“Cao”,“Liu”,“Ma”,“Peng”,“Wang”,“zhang”}集合中的成员一般是无序的，但在表示它时，常写在一个序列里。常设定集合中的单元素具有线性有序关系，此关系可记作“<”，表示“优先于”。整数、字符和字符串都有一个自然线性顺序。指针也可依据其在序列中安排的位置给予一个线性顺序。集合(Set)的抽象数据类型template<classType>classSet{Set(intMaxSetSize):MaxSize(MaxSetSize);

voidMakeEmpty(Set&s);

intAddMember(Set&s,constTypex);

intDelMember(Set&s,constType&x);AB或

A+BAB或

ABA-BAAABBB

void

Assign

(Set&s1,Set&s2);

void

Union

(Set&s1,Set&s2);

voidIntersection

(Set&s1,Set&s2);

void

Difference

(Set&s1,Set&s2);

intContains(Set&s,constType&x);

intEqual(Set&s1,Set&s2);

intSubSet(Set&s1,Set&s2);}用位向量实现集合抽象数据类型

当集合是全集合{0,1,2,…,n}的一个子集，且n是不大的整数时，可用位(0,1)向量来实现集合。当全集合是由有限的可枚举的成员组成的集合时，可建立全集合成员与整数0,1,2,…的一一对应关系，用位向量来表示该集合的子集。集合的位向量(bitVector)类的定义#include<assert.h>constintDefaultSize=100;classSet{private:int*bitVector;

intMaxSize;public:Set(intMaxSetSize=DefaultSize);~Set(){delete[]bitVector;}

voidMakeEmpty(){for(inti=0;i<MaxSize;i++)bitVector[i]=0;

}

intGetMember(constintx){

returnx>=0&&x<MaxSize?

bitVector[x]:

-1;}

intAddMember(constintx);

intDelMember(constintx);Setoperator=(Set&right);Setoperator+(Set&right);

Setoperator*(Set&right);Setoperator

-(Set&right);

intContains(constintx);

intSubSet(Set&right);

intoperator==(Set&right);};使用示例Sets1,s2,s3,s4,s5;

intindex,equal;

for(intk=0;k<10;k++)//集合赋值{

s1.AddMember(k);s2.AddMember(k+7);}

//s1:{0,1,2,…,9},s2:{7,8,9,…,16}

s3=s1+s2;//求s1与s2的并

{0,1,…,16}s4=s1*s2;//求s1与s2的交

{

7,8,9}

s5=s1-s2;//求s1与s2的差

{0,1,…,6}

//s1:{0,1,2,…,9}

index=s1.SubSet(s4);//判断s1是否为s4子集

cout<<index<<endl;//结果，index=0

//s1:{0,1,2,3,4,5,6,7,8,9}//s4:{7,8,9}equal=s1==s2;

//集合s1与s2比较相等

cout<<equal<<endl;

//为0,两集合不等用位向量实现集合时部分操作的实现Set::Set(intMaxSetSize):

MaxSize(MaxSetSize){

assert(MaxSize>0); bitVector=newint[MaxSize];

assert(bitVector!=0);

for(inti=0;i<MaxSize;i++)bitVector[i]=0;}intSet::Addmember(constintx){

assert(x>=0&&x<MaxSize

);if(!bitVector[x])

{bitVector[x]=1;

return1;

}

return0;}intSet::DelMember(constintx){

assert(x>=0&&x<MaxSize);

if(bitVector[x])

{bitVector[x]=0;

return1;

}

return0; }Set&Set::operator=(Set&right){assert(MaxSize==right.MaxSize);for(inti=0;i<MaxSize;i++)bitVector[i]=right.bitVector[i]; return*this;}intSet::Contains(constintx){

assert(x>=0&&x<MaxSize);

returnbitVector[x]; }SetSet::operator+(Set&right){

assert(MaxSize==right.MaxSize);Settemp(MaxSize);

for(inti=0;i<MaxSize;i++)temp.bitVector[i]=bitVector[i]||right.bitVector[i];returntemp;}thisrighttemp011100001100010010101001110101110SetSet::operator*(Set&right){

assert(MaxSize==right.MaxSize);Settemp(MaxSize);for(inti=0;i<MaxSize;i++)temp.bitVector[i]=bitVector[i]&&right.bitVector[i];returntemp;}thisrighttemp011100001100010010101000100000010SetSet::operator

-(Set&right){

assert(MaxSize==right.MaxSize);Settemp(MaxSize);

for(inti=0;i<MaxSize;i++)

temp.bitVector[i]=bitVector[i]&&!right.bitVector[i];returntemp;}thisrighttemp011100001100010010101001010000100intSet::operator

==(Set&right){

assert(MaxSize==right.MaxSize);

for(inti=0;i<MaxSize;i++)

if(bitVector[i]!=right.bitVector[i])

return0;

return1;}thisright0011000011000100101010iintSet::SubSet(Set&right){

assert(MaxSize==right.MaxSize);

for(inti=0;i<MaxSize;i++)

if(bitVector[i]&&!right.bitVector[i])

return0;

return1;

}thisright00110000110001001010100001i用有序链表实现集合的抽象数据类型用带表头结点的有序链表表示集合firstfirst081723354972用有序链表来表示集合时，链表中的每个结点表示集合的一个成员。各结点所表示的成员e0,e1,…,en

在链表中按升序排列，即e0<e1<…<en。集合成员可以无限增加。因此，用有序链表可以表示无穷全集合的子集。template<classType>classSetList;

template<classType>

classSetNode{friendclassSetList<Type>;public:SetNode(constType&item):

data(item),link(NULL); private:

Typedata; SetNode<Type>*link;};集合的有序链表类的定义template<classType>classSetList{private:SetNode<Type>*first,*last;

//有序链表的表头指针,表尾指针public:

SetList()//构造函数

{first=last=newSetNode<Type>(0);}~SetList(){MakeEmpty();deletefirst;}voidMakeEmpty();//置空集合

intAddMember(constType&x);intDelMember(constType&x);SetList<Type>&operator=(SetList<Type>&

right);//将集合right赋给集合thisSetList<Type>operator+(SetList<Type>&

right);

//求集合this与集合right的并SetList<Type>operator*(SetList<Type>&

right);//求集合this与集合right的交SetList<Type>operator-(SetList<Type>&

right); //求集合this与集合right的差intContains(constType&x); //判x是否集合的成员int

operator

==(SetList<Type>&right); //判集合this与集合right相等Type&Min();//返回集合中最小元素值

Type&Max();//返回集合中最大元素值}

集合的搜索、加入和删除操作template<classType>intSetList<Type>::Contains(constType&x){//若x是集合成员,则函数返回1,否则返回0SetNode<Type>*temp=first->link;

while(temp!=NULL&&temp->data<x)temp=temp->link; //循链搜索if(temp!=NULL&&temp->data==x)

return1; //找到,返回1elsereturn0; //未找到,返回0}template<classType>intSetList<Type>::AddMember(constType&x){SetNode<Type>*p=first->link,*q=first;

while(p!=NULL&&p->data<x)

{q=p;p=p->link;

}//循链扫描

if(p!=NULL&&p->data==x)return0;

//集合中已有此元素

SetNode<Type>*s=newSetNode(x);s->link=p;q->link=s;//链入

if(p==NULL)last=s;

//链到链尾时改链尾指针

return1;}template<classType>intSetList<Type>::DelMember(constType&x){SetNode<Type>*p=first->link,*q=first;

while(p!=NULL&&p->data<x)

{q=p;p=p->link;

}

//循链扫描if(p!=NULL&&p->data==x){//找到

q->link=p->link; //重新链接

if(p==last)last

=q;

//删去链尾结点时改链尾指针

deletep;

return1; //删除含x结点

}

elsereturn0; //集合中无此元素}用有序链表表示集合时的几个重载函数template<classType>SetList<Type>&SetList<Type>::operator=(

SetList<Type>&right){//复制集合right到thisSetNode<Type>*pb=right.first->link;//源

SetNode<Type>*pa=first=//目标

newSetNode<Type>;while(pb!=NULL){ //逐个结点复制

pa->link=newSetNode<Type>(pb->data);pa=pa->link;pb=pb->link;

}pa->link=NULL;last

=pa;return*this; //目标链表收尾}//求集合this与集合right的并,结果通过临时//集合temp返回，this集合与right集合不变。

template<classType>SetList<Type>SetList<Type>::operator+(SetList<Type>&right){firstright.first08172349temp.first231735papbpc0817233549

SetNode<Type>*pb=right.first->link;SetNode<Type>*pa=first->link;

SetList<Type>temp;SetNode<Type>*pc=temp.first;

while(pa!=NULL&&pb!=NULL){

if(pa->data==pb->data) {//共有元素

pc->link=newSetNode<Type>(pa->data);

pa=pa->link;pb=pb->link;

}

elseif(pa->data<pb->data){

pc->link=newSetNode<Type>(pa->data);

pa=pa->link;}

else {//pa->data>pb->data

pc->link=newSetNode<Type>(pb->data);

pb=pb->link;

}pc=pc->link;

}

if(pa!=NULL)pb=pa;//pb指未扫完集合

while(pb!=NULL){

//向结果链逐个复制

pc->link=newSetNode<Type>(pb->data);

pc=pc->link;pb=pb->link;

}pc->link=NULL;temp.last=pc; //链表收尾

returntemp;}template<classType>int

SetList<Type>::operator==(SetList<Type>&right){SetNode<Type>*pb=right.first->link;SetNode<Type>*pa=first->link;

while(pa!=NULL&&pb!=NULL)

if(pa->data==pb->data) //相等,继续

{pa=pa->link;pb=pb->link;

}

elsereturn0;//不等时中途退出,返回0

if(pa!=NULL||pb!=NULL)return0;

//链不等长时,返回0

return1;}等价关系与等价类(EquivalenceClass)等价类与并查集在求解实际应用问题时常会遇到等价类问题。从数学上看，等价类是一个对象(或成员)的集合，在此集合中所有对象应满足等价关系。若用符号“”表示集合上的等价关系，那么对于该集合中的任意对象x,y,

z，下列性质成立：自反性：xx(即等于自身)。对称性：若x

y,则y

x。传递性：若x

y且y

z,则x

z。因此，等价关系是集合上的一个自反、对称、传递的关系。

“相等”(=)就是一种等价关系，它满足上述的三个特性。一个集合S

中的所有对象可以通过等价关系划分为若干个互不相交的子集S1,S2,S3,…，它们的并就是

S。这些子集即为等价类。确定等价类的方法分两步走。第一步，读入并存储所有的等价对(i,j)；第二步，标记和输出所有的等价类。voidequivalence

(){

初始化;

while等价对未处理完

{读入下一个等价对

(i,j);

存储这个等价对

;}

输出初始化;

for(尚未输出的每个对象)

输出包含这个对象的等价类

;}给定集合

S={0,1,2,3,4,5,6,7,8,9,10,11},及如下等价对:

0

4,3

1,6

10,8

9,7

4,

6

8,3

5,2

11,11

0初始

{0},{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}0

4

{0,4},{1},{2},{3},{5},{6},{7},{8},{9},{10},{11}3

1

{0,4},{1,3},{2},{5},{6},{7},{8},{9},{10},{11}6

10{0,4},{1,3},{2},{5},{6,10},{7},{8},{9},{11}

8

9

{0,4},{1,3},{2},{5},{6,10},{7},{8,9},{11}7

4

{0,4,7},{1,3},{2},{5},{6,10},{8,9},{11}6

8

{0,4,7},{1,3},{2},{5},{6,8,9,10},{11}3

5

{0,4,7},{1,3,5},{2},{6,8,9,10},{11}2

11{0,4,7},{1,3,5},{2,11},{6,8,9,10}11

0{0,2,4,7,11},{1,3,5},{6,8,9,10}确定等价类的链表方法

设等价对个数为m,对象个数为n。一种可选的存储表示为单链表。可为集合的每一对象建立一个带表头结点的单链表，并建立一个一维的指针数组seq[n]

作为各单链表的表头结点向量。seq[i]是第i个单链表的表头结点,第i个单链表中所有结点的data

域存放在等价对中与i等价的对象编号。

当输入一个等价对(i,j)

后,就将集合元素i链入第j个单链表，且将集合元素

j链入第i个单链表。

在输出时,设置一个布尔数组out[n],用out[i]

标记第i

个单链表是否已经输出。算法的输出从编号i=0

的对象开始,对所有的对象进行检测。在i=0

时,循第0

个单链表先找出形式为(0,j)的等价对,把

0和j

作为同一个等价类输出。再根据等价关系的传递性,找所有形式为(j,k)的等价对,把

k也纳入包含0的等价类中输出。如此继续，直到包含0的等价类完全输出为止。接着再找一个未被标记的编号,如i=1，该对象将属于一个新的等价类，再用上述方法划分、标记和输出这个等价类。在算法中使用了一个栈。每次输出一个对象编号时，都要把这个编号进栈，记下以后还要检测输出的等价对象的单链表。等价类链表的定义enumBoolean{False,True};

classListNode{ //定义链表结点类

friendvoidequivalence();

private:

intdata; //结点数据

ListNode*link; //结点链指针

ListNode(intd){data=d;link=NULL;}

};typedefListNode*ListNodePtr;建立等价类算法(输入等价对并输出等价类)每当一个对象的单链表检测完，就需要从栈中退出一个指针，以便继续输出等价类中的其它对象。如果栈空，说明该等价类所有对象编号都已输出，再找一个使得out[i]==False

的最小的i，标记并输出下一个等价类。voidequivalence(){

ifstreaminFile("equiv.in",ios::in);

//输入文件

if(!inFile){

cerr<<“不能打开输入文件"<<endl;exit(1);}inti,j,n;

inFile>>n; //读入对象个数

seq=newListNodePtr[n];

out=newBoolean[n];//初始化seq和out

for(i=0;i<n;i++)

{seq[i]=0;out[i]=False;

}inFile>>i>>j; //输入等价对

(i,j)

while(inFile.good()){ //文件结束出循环

x=newListNode(j);//创建结点

j

x->link=seq[i];

seq[i]=x;//链入第i个链表

y=newListNode(i);//创建结点iy->link=seq[j];

seq[j]=y;//链入第j个链表

inFile>>i>>j; //输入下一个等价对

}for

(i=0;i<n;i++)

if(out[i]==False){ //未输出,需要输出

cout<<endl<<“Anewclass:”<<i;//输出

out[i]=True; //作输出标记

ListNode*x=seq[i];

//取第i链表头指针

ListNode*top=NULL;//栈初始化

while(1){ //找类的其它成员

while(x){ //处理链表,直到

x=0

j=x->data; //成员j

if(out[j]==False){//未输出,输出

cout<<“,”<<j;out[j]=True;

ListNode*y=x->link;x->link=top;top=x;//结点x进栈

x=y; //x进到链表下一个结点

}

elsex=x->link;//已输出过,跳过

}

if

(top==NULL)break;

//栈空退出循环

else{

x=seq[top->data];

top=top->link;}

//栈不空,退栈,x是根据结点编号回

//溯的另一个链表的头指针

}

}

delete

[]

seq;

delete[]

out;}并查集

(Union-FindSets)并查集支持以下三种操作：

Union(Root1,Root2)

//并操作

Find(x)

//搜索操作

UFSets(s)

//构造函数对于并查集来说，每个集合用一棵树表示。为此，采用树的双亲表示作为集合存储表示。集合元素的编号从0到n-1。其中n

是最大元素个数。在双亲表示中，第i

个数组元素代表包含集合元素i的树结点。根结点的双亲为-1，表示集合中的元素个数。在同一棵树上所有结点所代表的集合元素在同一个子集合中。为此，需要有两个映射：集合元素到存放该元素名的树结点间的对应；集合名到表示该集合的树的根结点间的对应。设S1={0,6,7,8},S2={1,4,9},S3={2,3,5}集合名指针0

S11

S22

S30427681935为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合。初始时,用构造函数UFSets(s)构造一个森林,每棵树只有一个结点,表示集合中各元素自成一个子集合

S[i]=-1,i=0,1,…,n-1

。用Find(i)寻找集合元素i的根。如果有两个集合元素i和j:

Find(i)==Find(j),

表明这两个元素在同一个集合中，如果两个集合元素i和j不在同一个集合中,可用Union(i,j)

将它们合并到一个集合中。S1下标parent集合S1,S2和S3的双亲表示-4

4

-3

2

-3

2000401234567890768419235S2S3S1

S2的可能的表示方法下标parent集合S1

S2

和S3

的双亲表示-7

4

-320

2000

4012345678907684194190876constintDefaultSize=10;classUFSets{ //并查集类定义private:

int*parent; //集合元素数组

intsize; //集合元素的数目public:UFSets(ints=DefaultSize);//构造函数

~UFSets(){

delete[]parent;}//析构函数

constUFSets&

operator=(UFSets&right);

//重载函数：集合赋值

voidUnion(intRoot1,intRoot2);

//基本例程

:

两个子集合合并intFind(intx);

//基本例程

:搜寻集合x的根

voidUnionByHeight(intRoot1,intRoot2);

//改进例程

:压缩高度的合并算法};UFSets::UFSets(ints){

//构造函数

size=s;

//集合元素个数

parent=newint[size];

//双亲指针数组

for(inti=0;i<size;i++)parent[i]=-1;

//每一个自成一个单元素集合}

并查集操作的算法

查找-5012301234Find(4)Find

(3)=3

Find(2)=2Find(1)=1Find(0)=0

=-5<0

结束int

UFSets::Find(intx){if(parent[x]<0)returnx;elsereturnFind(parent[x]);}

-50123parentParent[4]=3Parent[3]=2Parent[2]=1Parent[1]=0Parent[0]=-501234voidUFSets::Union(intRoot1,intRoot2){//求两个不相交集合Root1与Root2的并

parent[Root1]+=parent[Root2];

parent[Root2]=Root1;

//将Root2连接到Root1下面}Find和Union操作性能不好。假设最初n个元素构成n棵树组成的森林，parent[i]=-1。做处理Union(n-2,n-1),…,Union(1,2),Union(0,1)后，将产生退化的树。合并-1-1-1-1-10234-3-503213341332202314Union(0,1)-23-41421234Union(1,2)Union(2,3)Union(3,4)

执行一次Union操作所需时间是O(1)，n-1次Union操作所需时间是O(n)。若再执行Find(0),Find(1),…,Find(n-1),若被搜索的元素为i，完成Find(i)操作需要时间为O(i)，完成n次搜索需要的总时间将达到改进的方法按树的结点个数合并按树的高度合并压缩元素的路径长度按树结点个数合并结点个数多的树的根结点作根-1-1-1-1-101234-1-10-7256-5-222332013456233020562314Union(2,0)voidUFSets::WeightedUnion(intRoot1,intRoot2){//按Union的加权规则改进的算法

inttemp=parent[Root1]+parent[Root2];if(parent[Root2]<parent[Root1]){

parent[Root1]=Root2;//Root2中结点数多

parent[Root2]=temp;//Root1指向Root2}

else{

parent[Root2]=Root1;//Root1中结点数多

parent[Root1]=temp;//Root2指向Root1

}}按树高度合并高度高的树的根结点作根-0-0-0-0-001234-0-00-2256-2-122332013456233020562314Union(2,0)Union操作的折叠规则为进一步改进树的性能，可以使用如下折叠规则来“压缩路径”。即：如果j是从i到根的路径上的一个结点，且parent[j]root[j]，则把parent[j]置为root[i]。0067867819193535从i=5

压缩路径intUFSets::CollapsingFind(inti){//使用折叠规则的搜索算法

for(intj=i;parent[j]>=0;j=parent[j]);

//让

j

循双亲指针走到根

while(i!=j){

//换

parent[i]

到

jinttemp=parent[i];

parent[i]=j;i=temp;}

returnj;}

搜索(Search)的概念静态搜索表

所谓搜索，就是在数据集合中寻找满足某种条件的数据对象。搜索的结果通常有两种可能：

搜索成功，即找到满足条件的数据对象这时,作为结果,可报告该对象在结构中的位置,还可给出该对象中的具体信息。

搜索不成功，或搜索失败。作为结果,

应报告一些信息,如失败标志、位置等。通常称用于搜索的数据集合为搜索结构，它是由同一数据类型的对象(或记录)组成。在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。称为关键码。使用基于关键码的搜索，搜索结果应是唯一的。但在实际应用时，搜索条件是多方面的，可以使用基于属性的搜索方法，但搜索结果可能不唯一。实施搜索时有两种不同的环境。

静态环境，搜索结构在插入和删除等操作的前后不发生改变。静态搜索表

动态环境，为保持较高的搜索效率,搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。

动态搜索表

静态搜索表template<classType>class

dataList;template<classType>classNode{friendclassdataList<Type>;private:

Typekey;other;public:

Node

(constType&value):key

(value){}TypegetKey()const

{returnkey;

}

voidsetKey(Typek){key=k;

}};template<classType>classdataList

{protected:Node<Type>*Element;//数据存储数组

intArraySize;//存储数组最大长度

intCurrentSize; //存储数组当前长度public:dataList(intsz=10):ArraySize(sz){

Element=newNode<Type>[sz];

CurrentSize=0;}virtual~dataList(){

delete[]Element;}

friendostream&operator<<(ostream&OutStream,

constdataList<Type>&OutList);

friendistream

&operator>>(istream&InStream,dataList<Type>&InList);};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)，通常它是搜索结构中对象总数n或文件结构中物理块总数n的函数。在静态搜索表中,利用数组元素的下标作为数据对象的存放地址。搜索算法根据给定值x,在数组中进行搜索。直到找到x在数组中的位置或可确定在数组中找不到x为止。另外衡量一个搜索算法还要考虑算法所需要的存储量和算法的复杂性等问题。顺序搜索

(SequentialSearch)所谓顺序搜索,又称线性搜索,主要用于在线性结构中进行搜索。设若表中有CurrentSize个对象，则顺序搜索从表的先端开始,顺序用各对象的关键码与给定值x进行比较,直到找到与其值相等的对象,则搜索成功;给出该对象在表中的位置。若整个表都已检测完仍未找到关键码与x相等的对象,则搜索失败。给出失败信息。template<classType>intsearchList<Type>::Search(constType&x)const{//顺序搜索关键码为x的数据对象,第0号位置//作为控制搜索自动结束的“监视哨”使用

Element[0].key=x;

inti=CurrentSize;

//将x送0号位置设置监视哨

while(Element[i].key!=x)i--;

//从后向前顺序搜索

returni;}constintSize=10;main

(){//顺序搜索的主过程

searchList<float>List1(Size); //定义搜索表

floatTarget;

intLocation;cin>>List1;

cout<<List1; //输入List1

cout<<“搜索浮点数

:”;

cin>>Target; if((Location=List1.search(Target))!=0)cout<<“找到位置在”<<Location<<

endl; //搜索成功,输出找到的位置

elsecout<<“没有找到.\n”;//搜索失败}顺序搜索的平均搜索长度

设搜索第

i

个元素的概率为pi,搜索到第

i

个元素所需比较次数为

ci,则搜索成功的平均搜索长度:在顺序搜索并设置“监视哨”情形：

ci=n-i+1,i=n,n-1,,1，因此在等概率情形，pi=1/n,

i=1,2,,n。

在搜索不成功情形，ASLunsucc=n+1.

顺序搜索的递归算法template<classType>int

SearchList<Type>::Search(constType&x,int&loc)const{//在数据表Element[0..n-1]

中搜索其关键码与//给定值匹配的对象,函数返回其表中位置。//参数loc

是在表中开始搜索位置

if(loc>=CurrentSize

)return

-1;//搜索失败

elseif(Element[loc].key==x)returnloc;

//搜索成功

elsereturnSearch(x,loc+1);//递归搜索}基于有序顺序表的顺序搜索算法template<classType>intsearchList<Type>::Search(constType&x)const{//顺序搜索关键码为x的数据对象

for(inti=0;i<CurrentSize;i++)

if(Element[i].key==x)returni;//成功

elseif(Element[I].key>x)break;return

-1;//顺序搜索失败,返回失败信息}有序顺序表的顺序搜索

(10,20,30,40,50,60)105060======203040<<<<<<>>>>>>基于有序顺序表的折半搜索设n个对象存放在一个有序顺序表中，并按其关键码从小到大排好了序。折半搜索时,先求位于搜索区间正中的对象的下标mid，用其关键码与给定值x比较:

Element[mid].key==x，搜索成功；

Element[mid].key>x，把搜索区间缩小到表的前半部分，继续折半搜索；

Element[mid].key<x，把搜索区间缩小到表的后半部分，继续折半搜索。如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败。搜索成功的例子-101346810126012345678搜索lowmidhigh66810125678lowmidhigh665lowmidhigh6搜索失败的例子-101346810125012345678搜索lowmidhigh56810125678lowmidhigh655lowmidhigh5template<classType>classorderedList:publicdataList<Type>{//有序表的类定义,继承了数据表public:

orderedList(intsz=10):

dataList<Type>(sz){}

virtual~orderedList(){}

virtualintSearch(constType&x

)const;};

template<classType>intorderedList<Type>:://折半搜索算法BinarySearch(constType&x,const

intlow,

const

inthigh)const{//折半搜索的递归算法

intmid=-1;if(low<=high){

mid=(low+high)/2;

if(Element[mid].key<x)mid=BinarySearch(x,mid+1,high);

elseif(Element[mid].key>x) mid=BinarySearch(x,low,mid-1);}returnmid;}template<classType>intorderedList<Type>::BinarySearch(constType&x)const{

//折半搜索的迭代算法

inthigh=CurrentSize-1,low=0,mid;

while(low<=high){

mid=(low+high)/2;

if(Element[mid].key<x)low=mid+1; //右缩搜索区间

else

if(Element[mid].key)>x)high=mid-1;//左缩搜索区间

elsereturnmid;//搜索成功

}

return

-1;//搜索失败}搜索成功时检测指针停留在树中某个结点。搜索不成功时检测指针停留在某个外结点（失败结点）。3515455025102030搜索22搜索45有序顺序表的折半搜索的判定树

(10,20,30,40,50,60)1050======30<<<<<<>>>