c数据结构算法模板.doc

目 录1、顺序表1Seqlist.h1Test.cpp62、单链表8ListNode.h8SingleList.h10test.cpp203、双向链表22NodeList.h22DoubleList.h24Test.cpp344、循环链表36ListNode.h36CircularList.h37Test.cpp475、顺序栈49SeqStack.h49Test.cpp546、链式栈55StackNode.h55LinkStack.h56Test.cpp607、顺序队列62SeqQueue.h63Test.cpp688、链式队列70QueueNode.h70LinkQueue.h71Test.cpp759、优先级队列77QueueNode.h77Compare.h78PriorityQueue.h80Test.cpp8510、串88MyString.h88MyString.cpp90test.cpp10111、二叉树104BinTreeNode.h104BinaryTree.h112Test.cpp12412、线索二叉树126ThreadNode.h126ThreadTree.h128ThreadInorderIterator.h128test.cpp13913、堆140MinHeap.h140test.cpp14714、哈夫曼树149BinTreeNode.h149BinaryTree.h151MinHeap.h156Huffman.h161Test.cpp16315、树164QueueNode.h164LinkQueue.h165TreeNode.h169Tree.h170test.cpp18716、B+树189BTreeNode.h189BTree.h192test.cpp21517、图217MinHeap.h217Edge.h222Vertex.h223Graph.h224test.cpp24618、排序249Data.h249QueueNode.h255LinkQueue.h259Sort.h263test.cpp2781、顺序表Seqlist.hconst int DefaultSize=100;template class SeqListpublic:SeqList(int sz=DefaultSize):m_nmaxsize(sz),m_ncurrentsize(-1)if(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_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_ncurrentsize;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_elementsj=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 removeendl;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,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;2、 单链表ListNode.htemplate class SingleList;template class ListNodeprivate:friend typename SingleList;ListNode():m_pnext(NULL)ListNode(const Type item,ListNode *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 os;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(int 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 void 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)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(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)coutApplication 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 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_pnext=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_pnext;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.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;list.Print();return 0;3、 双向链表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;public: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;DoublyList()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(int 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 DoublyList: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 boundaryendl;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=NULL)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);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 *pmove=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,*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 namespace 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;list.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;4、 循环链表ListNode.htemplate class CircularList;template class ListNodeprivate:friend class CircularList;ListNode():m_pnext(NULL)ListNode(const Type 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();/clear 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);/delete 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 CircularList: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;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 bool 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;return 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)coutcant 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 out 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;whi