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

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

1、1、顺序表1Seqlist. h1SingleList. h4test. cpp8i双向链表9NodeList. h9DoubleList .h9Test. cpp134. 循环链表14CircularList. h15顺序栈19Test. cpp216 链式栈22StackNode . h22Test. cpp247 .顺序队列24SeqQueue. h24Test. cpp26QueueNode . h27LinkQueue . h289歹U30Test. cpp33IQ 申34MyString.h34BinTreeNode . h40Test. cpp481ZThreadTree. h4

2、9Threadinorderiterator. h4911 堆54test. cpp57BinTreeNode. h57Tree. h66BTree .h74test. cpp82MinHeap. h83Edge. h85Vertex. h85test. cpp941 & 抖Ej亨 95test. cpp106Seqlist.h const int DeaultSize100;template class SeqList public:SeqList(int szDefaultSize):m mnaxsize(sz)ncurrentsize(-1)if (sz0)m_elementssnew

3、Typemnmaxsize;-SeqList()delete m_elements;intLength() const(/get the lengthreturn m ncurrentsize+1；intFind(Type x) const;/find the position of xintIsElement(Type x) const;/is it in the listintInsert(Type x,int i);/insert dataintRemove(Type x);/delete dataintIsEmpty()intIsFull()return m ncurrentsize=

4、m nmaxsize-1;Type/get the ith datareturn im_ncurrentsize?(coutcan11 find the elementendl,0):m_elementsi;voidPrint();private:Type*m elements;const int m_nmaxsize;int m ncurrentsize;template int SeqList:Find(Type x) const for(int isO;im_ncurrentsize;)i(m_elementsi=x) return i；coutcant ind the element

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

6、te int SeqList:Remove(Type x) int size=m_ncurrentsize；for(int isO;im_ncurrentsize;)if(melementsix)for(int j =i;jm_ncurrentsize;j +) m elementsj=m_elementsj + 1;mncurrentsize-;continue; i+ +;)i(sizessm_ncurrentsize) coutncant find the element you want to removeendl; return 0;) return 1;template void

7、SeqList s s Print()for(int isO;ism_ncurrentsize;i+)couti+lstm_elements1endl;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);)test.Insert(1,0);cout (test.Find(0) ?can t be

8、 found : Be found ,) 0 endlendl;test.Remove(7);test.Print();test.Remove(9);test.Print();test.Remove(0);test.Print();return 0;)2. 单链表ListNode.htemplate class SingleList;template class ListNode private:friend typename SingleList;ListNodeO :m_pnext (NULL) ListNode(const Type item,ListNode *next=NULL):m

9、_data(item)rm_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& os,ListNode& out) os class SingleListpublic:SingleList

10、()：head(new ListNode()SingleList ()MakeEmpty(); delete head;public;void MakeEmpty();/make the 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 t

11、he nth positionTypeRemove(int n=0);/remove the nth databoolRemoveAll(Type item);/remove all the data which is equal to itemTypeGet(int n);/get the nth datavoidPrint()；/print the listprivate:ListNode *head;);template void SingleList:MakeEmpty()ListNode *pdel;while(head-m_pnext!=NULL)pdel=head-m_pnext

12、;head-m_pnext=pdel-m_pnext;delete pdel;)template int SingleList:Length()ListNode *pmove=head-m_pnext;int countsO;while(pmove!=NULL)pmove=pmove-m_pnext;count+;)return count;template ListNode* SingleList:Find(int n)if(n0)coutnThe n is out of boundaryendl； return NULL;ListNode *pmove=head-m_pnext;for(i

13、nt i0;im_pnext;)i(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 counts0;while(count!sn&pmove) pmove=pmove-m_pnext; if(pmove-m_datassvalue) count+;)i(pmov

14、e=NULL)coutcant find the elementnendl;return NULL;) return pmove;)template bool SingleList:Insert(Type item, int n) if(n0) coutThe n is illegalendl; return 0;)ListNode *pmovehead；ListNode *pnodesnew ListNode(item);if(pnode=NULL)coutApplication error 1endl； return 0;)or(int i0;im_pnext;if(pmove=NULL)

15、 coutthe n is illegalm_pnext=pmove-m_pnext;pmove-m_pnextpnode;return 1;)template bool SingleList s:RemoveAll(Type item) ListNode *pmove=head;ListNode *pdel=head-m_pnext;while(pdel!=NULL)数据结构算法实现if(pdel-m_data=sitem)pmove-m_pnext=pdel-m_pnext;delete pdel;pde1spmove-m_pnext;continue;pmove=pmove-m_pnex

16、t;pdel=pdel-m_pnext;)return 1； template Type SingleList:Remove(int n) if(n0) coutcan t ind the elementendl;exit(1);) ListNode *pmove=head,*pdel; for(int i=0;im_pnext;i+) pmove upmove-m_pnext;i(pmove-m_pnext=sNULL) coutcant find the elementm_pnext;pmove-m_pnextpdel-m_pnext;Type temppdel-m_data；delete

17、 pdel;return temp;template Type SingleList:：Get(int n) if(n0)coutThe n is out of boundaryendl; exit(1);) ListNode *pmove=head-m_pnext;or(int i0;im_pnext;if(NULL=pmove)coutThe n is out of boundarym_data;template void SingleList s:Print()ListNode pmove=head-m_pnext;couthead;while(pmove)cout m_data;pmo

18、ve=pmove-m_pnext;)coutoverendlendlendl;test.cpp#include using namespace std;#include SingleList.h int main()SingleList list;or(int =0;i20;1+)list.Insert(i*3,i);)for(int i0;i5;i+)list.Insert(3,1*3);)coutthe Length of the list is list.Length()endl; list.Print();list.Remove(5);coutthe Length of the lis

19、t is list.Length()endl; list.Print();list.RemoveAll(3);coutthe Length of the list is list.Length()endl; list.Print();coutnThe third elementis.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();双向链表NodeList.htemplate class

20、DoublyList;templatetypename Typo class ListNodeprivate:friend class Doub1yList;ListNodeO: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;mpnext=NULL;public:Type GetData();private:Type md

21、ata;ListNode *m_pprior;ListNode *m_pnext;ftemplate Type ListNode:GetData() return this-m_data;)DoubleList.h#include ListNode.h template class DoublyList public:DoublyList():head(new ListNode() /the head node point to itself head-m_ppriorshead;head-m_pnext=head;)-DoublyList() MakeEmpty(); delete head

22、; )public:void MakeEmpty () ; /make the list empty int Length(); /get the length of the list ListNode *Find(int n=0); /find the nth data ListNode * 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 t

23、he nth dataType Get(int n=0); /get the nth data void Print();/print the listprivate: ListNode *head； ;template void DoublyList:：MakeEmpty() ListNode *pmovehead-m_pnext,*pdel;while(pmove!shead)pdel=pmove;pmove=pdel-m_pnext;delete pdel;)head-m_pnexthead;head-m_pprior=head;)template int DoublyList;:Len

24、gth() ListNode *pprior=head-m_pprior,*pnext=head-m_pnext; int count0;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(n0) coutThe n is out of bo

25、undaryendl; return NULL;ListNode *pmove=head-m_pnext;or(int i=0;im_pnext; if(pmove=head)coutThe n is out of boundary bool DoublyLists:Insert(Type item,int n) i(n0)coutThe n is out of boundaryendl； return 0;)ListNode *newnode=new ListNode(item),*pmoveshead;if(newnode=NULL)coutApplication Erorr!Mendl;

26、 exit(1);)or(int i0;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 DoublyLists:Remove(int n = 0) if(n0)coutThe n is out of boundaryendl;exit(1);)ListNode *pmove=headr *pdel;

27、or(int i=0;im_pnext;if(pmove=head)coutThe n is out of boundarym_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 = 0) if(n0)coutThe n is out of boundaryendl; exit(1);)ListNode *pmovehead;or(int i=0;im

28、_pnext; if(pmovesshead)coutThe n is out of boundaryendl; exit(1); )return pmove-m_data； )template void DoublyList:Print()数据结构算法实现 ListNode *pmove=head-m_pnext; couthead;while(pmove!=head) coutm data; pmove=pmove-m_pnext; coutoverendlendlendl;template ListNode* DoublyList:FindData(Type item) ListNode

29、 *pprior=head-m_pprior,*pnext=head-m_pnext;while(pprior-m_pnext!=pnext & pprior!=pnext) /find the data in the two direction if(pprior-m_data=item)return pprior； )if(pnext-m_data=sitem) return pnext;)pprior=pprior-m_pprior;pnext=pnext-m_pnext;) coutcant find the elementendl;return NULL;Test.cpp#inclu

30、de #include -DoublyList.husing namespace std;int main()(DoublyList list;for(int i0;i20;i+)list.Insert(1*3,1);)coutwthe Length of the list is list.Length()endl; list.Print();or(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

31、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.循环链表ListNode.htemplate class CircularList;template class ListNode(private：friend class CircularList;ListNo

32、de():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.h template class CircularList public:CircularList():head(new ListNode() head-m_pnext=head;CircularList() MakeEmpty

33、();delete head;public:void MakeEmpty() ; /clear the list int Length();/get the lengthListNode *Find(Type value,int n)；:/find the nth data which isequalto valueListNode *Find(int n)；bool Insert(Type item,int n0);/find the nth data/insert the datainto the nthdata of the listType Remove(int n=0);bool R

34、emoveAll(Type item);/delete the/delete allnththedatadataswhichare equal to valueType Get(int n) ; /get the nth datavoid Print(); /print the list private:ListNode *head;template void CircularList:MakeEmpty() ListNode *pdel,*pmove=head;while(pmove-m_pnextI=head)pdelpmove-m_pnext;pmove-m_pnextspdel-m_p

35、next;delete pdel;)template int CircularList:Length() ListNode *pxnove=head;int count0;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 iaO;im_pnext;)

36、i(pmove=head) coutMThe 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 *pmovehead； int countsO;while(count!n)pmove=pmove-m_pnext;if(pmove-m_data *value) count+;if(pmove=head) coutcant

37、find the elementendl; return NULL;) return pmove； )templatetypename Typo bool CircularList:Insert(Type item, int n) if(n0)coutMThe n is out of boundaryNendl; return 0;)ListNode *pmovehead;ListNode *pnode=new ListNode(item);if(pnode=NULL)coutApplication error!endl; exit(1);or(int i=0;im_pnext； if(pmove=head)coutThe n is