数据结构各种算法实现(C++模板).docx

1、顺序表1Seqlist. h 1Test, cpp 72、单链表9ListNode. h 9SingleList, h 11test, cpp 223、双向链表25NodeList, h 25DoubleList, h 27Test, cpp 384、循环链表40ListNode. h 41CircularList. h 42Test, cpp 535、顺序栈56SeqStack. h 56Test, cpp 616、链式栈63StackNode. h 63LinkStack. h 64Test, cpp 687、顺序队列71SeqQueue. h 71Test, cpp 768、链式队列79QueueNode. h 79LinkQueue. h 80Test, cpp 849、优先级队列87QueueNode. h 87Compare, h 88Pr iorityQueue. h 90Test, cpp 9610、串99MyString. h 99MyString. cpp 102test, cpp 11411、二叉树117BinTreeNode. h 117BinaryTree. h 126Test, cpp 14012、线索二叉树142ThreadNode. h 143ThreadTree. h 144Threadinorderiterator, h 145test, cpp 15713、堆158MinHeap. h 159test, cpp 16714、哈夫曼树168BinTreeNode.h 168BinaryTree. h 171MinHeap. h 177Huffman, h 182Test, cpp 18415、树185QueueNode. h 186LinkQueue. h 187TreeNode. h 191Tree, h 192test, cpp 21116、B+树214BTreeNode. h 214BTree. h 218test, cpp 24317、图245MinHeap. h 246Edge, h 251Vertex, h 252Graph, h 254test, cpp 27918、排序282Data, h 282QueueNode. h 289LinkQueue. h 293Sort.h 298test, cpp 3141、顺序表Seqlist.hconst int DefaultSize=100;template <typename Type> class SeqListpublic:SeqList(int sz=DefaultSize):m_nmaxsize(sz),m_ncurrentsize(-1)if(sz>0)m_elements=new Typem_nmaxsize;SeqList()delete m_elements;)int Length() constreturn m_ncurrentsize+l;)int Find(Type x) const;int IsElement(Type x) const;int Insert(Type x,int i);int Remove(Type x);int IsEmpty()return m_ncurrentsize=-l)int IsFull()return m_ncurrentsize=m_/get the length/find the position of x/is it in the list/insert data/delete datamaxsize-1;)Type Get(int i)/get the ith datareturn i<0| |i>m_ncurrentsize?(cout<<"can't find the element"<<endlf 0) :m_elementsi;)void Print();private:Type *m_elements;const int m_nmaxsize;int m_ncurrentsize;；template <typename Type> int SeqList<Type>:Find(Type x) constfor(int i=0;i<m_ncurrentsize;i+)if(m_elementsi=x)return i;cout<<"can't find the element you want to find"<<endl;return -1;template <typename Type> int SeqList<Type>:IsElement(Type x) const if(Find(x)=-l)return 0;return 1;template <typename Type> int SeqList<Type>:Insert(Type x, int i)if(i<0|i>m_ncurrentsize+l|m_ncurrentsize=m_nmaxsize-l) cout<<"the operate is illegal"<<endl;return 0;)m_ncurrentsize+;for(int j=m_ncurrentsize;j>i;j) m_elementsj=m_elementsj-1;)m_elementsi=x;return 1;template <typename Type> int SeqList<Type> int size=m_ncurrentsize;for(int i=0;i<m_ncurrentsize;)if(m_elementsi=x)for(int j=i;j<m_ncurrentsize;j+)m_elementsj=m_elementsj+1;:Remove(Type x)m_ncurrent size;continue;i+；)if(size=m_ncurrentsize)cout<<"can't find the element you want to return 0;)return 1;template <typename Type> void SeqList<Type>:Prfor(int i=0;i<=m_ncurrentsize;i+)remove"<<endl;int ()cout<<i+l<<":t"<<m_elementsicout<<endl<<endl;Test.cpp#include <iostream>#include "SeqList.h"using namespace std;int main()SeqList<int> test(15);<<endl;int array 15 = 2,5,8,1,9,9,7,6,4,3,2,9,7,7,9;for(int i=0;i<15;i+)test.Insert(arrayi , 0);)test.Insert(1,0);cout<<(test.Find(0)?"can't be found ":"Be foundtest.Remove(7);test.Print();test.Remove(9);test.Print();test.Remove(0);test.Print();return 0;H)<< 0 << endl<<endl;2、单链表ListNode.htemplate<typename Type> class SingleList;template<typename Type> class ListNodeprivate:friend typename SingleList<Type>ListNode():m_pnext(NULL)ListNode(const Type item,ListNode<Type> *next=NULL):m_data(item),m_pnext(next)ListNode()m_pnext=NULL;public:Type GetData();friend ostream& operator<< <Type>(©streams ,ListNode<Type>&);private:Type m_data;ListNode *m_pnext;；template<typename Type> Type ListNode<Type>:GetData() return this->m_data;template<typename Type> ostream& operator<<(ostream& os,ListNode<Type>& out)os<<out.m_data;return os;SingleList.h#include "ListNode.h"template<typename Type> class SingleListpxiblic:SingleList () :head(new ListNode<Type>()SingleList()MakeEmpty();delete head;)public:void MakeEmpty();int Length();ListNode<Type> *Find(Type ListNode<Type> *Find(int bool Insert(Type item,int Type Remove(int n=0);bool RemoveAl1(Type item)Type Get(int n);void Print();/make the list empty/get the lengthvalue,int n); /find thd nth data which is equal to valuei) ;/find the nth datan=0) ;/insert the data in the nth position/remove the nth data/remove all the data which is equal to item/get the nth data/print the listprivate:ListNode<Type> *head;；template<typename Type> void SingleList<Type：ListNode<Type> *pdel;while(head->m_pnext!=NULL)pde1=head->m_pnext;he ad->m_pn ext =pde1->m_pnext;delete pdel;)template<typename Type> int SingleList<Type>ListNode<Type> *pmove=head->m_pnext;int count=0;> :MakeEmpty () :Length()while(pmove!=NULL) pmove=pmove->m_pnext; count+;) return count;template<typename Type> ListNode<Type>* SingleList<Type>:Find(int n) if(n<0)cout<<"The n is out of boundary"<<endl; return NULL;)ListNode<Type> *pmove=head->m_pnext;for(int i=0;i<n&&pmove;i+)pmove=pmove->m_pnext;)if(pmove=NULL)cout<<"The n is out of boundary"<<endl;return NULL;) return pmove; template<typename Type> ListNode<Type>* SingleList<Type>:Find(Type value,int n) if(n<l) cout<<"The n is illegal"<<endl;return NULL;)ListNode<Type> *pmove=head;int count=0;while(count!=n&&pmove) pmove=pmove->m_pnext; if(pmove->m_data=value)count+;)if(pmove=NULL) cout<<"can't find the element"<<endl; return NULL;)return pmove; template<typename Type> bool SingleList<Type>:Insert(Type item, int n)if(n<0) cout<<"The n is illegal"<<endl;return 0;)ListNode<Type> *pmove=head;ListNode<Type> *pnode=new ListNode<Type>(item);if(pnode=NULL)cout<<"Application error!"<<endl;return 0;)for(int i=0;i<n&&pmove;i+)pmove=pmove->m_pnext;)if(pmove=NULL)cout<<"the n is illegal"<<endl;return 0;)pnode->m_pnext=pmove->m_pnext;pmove->m_pnext=pnode;return 1;template<typename Type> bool SingleList<Type>ListNode<Type> *pmove=head;ListNode<Type> *pdel=head->m_pnext;while(pdel!=NULL)if(pdel->m_data=item)pmove->m_pnext=pdel->m_pnext;delete pdel;pdel=pmove->m_pnext;:Remove All (Type item) continue;pmove=pmove->m_pnext;pdel=pdel->m_pnext;)return 1;template<typename Type> Type SingleList<Type> if(n<0) cout<<"can't find the element"<<endl;exit (1);)ListNode<Type> *pmove=head,*pdel;for(int i=0;i<n&&pmove->m_pnext;i+):Remove(int n)pmove=pmove->m_pnext;)if(pmove->m_pnext=NULL) cout<<"can't find the element"<<endl; exit(1);)pde1=pmove->m_pnext;pmove->m_pnext=pdel->m_pnext;Type temp=pdel->m_data;delete pdel;return temp;template<typename Type> Type SingleList<Type>if(n<0):Get(int n) cout<<"The n is out of boundary"<<endl;exit(1);)ListNode<Type> *pmove=head->m_pnext;for(int i=0;i<n;i+)pmove=pmove->m_pnext;if(NULL=pmove)cout<<"The n is out of boundary"<<endl;exit (1);)return pmove->m_data; template<typename Type> void SingleList<Type>:Print () ListNode<Type> *pmove=head->m_pnextcout<<"head"while(pmove)cout<<">"<<pmove->m_data;pmove=pmove->m_pnext;)cout<<">over"<<endl<<endl<<endl;test.cpp#include <iostream>using namespace std;#include "SingleList.h"int main()(SingleList<int> list;for(int i=0;i<20;i+)list.Insert(i*3, i);)for(int i=0; i<5; i+)list.Insert(3,i*3);)cout<<"the Length of the list.Print();list.Remove(5);list i“«list .Length () <<endl;cout<<"the Length of the list is "<<list.Length()<<endl;list.Print();list.RemoveAll(3);cout<<"the Length of the list is <<list. Length () <<endl;list.Print ();cout<<"The third element is "<<list.Get(3)<<endl;cout<<*list.Find(18,1)<<endl;list.Find(lOO);list.MakeEmpty();cout<<"the Length of the list is "<<list.Length()<<endl;list.Print ();return 0;3、双向链表NodeList.htemplate<typename Type> class DoublyList;template<typename Type> class ListNodeprivate:friend class DoublyList<Type>ListNode():m_pprior(NULL),m_pnext(NULL)ListNode(const Type item,ListNode<Type> *prior=NULL,ListNode<Type> *next=NULL):m_data(item),m_pprior(prior),m_pnext(next)ListNode()m_pprior=NULL;m_pnext=NULL;)public:Type GetData();private:Type m_data;ListNode *m_pprior;ListNode *m_pnext;；template<typename Type> Type ListNode<Type> return this->m_data;DoubleList.h#include "ListNode.h"template<typename Type> class DoublyListpublic:DoublyList():head(new ListNode<Type>() head->m_pprior=head;head->m_pnext=head;)DoublyList():GetData()/the head node point to itselfMakeEmpty();delete head;) pxiblic:void MakeEmpty () ;/make the list emptyint Length();/get the length of the listListNode<Type> *Find(int n=0); /find the nth dataListNode<Type> * FindData(Type item); /find the data which is equal to itembool Insert(Type item,int n=0); /insert item in the nth dataType Remove(int n=0); /delete the nth dataType Get(int n=0); /get the nth datavoid Print();/print the list private:ListNode<Type>*head;；template<typename Type> void DoublyList<Type>:MakeEmpty()ListNode<Type> *pmove=head->m_pnext,*pdel;while(pmove!=head)pdel=pmove;pmove=pde1->m_pnext;delete pdel;)head->m_pnext=head;head->m_pprior=head;) template<typename Type> int DoublyList<Type>:Length()ListNode<Type> *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<typename Type> ListNode<Type>* DoublyList<Type>:Find(int n = 0) if(n<0) cout<<"The n is out of boundary"<<endl;return NULL;)ListNode<Type> *pmove=head->m_pnext;for(int i=0;i<n;i+)pmove=pmove->m_pnext;if(pmove=head)cout<<"The n is out of boundary"<<endl;return NULL;return pmove;template<typename Type> bool DoublyList<Type>:Insert(Type item,int n)if(n<0)cout<<"The n is out of boundary"<<endl;return 0;)ListNode<Type> *newnode=new ListNode<Type>(item),*pmove=head;if(newnode=NULL)cout<<"Application Erorr!"<<endl;exit(1);)for(int i=0;i<n;i+)/find the position for insertpmove=pmove->m_pnext;if(pmove=head)cout<<"The n is out of boundary"<<endl;return 0;)/insert the datanewnode->m_pnext=pmove->m_pnext;newnode->m_pprior=pmove;pmove->m_pnext=newnode;newnode->m_pnext->m_pprior=newnode;return 1;template<typename Type> Type DoublyList<Type>:FLemove (int n = 0) if(n<0) cout<<"The n is out of boundary"<<endl;exit(1);)ListNode<Type> *pmove=head,*pdel;for(int i=0;i<n;i+) /find the position pmove=pmove->m_pnext;if(pmove=head)cout<<"The n is out of boundary"<<endl exit (1);)/delete the datapdel=pmove;for deletepmove->m_pprior->m_pnext=pdel->m_pnext;pmove->m_pnext->m_pprior=pdel->m_pprior;Type temp=pdel->m_data;delete pdel;return temp;template<typename Type> Type DoublyList<Type>:Cif(n<0)cout<<"The n is out of boundary"<<endl;exit(1);)ListNode<Type> *pmove=head;for(int i=0;i<n;i+)pmove=pmove->m_pnext;Set(int n = 0) if(pmove=head)cout<<"The n is out of boundary"<<endl;exit (1);)return pmove->m_data;template<typename Type> void DoublyList<Type>:EListNode<Type> *pmove=head->m_pnext;cout<<"headn;while(pmove!=head)cout<<">"<<pmove->m_data;pmove=pmove->m_pnext;>rint () cout<<">over"<<endl<<endl<<endl;template<typename Type> ListNode<Type>* DoublyList<Type>:FindData(Type item)ListNode<Type> *pprior=head->m_pprior,*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;)cout<<"can't find the return NULL;Test.cpp#include <iostream>#include "DoublyList.h"using namespace std;int main()DoublyList<int> list;elementn < <endl;for(int i=0;i<20;i+)list.Insert(i*3, i);)cout<<"the Length of the listlist.Print();for(int i=0;i<5;i+)list.Insert(3,i*3);)cout<<"the Length of the list list.Print();list.Remove(5);cout<<"the Length of the list list.Print();is "«list. Length () <<endl;is "<<list.Length()<<endl;is "<<list.Length()<<endl;cout<<list.FindData(54)->GetData()<<endl;cout<<"The third element is "<<list.Get(3)<<endl;list.MakeEmpty();cout<<"the Length of the list is "<<list.Length()<<endl;list.Print();return 0;4、循环链表ListNode.htemplate<typename Type> class CircularList;template<typename Type> class ListNodeprivate:friend class CircularList<Type>ListNode():m_pnext(NULL)ListNode(const Type item,ListNode<Type> *next=NULL):m_data(item),m_pnext(next)-ListNode()m_pnext=NULL;private:Type m_data;ListNode *m_pnext;；CircularList.h#include "ListNode.h"template<typename Type> class CircularList ptiblic:CircularList():head(new ListNode<Type>() head->m_pnext=head;)CircularList()MakeEmpty();delete head;)public:void MakeEmptyO ; /clear the listint Length(); /get the lengthListNode<Type> *Find(Type value,int n); /find the nth data which is equal to valueListNode<Type> *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 RemoveAl1(Type item);/delete all the datas which are equal to valueType Get (int n) ; /get the nth datavoid Print(); /print the listprivate:ListNode<Type> *head;；template<typename Type> void CircularList<Type>:MakeEmpty()ListNode<Type> *pdel,*pmove=head;while(pmove->m_pnext!=head)pde1=pmove->m_pnext;pmove->m_pnext=pdel->m_pnext;delete pdel;)template<typename Type> int CircularList<Type>:Length()ListNode<Type> *pmove=head;int count=0;while(pmove->m_pnext!=head)pmove=pmove->m_pnext; count+;) return count;template<typename Type> ListNode<Type>* CircularList<Type>:Find(int n) if(n<0)cout<<"The n is out of boundary"<<endl; return NULL;)ListNode<Type> *pmove=head->m_pnext;for(int i=0;i<n&&pmove!=head;i+) pmove=pmove->m_pnext;if(pmove=