数据结构_C源代码.docx

1、顺序表Seqlist.hconst int DefaultSize=100;template <typename Typo class SeqListpublic:SeqList(int sz=DefaultSize):m_nmaxsize(sz),m_ncurrentsize(-l)if(sz>0)m_elements=new Typem_nmaxsize;)SeqList()delete m_elements;int Length() constreturn m_ncurrentsize+l;)int Find(Type x) const;int lsElement(Type x) const;int lnsert(Type xjnt i);int Remove(Type x);int lsEmpty()return m_ncurrentsize=-l;)int lsFull()/get the length/find the position of x/is it in the list/insert data/delete datareturn m_ncurrentsize=m_nmaxsize-l;)Type Get(int i)/get the ith datafindthereturni<011 i>m_ncurrentsize?(cout«"can'telement"«endlzO):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=O;i<m_ncurrentsize;i+)if(m_elementsi=x)return i;cout«Hcan't find the element you want to find"«endl;return -1;template <typename Typo int SeqList<Type>:lsElement(Type x) const if(Find(x)=-l)return 0;return 1;template <typename Type> int SeqList<Type>:lnsert(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-l;m_elementsi=x;return 1;template <typename Type> int SeqList<Type>:Remove(Type x)int size=m_ncurrentsize;for(int i=O;i<m_ncurrentsize;)if(m_elementsi=x)for(int j=i;j<m_ncurrentsize;j+) m_elementsj=m_elementsj+l;m_ncurrentsize-;continue;)i+;if(size=m_ncurrentsize)cout«"can't find the element you want to remove"«endl; return 0;)return 1;删除所有为X的数template <typename Type> void SeqList<Type>:Print()for(int i=O;i<=m_ncurrentsize;i+)cout«i+l«":t"«m_elementsi«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,l,9,9,7,6,4,3,2,9,7,7,9;for(int i=0;i<15;i+)test.lnsert(arrayi,O);test.lnsert(l,O);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(O);test.Print();return 0;2、单链表ListNode.htemplate<typename Type> class SingleList;/List 类的前视声明template<typename Type> class ListNode private: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>(ostream& zListNode<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.hinclude "UstNode.h"template<typename Type> class SingleListpublic:SingleList():head(new ListNode<Type>()SingleList()MakeEmptyO;delete head;public:void MakeEmpty();/make the list emptyint Length();/get the lengthListNode<Type> *Find(Type valuejnt n); /find thd nth data which is equal to valueListNode<Type> *Find(int n);/find the nth databool lnsert(Type itemjnt n=O);/insert the data in the nth positionType Remove(int n=O);/remove the nth databool RemoveAII(Type item);/remove all the data which is equal to itemType Get(int n);/get the nth datavoid Print();/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 count=0;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 boundaryH«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 valuejnt 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>:lnsert(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>:RemoveAII(Type item)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;continue;pmove=pmove->m_pnext;pdel=pdel->m_pnext;return 1;template<typename Type> Type SingleList<Type>:Remove(int n) if(n<0)cout«Hcan't find the element"«endl;exit ；ListNode<Type> *pmove=headz*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(l);pdel=pmove->m_pnext;pmove->m_pnext=pdel->m_pnext;Type temp=pdel->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(l);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(l);return pmove->m_data;template<typename Type> void SingleList<Type>:Print() ListNode<Type> *pmove=head->m_pnext;cout«nhead"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=O;i<2O;i+)list.lnsert(i*3,i);for(int i=0;i<5;i+)list.lnsert(3J*3);cout«"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();list.RemoveAII(3);cout«"the Length of the list is "«list.Length()«endl;list.Print();cout«"The third element is u«list.Get(3)«endl;cout«*list.Find(184)«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 private: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;|DoubleList.h#include "ListNode.h" template<typename Type> class DoublyList public:DoublyList():head(new ListNode<Type>() /the head node point to itself head->m_pprior=head;head->m_pnext=head;)DoublyList()MakeEmptyO;delete head;public:void MakeEmpty(); /make the list emptyint Length(); /get the length of the listListNode<Type> *Find(int n=O); /find the nth dataListNode<Type> * FindData(Type item); /find the data which is equal to item bool lnsert(Type itemjnt n=O); /insert item in the nth data Type Remove(int n=0); /delete the nth data Type 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!=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_pprior/*pnext=head->m_pnext;int count=0;while(l)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 Typo 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>:lnsert(Type itemjnt 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(l);)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 Typo Type DoublyList<Type>:Remove(int n = 0) if(n<0)cout«"The n is out of boundaryH«endl;exit(l);ListNode<Type> *pmove=headz*pdel;for(int i=0;i<n;i+) /find the position for deletepmove=pmove->m_pnext;if(pmove=head)cout«"The n is out of boundary"«endl;exit(l);/delete the datapdel=pmove;pmove->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>:Get(int n = 0) if(n<0)cout«"The n is out of boundaryH«endl;exit(l);)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 ；)return pmove->m_data;template<typename Type> void DoublyList<Type>:Print()ListNode<Type> *pmove=head->m_pnext;cout«Hhead"while(pmove!=head)cout«n一>"«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=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.lnsert(i*3,i);cout«nthe Length of the list is u«list.Length()«endl;list.Print();for(int i=0;i<5;i+)list.lnsert(3,i*3);cout«Hthe Length of the list is n«list.Length()«endl;list.Print();list.Remove(5);cout«Hthe 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、循环链表UstNode.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)zm_pnext(next) ListNode()m_pnext=NULL;private:Type m_data;ListNode *m_pnext;；CircularList.hinclude "ListNode.h" template<typename Type> class CircularList public:CircularList():head(new ListNode<Type>() head->m_pnext=head;CircularList()MakeEmptyO; delete head;public:void MakeEmptyO; /clear the listint Length();/get the lengthListNode<Type> *Find(Type valuejnt n); /find the nth data which is equal to value/find the nth data/insert the data into the nth data of the list/delete the nth data/delete all the dates which are equal to valueListNode<Type> *Find(int n);bool lnsert(Type itemjnt n=O);Type Remove(int n=O);bool RemoveAII(Type item);Type Get(int n); /get the nth data void Print(); /print the listprivate:ListNode<Type> *head;template<typename Type> void CircularList<Type>:MakeEmpty() ListNode<Type> *pdelz*pmove=head;while(pmove->m_pnext!=head)pdel=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 boundaryn«endl;return NULL;)ListNode<Type> *pmove=head->m_pnext;for(int i=0;i<n&&pmove!=head;i+)pmove=pmove->m_pnext;if(pmove=head)cout«"The n is out of boundaryn«endl;return NULL;)return pmove;)template<typename Type> ListNode<Type>* CircularList<Type>:Find(Type valuejnt n) if(n<l)cout«"The n is illegal,«endl;return NULL;ListNode<Type> *pmove=head;int count=0;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 Type> bool CircularList<Type>:lnsert(Type item, int n)if(n<0)cout«"The n is out of boundaryH«endl;return 0;)ListNode<Type> *pmove=head;ListNode<Type> *pnode=new ListNode<Type>(item);if(pnode=NULL)cout«"Application error!"«endl;exit(l);)for(int i=O;i<n;i+)pmove=pmove->m_pnext;if(pmove=head)cout«"The n is out of boundary"«endl;return 0;)pnode->m_pnext=pmove->m_pnext;pmove->m_pnext=pnode;return 1;)template<typename Type> bool CircularList<Type>:RemoveAII(Type item) ListNode<Type> *pmove=head;ListNode<Type> *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<typename Type> Type CircularList<Type>:Remove(int n)if(n<0)cout«"can't find the element"«endl;exit(l);)ListNode<Type> *pmove=head/*pdel;for(int i=0;i<n&&pmove->m_pnext!=head;i+) pmove=pmove->m_pnext;if(pmove->m_pnext=head)cout«"can't find the element"«endl;exit(l);pdel=pmove