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

TOC\o"1-5"\h\z目乔 11、顺序表 1Test.cpp 4单链表 5ListNode.h 5test.cpp 12双向循环链表 13NodeList.h 13DoubleList.h 14Test.cpp 20ListNode.h 21Test.cpp 28、顺序栈 29SeqStack.h 29Test・cpp 32Linkstack.h 33.顺序队列 37Test.cpp 408、链式队列 41QueueNode.h 41LinkQueue.h 42Test.cpp 449,优先级队列 45QueueNode.h 46PriorityQueue.h 47Test.cpp 5110、串 52MyString.h 52MyString.cpp 5411.ニ叉树 61BinTreeNode.h 62BinaryTree,h 66Test.cpp 7312、线索ニ叉树 74ThreadNode.h 74ThreadTree.h 75ThreadinorderIterator.h 76test•cpp 8213、堆 83MinHeap・h 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 11317、图 127MinHeap.h 127Edge・h 130Vertex.h 131Graph.h 132test.cpp 14418、排序 145QueueNode.h 149LinkQueue.h 152Sort・h 1541、顺序表Seqlist.hconstintDefaultSize=100;template<typenameType>classSeqList{public:SeqList(intsz=DefaultSize):m_nmaxsize(sz),m_ncurrentsize(-1){if(sz>0){m_elements=newType[m_nmaxsize];}}〜SeqList(){delete[]m_elements;intLength()const{returnm_ncurrentsize+l;//getthelength}intFind(Typex)const;//findthepositionintIsElement(Typex)const;//isitinthelistintInsert(Typexzinti);//insertdataintRemove(Typex);//deletedataofXintIsEmpty(){returnm_ncurrentsize==-l;}intIsFull(){returnm_ncurrentsize==m_nmaxsize-l;}TypeGet(inti){ //gettheithdatareturni<0||i>m_ncurrentsize?(cout<<Hcan*tfindtheelementn<<endlz0):m_elements[i];}voidPrint();private:Type*m_elements;constintm_nmaxsize;intm_ncurrentsize;}；template<typenameType>intSeqList<Type>::Find(Typex)const{for(inti=0;i<m_ncurrentsize;i++)if(m_elements[i]==x)returni;cout<<Hcan1tfindtheelementyouwanttofindn<<endl;return-1;}template<typenameType>intSeqList<Type>::IsElement(Typex)const{if(Find(x)==-1)return0;return1;template<typenameType>intSeqList<Type>::Insert(Typex,inti){if(i<0IIi>m_ncurrentsize+1||m_ncurrentsize==m_nmaxsize-l){cout<<ntheoperateisillegaln<<endl;return0;}m_ncurrentsize++；for(intj=m_ncurrentsize;j>i;j——){m_elements[j]=m_elements[j-1];)m_elements[i]=x;return1;}template<typenameType>intSeqList<Type>::Remove(Typex){intsize=m_ncurrentsize;for(inti=0;i<m_ncurrentsize;){if(m_elements[i]==x){for(intj=i;j<m_ncurrentsize;j++){m_elements[j]=m_elements[j+1];)m_ncurrentsize——;continue;}i++；)if(size==m_ncurrentsize){cout<<ncan11findtheelementyouwanttoremoven<<endl;return0;数据结构算法实现return1;}template<typenameType>voidSeqList<Type>::Print()for(inti=0;i<=m_ncurrentsize;i++)cout<<i+l<<n:\tn<<m_elements[i]<<endl;cout<<endl<<endl;}Test,cpp♦include<iostream>♦include"SeqList.hnusingnamespacestd;intmain(){SeqList<int>test(15);intarray[15]={2,5,8,1,9,9,7,6,4,3,2,9,7,7,9};for(inti=0;i<15;i++){test.Insert(array[i],0);}test.Insert(1,0);cout<<(test.Find(0)?ncan*tbefound"："Befoundtest.Remove(7);test・Print();test.Remove(9);)<<0<<endl<<endl;test,Print();test,Remove(0);test・Print();return0;}单链表ListNode.htempiate<typenameType>classSingleList;tempiate<typenameType>classListNode{private:friendtypenameSingleList<Type>;ListNode():m_pnext(NULL){}ListNode(constTypeitem,ListNode<Type>*next=NULL):m_data(item),m_pnext(next){}〜ListNode(){m_pnext=NULL;}public:TypeGetData();friendostream&operator<<<Type>(ostream&,ListNode<Type>&);private:Typem_data;ListNode*m_pnext;}；tempiate<typenameType>TypeListNode<Type>::GetData(){returnthis->m_data;}tempiate<typenameType>ostreamSoperator<<(ostreamSos,ListNode<Type>&out){os<<out.m_data;returnos;}SingleList,h♦include"ListNode.h"tempiate<typenameType>classSingleList{public:SingleList():head(newListNode<Type>()){}〜SingleList(){MakeEmpty();deletehead;}public:voidMakeEmpty();intLength();ListNode<Type>*Find(Typevalue,intListNode<Type>*Find(intn);boolInsert(Typeitem,intn=0);TypeRemove(intn=0);//makethelistempty//getthelengthn);//findthdnthdatawhichisequaltovalue//findthenthdata//insertthedatainthenthposition//removethenthdataboolRemoveAll(Typeitem);TypeGet(intn);voidPrint();//removeallthedatawhichisequaltoitem//getthenthdata//printthelistprivate:ListNode<Type>*head;}；tempiate<typenameType>voidSingleList<Type>::MakeEmpty(){ListNode<Type>*pdel;while(head->m_pnext!=NULL){pdel=head->m_pnext;head->m_pnext=pdel->m_pnext;deletepdel;tempiate<typenameType>intSingleList<Type>::Length(){ListNode<Type>*pmove=head->m_pnext;intcount=0;while(pmove!=NULL){pmove=pmove一〉m_pnext;count++；数据结构算法实现returncount;}tempiate<typenameType>ListNode<Type>*SingleList<Type>if(n<0){cout<<nThenisoutofboundaryn<<endl;returnNULL;}ListNode<Type>*pmove=head->m_pnext;for(inti=0;i<n&&pmove;i++){pmove=pmove->m_pnext;}if(pmove==NULL){cout<<nThenisoutofboundaryn<<endl;returnNULL;}returnpmove;}tempiate<typenameType>ListNode<Type>*SingleList<Type>if(n<l){cout<<nThenisillegaln<<endl;returnNULL;}ListNode<Type>*pmove=head;intcount=0;while(count!=n&&pmove){pmove=pmove->m_pnext;if(pmove->m_data==value){count++;::Find(intn){::Find(Typevalue,intn){}if(pmove==NULL){cout<<ncan*tfindtheelementn<<endl;returnNULL;}returnpmove;)template<typenameType>boolSingleList<Type>::Insert(Typeitem,intn){if(n<0){coutくく“Thenisillegal"<<endl;return0;}ListNode<Type>*pmove=head;ListNode<Type>*pnode=newListNode<Type>(item);if(pnode==NULL){cout<<"Applicationerror!"<<endl;return0;}for(inti=0;i<n&&pmove;i++){pmove=pmove->m_pnext;}if(pmove==NULL){cout<<"thenisillegal"<<endl;return0;}pnode->m_pnext=pmove->m_pnext;pmove->m_pnext=pnode;数据结构算法实现return1;}tempiate<typenameType>boolSingleList<Type>::RemoveAll(Typeitem){ListNode〈Type>*pmove=head;ListNode<Type>*pdel=head->m_pnext;while(pdel!=NULL){if(pdel->m_data==item){pmove->m_pnext=pdel->m_pnext;deletepdel;pdel=pmove->m_pnext;continue;}pmove=pmove->m_pnext;pdel=pdel->m_pnext;}return1;}tempiate<typenameType>TypeSingleList<Type>::Remove(intn){if(n<0){cout<<ncan11findtheelementn<<endl;exit(1);}ListNode<Type>*pmove=headz*pdel;for(inti=0;i<n&&pmove->m_pnext;i++){pmove=pmove->m_pnext;}if(pmove->m_pnext==NULL){cout<<ncan*tfindtheelementn<<endl;数据结构算法实现exit(1);}pdel=pmove->m_pnext;pmove->m_pnext=pdel->m_pnext;Typetemp=pdel->m_data;deletepdel;returntemp;}tempiate<typenameType>TypeSingleList<Type>::Get(intif(n<0){cout<<nThenisoutofboundaryn<<endl;exit(1);)ListNode<Type>*pmove=head->m_pnext;for(inti=0;i<n;i++){pmove=pmove->m_pnext;if(NULL==pmove){cout<<nThenisoutofboundaryn<<endl;exit(1);}}returnpmove->m_data;}tempiate<typenameType>voidSingleList<Type>::Print()ListNode<Type>*pmove=head->m_pnext;cout<<Mheadn;while(pmove){cout<<">"<<pmove->m_data;n){pmove=pmove->m_pnext;}cout<<n >overn<<endl<<endl<<endl;test.cpp♦include<iostream>usingnamespacestd;♦include"SingleList.h"intmain()(SingleList<int>list;for(inti=0;i<20;i++){list.Insert(i*3fi);}for(inti=0;i<5;i++){list.Insert(3,i*3);}cout<<"theLengthofthelistis"<<list.Length()<<endl।list.Print();list.Remove(5);cout<<"theLengthofthelistis"<<list.Length()<<endl।list.Print();2008-9-3list.RemoveAll(3);cout<<ntheLengthofthelistisn<<list.Length()<<endl;list.Print();cout<<nThethirdelementisn<<list.Get(3)<<endl;cout<<*list.Find(18,1)<<endl;list.Find(100);list.MakeEmpty();cout<<ntheLengthofthelistis"<<list.Length()<<endl;list.Print();return0;双向循环链表NodeList.htempiate<typenameType>classDoublyList;tempiate<typenameType>classListNode{2008-9-3private:friendclassDoublyList<Type>;ListNode():m_pprior(NULL),m_pnext(NULL){}ListNode(constTypeitem,ListNode<Type>*prior=NULLzListNode<Type>*next=NULL):m_data(item),m_pprior(prior),m_pnext(next){}〜ListNode(){m_pprior=NULL;m_pnext=NULL;}public:TypeGetData();private:Typem_data;ListNode*m_pprior;ListNode*m_pnext;}；tempiate<typenameType>TypeListNode<Type>::GetData(){returnthis->m_data;DoubleList・h♦include"ListNode・h"//theheadnodepointtoitselftempiate<typenameType>classDoublyList{public://theheadnodepointtoitselfDoublyList():head(newListNode<Type>()){head->m_pprior=head;head->m_pnext=head;}-DoublyList(){MakeEmpty();deletehead;}public:voidMakeEmpty(); //makethelistemptyintLength();//getthelengthofthelistListNode<Type>*Find(intn=0);//findthenthdataListNode<Type>*FindData(Typeitem);//findthedatawhichisequaltoitemboolInsert(Typeitem,intn=0); //insertiteminthenthdataTypeRemove(intn=0);//deletethenthdataTypeGet(intn=0);//getthenthdatavoidPrint(); //printthelistprivate:ListNode<Type>*head;)；template<typenameType>voidDoublyList<Type>::MakeEmpty(){ListNode<Type>*pmove=head->m_pnext,*pdel;while(pmove!=head){pdel=pmove;pmove=pdel->m_pnext;deletepdel;}head-〉m_pnext=head;head->m_pprior=head;}tempiate<typenameType>intDoublyList<Type>::Length(){ListNode<Type>*pprior=head->m_ppriorz*pnext=head->m_pnext;intcount=0;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;}returncount;}tempiate<typenameType>ListNode<Type>*DoublyList<Type>::Find(intn=0){if(n<0){cout<<nThenisoutofboundaryn<<endl;returnNULL;)ListNode<Type>*pmove=head->m_pnext;for(inti=0;i<n;i++){pmove=pmove->m_pnext;if(pmove==head){16cout<<nThenisoutofboundaryn<<endl;returnNULL;}}returnpmove;}tempiate<typenaineType>boolDoublyList<Type>::Insert(Typeitem,intn){if(n<0){cout<<nThenisoutofboundaryn<<endl;return0;}ListNode<Type>*newnode=newListNode<Type>(item),*pmove=head;if(newnode==NULL){cout<<nApplicationErorr!n<<endl;exit(1);)for(inti=0;i<n;i++){ //findthepositionforinsertpmove=pmove->m_pnext;if(pmove==head){cout<<nThenisoutofboundaryn<<endl;return0;}}//insertthedatanewnode->m_pnext=pmove->m_pnext;newnode-〉m_pprior=pmove;pmove->m_pnext=newnode;newnode->m_pnext->m_pprior=newnode;数据结构算法实现return1;}tempiate<typenameType>TypeDoublyList<Type>::Remove(intif(n<0){cout<<nThenisoutofboundaryn<<endl;exit(1);}ListNode<Type>*pmove=headz*pdel;for(inti=0;i<n;i++){ //findthepositionfordeletepmove=pmove->m_pnext;if(pmove==head){cout<<nThenisoutofboundaryn<<endl;exit(1);//deletethedatapdel=pmove;pmove->m_pprior->m_pnext=pdel->m_pnext;pmove->m_pnext->m_pprior=pdel->m_pprior;Typetemp=pdel->m_data;deletepdel;returntemp;)template<typenameType>TypeDoublyList<Type>::Get(intnif(n<0){coutく<”Thenisoutofboundaryn<<endl;exit(1);n=0){0)(数据结构算法实现)ListNode<Type>*pmove=head;for(inti=0;i<n;i++){pmove=pmove->m_pnext;if(pmove==head){cout<<nThenisoutofboundaryH<<endl;exit(1);}}returnpmove->m_data;)tempiate<typenameType>voidDoublyList<Type>::Print(){ListNode<Type>*pmove=head->m_pnext;cout<<nheadn;while(pmove!=head){cout<<n>n<<pmove->m_data;pmove=pmove->m_pnext;}cout<<n >overn<<endl<<endl<<endl;directiontempiate<typenameType>ListNode<Type>*DoublyList<Type>::FindData(Typeitem)ListNode<Type>*pprior=head->m_pprior,*pnext=head->m_pnext;directionwhile(pprior->m_pnext!=pnext&&pprior!=pnext){//findthedatainthetwoif(ppriorー〉m_data==item){returnpprior;}if(pnext->m_data==item){数据结构算法实现returnpnext;}pprior=pprior->m_pprior;pnext=pnext->m_pnext;}cout<<ncan11findtheelementn<<endl;returnNULL;}Test,cpp♦include<iostream>♦include"DoublyList・h”usingnamespacestd;intmain(){DoublyList<int>list;for(inti=0;i<20;i++){list.Insert(i*3,i);}cout<<ntheLengthofthelistisn<<list.Length()<<endllist.Print();for(inti=0;i<5;i++){list.Insert(3ri*3);}cout<<ntheLengthofthelistisn<<list.Length()<<endl2008-9-3list・Print();list・Remove(5);cout<<ntheLengthofthelistisn<<list.Length()<<endl,list,Print();cout<<list,FindData(54)->GetData()<<endl;cout<<nThethirdelementisn<<list.Get(3)<<endl;list.MakeEmpty();cout<<ntheLengthofthelistisn<<list.Length()<<endl,list,Print();return0;单项循环链表ListNode,htempiate<typenameType>tempiate<typenameType>classCircularList;tempiate<typenameType>classListNode{2008-9-3private:friendclassCircularList<Type>;ListNode():m_pnext(NULL){}ListNode(constTypeitem,ListNode<Type>*next=NULL):〜ListNode(){m_pnext=NULL;}private:Typem_data;ListNode*m_pnext;}；CircularList.h♦include"ListNode・h”tempiate<typenameType>classCircularList{public:CircularList():head(newListNode<Type>()){head->m_pnext=head;}-CircularList(){MakeEmpty();deletehead;}public:voidMakeEmpty();//clearthelistm_data(item),m_pnext(next){}ListNode<Type>*FindListNode<Type>*Find(intn);boolInsert(Typeitem,intn=0);TypeRemove(intn=0);boolRemoveAll(Typeitem);TypeGet(intn);//getthenthintLength();//getthelengthListNode<Type>*Find(Typevalue,intn); //findthenthdatawhichisequaltovalue//findthenthdata//insertthedataintothenthdataofthelist//deletethenthdata//deleteallthedataswhichareequaltovaluedatavoidPrint();//printthelistprivate:ListNode<Type>*head;}；tempiate<typenameType>voidCircularList<Type>::MakeEmpty(){ListNode<Type>*pdel,*pmove=head;while(pmove->m_pnext!=head){pdel=pmove->m_pnext;pmove->m_pnext=pdel->m_pnext;deletepdel;tempiate<typenameType>intCircularList<Type>::Length(){ListNode<Type>*pmove=head;intcount=0;while(pmove->m_pnext!=head){pmove=pmove->m_pnext;count++；数据结构算法实现returncount;}tempiate<typenameType>ListNode<Type>*CircularList<Type>if(n<0){cout<<nThenisoutofboundaryn<<endl;returnNULL;}ListNode<Type>*pmove=head->m_pnext;for(inti=0;i<n&&pmove!=head;i++){pmove=pmove->m_pnext;}if(pmove==head){cout<<nThenisoutofboundaryn<<endl;returnNULL;}returnpmove;}tempiate<typenameType>ListNode<Type>*CircularList<Type>if(n<l){cout<<nThenisillegaln<<endl;returnNULL;}ListNode<Type>*pmove=head;intcount=0;while(count!=n){pmove=pmove->m_pnext;if(pmove->m_data==value){count++;::Find(intn){::Find(Typevalue,intn){if(pmove==head){cout<<ncan11findtheelementn<<endl;returnNULL;}returnpmove;item,intitem,intn){tempiate<typenameType>boolCircularList<Type>::Insert(Typeif(n<0){cout<<nThenisoutofboundaryn<<endl;return0;)ListNode<Type>*pmove=head;ListNode<Type>*pnode=newListNode<Type>(item);if(pnode==NULL){cout<<nApplicationerror!u<<endl;exit(1);}for(inti=0;i<n;i++){pmove=pmove->m__pnext;if(pmove==head){cout<<nThenisoutofboundaryM<<endl;return0;}}pnode->m_pnext=pmove->m_pnext;pmove->m__pnext=pnode;return1;tempiate<typenameType>boolCircularList<Type>::RemoveAll(Typeitem){ListNode〈Type>*pmove=head;ListNode<Type>*pdel=head->m_pnext;while(pdel!=head){if(pdel->m_data==item){pmove->m_pnext=pdel->m_pnext;deletepdel;pdel=pmove->m_pnext;continue;pmove=pmove->m_pnext;pdel=pdel->m_pnext;}return1;}tempiate<typenameType>TypeCircularList<Type>::Remove(intn){if(n<0){cout<<ncan11findtheelementn<<endl;exit(1);}ListNode<Type>*pmove=headz*pdel;for(inti=0;i<n&&pmove->m_pnext!=head;i++){pmove=pmove->m_pnext;}if(pmove->m_pnext==head){cout<<ncan*tfindtheelementn<<endl;exit(1);}pdel=pmove->m_pnext;pmove->m_pnext=pdel->m_pnext;Typetemp=pdel->m_data;deletepdel;returntemp;}tempiate<typenameType>TypeCircularList<Type>::Get(intif(n<0){cout<<nThenisoutofboundaryn<<endl;exit(1);)ListNode<Type>*pmove=head->m_pnext;for(inti=0;i<n;i++){pmove=pmove->m_pnext;if(pmove==head){cout<<nThenisoutofboundaryn<<endl;exit(1);}}returnpmove->m_data;}tempiate<typenameType>voidCircularList<Type>::Print()ListNode<Type>*pmove=head->m_pnext;cout<<Mheadn;while(pmove!=head){cout<<">"<<pmove->m_data;n){pmove=pmove->m_pnext;}cout<<n >overn<<endl<<endl<<endl;Test,cpp♦include<iostream>♦includenCircularList・h”usingnamespacestd;intmain()CircularList<int>list;for(inti=0;i<20;i++){list.Insert(i*3zi);}cout<<ntheLengthofthelist.Print();for(inti=0;i<5;i++){list.Insert(3,i*3);)cout<<ntheLengthofthelist,Print();listlistisisn<<list.Length()<<endl,n<<list.Length()<<endl,list.Remove(5);cout<<ntheLengthofthelistisn<<list.Length()<<endl,2008-9-3list・Print();list・RemoveAll(3);cout<<ntheLengthofthelistisn<<list.Length()<<endllist,Print();cout<<nThethirdelementisn<<list.Get(3)<<endl;list.MakeEmpty();cout<<ntheLengthofthelistisn<<list.Length()<<endllist.Print();return0;顺序栈SeqStack.htempiate<typenameType>classSeqStack{public:SeqStack(intsz):m_ntop(-1),m_nMaxSize(sz){m_pelements=newType[sz];if(m_pelements==NULL){2008-9-3cout<<nApplicationError!n<<endl;exit(1);}}〜SeqStack(){delete[]m_pelements;}public:voidPush(constTypeitem);//pushdataTypePop0;//popdataTypeGetTop()const;//getdatavoidPrint();//printthestackvoidMakeEmpty(){//makethestackemptym__ntop=-l;)boolIsEmpty()const{returnm_ntop==-l;}boolIsFull()const{returnm_ntop==m_nMaxSize-l;}private:intm_ntop;Type*m_pelements;intm_nMaxSize;2008-9-3};template<typenameType>voidSeqStack<Type>::Push(constTypeitem){if(IsFull()){cout<<nThestackisfull!u<<endl;return;}m_pelements[++m_ntop]=item;)template<typenameType>TypeSeqStack<Type>::Pop(){if(IsEmpty()){coutく<"Thereisnoelement!"<<endl;exit(1);}returnm_pelements[m_ntop——];}template<typenameType>TypeSeqStack<Type>::GetTop()const{if(IsEmpty()){cout<<"Thereisnoelement!"<<endl;exit(1);}returnm_pelements[m_ntop];)template<typenameType>voidSeqStack<Type>::Print(){cout<<"bottom";for(inti=0;i<=m_ntop;i++){cout<<" >"<<m_pelements[i];}cout<<n >topn<<endl<<endl<<endlTest,cpp#include<iostream>usingnamespacestd;♦include"SeqStack・h”intmain(){SeqStack<int>stack(10);intinit[10]={lz2z6,9,0,3,8,7,5,4for(inti=0;i<10;i++){stack.Push(init[i]);}stack.Print();stack.Push(88);cout<<stack.Pop()<<endl;stack.Print();stack.MakeEmpty();stack.Print();stack.Pop();return0;、链式栈StackNode,htempiate<typenameType>classLinkstack;tempiate<typenameType>classStackNode{private:friendclassLinkStack<Type>;StackNode(Typedt,StackNode<Type>*next=NULL)private:Typem_data;StackNode<Type>*m_pnext;}；Linkstack.h♦include"StackNode.h":m_data(dt),m_pnext(next){}tempiate<typenameType>classLinkstack{public:LinkStack():m_ptop(NULL){}〜LinkStack(){MakeEmpty();}public:voidMakeEmpty(); //makethestackemptyvoidPush(constTypeitem);//pushthedataTypePop(); //popthedataTypeGetTop()const; //getthedatavoidPrint(); //printthestackboolIsEmpty()const{returnm_ptop==NULL;)private:StackNode<Type>*m_ptop;)；template<typenameType>voidLinkStack<Type>::MakeEmpty(){StackNode<Type>*pmove;while(m_ptop!=NULL){pmove=m_ptop;m_ptop=m_ptop->m_pnext;deletepmove;2008-9-3tempiate<typenameType>voidLinkStack<Type>::Push(constTypeitem){m_ptop=newStackNode<Type>(item,m_ptop);}tempiate<typenameType>TypeLinkStack<Type>::GetTop()const{if(IsEmpty()){cout<<nThereisnoelements!n<<endl;exit(1);)returnm_ptop->m_data;}tempiate<typenameType>TypeLinkStack<Type>::Pop(){if(IsEmpty()){cout<<nThereisnoelements!n<<endl;exit(1);}StackNode<Type>*pdel=m_ptop;m__ptop=m_ptop->m_pnext;Typetemp=pdel->m_data;deletepdel;returntemp;}tempiate<typenameType>voidLinkStack<Type>::Print(){StackNode<Type>*pmove=m_ptop;cout<<,,buttomn;while(pmove!=NULL){cout<<" >"<<pmove->m_data;pmove=pmove->m_pnext;}cout<<n >topn<<endl<<endl<<endl;Test.cpp♦include<iostream>usingnamespacestd;♦includenLinkStack.hnintmain(){LinkStack<int>stack;intinit[10]={l,3,5,7,4,2,8,0,6,9};for(inti=0;i<10;i++){stack.Push(init[i]);)stack.Print();cout<<stack.Pop()<<endl;stack.Print();cout<<stack.GetTop()<<endl;stack.Print();cout<<stack.Pop()<<endl;stack.Print();stack.MakeEmpty();stack.Print();stack.Pop();return0;).顺序队列SeqQueue.htemplate<typenameType>classSeqQueue{public:SeqQueue(intsz):m_nrear(0)tm_nfront(〇),m_ncount(0),m_nMaxSize(sz){m_pelements=newType[sz];if(m_pelements==NULL){cout<<nApplicationError!n<<endl;exit(1);}}〜SeqQueue(){delete[]m_pelements;数据结构算法实现)//makethequeueempty//insertdata//deletedata//getdata//printthequeue//makethequeueempty//insertdata//deletedata//getdata//printthequeueboolIsEmpty();boolIsFull();boolAppend(constTypeitem)TypeDelete();TypeGet();voidPrint();private:intm_nrear;intm_nfront;intm_ncount;intm_nMaxSize;Type*m_pelements;SeqQueue<Type>::MakeEmptySeqQueue<Type>::MakeEmpty(){template<typenameType>voidthis->m_ncount=0;this->m_nfront=0;this->m_nrear=0;)tempiate<typenameType>boolreturnm_ncount==0;)SeqQueue<Type>::IsEmpty(){template<typenameType>boolSeqQueue<Type>::IsFull(){returnm_ncount==m_nMaxSize;2008-9-3数据结构算法实现}tempiate<typenameType>boolSeqQueue<Type>::Append(constif(IsFull()){cout<<nThequeueisfull!n<<endl;return0;}m_pelements[m_nrear]=item;m_nrear=(m_nrear+l)%m_nMaxSize;m_ncount++;return1;}tempiate<typenameType>TypeSeqQueue<Type>::Delete(){if(IsEmpty()){cout<<nThereisnoelement!n<<endl;exit(1);}Typetemp=m_pelements[m_nfront];m_nfront=(m_nfront+1)%m_nMaxSize;m_ncount--;returntemp;)tempiate<typenameType>TypeSeqQueue<Type>::Get(){if(IsEmpty()){cout<<nThereisnoelement!n<<endl;exit(1);}returnm_pelements[m_nfront];Typeitem){数据结构算法实现}template<typenameType>voidSeqQueue<Type>::Print〇{cout<<nfrontn;for(inti=0;i<m_ncount;i++){cout<<n >n<<m_pelements[(m_nfront+i+m_nMaxSize)}cout<<n>rearn<<endl<<endl<<endl;}Test・cpp♦include<iostream>usingnamespacestd;♦include"SeqQueue.h"intmain(){SeqQueue<int>queue(10);intinit[10]={lz6,9,0,2,5,8,3,フ,4};for(inti=0;i<5;i++){queue.Append(init[i]);}queue.Print();cout<<queue.Delete()<<endl;queue.Print();%m__nMaxSize];for(inti=5;i<10;i++){queue.Append(init[i]);)queue.Print();cout<<queue.Get()<<endl;queue.MakeEmpty();queue.Print();queue.Append(1);queue.Print();return0;}8、链式队列QueueNode.htempiate<typenameType>classLinkQueue;tempiate<typenameType>classQueueNode{private:friendclassLinkQueue<Type>;QueueNode(constTypeitem,QueueNode<Type>*next=NULL):m_data(item),m_pnext(next){}private:Typem_data;QueueNode<Type>*m_pnext;}；LinkQueue.h♦includenQueueNode.hntempiate<typenameType>classLinkQueue{public:LinkQueue():m__prear(NULL),m_pfront(NULL){}〜LinkQueue(){MakeEmpty();voidAppend(constTypeTypeDelete();TypeGetFront();voidMakeEmpty();voidPrint();item); //insertdata//deletedata//getdata//makethequeueempty//printthequeueboolIsEmpty()const{returnm_pfront==NULL;}private:2008-9-3QueueNode<Type>*m_prearz*m_pfront;}；tempiate<typenameType>voidLinkQueue<Type>::MakeEmpty(){QueueNode<Type>*pdel;while(m_pfront){pdel=m_pfront;m_pfront=m_pfront->m_pnext;deletepdel;}}tempiate<typenameType>voidLinkQueue<Type>::Append(constif(m_pfront==NULL){m_pfront=m_prear=newQueueNode<Type>(item);}else{m_prear=m_prearー〉m_pnext=newQueueNode<Type>(item);}}template<typenameType>TypeLinkQueue<Type>::Delete(){if(IsEmpty()){cout<<nThereisnoelement!n<<endl;exit(1);}QueueNode<Type>*pdel=m_pfront;Typetemp=m_pfront->m_data;m_pfront=m_pfront->m_pnext;deletepdel;Typeitem){数据结构算法实现returntemp;}tempiate<typenameType>TypeLinkQueue<Type>::GetFront()if(IsEmpty()){cout<<nThereisnoelement!n<<endl;exit(1);}returnm_pfront->m_data;}tempiate<typenameType>voidLinkQueue<Type>::Print(){QueueNode<Type>*pmove=m_pfront;cout<<nfrontH;while(pmove){cout<<n >n<<pmove->m_data;pmove=pmove->m_pnext;}cout<<n >rearn<<endl<<endl<<endl;Test.cpp♦include<iostream>usingnamespacestd;♦include"LinkQueue.hn2008-9-3intmain(){LinkQueue<int>queue;intinit[10]={l,3,6,8,9,2,0,5,4,7};for(inti=0;i<10;i++){queue.Append(init[i]);}queue.Print();queue.Delete();queue.Print();cout<<queue.GetFront()<<endl;queue.Print();queue.MakeEmpty();queue.Print();queue.Delete();return0;)9、优先级队列〃用队列实现优先级队列QueueNode,htempiate<typenameType,typenameCmp>classPriorityQueue;template<typenameType,typenameCmp>classQueueNode{private:friendclassPriorityQueue<Type,Cmp>;QueueNode(constTypeitem,QueueNode<Type,Cmp>*next=NULL):m_data(item),m_pnext(next){}private:Typem_data;QueueNode<Type,Cmp>*m_pnext;)；Compare.htempiate<typenameType>classCompare{ //处理——般比较大小public:staticboolIt(Typeiteml,Typeitem2);}；tempiate<typenameType>boolCompare<Type>::It(Typeiteml,Typeitem2){returniteml<item2;structSpecialData{friendostream&operator<<(ostream&,SpecialData&);intm_ntenor;intm_npir;)；ostream&operator<<(ostream&oszSpecialData&out){os<<out.m_ntenor<<HH<<out.m_npir;returnos;}classSpecialCmp{ //处理特殊比较大小,用户可添加适当的类public:staticboolIt(SpecialDataiteml,SpecialDataitem2);}；boolSpecialCmp::It(SpecialDataiteml,SpecialDataitem2){returniteml.m_npir<item2.m_npir;}PriorityQueue.h♦include"QueueNode.h"♦include"Compare.h"template<typenameType,typenameCmp>classPriorityQueue{//CmpisDesignedforcomparepublic:

PriorityQueue():m_prear(NULL),m_pfront(NULL){}^PriorityQueue(){MakeEmpty();//makethequeueempty//insertdata//deletedata//getdata//printthequeuevoidMakeEmpty();//makethequeueempty//insertdata//deletedata//getdata//printthequeuevoidAppend(constTypeitem)TypeDelete();TypeGetFront();voidPrint();boolIsEmpty()const{returnm_pfront==NULL;private:QueueNode<Type,Cmp>*m_prearz*m_pfront;)；template<typenameType,typenameCmp>voidPriorityQueue<Type,Cmp>::MakeEmpty(){QueueNode<Type,Cmp>*pdel;while(m_pfront){pdel=m_pfront;m_pfront=m_pfront->m_pnext;deletepdel;}item){}item){tempiate<typenameType,typenameCmp>voidPriorityQueue<TypezCmp>::Append(constTypeif(m_pfront==NULL){m_pfront=m_prear=newQueueNode<TypezCmp>(item);}else{m_prear=m_prear->m_pnext=newQueueNode<TypezCmp>(item);}}tempiate<typenameTypeztypenameCmp>TypePriorityQueue<TypezCmp>::Delete(){if(IsEmpty()){cout<<nThereisnoelements!n<<endl;exit(1);}QueueNode<TypezCmp>*pdel=m_pfrontz*pmove=m_pfront;while(pmove->m_pnext){//gettheminimizepriority1sdata//cmp::Itisusedforcomparethetwodatazifthefrontone//islessthantheback,thenreturn1if(Cmp::It(pmove->m_pnext->m_datazpdel->m_pnext->m_data)){pdel=pmove;}pmove=pmove->m__pnext;}pmove=pdel;pdel=pdel->m__pnext;pmove->m_pnext=pdel->m_pnext;Typetemp=pdel->m_data;deletepdel;returntemp;数据结构算法实现}tempiate<typenameType,typenameCmp>TypePriorityQueue<Type,Cmp>::GetFront(){if(IsEmpty()){cout<<nThereisnoelements!n<<endl;exit(1);}QueueNode<TypezCmp>*pdel=m_pfront,*pmove=m_pfront->m_pnext;while(pmove){//gettheminimizepriority1sdataif(Cmp::It(pmove->m_data,pdel->m_data)){pdel=pmove;}pmove=pmove->m_pnext;}returnpdel->m_data;}tempiate<typenameType,typenameCmp>voidPriorityQueue<Type,Cmp>::Print(){QueueNode<Type,Cmp>*pmove=m_pfront;cout<<nfrontn;while(pmove){cout<<n >n<<pmove->m_data;pmove=pmove-〉m_pnext;}cout<<n >rearu<<endl<<endl<<endl;Test・cpp♦include<iostream>♦i