《《数据结构与算法》PPT课堂课件-集合和搜索.pdf》由会员分享，可在线阅读，更多相关《《数据结构与算法》PPT课堂课件-集合和搜索.pdf（147页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、n n集集集集合合合合及及及及其其其其表表表表示示示示n n并并并并查查查查集集集集n n静静静静态态态态搜搜搜搜索索索索表表表表n n二二二二叉叉叉叉搜搜搜搜索索索索树树树树n nAVLAVL树树树树集集集集合合合合基基基基本本本本概概概概念念念念集集集集合合合合及及及及其其其其表表表表示示示示n n集集集集合合合合是是是是成成成成员员员员( ( ( (对对对对象象象象或或或或元元元元素素素素) ) ) )的的的的一一一一个个个个群群群群集集集集。集集集集合合合合中中中中的的的的成成成成员员员员可可可可以以以以是是是是原原原原子子子子( ( ( (单单单单元元元元素素素素) ) ) )，也也
2、也也可可可可以以以以是是是是集集集集合合合合。n n集集集集合合合合的的的的成成成成员员员员必必必必须须须须互互互互不不不不相相相相同同同同。n n在在在在算算算算法法法法与与与与数数数数据据据据结结结结构构构构中中中中所所所所遇遇遇遇到到到到的的的的集集集集合合合合，其其其其单单单单元元元元素素素素通通通通常常常常是是是是整整整整数数数数、字字字字符符符符、字字字字符符符符串串串串或或或或指指指指针针针针，且且且且同同同同一一一一集集集集合合合合中中中中所所所所有有有有成成成成员员员员具具具具有有有有相相相相同同同同的的的的数数数数据据据据类类类类型型型型。 colourcolour = =
3、 red, orange, yellow, green, red, orange, yellow, green, black, blue, purple, white black, blue, purple, white namename = = “An”, “ “An”, “CaoCao”, “Liu”, “Ma”, ”, “Liu”, “Ma”, “ “PengPeng”, “Wang”, “”, “Wang”, “zhangzhang” ” n n集集集集合合合合中中中中的的的的成成成成员员员员一一一一般般般般是是是是无无无无序序序序的的的的，但但但但在在在在表表表表示示示示它它它它时时
4、时时，常常常常写写写写在在在在一一一一个个个个序序序序列列列列里里里里。n n常常常常设设设设定定定定集集集集合合合合中中中中的的的的单单单单元元元元素素素素具具具具有有有有线线线线性性性性有有有有序序序序关关关关系系系系，此此此此关关关关系系系系可可可可记记记记作作作作“ “”，表表表表示示示示“ “优优优优先先先先于于于于” ”。n n整整整整数数数数、字字字字符符符符和和和和字字字字符符符符串串串串都都都都有有有有一一一一个个个个自自自自然然然然线线线线性性性性顺顺顺顺序序序序。指指指指针针针针也也也也可可可可依依依依据据据据其其其其在在在在序序序序列列列列中中中中安安安安排排排排的的的
5、的位位位位置置置置给给给给予予予予一一一一个个个个线线线线性性性性顺顺顺顺序序序序。集集集集合合合合( (SetSet) )的的的的抽抽抽抽象象象象数数数数据据据据类类类类型型型型template class Set Set (int MaxSetSize) : MaxSize(MaxSetSize); void MakeEmpty (Set& s); int AddMember (Set& s, const Type x); int DelMember (Set& s, const Type& x);A B 或 A+B A B 或 A B A- -BAAABBB void Assign (S
6、et& s1, Set& s2); void Union (Set& s1, Set& s2); void Intersection (Set& s1, Set& s2); void Difference (Set& s1, Set& s2); int Contains (Set& s, const Type& x); int Equal (Set& s1, Set& s2); int SubSet (Set& s1, Set& s2);用用用用位位位位向向向向量量量量实实实实现现现现集集集集合合合合抽抽抽抽象象象象数数数数据据据据类类类类型型型型n n 当当当当集集集集合合合合是是是是全全全
7、全集集集集合合合合 0, 1, 2, 0, 1, 2, , , n n 的的的的一一一一个个个个子子子子集集集集，且且且且 n n是是是是不不不不大大大大的的的的整整整整数数数数时时时时，可可可可用用用用位位位位(0, 1)(0, 1)向向向向量量量量来来来来实实实实现现现现集集集集合合合合。n n 当当当当全全全全集集集集合合合合是是是是由由由由有有有有限限限限的的的的可可可可枚枚枚枚举举举举的的的的成成成成员员员员组组组组成成成成的的的的集集集集合合合合时时时时，可可可可建建建建立立立立全全全全集集集集合合合合成成成成员员员员与与与与整整整整数数数数 0, 1, 2, 0, 1, 2, 的
8、的的的一一一一一一一一对对对对应应应应关关关关系系系系，用用用用位位位位向向向向量量量量来来来来表表表表示示示示该该该该集集集集合合合合的的的的子子子子集集集集。集集集集合合合合的的的的位位位位向向向向量量量量( (bit Vector)bit Vector)类类类类的的的的定定定定义义义义#include const int DefaultSize = 100;class Set private: int * bitVector; int MaxSize;public: Set ( int MaxSetSize = DefaultSize ); Set ( ) delete bitVecto
9、r; void MakeEmpty ( ) for ( int i = 0; i = 0 & x MaxSize ? bitVectorx : -1; int AddMember ( const int x ); int DelMember ( const int x ); Set& operator = ( Set& right ); Set& operator + ( Set& right ); Set& operator * ( Set& right ); Set& operator - ( Set& right ); int Contains ( const int x ); int
10、SubSet ( Set& right ); int operator = ( Set& right );使使使使用用用用示示示示例例例例Set s1, s2, s3, s4, s5; int index, 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 s3 = s1+s2; /求s1与s2的并 0, 1, , 16 s4 = s1*s2; /求s1与s2的交 7, 8, 9 s5 = s
11、1-s2; /求s1与s2的差 0, 1, , 6 / s1 : 0, 1, 2, , 9 index = s1.SubSet ( s4 ); /s4在s1中首次匹配 cout index endl; /位置，index = 7 / s1 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 / s4 : 7, 8, 9 equal = s1 = s2; /集合s1与s2比较相等 cout equal 0 ); bitVector = new int MaxSize; assert ( bitVector != 0 ); for ( int i = 0; i = 0 & x = 0 &
12、 x MaxSize ); if ( bitVectorx ) bitVectorx = 0; return 1; return 0; Set& Set : operator = ( Set& right ) assert ( MaxSize = right.MaxSize ); for ( int i = 0; i = 0 & x MaxSize ); return bitVectorx;Set& Set : operator + ( Set& right ) assert ( MaxSize = right.MaxSize ); Set temp ( MaxSize ); for ( in
13、t i = 0; i MaxSize; i+ ) temp.bitVectori = bitVectori | right.bitVectori; return temp;thisrighttemp0 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 0Set& Set : operator * ( Set & right ) assert ( MaxSize = right.MaxSize ); Set temp ( MaxSize ); for ( int i = 0; i MaxSize; i+) temp.bitVe
14、ctori = bitVectori & right.bitVectori; return temp;thisrighttemp0 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 0Set& Set : operator - ( Set & right ) assert ( MaxSize = right.MaxSize ); Set temp ( MaxSize ); for ( int i = 0; i MaxSize; i+ ) temp. bitVectori = bitVectori & !right.bitVe
15、ctori; return temp;thisrighttemp0 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 0int Set : operator = ( Set& right ) assert ( MaxSize = right.MaxSize ); for ( int i = 0; i MaxSize; i+) if ( bitVectori != right.bitVectori ) return 0; return 1;thisright0 0 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0
16、1 0 1 0iint Set : SubSet (Set& right ) assert ( MaxSize = right.MaxSize ); for ( int i = 0; i MaxSize; i+) if (bitVectori & ! right.bitVectori) return 0; return 1;thisright0 0 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 01 1 0 1 1 0 1 0 1 0 1i用用用用有有有有序序序序链链链链表表表表实实实实现现现现集集集集合合合合的的的的抽抽抽抽象象象象数数数数据据据据类类类类型型型型
17、用用用用带带带带表表表表头头头头结结结结点点点点的的的的有有有有序序序序链链链链表表表表表表表表示示示示集集集集合合合合firstfirst081723354972n n用用用用有有有有序序序序链链链链表表表表来来来来表表表表示示示示集集集集合合合合时时时时，链链链链表表表表中中中中的的的的每每每每个个个个结结结结点点点点表表表表示示示示集集集集合合合合的的的的一一一一个个个个成成成成员员员员。n n各各各各结结结结点点点点所所所所表表表表示示示示的的的的成成成成员员员员 e e0 0, , e e1 1, , , , e en n 在在在在链链链链表表表表中中中中按按按按升升升升序序序序排排
18、排排列列列列，即即即即 e e0 0 e e1 1 e en n。n n集集集集合合合合成成成成员员员员可可可可以以以以无无无无限限限限增增增增加加加加。因因因因此此此此，用用用用有有有有序序序序链链链链表表表表可可可可以以以以表表表表示示示示无无无无穷穷穷穷全全全全集集集集合合合合的的的的子子子子集集集集。template class SetList;template class SetNode friend class SetList;public: SetNode (const Type& item ) : data (item), link (NULL);private: Type d
19、ata; SetNode * link; 集集集集合合合合的的的的有有有有序序序序链链链链表表表表类类类类的的的的定定定定义义义义template class SetList private: SetNode *first, *last; /有序链表的表头指针, 表尾指针public: SetList ( ) /构造函数 first = last = new SetNode(0); SetList ( ) MakeEmpty( ); delete first; void MakeEmpty ( ); /置空集合 int AddMember ( const Type& x ); int DelM
20、ember ( const Type& x );SetList & operator = ( SetList& right ); /将集合right赋给集合this SetList & operator + ( SetList& right ); /求集合this与集合right的并SetList & operator * ( SetList& right ); /求集合this与集合right的交SetList & operator - ( SetList& right ); /求集合this与集合right的差int Contains ( const Type& x ); /判x是否集合的
21、成员int operator = ( SetList& right ); /判集合this与集合right相等 Type& Min ( ); /返回集合中最小元素值 Type& Max ( ); /返回集合中最大元素值 集集集集合合合合的的的的搜搜搜搜索索索索、加加加加入入入入和和和和删删删删除除除除操操操操作作作作template int SetList :Contains ( const Type& x ) /若x是集合成员, 则函数返回1, 否则返回0 SetNode * temp = first-link; while ( temp != NULL & temp-data link;
22、/循链搜索 if ( temp != NULL & temp-data = x ) return 1;/找到, 返回1 else return 0;/未找到, 返回0template int SetList :AddMember ( const Type& x ) SetNode *p = first-link, *q = first; while ( p != NULL & p-data link; /循链扫描 if ( p != NULL & p-data = x ) return 0; /集合中已有此元素 SetNode * s = new SetNode (x); s-link = p
23、; q-link = s; /链入 if ( p = NULL ) last = s; /链到链尾时改链尾指针 return 1;template int SetList :DelMember ( const Type& x ) SetNode * p = first-link, * q = first; while ( p != NULL & p-data link; /循链扫描 if ( p != NULL & p-data = x ) /找到 q-link = p-link;/重新链接 if ( p = last ) last = q; /删去链尾结点时改链尾指针 delete p; r
24、eturn 1;/删除含x结点 else return 0; /集合中无此元素用用用用有有有有序序序序链链链链表表表表表表表表示示示示集集集集合合合合时时时时的的的的几几几几个个个个重重重重载载载载函函函函数数数数template SetList& SetList : operator = ( SetList& right ) /复制集合right到this SetNode * pb = right.first-link; /源 SetNode * pa = first = /目标 new SetNode; while ( pb != NULL ) /逐个结点复制 pa-link = new
25、SetNode(pb-data); pa = pa-link; pb = pb-link; pa-link = NULL; last = pa; return *this; /目标链表收尾/求求集集合合this与与集集合合right的的并并, 结结果果通通过过临临时时/集集合合temp返返回回，this集集合合与与right集集合合不不变变。 template SetList& SetList : operator + ( SetList& right ) firstright.first08172349temp.first231735papbpc0817233549 SetNode *pb
26、= right.first-link; SetNode *pa = first-link; SetList temp; SetNode *pc = temp.first; while ( pa != NULL & pb != NULL ) if ( pa-data = pb-data ) /共有元素 pc-link=new SetNode(pa-data); pa = pa-link; pb = pb-link; else if ( pa-data data ) pc-link=new SetNode(pa-data); pa = pa-link; else /pa-data pb-data
27、pc-link=new SetNode(pb-data); pb = pb-link; pc = pc-link; if ( pa != NULL ) pb = pa; /pb指未扫完集合 while ( pb != NULL ) /向结果链逐个复制 pc-link = new SetNode(pb-data); pc = pc-link; pb = pb-link; pc-link = NULL; temp.last = pc; /链表收尾 return temp;template int SetList : operator = ( SetList & right ) SetNode *
28、pb = right.first-link; SetNode * pa = first-link; while ( pa != NULL & pb != NULL ) if ( pa-data = pb-data ) /相等, 继续 pa = pa-link; pb = pb-link; else return 0; /不等时中途退出, 返回0 if ( pa != NULL | pb != NULL ) return 0; /链不等长时, 返回0 return 1;并并并并查查查查集集集集 ( (Union-Find Sets)Union-Find Sets)n n并并并并查查查查集集集集支
29、支支支持持持持以以以以下下下下三三三三种种种种操操操操作作作作：uu UnionUnion ( (RootRoot1, 1, RootRoot2)2) / /并并并并操操操操作作作作uu Find Find ( (x x) ) / /搜搜搜搜索索索索操操操操作作作作uu UFSetsUFSets ( (s s) ) / /构构构构造造造造函函函函数数数数n n对对对对于于于于并并并并查查查查集集集集来来来来说说说说，每每每每个个个个集集集集合合合合用用用用一一一一棵棵棵棵树树树树表表表表示示示示。n n为为为为此此此此，采采采采用用用用树树树树的的的的双双双双亲亲亲亲表表表表示示示示作作作作为
30、为为为集集集集合合合合存存存存储储储储表表表表示示示示。集集集集合合合合元元元元素素素素的的的的编编编编号号号号从从从从0 0到到到到 n n- - - -1 1。其其其其中中中中 n n 是是是是最最最最大大大大元元元元素素素素个个个个数数数数。n n在在在在双双双双亲亲亲亲表表表表示示示示中中中中，第第第第 i i 个个个个数数数数组组组组元元元元素素素素代代代代表表表表包包包包含含含含集集集集合合合合元元元元素素素素 i i 的的的的树树树树结结结结点点点点。根根根根结结结结点点点点的的的的双双双双亲亲亲亲为为为为- - - -1 1，表表表表示示示示集集集集合合合合中中中中的的的的元元
31、元元素素素素个个个个数数数数。n n在在在在同同同同一一一一棵棵棵棵树树树树上上上上所所所所有有有有结结结结点点点点所所所所代代代代表表表表的的的的集集集集合合合合元元元元素素素素在在在在同同同同一一一一个个个个子子子子集集集集合合合合中中中中。n n为为为为此此此此，需需需需要要要要有有有有两两两两个个个个映映映映射射射射：uu 集集集集合合合合元元元元素素素素到到到到存存存存放放放放该该该该元元元元素素素素名名名名的的的的树树树树结结结结点点点点间间间间的的的的对对对对应应应应；uu 集集集集合合合合名名名名到到到到表表表表示示示示该该该该集集集集合合合合的的的的树树树树的的的的根根根根结
32、结结结点点点点间间间间的的的的对对对对应应应应。n n设设设设 S S1 1= 0, 6, 7, 8 , = 0, 6, 7, 8 , S S2 2= 1, 4, 9 , = 1, 4, 9 , S S3 3= 2, 3, = 2, 3, 5 5 集集合合名名 指指针针0 S11 S22 S30427681935n n为为为为简简简简化化化化讨讨讨讨论论论论，忽忽忽忽略略略略实实实实际际际际的的的的集集集集合合合合名名名名，仅仅仅仅用用用用表表表表示示示示集集集集合合合合的的的的树树树树的的的的根根根根来来来来标标标标识识识识集集集集合合合合。n n初初初初始始始始时时时时, , 用用用用构构
33、构构造造造造函函函函数数数数 UFSetsUFSets(s) (s) 构构构构造造造造一一一一个个个个森森森森林林林林, , 每每每每棵棵棵棵树树树树只只只只有有有有一一一一个个个个结结结结点点点点, , 表表表表示示示示集集集集合合合合中中中中各各各各元元元元素素素素自自自自成成成成一一一一个个个个子子子子集集集集合合合合。n n用用用用 Find(i) Find(i) 寻寻寻寻找找找找集集集集合合合合元元元元素素素素 i i 的的的的根根根根。如如如如果果果果有有有有两两两两个个个个集集集集合合合合元元元元素素素素 i i 和和和和 j j, , Find(i) Find(i) = = F
34、ind(j)Find(j), , 表表表表明明明明这这这这两两两两个个个个元元元元素素素素在在在在同同同同一一一一个个个个集集集集合合合合中中中中，n n如如如如果果果果两两两两个个个个集集集集合合合合元元元元素素素素 i i 和和和和 j j 不不不不在在在在同同同同一一一一个个个个集集集集合合合合中中中中, ,可可可可用用用用 Union(i, Union(i, j) j) 将将将将它它它它们们们们合合合合并并并并到到到到一一一一个个个个集集集集合合合合中中中中。S S1 1 S S2 2的的的的可可可可能能能能的的的的表表表表示示示示方方方方法法法法下下下下标标标标parent集集合合
35、S S1 1, , S S2 2 和和 S S3 3 的的双双亲亲表表示示- -1 4 - -1 2 - -1 2 0 0 0 40 1 2 3 4 5 6 7 8 907684194190876const int DefaultSize = 10;class UFSets /并查集类定义private: int *parent; /集合元素数组 int size; /集合元素的数目public: UFSets ( int s = DefaultSize ); /构造函数 UFSets ( ) delete parent; /析构函数 const UFSets& operator = (UFS
36、ets& right); /重载函数：集合赋值 void Union ( int Root1, int Root2 );/基本例程 : 两个子集合合并 int Find ( int x );/基本例程 : 搜寻集合x的根 void UnionByHeight ( int Root1, int Root2 );/改进例程 : 压缩高度的合并算法;UFSets : UFSets ( int s ) /构造函数 size = s; /集合元素个数 parent = new int size; /双亲指针数组 for ( int i = 0; i size; i+ ) parenti = -1;/每一
37、个自成一个单元素集合% 并并并并查查查查集集集集操操操操作作作作的的的的算算算算法法法法n n 查查查查找找找找- - - -501230 01 12 23 34 4Find (4)Find (3) = 3 Find (2) =2 Find (1) = 1Find (0) = 0 = - -5 0 结结结结束束束束int UFSets : Find ( int x ) if ( parent x 0 ) return x; else return Find ( parent x ); -5 0 1 2 35 0 1 2 3parentparentParent4 =3 Parent3 =2Par
38、ent2 =1Parent1 =0Parent0 =-50 1 2 3 4void UFSets : Union ( int Root1, int Root2 ) /求两个不相交集合Root1与Root2的并 parentRoot2 = Root1; /将Root2连接到Root1下面n nFindFind和和和和UnionUnion操操操操作作作作性性性性能能能能不不不不好好好好。假假假假设设设设最最最最初初初初 n n 个个个个元元元元素素素素构构构构成成成成 n n 棵棵棵棵树树树树组组组组成成成成的的的的森森森森林林林林，parenti parenti = = - - - -1 1。做
39、做做做处处处处理理理理Union(nUnion(n- - - -2, n2, n- - - -1), 1), , , Union(1, Union(1, 2)2), , Union(0, 1)Union(0, 1)后后后后，将将将将产产产产生生生生退退退退化化化化的的的的树树树树。n n合合合合并并并并- - - -1- - - -1- - - -1- - - -1- - - -10 02 23 34 4- - - -3- - - -5032 21 13 33 34 4133220 02 23 31 14 4Union(0,1)- - - -23- - - -414 421 12 23 34
40、4Union(1,2)Union(2,3)Union(3,4)n n 执执执执行行行行一一一一次次次次UnionUnion操操操操作作作作所所所所需需需需时时时时间间间间是是是是 O(1)O(1)，n n- - - -1 1次次次次UnionUnion操操操操作作作作所所所所需需需需时时时时间间间间是是是是O(n)O(n)。n n 若若若若再再再再执执执执行行行行Find(0)Find(0), , Find(1)Find(1), , , , Find(nFind(n- - - -1)1), , 若若若若被被被被搜搜搜搜索索索索的的的的元元元元素素素素为为为为 i i，完完完完成成成成 Find
41、(i) Find(i) 操操操操作作作作需需需需要要要要时时时时间间间间为为为为O(i)O(i)，完完完完成成成成 n n 次次次次搜搜搜搜索索索索需需需需要要要要的的的的总总总总时时时时间间间间将将将将达达达达到到到到n n 改改改改进进进进的的的的方方方方法法法法uu 按按按按树树树树的的的的结结结结点点点点个个个个数数数数合合合合并并并并uu 按按按按树树树树的的的的高高高高度度度度合合合合并并并并uu 压压压压缩缩缩缩元元元元素素素素的的的的路路路路径径径径长长长长度度度度n n按按按按树树树树结结结结点点点点个个个个数数数数合合合合并并并并结结结结点点点点个个个个数数数数多多多多的的
42、的的树树树树的的的的根根根根结结结结点点点点作作作作根根根根- - - -1- - - -1- - - -1- - - -1- - - -10 01 12 23 34 4- - - -1- - - -10- - - -725 56 6- - - -5- - - -222332 20 01 13 34 45 56 6233020 05 56 62 23 31 14 4Union(2, 0)void UFSets : WeightedUnion ( int Root1, int Root2 ) / /按Union的加权规则改进的算法 int temp = parentRoot1 + parentR
43、oot2; if ( parentRoot2 = 0; j = parentj ); /让 j 循双亲指针走到根 while ( i != j ) /换 parenti 到 j int temp = parenti; parenti = j; i = temp; return j;搜搜搜搜索索索索( (Search)Search)的的的的概概概概念念念念静静静静态态态态搜搜搜搜索索索索表表表表n n 所所所所谓谓谓谓搜搜搜搜索索索索，就就就就是是是是在在在在数数数数据据据据集集集集合合合合中中中中寻寻寻寻找找找找满满满满足足足足某某某某 种种种种条条条条件件件件的的的的数数数数据据据据对对对对
44、象象象象。n n 搜搜搜搜索索索索的的的的结结结结果果果果通通通通常常常常有有有有两两两两种种种种可可可可能能能能：uu 搜搜搜搜索索索索成成成成功功功功，即即即即找找找找到到到到满满满满足足足足条条条条件件件件的的的的数数数数据据据据对对对对象象象象 这这这这时时时时, ,作作作作为为为为结结结结果果果果, , 可可可可报报报报告告告告该该该该对对对对象象象象在在在在结结结结构构构构中中中中 的的的的位位位位置置置置, , 还还还还可可可可给给给给出出出出该该该该对对对对象象象象中中中中的的的的具具具具体体体体信信信信息息息息。uu 搜搜搜搜索索索索不不不不成成成成功功功功，或或或或搜搜搜搜
45、索索索索失失失失败败败败。作作作作为为为为结结结结果果果果, , 应应应应报报报报告告告告一一一一些些些些信信信信息息息息, , 如如如如失失失失败败败败标标标标志志志志、位位位位置置置置等等等等。 n n通通通通常常常常称称称称用用用用于于于于搜搜搜搜索索索索的的的的数数数数据据据据集集集集合合合合为为为为搜搜搜搜索索索索结结结结构构构构，它它它它是是是是由由由由同同同同一一一一数数数数据据据据类类类类型型型型的的的的对对对对象象象象( (或或或或记记记记录录录录) )组组组组成成成成。n n在在在在每每每每个个个个对对对对象象象象中中中中有有有有若若若若干干干干属属属属性性性性，其其其其中
46、中中中有有有有一一一一个个个个属属属属性性性性，其其其其值值值值可可可可唯唯唯唯一一一一地地地地标标标标识识识识这这这这个个个个对对对对象象象象。称称称称为为为为关关关关键键键键码码码码。使使使使用用用用基基基基于于于于关关关关键键键键码码码码的的的的搜搜搜搜索索索索，搜搜搜搜索索索索结结结结果果果果应应应应是是是是唯唯唯唯一一一一的的的的。但但但但在在在在实实实实际际际际应应应应用用用用时时时时，搜搜搜搜索索索索条条条条件件件件是是是是多多多多方方方方面面面面的的的的，可可可可以以以以使使使使用用用用基基基基于于于于属属属属性性性性的的的的搜搜搜搜索索索索方方方方法法法法，但但但但搜搜搜搜索
47、索索索结结结结果果果果可可可可能能能能不不不不唯唯唯唯一一一一。n n实实实实施施施施搜搜搜搜索索索索时时时时有有有有两两两两种种种种不不不不同同同同的的的的环环环环境境境境。n n 静静静静态态态态环环环环境境境境，搜搜搜搜索索索索结结结结构构构构在在在在插插插插入入入入和和和和删删删删除除除除等等等等操操操操作作作作的的的的前前前前后后后后不不不不发发发发生生生生改改改改变变变变。 静静静静态态态态搜搜搜搜索索索索表表表表 n n动动动动态态态态环环环环境境境境，为为为为保保保保持持持持较较较较高高高高的的的的搜搜搜搜索索索索效效效效率率率率, , , , 搜搜搜搜索索索索结结结结构构构构
48、在在在在执执执执行行行行插插插插入入入入和和和和删删删删除除除除等等等等操操操操作作作作的的的的前前前前后后后后将将将将自自自自动动动动进进进进行行行行调调调调整整整整，结结结结构构构构可可可可能能能能发发发发生生生生变变变变化化化化。 动动动动态态态态搜搜搜搜索索索索表表表表 静静静静态态态态搜搜搜搜索索索索表表表表template class dataList; template class Node friend class dataList;private: Type key; other;public: Node ( const Type& value ) : key (value)
49、 Type getKey ( ) const return key; void setKey ( Type k ) key = k; ;template class dataList protected: Node *Element; /数据存储数组 int ArraySize, CurrentSize;/数组最大长度和当前长度public: dataList ( int sz = 10 ) : ArraySize (sz) Element = new Node sz; virtual dataList ( ) delete Element; friend ostream& operator
50、(ostream& OutStream, const dataList& OutList ); friend istream & operator ( istream& InStream, dataList& InList );template class searchList : public dataList /作为派生类的静态搜索表的类定义public: searchList ( int sz = 10 ) : dataList (sz) virtual searchList ( ) virtual int Search ( const Type & x ) const;template