用C++实现数据结构中的各种算法

1、目 录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.

2、cpp759、优先级队列77queuenode.h77compare.h78priorityqueue.h80test.cpp8510、串88mystring.h88mystring.cpp90test.cpp10111、二叉树104bintreenode.h104binarytree.h112test.cpp12412、线索二叉树126threadnode.h126threadtree.h128threadinorderiterator.h128test.cpp13913、堆140minheap.h140test.cpp14714、哈夫曼树149bintreenode.h149binaryt

3、ree.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.cpp278数据结构算法实现 2008-9-31、顺

4、序表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 is

5、element(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 p

6、rint();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

7、;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_ncurrent

8、size;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 namespac

9、e 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.htem

10、plate 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

11、_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

12、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

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

14、e=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;t

15、emplate 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(ty

16、pe 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:removeal

17、l(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);listno

18、de *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_pn

19、ext;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

20、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 ele

21、ment 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(con

22、st 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.htempl

23、ate 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

24、 * 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 *pmo

25、ve=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

26、+=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 doublyli

27、st: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=newn

28、ode;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 tem

29、p=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!=he

30、ad)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 p

31、next;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.inse

32、rt(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、 循环链表

33、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

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

35、rt(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:makeempt

36、y()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)cout

37、the 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(c

38、ount!=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)couta

39、pplication 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_pn

40、ext;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