用C++实现数据结构中的各种算法.docx

目求11、顺序表1Seqlist .h1Test. cpp42单链表5ListNode .h5SingleList .h6test. cpp12双向循环链表13NodeList .h13DoubleList. h14Test. cpp204单项循环链表21ListNode .h21CircularList .h22Test . cpp28顺序栈29SeqStack.h29Test. cpp326 链式栈33StackNode . h33Linkstack. h33Test. cpp367 .顺序队列37SeqQueue .h37Test . cpp40*、! 0 rlQueueNode. h41LinkQueue . h42Test cpp44QueueNode. h46Priori tyQueue. h47ltt串52MyString. cpp54l二叉树61BinTreeNode . h62BinaryTree . h66ThreadNodu . h 74Threadinorderiterator. h76U堆83MinHeap. h83BinTreeNode . h88BinaryTree . h89MinHeap. h92Huffman. h95Test. cpp961树97TreeNode . h100Tree. h10016硼IllBTreeNode . h111BTree.h113test. cpp1261图127MinHeap.h127Vertex, h131Graph, h132test. cpp1441a排序145QueueNode. h1491、顺序表Seqlist.hconst int DefaultSize=100；template <typename Type>class SeqListpublic：SeqList(int sz=DefaultSize)：m_nmaxsize(sz)z m_ncurrentsize(-1) if (sz>0)m_elements=new Typem_nmaxsize；SeqList()delete m_elements；int Length() constreturn m ncurrentsize+1；/get the lengthint int int intFind(Type x) const;IsElement(Type x) const； Insert(Type xz int i)； Remove(Type x)；/find the position /is it in the list /insert data /delete dataOf Xint IsEmpty()return m_ncurrentsize="l；)int IsFull()return m_ncurrentsize=m_nmaxsize-1； Type Get(int i)/get the ith datareturn i<0| |i>m_ncurrentsize?(cout<<Hcan't find the element"<<endlz0) ：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<<"can11 find the element you want to find"<<endl； return -1；)template <typename Type> int SeqList<Type>：IsElement(Type x) const if(Find(x)=-1)return 0；return 1；template <typename Type> int SeqList<Type>：Insert(Type xz int i) if (i<0| Ii>m_ncurrentsize + lI |m_ncurrentsize=m_nmaxsize-l)cout<<Hthe operate is illegaln<<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>：Remove(Type x)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;)m_ncurrentsize-；continue； i + +; if(size=m_ncurrentsize)cout<<11 can' t find the element you want to removeH<<endl ；return 0；)return 1；template <typename Type> void SeqList<Type>：Print() for(int i=0；i<=m_ncurrentsize；i+)cout<<i + l<< *' ： tH<<m_elements i <<endl ；cout<<endl<<endl；Test . cpp#include <iostream>#include "SeqList.h"using namespace std；int main()SeqList<int> test (15)；int array15=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)；)<< endl<<endl；test.Insert(1,0)；cout<<(test.Find(0)?"can't be found "："Be found ")<< 0test .Remove(7)；test . Print()；test.Remove(9)；test.Print()；test ,Remove(0)； test.Print()； return 0；2 单链表ListNode.h template<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)zm_pnext(next) ListNode()m_pnext =NULL；)public：Type GetData()；friend ostream& operator<< <Type>(ostream& ,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& osz ListNode<Type>& out)os<<out.m_data；return os；SingleList.h#include "ListNode.h"template<typename Type> class SingleListpublic：SingleList()：head(new ListNode<Type>()SingleList()MakeEmpty()；delete head； public：数据结构算法实现2008-9-3void MakeEmpty()；int Length()；ListNode<Type> *Find(Type valuez intListNode<Type> *Find(int n)；bool Insert(Type item,int n=0)；Type Remove(int n=0)；bool RemoveAll(Type item)；Type Get(int n)；void Print()；/make the list empty/get the lengthn)； /find thd nth data which is equal to value/find the nth data/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>：MakeEmpty()ListNode<Type> *pdel；while(head->m_pnext!=NULL)pdel=head->m_pnext；head->m_pnext=pde1->m_pnext；delete pdel；)template<typename Type> int SingleList<Type>：Length()ListNode<Type> *pmove=head->m_pnext；int count=0；while(pmove!=NULL)pmove=pmove->m_pnext； count+；数据结构算法实现 return count；template<typename Type> ListNode<Type>* SingleList<Type： 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<<HThe n is out of boundary"<<endl；return NULL；)return pmove；template<typename Type> ListNode<Type>* SingleList<Type： 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+；：Find(int n)：Find(Type valuez int n)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>：RemoveAll(Type item)ListNode<Type> *pmove=head；ListNode<Type> *pdel=head->m_pnext ；while(pdel!=NULL)if(pdel->m_data=item)pmove->m_pnext=pde1->m_pnext；delete pdel；pde1=pmove->m_pnext；continue；)pmove=pmove->m_pnext；pde1=pde1->m_pnext；) return 1；template<typename Type> Type SingleList<Type>：Remove(int n)if(n<0)cout<<"can11 find the element"<<endl；exit(1)；)ListNode<Type> pmove=head,*pdel；for(int i=0；i<n&&pmove->m_pnext;i+)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 =pde1->m_pnext；Type temp=pdel->m_data；delete pdel； return temp；)template<typename Type> Type SingleList<Type>：Get(int n) if(n<0)cout<<11 The n is out of boundary H<<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_pnext；cout<<"head"；while(pmove)cout<<" >"<<pmove->m_data；2008-9-3pmove=pmove->m_pnext；) "cout<<" >over11 <<endl<<endl<<endl ；test . cpp#include <iostream> using namespace std；#include HSingleList.hnint 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 z i*3)；)cout<<11 the Length of the list is " <<list. Length () <<endl ； list , Print()；list.Remove(5);cout<<Hthe Length of the list is H<<list.Length()<<endl； list Print()；2008-9-3list.RemoveAll(3);cout<< " the Length of the list is 11 <<list. Length () <<endl ； list , Print()；cout<<HThe third element is H<<list.Get(3)<<endl；cout<<*list , Find(18 z1)<<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 ListNode(2008-9-3private：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>：GetData()return this->m_data；1 -DoubleList.h#include "ListNode.hHtemplate<typename Type> class DoublyListpublic：/the head node point to itselfDoublyList():head(new ListNode<Type>()head->m_pprior=head；head->m_pnext=head；)-DoublyList()MakeEmpty()； delete head； )public：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 item bool 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 listprivate：ListNode<Type> *head; );template<typename Type> void DoublyList<Type>：MakeEmpty()ListNode<Type> *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<typename Type> int DoublyList<Type>：Length()ListNode<Type> *pprior=head->m_ppriorz *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<<11 The n is out of boundary11 <<endl ；return NULL；)ListNode<Type> *pmove=head->m_pnext；for(int i=0；i<n；i+)pmove=pmove->m_pnext；if(pmove=head)cout<< HThe 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<<HThe n is out of boundary*' <<endl ；return 0；)ListNode<Type> *newnode=new ListNode<Type>(item)z *pmove=head；if(newnode=NULL)cout<<"Application Erorr!"<<endl； exit(1)；)for(int i=0；i<n；i+) /find the position for insert pmove=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>：Remove(int 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 for delete pmove=pmove->m_pnext；if(pmove=head)cout<<"The n is out of boundary"<<endl；exit(1);/delete the datapdel=pmove；pmove->m_pprior->m_pnext=pde1->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>：Get(int n if(n<0)cout<<"The n is out of boundary"<<endl；exit(1)；n = 0) ）ListNode<Type> *pmove=head；for(int i=0；i<n；i+)pmove=pmove->m_pnext；if(pmove=head)cout<<"The n is out of boundary"<<endl；exit(1)；)return pmove->m_data； "template<typename Type> void DoublyList<Type>：Print()ListNode<Type> *pmove=head->m_pnext；cout<<"head"；while(pmove!=head) cout<<11 > "<< pmove - >m_ data ；pmove=pmove->m_pnext；)cout<<" >overH<<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 direction if(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 element"<<endl；return NULL；Test cpp#include <iostream>#include "DoublyList.h"using namespace std；int main()DoublyList<int> list；for(int i=0；i<20；i+)list.Insert(i*3 z i)；)cout<<"the Length of the list is "<<list.Length()<<endl； list , Print()；for(int i=0；i<5；i+)list.Insert(3 z i*3)；)cout<<"the Length of the list is "<<list.Length()<<endl；2008-9-3list.Print()；list.Remove(5)；cout<<Hthe Length of the list is H<<list.Length()<<endl； list . Print()；cout<<list.FindData(54)->GetData()<<endl；cout<<*'The third element is 11 <<list .Get (3) <<endl；list.MakeEmpty()；cout<<11 the Length of the list is H<<list. Length () <<endl ； list.Print()；return 0；4单项循环链表ListNode.h template<typename Type> class CircularList；template<typename Type> class ListNode(2008-9-3private：friend class CircularList<Type>；ListNode()：m_pnext(NULL)ListNode(const Type item,ListNode<Type> *next=NULL)： ListNode()m_pnext=NULL；)private：Type m_data；ListNode *m_pnext；CircularList.h#include "ListNode.h"template<typename Type> class CircularList public：CircularList()：head(new ListNode<Type>() head->m_pnext=head；) 一-CircularList()MakeEmpty()； delete head； public：void MakeEmpty() ； /clear the listm_data(item)z m_pnext(next)ListNode<Type> *Find(int n)；bool Insert(Type item,int n=0)；Type Remove(int n=0)；bool RemoveAll(Type item)；Type Get (int n) ； /get the nthint Length()； /get the length/find the nth data which is equal to valueListNode<Type> *Find(Type valuez int n)；/find the nth data/insert the data into the nth data of the list/delete the nth data/delete all the datas which are equal to value 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=pde1->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 if(n<0)cout<<"The n is out of boundary"<<endl； return NULL；)ListNode<Type> *pmove=head->m_pnext；for(i