运算符重载精品文稿.ppt

运算符重载第1页，本讲稿共55页10.1 10.1 查找的基本概念查找的基本概念 查找查找:查询查询关键字关键字是否在是否在(数据元素集合）表中的过程。也称作数据元素集合）表中的过程。也称作检索检索。主关键字主关键字:能够惟一区分各个不同数据元素的关键字能够惟一区分各个不同数据元素的关键字次关键字次关键字:通常不能惟一区分各个不同数据元素的关键字通常不能惟一区分各个不同数据元素的关键字查找成功查找成功:在数据元素集合中找到了要查找的数据元素在数据元素集合中找到了要查找的数据元素查找不成功查找不成功:在数据元素集合中没有找到要查找的数据元素在数据元素集合中没有找到要查找的数据元素静态查找静态查找:只查找，不改变数据元素集合内的数据元素只查找，不改变数据元素集合内的数据元素动态查找动态查找:既查找，又改变（增减）集合内的数据元素既查找，又改变（增减）集合内的数据元素静态查找表静态查找表:静态查找时构造的存储结构静态查找时构造的存储结构动态查找表动态查找表:动态查找时构造的存储结构动态查找时构造的存储结构平均查找长度平均查找长度:查找过程所需进行的关键字比较次数的平均值查找过程所需进行的关键字比较次数的平均值,是衡量查找算法效率的最主是衡量查找算法效率的最主要标准要标准,其数学定义为：其数学定义为：第2页，本讲稿共55页10.2 10.2 静态查找表静态查找表 静态查找表主要有三种结构：静态查找表主要有三种结构：顺序表顺序表 有序顺序表有序顺序表 索引顺序表索引顺序表第3页，本讲稿共55页1.1.顺序表顺序表 在顺序表上查找的在顺序表上查找的基本思想是：基本思想是：从顺序表的一端开始，用给从顺序表的一端开始，用给定数据元素的关键字逐个和顺序表中各数据元素的关键字比较，定数据元素的关键字逐个和顺序表中各数据元素的关键字比较，若在顺序表中查找到要查找的数据元素，则查找成功，函数返回若在顺序表中查找到要查找的数据元素，则查找成功，函数返回该数据元素在顺序表中的位置；否则查找失败，函数返回该数据元素在顺序表中的位置；否则查找失败，函数返回-1-1。查找函数设计如下：查找函数设计如下：intSeqSearch(DataTypea,intn,KeyTypekey)/在在a0-an-1中顺序查找关键码为中顺序查找关键码为key的数据元素的数据元素/查找成功时返回该元素的下标序号；失败时返回查找成功时返回该元素的下标序号；失败时返回-1inti=0;while(in&ai.key!=key)i+;if(ai.key=key)returni;elsereturn-1;第4页，本讲稿共55页算法分析算法分析查找成功时的平均查找长度查找成功时的平均查找长度ASLASL成功成功为：为：查找失败时的平均查找长度查找失败时的平均查找长度ASLASL失败失败为为 时间效率为时间效率为 O(n)第5页，本讲稿共55页2.2.有序顺序表有序顺序表 有序顺序表上的查找算法主要有有序顺序表上的查找算法主要有顺序查找顺序查找和和折半查找折半查找两种方法。两种方法。一、顺序查找一、顺序查找有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同 二、二分查找（二、二分查找（又称又称折半查找）折半查找）算法的基本思想：算法的基本思想：先给数据排序先给数据排序（例如按升序排好），形成（例如按升序排好），形成有有序表，序表，然后再将然后再将keykey与与正中正中元素相比，若元素相比，若keykey小，则缩小至前半小，则缩小至前半部内查找；再取其部内查找；再取其中值中值比较，每次缩小比较，每次缩小1/21/2的范围，直到查找的范围，直到查找成功或失败为止。反之，如果成功或失败为止。反之，如果keykey大，则缩小至后半部内查找。大，则缩小至后半部内查找。第6页，本讲稿共55页二分查找算法如下：二分查找算法如下：intBiSearch(DataTypea,intn,KeyTypekey)/在有序表在有序表a0-an-1中二分查找关键码为中二分查找关键码为key的数据元素的数据元素/查找成功时返回该元素的下标序号；失败时返回查找成功时返回该元素的下标序号；失败时返回-1intlow=0,high=n-1;/确定初始查找区间上下界确定初始查找区间上下界intmid;while(low=high)mid=(low+high)/2;/确定查找区间中心下标确定查找区间中心下标if(amid.key=key)returnmid;/查找成功查找成功elseif(amid.keykey)low=mid+1;elsehigh=mid-1;return-1;/查找失败查找失败第7页，本讲稿共55页算法分析算法分析查找成功时的平均查找长度查找成功时的平均查找长度ASLASL成功成功为：为：查找失败时的平均查找长度查找失败时的平均查找长度ASLASL失败失败为为 第8页，本讲稿共55页3.3.索引顺序表索引顺序表 当顺序表中的数据元素个数非常大时，采用当顺序表中的数据元素个数非常大时，采用在顺序表上建在顺序表上建立索引表立索引表的办法提高查找速度。把要在其上建立索引表的顺序的办法提高查找速度。把要在其上建立索引表的顺序表称作表称作主表主表。主表中存放着数据元素的。主表中存放着数据元素的全部信息全部信息，索引表中只，索引表中只存放主表中要查找数据元素的存放主表中要查找数据元素的主关键字和索引信息主关键字和索引信息。8146910223418193140385466467178688085140034516610285153keylink下标下标索引表索引表012345678910111213141516171819key其它域其它域位置位置主表主表索引表结构图索引表结构图 索索引引表表中中的的数数据据元元素素由由两两个个域域构构成成，keykey域域为为被被索索引引的的若若干干个个数数据据元元素素中中关关键键字字的的最最大大值值，linklink域域为为被被索索引引的的若若干干个个数数据据元元素素中中第第一一个个数数据据元元素素的的位位置置编号。编号。第9页，本讲稿共55页完全索引表完全索引表:和主表项完全相同，但只包含索引关键字和该数和主表项完全相同，但只包含索引关键字和该数据元素在主表中位置信息的索引表据元素在主表中位置信息的索引表二级索引表二级索引表:当主表中的数据元素个数非常庞大时，按照建立当主表中的数据元素个数非常庞大时，按照建立索引表的同样方法对索引表再建立的索引表。二级以上的索引索引表的同样方法对索引表再建立的索引表。二级以上的索引结构称作结构称作多级索引结构多级索引结构等长索引表等长索引表:索引表中的每个索引项对应主表中的数据元素个索引表中的每个索引项对应主表中的数据元素个数相等数相等;反之称为反之称为不等长索引表不等长索引表。不等长索引表中的。不等长索引表中的索引长度索引长度可随着动态插入和动态删除过程改变可随着动态插入和动态删除过程改变,因此不仅适用于因此不仅适用于静态查静态查找找问题，而且也适用于问题，而且也适用于动态查找动态查找问题。问题。相关术语相关术语第10页，本讲稿共55页 假假设设索索引引表表的的长长度度为为m m，主主表表中中每每个个子子表表的的长长度度为为s s，并并假假设设在在索索引引表表上上和和在在主主表表上上均均采采用用顺顺序序查查找找算算法法，则则索索引引顺顺序序表上查找算法的表上查找算法的平均查找长度平均查找长度为：为：算法分析算法分析第11页，本讲稿共55页10.3 10.3 动态查找表动态查找表 动态查找表主要有动态查找表主要有二叉树结构二叉树结构和和树结构树结构两种类型。二叉两种类型。二叉树结构有树结构有二叉排序树、平衡二叉树二叉排序树、平衡二叉树等。树结构有等。树结构有B-B-树、树、B B+树树等。等。1.1.1.1.二叉排序树二叉排序树二叉排序树二叉排序树一、基本概念一、基本概念一、基本概念一、基本概念-或是一棵空树；或者是具有如下性质的非空二叉树：或是一棵空树；或者是具有如下性质的非空二叉树：（1 1）左子树的所有结点均小于根的值；）左子树的所有结点均小于根的值；（2 2）右子树的所有结点均大于根的值；）右子树的所有结点均大于根的值；（3 3）它的左右子树也分别为二叉排序树。）它的左右子树也分别为二叉排序树。第12页，本讲稿共55页3811241094039454035190146476760445600800下图所示就是一棵二叉排序树下图所示就是一棵二叉排序树 第13页，本讲稿共55页二、二叉排序树类二、二叉排序树类二、二叉排序树类二、二叉排序树类定义如下：定义如下：templateclassBiSearchTree/输出流运算符重载输出流运算符重载friendistream&operator(istream&in,BiSearchTree*&tree);private:BiTreeNode*root;/根指针根指针voidInsert(BiTreeNode*&ptr,constT&item);/插入插入voidDelete(BiTreeNode*&ptr,constT&item);/删除删除/前序、中序和后序遍历，访问操作为前序、中序和后序遍历，访问操作为Visit()函数函数voidPreOrder(BiTreeNode*&t,void(*Visit)(Titem);voidInOrder(BiTreeNode*&t,void(*Visit)(Titem);voidPostOrder(BiTreeNode*&t,void(*Visit)(Titem);第14页，本讲稿共55页public:/构造函数和析构函数构造函数和析构函数BiSearchTree():root(NULL);/注意：生成的二叉排序树不带根结点注意：生成的二叉排序树不带根结点BiSearchTree();BiTreeNode*Find(constT&item);/查找查找voidInsert(constT&item)/插入插入Insert(GetRoot(),item);voidDelete(constT&item)/删除删除Delete(GetRoot(),item);BiTreeNode*&GetRoot()/取树根取树根returnroot;第15页，本讲稿共55页BiTreeNode*&LeftChild(BiTreeNode*&current)/取左孩子结点取左孩子结点returnroot!=NULL?current-Left():NULL;BiTreeNode*&RightChild(BiTreeNode*&current)/取右孩子结点取右孩子结点returnroot!=NULL?current-Right():NULL;voidPreOrder(void(*Visit)(Titem)/前序遍历前序遍历PreOrder(root,Visit);voidInOrder(void(*Visit)(Titem)/中序遍历中序遍历InOrder(root,Visit);voidPostOrder(void(*Visit)(Titem)/后序遍历后序遍历PostOrder(root,Visit);第16页，本讲稿共55页三、查找算法三、查找算法 二叉排序树上的查找过程，就是遍历二叉排序树并在遍历二叉排序树上的查找过程，就是遍历二叉排序树并在遍历过程中寻找要查找的数据元素是否存在。过程中寻找要查找的数据元素是否存在。循环结构的查找算法循环结构的查找算法设计如下：设计如下：templateBiTreeNode*BiSearchTree:Find(constT&item)if(root!=NULL)BiTreeNode*temp=root;while(temp!=NULL)if(temp-data=item)returntemp;/查找成功查找成功if(temp-dataRight();/在右子树继续在右子树继续elsetemp=temp-Left();/在左子树继续在左子树继续returnNULL;/查找失败查找失败第17页，本讲稿共55页四、插入算法四、插入算法 插入操作要求首先查找数据元素是否在二叉排序树中存插入操作要求首先查找数据元素是否在二叉排序树中存在，若在，若存在则返回存在则返回；若不存在，；若不存在，插入查找失败时结点的左指插入查找失败时结点的左指针或右指针上。针或右指针上。插入算法设计如下插入算法设计如下:templatevoidBiSearchTree:Insert(BiTreeNode*&ptr,constT&item)if(ptr=NULL)ptr=newBiTreeNode(item);/生成并插入结点生成并插入结点elseif(itemdata)Insert(ptr-Left(),item);/在左子树递归在左子树递归elseif(itemptr-data)Insert(ptr-Right(),item);/在右子树递归在右子树递归第18页，本讲稿共55页下图是调用上述插入函数依次插入数据元素下图是调用上述插入函数依次插入数据元素 4,5,7,2,1,9,8,11,34,5,7,2,1,9,8,11,3的过程。的过程。41152791384115279184527918452791452714527457454(d)(c)(b)(a)(g)(f)(e)(i)(h)第19页，本讲稿共55页五、删除算法五、删除算法 删删除除操操作作要要求求首首先先查查找找数数据据元元素素是是否否在在二二叉叉排排序序树树中中存存在在，若若不存在则结束；不存在则结束；存在的情况及相应的删除方法有如下四种：存在的情况及相应的删除方法有如下四种：(1)(1)要删除结点要删除结点无孩子结点无孩子结点，直接删除该结点。，直接删除该结点。(2)(2)要要删删除除结结点点只只有有左左孩孩子子结结点点，删删除除该该结结点点且且使使被被删删除除结结点点的双亲结点指向被删除结点的左孩子结点。的双亲结点指向被删除结点的左孩子结点。(3)(3)要要删删除除结结点点只只有有右右孩孩子子结结点点，删删除除该该结结点点且且使使被被删删除除结结点点的双亲结点指向被删除结点的右孩子结点。的双亲结点指向被删除结点的右孩子结点。(4)(4)要要删删除除结结点点有有左左右右孩孩子子结结点点，分分如如下下三三步步完完成成：首首先先寻寻找找数数据据元元素素的的关关键键字字值值大大于于要要删删除除结结点点数数据据元元素素关关键键字字的的最最小小值值，即即寻寻找找要要删删除除结结点点右右子子树树的的最最左左结结点点；然然后后把把右右子子树树的的最最左左结结点点的的数数据据元元素素值值拷拷贝贝到到要要删删除除的的结结点点上上；最最后后删删除除右右子子树树的的最最左结点。左结点。第20页，本讲稿共55页删除过程分别如图所示删除过程分别如图所示1814245162038710303518142451620387303518142451620387103035181424516203071035ptrptr(a)无孩子结点无孩子结点(b)有左孩子结点有左孩子结点第21页，本讲稿共55页18142451620387103035181424716203810303518142451620387103035181438516307102035ptrptr(c)有右孩子结点有右孩子结点(d)有左右孩子结点有左右孩子结点第22页，本讲稿共55页算法设计如下算法设计如下:templatevoidBiSearchTree:Delete(BiTreeNode*&ptr,constT&item)BiTreeNode*temp;if(ptr!=NULL)if(itemdata)Delete(ptr-Left(),item);elseif(itemptr-data)Delete(ptr-Right(),item);elseif(ptr-Left()!=NULL&ptr-Right()!=NULL)/要删除结点左右子树均存在的情况要删除结点左右子树均存在的情况 BiTreeNode*min;min=ptr-Right();/等于要删除结点的右子树等于要删除结点的右子树while(min-Left()!=NULL)min=min-Left();/寻找最左结点寻找最左结点ptr-data=min-data;/拷贝结点数值拷贝结点数值Delete(ptr-Right(),min-data);/删除结点删除结点 第23页，本讲稿共55页else/要删除结点的其他三种情况要删除结点的其他三种情况temp=ptr;if(ptr-Left()=NULL)ptr=ptr-Right();elseif(ptr-Right()=NULL)ptr=ptr-Left();deletetemp;/删除等于删除等于item的结点的结点第24页，本讲稿共55页测试程序测试程序例例10-2 设计一个测试二叉排序树类的主函数。设计一个测试二叉排序树类的主函数。第25页，本讲稿共55页六、二叉排序树的性能分析六、二叉排序树的性能分析 一棵二叉排序树的平均查找长度为：一棵二叉排序树的平均查找长度为：其中：其中：ni是每层结点个数；是每层结点个数；Ci是结点所在层次数；是结点所在层次数；m为树深。为树深。当当二二叉叉排排序序树树是是一一棵棵单单分分支支退退化化树树时时，查查找找成成功功的的平平均均查查找找长长度和有序顺序表的平均查找长度相同，即为：度和有序顺序表的平均查找长度相同，即为：若每个数据元素的查找概率相等，则二叉排序树查找成功的平若每个数据元素的查找概率相等，则二叉排序树查找成功的平均查找长度为：均查找长度为：第26页，本讲稿共55页3456781064835710(a)(b)（a）满二叉排序树时，）满二叉排序树时，k=log2(7+1)=3，所以，所以查找成功的平均查找长度为：查找成功的平均查找长度为：（b）左分支退化二叉排序树时，）左分支退化二叉排序树时，k=n=7，所以查找成功的平均查找长度为：，所以查找成功的平均查找长度为：在最坏情况下，二叉排序树的平均查找长度为在最坏情况下，二叉排序树的平均查找长度为O(n)。在一般情。在一般情况下，二叉排序树的平均查找长度为况下，二叉排序树的平均查找长度为O(log2n)。第27页，本讲稿共55页2.B_树树 B_B_树树是是一一种种平平衡衡多多叉叉排排序序树树。平平衡衡是是指指所所有有叶叶结结点点都都在在同同一一层层上上，从从而而可可避避免免出出现现像像二二叉叉排排序序树树那那样样的的分分支支退退化化现现象象。因因此此B_B_树的动态查找效率更高树的动态查找效率更高。B_B_树中所有结点的孩子结点的最大值称为树中所有结点的孩子结点的最大值称为B_B_树的阶树的阶，一棵一棵m阶阶的的B_树或者是一棵空树，或者是满足下列要求的树或者是一棵空树，或者是满足下列要求的m叉树：叉树：(1)树中每个结点至多有树中每个结点至多有m个孩子结点。个孩子结点。(2)除根结点外，其他结点至少有除根结点外，其他结点至少有 m/2 个孩子结点（符号个孩子结点（符号“”表示上取整）。表示上取整）。(3)若根结点不是叶结点，则根结点至少有两个孩子结点；若根结点不是叶结点，则根结点至少有两个孩子结点；(4)每个结点的结构为：每个结点的结构为：nP0K1P1K2P2KnPn(5)(5)所有叶结点都在同一层上。所有叶结点都在同一层上。第28页，本讲稿共55页1502041172214432330351151603778088 root一棵一棵4阶阶B_树树第29页，本讲稿共55页1.查找算法查找算法 在在B_树树上上查查找找数数据据元元素素x的的方方法法为为：将将 x.key与与根根结结点点的的Ki逐逐个个进进行比较：行比较：（1）若）若x.key=Ki则查找成功。则查找成功。（2）若）若keyK1则沿着指针则沿着指针P0所指的子树继续查找。所指的子树继续查找。（3）若）若KikeyKn则沿着指针则沿着指针Pn所指的子树继续查找。所指的子树继续查找。2.插入算法插入算法 插入过程分两步完成：插入过程分两步完成：（1 1）利利用用查查找找算算法法找找出出该该关关键键字字的的插插入入结结点点（B_B_树树的的插插入入结结点点一一定是叶结点定是叶结点）。）。（2 2）判判断断该该结结点点是是否否还还有有空空位位置置，即即判判断断该该结结点点是是否否满满足足nm-1nm-1，若若该该结结点点满满足足nm-1n=0?1:0;DataTypeGetValue(inti)const/取数据元素取数据元素returnhti.data;第50页，本讲稿共55页/哈希表类实现哈希表类实现HashTable:HashTable(intm)/构造函数构造函数TableSize=m;/置哈希表长度置哈希表长度ht=newHashItemTableSize;/申请动态数组空间申请动态数组空间currentSize=0;/置初始的当前表项个数置初始的当前表项个数为适应哈希表长度为适应哈希表长度m m的不同，存放哈希表的数组采用动态数组。的不同，存放哈希表的数组采用动态数组。构造函数的参数构造函数的参数m m即为哈希表的长度即为哈希表的长度。第51页，本讲稿共55页intHashTable:Find(constDataType&x)const/查找查找inti=x.key%TableSize;intj=i;while(htj.info=Active&htj.data!=x)/说明存在冲突说明存在冲突j=(j+1)%TableSize;/用哈希冲突方法继续查找用哈希冲突方法继续查找if(j=i)/说明已遍历整个哈希表未找到且表已满说明已遍历整个哈希表未找到且表已满return-TableSize;if(htj.info=Active)returnj;/找到，返回正值找到，返回正值elsereturn-j;/未找到，返回负值未找到，返回负值第52页，本讲稿共55页intHashTable:Insert(constDataType&x)/插入插入inti=Find(x);/调用调用Find(x)if(i0)return0;/数据元素数据元素x已经存在已经存在elseif(i!=-TableSize)/数据元素数据元素x不存在且哈希表未满不存在且哈希表未满ht-i.data=x;/数据元素赋值数据元素赋值ht-i.info=Active;/置活动标记置活动标记currentSize+;/当前表项个数加当前表项个数加1return1;/返回插入成功返回插入成功elsereturn0;/返回插入失败返回插入失败第53页，本讲稿共55页intHashTable:Delete(constDataType&x)/删除删除inti=Find(x);/调用调用Find(x)if(i=0)/查找到查找到hti.info=Deleted;/置删除标记置删除标记currentSize-;/当前表项个数减当前表项个数减1return1;/返回删除成功返回删除成功elsereturn0;/返回删除失败返回删除失败第54页，本讲稿共55页三、测试程序三、测试程序例例10-4 测试程序设计。建立数据元素集合测试程序设计。建立数据元素集合a=180,750,600,430,541,900,460的哈希表，并分别测试哈希表长度的哈希表，并分别测试哈希表长度m=13和和m=11两种情况得到的哈希表。两种情况得到的哈希表。第55页，本讲稿共55页