数据结构C++算法(代码).docx

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

1、目录11、顺序表1Seqlist.h 1Test.cpp7单链表9ListNode.h9test.cpp22双向链表25循环链表40ListNode.h40CircularList.h41Test.cpp52顺序栈55Test.cpp60链式栈61LinkStack.h63Test.cpp677.顺序队列69Test.cpp758、链式队歹ij77QueueNode.h77LinkQueue.h789、优先级队列85QueueNode.h85Test.cpp9410、串97MyString.h97MyString.cpp10011、二叉树117BinTreeNode.h117Test.cpp1

2、3812、线索二叉树141ThreadNode.h141ThreadTree.h14313、堆157MinHeap.h15714、哈夫曼树166BinTreeNode.h166BinaryTree.h169Test.cpp182QueueNode.h183LinkQueue.h184BTreeNode.h211BTree.h215test.cpp23917、图242MinHeap.h242Edge.h247Vertex.h248Graph, h250test.cpp27518、排序278Data.h278LinkQueue.h289Sort.h2941、顺序表Seqlist.hconst in

3、t 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() constreturn m_ncurrentsize+l;)int Find(Type x) const;int IsElement(Type x) const;int Insert(Type x,int i);int Rem

4、ove(Type x);int IsEmpty()return m_ncurrentsize=-l)int IsFull()return m_ncurrentsize=m_i)/get the length/find the position of x/is it in the list/insert data/delete datanmaxsize-1;Type Get(inti) /get the ith datareturn im_ncurrentsize?(coutcant find the elementendl,0):m_elementsi;)void Print ();priva

5、te: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 theelement you want to findendl;return -1;template int SeqList:IsElement(Type x) const if(Find(x)=-l)return 0;return 1;template i

6、nt 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 SeqList int size=m_ncurrentsize;for(int i=0;im_ncurrentsize;)if(m_elementsi=x)for(int j=i;jm_ncurrentsize;j+)m_elementsj=

7、m_elementsj+1;:Remove(Type x)m_ncurrentsize;continue;i+；)if(size=m_ncurrentsize)coutcant find the element you want return 0;)return 1;template void SeqList for(int i=0;i=m_ncurrentsize;i+)couti+l:tm_elementsiendl;to remove”endl;:Print () coutendlendl;Test.cpp#include #include SeqList.husing namespac

8、e std;int main()SeqList test(15);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 :Betest.Remove(7);test.Print();test.Remove(9);test.Print();test.Remove(0);test.Print();return 0;单链表found n) 0 endlendl;ListNode.h

9、template class SingleList;template class ListNode private:friend typename SingleList;ListNode():m_pnext(NULL)ListNode(const Type item,ListNode ListNode()m_pnext=NULL;*next=NULL):m_data(item),m_pnext(next)pxiblic:Type GetData();friend ostream& operator (streams ,ListNode&);private:Type m_data;ListNod

10、e *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 SingleListpxiblic:SingleList () :head(new ListNode()SingleList()MakeEmpty();delete head;)public:void MakeEmpty();/

11、make the list emptyint Length ();ListNode *Find(int n);bool Insert(Type item,int n=0);Type Remove(int n=0);bool RemoveAl1(Type item);Type Get(int n);void Print();/get the lengthListNode *Find(Type value,int n); /find thd nth data which is equal to value/find the nth data/insert the data in the nth p

12、osition/remove the nth data/remove all the data which is equal to item/get the nth data/print the listprivate:ListNode *head;；template void SingleList:MakeEmpty() ListNode *pdel;while(head-m_pnext!=NULL)pde1=head-m_pnext;he ad-m_pn ext =pde1-m_pnext;delete pdel;)template int SingleList:Length() List

13、Node *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

14、;) 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=pmove-m_pnext;if(pmove-m_data=value) count+;if(pmove=NULL) coutcant find the elementendl; return NULL;)return pmove; template

15、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;templ

16、ate bool SingleList: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;:Remove All (Type item) continue;pmove=pmove-m_pnext;pdel=pdel-m_pnext;)return 1;template Type SingleList:if(n0) coutcant find the eleme

17、ntendl;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=pdel-m_pnext;Type temp=pdel-m_data;delete pdel;return temp;template Type SingleListif(n0) coutThe n is out of boundaryendl;exit(

18、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 coutheadn;while(pmove)coutm_data;pmove=pmove-m_pnext;)coutoverendlendlendl;test.cpp#include using namespace std;#include SingleList.hi

19、nt 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 is nlist. Length () endl;coutthe Length of the list is list.Length()endl;list.Print();list.RemoveAll(3);coutthe Length of the list is * list.

20、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.Length()endl;list.Print ();return 0;双向链表NodeList.htemplate class DoublyList;template class ListNodeprivate:friend class DoublyList;ListNode

21、():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 return this-m_data;

22、DoubleList.h#include ListNode.htemplate class DoublyListpublic:DoublyList():head(new ListNode() head-m_pprior=head;head-m_pnext=head;)DoublyList():GetData()/the head node point to itselfMakeEmpty();delete head;)pxiblic:void MakeEmpty () ; /make the list emptyint Length();/get the length of the listL

23、istNode *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 list private:ListNode *head

24、;；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_pprior=head;)template int DoublyList:Length()ListNode *pprior=head-m_pprior,*pnext=head-m_pnext;int count=0;while(1)if(pprior-m_pnext=pnex

25、t)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 bo

26、undaryendl;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)cout*The n is out of boundarym_p

27、next=pmove-m_pnext;newnode-m_pprior=pmove;pmove-m_pnext=newnode;newnode-m_pnext-m_pprior=newnode;return 1;template Type DoublyList:IRemove(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_p

28、next=pdel-m_pnext;pmove-m_pnext-m_pprior=pdel-m_pprior;Type temp=pdel-m_data;delete pdel;return temp;template Type DoublyList:( if(n0) coutThe n is out of boundaryendl;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 Do

29、ublyListListNode *pmove=head-m_pnext;couthead;while(pmove!=head)coutm_data;pmove=pmove-m_pnext;):Print () 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 d

30、irectionif(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#include #include DoublyList.husing namespace std;int main()DoublyList list;elementnendl;38for(int i=0;i20;i+)list.Insert(i*3, i);)coutthe L

31、ength 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(

32、);coutthe Length of the list is list.Length()endl;list.Print();return 0;循环链表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:T

33、ype m_data;ListNode *m_pnext;；CircularList.h#include ListNode.htemplate class CircularList public:CircularList():head(new ListNode() head-m_pnext=head;)CircularList()MakeEmpty();delete head;)pxiblic:void MakeEmptyO ; /clear the listint Length(); /get the lengthListNode *Find(Type value,int n); /find

34、 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 nt

35、h datavoid Print(); /print the listprivate:ListNode *head;；template void CircularList:MakeEmpty()ListNode *pdel,*pmove=head;while(pmove-m_pnext!=head)pde1=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!=hea

36、d)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(nl) 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 CircularListTy