【数据结构讲解】集合和搜索

1、 集合运算的文氏集合运算的文氏(Venn)图图 Template class Set Set ( int MaxSetSize ) : MaxSize ( MaxSetSize ); void MakeEmpty ( Set int AddMember ( Set int DelMember ( Set void Assign ( Set void Union ( Set void Intersection ( Set void Difference ( Set int Contains ( Set int Equal ( Set int SubSet ( Set #include const

2、 int DefaultSize = 100; class Set private: int * bitVector; int MaxSize; public: Set ( int MaxSetSize = DefaultSize ); Set ( ) delete bitVector; void MakeEmpty ( ) for ( int i = 0; i MaxSize; i+ ) bitVectori = 0; int AddMember ( const int x ); int DelMember ( const int x ); Set Set Set Set int Conta

3、ins ( const int x ); int SubSet ( Set int operator = ( Set ; 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的交的交

4、7, 8, 9 s5 = s1 - s2; /求求s1与与s2的差的差 0, 1, 2, 3, 4, 5, 6 index = s1.SubSet ( s4 ); /求求s4在在s1中首次匹配中首次匹配 cout index endl; /位置位置， index = 7 equal = s1 = s2; /集合集合s1与与s2比较相等比较相等 cout equal 0 ); bitVector = new int MaxSize; assert ( bitVector != 0 ); for ( int i = 0; i = 0 if ( bitVectorx ) bitVectorx = 0

5、; return 1; return 0; Set for ( int i =0; i MaxSize; i+ ) bitVectori = right.bitVectori; return *this; Set for ( int i = 0; i MaxSize; i+ ) bitVectori = bitVectori | right.bitVectori; return *this; Set for ( int i = 0; i MaxSize; i+) bitVectori = bitVectori return *this; Set for ( int i = 0; i = 0 r

6、eturn bitVectorx; int Set : operator = ( Set for ( int i = 0; i MaxSize; i+) if ( bitVectori != right.bitVectori ) return 0; return 1; int Set : SubSet (Set for ( int i = 0; i MaxSize; i+) if (bitVectori return 1; template class SetList; template class SetNode friend class SetList; public: SetNode (

7、const Type private: Type data; SetNode *link; ; template class SetList private: SetNode *first, *last; public: SetList ( ); void MakeEmpty ( ); int AddMember ( const Type int DelMember ( const Type SetList SetList SetList SetList int Contains ( const Type int operator = ( SetList Type Type template

8、void SetList : SetList ( ) SetNode *first = *last = new SetNode(0); template int SetList : Contains (const Type while ( temp != NULL if (temp != NULL else return 0; template int SetList : AddMember ( const Type while ( p != NULL p = plink; if ( p != NULL SetNode *s = new SetNode (x); slink = p; qlin

9、k = s; if ( p = NULL ) last = s; return 1; template int SetList : DelMember ( const Type while ( p != NULL p = plink; if ( p != NULL if ( p = last ) last = q; delete p; return 1; else return 0; template SetList SetNode*pa = first = new SetNode; while ( pb != NULL ) palink = new SetNode (pbdata); pa

10、= palink; pb = pblink; palink = NULL; last = pa; return *this; template SetList SetNode *pa = firstlink; SetNode *pc = first; while ( pa != NULL pa = palink; pb = pblink; else if ( padata pbdata ) pclink = pa; pa = palink; else pclink = new SetNode (pbdata); pb = pblink; pc = pclink; if ( pa != NULL

11、 ) pclink = pa; else while ( pb != NULL ) pclink = new SetNode (pbdata); pc = pclink; pb = pblink; pclink = NULL; last = pc; return *this; template SetList SetNode *pa = firstlink; SetNode *pc = first; while ( pa != NULL pa = palink; pb = pblink; else if ( padata pbdata ) pclink = palink; delete pa;

12、 pa = pclink; else pb = pblink; while ( pa != NULL ) pclink = palink; delete pa; pa = pclink; last = pc; return *this; template SetList SetNode *pa = firstlink; SetNode *pc = first; while ( pa != NULL delete pa; pa = pclink; pb = pblink; else if ( padata pbdata ) pc = pclink; pa = palink; else pb =

13、pblink; if ( pa = NULL ) last = pc; return *this; template int SetList : operator = ( SetList SetNode *pa = firstlink; while ( pa != NULL pb = pblink; else return 0; if ( pa != NULL | pb != NULL ) return 0; return 1; void equivalence ( ) 初始化初始化; while 等价对未处理完等价对未处理完 读入下一个等价对读入下一个等价对 ( i, j ); 存储这个等价

14、对存储这个等价对 ; 输出初始化输出初始化; for ( 尚未输出的每个对象尚未输出的每个对象 ) 输出包含这个对象的等价类输出包含这个对象的等价类 ; 0,1,2,3,4,5,6,7,8,9, 10,11 0,4,1,2,3,5,6,7,8,9,10,11 0,4, 1,3,2,5,6,7,8,9,10,11 0,4,1,3,2,5,6,10,7,8,9,11 0,4,1,3,2,5,6,10,7,8,9,11 0,4,7,1,3,2,5,6,10,8,9,11 0,4,7,1,3,2,5,6,8,9,10,11 0,4,7,1,3,5,2,6,8,9,10,11 0,4,7,1,3,5,2

15、,11,6,8,9,10 0,2,4,7,11,1,3,5,6,8,9,10 void equivalence ( ) 读入读入 n; 将将 seq 初始化为初始化为 0 且将且将 out 初始化为初始化为 False; while等价对未处理完等价对未处理完 读入下一个等价对读入下一个等价对( i, j ); 将将 j 链入链入 seqi链表链表; 将将 i 链入链入 seqj链表链表; for ( i = 0; i n; i+ ) /检测所有对象检测所有对象 if ( outi = False ) /若对象若对象i未输出未输出 outi = True; /对象对象i做输出标志做输出标志 输

16、出包含对象输出包含对象 i 的等价类的等价类; 链链 序序号号 等等价价 对对 OUT 初初态态 输输 出出 OUT 终终态态 栈栈 0False 0 True 0 11 False 11 True 11 0 4 False 4 True 11,4 4 7 False 7 True 11,7 4 0 True True 11,7 链链 序序号号 等等价价 对对 OUT 初初态态 输输 出出 OUT 终终态态 栈栈 7 4 True True 11 11 0 True True 11 0 True True 11 2 False 2 True 2 2 11 True True enum Bool

17、ean False, True ; class ListNode /定义链表结点类定义链表结点类 friend void equivalence ( ); private: int data;/结点数据结点数据 ListNode *link;/结点链指针结点链指针 ListNode ( int d ) data = d; link = NULL; ; typedef ListNode *ListNodePtr; void equivalence ( ) ifstream inFile ( equiv.in, ios:in ); /输入文件输入文件 if ( !inFile ) cout “不能

18、打开输入文件不能打开输入文件 n; /读入对象个数读入对象个数 seq = new ListNodePtrn; out = new Booleann; /初始化初始化seq和和out for (i = 0; i i j; /输入等价对输入等价对 ( i, j ) while ( inFile.good ( ) ) /输入文件结束转出循环输入文件结束转出循环 x = new ListNode ( j ); /创建结点创建结点 j xlink = seqi; seqi = x; /链入第链入第i个链表个链表 y = new ListNode ( i ); /创建结点创建结点i ylink = se

19、qj; seqj = y; /链入第链入第j个链表个链表 inFile i j;/输入下一个等价对输入下一个等价对 for ( i = 0; i n; i+ ) if ( outi = False ) /未输出未输出, 需要输出需要输出 cout endl “A new class: ” i; /输出输出 outi = True; /作输出标记作输出标记 ListNode *x = seqi; /取第取第i链表头指针链表头指针 ListNode *top = NULL; /栈初始化栈初始化 while (1) /找类的其它成员找类的其它成员 while ( x ) /处理链表处理链表,直到直到

20、 x=0 j = xdata; /成员成员j if ( outj = False ) /未输出未输出, 输出输出 cout “,” j; outj=True; ListNode *y = xlink; xlink = top; top = x; /结点结点x进栈进栈 x = y;/x进到链表下一个结点进到链表下一个结点 else x = xlink; /已输出过已输出过,跳过跳过 if ( top = NULL ) break; /栈空退出循环栈空退出循环 else x = seqtopdata; top = toplink; /栈不空栈不空, 退栈退栈, x是根据结点编号回是根据结点编号回

21、/溯的另一个链表的头指针溯的另一个链表的头指针 delete seq; delete out; ； 。 。 parent - -1 4 - -1 2 - -1 2 0 0 0 4 0 1 2 3 4 5 6 7 8 9 const int DefaultSize = 10; class UFSets / public: UFSets ( int s = DefaultSize ); UFSets ( ) delete parent; const UFSets void Union ( int Root1, int Root2 ); int Find ( int x ); void UnionB

22、yHeight ( int Root1, int Root2 ); private: int *parent; int size; ; UFSets : UFSets ( int s ) / size = s; parent = new int size+1; for ( int i = 0; i = size; i+ ) parenti = -1; unsigned int UFSets : Find ( int x ) /搜索操作搜索操作 if ( parentx = 0 ) return x; else return Find ( parentx ); void UFSets : Uni

23、on ( int Root1, int Root2 ) /并并 parentRoot2 = Root1; /Root2指向指向Root1 n i ni 1 2 OO)()( parent0(= - -4) parent4 (= - -3) void UFSets : WeightedUnion ( int Root1, int Root2 ) Union int temp = parentRoot1 + parentRoot2; if ( parentRoot2 = 0; j = parentj); /让让 j 循双亲指针走到根循双亲指针走到根 while ( i != j ) /换换 par

24、enti 到到 j int temp = parenti; parenti = j; i = temp; return j; template class dataList; template class Node friend class dataList; public: Node ( const Type void setKey ( Type k ) key = k; private: Type key; other; ; template class dataList public: dataList ( int sz = 10 ) : ArraySize (sz), Element

25、(new Node sz) virtual dataList ( ) delete Element; friend ostream friend istream protected: Type *Element; int ArraySize, CurrentSize; ; template class searchList : public dataList / public: searchList ( int sz = 10 ) : dataList (sz) virtual searchList ( ) virtual int Search ( const Type ; template

26、istream cout “ : n”; for ( int i = 0; i InList.CurrentSize; i+ ) cout “ ” i InList.Elementi; return InStream; template ostream for ( int i = 0; i OutList.CurrentSize; i+ ) OutStream OutList.Elementi ; OutStream endl; OutStream “ : ” OutList.CurrentSize endl; return OutStream; template int searchList

27、 : Search ( const Type int i = CurrentSize; while (Elementi.getKey ( ) != x ) i -; return i; template int earchList : Search ( const Type else if ( Elementloc.getKey( ) = x ) return loc; else return Search ( x, loc+1 ); const int Size = 10; main ( ) / searchList List1 (Size); float Target; int Locat

28、ion; cin List1; cout List1; /List1 cout Target; if ( ( Location = List1.search (Target ) ) != 0 ) cout “ 找到下标找到下标 ” Location endl; else cout “ 没有找到没有找到.n”; 1 0 1 0 n i i n i iisucc pcpASL) 1 ( . )(1 1 0 ipASL n i isucc . )( )( 1 0 2 1 2 11 1 1 n i succ nnn n i n ASL 搜索成功的例子搜索成功的例子 搜索失败的例子搜索失败的例子 tem

29、plate class orderedList : public dataList / public: orderedList (int sz = 10) : dataList (sz) virtual orderedList ( ) virtual int Search ( const Type ; template int orderedList : BinarySearch ( const Type if ( low = high ) mid = ( low + high ) / 2; if ( Elementmid.getKey( ) x ) mid = BinarySearch (

30、x, low, mid -1 ); return mid; template in orderedList : BinarySearch ( const Type while ( low = high ) mid = ( low + high ) / 2; if ( Elementmid.getKey ( ) x ) high = mid - 1; else return mid; return -1; 搜索成功的情形搜索成功的情形 搜索不成功的情形搜索不成功的情形 )22)1( 23 2211 ( 11 122 1 1 0 1 0 hh n i i n i iisucc hh n C n C

31、PASL 12) 1( 22) 1( 232211 1221 h hh h hh 1) 1(log1) 1(log 1 ) 1(log) 1( 1 ) 12) 1( 1 22 2 nn n n nnn n h n ASL h succ 定义定义 #include template class BST; 几个二叉搜索树的例子几个二叉搜索树的例子 template Class BstNode : public BinTreeNode / friend class BST ; public: BstNode ( ) : leftChild (NULL), rightChild (NULL) BstN

32、ode ( const Type d ) : data (d), leftChild (NULL), rightChild (NULL) BstNode ( const Type d = 0, BstNode *L = NULL, BstNode *R = NULL) : data (d), leftChild (L), rightChild (R) BstNode ( ) protected: Type data; BstNode *leftChild, *rightChild; ; template class BST : public : BinaryTree private: BstN

33、ode *root; / Type RefValue; / BstNode *lastfound; / void MakeEmpty ( BstNode * void Insert ( const Type / void Remove ( const Type / void PrintTree ( BstNode *ptr ) const; BstNode *Copy (const BstNode *ptr ); / BstNode *Find (const Type / BstNode *Min ( BstNode * ptr ) const; / BstNode *Max ( BstNod

34、e * ptr ) const; / friend class BSTIterator; / public: BST ( ) : root (NULL) BST ( Type value ) : RefValue (value), root (NULL) BST ( ); const BST void MakeEmpty ( ) MakeEmpty ( ); root = NULL; void PrintTree ( ) const PrintTree ( root ); int Find ( const Type Type Min ( ) return Min ( root )data ;

35、Type Max ( ) return Max ( root )data ; void Insert ( const Type void Remove ( const Type template BstNode * BST : Find (const Type / else if ( x ptrdata ) / return Find ( x, ptrrightChild ); else return ptr; / template BstNode * BST : Find (const Type while ( temp != NULL ) if ( tempdata = x ) retur

36、n temp; / if ( tempdata x ) temp = temprightChild; / else temp = templeftChild; / return NULL; / 二叉搜索树的搜索二叉搜索树的搜索 插入新结点插入新结点88 template void BST: Insert (const Type / if ( ptr = NULL ) cout Out of space endl; exit (1); else if ( x ptrdata ) / Insert ( x, ptrrightChild ); template BST : BST ( Type va

37、lue ) Type root = NULL; RefValue = value; cin x; while ( x.key != RefValue ) Insert ( x, root ); cin x; 1 2 3 1 11 1 3 22 2 3 3 2 3 template void BST : Remove (const Type if ( ptr != NULL ) if ( x ptrdata ) Remove ( x, ptrrightChild ); else if ( ptrleftChild != NULL ptrdata = tempdata; Remove ( ptrd

38、ata, temp ); else temp = ptr; if ( ptrleftChild = NULL ) ptr = ptrrightChild; else if ( ptrrightChild = NULL ) ptr = ptrleftChild; delete temp; template class InorderIterator public: InorderIterator ( BST int Init ( ); / int operator ! ( ); / Type operator ( ) ( ); / int operator + ( ); / private: B

39、ST / Stack BstNode * itrStack; / template int InorderIterator : Init ( ) itrStack.MakeEmpty ( ); /迭代栈置空迭代栈置空 if ( ref.root != NULL ) /树非空树非空,根进栈根进栈 itrStack.Push ( ref.root ); return ! itrStack.IsEmpty ( ); /栈空返回栈空返回0 template int InorderIterator : operator ! ( ) return ! itrStack.IsEmpty ( ); /栈空返回

40、栈空返回0 template int InorderIterator : operator + ( ) BstNode * current = itrStack.GetTop ( ); BstNode * next = currentleftChild; if ( next != NULL ) /栈顶元素左子女进栈栈顶元素左子女进栈 itrStack.Push ( next ); return 1; while ( ! itrStack.IsEmpty ( ) ) /栈非空时循环栈非空时循环 current = itrStack.Pop ( ); next = currentrightChil

41、d; if ( next != NULL ) /右子女非空右子女非空 itrStack.Push ( next ); return 1; /进栈进栈 return 0; template Type InorderIterator : operator ( ) ( ) BstNode * current = itrStack.GetTop ( ); return currentdata; /返回栈顶元素值返回栈顶元素值 template BST : BST (const BST for ( itr.init ( ); ! itr; itr+ ) Insert ( itr ( ) ); templ

42、ate BST : BST ( ) MakeEmpty ( ); /二叉搜索树析构函数二叉搜索树析构函数 C n n n 2 1 1 (b) (d) (a) (c) ).(*1p 1 i liASL n i succ n j unsucc jljASL 0 q. * ASL = ASLsucc + ASLunsucc n i n j ji 10 qp1 . n i succ iASL 1 2 1log . 1n ni unsucc iASL 2 1 2 log n j n i nCjljiliASL 01 0q1p *)(* 关键码集合关键码集合 key1 key2 key3 实实 例例 do

43、 if to 对应对应 内部结点内部结点 p1=50 p2=10 p3=5 权值权值 外部结点外部结点 q0=15 q1=10 q2=5 q3=5 C 150 190 215 W 100 100 100 R 1 2 3 左子树左子树 T0,0 T0,1 T0,2 右子树右子树 T1,3 T2,3 T3,3 0 0 75 115 150 1 0 25 50 2 0 15 3 0 0 15 75 90 100 1 10 25 35 2 5 15 3 5 WijCij Rij 3个关键码个关键码 do, if, to 的的 最优二叉搜索树最优二叉搜索树 0 1 2 30 1 2 3 0 1 2 3

44、0 0 1 1 1 1 0 2 2 2 0 3 3 0 p1=50, p2=10, p3=5 q0=15, q1=10, q2= 5, q3= 5 template class AVLTree public: struct AVLNode Type data; AVLNode *left, *right; int balance; AVLNode ( ) : left (NULL), right (NULL), balance (0) AVLNode ( Type d, AVLNode *l = NULL, AVLNode *r = NULL ) : data (d), left (l), r

45、ight (r), balance (0) ; protected: Type RefValue; AVLNode *root; int Insert ( AVLNode* void RotateLeft ( AVLNode *Tree, AVLNode * void RotateRight ( AVLNode *Tree, AVLNode * void LeftBalance ( AVLNode * void RightBalance ( AVLNode * int Depth ( AVLNode *t ) const; public: AVLTree ( ) : root (NULL) A

46、VLNode ( Type Ref ) : RefValue (Ref), root (NULL) int Insert ( Type x ) int taller; return Insert ( root, x, taller ); friend istream friend ostream int Depth ( ) const; h hh A C E B D (a) (b) (c) h h h + 1 B A C E D hh h + 1 C EA B D template void AVLTree : RotateLeft ( AVLNode *Tree, AVLNode * Tre

47、eright = NewTreeleft; NewTreeleft = Tree; h hh A C E B D (a) (b) (c) h h + 1 B A C ED hh h + 1 CE A B D h template void AVLTree: RotateRight ( AVLNode *Tree, AVLNode * Treeleft = NewTreeright; NewTreeright = Tree; 插入插入 template void AVLTree: LeftBalance ( AVLNode * switch ( leftsubbalance ) case -1

48、: Treebalance = leftsubbalance = 0; RotateRight ( Tree, Tree ); taller = 0; break; case 0 : cout “.n; break; case 1 : rightsub = leftsubright; switch ( rightsubbalance ) case -1: Treebalance = 1; leftsubbalance = 0; break; case 0 : Treebalance = leftsubbalance = 0; break; case 1 : Treebalance = 0; l

49、eftsubbalance = -1; break; rightsubbalance = 0; RotateLeft ( leftsub, Treeleft ); RotateRight ( Tree, Tree ); taller = 0; template void AVLTree: RightBalance ( AVLNode * switch ( rightsubbalance ) case 1 : Treebalance = rightsubbalance = 0; RotateLeft ( Tree, Tree ); taller = 0; break; case 0 : cout “.n; break; case -1 : leftsub = rightsubleft; switch ( leftsubbalance ) case 1 : Treebalance = -1; rightsubbalance = 0; break; case 0 : Treebalance = rightsubbalance = 0; break; case -1 : Treebalance = 0; rightsubbalance = 1; break; leftsubbalance = 0; RotateRight ( rightsub, Treele