《用c实现数据结构中的各种算法.pdf》由会员分享，可在线阅读，更多相关《用c实现数据结构中的各种算法.pdf（166页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、目 录目 录.11、顺序表.1Seqlist.h.1Test.cpp.42、单链表.5ListNode.h.5SingleList.h.6test.cpp.123、双向循环链表.13NodeList.h.13DoubleList.h.14Test.cpp.204、单项循环链表.21ListNode.h.21CircularList.h.22Test.cpp.285、顺序栈.29SeqStack.h.29Test.cpp.326、链式栈.33StackNode.h.33Linkstack.h.33Test.cpp.367.顺序队列.37SeqQueue.h.37Test.cpp.408、链式队列
2、.41QueueNode.h.41LinkQueue.h.42Test.cpp.449、优先级队列.45QueueNode.h.46Compare.h.46PriorityQueue.h.47Test.cpp.5110、串.52MySt ring.h.52MyString.cpp.54test.cpp.60I E 二叉树.61BinTreeNode.h.62BinaryTree,h.66Test.cpp.7312、线索二叉树.74ThreadNode.h.74ThreadTree.h.75Threadlnorderlterator.h.76test.cpp.8213、堆.83MinHeap.h
3、.83test.cpp.8714、哈夫曼树.88BinTreeNode.h.88BinaryTree h.89MinHeap.h.92Huffman.h.95Test.cpp.9615、树.97QueueNode.h.97LinkQueue.h.97TreeNode.h.100Tree.h.100test.cpp.11016、B+树.IllBTreeNode.h.IllBTree.h.113test.cpp.12617、图.127MinHeap.h.127Edge.h.130Vertex.h.131Graph.h.132test.cpp.14418、排序.145Data.h.146QueueN
4、ode.h.149LinkQueue.h.152Sort.h.154test cpp.162数据结构算法实现2008-9-31、顺序表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()constreturn m_ncurrentsize+1;
5、)int Find(Type x)const;int IsElement(Type x)const;int Insert(Type int i);int Remove(Type x);/get the length/find the position/is it in the list/insert data/delete dataX数据结构算法实现int IsEmpty()return m_ncurrentsize=-l;)int IsFull()return m_ncurrentsize=m_nmaxsize-l;Type Get(int i)/get the ith datareturn
6、 im_ncurrentsize?(coutHcan11 find the elementnendlz 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;coutHcan*t find the element you want to findHendl;return-1;
7、)template int SeqList:IsElement(Type x)constif(Find(x)=-l)return 0;return 1;22008-9-3数据结构算法实现2008-9-3template int SeqList:Insert(Type x,int i)if(im_ncurrentsize+l|m_ncurrentsize=m_nmaxsize-l)coutnthe operate is illegalni;j-)m_elementsj=m_elementsj-1;m_elementsi=x;return 1;)template int SeqList:Remov
8、e(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)coutncan*t find the element you want to removeuendl;return 0;3数据结构算法实现return 1;)template void SeqList:Printfor(in
9、t i=0;i=m_ncurrentsize;i+)couti+ln:tH m_elementsiendl;coutendlendl;2008-9-30 Test.cppinclude include nSeqList.hHusing namespace std;int m a i n()(SeqList test(15);int array15=2,5,8,1r 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)?ncan1t be found n
10、:Be foundtest.Remove(7);test,Print();test,Remove(9);)0 endlendl;4数据结构算法实现test,Print();test,Remove(0);test,Print();return 0;2、单链表2008-9-3ListNode.htempiate class SingleList;tempiate class ListNodeprivate:friend typename SingleList;ListNode():m_pnext(NULL)ListNode(const Type itemA ListNode*next=NULL):
11、m_data(item),m_pnext(next)ListNode()m_pnext=NULL;)public:Type GetData();friend ostream&operator(ostreamS zListNode&);5数据结构算法实现private:Type m_data;ListNode*m_pnext;；tempiate Type ListNode:GetData()return this-m_data;)tempiate ostream&operator(ostream&os,ListNode&out)osout.m_data;return os;)2008-9-3Si
12、ngleList h#include ListNode.hHtempiate class SingleListpublic:SingleList():head(new ListNode()-SingleList()MakeEmpty();delete head;public:6数据结构算法实现2008-9-3void MakeEmpty();int Length();ListNode*Find(Type value,intListNode*Find(int n);bool Insert(Type item,int n=0);Type Remove(int n=0);bool RemoveAll
13、(Type item);Type Get(int n);void Print();/make the list empty/get the lengthn);/find thd nth data/find the nth datawhich is equal to value/insert the data in/remove the nth data/remove all the data/get the nth data/print the listthe nth positionwhich is equal to itemprivate:ListNode*head;)；tempiate
14、void SingleList:MakeEmpty()*pdel;while(head-m_pnext!=NULL)pdel=head-m_pnext;head-m_pnext=pdel-m_pnext;delete pdel;)tempiate int SingleList:Length()ListNode*pmove=head-m_pnext;int count=0;while(pmove!=NULL)pmove=pmove-m_pnext;count+;7数据结构算法实现return count;)tempiate ListNode*SingleListif(n0)coutnThe n
15、is out of boundarynendl;return NULL;ListNode*pmove=head-m_pnext;for(int i=0;im_pnext;)if(pmove=NULL)coutnThe n is out of boundarynendl;return NULL;)return pmove;)tempiate ListNode*SingleListif(nl)coutnThe n is illegaluendl;return NULL;ListNode*pmove=head;int count=0;while(count!=n&pmove)pmove=pmove-
16、m_pnext;if(pmove-m_data=value)count+；:Find(int n):Find(Type value,int n)2008-9-382008-9-3数据结构算法实现)if(pmove=NULL)coutncan*t find the element uendl;return NULL;)return pmove;tempiate bool SingleList:Insert(Type item,int n)if(n0)coutThe n is illegalnendl;return 0;)ListNodeType *pmove=head;ListNode*pnod
17、e=new ListNode(item);if(pnode=NULL)coutnApplication error!uendl;return 0;for(int i=0;im_pnext;if(pmove=NULL)coutnthe n is illegalum_pnext=pmove-m_pnext;pmove-m_pnext=pnode;9数据结构算法实现return 1;)tempiate bool SingleList:RemoveAll(Type item)ListNode*pmove=head;ListNode*pdel=head-m_pnext;while(pdel!=NULL)
18、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;)tempiate Type SingleList:Remove(int n)if(n0)coutncan11 find the elementnendl;exit(1);ListNode*pmove=headr*pdel;for(int i=0;im_pnext;i+)pmove=pmove-m_pnext;if(pmove
19、-m_pnext=NULL)coutncan11 find the elementnm_pnext;pmove-m_pnext=pdel-m_pnext;Type temp=pdel-m_data;delete pdel;return temp;tempiate Type SingleList:Get(int n)if(n0)coutHThe n is out of boundarynendl;exit(1);)ListNode*pmove=head-m_pnext;for(int i=0;im_pnext;if(NULL=pmove)coutnThe n is out of boundary
20、nm_data;tempiate void SingleList:Print()ListNode*pmove=head-m_pnext;coutnheadn;while(pmove)cout n m_dat a;11数据结构算法实现pmove=pmove-m_pnext;)coutover endlendlendl;2008-9-3test.cppinclude using namespace std;include SingleList.h”int main()(SingleList list;for(int i=0;i20;i+)list.Insert(i*3z i);for(int i=
21、0;i5;i+)list.Insert(3Z i*3);)coutthe Length of the list is nlist.Length()endllist.Print();list,Remove(5);coutthe Length of the list is Hlist.Length()endllist.Print();12数据结构算法实现2008-9-3list.RemoveAll(3);coutnthe Length of the list is list.Length()endllist.Print();coutHThe third element is nlist.Get(3
22、)endl;cout*list.Find(18,1)endl;list,Find(100);list.MakeEmpty();coutnthe Length of the list is Hlist.Length()endllist.Print();return 0;3、双向循环链表NodeList htempiate class DoublyList;tempiate class ListNode13数据结构算法实现private:friend class DoublyList;ListNode():m_pprior(NULL),m_pnext(NULL)ListNode(const Typ
23、e 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;；tempiate Type ListNode:GetData()return this-m_data;2008-9-3DoubleList h#include ListNode.htemp
24、iate class DoublyListpublic:DoublyList():head(new ListNode()/the head node point to itself142008-9-3数据结构算法实现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 listListNode*Find(int n=0);/find the
25、 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:ListNodeType*head;)；tempiate void DoublyList:MakeEmpty
26、()ListNode*pmove=head-m_pnext,*pdel;while(pmove!=head)pdel=pmove;pmove=pdel-m_pnext;delete pdel;)head-m_pnext=head;152008-9-3数据结构算法实现head-m_pprior=head;tempiate int DoublyList:Length()ListNode*pprior=head-m_ppriorr*pnext=head-m_pnext;int count=0;while(1)if(pprior-m_pnext=pnext)break;if(pprior=pnext&
27、pprior!=head)count+;break;)count+=2;pprior=pprior-m_pprior;pnext=pnext-m_pnext;return count;tempiate ListNode*DoublyList:Find(int n=0)if(n0)coutHThe n is out of boundarynendl;return NULL;ListNode*pmove=head-m_pnext;for(int i=0;im_pnext;if(pmove=head)16数据结构算法实现coutHThe n is out of boundaryHendl;retur
28、n NULL;)return pmove;)tempiate bool DoublyList:Insert(Type item,int n)if(n0)coutnThe n is out of boundaryuendl;return 0;)ListNode*newnode=new ListNode(item),*pmove=head;if(newnode=NULL)coutApplication Erorr!nendl;exit(1);)for(int i=0;im_pnext;if(pmove=head)coutHThe n is out of boundarym_pnext=pmove-
29、m_pnext;newnode-m_pprior=pmove;pmove-m_pnext=newnode;newnode-m_pnext-m_pprior=newnode;2008-9-317数据结构算法实现return 1;)tempiate Type DoublyList:Remove(intif(n0)coutnThe n is out of boundarynendl;exit(1);ListNode*pmove=headr*pdel;for(int i=0;im_pnext;if(pmove=head)coutThe n is out of boundarynm_pprior-m_p
30、next=pdel-m_pnext;pmove-m_pnext-m_pprior=pdel-m_pprior;Type temp=pdel-m_data;delete pdel;return temp;tempiate Type DoublyList:Get(int nif(n0)coutThe n is out of boundarynendl;exit(1);n=0)0)(2008-9-3数据结构算法实现)ListNode*pmove=head;for(int i=0;im_pnext;if(pmove=head)coutnThe n is out of boundarynm_data;)
31、tempiate void DoublyList:Print()ListNode*pmove=head-m_pnext;coutnheadn;while(pmove!=head)cout m_data;pmove=pmove-m_pnext;)coutoverH endlendlendl;)tempiate ListNode*DoublyList:FindData(Type item)ListNode*pprior=head-m_ppriorf*pnext=head-m_pnext;while(pprior-m_pnext!=pnext&pprior!=pnext)/find the data
32、 in the two directionif(pprior-m_data=item)return pprior;)if(pnext-m_data=item)2008-9-319数据结构算法实现return pnext;pprior=pprior-m_pprior;pnext=pnext-m_pnext;coutHcan11 find the elementnendl;return NULL;2008-9-3Test.cppinclude include DoublyList.hHusing namespace std;int m a i n()(DoublyList list;for(int
33、 i=0;i20;i+)list.Insert(i*3f i);)coutnthe Length of the list is nlist.Length()endllist.Print();for(int i=0;i5;i+)list.Insert(3,i*3);)coutnthe Length of the list is nlist.Length()endl20数据结构算法实现list,Print();list.Remove(5);coutnthe Length of the list is nlist.Length()endllist Print();coutGetData()endl;
34、coutnThe third element is Hlist.Get(3)endl;list.MakeEmpty();coutnthe Length of the list is nlist.Length()endllist Print();return 0;2008-9-34、单项循环链表ListNode.htempiateclass CircularList;tempiate class ListNode21数据结构算法实现private:friend class CircularList;ListNode():m_pnext(NULL)ListNode(const Type item,
35、ListNode*next=NULL):m_data(item),m_pnext(next)-ListNode()m_pnext=NULL;)2008-9-3private:Type m_data;ListNode*m_pnext;；CircularList,hinclude ListNode.hHtempiate class CircularListpublic:CircularList():head(new ListNodeType()head-m_pnext=head;)-CircularList()MakeEmpty();delete head;public:void MakeEmpt
36、y();/clear the list22数据结构算法实现2008-9-3int Length();/get the lengthListNode*Find(Type value,int n);/find the nth data which is equal to valueListNode*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 nth/find the nth data/insert the data
37、 into the nth data of the list/delete the nth data/delete all the datas which are equal to valuedatavoid Print();/print the listprivate:ListNode*head;)；tempiate void CircularList:MakeEmpty()*pdelz*pmove=head;while(pmove-m_pnext!=head)pdel=pmove-m_pnext;pmove-m_pnext=pdel-m_pnext;delete pdel;)tempiat
38、e int CircularList:Length()ListNode*pmove=head;int count=0;while(pmove-m_pnext!=head)pmove=pmove-m_pnext;count+;23数据结构算法实现return count;)tempiate ListNode*CircularListif(n0)coutnThe n is out of boundarynendl;return NULL;ListNode*pmove=head-m_pnext;for(int i=0;im_pnext;)if(pmove=head)coutnThe n is out
39、 of boundarynendl;return NULL;)return pmove;)tempiate ListNode*CircularListif(nl)coutnThe n is illegaluendl;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 value,int n)2008-9-324数据结构算法实现)if(pmove=head)coutncan*t find
40、the elementendl;return NULL;return pmove;)tempiate bool CircularList:Insert(Type item,int n)if(n0)coutHThe n is out of boundarynendl;return 0;)ListNode*pmove=head;ListNode*pnode=new ListNode(item);if(pnode=NULL)coutnApplication error!uendl;exit(1);)for(int i=0;im_pnext;if(pmove=head)coutHThe n is ou
41、t of boundaryHm_pnext=pmove-m_pnext;pmove-m_pnext=pnode;25数据结构算法实现return 1;)tempiate 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=
42、pdel-m_pnext;)return 1;)tempiate Type CircularList:Remove(int n)if(n0)coutncan11 find the elementnendl;exit(1);ListNode*pmove=headr*pdel;for(int i=0;im_pnext!=head;i+)pmove=pmove-m_pnext;if(pmove-m_pnext=head)coutncan11 find the elementnm_pnext;pmove-m_pnext=pdel-m_pnext;Type temp=pdel-m_data;delete
43、 pdel;return temp;tempiate Type CircularList:Get(intif(n0)coutHThe n is out of boundarynendl;exit(1);)ListNode*pmove=head-m_pnext;for(int i=0;im_pnext;if(pmove=head)coutnThe n is out of boundarynm_data;tempiate void CircularList:Print()ListNode*pmove=head-m_pnext;coutnheadn;while(pmove!=head)cout n
44、m_dat a;n)27数据结构算法实现pmove=pmove-m_pnext;)coutover endlendlendl;2008-9-3Test.cpp#include include nCircularList.hnusing namespace std;int m a i n()(CircularList list;for(int i=0;i20;i+)list.Insert(i*3,i);)coutnthe Length of the list is list.Length()endllist.Print();for(int i=0;i5;i+)list.Insert(3,i*3)
45、;)coutnthe Length of the list is nlist.Length()endllist Print();list,Remove(5);coutnthe Length of the list is nlist.Length()endl28数据结构算法实现list,Print();list.RemoveAll(3);coutnthe Length of the list is nlist.Length()endllist Print();coutThe third element is list.Get(3)endl;list.MakeEmpty();coutnthe Le
46、ngth of the list is Hlist.Length()endllist.Print();return 0;2008-9-35、顺序栈SeqStack.htempiate class SeqStackpublic:SeqStack(int sz):m_ntop(-1),m_nMaxSize(sz)m_pelements=new Typesz;if(m_pelements=NULL)29数据结构算法实现coutApplication Error!Hendl;exit(1);)-SeqStack()delete m_pelements;)2008-9-3public:voidTypeT
47、ypevoidvoidPush(const Type item);/push dataPop();GetTop()const;Print();MakeEmpty()/pop data/get data/print the stack/make the stack emptym_ntop=-l;)bool IsEmpty()constreturn m_ntop=-l;)bool IsFull()constreturn m_ntop=m_nMaxSize-l;)private:int m_ntop;Type*m_pelements;int m_nMaxSize;302008-9-3数据结构算法实现
48、T；tempiate void SeqStack:Push(const Type item)if(IsFull()coutnThe stack is full!uendl;return;)m_pelements +m_ntop=item;tempiate Type SeqStack:Pop()if(IsEmpty()coutThere is no element!uendl;exit(1);)return m_pelementsm_ntop-;)tempiate Type SeqStack:GetTop()constif(IsEmpty()coutnThere is no element!ne
49、ndl;exit(1);)return m_pelements m_ntop;)tempiate void SeqStack:Print()coutbottom;for(int i=0;i=m_ntop;i+)coutum_pelementsi;31数据结构算法实现)couttopH endlendlendl2008-9-3Test cpp#includeusing namespace std;#include nSeqStack hHint m a i n()SeqStack stack(10);int init 10=1,2,6,9,0,3,8,7,5,4for(int i=0;i10;i
50、+)stack.Push(initi);)stack.Print();stack.Push(88);coutstack.P o p()endl;stack.Print();stack.MakeEmpty();stack.Print();；stack.Pop();32数据结构算法实现return 0;)2008-9-36、链式栈StackNode.htempiate class Linkstack;tempiate class StackNodeprivate:friend class LinkStack;StackNode(Type dt,StackNode*next=NULL)private