数据结构各种算法实现C++模板

1、数据结构各种算法实现(C+模板)目 录 TOC o 1-3 h z u HYPERLINK l _Toc208152380 1、顺序表 PAGEREF _Toc208152380 h 1 HYPERLINK l _Toc208152381 Seqlist.h PAGEREF _Toc208152381 h 1 HYPERLINK l _Toc208152382 Test.cpp PAGEREF _Toc208152382 h 6 HYPERLINK l _Toc208152383 2、单链表 PAGEREF _Toc208152383 h 8 HYPERLINK l _Toc208152384

2、 ListNode.h PAGEREF _Toc208152384 h 8 HYPERLINK l _Toc208152385 SingleList.h PAGEREF _Toc208152385 h 10 HYPERLINK l _Toc208152386 test.cpp PAGEREF _Toc208152386 h 20 HYPERLINK l _Toc208152387 3、双向链表 PAGEREF _Toc208152387 h 22 HYPERLINK l _Toc208152388 NodeList.h PAGEREF _Toc208152388 h 22 HYPERLINK

3、l _Toc208152389 DoubleList.h PAGEREF _Toc208152389 h 24 HYPERLINK l _Toc208152390 Test.cpp PAGEREF _Toc208152390 h 34 HYPERLINK l _Toc208152391 4、循环链表 PAGEREF _Toc208152391 h 36 HYPERLINK l _Toc208152392 ListNode.h PAGEREF _Toc208152392 h 36 HYPERLINK l _Toc208152393 CircularList.h PAGEREF _Toc20815

4、2393 h 37 HYPERLINK l _Toc208152394 Test.cpp PAGEREF _Toc208152394 h 47 HYPERLINK l _Toc208152395 5、顺序栈 PAGEREF _Toc208152395 h 49 HYPERLINK l _Toc208152396 SeqStack.h PAGEREF _Toc208152396 h 49 HYPERLINK l _Toc208152397 Test.cpp PAGEREF _Toc208152397 h 54 HYPERLINK l _Toc208152398 6、链式栈 PAGEREF _To

5、c208152398 h 55 HYPERLINK l _Toc208152399 StackNode.h PAGEREF _Toc208152399 h 55 HYPERLINK l _Toc208152400 LinkStack.h PAGEREF _Toc208152400 h 56 HYPERLINK l _Toc208152401 Test.cpp PAGEREF _Toc208152401 h 60 HYPERLINK l _Toc208152402 7、顺序队列 PAGEREF _Toc208152402 h 62 HYPERLINK l _Toc208152403 SeqQue

6、ue.h PAGEREF _Toc208152403 h 63 HYPERLINK l _Toc208152404 Test.cpp PAGEREF _Toc208152404 h 68 HYPERLINK l _Toc208152405 8、链式队列 PAGEREF _Toc208152405 h 70 HYPERLINK l _Toc208152406 QueueNode.h PAGEREF _Toc208152406 h 70 HYPERLINK l _Toc208152407 LinkQueue.h PAGEREF _Toc208152407 h 71 HYPERLINK l _Toc

7、208152408 Test.cpp PAGEREF _Toc208152408 h 75 HYPERLINK l _Toc208152409 9、优先级队列 PAGEREF _Toc208152409 h 77 HYPERLINK l _Toc208152410 QueueNode.h PAGEREF _Toc208152410 h 77 HYPERLINK l _Toc208152411 Compare.h PAGEREF _Toc208152411 h 78 HYPERLINK l _Toc208152412 PriorityQueue.h PAGEREF _Toc208152412 h

8、 80 HYPERLINK l _Toc208152413 Test.cpp PAGEREF _Toc208152413 h 85 HYPERLINK l _Toc208152414 10、串 PAGEREF _Toc208152414 h 88 HYPERLINK l _Toc208152415 MyString.h PAGEREF _Toc208152415 h 88 HYPERLINK l _Toc208152416 MyString.cpp PAGEREF _Toc208152416 h 90 HYPERLINK l _Toc208152417 test.cpp PAGEREF _To

9、c208152417 h 101 HYPERLINK l _Toc208152418 11、二叉树 PAGEREF _Toc208152418 h 104 HYPERLINK l _Toc208152419 BinTreeNode.h PAGEREF _Toc208152419 h 104 HYPERLINK l _Toc208152420 BinaryTree.h PAGEREF _Toc208152420 h 112 HYPERLINK l _Toc208152421 Test.cpp PAGEREF _Toc208152421 h 124 HYPERLINK l _Toc20815242

10、2 12、线索二叉树 PAGEREF _Toc208152422 h 126 HYPERLINK l _Toc208152423 ThreadNode.h PAGEREF _Toc208152423 h 126 HYPERLINK l _Toc208152424 ThreadTree.h PAGEREF _Toc208152424 h 128 HYPERLINK l _Toc208152425 ThreadInorderIterator.h PAGEREF _Toc208152425 h 128 HYPERLINK l _Toc208152426 test.cpp PAGEREF _Toc20

11、8152426 h 139 HYPERLINK l _Toc208152427 13、堆 PAGEREF _Toc208152427 h 140 HYPERLINK l _Toc208152428 MinHeap.h PAGEREF _Toc208152428 h 140 HYPERLINK l _Toc208152429 test.cpp PAGEREF _Toc208152429 h 147 HYPERLINK l _Toc208152430 14、哈夫曼树 PAGEREF _Toc208152430 h 149 HYPERLINK l _Toc208152431 BinTreeNode.

12、h PAGEREF _Toc208152431 h 149 HYPERLINK l _Toc208152432 BinaryTree.h PAGEREF _Toc208152432 h 151 HYPERLINK l _Toc208152433 MinHeap.h PAGEREF _Toc208152433 h 156 HYPERLINK l _Toc208152434 Huffman.h PAGEREF _Toc208152434 h 161 HYPERLINK l _Toc208152435 Test.cpp PAGEREF _Toc208152435 h 163 HYPERLINK l

13、_Toc208152436 15、树 PAGEREF _Toc208152436 h 164 HYPERLINK l _Toc208152437 QueueNode.h PAGEREF _Toc208152437 h 164 HYPERLINK l _Toc208152438 LinkQueue.h PAGEREF _Toc208152438 h 165 HYPERLINK l _Toc208152439 TreeNode.h PAGEREF _Toc208152439 h 169 HYPERLINK l _Toc208152440 Tree.h PAGEREF _Toc208152440 h

14、 170 HYPERLINK l _Toc208152441 test.cpp PAGEREF _Toc208152441 h 187 HYPERLINK l _Toc208152442 16、B+树 PAGEREF _Toc208152442 h 189 HYPERLINK l _Toc208152443 BTreeNode.h PAGEREF _Toc208152443 h 189 HYPERLINK l _Toc208152444 BTree.h PAGEREF _Toc208152444 h 192 HYPERLINK l _Toc208152445 test.cpp PAGEREF

15、_Toc208152445 h 215 HYPERLINK l _Toc208152446 17、图 PAGEREF _Toc208152446 h 217 HYPERLINK l _Toc208152447 MinHeap.h PAGEREF _Toc208152447 h 217 HYPERLINK l _Toc208152448 Edge.h PAGEREF _Toc208152448 h 222 HYPERLINK l _Toc208152449 Vertex.h PAGEREF _Toc208152449 h 223 HYPERLINK l _Toc208152450 Graph.h

16、 PAGEREF _Toc208152450 h 224 HYPERLINK l _Toc208152451 test.cpp PAGEREF _Toc208152451 h 246 HYPERLINK l _Toc208152452 18、排序 PAGEREF _Toc208152452 h 249 HYPERLINK l _Toc208152453 Data.h PAGEREF _Toc208152453 h 249 HYPERLINK l _Toc208152454 QueueNode.h PAGEREF _Toc208152454 h 255 HYPERLINK l _Toc20815

17、2455 LinkQueue.h PAGEREF _Toc208152455 h 259 HYPERLINK l _Toc208152456 Sort.h PAGEREF _Toc208152456 h 263 HYPERLINK l _Toc208152457 test.cpp PAGEREF _Toc208152457 h 2781、顺序表Seqlist.hconst int DefaultSize=100;template class SeqListpublic:SeqList(int sz=DefaultSize):m_nmaxsize(sz),m_ncurrentsize(-1)if

18、(sz0)m_elements=new Typem_nmaxsize;SeqList()delete m_elements;int Length() const/get the lengthreturn m_ncurrentsize+1;int Find(Type x) const;/find the position of xint IsElement(Type x) const;/is it in the listint Insert(Type x,int i);/insert dataint Remove(Type x);/delete dataint IsEmpty()return m

19、_ncurrentsize=-1;int IsFull()return m_ncurrentsize=m_nmaxsize-1;Type Get(int i)/get the ith datareturn im_ncurrentsize?(coutcant find the elementendl,0):m_elementsi;void Print();private:Type *m_elements;const int m_nmaxsize;int m_ncurrentsize;template int SeqList:Find(Type x) constfor(int i=0;im_ncu

20、rrentsize;i+)if(m_elementsi=x)return i;coutcant find the element you want to findendl;return -1;template int SeqList:IsElement(Type x) constif(Find(x)=-1)return 0;return 1;template int SeqList:Insert(Type x, int i)if(im_ncurrentsize+1|m_ncurrentsize=m_nmaxsize-1)coutthe operate is illegali;j-)m_elem

21、entsj=m_elementsj-1;m_elementsi=x;return 1;template int SeqList:Remove(Type x)int size=m_ncurrentsize;for(int i=0;im_ncurrentsize;)if(m_elementsi=x)for(int j=i;jm_ncurrentsize;j+)m_elementsj=m_elementsj+1;m_ncurrentsize-;continue;i+;if(size=m_ncurrentsize)coutcant find the element you want to remove

22、endl;return 0;return 1;template void SeqList:Print()for(int i=0;i=m_ncurrentsize;i+)couti+1:tm_elementsiendl;coutendlendl;Test.cpp#include #include SeqList.husing namespace std;int main()SeqList test(15);int array15=2,5,8,1,9,9,7,6,4,3,2,9,7,7,9;for(int i=0;i15;i+)test.Insert(arrayi,0);test.Insert(1

23、,0);cout(test.Find(0)?cant be found :Be found ) 0 endlendl;test.Remove(7);test.Print();test.Remove(9);test.Print();test.Remove(0);test.Print();return 0;单链表ListNode.htemplate class SingleList;template class ListNodeprivate:friend typename SingleList;ListNode():m_pnext(NULL)ListNode(const Type item,Li

24、stNode *next=NULL):m_data(item),m_pnext(next)ListNode()m_pnext=NULL;public:Type GetData();friend ostream& operator (ostream& ,ListNode&);private:Type m_data;ListNode *m_pnext;template Type ListNode:GetData()return this-m_data;template ostream& operator(ostream& os,ListNode& out)osout.m_data;return o

25、s;SingleList.h#include ListNode.htemplate class SingleListpublic:SingleList():head(new ListNode()SingleList()MakeEmpty();delete head;public:void MakeEmpty(); /make the list emptyint Length(); /get the lengthListNode *Find(Type value,int n); /find thd nth data which is equal to valueListNode *Find(in

26、t n); /find the nth databool Insert(Type item,int n=0); /insert the data in the nth positionType Remove(int n=0); /remove the nth databool RemoveAll(Type item); /remove all the data which is equal to itemType Get(int n); /get the nth datavoid Print(); /print the listprivate:ListNode *head;template v

27、oid SingleList:MakeEmpty()ListNode *pdel;while(head-m_pnext!=NULL)pdel=head-m_pnext;head-m_pnext=pdel-m_pnext;delete pdel;template int SingleList:Length()ListNode *pmove=head-m_pnext;int count=0;while(pmove!=NULL)pmove=pmove-m_pnext;count+;return count;template ListNode* SingleList:Find(int n)if(n0)

28、coutThe n is out of boundaryendl;return NULL;ListNode *pmove=head-m_pnext;for(int i=0;im_pnext;if(pmove=NULL)coutThe n is out of boundaryendl;return NULL;return pmove;template ListNode* SingleList:Find(Type value,int n)if(n1)coutThe n is illegalendl;return NULL;ListNode *pmove=head;int count=0;while

29、(count!=n&pmove)pmove=pmove-m_pnext;if(pmove-m_data=value)count+;if(pmove=NULL)coutcant find the elementendl;return NULL;return pmove;template bool SingleList:Insert(Type item, int n)if(n0)coutThe n is illegalendl;return 0;ListNode *pmove=head;ListNode *pnode=new ListNode(item);if(pnode=NULL)coutApp

30、lication error!endl;return 0;for(int i=0;im_pnext;if(pmove=NULL)coutthe n is illegalm_pnext=pmove-m_pnext;pmove-m_pnext=pnode;return 1;template bool SingleList:RemoveAll(Type item)ListNode *pmove=head;ListNode *pdel=head-m_pnext;while(pdel!=NULL)if(pdel-m_data=item)pmove-m_pnext=pdel-m_pnext;delete

31、pdel;pdel=pmove-m_pnext;continue;pmove=pmove-m_pnext;pdel=pdel-m_pnext;return 1;template Type SingleList:Remove(int n)if(n0)coutcant find the elementendl;exit(1);ListNode *pmove=head,*pdel;for(int i=0;im_pnext;i+)pmove=pmove-m_pnext;if(pmove-m_pnext=NULL)coutcant find the elementm_pnext;pmove-m_pnex

32、t=pdel-m_pnext;Type temp=pdel-m_data;delete pdel;return temp;template Type SingleList:Get(int n)if(n0)coutThe n is out of boundaryendl;exit(1);ListNode *pmove=head-m_pnext;for(int i=0;im_pnext;if(NULL=pmove)coutThe n is out of boundarym_data;template void SingleList:Print()ListNode *pmove=head-m_pne

33、xt;couthead;while(pmove)coutm_data;pmove=pmove-m_pnext;coutoverendlendlendl;test.cpp#include using namespace std;#include SingleList.hint main()SingleList list;for(int i=0;i20;i+)list.Insert(i*3,i);for(int i=0;i5;i+)list.Insert(3,i*3);coutthe Length of the list is list.Length()endl;list.Print();list

34、.Remove(5);coutthe Length of the list is list.Length()endl;list.Print();list.RemoveAll(3);coutthe Length of the list is list.Length()endl;list.Print();coutThe third element is list.Get(3)endl;cout*list.Find(18,1)endl;list.Find(100);list.MakeEmpty();coutthe Length of the list is list.Length()endl;lis

35、t.Print();return 0;双向链表NodeList.htemplate class DoublyList;template class ListNodeprivate:friend class DoublyList;ListNode():m_pprior(NULL),m_pnext(NULL)ListNode(const Type item,ListNode *prior=NULL,ListNode *next=NULL):m_data(item),m_pprior(prior),m_pnext(next)ListNode()m_pprior=NULL;m_pnext=NULL;p

36、ublic:Type GetData();private:Type m_data;ListNode *m_pprior;ListNode *m_pnext;template Type ListNode:GetData()return this-m_data;DoubleList.h#include ListNode.htemplate class DoublyListpublic:DoublyList():head(new ListNode() /the head node point to itselfhead-m_pprior=head;head-m_pnext=head;DoublyLi

37、st()MakeEmpty();delete head;public:void MakeEmpty(); /make the list emptyint Length(); /get the length of the listListNode *Find(int n=0); /find the nth dataListNode * FindData(Type item); /find the data which is equal to itembool Insert(Type item,int n=0); /insert item in the nth dataType Remove(in

38、t n=0); /delete the nth dataType Get(int n=0); /get the nth datavoid Print(); /print the listprivate:ListNode *head;template void DoublyList:MakeEmpty()ListNode *pmove=head-m_pnext,*pdel;while(pmove!=head)pdel=pmove;pmove=pdel-m_pnext;delete pdel; head-m_pnext=head;head-m_pprior=head;template int Do

39、ublyList:Length()ListNode *pprior=head-m_pprior,*pnext=head-m_pnext;int count=0;while(1)if(pprior-m_pnext=pnext)break;if(pprior=pnext&pprior!=head)count+;break;count+=2;pprior=pprior-m_pprior;pnext=pnext-m_pnext;return count;template ListNode* DoublyList:Find(int n = 0)if(n0)coutThe n is out of boun

40、daryendl;return NULL;ListNode *pmove=head-m_pnext;for(int i=0;im_pnext;if(pmove=head)coutThe n is out of boundaryendl;return NULL;return pmove;template bool DoublyList:Insert(Type item,int n)if(n0)coutThe n is out of boundaryendl;return 0;ListNode *newnode=new ListNode(item),*pmove=head;if(newnode=N

41、ULL)coutApplication Erorr!endl;exit(1);for(int i=0;im_pnext;if(pmove=head)coutThe n is out of boundarym_pnext=pmove-m_pnext;newnode-m_pprior=pmove;pmove-m_pnext=newnode;newnode-m_pnext-m_pprior=newnode;return 1;template Type DoublyList:Remove(int n = 0)if(n0)coutThe n is out of boundaryendl;exit(1);

42、ListNode *pmove=head,*pdel;for(int i=0;im_pnext;if(pmove=head)coutThe n is out of boundarym_pprior-m_pnext=pdel-m_pnext;pmove-m_pnext-m_pprior=pdel-m_pprior;Type temp=pdel-m_data;delete pdel;return temp;template Type DoublyList:Get(int n = 0)if(n0)coutThe n is out of boundaryendl;exit(1);ListNode *p

43、move=head;for(int i=0;im_pnext;if(pmove=head)coutThe n is out of boundarym_data;template void DoublyList:Print()ListNode *pmove=head-m_pnext;couthead;while(pmove!=head)coutm_data;pmove=pmove-m_pnext;coutoverendlendlendl;template ListNode* DoublyList:FindData(Type item)ListNode *pprior=head-m_pprior,

44、*pnext=head-m_pnext;while(pprior-m_pnext!=pnext & pprior!=pnext) /find the data in the two directionif(pprior-m_data=item)return pprior;if(pnext-m_data=item)return pnext;pprior=pprior-m_pprior;pnext=pnext-m_pnext;coutcant find the elementendl;return NULL;Test.cpp#include #include DoublyList.husing n

45、amespace std;int main()DoublyList list;for(int i=0;i20;i+)list.Insert(i*3,i);coutthe Length of the list is list.Length()endl;list.Print();for(int i=0;i5;i+)list.Insert(3,i*3);coutthe Length of the list is list.Length()endl;list.Print();list.Remove(5);coutthe Length of the list is list.Length()endl;l

46、ist.Print();coutGetData()endl;coutThe third element is list.Get(3)endl;list.MakeEmpty();coutthe Length of the list is list.Length()endl;list.Print();return 0;循环链表ListNode.htemplate class CircularList;template class ListNodeprivate:friend class CircularList;ListNode():m_pnext(NULL)ListNode(const Type

47、 item,ListNode *next=NULL):m_data(item),m_pnext(next)ListNode()m_pnext=NULL;private:Type m_data;ListNode *m_pnext;CircularList.h#include ListNode.htemplate class CircularListpublic:CircularList():head(new ListNode()head-m_pnext=head;CircularList()MakeEmpty();delete head;public:void MakeEmpty();/clea

48、r the listint Length();/get the lengthListNode *Find(Type value,int n);/find the nth data which is equal to valueListNode *Find(int n);/find the nth databool Insert(Type item,int n=0);/insert the data into the nth data of the listType Remove(int n=0);/delete the nth databool RemoveAll(Type item);/de

49、lete all the datas which are equal to valueType Get(int n);/get the nth datavoid Print();/print the listprivate:ListNode *head;template void CircularList:MakeEmpty()ListNode *pdel,*pmove=head;while(pmove-m_pnext!=head)pdel=pmove-m_pnext;pmove-m_pnext=pdel-m_pnext;delete pdel;template int CircularLis

50、t:Length()ListNode *pmove=head;int count=0;while(pmove-m_pnext!=head)pmove=pmove-m_pnext;count+;return count;template ListNode* CircularList:Find(int n)if(n0)coutThe n is out of boundaryendl;return NULL;ListNode *pmove=head-m_pnext;for(int i=0;im_pnext;if(pmove=head)coutThe n is out of boundaryendl;

51、return NULL;return pmove;template ListNode* CircularList:Find(Type value,int n)if(n1)coutThe n is illegalendl;return NULL;ListNode *pmove=head;int count=0;while(count!=n)pmove=pmove-m_pnext;if(pmove-m_data=value)count+;if(pmove=head)coutcant find the elementendl;return NULL;return pmove;template boo

52、l CircularList:Insert(Type item, int n)if(n0)coutThe n is out of boundaryendl;return 0;ListNode *pmove=head;ListNode *pnode=new ListNode(item);if(pnode=NULL)coutApplication error!endl;exit(1);for(int i=0;im_pnext;if(pmove=head)coutThe n is out of boundarym_pnext=pmove-m_pnext;pmove-m_pnext=pnode;ret

53、urn 1;template bool CircularList:RemoveAll(Type item)ListNode *pmove=head;ListNode *pdel=head-m_pnext;while(pdel!=head)if(pdel-m_data=item)pmove-m_pnext=pdel-m_pnext;delete pdel;pdel=pmove-m_pnext;continue;pmove=pmove-m_pnext;pdel=pdel-m_pnext;return 1;template Type CircularList:Remove(int n)if(n0)c

54、outcant find the elementendl;exit(1);ListNode *pmove=head,*pdel;for(int i=0;im_pnext!=head;i+)pmove=pmove-m_pnext;if(pmove-m_pnext=head)coutcant find the elementm_pnext;pmove-m_pnext=pdel-m_pnext;Type temp=pdel-m_data;delete pdel;return temp;template Type CircularList:Get(int n)if(n0)coutThe n is ou

55、t of boundaryendl;exit(1);ListNode *pmove=head-m_pnext;for(int i=0;im_pnext;if(pmove=head)coutThe n is out of boundarym_data;template void CircularList:Print()ListNode *pmove=head-m_pnext;couthead;while(pmove!=head)coutm_data;pmove=pmove-m_pnext;coutoverendlendlendl;Test.cpp#include #include Circula

56、rList.husing namespace std;int main()CircularList list;for(int i=0;i20;i+)list.Insert(i*3,i);coutthe Length of the list is list.Length()endl;list.Print();for(int i=0;i5;i+)list.Insert(3,i*3);coutthe Length of the list is list.Length()endl;list.Print();list.Remove(5);coutthe Length of the list is lis

57、t.Length()endl;list.Print();list.RemoveAll(3);coutthe Length of the list is list.Length()endl;list.Print();coutThe third element is list.Get(3)endl;list.MakeEmpty();coutthe Length of the list is list.Length()endl;list.Print();return 0;顺序栈SeqStack.htemplate class SeqStackpublic:SeqStack(int sz):m_nto

58、p(-1),m_nMaxSize(sz)m_pelements=new Typesz;if(m_pelements=NULL)coutApplication Error!endl;exit(1);SeqStack()delete m_pelements;public:void Push(const Type item); /push dataType Pop(); /pop dataType GetTop() const; /get data void Print(); /print the stackvoid MakeEmpty() /make the stack emptym_ntop=-

59、1;bool IsEmpty() constreturn m_ntop=-1;bool IsFull() constreturn m_ntop=m_nMaxSize-1;private:int m_ntop;Type *m_pelements;int m_nMaxSize;template void SeqStack:Push(const Type item)if(IsFull()coutThe stack is full!endl;return;m_pelements+m_ntop=item;template Type SeqStack:Pop()if(IsEmpty()coutThere

60、is no element!endl;exit(1);return m_pelementsm_ntop-;template Type SeqStack:GetTop() constif(IsEmpty()coutThere is no element!endl;exit(1);return m_pelementsm_ntop;template void SeqStack:Print()coutbottom;for(int i=0;i=m_ntop;i+)coutm_pelementsi;couttopendlendlendl;Test.cpp#includeusing namespace st