《六章节集合与字典.ppt》由会员分享，可在线阅读，更多相关《六章节集合与字典.ppt（138页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、六章节集合与字典 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望内容集合及其表示并查集与等价类字典跳表散列集合的基本概念具有某种共同性质具有某种共同性质”的若干不同的对象合在一起的若干不同的对象合在一起构成集合构成集合。在算法与数据结构中所遇到的集合中所有成员在算法与数据结构中所遇到的集合中所有成员具有相同的数据类型。具有相同的数据类型。例如：例如：colour=red,orange,yellow,green,black,blue,purple,white 一些说
2、明作为数据结构中的集合在概念上讲，元素之间是无序的。但是可能为了效率，在实现中将元素之间的某个序关系和元素的存储方式对应起来；不同的表示方法：保存实际数据值保存下标或者reference在父集中存放指示信息，表示是否在子集合内。允许相同元素多次出现的称为多重集合或者包。集合的运算还包括：判断一个元素是否在集合中集合是否为空A是否为B的子集以及添加/删除元素等操作遍历所以元素求满足某个条件的所有元素组成的子集A B 或 A+B A B 或 A B A-BAAABBB集合（Set）的抽象数据类型template class Set public:virtual Set()=0;/构造函数 virt
3、ual makeEmpty()=0;/置空集合 virtual bool addMember(const T x)=0;virtual bool delMember(const T x)=0;virtual Set intersectWith(Set&R)=0;/集合的交运算 virtual Set unionWith(Set&R)=0;/集合的并运算 virtual Set differenceFrom(Set&R)=0;/集合的差运算 virtual bool Contains(T x)=0;virtual bool subSet(Set&R)=0;virtual bool operato
4、r=(Set&R)=0;/判集合是否相等;集合的位向量实现当集合是全集合 0,1,2,n 的一个子集，且n是不大的整数时，可用位(0,1)向量来实现集合。对于每个i，有一个二进位；取值1或0分别表示在集合与不在集合中。如果n小于32，可以直接用32位整数表示；否则可以使用整数数组表示。当全集合是由有限个可枚举的成员组成时，可建立全集合成员与整数0,1,2,的一一对应关系，然后用位向量来表示该集合的子集。如果全集用数组表示，那么其子集也可以用位向量表示。但是，此时需要保证全集不改变。位向量集合的类定义#include#include const int DefaultSize=50;class
5、bitSet/用位向量来存储集合元素,集合元素的范围在0到/setSize-1之间。数组采用16位无符号短整数实现 int setSize;/集合大小 int vecterSize;/位数组大小 unsigned short*bitVector;/bitVectori的第j位为0/1表示第i*16+j个元素是否在此集合内。位向量集合的类定义（二）public:bitSet(int sz=DefaultSize);/构造函数 bitSet(const bitSet&R);/复制构造函数 bitSet()delete bitVector;/析构函数 int getMember(const int
6、x);/取集合元素x void putMember(const int x,int v);/改集合元素x void makeEmpty()/置空集合 for(int i=0;i vectorSize;i+)bitVectori=0;bool addMember(const int x);/加入新成员x bool delMember(const int x);/删除老成员x位向量集合的类定义（三）bitSet&operator=(const bitSet&R);bitSet operator+(const bitSet&R);bitSet operator*(const bitSet&R);bi
7、tSet operator-(const bitSet&R);bool Contains(const int x);bool subSet(bitSet&R);/判this是否R的子集 bool operator=(bitSet&R);/判集合this与R相等 friend istream&operator (istream&in,bitSet&R);/输入 friend ostream&operator 0);/检查参数的合理性 vectorSize=(setSize+15)/16;/vectorSize*16必须大于setSize bitVector=new int vectorSize;
8、/分配空间 assert(bitVector!=NULL);/检查存储分配是否成功 for(int i=0;i vectorSize;i+)bitVectori=0;/初始化为空集;复制构造函数bitSet:bitSet(const bitSet&R)/复制构造函数 setSize=R.setSize;/集合元素个数 vectorSize=R.vectorSize;/存储数组大小 bitVector=new int vectorSize;/分配空间 assert(bitVector!=NULL);/检查存储分配是否成功 for(int i=0;i (15-id)&1);/取第id位(从高位算起
9、）的值/上面的表达式判断elem的第id位是否为1;注：第x个元素存放在bitVector的第x/16个元素的（从高位起）第x%16位上。0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0putMember/如如v为为1，将，将x加入集合；（如果加入集合；（如果x在集合中，操作无效果）在集合中，操作无效果）/否则将否则将x从集合中删除；（如果从集合中删除；（如果x不在集合中，操作无效果）不在集合中，操作无效果）void bitSet:putMember(const int x,int v)/将值v送入集合元素x int ad=x/16,id=x%16;/计算数组元素下标 unsig
10、ned short elem=bitVector ad;/取x所在数组元素 int temp=elem (15-id);/右移,该位移至末尾elem=elem (id+1);/此时elem中包含了后面的16-id位/根据v的值,修改该位if(temp%2=0&v=1)temp=temp+1;else if(temp%2=1&v=0)temp=temp-1;bitVectorad=(temp(id+1);/送回;0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0设：id=2；右移后，temp为0000000000000011elem左移后为：0001001000100000Add/d
11、elete memberbool bitSet:addMember(const int x)assert(x=0&x=0&x setSize);if(getMember(x)=1)putMember(x,0);return true;return false;另一种实现位集合的方法设立数组：bitArray16=0 x8000,0 x4000,0 x2000,0 x1000,0 x0800,0 x0400,0 x0200,0 x0100,0 x0080,0 x0040,0 x0020,0 x0010,0 x0008,0 x0004,0 x0002,0 x0001 判断bitVector的第i个
12、元素的第j位是否为1bitArrayj&bitVectori表示；将bitVector的第i个元素的第j位设置为1bitVectori|=bitArrayj;将bitVector的第i个元素的第j位设置为0bitVectori&=bitArrayj;集合的并运算bitSet bitSet:/求集合this与R的并operator+(const bitSet&R)assert(vectorSize=R.vectorSize);bitSet temp(vectorSize);for(int i=0;i vectorSize;i+)temp.bitVectori=bitVectori|R.bitVe
13、ctori;return temp;/按位求或,由第三个集合返回;集合的交运算/求集合this与R的交bitSet bitSet:operator*(const bitSet&R)assert(vectorSize=R.vectorSize);bitSet temp(vectorSize);for(int i=0;i vectorSize;i+)temp.bitVectori=bitVectori&R.bitVectori;return temp;/按位求“与”,由第三个集合返回集合的差运算/求集合this与R的差bitSet bitSet:operator-(const bitSet&R)a
14、ssert(vectorSize=R.vectorSize);bitSet temp(vectorSize);for(int i=0;i vectorSize;i+)temp.bitVectori=bitVectori&R.bitVectori;return temp;/由第三个集合返回;thisRtemp0 1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 1 1 1 0 1 0 1 1 1 0thisRtemp0 1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 0 1 0 0 0 0 0 0 1 0thisRtemp0
15、1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 1 0 1 0 0 0 0 1 0 0集合的并集合的并集合的交集合的交集合的差集合的差集合的子集判断/判this是否R的子集bool bitSet:subSet(bitSet&R)assert(setSize=R.setSize);for(int i=0;i vectorSize;i+)/按位判断 if(bitVectori&R.bitVectori)return false;return true;thisR0 0 1 1 1 0 1 0 1 1 00 0 1 1 1 0 0 1 0 1 01 1 0 0 0
16、 1 1 0 1 0 1 判断集合相等template bool bitSet:operator=(bitSet&R)/判集合this与R相等 if(vectorSize!=R.vectorSize)return false;for(int i=0;i vectorSize;i+)if(bitVectori!=R.bitVectori)return false;return true;/对应位全部相等;thisR0 0 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 0ifirstfirst081723354972用有序链表实现集合链表的每个结点存放集合的一个成员。各
17、结点所表示的成员 e0,e1,en 在链表中按某种顺序排列，即 e0 e1 en。有序链表可以表示无穷全集的子集，集合中的元素个数也没有限制；本课程内使用带有表头结点的有序链表，也可以使用其它的链表形式。集合的有序链表类的定义（链表结点）template struct SetNode/集合的结点类定义 T data;/每个成员的数据 SetNode*link;/链接指针 SetNode():link(NULL);/构造函数 SetNode(const T&x,SetNode*next=NULL):data(x),link(next);/构造函数;注意：可参照带表头的链表的实现方式注意：可参照带
18、表头的链表的实现方式集合的有序链表类的定义（链表）集合的有序链表类的定义（链表）template class LinkedSet/集合的类定义private:SetNode*first,*last;/有序链表表头指针,表尾指针public:LinkedSet()first=last=new SetNode;LinkedSet(LinkedSet&R);/复制构造函数 LinkedSet()makeEmpty();delete first;void makeEmpty();/置空集合 bool addMember(const T&x);bool delMember(const T&x);bool
19、 Contains(const T x);/判x是否集合的成员 LinkedSet&operator=(LinkedSet&R);LinkedSet operator+(LinkedSet&R);/集合的交、差、相等判断、子集判断运算等运算集合的交、差、相等判断、子集判断运算等运算 bool Min(T&x);bool Max(T&x);/返回集合最大/小元素的值;加入一个元素的操作template bool LinkedSet:addMember(const T&x)/把新元素x加入到集合之中 SetNode*p=first-link,*pre=first;while(p!=NULL&p-d
20、ata link;/注意注意pre的用法的用法，始终有pre-link=p/循环退出时，要么已经扫描到结尾，要么循环退出时，要么已经扫描到结尾，要么p指向的元素大于等于指向的元素大于等于x/注意：这个结论是因为链表中的元素从小到大排列注意：这个结论是因为链表中的元素从小到大排列 if(p!=NULL&p-data=x)return false;/x在集合中,不加入 SetNode*s=new SetNode(x);/创建结点 s-link=p;pre-link=s;/链入if(p=NULL)last=s;/当当链到链尾时改链尾指针，以保证类不变式成立 return true;d1d2preda
21、tas插入时，必然有d1datad2删除一个元素template bool LinkedSet:delMember(const T&x)/把集合中成员x删去 SetNode*p=first-link,*pre=first;while(p!=NULL&p-data link;/循环退出时，要么已经扫描到结尾，要么循环退出时，要么已经扫描到结尾，要么p指向的元素大于等于指向的元素大于等于x/注意：这个结论是因为链表中的元素从小到大排列注意：这个结论是因为链表中的元素从小到大排列 if(p!=NULL&p-data=x)/找到,可删pre-link=p-link;/重新链接if(p=last)las
22、t=pre;/删链尾时改尾指针delete p;/删除含x结点return true;else return false;/集合中无此元素;集合的合并（1）template LinkedSet LinkedSet:operator+(LinkedSet&R)/求集合this与集合R的并SetNode*pb=R.first-link;/R扫描指针SetNode*pa=first-link;/this扫描指针LinkedSet temp;/创建空链表SetNode*p,*pc=temp.first;/结果存放指针while(pa!=NULL&pb!=NULL)if(pa-data=pb-data)
23、/两集合共有pc-link=new SetNode(pa-data);pa=pa-link;pb=pb-link;else if(pa-data data)/this元素值小pc-link=new SetNode(pa-data);pa=pa-link;/end of else if(pa-data data)，待续，待续 集合的合并（2）else/R集合元素值小pc-link=new SetNode(pb-data);pb=pb-link;/end of elsepc=pc-link;/扫尾处理扫尾处理if(pa!=NULL)p=pa;/this集合未扫完else p=pb;/或R集合未扫完
24、while(p!=NULL)/向结果链逐个复制pc-link=new SetNode(p-data);pc=pc-link;p=p-link;/end of whilepc-link=NULL;temp.last=pc;/链表收尾return temp;；回忆一下以前的多项式合并算法：1、一元多项式被表示成为不同次数的项的集合，2、每个项包括系数、指数，且从小到大排列；请考虑几个问题：1、得到的集合仍然是从小到大排列吗？2、既在A中，又在B中的元素会重复出现在并集中吗？集合并运算的例子firstR.first08172349temp.first231735papbpc0817233549判断集
25、合相等bool LinkedSet:operator=(LinkedSet&R)SetNode*pb=R.first-link;SetNode*pa=first-link;while(pa!=NULL&pb!=NULL)if(pa-data=pb-data)pa=pa-link;pb=pb-link;else return false;/扫描途中不等时退出 if(pa!=NULL|pb!=NULL)return false;/链不等长时,返回0 return true;内容集合及其表示并查集与等价类字典跳表散列等价关系/等价类l若用符号“”表示集合上的等价关系，则对于该集合中的任意对象x,y,
26、z，下列性质成立：u自反性：x x(即等于自身)。u对称性：若 x y,则 y x。u传递性：若 x y且 y z,则 x z。从数学上看，等价类是对象（或成员）的集合，在一个等价类中的各个元素满足等价关系。一个集合上的等价关系将该集合划分成为互不相交的子集。并查集（disjoint set）问题高效地建立和表示某个集合上有一个等价关系建立过程如下：已知一个集合S，并且已知一个关系r。这个关系r通过一个二元组集合来表示；等价关系R是r的自反/传递/对称闭包；我们通过逐个读入r中的二元组，高效建立起等价关系R。用途主要用于按照某些已知的等价关系事实，将一个集合中的元素分划成为互不相交的子集。由已
27、知事实推导出等价的两个元素一定在同一子集中。等价关系建立的例子l给定集合给定集合 S=0,1,2,3,4,5,6,7,8,9,10,11,l已知已知:0 4,3 1,6 10,8 9,7 4,6 8,3 5,2 11,11 0l归并过程：归并过程：初始初始0,1,2,3,4,5,6,7,8,9,10,110 4 0,4,1,2,3,5,6,7,8,9,10,113 1 0,4,1,3,2,5,6,7,8,9,10,116 10 0,4,1,3,2,5,6,10,7,8,9,118 9 0,4,1,3,2,5,6,10,7,8,9,117 4 0,4,7,1,3,2,5,6,10,8,9,116
28、 8 0,4,7,1,3,2,5,6,8,9,10,113 5 0,4,7,1,3,5,2,6,8,9,10,112 11 0,4,7,1,3,5,2,11,6,8,9,1011 0 0,2,4,7,11,1,3,5,6,8,9,10并查集(Union-Find Sets)l并查集支持一个有穷集合上的某些操作并查集支持一个有穷集合上的某些操作l并查集支持以下三种操作：并查集支持以下三种操作：u Union(Root1,Root2)/合并操作合并操作u Find(x)/查找操作查找操作u UFSets(s)/构造函数构造函数l对于并查集来说，分划的每个子集用一棵树表示。也可以对于并查集来说，分划
29、的每个子集用一棵树表示。也可以用树的根结点来用树的根结点来代表代表子集。子集。l子树采用双亲表示法。子树采用双亲表示法。l全集本身可以使用其它数据结构表示。这里我们使用数组全集本身可以使用其它数据结构表示。这里我们使用数组表示，用下标指示元素。表示，用下标指示元素。S=0,1,2,3,4,5,6,7,8,9S1=0,6,7,8,S2=1,4,9,S3=2,3,5为为简简化化讨讨论论，忽忽略略实实际际的的集集合合名名，仅仅用用表表示示集集合合的的树树的的根根来来标识集合。标识集合。子集名子集名 指针指针0 S11 S22 S30427681935-4000-3-344220 1 2 3 4 5
30、6 7 8 94 4 3 2 3 2 0 0 0 4n初初始始时时,用用构构造造函函数数 UFSets(s)UFSets(s)构构造造一一个个森森林林,每每棵棵树树只只有有一一个个结结点点,表表示示集集合合中中各各元元素自成一个子集合。素自成一个子集合。nFind(i)：寻找集合元素：寻找集合元素 i所在子树的根。所在子树的根。nFind(i)=Find(j)表明表明i和和j在同一个子集中在同一个子集中nUnion(i,j)：将：将 i 和和 j 所在的子集合并所在的子集合并下标下标下标下标parent-1 -1 -1 -1 -1 -1 -1 -1 -1 -10 1 2 3 4 5 6 7 8
31、 9S1下标下标下标下标parent集合集合 S S1 1,S S2 2 和和 S S3 3 的双亲表示的双亲表示-4 4 -3 2 -3 2 0 0 0 40 1 2 3 4 5 6 7 8 9S2S30768000-4419-344235-322S1 S2的可能的表示方法的可能的表示方法下标下标下标下标parent集合集合 S1 S2 和和 S3 的双亲表示的双亲表示-7 4 -3 2 0 2 0 0 0 40 1 2 3 4 5 6 7 8 907684194190876-7-7000044444000用双亲表示实现并查集的类定义用双亲表示实现并查集的类定义 const int Defa
32、ultSize=10;class UFSets/集合中的各个子集合互不相交public:UFSets(int sz=DefaultSize);/构造函数 UFSets()delete parent;/析构函数 UFSets&operator=(UFSets&R);/集合赋值 void Union(int Root1,int Root2);/子集合并 int Find(int x);/查找x的根 void UnionByHeight(int Root1,int Root2);/改进例程:压缩高度的合并算法private:int*parent;/集合元素数组(双亲表示)int size;/集合元素
33、的数目;UFSets:UFSets(int sz)/构造函数：sz 是集合元素个数，双亲数组的/范围为parent0parentsize-1。size=sz;/集合元素个数 parent=new intsize;/创建双亲数组 for(int i=0;i size;i+)parenti=-1;/每个自成单元素集合;并查集操作的算法并查集操作的算法 查找查找-5012301234Find(4)Find(3)Find(2)Find(1)Find(0)-5 0 返回返回 0 -5 0 1 2 3parentParent4 =3 Parent3 =2Parent2 =1Parent1 =0Parent
34、0 =-50 1 2 3 4int UFSets:Find(int x)/函数搜索并返回包含元素x的树的根。/递归版本 if(parentx 0)return x;/根的parent值小于0 else return(Find(parentx);Find的非递归版本int UFSets:Find(int x)/函数搜索并返回包含元素x的树的根。while(parentx 0)x=parentx;returnx;这两个版本都有待改进Union的实现void UFSets:Union(int Root1,int Root2)/求两个不相交集合Root1与Root2的并 parentRoot1+=pa
35、rentRoot2;/注意，root1和root2都是根结点/-parentRoot1表示集合的元素总数 parentRoot2=Root1;/将Root2连接到Root1下面;下标下标下标下标parent-7 4 -3 2 0 2 0 0 0 40 1 2 3 4 5 6 7 8 90768419-7000044下标下标下标下标parent-4 4 -3 2 -3 2 0 0 0 40 1 2 3 4 5 6 7 8 9退化情况及其改进Union操作可能引起退化情况：操作可能引起退化情况：假设最初假设最初 n 个元素构成个元素构成 n 棵树组成的森林，棵树组成的森林，parenti=-1。做
36、处理。做处理Union(n-2,n-1),Union(1,2),Union(0,1)后，将产生退化的树。后，将产生退化的树。此时进行此时进行Find的话，平均需要的话，平均需要n/2次查询。次查询。改进的方法：尽量使得树变矮改进的方法：尽量使得树变矮 按树的结点个数合并按树的结点个数合并 按树的高度合并按树的高度合并 压缩元素的路径长度压缩元素的路径长度 朴素合并朴素合并-1-1-1-1-10 02 23 34 4-3-50321 13341332202314Union(0,1)-23-41421234Union(1,2)Union(2,3)Union(3,4)l按树结点个数合并按树结点个数合
37、并结点个数多的树的根结点作根结点个数多的树的根结点作根-1-1-1-1-101234-1-10-7256-5-2223320134 456233020562314Union(2,0)void UFSets:WeightedUnion(int Root1,int Root2)/按Union的加权规则改进的算法 int temp=parentRoot1+parentRoot2;if(parentRoot2 parentRoot1)parentRoot1=Root2;/Root2中结点数多 parentRoot2=temp;/Root1指向Root2 else parentRoot2=Root1;/
38、Root1中结点数多 parentRoot1=temp;/Root2指向Root1 ;l按树高度合并按树高度合并 高度高的树的根结点作根高度高的树的根结点作根-1-1-1-1-101234-1-10-3256-3-222332013456233020562314Union(2,0)按高度合并注意：在根结点中记录高度，而不是元素个数。void UFSets:WeightedUnion(int Root1,int Root2)/按Union的加权规则改进的算法，但是按照高度合并 if(parentRoot2=0;j=parentj);/让 j 循双亲指针走到根 while(parenti!=j)/
39、换 parenti 到 j int temp=parenti;parenti=j;i=temp;return j;实际例子ML语言的类型推理系统是一个函数式语言。ML语言不需要声明值的类型，且是强类型的。通过合一的方法推导出各个值的类型。x=head(l)得出l是list类型，x是这个list类型的元素类型；m=tail(l)；得出m和l的类型相同；y=x得出y和x是相同的类型；y=2得出y是整数类型，从而推导出x是整数类型；内容集合及其表示集合及其表示并查集与等价类并查集与等价类字典字典跳表跳表散列散列字典（字典（DictionaryDictionary）字典是一些元素的集合，每个元素有一个
40、称作字典是一些元素的集合，每个元素有一个称作关键码（关键码（key）的域，不同元素的关键码互不相）的域，不同元素的关键码互不相同。同。通常以文件（通常以文件（File）或者表格（）或者表格（Table）的方式）的方式出现。出现。在讨论字典抽象数据类型时，把字典定义为在讨论字典抽象数据类型时，把字典定义为对的集合。根据问题的不同，可以为对的集合。根据问题的不同，可以为名字和属性赋予不同的含义。名字和属性赋予不同的含义。从抽象的角度看，字典是一个从名字（或者说从抽象的角度看，字典是一个从名字（或者说Key）到属性的映射（）到属性的映射（MAP）。）。字典的典型操作1.确定一个指定的名字是否在字典中
41、；2.搜索出该名字的属性；3.修改该名字的属性；4.插入一个新的名字及其属性；5.删除一个名字及其属性。字典的抽象数据类型字典的抽象数据类型 const int DefaultSize=26;template class Dictionary/对象:一组对,其中,名字是唯一的public:Dictionary(int size=DefaultSize);/构造函数 bool Member(Name name);/判name是否在字典中 Attribute*Search(Name name);/在字典中搜索关键码与name匹配的表项 字典的抽象数据类型（续）字典的抽象数据类型（续）void In
42、sert(Name name,Attribute attr);/若name在字典中,则修改相应对 /的attr项;否则插入到字典中void Remove(Name name);/若name在字典中,则在字典中删除相应的 /对。否则无操作;索引项用文件记录（用文件记录（record）或表格的表项）或表格的表项（entry）来表示单个元素时，可以使用）来表示单个元素时，可以使用（key，记录或表项位置，记录或表项位置adr）构成搜索某一指定记录或表项的索引项。构成搜索某一指定记录或表项的索引项。可以通过索引项提高查找效率。可以通过索引项提高查找效率。具有重复元素的字典字典中的元素可以具有相同的关键
43、码（Key）。可能有多个元素具有相同的关键码，需要制定规则消除歧义，使得Find,Remove可以无歧义地执行；也可以Find/Remove所有的元素;字典的线性表描述保存在线性序列(e1,e2,)中，其中ei 是字典中的元素，其关键码从左到右依次增大。可以使用有序链表（有序顺序表）结构；每个结点表示字典中的一个元素各个结点按照结点中保存的数据值非递减链接。#include#include“SeqList.h”const int defaultSize=50;template class SortedList:public SeqList public:int Search(K k1)cons
44、t;/搜索 void Insert(const K k1,E&e1);/插入 bool Remove(const K k1,E&e1);/删除;有序顺序表的类定义基于有序顺序表的顺序搜索算法template int SortedList:Search(K k1)const/顺序搜索关键码为x的数据对象 for(int i=1;i k1)break;return 0;/顺序搜索失败,返回失败信息;l算法中的算法中的“=”和和“”都是重载函数，在定都是重载函数，在定义义E时定义它们的实现。时定义它们的实现。有序顺序表顺序搜索的时间代价有序顺序表顺序搜索的时间代价搜索算法的时间效率的衡量标准搜索算法
45、的时间效率的衡量标准在搜索过程中关键码平均比较次数，也称为平均在搜索过程中关键码平均比较次数，也称为平均搜索长度搜索长度ASL(Average Search Length)，通常它，通常它是字典中元素总数是字典中元素总数 n 的函数。的函数。设搜索第设搜索第 i 个元素的概率为个元素的概率为 pi,搜索到第搜索到第 i 个个元素所需比较次数为元素所需比较次数为 ci,则搜索成功的平均则搜索成功的平均搜索长度搜索长度：（只考虑了搜索成功的情况）（只考虑了搜索成功的情况）在顺序搜索情形，搜索第在顺序搜索情形，搜索第 i(1in)个元素需个元素需要比较要比较 i 次，假定按等概率搜索各元素：次，假定
46、按等概率搜索各元素：这与一般顺序表情形相同。但搜索不成功时这与一般顺序表情形相同。但搜索不成功时不需一直比较到表尾，只要发现下一个元素不需一直比较到表尾，只要发现下一个元素的值比给定值大，就可断定搜索不成功。的值比给定值大，就可断定搜索不成功。基于有序顺序表的折半搜索基于有序顺序表的折半搜索l设设 n 个元素存放在一个有序顺序表中。个元素存放在一个有序顺序表中。l折折半半搜搜索索时时,先先求求位位于于搜搜索索区区间间正正中中的的元元素素的的下标下标mid，用其关键码与给定值，用其关键码与给定值 x 比较比较:l datamid.key=x，搜索成功；，搜索成功；l datamid.key x，
47、把把搜搜索索区区间间缩缩小小到到表表的的前半部分前半部分，继续折半搜索；，继续折半搜索；l datamid.key x，把把搜搜索索区区间间缩缩小小到到表表的的后半部分后半部分，继续折半搜索。，继续折半搜索。l如如果果搜搜索索区区间间已已缩缩小小到到一一个个对对象象，仍仍未未找找到到想要搜索的对象，则搜索失败。想要搜索的对象，则搜索失败。搜索成功的例子搜索成功的例子-1 0 1 3 4 6 8 10 1260 1 2 3 4 5 6 7 8搜索搜索给定值给定值lowmidhigh6 6 8 10 125 6 7 8low midhigh665low mid high6搜索失败的例子搜索失败的例
48、子-1 0 1 3 4 6 8 10 1250 1 2 3 4 5 6 7 8搜索搜索给定值给定值lowmidhigh5 6 8 10 125 6 7 8low midhigh655low mid high5templateint SortedList:BinarySearch (K k1,const int low,const int high)const/折半搜索的递归算法，用到E的重载操作“”int mid=0;/元素序号从1开始 if(low=high)mid=(low+high)/2;if(datamid-1 k1)mid=BinarySearch(k1,low,mid-1);ret
49、urn mid;注：这个递归算法是一个尾递归，可以转化为迭代注：这个递归算法是一个尾递归，可以转化为迭代字典的有序链表实现字典的有序链表实现#include template struct ChainNode/链表结点类定义 E data;ChainNode*link;ChainNode():link(NULL);/构造函数 ChainNode(E&e1,/构造函数 ChainNode*next=NULL):data(e1),link(next);template class SortedChain/有序链表类定义private:ChainNode*first;/链表的头指针public:So
50、rtedChain()/构造函数 first=new ChainNode;assert(first!=NULL);SortedChain();/析构函数 ChainNode*Search(K k1);/搜索 void Insert(const K k1,E&e1);/插入 bool Remove(const K k1,E&e1);/删除 /用于遍历的接口；用于遍历的接口；ChainNode*Begin()return first-link;/定位第一个 ChainNode*Next(ChainNode *current)const /定位下一个 return(current!=NULL)?cu