【正文】 ize = 10。 ? 在 雙親表示 中， 第 i 個(gè)數(shù)組元素代表包含集合元素 i 的樹(shù)結(jié)點(diǎn) 。 存儲(chǔ)這個(gè)等價(jià)對(duì) 。 ? 因此，等價(jià)關(guān)系是集合上的一個(gè)自反、對(duì)稱、傳遞的關(guān)系。 } else return 0。 //鏈表收尾 return temp。 pb = pblink。 while ( pa != NULL amp。 } palink = NULL。 return 1。amp。 //集合中已有此元素 SetNodeType * s = new SetNode (x)。 x ) { SetNodeType *p = firstlink, *q = first。 while ( temp != NULL amp。 //返回集合最大元素值 } 集合的復(fù)制構(gòu)造函數(shù) template class Type SetListType :: SetList ( SetList Type amp。 //求集合 this與集合 right的差 int Contains ( const Typeamp。 void operator = ( SetListTypeamp。 right )。 public: SetNode ( ) : link(NULL) { }。 ! [i]) return 0。 i++) if ( bitVector[i] != [i] ) return 0。 i++ ) temp. bitVector[i] = bitVector[i] amp。amp。 i++ ) [i] = bitVector[i] || [i]。amp。 return 1。 } int Set :: Addmember ( const int x ) { if ( x = 0 amp。 i++ ) //置空集合 bitVector[i] = 0。 //判斷 s1是否為 s4子集 cout index endl。 for ( int k = 0。 //差 int Contains ( const int x )。 //刪 Set operator = ( Setamp。 } void MakeEmpty ( ) { //置空 for ( int i = 0。 ? 當(dāng)全集合是由有限的可枚舉的成員組成的集合時(shí)，可建立全集合成員與整數(shù) 0, 1, 2, … 的一一對(duì)應(yīng)關(guān)系，用位向量來(lái)表示該集合的子集。 x)。 Set Intersection (Setamp。 s, const Typeamp。 ? 整數(shù)、字符和字符串都有一個(gè)自然線性順序。集合中的成員可以是原子 (單元素 )，也可以是集合。 void MakeEmpty (Setamp。 s1, Setamp。 Set Difference (Setamp。 s2)。 //集合的位向量數(shù)組 int MaxSize。 } int GetMember ( const int x ) { //提取 return x = 0 amp。 right )。 //判子集 int operator == ( Setamp。 ( k +7 )。 //為 0, 兩集合不等 用位向量實(shí)現(xiàn)集合時(shí)部分操作的實(shí)現(xiàn) Set :: Set (int MaxSetSize) : MaxSize (MaxSetSize) { assert ( MaxSize 0 )。 //位向量大小 bitVector = new int [MaxSize]。 return 1。 right ) { //賦值 assert ( MaxSize == )。 } Set Set :: operator + ( Setamp。 right ) { //求交 assert ( MaxSize == )。 } this right temp 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 Set Set :: operator ( Set amp。 return temp。 right ) { //判斷 this 是否是 right 的子集 assert ( MaxSize == )。 ? 各結(jié)點(diǎn)所表示的成員 e0, e1, …, en 在鏈表中按升序排列，即 e0 e1 … en。 SetNodeType * link。 } void MakeEmpty ( )。 right )。 right )。 while ( srcptr != NULL ) { last = lastlink = new SetNodeType (srcptrdata)。 //循鏈搜索 if ( temp != NULL amp。 pdata x ) { q = p。 //鏈入 if ( p == NULL ) last = s。 } //循鏈掃描 if ( p != NULL amp。 right ) { //復(fù)制集合 right到 this SetNodeType * pb = link。 template class Type SetListType SetListType :: operator + ( SetListTypeamp。 pa = palink。 //pb指未掃完集合 while ( pb != NULL ) { //向結(jié)果鏈逐個(gè)復(fù)制 pclink = new SetNodeType(pbdata)。 SetNodeType * pa = firstlink。 } 等價(jià)關(guān)系與等價(jià)類 (Equivalence Class) 等價(jià)類與并查集 ? 在求解實(shí)際應(yīng)用問(wèn)題時(shí)常會(huì)遇到等價(jià)類問(wèn)題。 這些子集即為等價(jià)類 。 } 給定集合 S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }, 及如下等價(jià)對(duì) : 0 ? 4, 3 ? 1, 6 ? 10, 8 ? 9, 7 ? 4, 6 ? 8, 3 ? 5, 2 ? 11, 11 ? 0 。 ? 為此，需要有兩個(gè)映射： ? 集合元素到存放該元素名的樹(shù)結(jié)點(diǎn)間的對(duì)應(yīng)； ? 集合名到表示該集合的樹(shù)的根結(jié)點(diǎn)間的對(duì)應(yīng)。 //集合元素的數(shù)目 public: UFSets ( int s = DefaultSize )。 //改進(jìn)例程 : 壓縮高度的合并算法 }。 } 5 0 1 2 3 parent Parent[4] =3 Parent[3] =2 Parent[2] =1 Parent[1] =0 Parent[0] =5 0 1 2 3 4 void UFSets :: Union ( int Root1, int Root2 ) { //求兩個(gè)不相交集合 Root1與 Root2的并 parent[Root1] += parent[Root2]。 1 1 1 1 1 0 1 2 3 4 1 1 0 7 2 5 6 5 2 2 2 3 3 2 0 1 3 4 5 6 2 3 3 0 2 0 5 6 2 3 1 4 Union(2, 0) void UFSets :: WeightedUnion ( int Root1, int Root2 ) { //按 Union的加權(quán)規(guī)則改進(jìn)的算法 int temp = parent[Root1] + parent[Root2]。 0 0 6 7 8 6 7 8 1 9 1 9 3 5 3 5 從 i = 5 壓縮路徑 int UFSets :: CollapsingFind ( int i ) { //使用折疊規(guī)則的搜索算法 for ( int j = i。 ? 搜索的結(jié)果通常有兩種可能： ? 搜索成功 ，即找到滿足條件的數(shù)據(jù)對(duì)象 這時(shí) ,作為結(jié)果 , 可報(bào)告該對(duì)象在結(jié)構(gòu)中 的位置 , 還可給出該對(duì)象中的具體信息。 ? 實(shí)施搜索時(shí)有兩種不同的環(huán)境。 value ) : key (value) { } Type getKey ( ) const { return key。 } virtual ~dataList ( ) { delete [ ] Element。 InStream, dataListTypeamp。 InStream, dataListTypeamp。 } return InStream。 OutStream endl。 順序搜索 (Sequential Search) ? 所謂順序搜索 , 又稱線性搜索 , 主要用于在線性結(jié)構(gòu)中進(jìn)行搜索 。 //將 x送 CurrentSize號(hào)位置設(shè)監(jiān)視哨 while ( Element[i].key != x ) i++。 cout “搜索浮點(diǎn)數(shù) : ”。 //搜索失敗 else if ( Element[loc].key == x ) return loc。 //順序搜索失敗 , 返回失敗信息 } ? 有序順序表的順序搜索 ( 10, 20, 30, 40, 50, 60 ) 10 50 60 = = = = = = 20 30 40 ? ?27161 50??? ??is uc c iA SL? ?7276171 50?????????????iu n s u c ciA S L基于有序順序表的折半搜索 ? 設(shè) n個(gè)對(duì)象 存放在一個(gè)有序順序表中 ， 并按其關(guān)鍵碼 從小到大排好了序 。 if ( low = high ) { mid = ( low + high ) / 2。 //右縮搜索區(qū)間 else if ( Element[mid].key x ) high = mid 1。 …, 第 i (0 ≤ i ? h) 層結(jié)點(diǎn)有 2i 個(gè) , 搜索第 i 層結(jié)點(diǎn)要比較 i+1次， … 。 n 個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)的數(shù)目 【例】 3 個(gè)結(jié)點(diǎn)的二叉搜索樹(shù) ： 512345641C131 332 ???????? ?1 2 2 1 3 3 1 3 2 1 2 3 1 2 3 {123} {132} {213} {231} {312} {321} 二叉搜索樹(shù)的類定義 include template class Type class BST。 } ~BstNode ( ) { } //析構(gòu)函數(shù) }。 ptr )。 //析構(gòu)函數(shù) const BSTamp。 } Type Max ( ) { return Max ( root )data。 遞歸搜索根結(jié)點(diǎn)的右子樹(shù) 。 //右子樹(shù) else temp = templeftChild。 ptr) { if ( ptr == NULL ) {