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

《用C++实现数据结构中的各种算法》由会员分享，可在线阅读，更多相关《用C++实现数据结构中的各种算法（221页珍藏版）》请在装配图网上搜索。

1、目求11、顺序表1Seqlist .h1Test. cpp42单链表5ListNode .h5SingleList .h6test. cpp12双向循环链表13NodeList .h13DoubleList. h14Test. cpp204单项循环链表21ListNode .h21CircularList .h22Test . cpp28顺序栈29SeqStack.h29Test. cpp326 链式栈33StackNode . h33Linkstack. h33Test. cpp367 .顺序队列37SeqQueue .h37Test . cpp40*、! 0 rlQueueNode. h4

2、1LinkQueue . h42Test cpp44QueueNode. h46Priori tyQueue. h47ltt串52MyString. cpp54l二叉树61BinTreeNode . h62BinaryTree . h66ThreadNodu . h 74Threadinorderiterator. h76U堆83MinHeap. h83BinTreeNode . h88BinaryTree . h89MinHeap. h92Huffman. h95Test. cpp961树97TreeNode . h100Tree. h10016硼IllBTreeNode . h111BTr

3、ee.h113test. cpp1261图127MinHeap.h127Vertex, h131Graph, h132test. cpp1441a排序145QueueNode. h1491、顺序表Seqlist.hconst int DefaultSize=100；template class SeqListpublic：SeqList(int sz=DefaultSize)：m_nmaxsize(sz)z m_ncurrentsize(-1) if (sz0)m_elements=new Typem_nmaxsize；SeqList()delete m_elements；int Length

4、() constreturn m ncurrentsize+1；/get the lengthint int int intFind(Type x) const;IsElement(Type x) const； Insert(Type xz int i)； Remove(Type x)；/find the position /is it in the list /insert data /delete dataOf Xint IsEmpty()return m_ncurrentsize=l；)int IsFull()return m_ncurrentsize=m_nmaxsize-1； Typ

5、e Get(int i)/get the ith datareturn im_ncurrentsize?(coutHcant find the elementendlz0) ：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；coutcan11 find the e

6、lement you want to findendl； return -1；)template int SeqList：IsElement(Type x) const if(Find(x)=-1)return 0；return 1；template int SeqList：Insert(Type xz int i) if (im_ncurrentsize + lI |m_ncurrentsize=m_nmaxsize-l)coutHthe operate is illegalni；j-)m_elementsj=m_elementsj-1； m_elementsi=x；return 1；)te

7、mplate 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)cout11 can t find the element you want to removeHendl ；return 0；)return 1；templa

8、te void SeqList：Print() for(int i=0；i=m_ncurrentsize；i+)couti + l * ： tHm_elements i endl ；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)；) endlendl；test.Insert(1,0)

9、；cout(test.Find(0)?cant be found ：Be found ) 0test .Remove(7)；test . Print()；test.Remove(9)；test.Print()；test ,Remove(0)； test.Print()； return 0；2 单链表ListNode.h template class SingleList；template class ListNodeprivate：friend typename SingleList；ListNode () ：m_pnext (NULL) ListNode(const Type item,Li

10、stNode *next=NULL)：m_data(item)zm_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& osz ListNode& out)osout.m_data

11、；return os；SingleList.h#include ListNode.htemplate class SingleListpublic：SingleList()：head(new ListNode()SingleList()MakeEmpty()；delete head； public：数据结构算法实现2008-9-3void MakeEmpty()；int Length()；ListNode *Find(Type valuez intListNode *Find(int n)；bool Insert(Type item,int n=0)；Type Remove(int n=0)；

12、bool RemoveAll(Type item)；Type Get(int n)；void Print()；/make the list empty/get the lengthn)； /find thd nth data which is equal to value/find the nth data/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：ListNod

13、e *head;);template void SingleList：MakeEmpty()ListNode *pdel；while(head-m_pnext!=NULL)pdel=head-m_pnext；head-m_pnext=pde1-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 ListNod

14、e* SingleListType： if(n0)coutThe n is out of boundaryendl；return NULL；)ListNode *pmove=head-m_pnext；for(int i=0；im_pnext；) 一if(pmove = =NULL) coutHThe n is out of boundaryendl；return NULL；)return pmove；template ListNode* SingleListType： if(nl)coutThe n is illegalendl；return NULL；)ListNode *pmove=hea

15、d；int count=0；while(count!=n&pmove)pmove=pmove-m_pnext；if(pmove-m_data=value)count+；：Find(int n)：Find(Type valuez int n)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=

16、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 ；whi

17、le(pdel!=NULL)if(pdel-m_data=item)pmove-m_pnext=pde1-m_pnext；delete pdel；pde1=pmove-m_pnext；continue；)pmove=pmove-m_pnext；pde1=pde1-m_pnext；) return 1；template Type SingleList：Remove(int n)if(n0)coutcan11 find the elementendl；exit(1)；)ListNode pmove=head,*pdel；for(int i=0；im_pnext;i+)pmove=pmove-m_p

18、next；)一if(pmove-m_pnext = =NULL)coutcant find the elementm_pnext；pmove-m_pnext =pde1-m_pnext；Type temp=pdel-m_data；delete pdel； return temp；)template Type SingleList：Get(int n) if(n0)cout11 The n is out of boundary Hendl ；exit(1)；)ListNode pmove=head-m_pnext；for(int i=0；im_pnext；if(NULL=pmove) coutT

19、he n is out of boundarym_data；) 一template void SingleList：Print()ListNode *pmove=head-m_pnext；couthead；while(pmove)coutm_data；2008-9-3pmove=pmove-m_pnext；) coutover11 endlendlendl ；test . cpp#include using namespace std；#include HSingleList.hnint main()(SingleList list;for(int i=0；i20；i+)list.Insert

20、(i*3,i)；)for(int i=0；i5；i+)list.Insert(3 z i*3)；)cout11 the Length of the list is list. Length () endl ； list , Print()；list.Remove(5);coutHthe Length of the list is Hlist.Length()endl； list Print()；2008-9-3list.RemoveAll(3);cout the Length of the list is 11 list. Length () endl ； list , Print()；cou

21、tHThe third element is Hlist.Get(3)endl；cout*list , Find(18 z1)endl；list.Find(lOO);list.MakeEmpty()；coutthe Length of the list is list.Length()endl； list . Print()；return 0；3,双向循环链表NodeList.htemplate class DoublyList；template class ListNode(2008-9-3private：friend class DoublyList;ListNode()：m_pprior

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

23、；1 -DoubleList.h#include ListNode.hHtemplate class DoublyListpublic：/the head node point to itselfDoublyList():head(new ListNode()head-m_pprior=head；head-m_pnext=head；)-DoublyList()MakeEmpty()； delete head； )public：void MakeEmpty () ； /make the list emptyint Length()；/get the length of the listListN

24、ode *Find(int n=0)； /find the nth dataListNode * FindData(Type item)； /find the data which is equal to item bool 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; );t

25、emplate 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_ppriorz *pnext=head-m_pnext；int count=0；while(1)if(pprior-m_pnext=pnext

26、)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)cout11 The n is out of boundary11 endl ；return NULL；)ListNode *pmove=head-m_pnext；for(int i=0；im_pnext；if(pmove=head)cout HThe n i

27、s out of boundaryendl； return NULL；)return pmove；)template bool DoublyList：Insert(Type item,int n) if(n0)coutHThe n is out of boundary* endl ；return 0；)ListNode *newnode=new ListNode(item)z *pmove=head；if(newnode=NULL)coutApplication Erorr!endl； exit(1)；)for(int i=0；im_pnext；if(pmove=head)coutThe n

28、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 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 boundary

29、m_pprior-m_pnext=pde1-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 if(n0)coutThe n is out of boundaryendl；exit(1)；n = 0) ）ListNode *pmove=head；for(int i=0；im_pnext；if(pmove=head)coutThe n is out of boundarym_data； templ

30、ate void DoublyList：Print()ListNode *pmove=head-m_pnext；couthead；while(pmove!=head) cout m_ data ；pmove=pmove-m_pnext；)coutoverHendlendlendl； template ListNode* DoublyList：FindData(Type item)ListNode *pprior=head-m_pprior,*pnext=head-m_pnext；while(pprior-m_pnext!=pnext & pprior!=pnext) /find the dat

31、a 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；)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 z

32、 i)；)coutthe Length of the list is list.Length()endl； list , Print()；for(int i=0；i5；i+)list.Insert(3 z i*3)；)coutthe Length of the list is list.Length()endl；2008-9-3list.Print()；list.Remove(5)；coutHthe Length of the list is Hlist.Length()endl； list . Print()；coutGetData()endl；cout*The third element

33、is 11 list .Get (3) endl；list.MakeEmpty()；cout11 the Length of the list is Hlist. Length () endl ； list.Print()；return 0；4单项循环链表ListNode.h template class CircularList；template class ListNode(2008-9-3private：friend class CircularList；ListNode()：m_pnext(NULL)ListNode(const Type item,ListNode *next=NUL

34、L)： ListNode()m_pnext=NULL；)private：Type 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； public：void MakeEmpty() ； /clear the listm_data(item)z m_pnext(next)L

35、istNode *Find(int n)；bool Insert(Type item,int n=0)；Type Remove(int n=0)；bool RemoveAll(Type item)；Type Get (int n) ； /get the nthint Length()； /get the length/find the nth data which is equal to valueListNode *Find(Type valuez int n)；/find the nth data/insert the data into the nth data of the list/

36、delete the nth data/delete all the datas which are equal to value 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=pde1-m_pnext；delete pdel； template int CircularList：

37、Length()ListNode *pmove=head；int count=0；while(pmove-m_pnext!=head)pmove=pmove-m_pnext；count+；return count； template ListNode* CircularListType if(n0)coutThe n is out of boundaryendl； return NULL；)ListNode *pmove=head-m_pnext；for(int i=0；im_pnext；) 一if(pmove=head)coutHThe n is out of boundaryendl；re

38、turn NULL；)return pmove； template ListNode* CircularListType 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+；：Find(int n)：Find(Type valuez int n)if(pmove=head)coutcan11 find the elementendl；return NULL； )ret

39、urn 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_pne

40、xt； 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=pde1-m_pnext；delete pdel；pdel=pmove-m_pnext； continue；)pmove=pmove-m_pnext；pde1=pde1-m_pnext；) return 1；template Type

41、CircularList：Remove(int n) if(n0)coutcan11 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=pde1-m_pnext；Type temp=pdel-m_data；delete pdel； return temp；)template Type Circula

42、rList：Get(int n) if(n0)cout11 The n is out of boundary Hendl ；exit(1)；ListNode *pmove=head-m_pnext；for(int i=0；im_pnext； if(pmove=head)coutnThe n is out of boundaryHm_data；) 一template void CircularList：Print()ListNode *pmove=head-m_pnext；coutvvhead”；while(pmove!=head)cout m_data ；pmove=pmove-m_pnext

43、；) coutover11 endlendlendl ；Test . cpp#include #include CircularList.husing namespace std；int main()(CircularList list；for(int i=0；i20；i+)list.Insert(i*3 z i)；)coutthe Length of the list is list.Length()endl； list Print()；for(int i=0；i5；i+)list.Insert(3 z i*3)；)coutthe Length of the list is list.Len

44、gth()endl； list . Print()；list.Remove(5)；coutthe Length of the list is list.Length()endl；2008-9-3list.Print()；list.RemoveAll(3)；coutHthe Length of the list is Hlist.Length()endl； list . Print()；coutThe third element is Hlist.Get(3)endl；list.MakeEmpty()；cout *the Length of the list is 11 list. Length

45、 () endl； list . Print()；return 0； 顺序栈SeqStack.h template class SeqStack public：SeqStack(int sz)：m_ntop(-1)tm_nMaxSize(sz) m_pelements=new Typesz； if(m_pe1ement s = =NULL)2008-9-3coutApplication Error!nendl； exit(1)；)-SeqStack()delete m_pelements； public：void Push(const Type item)； /push dataType Po

46、p();/pop dataType GetTop() const；/get datavoid Print()；/print the stackvoid MakeEmpty()/make the stack emptym ntop=-l；)bool IsEmpty() constreturn m_ntop=-l；) 一bool IsFull() constreturn m_ntop=m nMaxSize-1；private： int m_ntop； Type *m_pelements； int m_nMaxSize；2008-9-3;template void SeqStack：Push(con

47、st Type item) if(IsFull()coutThe stack is full!nendl；return；)m_pelements+m_ntop=item；) template Type SeqStack：Pop()if(IsEmpty()coutThere is no element!endl；exit(1)；)return m_pe1ementsm ntop-； template Type SeqStack：GetTop() const if(IsEmpty()coutThere is no element!endl；exit(1)；)return m_pelements m

48、_ntop；) template void SeqStack：Print()coutbottom；for(int i=0；i=m_ntop;i+)coutm_pelementsi；couttop endlendlendl ；Test . cpp#includeusing namespace std；#include SeqStack.hint main()SeqStack stack(10)；int init10=1,2,6,9,0,3,8,7,5,4;for(int i=0；i10；i+)stack.Push(initi)；)stack.Print()；stack.Push(88)；cout

49、stack . Pop()endl；stack Print()；stack.MakeEmpty()；stack.Print()；stack . Pop()；return 0；& 链式栈StackNode.h template class Linkstack；template class StackNode private：friend class LinkStack；StackNode(Type dt,StackNode *next=NULL)private：Type m data；StackNode *m_pnext；Linkstack.h#include StackNode.h：m_data(dt)z m_pnext(next)templatety