《《数据结构与算法》PPT课堂课件-第8章-集合》由会员分享，可在线阅读，更多相关《《数据结构与算法》PPT课堂课件-第8章-集合（105页珍藏版）》请在金锄头文库上搜索。
1、1 1第第第第9 9章章章章 集集集集合合合合学学学学习习习习要要要要点点点点: :9.19.1以以以以集集集集合合合合为为为为基基基基础础础础的的的的抽抽抽抽象象象象数数数数据据据据类类类类型型型型 理理理理解解解解集集集集合合合合的的的的概概概概念念念念。 理理理理解解解解以以以以集集集集合合合合为为为为基基基基础础础础的的的的抽抽抽抽象象象象数数数数据据据据类类类类型型型型。 掌掌掌掌握握握握用用用用位位位位向向向向量量量量实实实实现现现现集集集集合合合合的的的的方方方方法法法法。 掌掌掌掌握握握握用用用用链链链链表表表表实实实实现现现现集集集集合合合合的的的的方方方方法法法法。2 29
2、.29.2符符符符号号号号表表表表 理理理理解解解解抽抽抽抽象象象象数数数数据据据据类类类类型型型型符符符符号号号号表表表表的的的的概概概概念念念念。 掌掌掌掌握握握握数数数数组组组组实实实实现现现现符符符符号号号号表表表表的的的的方方方方法法法法。 理理理理解解解解开开开开散散散散列列列列和和和和闭闭闭闭散散散散列列列列的的的的概概概概念念念念。 掌掌掌掌握握握握用用用用开开开开散散散散列列列列表表表表实实实实现现现现符符符符号号号号表表表表的的的的方方方方法法法法。 掌掌掌掌握握握握除除除除余余余余法法法法、数数数数乘乘乘乘法法法法、平平平平方方方方取取取取中中中中法法法法、基基基基数数数
3、数转转转转换换换换法法法法和和和和随随随随机机机机数数数数法法法法等等等等散散散散列列列列函函函函数数数数构构构构造造造造方方方方法法法法。 掌掌掌掌握握握握采采采采用用用用线线线线性性性性重重重重新新新新散散散散列列列列技技技技术术术术的的的的闭闭闭闭散散散散列列列列表表表表实实实实现现现现符符符符号号号号表表表表的的的的方方方方法法法法。3 39.39.3字字字字典典典典 理理理理解解解解以以以以有有有有序序序序集集集集为为为为基基基基础础础础的的的的抽抽抽抽象象象象数数数数据据据据类类类类型型型型字字字字典典典典。 理理理理解解解解用用用用数数数数组组组组实实实实现现现现字字字字典典典典
4、的的的的方方方方法法法法。 理理理理解解解解二二二二叉叉叉叉搜搜搜搜索索索索树树树树的的的的概概概概念念念念和和和和实实实实现现现现方方方方法法法法。 掌掌掌掌握握握握用用用用二二二二叉叉叉叉搜搜搜搜索索索索树树树树实实实实现现现现字字字字典典典典的的的的方方方方法法法法。 理理理理解解解解AVLAVL树树树树的的的的定定定定义义义义和和和和性性性性质质质质。 掌掌掌掌握握握握二二二二叉叉叉叉搜搜搜搜索索索索树树树树的的的的结结结结点点点点旋旋旋旋转转转转变变变变换换换换及及及及实实实实现现现现方方方方法法法法。 掌掌掌掌握握握握AVLAVL树树树树的的的的插插插插入入入入重重重重新新新新平平
5、平平衡衡衡衡运运运运算算算算及及及及实实实实现现现现方方方方法法法法。 掌掌掌掌握握握握AVLAVL树树树树的的的的删删删删除除除除重重重重新新新新平平平平衡衡衡衡运运运运算算算算及及及及实实实实现现现现方方方方法法法法。4 49.49.4优优优优先先先先队队队队列列列列 理理理理解解解解以以以以集集集集合合合合为为为为基基基基础础础础的的的的抽抽抽抽象象象象数数数数据据据据类类类类型型型型优优优优先先先先队队队队列列列列。 理理理理解解解解用用用用有有有有序序序序字字字字典典典典实实实实现现现现优优优优先先先先队队队队列列列列的的的的方方方方法法法法。 理理理理解解解解优优优优先先先先级级级
6、级树树树树和和和和堆堆堆堆的的的的概概概概念念念念。 掌掌掌掌握握握握用用用用数数数数组组组组实实实实现现现现堆堆堆堆的的的的方方方方法法法法。 理理理理解解解解以以以以集集集集合合合合为为为为基基基基础础础础的的的的抽抽抽抽象象象象数数数数据据据据类类类类型型型型可可可可并并并并优优优优先先先先队队队队列列列列。 理理理理解解解解左左左左偏偏偏偏树树树树的的的的定定定定义义义义和和和和概概概概念念念念。 掌掌掌掌握握握握用用用用左左左左偏偏偏偏树树树树实实实实现现现现可可可可并并并并优优优优先先先先队队队队列列列列的的的的方方方方法法法法。 掌掌掌掌握握握握堆堆堆堆排排排排序序序序算算算算法
7、法法法。5 59.59.5并并并并查查查查集集集集 理理理理解解解解以以以以不不不不相相相相交交交交的的的的集集集集合合合合为为为为基基基基础础础础的的的的抽抽抽抽象象象象数数数数据据据据类类类类型型型型并并并并查查查查集集集集。 掌掌掌掌握握握握用用用用数数数数组组组组实实实实现现现现并并并并查查查查集集集集的的的的方方方方法法法法。 掌掌掌掌握握握握用用用用树树树树结结结结构构构构实实实实现现现现并并并并查查查查集集集集的的的的方方方方法法法法。 理理理理解解解解将将将将小小小小树树树树合合合合并并并并到到到到大大大大树树树树的的的的合合合合并并并并策策策策略略略略及及及及其其其其实实实实
8、现现现现。 掌掌掌掌握握握握路路路路径径径径压压压压缩缩缩缩技技技技术术术术及及及及其其其其实实实实现现现现方方方方法法法法。6 69 9. .0 0 引引引引言言言言9 9. .0 0. .1 1 集集集集合合合合的的的的概概概概念念念念的的的的原原原原形形形形 银银银银行行行行中中中中所所所所有有有有储储储储户户户户帐帐帐帐号号号号的的的的集集集集合合合合；图图图图书书书书馆馆馆馆中中中中 所所所所有有有有藏藏藏藏书书书书的的的的集集集集合合合合；一一一一个个个个程程程程序序序序中中中中所所所所有有有有标标标标识识识识 符符符符的的的的集集集集合合合合；2 2 2 20 0 0 00 0
9、0 03 3 3 3级级级级3 3 3 34 4 4 4班班班班全全全全体体体体同同同同学学学学的的的的集集集集合合合合等等等等 7 79.09.0引引引引言言言言9.0.29.0.2集集集集合合合合的的的的概概概概念念念念与与与与术术术术语语语语 集集集集合合合合：集集集集合合合合是是是是由由由由元元元元素素素素( (成成成成员员员员) )组组组组成成成成的的的的一一一一个个个个类类类类。 原原原原子子子子：不不不不可可可可再再再再分分分分的的的的元元元元素素素素。 多多多多重重重重集集集集合合合合：允允允允许许许许同同同同一一一一元元元元素素素素在在在在集集集集合合合合中中中中多多多多次次
10、次次出出出出现现现现的的的的集集集集合合合合称称称称为为为为多多多多重重重重集集集集合合合合。 有有有有序序序序集集集集：当当当当由由由由原原原原子子子子组组组组成成成成的的的的集集集集合合合合具具具具有有有有线线线线性性性性序序序序关关关关系系系系“ “ ” ”时时时时，称称称称该该该该集集集集合合合合为为为为有有有有序序序序集集集集。“ “ ” ”是是是是集集集集合合合合的的的的一一一一个个个个线线线线性性性性序序序序，它它它它满满满满足足足足：(1)(1)若若若若a a、b b是是是是集集集集合合合合中中中中任任任任意意意意2 2个个个个原原原原子子子子, ,则则则则abab, ,a=b
11、a=b和和和和baba三三三三者者者者必必必必居居居居其其其其一一一一；(2)a(2)a，b b和和和和c c是是是是集集集集合合合合中中中中的的的的原原原原 子子子子，且且且且abab，bcbc则则则则ac(a s se et ts si iz ze e= =s si iz ze e; ; S S- - a ar rr ra ay ys si iz ze e= =( (s si iz ze e+ +1 15 5) ) 4 4; ; S S- - v v= =mma al ll lo oc c( (s si iz ze e* *s si iz ze eo of f( (u un ns si i
12、g gn ne ed d s sh ho or rt t) ) ); ; f fo or r ( (i i= =0 0; ; i i v v i i = =0 0; ; r re et tu ur rn n S S; ; 1515v vo oi id d S Se et tA As ss si ig gn n( (S Se et t A A, , S Se et t B B) ) i in nt t i i; ; i if f ( (A A- - s se et ts si iz ze e ! != =B B- - s se et ts si iz ze e) ) E Er rr ro or
13、r( (“ “S Se et ts s a ar re e n no ot t t th he e s sa amme e s si iz ze e” ”) ); ; f fo or r( (i i= =0 0; ; i i a ar rr ra ay ys si iz ze e; ; i i+ + +) ) A A- - v v i i = =B B- - v v i i ; ; 1616i in nt t S Se et tMMe emme eb be er r( (i in nt t x x, , S Se et t S S) ) i if f ( (x x = =S S- - s se
14、 et ts si iz ze e) ) E Er rr ro or r( (“ “I In nv va al li id d mme emmb be er r r re ef fe er re en nc ce e” ”) ); ; r re et tu ur rn n S S- - v v A Ar rr ra ay yI In nd de ex x( () ) & & B Bi it tMMa as sk k( (x x) ); ; 1717i in nt t A Ar rr ra ay yI In nd de ex x( (i in nt t x x) ) r re et tu ur
15、rn n x x 4 4; ; u un ns si ig gn ne ed d s sh ho or rt t B Bi it tMMa as sk k( (i in nt t x x) ) r re et tu ur rn n 1 1 s se et ts si iz ze e ! != =B B- - s se et ts si iz ze e) ) E Er rr ro or r( (“ “. . .” ”) ); ; f fo or r( (i i= =0 0; ; i i a ar rr ra ay ys si iz ze e; ; i i+ + +) ) i if f( (A A
16、- - v v i i ! != =B B- - v v i i ) ) r re et tv va al l= =0 0; ; b br re ea ak k; ; r re et tu ur rn n r re et tv va al l; ; 1919S Se et t S Se et tU Un ni io on n( (S Se et t A A, , S Se et t B B) ) i in nt t i i; ; S Se et t t tmmp p= =S Se et tI In ni it t( (A A- - s se et ts si iz ze e) ); ; f f
17、o or r( (i i= =0 0; ; i i a ar rr ra ay ys si iz ze e; ; i i+ + +) ) t tmmp p- - v v i i = =A A- - v v i i | | B B- - v v i i ; ; r re et tu ur rn n t tmmp p; ; 2020S Se et t S Se et tI In nt te er rs se ec ct ti io on n( (S Se et t A A, , S Se et t B B) ) i in nt t i i; ; S Se et t t tmmp p= =S Se
18、et tI In ni it t( (A A- - s se et ts si iz ze e) ); ; f fo or r( (i i= =0 0; ; i i a ar rr ra ay ys si iz ze e; ; i i+ + +) ) t tmmp p- - v v i i = =A A- - v v i i & & B B- - v v i i ; ; r re et tu ur rn n t tmmp p; ; 2121S Se et t S Se et tD Di if ff fe er re en nc ce e( (S Se et t A A, , S Se et t
19、 B B) ) i in nt t i i; ; S Se et t t tmmp p= =S Se et tI In ni it t( (A A- - s se et ts si iz ze e) ); ; f fo or r( (i i= =0 0; ; i i a ar rr ra ay ys si iz ze e; ; i i+ + +) ) t tmmp p- - v v i i = =A A- - v v i i ( (B B- - v v i i & & A A- - v v i i ) ); ; r re et tu ur rn n t tmmp p; ; 2222v vo o
20、i id d S Se et tI In ns se er rt t( (i in nt t x x, , S Se et t S S) ) i if f ( (x x = =S S- - s se et ts si iz ze e) ) E Er rr ro or r( (“ “. . .” ”) ); ; S S- - v v A Ar rr ra ay yI In nd de ex x( (x x) ) | |= =B Bi it tMMa as sk k( (x x) ); ; 2323v vo oi id d S Se et tD De el le et te e( (i in nt
21、 t x x, , S Se et t S S) ) i if f ( (x x = =S S- - s se et ts si iz ze e) ) E Er rr ro or r( (“ “. . .” ”) ); ; S S- - v v A Ar rr ra ay yI In nd de ex x( (x x) ) & &= = B Bi it tMMa as sk k( (x x) ); ; 24249.19.1以以以以集集集集合合合合为为为为基基基基础础础础的的的的抽抽抽抽象象象象数数数数据据据据类类类类型型型型9.1.39.1.3ADTADTADTADT集集集集合合合合的的的的简
22、简简简单单单单实实实实现现现现用用用用有有有有序序序序链链链链表表表表实实实实现现现现9.1.3.09.1.3.0LinkedSetLinkedSet的的的的有有有有序序序序链链链链表表表表结结结结点点点点类类类类型型型型NodeNode的的的的定定定定义义义义TypedefTypedef structstructnode*linknode*linkstructstructnodenodeListItemListItemelement;element;linknext;linknext;Node;Node;25259.19.1以以以以集集集集合合合合为为为为基基基基础础础础的的的的抽抽抽抽象象
23、象象数数数数据据据据类类类类型型型型9.1.39.1.3ADTADTADTADT集集集集合合合合的的的的简简简简单单单单实实实实现现现现用用用用有有有有序序序序链链链链表表表表实实实实现现现现 9.1.3.19.1.3.1有有有有序序序序链链链链表表表表实实实实现现现现的的的的集集集集合合合合SetSet的的的的定定定定义义义义TypedefTypedef structstructlist*Setlist*SetTypedefTypedef structstructlistlistlinkfirst;linkfirst; 2626S Se et t S Se et tI In ni it t(
24、 ( ) ) S Se et t S S= =mma al ll lo oc c( (s si iz ze eo of f * *S S) ); ; S S- - f fi ir rs st t= =0 0; ; r re et tu ur rn n S S; ; 2727i in nt t S Se et tE Emmp pt ty y( (S Se et t S S) ) r re et tu ur rn n S S- - f fi ir rs st t= = =0 0; ; 2828intint SetSize(SetSetSize(SetS)S) intint lenlen; ;lin
25、kcurrent;linkcurrent;current=S-first;current=S-first;lenlen=0;=0;while(current)while(current)lenlen+;+;current=current=currentcurrent-next;-next;returnreturnlenlen; ; 2929voidvoidSetAssign(SetSetAssign(SetA,SetB)A,SetB) linklinka,b,ca,b,c; ;b=B-first;b=B-first;A-first=0;A-first=0;if(b)if(b)A-first=A
26、-first=NewNodeNewNode();();a=A-first;a=A-first;a-element=b-element;a-element=b-element;a-next=0;a-next=0;b=b-next;b=b-next;while(bwhile(b) )c=c=NewNodeNewNode();();c-element=b-element;c-element=b-element;c-next=0;c-next=0;b=b-next;b=b-next;a-next=c;a-next=c;a=c;a=c; 3030SetSetSetIntersection(SetSetI
27、ntersection(SetA,SetB)A,SetB) linklinka,b,p,q,ra,b,p,q,r; ;SetSettmptmp= =SetInitSetInit();();a=A-first;a=A-first;b=B-first;b=B-first;p=p=NewNodeNewNode();();q=p;q=p;while(awhile(a&b)&b)if(aif(a-element=b-element)-element=b-element)r=r=NewNodeNewNode();();r-element=a-element;r-element=a-element;r-ne
28、xt=0;r-next=0;p-next=r;p-next=r;p=r;p=r;a=a-next;a=a-next;b=b-next;b=b-next;elseelseif(aif(a-elementelement)a=a-next;-elementelement)a=a-next;elseb=b-next;elseb=b-next; if(pif(p!=q)!=q)tmptmp-first=q-next;-first=q-next; free(qfree(q); );returnreturntmptmp; ; 3131voidvoidSetIntsert(ListItemSetIntsert
29、(ListItemx,SetS)x,SetS) linklinkp,q,rp,q,r; ;p=S-first;p=S-first;q=p;q=p;while(p&p-elementelementnext;p=p-next;if(p&p-element=x)return;if(p&p-element=x)return;r=r=NewNodeNewNode();();r-element=x;r-element=x;r-next=p;r-next=p;if(p=q)S-first=r;if(p=q)S-first=r;elseq-next=r;elseq-next=r; 32329.29.2符符符符
30、号号号号表表表表9.2.09.2.0引引引引言言言言 ADTADT符符符符号号号号表表表表的的的的概概概概念念念念 以以以以集集集集合合合合为为为为基基基基础础础础，并并并并支支支支持持持持MemberMember、InsertInsert和和和和DeleteDelete三三三三种种种种运运运运算算算算的的的的抽抽抽抽象象象象数数数数据据据据类类类类型型型型叫叫叫叫做做做做符符符符号号号号表表表表。 ADTADT符符符符号号号号表表表表的的的的应应应应用用用用公公公公司司司司的的的的客客客客户户户户字字字字典典典典一一一一个个个个地地地地区区区区的的的的固固固固定定定定/ /移移移移动动动动电
31、电电电话话话话号号号号码码码码字字字字典典典典软软软软件件件件开开开开发发发发中中中中的的的的数数数数据据据据字字字字典典典典网网网网上上上上的的的的在在在在线线线线字字字字典典典典互互互互联联联联网网网网/ /企企企企业业业业网网网网/ /局局局局域域域域网网网网网网网网管管管管中中中中的的的的IPIP地地地地址址址址字字字字典典典典等等等等等等等等33339.29.2符符符符号号号号表表表表9.2.19.2.1实实实实现现现现符符符符号号号号表表表表的的的的简简简简单单单单方方方方法法法法用用用用固固固固定定定定数数数数组组组组typedeftypedeftypedeftypedef st
32、ructstructstructstruct atabatabatabatab *Table; *Table; *Table; *Table;typedeftypedeftypedeftypedef structstructstructstruct atabatabatabatab intintintint arraysizearraysizearraysizearraysize; ; ; ; intintintint last; last; last; last; SetItemSetItemSetItemSetItem*data;*data;*data;*data; AtabAtabAta
33、bAtab; ; ; ;3434T Ta ab bl le e T Ta ab bl le eI In ni it t( (i in nt t s si iz ze e) ) T Ta ab bl le e T T= =mma al ll lo oc c( (s si iz ze eo of f * *T T) ); ; T T- - a ar rr ra ay ys si iz ze e= =s si iz ze e; ; T T- - l la as st t= =0 0; ; T T- - d da at ta a= =mma al ll lo oc c( (s si iz ze e*
34、*s si iz ze eo of f( (S Se et tI It te emm) ) ); ; r re et tu ur rn n T T; ; 3535i in nt t T Ta ab bl le eMMe emmb be er r( (S Se et tI It te emm x x, ,T Ta ab bl le e T T) ) i in nt t I I; ; f fo or r( (i i= =0 0; ;i i l la as st t; ;i i+ + +) ) i if f( (T T- - d da at ta a i i = = =x x) ) r re et
35、tu ur rn n 1 1; ;r re et tu ur rn n 0 0; ; 3636voidvoidTableInsert(SetItemTableInsert(SetItem x,Tablex,TableT)T) if(!if(!TableMember(x,TTableMember(x,T)&T-lastlast arraysizearraysize) )T-T-dataTdataT-last+=x;-last+=x; 3737voidvoidTableDelete(SetItemTableDelete(SetItem x,Tablex,TableT)T) intinti=0;i=
36、0;if(T-last0)if(T-last0)while(Ywhile(Y-dataidatai!=x&ilast)i+;!=x&ilast)i+;if(iif(ilast&T-last&T-dataidatai=x)=x)T-T-dataidatai=T-data-T-last;=T-data-T-last; ; 38389.29.2符符符符号号号号表表表表9.2.19.2.1实实实实现现现现符符符符号号号号表表表表的的的的简简简简单单单单方方方方法法法法用用用用固固固固定定定定数数数数组组组组9.2.1.39.2.1.3优优优优缺缺缺缺点点点点 优优优优点点点点：结结结结构构构构简简简简
37、单单单单，实实实实现现现现操操操操作作作作的的的的逻逻逻逻辑辑辑辑简简简简单单单单。 缺缺缺缺点点点点： 所所所所表表表表示示示示的的的的集集集集合合合合的的的的大大大大小小小小受受受受到到到到数数数数组组组组大大大大小小小小的的的的限限限限制制制制。三三三三个个个个基基基基本本本本操操操操作作作作在在在在最最最最坏坏坏坏情情情情况况况况下下下下都都都都需需需需要要要要O(n)O(n)。通通通通常常常常集集集集合合合合元元元元素素素素并并并并不不不不占占占占满满满满整整整整个个个个数数数数组组组组，因因因因此此此此，空空空空间间间间没没没没有有有有得得得得到到到到充充充充分分分分利利利利用用用
38、用。39399.29.2符符符符号号号号表表表表9.2.29.2.2实实实实现现现现符符符符号号号号表表表表的的的的简简简简单单单单方方方方法法法法开开开开散散散散列列列列9.2.2.19.2.2.1基基基基本本本本设设设设想想想想把把把把符符符符号号号号表表表表中中中中的的的的所所所所有有有有元元元元素素素素散散散散列列列列(hashing)(hashing)即即即即映映映映射射射射到到到到一一一一个个个个桶桶桶桶数数数数组组组组( (散散散散列列列列表表表表) )的的的的桶桶桶桶中中中中。当当当当有有有有多多多多个个个个不不不不同同同同元元元元素素素素被被被被散散散散列列列列到到到到同同同
39、同一一一一个个个个桶桶桶桶时时时时，这这这这些些些些元元元元素素素素用用用用链链链链在在在在一一一一个个个个表表表表里里里里。期期期期望望望望散散散散列列列列能能能能均均均均匀匀匀匀，使使使使得得得得当当当当桶桶桶桶数数数数组组组组的的的的规规规规模模模模与与与与字字字字典典典典的的的的规规规规模模模模同同同同阶阶阶阶时时时时，桶桶桶桶数数数数组组组组的的的的每每每每一一一一个个个个桶桶桶桶中中中中大大大大致致致致有有有有常常常常数数数数个个个个元元元元素素素素，从从从从而而而而对对对对字字字字典典典典的的的的三三三三个个个个基基基基本本本本操操操操作作作作都都都都只只只只需需需需要要要要常常
40、常常数数数数时时时时间间间间。这这这这里里里里的的的的问问问问题题题题是是是是如如如如何何何何散散散散列列列列即即即即如如如如何何何何构构构构造造造造散散散散列列列列( (映映映映射射射射) )函函函函数数数数去去去去达达达达到到到到设设设设想想想想的的的的期期期期望望望望？40409 9. .2 2符符符符号号号号表表表表9.2.29.2.2实实实实现现现现符符符符号号号号表表表表的的的的简简简简单单单单方方方方法法法法开开开开散散散散列列列列9.2.2.29.2.2.2开开开开散散散散列列列列的的的的数数数数据据据据要要要要素素素素按按按按照照照照设设设设想想想想，开开开开散散散散列列列列
41、首首首首先先先先需需需需要要要要拥拥拥拥有有有有一一一一个个个个桶桶桶桶数数数数组组组组，桶桶桶桶数数数数组组组组的的的的规规规规模模模模与与与与符符符符号号号号表表表表的的的的规规规规模模模模同同同同阶阶阶阶，桶桶桶桶数数数数组组组组中中中中的的的的每每每每一一一一个个个个桶桶桶桶有有有有一一一一个个个个指指指指针针针针各各各各指指指指向向向向一一一一个个个个链链链链表表表表。其其其其次次次次需需需需要要要要拥拥拥拥有有有有一一一一个个个个散散散散列列列列( (映映映映射射射射) )函函函函数数数数，它它它它把把把把字字字字典典典典中中中中的的的的元元元元素素素素分分分分别别别别散散散散列列
42、列列( (映映映映射射射射，分分分分散散散散) )到到到到各各各各桶桶桶桶所所所所对对对对应应应应的的的的链链链链表表表表中中中中。41419.29.2符符符符号号号号表表表表9.2.29.2.2实实实实现现现现符符符符号号号号表表表表的的的的简简简简单单单单方方方方法法法法开开开开散散散散列列列列9.2.2.39.2.2.3散散散散列列列列函函函函数数数数的的的的例例例例子子子子假假假假设设设设符符符符号号号号表表表表的的的的元元元元素素素素是是是是字字字字符符符符串串串串x x，桶桶桶桶数数数数组组组组的的的的规规规规模模模模为为为为101101，那那那那么么么么，下下下下面面面面是是是是
43、散散散散列列列列函函函函数数数数的的的的一一一一个个个个具具具具体体体体例例例例子子子子inthash1(char*x)inthash1(char*x) intint lenlen= =strlen(xstrlen(x),),hashvalhashval=0;=0;for(intfor(inti=0;ii=0;isize=H-size=nbucketsnbuckets; ;H-H-hfhf= =hashfhashf; ;H-ht=H-ht=malloc(Hmalloc(H-size*-size*sizeof(Listsizeof(List););for(ifor(i=0;i=0;isize;i
44、size;i+)+)H-H-htihti=ListInitListInit() ()returnH;returnH; 4545intint HTMember(SetItemHTMember(SetItem x,OpenHashTablex,OpenHashTable H)H) intinti=(*h-i=(*h-HF)(xHF)(x)%H-size;)%H-size;return(return(ListLocate(x,HListLocate(x,H-htihti)0);)0); 4646voidvoidHTInsert(SetItemHTInsert(SetItem x,OpenHashTa
45、blex,OpenHashTable H)H) intinti;i;if(if(HTMember(x,HHTMember(x,H)Error(“BadError(“BadInput”);Input”);i=(*h-i=(*h-hf)(xhf)(x)%H-size;)%H-size;ListInsert(0,x,H-ListInsert(0,x,H-htihti);); 4747voidvoidHTDelete(SetItemHTDelete(SetItem x,OpenHashTablex,OpenHashTableH)H) intinti;i;i=(*h-i=(*h-hf)(xhf)(x)%
46、H-size;)%H-size;if(k=if(k=ListLocate(x,HListLocate(x,H-htihti)ListDelete(k,HListDelete(k,H-htihti);); 48489.29.2符符符符号号号号表表表表9.2.39.2.3实实实实现现现现符符符符号号号号表表表表的的的的简简简简单单单单方方方方法法法法闭闭闭闭散散散散列列列列9.2.3.19.2.3.1与与与与开开开开散散散散列列列列的的的的相相相相同同同同点点点点和和和和区区区区别别别别 相相相相同同同同点点点点：把把把把字字字字典典典典中中中中的的的的所所所所有有有有元元元元素素素素散散散散列列
47、列列(hashing)(hashing)即即即即映映映映射射射射到到到到一一一一个个个个桶桶桶桶数数数数组组组组( (散散散散列列列列表表表表) )的的的的桶桶桶桶中中中中。 区区区区别别别别：桶桶桶桶数数数数组组组组( (散散散散列列列列表表表表) )的的的的桶桶桶桶直直直直接接接接用用用用来来来来存存存存放放放放字字字字典典典典元元元元素素素素，而而而而且且且且一一一一个个个个桶桶桶桶只只只只存存存存放放放放一一一一个个个个元元元元素素素素。出出出出现现现现多多多多个个个个元元元元素素素素散散散散列列列列到到到到同同同同一一一一个个个个桶桶桶桶时时时时( (这这这这叫叫叫叫冲冲冲冲突突突突
48、) )，需需需需要要要要按按按按照照照照确确确确定定定定的的的的规规规规则则则则在在在在桶桶桶桶数数数数组组组组中中中中进进进进行行行行探探探探测测测测，找找找找还还还还没没没没有有有有存存存存放放放放元元元元素素素素的的的的桶桶桶桶( (这这这这叫叫叫叫空空空空桶桶桶桶) )，然然然然后后后后将将将将发发发发生生生生冲冲冲冲突突突突的的的的后后后后到到到到元元元元素素素素放放放放入入入入空空空空桶桶桶桶，解解解解决决决决冲冲冲冲突突突突，实实实实现现现现散散散散列列列列。 49499.29.2符符符符号号号号表表表表9.2.39.2.3实实实实现现现现符符符符号号号号表表表表的的的的简简简简
49、单单单单方方方方法法法法闭闭闭闭散散散散列列列列9.2.3.29.2.3.2闭闭闭闭散散散散列列列列引引引引发发发发的的的的问问问问题题题题(1)(1)需需需需要要要要一一一一个个个个探探探探测测测测函函函函数数数数c(i),i=0,1,2,c(i),i=0,1,2,size-1,size-1：c(0)=0,c(0)=0,而而而而且且且且对对对对于于于于任任任任意意意意的的的的0jsize-1(j+c(0)mod0jsize-1(j+c(0)modsize,(j+c(1)modsize,size,(j+c(1)modsize,(j+c(size-1)modsize,(j+c(size-1)mo
50、dsize是是是是 0,1,2,0,1,2,size-1,size-1的的的的重重重重排排排排, ,保保保保证证证证不不不不会会会会漏漏漏漏测测测测。(2)(2)需需需需要要要要对对对对htht的的的的每每每每一一一一个个个个桶桶桶桶的的的的状状状状态态态态加加加加以以以以标标标标记记记记：statek=0statek=0表表表表示示示示htkhtk桶桶桶桶存存存存放放放放着着着着元元元元素素素素。statek=1statek=1表表表表示示示示htkhtk桶桶桶桶一一一一直直直直是是是是空空空空桶桶桶桶。statek=2statek=2表表表表示示示示htkhtk桶桶桶桶现现现现在在在在是是
51、是是空空空空桶桶桶桶但但但但曾曾曾曾经经经经存存存存放放放放过过过过元元元元素素素素50509 9. .2 2符符符符号号号号表表表表9 9. .2 2. .3 3 实实实实现现现现符符符符号号号号表表表表的的的的简简简简单单单单方方方方法法法法闭闭闭闭散散散散列列列列9 9. .2 2. .3 3. .3 3 闭闭闭闭散散散散列列列列的的的的数数数数据据据据要要要要素素素素( (1 1) )桶桶桶桶数数数数组组组组的的的的规规规规模模模模s si iz ze e；( (2 2) )桶桶桶桶数数数数组组组组h ht t ；( (3 3) )散散散散列列列列函函函函数数数数指指指指针针针针 i
52、in nt t ( (* *h hf f) ) ( (T T x x) )；( (4 4) )探探探探测测测测函函函函数数数数c c( (i i) ), ,i i= =0 0, ,1 1, ,2 2, , ,s si iz ze e- -1 1；( (5 5) )桶桶桶桶状状状状态态态态标标标标记记记记数数数数组组组组s st ta at te e ；51519.29.2符符符符号号号号表表表表9.2.39.2.3实实实实现现现现符符符符号号号号表表表表的的的的简简简简单单单单方方方方法法法法闭闭闭闭散散散散列列列列9.2.3.49.2.3.4闭闭闭闭散散散散列列列列表表表表实实实实现现现现的
53、的的的的的的的定定定定义义义义 typedeftypedef structstruct hashtablehashtable* *HashTableHashTable; ;typedeftypedef structstruct hashtablehashtable intintsize;size;intint(*(*hf)(SetItemhf)(SetItemx);x);SetItemSetItem*ht;*ht;intint*state;*state; HashtableHashtable; ;5252HashTableHashTable HTInit(intHTInit(intdiviso
54、r,divisor,intint (* (*hashf)(SetItemhashf)(SetItemx)x)intinti;i;HashTableHashTableH=H=malloc(sizeofmalloc(sizeof*H);*H);H-size=divisor;H-size=divisor;H-H-hfhf=hashfhashf; ;H-ht=H-ht=malloc(Hmalloc(H-size*-size*sizeof(intsizeof(int););for(i=0;ifor(i=0;isize;isize;i+)+)H-H-stateistatei=1;=1;returnH;re
55、turnH; 5353intint FindMatch(SetItemFindMatch(SetItem x,HashTablex,HashTableH)H)intint I,j,kI,j,k; ;j=(*H-j=(*H-hf)(xhf)(x); );for(i=0;ifor(i=0;isize;isize;i+)+)k=(k=(j+HashProb(i)%Hj+HashProb(i)%H-size;-size;if(H-if(H-statekstatek=1)break;=1)break;if(!Hif(!H-statekstatek&H-&H-htkhtk=x)returnk;=x)ret
56、urnk; returnH-size;returnH-size; intint HashProb(intHashProb(inti)i) returni;returni; 5454intint Unoccupied(SetItemUnoccupied(SetItem x,HashTablex,HashTableH)H)intint I,j,kI,j,k; ;j=(*H-j=(*H-hf)(xhf)(x); );for(i=0;ifor(i=0;isize;isize;i+)+)k=(k=(j+HashProb(i)%Hj+HashProb(i)%H-size;-size;if(H-if(H-s
57、tatekstatek)returnk;)returnk; returnH-size;returnH-size; 5555intint HTMember(SetItemHTMember(SetItem x,HashTablex,HashTableH)H)intinti=i=FindMatch(x,HFindMatch(x,H); );if(isize&H-if(isize&H-htihti=x)return1;=x)return1;return0;return0; 5656intint HTInsert(SetItemHTInsert(SetItem x,HashTablex,HashTabl
58、eH)H)intintI;I;if(HTMember(x,Hif(HTMember(x,H)Error(“BadError(“BadInput”);Input”);i=i=Unoccupied(x,HUnoccupied(x,H); );if(iif(isize)size)H-H-stateistatei=0;=0;H-H-htihti=x;=x;elseelseError(“tableError(“tablefull”);full”); 5757intint HTDelete(SetItemHTDelete(SetItem x,HashTablex,HashTableH)H)intinti=
59、i=FindMatch(x,HFindMatch(x,H); );if(isize&H-if(isize&H-htihti=x)H-=x)H-stateistatei=2;=2; 58589.29.2符符符符号号号号表表表表9.2.39.2.3实实实实现现现现符符符符号号号号表表表表的的的的简简简简单单单单方方方方法法法法闭闭闭闭散散散散列列列列9.2.3.59.2.3.5 HashTableHashTable的的的的定定定定义义义义中中中中未未未未实实实实现现现现的的的的函函函函数数数数( (续续续续) )函函函函数数数数HTDeleteHTDelete的的的的缺缺缺缺点点点点：在在在在执执
60、执执行行行行了了了了大大大大量量量量元元元元素素素素删删删删除除除除运运运运算算算算后后后后，大大大大量量量量的的的的桶桶桶桶的的的的状状状状态态态态标标标标记记记记为为为为 22即即即即大大大大量量量量的的的的桶桶桶桶的的的的状状状状态态态态标标标标记记记记既既既既非非非非 11也也也也非非非非 00使使使使得得得得运运运运算算算算FindMatchFindMatch 中中中中的的的的循循循循环环环环次次次次数数数数大大大大大大大大增增增增加加加加，从从从从而而而而使使使使得得得得运运运运算算算算FindMatchFindMatch的的的的速速速速度度度度大大大大大大大大减减减减慢慢慢慢。因
61、因因因此此此此人人人人们们们们提提提提出出出出HTDeleteHTDelete的的的的一一一一种种种种改改改改进进进进版版版版本本本本HTDelete1HTDelete159599.29.2符符符符号号号号表表表表9.2.39.2.3实实实实现现现现符符符符号号号号表表表表的的的的简简简简单单单单方方方方法法法法闭闭闭闭散散散散列列列列9.2.3.59.2.3.5 HashTableHashTable的的的的定定定定义义义义中中中中未未未未实实实实现现现现的的的的函函函函数数数数( (续续续续) )改改改改进进进进HTDeleteHTDelete的的的的基基基基本本本本思思思思想想想想：动动动
62、动机机机机是是是是希希希希望望望望腾腾腾腾出出出出的的的的空空空空桶桶桶桶( (记记记记为为为为hti)hti)不不不不仅仅仅仅仅仅仅仅可可可可供供供供新新新新元元元元素素素素插插插插入入入入，而而而而且且且且能能能能为为为为提提提提高高高高还还还还在在在在桶桶桶桶数数数数组组组组中中中中的的的的元元元元素素素素( (比比比比如如如如y=htj)y=htj)的的的的查查查查找找找找速速速速度度度度作作作作出出出出贡贡贡贡献献献献：减减减减少少少少查查查查找找找找y y的的的的探探探探测测测测次次次次数数数数。容容容容易易易易理理理理解解解解，如如如如果果果果不不不不作作作作任任任任何何何何改改
63、改改进进进进，查查查查找找找找y y的的的的探探探探测测测测次次次次数数数数会会会会等等等等于于于于插插插插入入入入y y时时时时的的的的探探探探测测测测次次次次数数数数。如如如如果果果果插插插插入入入入y y时时时时x x已已已已在在在在桶桶桶桶htihti中中中中且且且且与与与与x x发发发发生生生生冲冲冲冲突突突突而而而而增增增增加加加加了了了了插插插插入入入入的的的的探探探探测测测测次次次次数数数数，那那那那么么么么，现现现现在在在在x x不不不不存存存存在在在在了了了了，只只只只要要要要将将将将x x腾腾腾腾出出出出的的的的桶桶桶桶htihti让让让让y y顶顶顶顶替替替替，就就就就
64、可可可可以以以以使使使使得得得得将将将将来来来来查查查查找找找找y y时时时时减减减减少少少少探探探探测测测测次次次次数数数数。因因因因此此此此改改改改进进进进HTDeleteHTDelete的的的的途途途途径径径径是是是是在在在在当当当当前前前前的的的的桶桶桶桶数数数数组组组组中中中中找找找找能能能能顶顶顶顶替替替替x x的的的的y y。如如如如果果果果找找找找不不不不到到到到，就就就就按按按按HTDeleteHTDelete的的的的原原原原版版版版处处处处理理理理；如如如如果果果果找找找找得得得得到到到到，在在在在用用用用y y顶顶顶顶替替替替x x之之之之后后后后还还还还可可可可以以以以
65、引引引引起起起起连连连连锁锁锁锁反反反反应应应应。 60609.29.2符符符符号号号号表表表表9.2.39.2.3实实实实现现现现符符符符号号号号表表表表的的的的简简简简单单单单方方方方法法法法闭闭闭闭散散散散列列列列9.2.3.59.2.3.5 HashTableHashTable的的的的定定定定义义义义中中中中未未未未实实实实现现现现的的的的函函函函数数数数( (续续续续) )改改改改进进进进HTDeleteHTDelete的的的的细细细细节节节节找找找找能能能能顶顶顶顶替替替替x x的的的的y y 假假假假设设设设被被被被删删删删除除除除元元元元素素素素x x位位位位于于于于桶桶桶桶单
66、单单单元元元元htihti。现现现现考考考考察察察察一一一一个个个个非非非非空空空空单单单单元元元元htjhtj 中中中中的的的的元元元元素素素素y y，其其其其散散散散列列列列函函函函数数数数值值值值设设设设为为为为h=h=hf(yhf(y) )，则则则则按按按按从从从从h h h h出出出出发发发发的的的的线线线线性性性性 探探探探测测测测，只只只只要要要要i i i i比比比比j j j j离离离离h h h h近近近近即即即即可可可可使使使使得得得得在在在在顶顶顶顶替替替替后后后后找找找找y y y y的的的的探探探探测测测测次次次次数数数数减减减减少少少少。 当当当当ijij时时时时
67、，若若若若ihih j j，则则则则不不不不可可可可用用用用元元元元素素素素htjhtj顶顶顶顶替替替替htihti；若若若若h h ijij或或或或ijhijh，则则则则可可可可用用用用元元元元素素素素htjhtj顶顶顶顶替替替替htihti。如如如如下下下下图图图图(a)(a)。当当当当jiji时时时时，若若若若jhjh I I，则则则则可可可可用用用用元元元元素素素素htjhtj顶顶顶顶替替替替htihti，如如如如下下下下图图图图 (b)(b)；否否否否则则则则不不不不可可可可。 这这这这里里里里以以以以线线线线性性性性探探探探测测测测为为为为前前前前题题题题，以以以以顶顶顶顶替替替替
68、后后后后减减减减少少少少探探探探测测测测次次次次数数数数为为为为目目目目标标标标。61619.29.2符符符符号号号号表表表表9.2.39.2.3实实实实现现现现符符符符号号号号表表表表的的的的简简简简单单单单方方方方法法法法闭闭闭闭散散散散列列列列9.2.3.59.2.3.5 HashTableHashTable的的的的定定定定义义义义中中中中未未未未实实实实现现现现的的的的函函函函数数数数( (续续续续) )(8)(8)改改改改进进进进HTDeleteHTDelete的的的的函函函函数数数数HTDelete1HTDelete1VoidVoidHTDelete1SetItemHTDelete
69、1SetItemx,HashTablex,HashTableH)H) intinti=i=FindMatch(xFindMatch(x); );if(isize)/if(isize)/&H-H-htihti=x=x可可可可以以以以去去去去掉掉掉掉 for(;)/for(;)/找找找找htihti的的的的顶顶顶顶替替替替元元元元素素素素H-H-stateistatei=2;/=2;/先先先先按按按按无无无无顶顶顶顶替替替替元元元元素素素素处处处处理理理理intintj;/j;/从从从从(i+1)%size(i+1)%size开开开开始始始始线线线线性性性性搜搜搜搜索索索索可可可可顶顶顶顶替替替替
70、元元元元素素素素for(j=(i+1)%H-size;!statej;j=(j+1)%H-size)for(j=(i+1)%H-size;!statej;j=(j+1)%H-size) 62629.29.2符符符符号号号号表表表表inth=(*H-inth=(*H-hfhf)(H-)(H-htjhtj););if(h=i&ij)|(ij&jh)|(jh&h=i)break;if(h=i&ij)|(ij&jh)|(jh&hif(H-statejstatej)break;/)break;/跳跳跳跳出出出出外外外外forfor循循循循环环环环 H-H-htihti=htj;H-=htj;H-stat
71、eistatei=statej;/=statej;/做做做做顶顶顶顶替替替替工工工工作作作作i=j;/i=j;/为为为为构构构构成成成成循循循循环环环环找找找找htjhtj的的的的顶顶顶顶替替替替元元元元素素素素 63639.29.2符符符符号号号号表表表表9.2.49.2.4开开开开散散散散列列列列的的的的效效效效率率率率若若若若能能能能选选选选择择择择一一一一个个个个好好好好的的的的散散散散列列列列函函函函数数数数，将将将将集集集集合合合合中中中中的的的的N N个个个个元元元元素素素素均均均均匀匀匀匀地地地地散散散散列列列列到到到到B B个个个个桶桶桶桶中中中中，那那那那么么么么，每每每每
72、个个个个桶桶桶桶中中中中平平平平均均均均有有有有N/BN/B个个个个元元元元素素素素，使使使使得得得得在在在在开开开开散散散散列列列列表表表表中中中中，InsertInsert，DeleteDelete和和和和MemberMember运运运运算算算算都都都都只只只只要要要要O(O(O(O(N/BN/B) ) ) )的的的的平平平平均均均均时时时时间间间间。进进进进而而而而当当当当N/BN/B为为为为一一一一常常常常数数数数时时时时，字字字字典典典典的的的的每每每每一一一一个个个个运运运运算算算算都都都都可可可可在在在在常常常常数数数数时时时时间间间间内内内内完完完完成成成成。因因因因此此此此：
73、对对对对于于于于开开开开散散散散列列列列表表表表，关关关关键键键键在在在在于于于于选选选选择择择择一一一一个个个个好好好好的的的的散散散散列列列列函函函函数数数数64649 9. .2 2符符符符号号号号表表表表9 9. .2 2. .5 5 散散散散列列列列函函函函数数数数举举举举例例例例( (1 1) )除除除除余余余余法法法法：h h( (k k) )= =k k %mm。( (2 2) )数数数数乘乘乘乘法法法法：h h( (k k) )= = 。( (3 3) )平平平平方方方方取取取取中中中中法法法法：h h( (k k) )= = %B B。( (4 4) )基基基基数数数数转转
74、转转换换换换法法法法 ：( (5 5) )随随随随机机机机数数数数法法法法 ：h h( (k k) )= =r ra an nd do omm( (k k) )。65659.29.2符符符符号号号号表表表表9.2.69.2.6闭闭闭闭散散散散列列列列的的的的重重重重新新新新散散散散列列列列技技技技术术术术 (1)(1)二二二二次次次次重重重重新新新新散散散散列列列列技技技技术术术术它它它它选选选选取取取取的的的的探探探探查查查查桶桶桶桶序序序序列列列列为为为为：h(x),hh(x),h1 1(x),h(x),h2 2(x),(x),h,h2i2i(x),h(x),h2i+12i+1(x),(x
75、), 其其其其中中中中， ， 。 (2)(2)随随随随机机机机重重重重新新新新散散散散列列列列技技技技术术术术 它它它它选选选选取取取取的的的的探探探探查查查查桶桶桶桶序序序序列列列列为为为为：,i=1,i=1，2 2，B-1B-1。 其其其其中中中中， 是是是是1 1，2 2，B-1B-1的的的的一一一一个个个个随随随随机机机机排排排排列列列列。 (3)(3)双双双双重重重重散散散散列列列列技技技技术术术术 这这这这种种种种方方方方法法法法使使使使用用用用2 2个个个个散散散散列列列列函函函函数数数数h h和和和和hh来来来来产产产产生生生生探探探探索索索索序序序序列列列列： 其其其其中中中
76、中 i=1i=1，2 2，B-1B-1。要要要要求求求求h(x)h(x)的的的的值值值值和和和和B B互互互互素素素素 。66669.3.19.3.1字字字字典典典典的的的的定定定定义义义义 字字字字典典典典是是是是以以以以有有有有序序序序集集集集为为为为基基基基础础础础的的的的抽抽抽抽象象象象数数数数据据据据类类类类型型型型。 它它它它支支支支持持持持以以以以下下下下运运运运算算算算：(1)Member(x)(1)Member(x)，成成成成员员员员运运运运算算算算。(2)Insert(x)(2)Insert(x)，插插插插入入入入运运运运算算算算：将将将将元元元元素素素素x x插插插插入入
77、入入集集集集合合合合。 (3)Delete(x)(3)Delete(x)，删删删删除除除除运运运运算算算算：将将将将元元元元素素素素x x从从从从当当当当前前前前集集集集合合合合中中中中删删删删去去去去。(4)Predecessor(x)(4)Predecessor(x)，前前前前驱驱驱驱运运运运算算算算：返返返返回回回回集集集集合合合合中中中中小小小小于于于于x x的的的的最最最最大大大大元元元元素素素素。(5)Successor(x)(5)Successor(x)，后后后后继继继继运运运运算算算算：返返返返回回回回集集集集合合合合中中中中大大大大于于于于x x的的的的最最最最小小小小元元元
78、元素素素素。 (6)Range(x(6)Range(x，y)y)，区区区区间间间间查查查查询询询询运运运运算算算算：返返返返回回回回集集集集合合合合中中中中界界界界于于于于x x和和和和y y之之之之间间间间，即即即即x xz zy y的的的的所所所所有有有有元元元元素素素素z z组组组组成成成成的的的的集集集集合合合合。(7)Min()(7)Min()，最最最最小小小小元元元元运运运运算算算算：返返返返回回回回当当当当前前前前集集集集合合合合中中中中依依依依线线线线性性性性序序序序最最最最小小小小的的的的元元元元素素素素。 9.39.3字字字字典典典典 67679.39.3字字字字典典典典
79、9.3.29.3.2用用用用数数数数组组组组实实实实现现现现字字字字典典典典 uu 用用用用数数数数组组组组实实实实现现现现字字字字典典典典与与与与用用用用数数数数组组组组实实实实现现现现符符符符号号号号表表表表的的的的不不不不同同同同之之之之处处处处： 可可可可以以以以利利利利用用用用线线线线性性性性序序序序将将将将字字字字典典典典中中中中的的的的元元元元素素素素从从从从小小小小到到到到大大大大依依依依序序序序存存存存储储储储在在在在数数数数组组组组中中中中，通通通通过过过过数数数数组组组组下下下下标标标标来来来来反反反反映映映映有有有有序序序序字字字字典典典典元元元元素素素素之之之之间间间
80、间的的的的序序序序关关关关系系系系。uu优优优优点点点点：可可可可用用用用二二二二分分分分法法法法高高高高效效效效地地地地实实实实现现现现与与与与线线线线性性性性序序序序有有有有关关关关的的的的一一一一些些些些运运运运算算算算。如如如如：Member(xMember(x) )，Predecessor(xPredecessor(x) )和和和和 Successor(xSuccessor(x) )可可可可在在在在时时时时间间间间O(lognO(lognO(lognO(logn) ) ) )内内内内实实实实现现现现。uu缺缺缺缺点点点点：插插插插入入入入和和和和删删删删除除除除运运运运算算算算的的的
81、的效效效效率率率率较较较较低低低低。每每每每执执执执行行行行一一一一次次次次InsertInsert或或或或DeleteDelete运运运运算算算算，需需需需要要要要移移移移动动动动部部部部分分分分数数数数组组组组元元元元素素素素，从从从从而而而而导导导导致致致致它它它它们们们们在在在在最最最最坏坏坏坏情情情情况况况况下下下下的的的的计计计计算算算算时时时时间间间间为为为为O(n)O(n)。uu考考考考虑虑虑虑：能能能能否否否否用用用用链链链链表表表表来来来来实实实实现现现现字字字字典典典典？MemberMember运运运运算算算算需需需需要要要要O(nO(n) )时时时时间间间间，一一一一旦
82、旦旦旦找找找找到到到到元元元元素素素素在在在在链链链链表表表表中中中中插插插插入入入入或或或或删删删删除除除除的的的的位位位位置置置置后后后后，只只只只要要要要用用用用O(1)O(1)O(1)O(1)时时时时间间间间就就就就可可可可完完完完成成成成插插插插入入入入或或或或删删删删除除除除操操操操作作作作。 两两两两种种种种实实实实现现现现方方方方式式式式均均均均不不不不可可可可取取取取！68689.39.3字字字字典典典典 9.3.39.3.3用用用用二二二二叉叉叉叉搜搜搜搜索索索索树树树树实实实实现现现现字字字字典典典典9.3.3.19.3.3.1基基基基本本本本思思思思想想想想：用用用用二
83、二二二叉叉叉叉树树树树来来来来存存存存储储储储有有有有序序序序集集集集，每每每每一一一一个个个个结结结结点点点点存存存存储储储储一一一一个个个个元元元元素素素素。满满满满足足足足：存存存存储储储储于于于于每每每每个个个个结结结结点点点点中中中中的的的的元元元元素素素素x x大大大大于于于于其其其其左左左左子子子子树树树树中中中中任任任任一一一一结结结结点点点点中中中中所所所所存存存存储储储储的的的的元元元元素素素素，小小小小于于于于其其其其右右右右子子子子树树树树中中中中任任任任一一一一结结结结点点点点中中中中所所所所存存存存储储储储的的的的元元元元素素素素。69699.39.3字字字字典典典
84、典 9.3.39.3.3用用用用二二二二叉叉叉叉搜搜搜搜索索索索树树树树实实实实现现现现字字字字典典典典9.3.3.29.3.3.2二二二二叉叉叉叉搜搜搜搜索索索索树树树树结结结结点点点点的的的的定定定定义义义义及及及及程程程程序序序序实实实实现现现现70709.39.3字字字字典典典典 9.3.39.3.3用用用用二二二二叉叉叉叉搜搜搜搜索索索索树树树树实实实实现现现现字字字字典典典典9.3.3.39.3.3.3二二二二叉叉叉叉搜搜搜搜索索索索树树树树的的的的定定定定义义义义及及及及运运运运算算算算的的的的实实实实现现现现: :7171例例 10， 18， 3， 8， 12， 2， 7， 4
85、1010181018310183810183812210183812710183812247101838122二二叉叉搜搜索索树树的的建建立立过过程程：7272删除508060120110150557053删除6080551201101505370805012060110150557053删除43例80501206011015055705343运运运运算算算算Delete(constDelete(constT&x)T&x)的的的的实实实实现现现现7373运运运运算算算算Delete(constDelete(constT&x)T&x)的的的的实实实实现现现现（续续续续）设设设设要要要要删删删删除
86、除除除二二二二叉叉叉叉搜搜搜搜索索索索树树树树中中中中的的的的结结结结点点点点p p p p ，分分分分三三三三种种种种情情情情况况况况：uup p p p为为为为叶叶叶叶结结结结点点点点 直直直直接接接接删删删删除除除除节节节节点点点点p p p puup p p p只只只只有有有有左左左左子子子子树树树树或或或或右右右右子子子子树树树树p p p p只只只只有有有有左左左左子子子子树树树树 用用用用p p p p的的的的左左左左儿儿儿儿子子子子代代代代替替替替p p p p p p p p只只只只有有有有右右右右子子子子树树树树 用用用用p p p p的的的的右右右右儿儿儿儿子子子子代代代
87、代替替替替p p p p uup p p p左左左左、右右右右子子子子树树树树均均均均非非非非空空空空找找找找p p p p的的的的左左左左子子子子树树树树的的的的最最最最大大大大元元元元素素素素结结结结点点点点（即即即即p p的的的的前前前前驱驱驱驱结结结结点点点点），用用用用该该该该结结结结点点点点代代代代替替替替结结结结点点点点p p，然然然然后后后后删删删删除除除除该该该该结结结结点点点点。7474用用用用二二二二叉叉叉叉搜搜搜搜索索索索树树树树实实实实现现现现字字字字典典典典时时时时间间间间复复复复杂杂杂杂性性性性分分分分析析析析 最最最最坏坏坏坏情情情情况况况况分分分分析析析析me
88、mber,insert,deletemember,insert,delete都都都都需需需需要要要要O(n)O(n)平平平平均均均均情情情情况况况况分分分分析析析析引引引引入入入入记记记记号号号号: :记记记记：p(np(n) )为为为为含含含含有有有有n n个个个个结结结结点点点点的的的的二二二二叉叉叉叉搜搜搜搜索索索索树树树树的的的的平平平平均均均均查查查查找找找找长长长长度度度度。显显显显然然然然p(0)=0,p(1)=1;p(0)=0,p(1)=1; 若若若若设设设设某某某某二二二二叉叉叉叉搜搜搜搜索索索索树树树树的的的的左左左左子子子子树树树树有有有有i i i i个个个个结结结结点
89、点点点，则则则则：p(i)+1p(i)+1为为为为查查查查找找找找左左左左子子子子树树树树中中中中每每每每个个个个结结结结点点点点的的的的平平平平均均均均查查查查找找找找长长长长度度度度; ;p(n-i-1)+1p(n-i-1)+1为为为为查查查查找找找找右右右右子子子子树树树树中中中中每每每每个个个个结结结结点点点点的的的的平平平平均均均均查查查查找找找找长长长长度度度度；由由由由此此此此构构构构造造造造而而而而得得得得的的的的二二二二叉叉叉叉搜搜搜搜索索索索树树树树在在在在n n个个个个结结结结点点点点的的的的查查查查找找找找概概概概率率率率相相相相等等等等的的的的情情情情况况况况下下下下
90、，其其其其平平平平均均均均查查查查找找找找长长长长度度度度为为为为：7575对对n用用数数学学归归纳纳法法可可以以证证明明:又又又又假假假假设设设设当当当当前前前前的的的的二二二二叉叉叉叉搜搜搜搜索索索索树树树树有有有有n n个个个个结结结结点点点点，而而而而它它它它是是是是从从从从空空空空树树树树开开开开始始始始反反反反复复复复调调调调用用用用n n次次次次的的的的InsertInsert运运运运算算算算得得得得到到到到的的的的，且且且且被被被被插插插插入入入入的的的的n n个个个个元元元元素素素素的的的的所所所所有有有有可可可可能能能能的的的的顺顺顺顺序序序序是是是是等等等等概概概概率率率
91、率的的的的。则则则则：当当n=1时时显显然然成成立立。若若设设in时时有有，则则7676平平平平均均均均情情情情况况况况下下下下的的的的时时时时间间间间复复复复杂杂杂杂度度度度为为为为：略略去去 -1/n-1/n项项7777运运运运算算算算Predecessor(xPredecessor(x) )和和和和Successor(xSuccessor(x) )的的的的实实实实现现现现：类类类类似似似似于于于于Search(xSearch(x) )算算算算法法法法运运运运算算算算Range(yRange(y,z),z)的的的的实实实实现现现现：可可可可借借借借助助助助于于于于Search(ySearc
92、h(y) )和和和和Successor(ySuccessor(y) )运运运运算算算算l l首首首首先先先先，用用用用Search(ySearch(y) )检检检检测测测测y y是是是是否否否否在在在在二二二二叉叉叉叉搜搜搜搜索索索索树树树树中中中中，是是是是则则则则输输输输出出出出y y，否否否否则则则则不不不不输输输输出出出出y y；l l然然然然后后后后，从从从从y y开开开开始始始始，不不不不断断断断地地地地用用用用SuccessorSuccessor找找找找当当当当前前前前元元元元素素素素在在在在二二二二叉叉叉叉搜搜搜搜索索索索树树树树中中中中的的的的后后后后继继继继元元元元素素素素
93、。当当当当找找找找出出出出的的的的后后后后继继继继元元元元素素素素x x满满满满足足足足xx zz时时时时，就就就就输输输输出出出出x x，并并并并将将将将x x作作作作为为为为当当当当前前前前元元元元素素素素。重重重重复复复复这这这这个个个个过过过过程程程程，直直直直到到到到找找找找出出出出的的的的当当当当前前前前元元元元素素素素的的的的后后后后继继继继元元元元素素素素大大大大于于于于z z，或或或或二二二二叉叉叉叉搜搜搜搜索索索索树树树树中中中中已已已已没没没没有有有有后后后后继继继继元元元元素素素素为为为为止止止止。l l时时时时间间间间复复复复杂杂杂杂度度度度：若若若若二二二二叉叉叉叉
94、树树树树搜搜搜搜索索索索树树树树中中中中有有有有r r个个个个元元元元素素素素x x满满满满足足足足yy xx zz，则则则则在在在在最最最最坏坏坏坏情情情情况况况况下下下下用用用用时时时时间间间间，在在在在平平平平均均均均情情情情况况况况下下下下用用用用时时时时间间间间可可可可实实实实现现现现RangeRange运运运运算算算算。 7878运运运运算算算算Range(y,zRange(y,z) )的的的的改改改改进进进进：考考考考虑虑虑虑半半半半无无无无限限限限查查查查询询询询区区区区域域域域, ,即即即即找找找找出出出出二二二二叉叉叉叉搜搜搜搜索索索索树树树树中中中中满满满满足足足足yy
95、xx的的的的所所所所有有有有元元元元素素素素x x。 当当当当y y不不不不在在在在二二二二叉叉叉叉搜搜搜搜索索索索树树树树中中中中时时时时，产产产产生生生生一一一一条条条条从从从从根根根根到到到到叶叶叶叶的的的的路路路路径径径径。如如如如下下下下图图图图(a)(a)当当当当y y在在在在二二二二叉叉叉叉搜搜搜搜索索索索树树树树中中中中时时时时，产产产产生生生生一一一一条条条条从从从从根根根根到到到到存存存存储储储储元元元元素素素素y y的的的的结结结结点点点点的的的的路路路路径径径径。如如如如下下下下图图图图(b)(b)7979在在在在找找找找到到到到的的的的搜搜搜搜索索索索路路路路径径径径
96、上上上上的的的的所所所所有有有有结结结结点点点点可可可可分分分分为为为为以以以以下下下下3 3种种种种情情情情况况况况，如如如如下下下下图图图图 ：8080运运运运算算算算Range(y,zRange(y,z) )的的的的实实实实现现现现：可可可可用用用用类类类类似似似似于于于于Range(y,Range(y, ) )算算算算法法法法 从从从从二二二二叉叉叉叉搜搜搜搜索索索索树树树树的的的的根根根根结结结结点点点点开开开开始始始始，同同同同时时时时与与与与y y y y和和和和z z z z比比比比较较较较, , , ,此此此此时时时时, , , ,结结结结点点点点分分分分类类类类的的的的情情
97、情情况况况况可可可可能能能能有有有有（见见见见下下下下图图图图） ：8181运运运运算算算算Range(y,zRange(y,z) )的的的的搜搜搜搜索索索索路路路路径径径径如如如如下下下下图图图图： 82829.49.4优优优优先先先先队队队队列列列列 9.4.09.4.0优优优优先先先先队队队队列列列列的的的的原原原原型型型型排排排排队队队队上上上上车车车车，老老老老弱弱弱弱病病病病残残残残者者者者优优优优先先先先上上上上车车车车排排排排队队队队候候候候诊诊诊诊，危危危危急急急急病病病病人人人人优优优优先先先先就就就就诊诊诊诊洗洗洗洗相相相相馆馆馆馆为为为为顾顾顾顾客客客客洗洗洗洗照照照照
98、片片片片，加加加加钱钱钱钱加加加加急急急急者者者者优优优优先先先先洗洗洗洗分分分分时时时时操操操操作作作作系系系系统统统统运运运运行行行行程程程程序序序序，小小小小程程程程序序序序优优优优先先先先贪贪贪贪心心心心算算算算法法法法对对对对解解解解分分分分量量量量的的的的选选选选择择择择，按按按按元元元元素素素素的的的的某某某某种种种种特特特特征征征征值值值值，大大大大( ( ( (或或或或小小小小) ) ) )的的的的优优优优先先先先在在在在一一一一个个个个集集集集合合合合中中中中搜搜搜搜索索索索，按按按按元元元元素素素素的的的的某某某某种种种种特特特特征征征征值值值值，大大大大( ( ( (或
99、或或或小小小小) ) ) )的的的的优优优优先先先先处处处处理理理理或或或或服服服服务务务务时时时时只只只只关关关关心心心心对对对对象象象象中中中中谁谁谁谁的的的的优优优优先先先先级级级级最最最最高高高高通通通通常常常常的的的的队队队队列列列列是是是是一一一一种种种种优优优优先先先先队队队队列列列列最最最最先先先先到到到到者者者者优优优优先先先先级级级级最最最最高高高高83839.49.4优优优优先先先先队队队队列列列列9.4.19.4.1优优优优先先先先队队队队列列列列的的的的定定定定义义义义 优优优优先先先先队队队队列列列列也也也也是是是是一一一一个个个个以以以以集集集集合合合合为为为为基
100、基基基础础础础的的的的抽抽抽抽象象象象数数数数据据据据类类类类型型型型。优优优优先先先先队队队队列列列列中中中中的的的的每每每每一一一一个个个个元元元元素素素素都都都都有有有有一一一一个个个个优优优优先先先先级级级级值值值值。优优优优先先先先队队队队列列列列中中中中元元元元素素素素x x的的的的优优优优先先先先级级级级值值值值记记记记为为为为p(x)p(x)，它它它它可可可可以以以以是是是是一一一一个个个个实实实实数数数数，也也也也可可可可以以以以是是是是一一一一个个个个一一一一般般般般的的的的全全全全序序序序集集集集中中中中的的的的元元元元素素素素。优优优优先先先先级级级级值值值值用用用用来
101、来来来表表表表示示示示该该该该元元元元素素素素出出出出列列列列的的的的优优优优先先先先级级级级。通通通通常常常常约约约约定定定定优优优优先先先先级级级级值值值值小小小小的的的的优优优优先先先先级级级级高高高高。也也也也可可可可以以以以约约约约定定定定优优优优先先先先级级级级值值值值大大大大的的的的优优优优先先先先级级级级高高高高。优优优优先先先先队队队队列列列列支支支支持持持持的的的的基基基基本本本本运运运运算算算算有有有有：(1)Size()(1)Size()：返返返返回回回回优优优优先先先先队队队队列列列列中中中中元元元元素素素素个个个个数数数数。(2)Min()(2)Min()：返返返返
102、回回回回优优优优先先先先队队队队列列列列中中中中具具具具有有有有最最最最小小小小优优优优先先先先级级级级值值值值的的的的元元元元素素素素。(3)Insert(x)(3)Insert(x)：将将将将元元元元素素素素x x插插插插入入入入优优优优先先先先队队队队列列列列。(4)DeleteMin(x)(4)DeleteMin(x)：删删删删除除除除优优优优先先先先队队队队列列列列中中中中具具具具有有有有最最最最小小小小优优优优先先先先级级级级值值值值的的的的元元元元素素素素，并并并并保保保保存存存存到到到到x x中中中中。 84849.49.4优优优优先先先先队队队队列列列列9.4.29.4.2用
103、用用用实实实实现现现现有有有有序序序序字字字字典典典典的的的的方方方方式式式式实实实实现现现现优优优优先先先先队队队队列列列列(1)(1)优优优优先先先先队队队队列列列列与与与与字字字字典典典典的的的的相相相相似似似似性性性性与与与与区区区区别别别别：l l优优优优先先先先队队队队列列列列中中中中元元元元素素素素的的的的优优优优先先先先级级级级值值值值可可可可以以以以看看看看作作作作是是是是有有有有序序序序字字字字典典典典中中中中元元元元素素素素的的的的线线线线性性性性序序序序值值值值。l l在在在在有有有有序序序序字字字字典典典典中中中中，不不不不同同同同的的的的元元元元素素素素具具具具有有
104、有有不不不不同同同同的的的的线线线线性性性性序序序序值值值值，其其其其插插插插入入入入运运运运算算算算仅仅仅仅当当当当要要要要插插插插入入入入元元元元素素素素x x的的的的线线线线性性性性序序序序值值值值与与与与当当当当前前前前字字字字典典典典中中中中所所所所有有有有元元元元素素素素的的的的线线线线性性性性序序序序值值值值都都都都不不不不同同同同时时时时才才才才执执执执行行行行。l l对对对对于于于于优优优优先先先先队队队队列列列列来来来来说说说说，不不不不同同同同的的的的元元元元素素素素可可可可以以以以有有有有相相相相同同同同的的的的优优优优先先先先级级级级值值值值。因因因因此此此此，优优优
105、优先先先先队队队队列列列列的的的的插插插插入入入入运运运运算算算算即即即即使使使使在在在在当当当当前前前前优优优优先先先先队队队队列列列列中中中中存存存存在在在在与与与与要要要要插插插插入入入入元元元元素素素素x x有有有有相相相相同同同同的的的的优优优优先先先先级级级级值值值值的的的的元元元元素素素素时时时时，也也也也要要要要执执执执行行行行元元元元素素素素x x的的的的插插插插入入入入。 85859.49.4优优优优先先先先队队队队列列列列9.4.29.4.2用用用用实实实实现现现现有有有有序序序序字字字字典典典典的的的的方方方方式式式式实实实实现现现现优优优优先先先先队队队队列列列列(2
106、)(2)(2)(2)由由由由于于于于优优优优先先先先队队队队列列列列与与与与字字字字典典典典的的的的相相相相似似似似性性性性, , , ,除除除除了了了了散散散散列列列列表表表表之之之之外外外外, , , ,所所所所有有有有实实实实现现现现字字字字典典典典和和和和有有有有序序序序字字字字典典典典的的的的方方方方法法法法都都都都可可可可用用用用于于于于实实实实现现现现优优优优先先先先队队队队列列列列。 用用用用有有有有序序序序链链链链表表表表实实实实现现现现优优优优先先先先队队队队列列列列;(;(;(;(InsertInsert低低低低效效效效) ) ) ) 用用用用二二二二叉叉叉叉搜搜搜搜索索
107、索索树树树树实实实实现现现现优优优优先先先先队队队队列列列列;(;(;(;(Insert,Insert,DeleteMinDeleteMin, ,MinMin 均均均均低低低低效效效效) ) ) ) 用用用用AVLAVLAVLAVL树树树树实实实实现现现现优优优优先先先先队队队队列列列列;(;(;(;(逻逻逻逻辑辑辑辑复复复复杂杂杂杂) ) ) ) 用用用用无无无无序序序序链链链链表表表表实实实实现现现现优优优优先先先先队队队队列列列列;(;(;(;(DeleteMinDeleteMin, ,MinMin均均均均低低低低效效效效) ) ) ) 都都都都有有有有缺缺缺缺点点点点。原原原原因因因因
108、在在在在于于于于没没没没有有有有考考考考虑虑虑虑到到到到优优优优先先先先队队队队列列列列的的的的特特特特性性性性。86869.49.4优优优优先先先先队队队队列列列列9.4.39.4.3用用用用优优优优先先先先级级级级树树树树实实实实现现现现优优优优先先先先队队队队列列列列 1.1.1.1.优优优优先先先先队队队队列列列列的的的的特特特特征征征征: : : : DeleteMinDeleteMin和和和和MinMin只只只只关关关关心心心心优优优优先先先先级级级级最最最最高高高高的的的的元元元元素素素素 InsertInsert的的的的元元元元素素素素不不不不要要要要求求求求全全全全局局局局的
109、的的的序序序序关关关关系系系系因因因因此此此此实实实实现现现现优优优优先先先先队队队队列列列列的的的的结结结结构构构构只只只只要要要要求求求求方方方方便便便便DeleteMinDeleteMin和和和和Min,Min,而而而而对对对对InsertInsert也也也也只只只只要要要要求求求求不不不不给给给给结结结结构构构构的的的的维维维维护护护护带带带带来来来来太太太太大大大大的的的的麻麻麻麻烦烦烦烦。根根根根据据据据这这这这两两两两个个个个特特特特征征征征, ,人人人人们们们们发发发发明明明明了了了了优优优优先先先先级级级级树树树树。87879.49.4优优优优先先先先队队队队列列列列9.4.
110、39.4.3用用用用优优优优先先先先级级级级树树树树实实实实现现现现优优优优先先先先队队队队列列列列( ( ( (续续续续) ) ) )2.2.2.2.优优优优先先先先级级级级树树树树的的的的概概概概念念念念优优优优先先先先级级级级树树树树是是是是满满满满足足足足下下下下面面面面的的的的优优优优先先先先级级级级性性性性质质质质的的的的二二二二叉叉叉叉树树树树：(1)(1)树树树树中中中中每每每每一一一一结结结结点点点点存存存存储储储储一一一一个个个个元元元元素素素素。 (2)(2)(2)(2)任任任任一一一一结结结结点点点点中中中中存存存存储储储储的的的的元元元元素素素素的的的的优优优优先先先
111、先级级级级值值值值不不不不大大大大( ( ( (小小小小) ) ) )于于于于 其其其其儿儿儿儿子子子子结结结结点点点点中中中中存存存存储储储储的的的的元元元元素素素素的的的的优优优优先先先先级级级级值值值值即即即即父父父父结结结结点点点点的的的的 优优优优先先先先级级级级不不不不低低低低于于于于其其其其儿儿儿儿子子子子结结结结点点点点的的的的优优优优先先先先级级级级。 换换换换句句句句话话话话说说说说，越越越越接接接接近近近近根根根根的的的的结结结结点点点点中中中中的的的的元元元元素素素素的的的的优优优优先先先先级级级级越越越越高高高高，越越越越方方方方便便便便被被被被访访访访问问问问，因因
112、因因为为为为根根根根最最最最方方方方便便便便被被被被访访访访问问问问。 相相相相应应应应的的的的优优优优先先先先级级级级树树树树称称称称为为为为极极极极小小小小( (大大大大) )化化化化优优优优先先先先级级级级树树树树。88889.49.4优优优优先先先先队队队队列列列列9.4.49.4.4用用用用堆堆堆堆实实实实现现现现优优优优先先先先队队队队列列列列用用用用优优优优先先先先级级级级树树树树实实实实现现现现优优优优先先先先队队队队列列列列仍仍仍仍有有有有不不不不足足足足：Insert(xInsert(x) )和和和和DeleteMin(xDeleteMin(x) )后后后后对对对对结结结结
113、构构构构的的的的维维维维护护护护，在在在在最最最最坏坏坏坏情情情情况况况况下下下下，仍仍仍仍需需需需O(h)=O(n)O(h)=O(n)。如如如如果果果果让让让让优优优优先先先先级级级级树树树树近近近近似似似似满满满满, , , ,从从从从而而而而h=log h=log h=log h=log n,n,n,n,达达达达到到到到最最最最小小小小, , , ,那那那那么么么么，结结结结果果果果将将将将令令令令人人人人满满满满意意意意：在在在在最最最最坏坏坏坏情情情情况况况况下下下下， Min(Min() )将将将将只只只只需需需需O(1),O(1),Insert(x)Insert(x)和和和和De
114、leteMin(xDeleteMin(x) )后后后后对对对对结结结结构构构构的的的的维维维维护护护护只只只只需需需需O(log n)O(log n)O(log n)O(log n)。因因因因而而而而引引引引入入入入堆堆堆堆的的的的概概概概念念念念并并并并用用用用堆堆堆堆来来来来实实实实现现现现优优优优先先先先队队队队列列列列。(1)(1)(1)(1)堆堆堆堆的的的的概概概概念念念念：如如如如果果果果一一一一棵棵棵棵优优优优先先先先级级级级树树树树是是是是一一一一棵棵棵棵近近近近似似似似满满满满二二二二叉叉叉叉树树树树，那那那那么么么么，这这这这棵棵棵棵具具具具有有有有优优优优先先先先级级级级
115、性性性性质质质质的的的的近近近近似似似似满满满满二二二二叉叉叉叉树树树树( ( ( (外外外外形形形形像像像像堆堆堆堆) ) ) )就就就就叫叫叫叫做做做做堆堆堆堆。(2)(2)(2)(2)用用用用堆堆堆堆实实实实现现现现优优优优先先先先队队队队列列列列： Min()Min()、Insert(x)Insert(x)和和和和DeleteMin(xDeleteMin(x) )运运运运算算算算的的的的实实实实现现现现89899.49.4优优优优先先先先队队队队列列列列9.4.59.4.5用用用用数数数数组组组组表表表表示示示示堆堆堆堆从从从从而而而而实实实实现现现现优优优优先先先先队队队队列列列列(
116、1)(1)用用用用数数数数组组组组表表表表示示示示堆堆堆堆： 从从从从1 1 1 1开开开开始始始始对对对对堆堆堆堆的的的的结结结结点点点点从从从从根根根根开开开开始始始始自自自自上上上上而而而而下下下下逐逐逐逐层层层层、 每每每每层层层层从从从从左左左左到到到到右右右右进进进进行行行行编编编编号号号号，然然然然后后后后让让让让结结结结点点点点中中中中的的的的元元元元 素素素素按按按按编编编编号号号号在在在在数数数数组组组组A A A A中中中中与与与与下下下下标标标标对对对对号号号号入入入入座座座座。(2)(2)用用用用数数数数组组组组表表表表示示示示堆堆堆堆的的的的优优优优点点点点： 存存
117、存存储储储储紧紧紧紧凑凑凑凑，空空空空间间间间利利利利用用用用率率率率高高高高 父父父父子子子子关关关关系系系系简简简简单单单单清清清清晰晰晰晰: :存存存存放放放放在在在在AiAi的的的的是是是是结结结结点点点点i i的的的的元元元元素素素素,A2i,A2i和和和和A2i+1A2i+1分分分分别别别别是是是是结结结结点点点点i i的的的的左左左左和和和和右右右右儿儿儿儿子子子子结结结结点点点点2i2i和和和和2i+12i+1的的的的元元元元素素素素， Ai/2Ai/2是是是是结结结结点点点点i i的的的的父父父父结结结结点点点点的的的的元元元元素素素素。90909.49.4优优优优先先先先队
118、队队队列列列列9.4.59.4.5用用用用数数数数组组组组表表表表示示示示堆堆堆堆从从从从而而而而实实实实现现现现优优优优先先先先队队队队列列列列（续续续续）(3)(3)数数数数组组组组实实实实现现现现优优优优先先先先队队队队列列列列极极极极小小小小化化化化堆堆堆堆MinHeapMinHeapMinHeapMinHeap91919.49.4优优优优先先先先队队队队列列列列9.4.69.4.6优优优优先先先先队队队队列列列列的的的的应应应应用用用用HuffmanHuffmanHuffmanHuffman编编编编码码码码9.4.6.19.4.6.1问问问问题题题题的的的的提提提提出出出出已已已已知
119、知知知一一一一个个个个文文文文本本本本文文文文件件件件，要要要要求求求求把把把把它它它它转转转转换换换换成成成成一一一一个个个个电电电电子子子子文文文文档档档档，以以以以便便便便存存存存储储储储在在在在磁磁磁磁介介介介质质质质中中中中或或或或在在在在网网网网络络络络上上上上传传传传输输输输。从从从从存存存存储储储储的的的的角角角角度度度度看看看看，我我我我们们们们自自自自然然然然希希希希望望望望该该该该电电电电子子子子文文文文档档档档越越越越短短短短越越越越好好好好即即即即存存存存储储储储占占占占用用用用的的的的空空空空间间间间越越越越少少少少越越越越好好好好；从从从从传传传传输输输输的的的的
120、角角角角度度度度看看看看，我我我我们们们们自自自自然然然然也也也也希希希希望望望望该该该该电电电电子子子子文文文文档档档档越越越越短短短短越越越越好好好好即即即即传传传传输输输输占占占占用用用用的的的的时时时时间间间间越越越越少少少少越越越越好好好好。因因因因此此此此，我我我我们们们们要要要要求求求求转转转转换换换换成成成成的的的的电电电电子子子子文文文文档档档档尽尽尽尽量量量量地地地地短短短短，尽尽尽尽量量量量地地地地压压压压缩缩缩缩。有有有有许许许许多多多多名名名名家家家家说说说说过过过过，把把把把一一一一个个个个问问问问题题题题表表表表述述述述清清清清楚楚楚楚了了了了，就就就就已已已已经
121、经经经解解解解决决决决了了了了问问问问题题题题的的的的一一一一半半半半。这这这这说说说说明明明明问问问问题题题题的的的的表表表表述述述述很很很很重重重重要要要要，表表表表述述述述得得得得越越越越清清清清楚楚楚楚、越越越越精精精精确确确确，对对对对问问问问题题题题的的的的解解解解决决决决越越越越好好好好。上上上上述述述述问问问问题题题题还还还还需需需需要要要要更更更更精精精精确确确确的的的的表表表表述述述述。92929.49.4优优优优先先先先队队队队列列列列9.4.69.4.6优优优优先先先先队队队队列列列列的的的的应应应应用用用用HuffmanHuffmanHuffmanHuffman编编编
122、编码码码码9.4.6.29.4.6.2表表表表述述述述HuffmanHuffmanHuffmanHuffman编编编编码码码码问问问问题题题题的的的的准准准准备备备备对对对对涉涉涉涉及及及及的的的的有有有有关关关关对对对对象象象象、概概概概念念念念、术术术术语语语语、和和和和记记记记号号号号的的的的准准准准备备备备 一一一一个个个个文文文文本本本本文文文文件件件件就就就就是是是是一一一一个个个个字字字字符符符符串串串串，记记记记为为为为F F。 文文文文本本本本文文文文件件件件中中中中所所所所用用用用到到到到的的的的不不不不同同同同的的的的字字字字符符符符组组组组成成成成的的的的集集集集合合合
123、合，记记记记为为为为C C。 CC中中中中的的的的字字字字符符符符c c在在在在文文文文件件件件中中中中出出出出现现现现的的的的频频频频率率率率/ /次次次次数数数数，记记记记为为为为f(c)f(c)或或或或f fc c。 字字字字符符符符的的的的编编编编码码码码0/10/1串串串串。如如如如字字字字符符符符 aa的的的的ASCIIASCII码码码码是是是是 0110000101100001。 字字字字符符符符编编编编码码码码的的的的码码码码长长长长0/10/1串串串串的的的的串串串串长长长长。记记记记c cC C的的的的码码码码长长长长为为为为l(c)l(c)。 文文文文件件件件F F编编编
124、编码码码码的的的的码码码码长长长长原原原原文文文文本本本本文文文文件件件件编编编编码码码码后后后后的的的的0/10/1串串串串的的的的累累累累计计计计长长长长。记记记记为为为为L(F)=L(F)=c cC Cf(c)*f(c)*l l(c)(c)。 字字字字符符符符的的的的定定定定长长长长编编编编码码码码。 ASCIIASCII码码码码是是是是一一一一种种种种定定定定长长长长编编编编码码码码。不不不不可可可可能能能能压压压压缩缩缩缩。 字字字字符符符符的的的的变变变变长长长长编编编编码码码码字字字字符符符符的的的的码码码码长长长长随随随随字字字字符符符符而而而而变变变变。 93939.49.4
125、优优优优先先先先队队队队列列列列9.4.69.4.6优优优优先先先先队队队队列列列列的的的的应应应应用用用用HuffmanHuffmanHuffmanHuffman编编编编码码码码9.4.6.29.4.6.2表表表表述述述述HuffmanHuffmanHuffmanHuffman编编编编码码码码问问问问题题题题的的的的的的的的准准准准备备备备( (续续续续) )编编编编码码码码与与与与解解解解码码码码既既既既要要要要编编编编码码码码又又又又要要要要解解解解码码码码，以以以以便便便便复复复复原原原原文文文文件件件件。 二二二二义义义义性性性性: :不不不不能能能能造造造造成成成成一一一一串串串串
126、编编编编码码码码有有有有两两两两种种种种理理理理解解解解。 前前前前缀缀缀缀码码码码：为为为为了了了了解解解解码码码码时时时时不不不不会会会会出出出出现现现现二二二二义义义义性性性性，要要要要求求求求任任任任意意意意一一一一个个个个字字字字符符符符的的的的编编编编码码码码不不不不能能能能是是是是另另另另一一一一个个个个字字字字符符符符的的的的前前前前缀缀缀缀。 字字字字符符符符集集集集C C的的的的前前前前缀缀缀缀码码码码的的的的表表表表示示示示以以以以C C中中中中的的的的字字字字符符符符为为为为叶叶叶叶结结结结点点点点的的的的二二二二叉叉叉叉树树树树，如如如如aa0 0，b b101101
127、，c c100100，d d111111，e e11011101，f f11001100可可可可表表表表示示示示成成成成右右右右图图图图的的的的二二二二叉叉叉叉树树树树。这这这这棵棵棵棵树树树树叫叫叫叫字字字字符符符符集集集集C C的的的的前前前前缀缀缀缀编编编编码码码码树树树树, ,记记记记为为为为T T。acbfed010101010194949.49.4优优优优先先先先队队队队列列列列9.4.69.4.6优优优优先先先先队队队队列列列列的的的的应应应应用用用用HuffmanHuffmanHuffmanHuffman编编编编码码码码9.4.6.39.4.6.3HuffmanHuffmanH
128、uffmanHuffman编编编编码码码码问问问问题题题题的的的的表表表表述述述述问问问问题题题题数数数数学学学学化化化化。经经经经上上上上述述述述准准准准备备备备，我我我我们们们们看看看看到到到到，字字字字符符符符c cC C的的的的码码码码长长长长l l (c)(c)正正正正是是是是c c在在在在字字字字符符符符集集集集C C的的的的前前前前缀缀缀缀编编编编码码码码树树树树T T中中中中的的的的深深深深度度度度，记记记记为为为为d dT T(c(c) )。这这这这样样样样，我我我我们们们们的的的的问问问问题题题题可可可可更更更更具具具具体体体体、更更更更精精精精确确确确地地地地表表表表述述
129、述述为为为为：已已已已知知知知字字字字符符符符串串串串F F和和和和出出出出现现现现在在在在F F中中中中的的的的字字字字符符符符集集集集C C及及及及C C中中中中每每每每一一一一字字字字符符符符c c出出出出现现现现的的的的频频频频率率率率/ /次次次次数数数数f(c)f(c)，要要要要求求求求C C的的的的一一一一棵棵棵棵最最最最优优优优的的的的前前前前缀缀缀缀编编编编码码码码树树树树T,T,使使使使得得得得F F的的的的编编编编码码码码长长长长 c cC Cf(c)*f(c)*d dT T(c(c)B(T)B(T)达达达达到到到到最最最最小小小小。这这这这棵棵棵棵最最最最优优优优的的的
130、的前前前前缀缀缀缀编编编编码码码码树树树树叫叫叫叫HuffmanHuffmanHuffmanHuffman编编编编码码码码树树树树。相相相相应应应应的的的的前前前前缀缀缀缀编编编编码码码码叫叫叫叫HuffmanHuffmanHuffmanHuffman编编编编码码码码。95959.49.4优优优优先先先先队队队队列列列列9.4.69.4.6优优优优先先先先队队队队列列列列的的的的应应应应用用用用HuffmanHuffmanHuffmanHuffman编编编编码码码码9.4.6.49.4.6.4求求求求解解解解问问问问题题题题的的的的设设设设想想想想与与与与分分分分析析析析 (1) (1) (1
131、) (1) 问问问问题题题题的的的的目目目目标标标标是是是是求求求求C C C C的的的的最最最最优优优优前前前前缀缀缀缀编编编编码码码码树树树树T T，因因因因此此此此，我我我我们们们们应应应应 该该该该先先先先分分分分析析析析一一一一下下下下C C C C的的的的最最最最优优优优的的的的前前前前缀缀缀缀编编编编码码码码树树树树T T的的的的性性性性质质质质: :它它它它是是是是一一一一棵棵棵棵以以以以C C中中中中 的的的的字字字字符符符符为为为为叶叶叶叶结结结结点点点点的的的的健健健健全全全全二二二二叉叉叉叉树树树树( (这这这这容容容容易易易易用用用用反反反反证证证证法法法法加加加加以
132、以以以证证证证明明明明) )。 因因因因而而而而一一一一定定定定有有有有两两两两个个个个最最最最深深深深的的的的叶叶叶叶结结结结点点点点是是是是兄兄兄兄弟弟弟弟结结结结点点点点。 (2)(2)按按按按照照照照大大大大数数数数学学学学家家家家、大大大大教教教教育育育育家家家家波波波波利利利利亚亚亚亚的的的的观观观观点点点点，“ “除除除除数数数数学学学学和和和和论论论论 证证证证逻逻逻逻辑辑辑辑外外外外, ,我我我我们们们们所所所所有有有有的的的的知知知知识识识识都都都都是是是是由由由由一一一一些些些些猜猜猜猜想想想想所所所所构构构构成成成成的的的的。”为为为为了了了了 得得得得到到到到有有有有
133、用用用用的的的的结结结结论论论论、方方方方法法法法，总总总总是是是是从从从从猜猜猜猜想想想想开开开开始始始始。而而而而猜猜猜猜想想想想的的的的依依依依据据据据是是是是 合合合合情情情情推推推推理理理理。就就就就摆摆摆摆在在在在面面面面前前前前的的的的问问问问题题题题而而而而言言言言，可可可可直直直直观观观观地地地地设设设设想想想想：最最最最深深深深的的的的叶叶叶叶结结结结点点点点中中中中 有有有有两两两两个个个个兄兄兄兄弟弟弟弟是是是是C C中中中中频频频频 度度度度最最最最低低低低的的的的字字字字符符符符x x和和和和yy，因因因因为为为为编编编编码码码码最最最最长长长长的的的的字字字字 符
134、符符符应应应应该该该该是是是是频频频频度度度度最最最最低低低低的的的的字字字字符符符符( (这这这这需需需需要要要要证证证证明明明明) )。96969.49.4优优优优先先先先队队队队列列列列9.4.69.4.6优优优优先先先先队队队队列列列列的的的的应应应应用用用用HuffmanHuffmanHuffmanHuffman编编编编码码码码9.4.6.49.4.6.4求求求求解解解解问问问问题题题题的的的的设设设设想想想想与与与与分分分分析析析析( (续续续续) )(3)(3)用用用用字字字字符符符符z z代代代代替替替替字字字字符符符符x x和和和和y,y,让让让让f(x)+f(y)f(x)+
135、f(y)作作作作为为为为字字字字符符符符zz的的的的频频频频度度度度 f(z)f(z)，相相相相应应应应地地地地，在在在在T T中中中中删删删删去去去去兄兄兄兄弟弟弟弟叶叶叶叶结结结结点点点点x x和和和和yy，而而而而且且且且用用用用zz取取取取代代代代已已已已经经经经成成成成为为为为叶叶叶叶结结结结点点点点的的的的x x和和和和y y的的的的父父父父结结结结点点点点，得得得得到到到到一一一一棵棵棵棵新新新新的的的的健健健健全全全全二二二二叉叉叉叉编编编编码码码码树树树树TTTT，那那那那么么么么，TTTT应应应应该该该该是是是是C-x,yzC-x,yzC-x,yzC-x,yz的的的的最最最
136、最优优优优前前前前缀缀缀缀编编编编码码码码树树树树( (这这这这需需需需要要要要证证证证明明明明) )。若若若若上上上上述述述述设设设设想想想想与与与与分分分分析析析析正正正正确确确确，那那那那么么么么，问问问问题题题题就就就就有有有有了了了了解解解解法法法法：把把把把C C中中中中的的的的字字字字符符符符以以以以其其其其频频频频度度度度为为为为优优优优先先先先级级级级值值值值，且且且且以以以以小小小小者者者者优优优优先先先先组组组组织织织织成成成成优优优优先先先先队队队队列列列列Q Q Q Q。然然然然后后后后反反反反复复复复地地地地执执执执行行行行下下下下面面面面两两两两个个个个语语语语句
137、句句句： 删删删删除除除除Q Q Q Q中中中中优优优优先先先先级级级级最最最最高高高高的的的的两两两两个个个个字字字字符符符符，设设设设为为为为x x x x和和和和y y y y； 虚虚虚虚拟拟拟拟字字字字符符符符z(z(z(z(分分分分别别别别以以以以x x x x和和和和y y y y为为为为左左左左和和和和右右右右儿儿儿儿子子子子) ) ) )，并并并并赋赋赋赋予予予予优优优优先先先先 级级级级值值值值f(z)=f(x)+f(y),f(z)=f(x)+f(y),f(z)=f(x)+f(y),f(z)=f(x)+f(y),插插插插入入入入Q Q Q Q；直直直直到到到到Q Q Q Q为
138、为为为空空空空，其其其其结结结结果果果果就就就就是是是是C C C C的的的的最最最最优优优优前前前前缀缀缀缀编编编编码码码码树树树树。97979.49.4优优优优先先先先队队队队列列列列9.4.69.4.6优优优优先先先先队队队队列列列列的的的的应应应应用用用用HuffmanHuffmanHuffmanHuffman编编编编码码码码9.4.6.59.4.6.5HuffmanHuffmanHuffmanHuffman编编编编码码码码问问问问题题题题的的的的解解解解决决决决从从从从理理理理论论论论上上上上看看看看待待待待HuffmanHuffmanHuffmanHuffman编编编编码码码码问问
139、问问题题题题，在在在在9.4.6.49.4.6.4求求求求解解解解问问问问题题题题的的的的设设设设想想想想与与与与分分分分析析析析中中中中的的的的(2)(2)和和和和(3)(3)所所所所猜猜猜猜想想想想的的的的分分分分别别别别是是是是问问问问题题题题的的的的解解解解的的的的贪贪贪贪心心心心选选选选择择择择性性性性质质质质和和和和最最最最优优优优子子子子结结结结构构构构性性性性质质质质。这这这这两两两两个个个个性性性性质质质质保保保保证证证证了了了了问问问问题题题题可可可可以以以以用用用用基基基基于于于于优优优优先先先先队队队队 列列列列的的的的前前前前述述述述算算算算法法法法正正正正确确确确地
140、地地地加加加加以以以以求求求求解解解解。所所所所以以以以问问问问题题题题的的的的真真真真 正正正正解解解解决决决决有有有有待待待待对对对对贪贪贪贪心心心心选选选选择择择择性性性性质质质质和和和和最最最最优优优优子子子子结结结结构构构构性性性性质质质质作作作作理理理理论论论论上上上上的的的的证证证证明明明明。此此此此外外外外，还还还还得得得得给给给给出出出出HuffmanHuffmanHuffmanHuffman编编编编 码码码码和和和和解解解解码码码码的的的的简简简简洁洁洁洁实实实实现现现现。98989.49.4优优优优先先先先队队队队列列列列9.4.69.4.6优优优优先先先先队队队队列列列
141、列的的的的应应应应用用用用HuffmanHuffmanHuffmanHuffman编编编编码码码码9.4.6.59.4.6.5HuffmanHuffmanHuffmanHuffman编编编编码码码码问问问问题题题题的的的的解解解解决决决决( (续续续续) )(1)(1)问问问问题题题题解解解解的的的的贪贪贪贪心心心心选选选选择择择择性性性性质质质质：设设设设x x和和和和y y是是是是C C 中中中中具具具具有有有有最最最最小小小小频频频频度度度度的的的的两两两两个个个个字字字字符符符符，则则则则存存存存在在在在C C的的的的 一一一一个个个个最最最最优优优优前前前前缀缀缀缀码码码码使使使使x
142、 x和和和和y y具具具具有有有有最最最最长长长长的的的的相相相相同同同同码码码码 长长长长且且且且仅仅仅仅最最最最后后后后一一一一位位位位编编编编码码码码不不不不同同同同，即即即即x x和和和和y y是是是是编编编编码码码码 树树树树中中中中最最最最深深深深的的的的一一一一对对对对叶叶叶叶结结结结点点点点兄兄兄兄弟弟弟弟。 证证证证明明明明：99999.49.4优优优优先先先先队队队队列列列列9.4.69.4.6优优优优先先先先队队队队列列列列的的的的应应应应用用用用HuffmanHuffmanHuffmanHuffman编编编编码码码码9.4.6.59.4.6.5HuffmanHuffma
143、nHuffmanHuffman编编编编码码码码问问问问题题题题的的的的解解解解决决决决（续续续续） (2)(2)问问问问题题题题解解解解的的的的最最最最优优优优子子子子结结结结构构构构性性性性质质质质：设设设设x x和和和和y y是是是是C C的的的的最最最最优优优优编编编编码码码码树树树树T T中中中中的的的的两两两两个个个个叶叶叶叶子子子子且且且且为为为为兄兄兄兄弟弟弟弟，z z是是是是它它它它们们们们的的的的父父父父亲亲亲亲。若若若若将将将将z z看看看看作作作作是是是是具具具具有有有有频频频频率率率率f(z)=f(x)f(z)=f(x)+f(y)+f(y)的的的的字字字字符符符符，则则
144、则则树树树树 T=T-T=T-x,yx,y表表表表示示示示字字字字符符符符集集集集C=C-C=C-x,yx,yz z的的的的最最最最优优优优编编编编码码码码树树树树。证证证证明明明明：1001009.49.4优优优优先先先先队队队队列列列列9.4.69.4.6优优优优先先先先队队队队列列列列的的的的应应应应用用用用HuffmanHuffmanHuffmanHuffman编编编编码码码码9.4.6.59.4.6.5HuffmanHuffmanHuffmanHuffman编编编编码码码码问问问问题题题题的的的的解解解解决决决决(3)(3)HuffmanHuffmanHuffmanHuffman编编
145、编编码码码码和和和和解解解解码码码码的的的的简简简简洁洁洁洁实实实实现现现现从从从从算算算算法法法法的的的的动动动动画画画画演演演演示示示示中中中中已已已已经经经经看看看看到到到到了了了了HuffmanHuffmanHuffmanHuffman编编编编码码码码和和和和解解解解码码码码的的的的一一一一种种种种实实实实现现现现方方方方式式式式。它它它它们们们们的的的的简简简简洁洁洁洁表表表表述述述述作作作作为为为为练练练练习习习习。1011019.69.6并并并并查查查查集集集集9.6.19.6.1并并并并查查查查集集集集的的的的定定定定义义义义及及及及其其其其简简简简单单单单实实实实现现现现在在
146、一一些些应应用用问问题题中中，需需将将n n个个不不同同的的元元素素划划分分成成一一组组不不相相交交的的集集合合。开开始始时时，每每个个元元素素自自成成一一个个单单元元素素集集合合，然然后后按按一一定定顺顺序序将将属属于于同同一一组组元元素素的的集集合合合合并并。其其间间要要反反复复用用到到查查询询某某个个元元素素属属于于哪哪个个集集合合的的运运算算。适适合合于于描描述述这这类类问问题题的的抽抽象象数数据据类类型型称称为为并并查查集集。它它的的数数学学模模型型是是一一组组不不相相交交的的动动态态集集合合的的集集合合S=AS=A，B B，C C， ，它它支支持持以以下下的的运运算算：(1)Uni
147、on(A(1)Union(A，B)B)：将将集集合合A A和和B B合合并并，其其结结果果取取名名为为A A或或B B；(2)Find(x)(2)Find(x)：找找出出包包含含元元素素x x的的集集合合，并并返返回回该该集集合合的的名名字字。并并查查集集的的一一个个应应用用是是确确定定集集合合上上的的等等价价关关系系。 1021029.69.6并并并并查查查查集集集集9.6.29.6.2用用用用数数数数组组组组实实实实现现现现并并并并查查查查集集集集classclassUnionFindUnionFind public:public:UnionFind(intUnionFind(intsiz
148、e);size);UnionFindUnionFind()deleteComponents;()deleteComponents;intintFind(intFind(inte);e);voidvoidUnion(intUnion(inti,intj);i,intj);private:private:int*Components;int*Components;intn;intn;其其中中：n n是是集集合合中中元元素素的的个个数数。ComponentsComponents是是表表示示元元素素及及其其所所属属子子集集关关系系的的数数组组，ComponentsxComponentsx 表表示示元元
149、素素x x当当前前所所属属的的集集合合的的名名字字。 1031039.69.6并并并并查查查查集集集集9.6.39.6.3用用用用父父父父亲亲亲亲数数数数组组组组实实实实现现现现并并并并查查查查集集集集采采用用树树结结构构实实现现并并查查集集的的基基本本思思想想是是，每每个个集集合合用用一一棵棵树树来来表表示示。树树的的结结点点用用于于存存储储集集合合中中的的元元素素名名。每每个个树树结结点点还还存存放放一一个个指指向向其其父父结结点点的的指指针针。树树根根结结点点处处的的元元素素代代表表该该树树所所表表示示的的集集合合。利利用用映映射射可可以以找找到到集集合合中中元元素素所所对对应应的的树树
150、结结点点。父父亲亲数数组组是是实实现现上上述述树树结结构构的的有有效效方方法法。 classclassUnionFindUnionFind public:public:UnionFind(intUnionFind(intn);n);UnionFindUnionFind()deleteparent;()deleteparent;intintFind(intFind(inte);e);voidvoidUnion(intUnion(inti,intj);i,intj);private:private:int*parent;int*parent;其其中中parentparent是是表表示示树树结结构构
151、的的父父亲亲数数组组。元元素素x x的的父父结结点点为为parentxparentx 。 1041049.69.6并并并并查查查查集集集集9.6.39.6.3用用用用父父父父亲亲亲亲数数数数组组组组实实实实现现现现并并并并查查查查集集集集Find(eFind(e) )运运算算就就是是从从元元素素e e相相应应的的结结点点走走到到树树根根处处，找找出出所所在在集集合合的的名名字字。 intintUnionFind:Find(intUnionFind:Find(inte)e) while(while(parenteparente)e=)e=parenteparente; ;returne;retu
152、rne; 合合并并2 2个个集集合合，只只要要将将表表示示其其中中一一个个集集合合的的树树的的树树根根改改为为表表示示另另一一个个集集合合的的树树的的树树根根的的儿儿子子。 voidvoidUnionFind:Union(intUnionFind:Union(inti,intj)i,intj) parentjparentj=i;=i; 容容易易看看出出，在在最最坏坏情情况况下下，合合并并可可能能使使n n个个结结点点的的树树退退化化成成一一条条链链。在在这这种种情情况况下下对对所所有有元元素素各各执执行行一一次次FindFind将将耗耗时时O(nO(n2 2) )。如如何何改改进进？10510
153、59.69.6并并并并查查查查集集集集9.6.39.6.3用用用用父父父父亲亲亲亲数数数数组组组组实实实实现现现现并并并并查查查查集集集集改改进进办办法法：l l在在树树根根中中保保存存该该树树的的结结点点数数，每每次次合合并并时时总总是是将将小小树树合合并并到到大大树树上上去去。当当一一个个结结点点从从一一棵棵树树移移到到另另一一棵棵树树上上去去时时，这这个个结结点点到到树树根根的的距距离离就就增增加加1 1，而而这这个个结结点点所所在在的的树树的的大大小小至至少少增增加加一一倍倍。于于是是并并查查集集中中每每个个结结点点至至多多被被移移动动O(lognO(logn) )次次，从从而而每每个
154、个结结点点到到树树根根的的距距离离不不会会超超过过O(lognO(logn) )。所所以以每每次次FindFind运运算算只只需需要要O(lognO(logn) )时时间间。 l l采采用用路路径径压压缩缩技技术术 在在执执行行FindFind时时，实实际际上上找找到到了了从从一一个个结结点点到到树树根根的的一一条条路路径径。路路径径压压缩缩就就是是把把这这条条路路上上的的所所有有结结点点都都改改为为树树根根的的儿儿子子。实实现现路路径径压压缩缩的的最最简简单单的的方方法法是是在在这这条条路路上上走走2 2次次，第第1 1次次找找到到树树根根，第第2 2次次将将路路上上所所有有结结点点的的父父结结点点都都改改为为树树根根。 路路径径压压缩缩并并不不影影响响UnionUnion运运算算的的时时间间，它它仍仍然然只只要要O(1)O(1)时时间间。但但是是路路径径压压缩缩大大大大地地加加速速了了FindFind运运算算。
