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

《数据结构各种算法实现(C++模板).docx》由会员分享，可在线阅读，更多相关《数据结构各种算法实现(C++模板).docx（418页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、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、链式队列

2、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, c

3、pp 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 252Gr

4、aph, h 254test, cpp 27918、排序282Data, h 282QueueNode. h 289LinkQueue. h 293Sort.h 298test, cpp 3141、顺序表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 Leng

5、th() 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

6、Get(int i)/get the ith datareturn im_ncurrentsize?(coutcant find the elementendlf 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

7、you want to findendl;return -1;template int SeqList:IsElement(Type x) const if(Find(x)=-l)return 0;return 1;template int SeqList:Insert(Type x, int i)if(im_ncurrentsize+l|m_ncurrentsize=m_nmaxsize-l) coutthe operate is illegali;j) m_elementsj=m_elementsj-1;)m_elementsi=x;return 1;template int SeqLis

8、t 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;:Remove(Type x)m_ncurrent size;continue;i+；)if(size=m_ncurrentsize)coutcant find the element you want to return 0;)return 1;template void SeqList:Prfor(int i=0;i=m_ncurren

9、tsize;i+)removeendl;int ()couti+l:tm_elementsicoutendlendl;Test.cpp#include #include SeqList.husing namespace std;int main()SeqList 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;i15;i+)test.Insert(arrayi , 0);)test.Insert(1,0);cout(test.Find(0)?cant be found :Be foundtest.Re

10、move(7);test.Print();test.Remove(9);test.Print();test.Remove(0);test.Print();return 0;H) 0 endlendl;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)ListN

11、ode()m_pnext=NULL;public:Type GetData();friend ostream& operator (streams ,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 S

12、ingleListpxiblic:SingleList () :head(new ListNode()SingleList()MakeEmpty();delete head;)public:void MakeEmpty();int Length();ListNode *Find(Type ListNode *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 length

13、value,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 *head;；template void SingleListType：ListNode *pdel;while(head-m_pnex

14、t!=NULL)pde1=head-m_pnext;he ad-m_pn ext =pde1-m_pnext;delete pdel;)template int SingleListListNode *pmove=head-m_pnext;int count=0; :MakeEmpty () :Length()while(pmove!=NULL) pmove=pmove-m_pnext; count+;) return count;template ListNode* SingleList:Find(int n) if(n0)coutThe n is out of boundaryendl;

15、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(nl) coutThe n is illegalendl;return NULL;)ListNode *pmove=head;int count=0;while(count!=n&pmove) pmove=pm

16、ove-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!e

17、ndl;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 SingleListListNode *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;:Remove All

18、 (Type item) continue;pmove=pmove-m_pnext;pdel=pdel-m_pnext;)return 1;template Type SingleList if(n0) coutcant find the elementendl;exit (1);)ListNode *pmove=head,*pdel;for(int i=0;im_pnext;i+):Remove(int n)pmove=pmove-m_pnext;)if(pmove-m_pnext=NULL) coutcant find the elementm_pnext;pmove-m_pnext=pd

19、el-m_pnext;Type temp=pdel-m_data;delete pdel;return temp;template Type SingleListif(n0):Get(int n) 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_pn

20、extcouthead;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.Print();list.Remove(5);list i“l

21、ist .Length () endl;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(lOO);list.MakeEmpty();coutthe Length of the list is list.Len

22、gth()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=NUL

23、L;m_pnext=NULL;)public:Type GetData();private:Type m_data;ListNode *m_pprior;ListNode *m_pnext;；template Type ListNode return this-m_data;DoubleList.h#include ListNode.htemplate class DoublyListpublic:DoublyList():head(new ListNode() head-m_pprior=head;head-m_pnext=head;)DoublyList():GetData()/the h

24、ead node point to itselfMakeEmpty();delete head;) pxiblic: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

25、 nth dataType Remove(int n=0); /delete the nth dataType Get(int n=0); /get the nth datavoid Print();/print the list private:ListNode*head;；template void DoublyList:MakeEmpty()ListNode *pmove=head-m_pnext,*pdel;while(pmove!=head)pdel=pmove;pmove=pde1-m_pnext;delete pdel;)head-m_pnext=head;head-m_ppri

26、or=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(

27、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(

28、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:FLemove (int n = 0) if(n0) coutTh

29、e 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:Cif(n0)coutThe n is out of boundarye

30、ndl;exit(1);)ListNode *pmove=head;for(int i=0;im_pnext;Set(int n = 0) if(pmove=head)coutThe n is out of boundarym_data;template void DoublyList:EListNode *pmove=head-m_pnext;coutheadn;while(pmove!=head)coutm_data;pmove=pmove-m_pnext;rint () coutoverendlendlendl;template ListNode* DoublyList:FindData

31、(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 return NULL;Test.cpp#inclu

32、de #include DoublyList.husing namespace std;int main()DoublyList list;elementn endl;for(int i=0;i20;i+)list.Insert(i*3, i);)coutthe Length of the listlist.Print();for(int i=0;i5;i+)list.Insert(3,i*3);)coutthe Length of the list list.Print();list.Remove(5);coutthe Length of the list list.Print();is l

33、ist. Length () endl;is list.Length()endl;is list.Length()endl;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 Circ

34、ularList;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 CircularList ptiblic:CircularList():head(new ListNode() head-m_pnext=head;)CircularL

35、ist()MakeEmpty();delete head;)public:void MakeEmptyO ; /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

36、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 *head;；template void CircularList:MakeEmpty()ListNode *pdel,*pmove=head;while(pmove-m_pnext!=head)pde1=pmove-m

37、_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=