第七章-集合与搜索-C++数据结构-教学课件

集合及其表示等价类与并查集静态搜索表二叉搜索树最优二叉搜索树AVL树小结第七章集合与搜索集合及其表示第七章集合与搜索1集合基本概念集合及其表示集合是成员(对象或元素)的一个群集。集合中的成员可以是原子(单元素)，也可以是集合。集合的成员必须互不相同。在算法与数据结构中所遇到的集合，其单元素通常是整数、字符、字符串或指针，且同一集合中所有成员具有相同的数据类型。colour={red,orange,yellow,green,black,blue,purple,white}name={“An”,“Cao”,“Liu”,“Ma”,“Peng”,“Wang”,“zhang”}集合基本概念集合及其表示集合是成员(对象或元素)的一个群集。2集合中的成员一般是无序的，没有先后次序关系。但在表示它时，常常写在一个序列里。我们常设定集合中的单元素具有线性有序关系，此关系可记作“<”，表示“优先于”。若a,b是集合中的两个单元素，则a<b,a==b,a>b三者必居其一；若a,b,c是集合中的三个单元素，且a>b,b>c，则a>c。(传递性)整数、字符和字符串都有一个自然的线性顺序。而指针也可以依据其在序列中安排的位置给予一个线性顺序。集合操作有求集合的并、交、差、判存在等。集合中的成员一般是无序的，没有先后次序关系。但在表示它时，常3集合运算的文氏(Venn)图集合(Set)的抽象数据类型Template<classType>class

Set{

Set(intMaxSetSize):MaxSize(MaxSetSize);

void

MakeEmpty(Set

&s);

int

AddMember(Set

&s,constTypex);

intDelMember(Set

&s,constType

&x);集合运算的文氏(Venn)图集合(Set)的抽象数据类型Te4

void

Assign

(Set&s1,

Set&s2

);

void

Union

(Set&s1,

Set&s2

);

voidIntersection

(Set&s1,

Set&s2

);

void

Difference

(Set&s1,

Set&s2

);

int

Contains(Set

&s,constType

&

x);

intEqual(Set

&s1,Set&s2);

int

SubSet(Set

&s1,Set&s2

);}voidAssign(Set&s1,Se5用位向量实现集合抽象数据类型集合的位向量(bitVector)类的定义#include<assert.h>constint

DefaultSize=100;classSet{

当集合是全集合{0,1,2,…,n}的一个子集，且n是不大的整数时，可用位(0,1)向量来实现集合。当全集合是由有限的可枚举的成员组成的集合时，可建立全集合成员与整数0,1,2,…的一一对应关系，用位向量来表示该集合的子集。用位向量实现集合抽象数据类型集合的位向量(bitVecto6private:int*bitVector;

int

MaxSize;public:

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

void

MakeEmpty(){for(int

i=0;

i<MaxSize;

i++)

bitVector[i]=0;

}

intAddMember(constintx);

int

DelMember(constintx);

Set&operator=(Set

&right);

private:7

Set&operator+(Set

&

right);

Set&operator*(Set

&

right);Set&operator

-(Set

&

right);

int

Contains(constint

x);

int

SubSet(Set

&

right);

intoperator==(Set

&right);};使用示例

Sets1,s2,s3,s4,s5;

intindex,equal;

//构造集合

for(int

k=0;

k<10;

k++)//集合赋值

{

s1.AddMember(k);

s2.AddMember(k+7);}

//s1:{0,1,2,…,9},s2:{7,8,9,…,16}Set&operator+(Set&ri8

s3=s1+s2;//求s1与s2的并{0,1,…,16}

s4=s1*s2;//求s1与s2的交{

7,8,9}

s5=s1-

s2;//求s1与s2的差{0,1,2,3,4,5,6}

index=s1.SubSet(s4);//求s4在s1中首次匹配

cout<<index<<endl;//位置，index=7

equal=s1==s2;

//集合s1与s2比较相等

cout<<equal<<endl;

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

MaxSetSize):

MaxSize(MaxSetSize){

assert(MaxSize>0);

bitVector=newint[MaxSize];

assert(bitVector!=0);

s3=s1+s2;//求s1与s2的9for(int

i=0;

i<MaxSize;

i++)bitVector[i]=0;}intSet::Addmember(constint

x){

assert(x>=0&&

x<MaxSize);

if(!bitVector[x]){

bitVector[x]=1;

return1;

}

return0;}int

Set::DelMember(constint

x){

assert(x>=0&&

x<MaxSize);

if(bitVector[x]){

bitVector[x]=0;

return1;

}

return0; }for(inti=0;i<MaxSi10Set&

Set::operator=(Set&

right){

assert(MaxSize==right.MaxSize);for(int

i=0;

i<MaxSize;

i++)

bitVector[i]=right.bitVector[i]; return*this;}Set&

Set::operator+(Set&

right){

assert(MaxSize==right.MaxSize);

for(int

i=0;

i<MaxSize;

i++)

bitVector[i]=bitVector[i]||right.bitVector[i];return*this;}Set&Set::operator=(Set&11Set&

Set::operator*(Set

&right){

assert(MaxSize==right.MaxSize);

for(inti=0;

i<MaxSize;

i++)

bitVector[i]=bitVector[i]&&

right.bitVector[i];return*this;}Set&

Set::operator

-(Set&

right){

assert(MaxSize==right.MaxSize);

for(inti=0;

i<MaxSize;

i++)

bitVector[i]=bitVector[i]&&!right.bitVector[i];return*this;}

Set&Set::operator*(Set&12int

Set::Contains(constint

x){

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

returnbitVector[x]; }intSet::operator

==(Set&

right){

assert(MaxSize==right.MaxSize);

for(inti=0;

i<MaxSize;i++)

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

return1;}int

Set::SubSet(Set&

right){

assert(MaxSize==right.MaxSize);intSet::Contains(constin13

for(int

i=0;

i<MaxSize;i++)

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

return1;

}用有序链表实现集合的抽象数据类型用带表头结点的有序链表表示集合for(inti=0;i<MaxSiz14用有序链表来表示集合时，链表中的每个结点表示集合的一个成员。各结点所表示的成员e0,e1,…,en

在链表中按升序排列，即e0<e1<…<en。在一个有序链表中寻找一个集合成员时，一般不用搜索整个链表，搜索效率可以提高很多。集合成员可以无限增加。因此，用有序链表可以表示无穷全集合的子集。集合的有序链表类的定义template<classType>classSetList;

用有序链表来表示集合时，链表中的每个结点表示集合的一个成员。15template<classType>

classSetNode{ friendclassSetList<Type>;public:

SetNode(constType&item):

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

Typedata;

SetNode<Type>*link;};template<classType>class

SetList

{private:

SetNode<Type>*first,*last;public:template<classType>classSe16SetList();

void

MakeEmpty();

intAddMember(constType&

x);int

DelMember(constType&

x);

SetList<Type>&operator=(SetList<Type>&

right);

SetList<Type>&operator+(SetList<Type>&

right);

SetList<Type>&operator*(SetList<Type>&

right);

SetList<Type>&operator-(SetList<Type>&

right);int

Contains(constType&x);

SetList();17int

operator

==(SetList<Type>&

right);

Type&

Min();

Type&

Max(); }集合构造函数template<classType>voidSetList<Type>::SetList(){

SetNode<Type>*first=*last=

new

SetNode<Type>(0);

}intoperator==(SetList<18集合的搜索、加入和删除操作template<classType>intSetList<Type>::Contains(constType&

x){

SetNode<Type>*temp=first→link;

while(temp!=NULL

&&

temp→data<x)

temp=temp→link;

if(temp!=NULL

&&

temp→data==x)

return1;

elsereturn0;}集合的搜索、加入和删除操作19template<classType>int

SetList<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=new

SetNode(x);

s→link=p;

q→link=s;

if(p==NULL)last=s;

return1;}template<classType>intSetL20template<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;

delete

p;

return1;}

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

right){

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

SetNode<Type>*pa=first=newSetNode<Type>;

while(pb!=NULL){

pa→link=new

SetNode<Type>(pb→data);

pa=pa→link;

pb=pb→link;

}

pa→link=NULL;

last=pa;return*this; }用有序链表表示集合时的几个重载函数22template<classType>SetList<Type>&

SetList<Type>::operator+(SetList<Type>&right){

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

SetNode<Type>*pa=first→link;

SetNode<Type>*pc=first;

while(pa!=NULL

&&

pb!=NULL){if(pa→data==pb→data)

{pc→link=pa;

pa=pa→link;

pb=pb→link;

}

elseif(pa→data<pb→data)

{

pc→link=pa;

pa=pa→link;

}

elsetemplate<classType>23

{pc→link=new

SetNode<Type>(pb→data);

pb=pb→link;

}pc=pc→link;}if(pa!=NULL)pc→link=pa;else{while(pb!=NULL){

pc→link=new

SetNode<Type>(pb→data);pc=pc→link;

pb=pb→link;

}pc→link=NULL;

last=pc;}return*this;}{pc→link=newSetN24template<classType>SetList<Type>&

SetList<Type>::operator*(SetList<Type>&right){

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

SetNode<Type>*pa=first→link;

SetNode<Type>*pc=first;

while(pa!=NULL

&&

pb!=NULL){

if(pa→data==pb→data)

{pc=pc→link;

pa=pa→link;

pb=pb→link;

}

elseif(pa→data<pb→data)

{

pc→link=pa→link;

delete

pa;

pa=pc→link;

}

else

pb=pb→link;

}

template<classType>25while(pa!=NULL){

pc→link=pa→link;

delete

pa;

pa=pc→link;

}

last=pc;return*this;}template<classType>SetList<Type>&

SetList<Type>::operator

-(SetList<Type>&right){

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

SetNode<Type>*pa=first→link;

while(pa!=NULL){26

SetNode<Type>*pc=first; while(pa!=NULL

&&pb!=NULL){

if(pa→data==pb→data)

{

pc→link=pa→link;

delete

pa;

pa=pc→link;

pb=pb→link;

}elseif(pa→data<pb→data)

{

pc=pc→link;

pa=pa→link;

}

else

pb=pb→link;

}

if(pa==NULL)last=pc;return*this;}SetNode<Type>*pc=first;27template<classType>intSetList<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;

if(pa!=NULL

||

pb!=NULL)return0;

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

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

y,则y

x。传递性：若x

y且y

z,则x

z。因此，等价关系是集合上的一个自反、对称、传递的关系。等价关系与等价类(EquivalenceClass)等价类29

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

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

S。这些子集即为等价类。确定等价类的方法分两步走。第一步，读入并存储所有的等价对(i,j)；第二步，标记和输出所有的等价类。“相等”(=)就是一种等价关系，它满足上述的三个特30void

equivalence(){

初始化;

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

0voidequivalence(){给定集合S=31初始

{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}初始{0},{1},{2},{3},{4},{5},{6}32确定等价类的链表方法

设等价对个数为m，对象个数为n。一种可选的存储表示为单链表。可为集合的每一对象建立一个带表头结点的单链表，并建立一个一维的指针数组seq[n]作为各单链表的表头结点向量。seq[i]是第i个单链表的表头结点，第i个单链表中所有结点的data域存放在等价对中与i等价的对象编号。

当输入一个等价对(i,j)后，就将集合元素i链入第j个单链表，且将集合元素j链入第i个单链表。在输出时，设置一个布尔数组out[n]，用out[i]标记第i个单链表是否已经输出。

确定等价类的链表方法设等价对个数为m，对象个数为n。33void

equivalence(){

读入n;

将seq

初始化为

0

且将

out

初始化为

False;

while等价对未处理完

{

读入下一个等价对(i,j);

将

j

链入

seq[i]链表;将i

链入

seq[j]链表;

}

for(i=0;i<n;i++) //检测所有对象

if(out[i]==False){//若对象i未输出

out[i]=True;//对象i做输出标志

输出包含对象i的等价类;

}}voidequivalence(){34算法的输出从编号i=0的对象开始，对所有的对象进行检测。在i=0时，循第0个单链表先找出形式为(0,j)的等价对，把0和j作为同一个等价类输出。再根据等价关系的传递性，找所有形式为(j,k)的等价对，把k也纳入包含0的等价类中输出。如此继续，直到包含0的等价类完全输出为止。接下来再找一个未被标记的编号，如i=1，该对象将属于一个新的等价类，我们再用上述方法划分、标记和输出这个等价类。在算法中使用了一个栈。每次输出一个对象编号时，都要把这个编号进栈，记下以后还要检测输出的等价对象的单链表。算法的输出从编号i=0的对象开始，对所有的对象进行检35输入所有等价对后的seq数组及各单链表的内容输入所有等价对后的seq数组及各单链表的内容36等价类链表的定义enum

Boolean

{False,True

};

class

ListNode

{ //定义链表结点类

friendvoidequivalence();

private:

intdata; //结点数据

ListNode*link; //结点链指针

ListNode(intd){

data=d;link=NULL;}

};

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

equivalence(){

ifstream

inFile("equiv.in",

ios::in);

//输入文件

if(!inFile){

cout

<<“不能打开输入文件"<<

endl;exit(1);}int

i,j,n;建立等价类算法(输入等价对并输出等价类)voidequi38

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

new

ListNodePtr[n];

out=

new

Boolean[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=

new

ListNode(i);//创建结点iy→link=seq[j];

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

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

}inFile>>n; //读入对象个39

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进栈for(i=0;i<n;i++)

40

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

}

else

x=x→link;//已输出过,跳过

}

if

(top==NULL)break;//栈空退出循环

else{x=seq[top→data];top=top→link;}

//栈不空,退栈,x是根据结点编号回//溯的另一个链表的头指针

}

}

delete

[]

seq;

delete[]

out;}x=y; //x41并查集(Union-FindSets)建立等价类的另一种解决方案是先把每一个对象看作是一个单元素集合，然后按一定顺序将属于同一等价类的元素所在的集合合并。在此过程中将反复地使用一个搜索运算，确定一个元素在哪一个集合中。能够完成这种功能的集合就是并查集。它支持以下三种操作：

Union(Root1,Root2)

//并操作；

Find(x)

//搜索操作；

UFSets(s)

//构造函数。一般情形，并查集主要涉及两种数据类型：集合名类型和集合元素的类型。并查集(Union-FindSets)建立等价类的另一种42

对于并查集来说，每个集合用一棵树表示。集合中每个元素的元素名分别存放在树的结点中，此外，树的每一个结点还有一个指向其双亲结点的指针。为此，需要有两个映射：集合元素到存放该元素名的树结点间的对应；集合名到表示该集合的树的根结点间的对应。设S1={0,6,7,8}，S2={1,4,9}，S3={2,3,5}对于并查集来说，每个集合用一棵树表示。43利用并查集来解决等价问题的步骤如下：利用UFSets操作,建立UFSets型集合this,集合中每一个元素初始化为0，各自形成一个单元素子集合,i=1,2,…,n。n是集合中元素个数。重复以下步骤,直到所有等价对读入并处理完为止。读入一个等价对[i][j];用Find(i),Find(j)搜索i、j所属子集合的名字x和y;若x

y.用Union(x,y)或Union(y,x)将它们合并,前者的根在x；后者的根在y。利用并查集来解决等价问题的步骤如下：利用UFSets操作,44为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合。如果我们确定了元素i在根为j的树中，而且j有一个指向集合名字表中第k项的指针，则集合名即为name[k]。为此，采用树的双亲表示作为集合存储表示。集合元素的编号从0到n-1。其中n是最大元素个数。在双亲表示中，第i个数组元素代表包含集合元素i的树结点。根结点的双亲为-1，表示集合中的元素个数。为了区别双亲指针信息(0)，集合元素个数信息用负数表示。为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合45S1S2的可能的表示方法下标parent集合S1,S2和S3的双亲表示-14-12-1200040123456789S1S2的可能的表示方法下标集合S1,S2和S3的双46constintDefaultSize=10;class

UFSets{//并查集的类定义public:

UFSets(int

s=DefaultSize); ~UFSets(){

delete[]parent;}

constUFSets

&

operator=(UFSets

const&

Value);

void

Union(intRoot1,intRoot2);

intFind(int

x);

voidUnionByHeight(int

Root1,int

Root2); private:

int*parent;

intsize;};constintDefaultSize=10;47UFSets::UFSets(int

s){//构造函数

size=s;

parent=newint[size+1];

for(int

i=0;

i<=size;

i++)parent[i]=-1;

}unsignedint

UFSets::Find(int

x){//搜索操作

if(parent[x]<=0)return

x;

elsereturnFind(parent[x]);}void

UFSets::Union(int

Root1,int

Root2){//并

parent[Root2]=Root1;//Root2指向Root1}UFSets::UFSets(ints){48Find和Union操作性能不好。假设最初n个元素构成n棵树组成的森林，parent[i]=-1。做处理Union(n-2,n-1),…,

Union(1,2),Union(0,1)后，将产生如图所示的退化的树。

执行一次Union操作所需时间是O(1)，n-1次Union操作所需时间是O(n)。若再执行Find(0),Find(1),…,Find(n-1),

若被搜索的元素为i，完成Find(i)操作需要时间为O(i)，完成n次搜索需要的总时间将达到Find和Union操作性能不好。假设最初n个元素构成49为避免产生退化的树，改进方法是先判断两集合中元素的个数，如果以

i为根的树中的结点个数少于以

j为根的树中的结点个数，即parent[i]>parent[j]，则让

j成为i的双亲，否则，让i成为j的双亲。此即Union的加权规则。Union操作的加权规则parent[0](==-4)<parent[4](==-3)为避免产生退化的树，改进方法是先判断两集合中元素的个数，如果50void

UFSets::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

}}voidUFSets::51

使用加权规则得到的树使用加权规则得到的树52使用并查集处理等价对，形成等价类的过程使用并查集处理等价对，形成等价类的过程53Union操作的折叠规则为进一步改进树的性能，可以使用如下折叠规则来“压缩路径”。即：如果j是从i到根的路径上的一个结点，且parent[j]

root[j]，则把parent[j]置为root[i]。Union操作的折叠规则为进一步改进树的性能，可以使用如下折54int

UFSets::CollapsingFind(int

i){//使用折叠规则的搜索算法

for(intj=i;

parent[j]>=0;

j=parent[j]);

//让j

循双亲指针走到根

while(i!=j)//换parent[i]到j

{int

temp=parent[i];

parent[i]=j;

i=temp;}

returnj;}

使用折叠规则完成单个搜索，所需时间大约增加一倍。但是，它能减少在最坏情况下完成一系列搜索操作所需的时间。intUFSets::CollapsingFind(55搜索(Search)的概念静态搜索表

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

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

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

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

动态环境，为保持较高的搜索效率，搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。动态搜索表在每一个对象中有若干属性，其中应当有一个属性，其值可唯一地标57静态搜索表template<classType>classdataList;template<classType>class

Node{friendclassdataList<Type>;public:

Node(constType&value):key

(value){}TypegetKey()const

{return

key;

}

void

setKey(Type

k){

key=k;

}private:

Type

key;

other;};静态搜索表58template<classType>class

dataList{public:

dataList(int

sz=10):

ArraySize(sz),

Element(new

Node<Type>[sz]){}

virtual~dataList(){

delete[]Element;}

friendostream

&operator<<(ostream&

OutStream,

const

dataList<Type>

&OutList);

friendistream

&operator>>(istream&

InStream,dataList<Type>

&InList);protected:

Type*Element;

int

ArraySize,CurrentSize;};template<classType>classda59template<classType>class

searchList

:public

dataList<Type>{//作为派生类的静态搜索表的类定义public:

searchList(intsz=10):

dataList<Type>(sz){}

virtual~searchList(){}

virtualint

Search(constType&

x)const;};template<classType>classse60template<classType>istream&operator>>(istream&

InStream,dataList<Type>

&

InList){//从输入流对象InStream输入数据到数据表InList

cout<<“输入数组当前大小

:”;

Instream>>InList.CurrentSize;cout<<“输入数组元素值

:\n”;

for(int

i=0;

i<InList.CurrentSize;i++){cout<<“元素”<<i<<“:”;

InStream>>InList.Element[i];}return

InStream;}template<classType>istream61template<classType>ostream&operator<<(ostream&

OutStream,

const

dataList<Type>&

OutList){//将数据表OutList内容输出到输出流对象OutStream

OutStream<<“数组内容

:\n”;

for(int

i=0;

i<OutList.CurrentSize;i++)

OutStream<<OutList.Element[i]<<‘’;

OutStream<<endl;

OutStream<<“数组当前大小

:”<<

OutList.CurrentSize<<endl;

return

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

(SequentialSearch)所谓顺序搜索，又称线性搜索，主要用于在线性结构中进行搜索。设若表中有CurrentSize个对象，则顺序搜索从表的先端开始，顺序用各对象的关键码与给定值x进行比较，直到找到与其值相等的对象，则搜索成功，给出该对象在表中的位置。若整个表都已检测完仍未找到关键码与x相等的对象，则搜索失败。给出失败信息。顺序搜索(SequentialSearch)所谓顺序搜索64template<classType>intsearchList<Type>::Search(constType&

x)const{//顺序搜索的迭代算法，0号元素为监视哨

Element[0].setKey(x);

int

i=CurrentSize;

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

return

i;}template<classType>intearchList<Type>::Search(constType&

x,int&loc)const{//顺序搜索的递归算法

if(loc>=CurrentSize)return

-1;

elseif(Element[loc].getKey()==

x)returnloc;elsereturn

Search(x,loc+1);}template<classType>intsear65constint

Size=10;main

(){//顺序搜索的主过程searchList<float>

List1(Size);

float

Target;

intLocation;

cin>>List1;

cout<<List1;

//输入/输出数据表List1

cout<<“搜索浮点数

:”;

cin>>Target;

if((Location=List1.search(Target))!=0)

cout<<“找到下标”<<Location<<endl;

else

cout<<“没有找到.\n”;}constintSize=10;66顺序搜索的平均搜索长度

设搜索第

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

i个元素所需比较次数为

ci，则搜索成功的平均搜索长度:在顺序搜索情形，ci=i+1,i=0,1,,n-1，因此在等概率情形，pi=1/n,

i=0,1,,n-1。

顺序搜索的平均搜索长度设搜索第i个元素的概率为pi，67基于有序顺序表的折半搜索设n个对象存放在一个有序顺序表中，并按其关键码从小到大排好了序。采用对分搜索时，先求位于搜索区间正中的对象的下标mid，用其关键码与给定值x比较:

Element[mid].getKey()=x，搜索成功；

Element[mid].getKey()>x，把搜索区间缩小到表的前半部分，再继续进行对分搜索；

Element[mid].getKey()<x，把搜索区间缩小到表的后半部分，再继续进行对分搜索。每比较一次，搜索区间缩小一半。如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败。基于有序顺序表的折半搜索设n个对象存放在一个有序顺序表中，并68搜索成功的例子 搜索失败的例子搜索成功的例子 搜索失败的例子69template<classType>class

orderedList

:public

dataList<Type>{//有序表的类定义,继承了数据表public:

orderedList(intsz=10):

dataList<Type>(sz){}

virtual~orderedList(){}

virtualint

Search(constType&

x)const;};

template<classType>classor70temp