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

1、顺序表1Seqlist. h1SingleList. h4test. cpp8i双向链表9NodeList. h9DoubleList .h9Test. cpp134. 循环链表14CircularList. h15顺序栈19Test. cpp216 链式栈22StackNode . h22Test. cpp247 .顺序队列24SeqQueue. h24Test. cpp26QueueNode . h27LinkQueue . h289歹U30Test. cpp33IQ 申34MyString.h34BinTreeNode . h40Test. cpp481ZThreadTree. h49Threadinorderiterator. h4911 堆54test. cpp57BinTreeNode. h57Tree. h66BTree .h74test. cpp82MinHeap. h83Edge. h85Vertex. h85test. cpp941 & 抖Ej亨» 95test. cpp106Seqlist.h const int De£aultSize»100;template <typename Type> class SeqList public:SeqList(int szDefaultSize):m mnaxsize(sz)ncurrentsize(-1)if (sz>0)m_elementssnew Typemnmaxsize;-SeqList()delete m_elements;intLength() const(/get the lengthreturn m ncurrentsize+1；intFind(Type x) const;/find the position of xintIsElement(Type x) const;/is it in the listintInsert(Type x,int i);/insert dataintRemove(Type x);/delete dataintIsEmpty()intIsFull()return m ncurrentsize=m nmaxsize-1;Type/get the ith datareturn i<0| |i>m_ncurrentsize?(cout<<"can11 find the element"<<endl,0):m_elementsi;voidPrint();private:Type*m elements;const int m_nmaxsize;int m ncurrentsize;template <typename Type> int SeqList<Type>:Find(Type x) const for(int isO;i<m_ncurrentsize;)i£(m_elementsi=x) return i；cout<<"can't £ind the element you want to find"<<endl; return -1； template <typename Type> int SeqList<Type>:IsElement(Type x) const i£(Find(x)=-1) return 0;return 1;template <typename Type> int SeqList<Type>:Insert(Type x, int i) if (i<0| | i>m_ncurrentsize-t-l | |m_ncurrentsize=m_nmaxsize-1) ( cout<<"the operate is illegal"<<endl; return 0;)m_ncurrentsize4-4；£or(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 isO;i<m_ncurrentsize;)if(melementsi««x)for(int j =i;j<m_ncurrentsize;j +) m elementsj=m_elementsj + 1;mncurrentsize-;continue; i+ +;)i£(sizessm_ncurrentsize) cout<<ncan't find the element you want to remove"«endl; return 0;) return 1;template <typename Type> void SeqList<Type> s s Print()for(int isO;i<sm_ncurrentsize;i+)cout<<i+l<<"st"<<m_elements1<<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);)test.Insert(1,0);cout<< (test.Find(0) ?"can' t be found " : "Be found ,) << 0 << endl<<endl;test.Remove(7);test.Print();test.Remove(9);test.Print();test.Remove(0);test.Print();return 0;)2. 单链表ListNode.htemplate<typename Type> class SingleList;template<typename Type> class ListNode private:friend typename SingleList<Type>ListNodeO :m_pnext (NULL) ListNode(const Type item,ListNode<Type> *next=NULL):m_data(item)rm_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& os,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;void MakeEmpty();/make the list emptyint Length();/get the lengthListNode<Type> *Find(Type value,int n); /find thd nth data which is equal to valueListNode<Type> *Find(int n);/find the nth databool Insert(Type item,int n=0);/insert the data in the nth positionTypeRemove(int n=0);/remove the nth databoolRemoveAll(Type item);/remove all the data which is equal to itemTypeGet(int n);/get the nth datavoidPrint()；/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=pdel->m_pnext;delete pdel;)template<typename Type> int SingleList<Type>:Length()ListNode<Type> *pmove=head->m_pnext;int countsO;while(pmove!=NULL)pmove=pmove->m_pnext;count+;)return count;template<typename Type> ListNode<Type>* SingleList<Type>:Find(int n)if(n<0)cout<<nThe n is out of boundary"<<endl； return NULL;ListNode<Type > *pmove=head->m_pnext;for(int i»0;i<n&apmove;i+) pmove upmove->m_pnext;)i£(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 counts0;while(count!sn&&pmove) pmove=pmove->m_pnext; if(pmove->m_datassvalue) count+;)i£(pmove=NULL)cout<<"can't find the elementn<<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> *pnodesnew ListNode<Type>(item);if(pnode=NULL)cout<<"Application error 1"<<endl； return 0;)£or(int i«0;i<n&apmove；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> s:RemoveAll(Type item) ListNode<Type> *pmove=head;ListNode<Type> *pdel=head->m_pnext;while(pdel!=NULL)数据结构算法实现if(pdel->m_data=sitem)pmove->m_pnext=pdel->m_pnext;delete pdel;pde1spmove->m_pnext;continue;pmove=pmove->m_pnext;pdel=pdel->m_pnext;)return 1； template<typename Type> Type SingleList<Type>:Remove(int n) if(n<0) cout<<"can' t £ind the element"«endl;exit(1);) ListNode<Type> *pmove=head,*pdel; for(int i=0;i<na&pmove->m_pnext;i+) pmove upmove->m_pnext;i£(pmove->m_pnext=sNULL) cout<<"can't find the element"<<endl; exit(1);)pdel=pmove->m_pnext;pmove->m_pnext«pdel->m_pnext;Type temppdel->m_data；delete pdel;return temp;template<typename Type> Type SingleList<Type>:：Get(int n) if(n<0)cout<<"The n is out of boundary"<<endl; exit(1);) ListNode<Type> *pmove=head->m_pnext;£or(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> s:Print()ListNode<Type> >pmove=head->m_pnext;cout<<"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;£or(int ±=0;i<20;1+)list.Insert(i*3,i);)for(int i«0;i<5;i+)list.Insert(3,1*3);)cout<<"the Length of the list is "<<list.Length()<<endl; list.Print();list.Remove(5);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<<nThe third elementis.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();双向链表NodeList.htemplate<typename Type> class DoublyList;template<typename Typo class ListNodeprivate:friend class Doub1yList<Type>ListNodeO: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;mpnext=NULL;public:Type GetData();private:Type mdata;ListNode *m_pprior;ListNode *m_pnext;ftemplate<typename Type> Type ListNode<Type>:GetData() return this->m_data;)DoubleList.h#include "ListNode.h" template<typename Type> class DoublyList public:DoublyList():head(new ListNode<Type>() /the head node point to itself head->m_ppriorshead;head->m_pnext=head;)-DoublyList() MakeEmpty(); delete head; )public:void MakeEmpty () ; /make the list empty int Length(); /get the length of the list ListNode<Type> *Find(int n=0); /find the nth data ListNode<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 data void Print();/print the listprivate: ListNode<Type> *head； ;template<typename Type> void DoublyList<Type>:：MakeEmpty() ListNode<Type> *pmove®head->m_pnext,*pdel;while(pmove!shead)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_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;£or(int i=0;i<n;i+) pmovepmove->m_pnext; if(pmove=head)cout<<"The n is out of boundary"<<endl;return NULL;) return pmove； templatectypename Type> bool DoublyList<Type>s:Insert(Type item,int n) i£(n<0)cout<<"The n is out of boundary"<<endl； return 0;)ListNode<Type> *newnode=new ListNode<Type>(item),*pmoveshead;if(newnode=NULL)cout<<"Application Erorr!M<<endl; exit(1);)£or(int i«0;i<n;i+) /find the position for insert pmove =：pmo ve - >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>s:Remove(int n = 0) if(n<0)cout<<"The n is out of boundary"<<endl;exit(1);)ListNode<Type> *pmove=headr *pdel;£or(int i=0;i<n;i+) /find the position for deletepmovexpmove->m_pnext;if(pmove=head)cout<<"The n is out of boundary"<<endl;exit(1);/delete the data pdelpmove;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 = 0) if(n<0)cout<<"The n is out of boundary"<<endl; exit(1);)ListNode<Type> *pmove®head;£or(int i=0;i<n;i+) pmove«pmove->m_pnext; if(pmovesshead)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<<M >"<<pmove->m data; pmove=pmove->m_pnext; 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 direction if(pprior->m_data=item)return pprior； )if(pnext->m_data=sitem) 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(1*3,1);)cout<<wthe Length of the list is "<<list.Length()<<endl; list.Print();£or(int i=0;i<5;i+)list.Insert(3,i*3);cout<<"the Length of the list is "<<list.Length()<<endl;list.Print()；list.Remove(5);cout<<"the Length of the list is "<<list.Length()<<endl;list.Print()；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 ListNode(private：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 public:CircularList():head(new ListNode<Type>() head->m_pnext=head;CircularList() MakeEmpty();delete head;public:void MakeEmpty() ; /clear the list int Length();/get the lengthListNode<Type> *Find(Type value,int n)；:/find the nth data which isequalto valueListNode<Type> *Find(int n)；bool Insert(Type item,int n«0);/find the nth data/insert the datainto the nthdata of the listType Remove(int n=0);bool RemoveAll(Type item);/delete the/delete allnththedatadataswhichare equal to valueType Get(int n) ; /get the nth datavoid Print(); /print the list private:ListNode<Type> *head;template<typename Type> void CircularList<Type>:MakeEmpty() ListNode<Type> *pdel,*pmove=head;while(pmove->m_pnextI=head)pdel«pmove->m_pnext;pmove->m_pnextspdel->m_pnext;delete pdel;)template<typename Type> int CircularList<Type>:Length() ListNode<Type> *pxnove=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 iaO;i<n&&pmove!=head;i+) pmove=pmove->m_pnext;)i£(pmove=head) cout<<MThe n is out of boundary"<<endl; return NULL;) return pmove;)template<typename Type> ListNode<Type>* CircularList<Type>:Find(Type value,int n) if(n<l) cout<<"The n is illegal"<<endl; return NULL;)ListNode<Type> *pmove«head； int countsO;while(count!«n)pmove=pmove->m_pnext;if(pmove->m_data« *value) count+;if(pmove=head) cout<<"can't find the element"<<endl; return NULL;) return pmove； )template<typename Typo bool CircularList<Type>:Insert(Type item, int n) if(n<0)cout<<MThe n is out of boundaryN<<endl; return 0;)ListNode<Type> *pmove®head;ListNode<Type> *pnode=new ListNode<Type>(item);if(pnode=NULL)cout<<"Application error!"<<endl; exit(1);£or(int i=0;i<n;i+) pmove=pmove->m_pnext； if(pmove=head)cout<<"The n is