第七章-集合与搜索-C++数据结构-教学课件.ppt

1、集合运算的文氏集合运算的文氏(Venn)图图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);void Assign(Set&s1,Set&s2);void Union(Set&s1,Set&s2);void Intersection(Set&s1,Set&s2);void Difference(Set&s1,Set&s2);int Contains

2、(Set&s,const Type&x);int Equal(Set&s1,Set&s2);int SubSet(Set&s1,Set&s2);#include const 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 Del

3、Member(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 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

4、);/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=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&

5、x=0&x MaxSize);if(bitVectorx)bitVectorx=0;return 1;return 0;Set&Set:operator=(Set&right)assert(MaxSize=right.MaxSize);for(int i=0;i MaxSize;i+)bitVectori=right.bitVectori;return*this;Set&Set:operator+(Set&right)assert(MaxSize=right.MaxSize);for(int i=0;i MaxSize;i+)bitVectori=bitVectori|right.bitVec

6、tori;return*this;Set&Set:operator*(Set&right)assert(MaxSize=right.MaxSize);for(int i=0;i MaxSize;i+)bitVectori=bitVectori&right.bitVectori;return*this;Set&Set:operator-(Set&right)assert(MaxSize=right.MaxSize);for(int i=0;i=0&x MaxSize);return bitVectorx;int Set:operator=(Set&right)assert(MaxSize=rig

7、ht.MaxSize);for(int i=0;i MaxSize;i+)if(bitVectori!=right.bitVectori)return 0;return 1;int Set:SubSet(Set&right)assert(MaxSize=right.MaxSize);for(int i=0;i MaxSize;i+)if(bitVectori&!right.bitVectori)return 0;return 1;template class SetList;template class SetNode friend class SetList;public:SetNode(c

8、onst Type&item):data(item),link(NULL);private:Type data;SetNode*link;template class SetList private:SetNode*first,*last;public:SetList();void MakeEmpty();int AddMember(const Type&x);int DelMember(const Type&x);SetList&operator=(SetList&right);SetList&operator+(SetList&right);SetList&operator*(SetLis

9、t&right);SetList&operator-(SetList&right);int Contains(const Type&x);int operator=(SetList&right);Type&Min();Type&Max();template void SetList:SetList()SetNode*first=*last=new SetNode(0);template int SetList:Contains(const Type&x)SetNode*temp=firstlink;while(temp!=NULL&tempdata x)temp=templink;if(tem

10、p!=NULL&tempdata=x)return 1;else return 0;template int SetList:AddMember(const Type&x)SetNode*p=firstlink,*q=first;while(p!=NULL&pdata x)q=p;p=plink;if(p!=NULL&pdata=x)return 0;SetNode*s=new SetNode(x);slink=p;qlink=s;if(p=NULL)last=s;return 1;template int SetList:DelMember(const Type&x)SetNode*p=fi

11、rstlink,*q=first;while(p!=NULL&pdata x)q=p;p=plink;if(p!=NULL&pdata=x)qlink=plink;if(p=last)last=q;delete p;return 1;else return 0;template SetList&SetList :operator=(SetList&right)SetNode*pb=right.firstlink;SetNode*pa=first=new SetNode;while(pb!=NULL)palink=new SetNode(pbdata);pa=palink;pb=pblink;p

12、alink=NULL;last=pa;return*this;template SetList&SetList:operator+(SetList&right)SetNode*pb=right.firstlink;SetNode*pa=firstlink;SetNode*pc=first;while(pa!=NULL&pb!=NULL)if(padata=pbdata)pclink=pa;pa=palink;pb=pblink;else if(padata pbdata)pclink=pa;pa=palink;else pclink=new SetNode(pbdata);pb=pblink;

13、pc=pclink;if(pa!=NULL)pclink=pa;else while(pb!=NULL)pclink=new SetNode(pbdata);pc=pclink;pb=pblink;pclink=NULL;last=pc;return*this;template SetList&SetList:operator*(SetList&right)SetNode*pb=right.firstlink;SetNode*pa=firstlink;SetNode*pc=first;while(pa!=NULL&pb!=NULL)if(padata=pbdata)pc=pclink;pa=p

14、alink;pb=pblink;else if(padata pbdata)pclink=palink;delete pa;pa=pclink;else pb=pblink;while(pa!=NULL)pclink=palink;delete pa;pa=pclink;last=pc;return*this;template SetList&SetList:operator-(SetList&right)SetNode*pb=right.firstlink;SetNode*pa=firstlink;SetNode*pc=first;while(pa!=NULL&pb!=NULL)if(pad

15、ata=pbdata)pclink=palink;delete pa;pa=pclink;pb=pblink;else if(padata pbdata)pc=pclink;pa=palink;else pb=pblink;if(pa=NULL)last=pc;return*this;template int SetList:operator=(SetList&right)SetNode*pb=right.firstlink;SetNode*pa=firstlink;while(pa!=NULL&pb!=NULL)if(padata=pbdata)pa=palink;pb=pblink;els

16、e return 0;if(pa!=NULL|pb!=NULL)return 0;return 1;void equivalence()初始化初始化;while 等价对未处理完等价对未处理完 读入下一个等价对读入下一个等价对(i,j);存储这个等价对存储这个等价对;输出初始化输出初始化;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,110,4,1,3,2,5,6,10,7,8,9,11 0,4,1

17、,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,110,4,7,1,3,5,2,11,6,8,9,100,2,4,7,11,1,3,5,6,8,9,10void equivalence()读入读入 n;将将 seq 初始化为初始化为 0 且将且将 out 初始化为初始化为 False;while等价对未处理完等价对未处理完 读入下一个等价对读入下一个等价对(i,j);将将 j 链入链入 seqi链表链表;将将 i 链入链入 seqj链表链表;for(i

18、=0;i n;i+)/检测所有对象检测所有对象 if(outi=False)/若对象若对象i未输出未输出 outi=True;/对象对象i做输出标志做输出标志 输出包含对象输出包含对象 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 T

19、rue 11 0 True True 11 2 False 2 True 2 2 11 True Trueenum Boolean 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);/输

20、入文件输入文件 if(!inFile)cout “不能打开输入文件不能打开输入文件 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=seqj;seqj=y;/链入第链入第

21、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)/处理链表处理链表,直到直到 x=0 j=xdata;/成员成员j if(outj=False)/未输出未输出,输出输出 cout “,”j

22、;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是根据结点编号回是根据结点编号回 /溯的另一个链表的头指针溯的另一个链表的头指针 delete seq;delete out;；。parent-1 4 -1 2 -1 2 0 0 0 40 1 2 3 4 5 6 7 8 9cons

23、t int DefaultSize=10;class UFSets /public:UFSets(int s=DefaultSize);UFSets()delete parent;const UFSets&operator=(UFSets const&Value);void Union(int Root1,int Root2);int Find(int x);void UnionByHeight(int Root1,int Root2);private:int*parent;int size;UFSets:UFSets(int s)/size=s;parent=new int size+1;f

24、or(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:Union(int Root1,int Root2)/并并 parentRoot2=Root1;/Root2指向指向Root1nini12OO)()(parent0(=-4)parent4(=-3)void UFSets:WeightedUnion(int Root1,int Root2)Unionint temp=parentRo

25、ot1+parentRoot2;if(parentRoot2=0;j=parentj);/让让 j 循双亲指针走到根循双亲指针走到根 while(i!=j)/换换 parenti 到到 j int temp=parenti;parenti=j;i=temp;return j;template class dataList;template class Node friend class dataList;public:Node(const Type&value):key(value)Type getKey()const return key;void setKey(Type k)key=k;p

26、rivate:Type key;other;template class dataList public:dataList(int sz=10):ArraySize(sz),Element(new Node sz)virtual dataList()delete Element;friend ostream&operator (ostream&OutStream,const dataList&OutList);friend istream&operator (istream&InStream,dataList&InList);protected:Type*Element;int ArraySi

27、ze,CurrentSize;template class searchList:public dataList/public:searchList(int sz=10):dataList(sz)virtual searchList()virtual int Search(const Type&x)const;template istream&operator (istream&InStream,dataList&InList)/从输入流对象从输入流对象InStream输入数据到数据表输入数据到数据表InList cout InList.CurrentSize;cout “:n”;for(in

28、t i=0;i InList.CurrentSize;i+)cout “”i InList.Elementi;return InStream;template ostream&operator(ostream&OutStream,const dataList&OutList)/将数据表将数据表OutList内容输出到输出流对象内容输出到输出流对象OutStream OutStream “:n”;for(int i=0;i OutList.CurrentSize;i+)OutStream OutList.Elementi ;OutStream endl;OutStream “:”OutList.

29、CurrentSize endl;return OutStream;template int searchList:Search(const Type&x)const/Element0.setKey(x);int i=CurrentSize;while(Elementi.getKey()!=x)i-;return i;template int earchList:Search(const Type&x,int&loc)const/if(loc=CurrentSize)return-1;else if(Elementloc.getKey()=x)return loc;else return Se

30、arch(x,loc+1);const int Size=10;main()/searchList List1(Size);float Target;int Location;cin List1;cout List1;/List1 cout Target;if(Location=List1.search(Target)!=0)cout “找到下标找到下标”Location endl;else cout “没有找到没有找到.n”;1010niiniiisuccpcpASL)1(.)(110ipASLniisucc.)()(102121111nisuccnnnninASL搜索成功的例子搜索成功的例

31、子 搜索失败的例子搜索失败的例子template class orderedList:public dataList /public:orderedList(int sz=10):dataList(sz)virtual orderedList()virtual int Search(const Type&x)const;template int orderedList:BinarySearch(const Type&x,const int low,const int high)const/int mid=-1;if(low=high)mid=(low+high)/2;if(Elementmid

32、.getKey()x)mid=BinarySearch(x,low,mid-1);return mid;template in orderedList:BinarySearch(const Type&x)const /int high=CurrentSize-1,low=0,mid;while(low=high)mid=(low+high)/2;if(Elementmid.getKey()x)high=mid-1;else return mid;return-1;搜索成功的情形搜索成功的情形 搜索不成功的情形搜索不成功的情形)22)1(23 2211(1112211010hhniiniiisu

33、cchhnCnCPASL12)1(22)1(2322111221hhhhhh1)1(log1)1(log1 )1(log)1(1)12)1(1 222nnnnnnnnhnASLhsucc定义定义#include template class BST;几个二叉搜索树的例子几个二叉搜索树的例子template Class BstNode:public BinTreeNode /friend class BST;public:BstNode():leftChild(NULL),rightChild(NULL)BstNode(const Type d):data(d),leftChild(NULL),

34、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:BstNode*root;/Type RefValue;/BstNode*lastfound;/void MakeEmpty(BstNode*&ptr);void Insert(con

35、st Type&x,BstNode*&ptr);/void Remove(const Type&x,BstNode*&ptr);/void PrintTree(BstNode*ptr)const;BstNode*Copy (const BstNode*ptr);/BstNode*Find(const Type&x,BstNode*ptr)const;/BstNode*Min(BstNode*ptr)const;/BstNode*Max(BstNode*ptr)const;/friend class BSTIterator;/public:BST():root(NULL)BST(Type val

36、ue):RefValue(value),root(NULL)BST();const BST&operator=(const BST&Value);void MakeEmpty()MakeEmpty();root=NULL;void PrintTree()const PrintTree(root);int Find(const Type&x)const return Find(x,root)!=NULL;Type Min()return Min(root)data;Type Max()return Max(root)data;void Insert(const Type&x)Insert(x,r

37、oot);void Remove(const Type&x)Remove(x,root);template BstNode*BST:Find (const Type&x,BstNode*ptr)const/if(ptr=NULL)return NULL;/else if(x ptrdata)/return Find(x,ptrrightChild);else return ptr;/template BstNode *BST :Find (const Type&x,BstNode*ptr)const/if(ptr!=NULL)BstNode*temp=ptr;while(temp!=NULL)

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

39、template BST:BST(Type value)Type&x;root=NULL;RefValue=value;cin x;while(x.key!=RefValue)Insert(x,root);cin x;123111132223323 template void BST:Remove(const Type&x,BstNode*&ptr)BstNode*temp;if(ptr!=NULL)if(x ptrdata)Remove(x,ptrrightChild);else if(ptrleftChild!=NULL&ptrrightChild!=NULL)temp=Min(ptrri

40、ghtChild);ptrdata=tempdata;Remove(ptrdata,temp);else temp=ptr;if(ptrleftChild=NULL)ptr=ptrrightChild;else if(ptrrightChild=NULL)ptr=ptrleftChild;delete temp;template class InorderIterator public:InorderIterator(BST&Tree):ref(Tree)Init();int Init();/int operator!();/Type operator()();/int operator+()

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

42、Iterator:operator+()BstNode*current=itrStack.GetTop();BstNode*next=currentleftChild;if(next!=NULL)/栈顶元素左子女进栈栈顶元素左子女进栈 itrStack.Push(next);return 1;while(!itrStack.IsEmpty()/栈非空时循环栈非空时循环 current=itrStack.Pop();next=currentrightChild;if(next!=NULL)/右子女非空右子女非空 itrStack.Push(next);return 1;/进栈进栈 return

43、0;template Type InorderIterator:operator()()BstNode*current=itrStack.GetTop();return currentdata;/返回栈顶元素值返回栈顶元素值template BST:BST(const BST&T):root(NULL)InorderIterator itr();for(itr.init();!itr;itr+)Insert(itr();template BST:BST()MakeEmpty();/二叉搜索树析构函数二叉搜索树析构函数Cnnn211(b)(d)(a)(c).(*1p1i liASLnisuccn

44、junsuccjljASL0q.*ASL=ASLsucc+ASLunsucc ninjji10qp1 .nisucciASL121log.1nniunsucciASL212log njninCjljiliASL010q1p *)(*关键码集合关键码集合 key1 key2 key3 实实 例例 do 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

45、0 0 75 115 1501 0 25 502 0 153 00 15 75 90 1001 10 25 352 5 153 5WijCijRij3个关键码个关键码 do,if,to 的的最优二叉搜索树最优二叉搜索树0 1 2 30 1 2 30 1 2 30 0 1 1 11 0 2 22 0 33 0 p1=50,p2=10,p3=5q0=15,q1=10,q2=5,q3=5 template class AVLTree public:struct AVLNode Type data;AVLNode*left,*right;int balance;AVLNode():left(NULL)

46、,right(NULL),balance(0)AVLNode(Type d,AVLNode*l=NULL,AVLNode*r=NULL):data(d),left(l),right(r),balance(0);protected:Type RefValue;AVLNode*root;int Insert(AVLNode*&tree,Type x,int&taller);void RotateLeft(AVLNode*Tree,AVLNode*&NewTree);void RotateRight(AVLNode*Tree,AVLNode*&NewTree);void LeftBalance(AV

47、LNode*&Tree,int&taller);void RightBalance(AVLNode*&Tree,int&taller);int Depth(AVLNode*t)const;public:AVLTree():root(NULL)AVLNode(Type Ref):RefValue(Ref),root(NULL)int Insert(Type x)int taller;return Insert(root,x,taller);friend istream&operator (istream&in,AVLTree&Tree);friend ostream&operator (ostr

48、eam&out,const AVLTree&Tree);int Depth()const;hhhACEBD(a)(b)(c)hhh+1BACEDhhh+1CEABDtemplate void AVLTree:RotateLeft(AVLNode*Tree,AVLNode*&NewTree)/NewTree=Treeright;Treeright=NewTreeleft;NewTreeleft=Tree;hhhACEBD(a)(b)(c)hh+1BACEDhhh+1CEABDhtemplate void AVLTree:RotateRight(AVLNode*Tree,AVLNode*&NewT

49、ree)/NewTree=Treeleft;Treeleft=NewTreeright;NewTreeright=Tree;插入插入template void AVLTree:LeftBalance(AVLNode*&Tree,int&taller)/AVLNode*leftsub=Treeleft,*rightsub;switch(leftsubbalance)case-1:Treebalance=leftsubbalance=0;RotateRight(Tree,Tree);taller=0;break;case 0:cout “.n;break;case 1:rightsub=lefts

50、ubright;switch(rightsubbalance)case-1:Treebalance=1;leftsubbalance=0;break;case 0:Treebalance=leftsubbalance=0;break;case 1:Treebalance=0;leftsubbalance=-1;break;rightsubbalance=0;RotateLeft(leftsub,Treeleft);RotateRight(Tree,Tree);taller=0;template void AVLTree:RightBalance(AVLNode*&Tree,int&taller