數(shù)據(jù)結(jié)構(gòu)C++算法(代碼)

TOC\o"1-5"\h\z目錄 1\o"CurrentDocument"1、順序表 1\o"CurrentDocument"Seqlist.h 1\o"CurrentDocument"Test.cpp 7\o"CurrentDocument"單鏈表 9\o"CurrentDocument"ListNode.h 9\o"CurrentDocument"test.cpp 22\o"CurrentDocument"雙向鏈表 25\o"CurrentDocument"循環(huán)鏈表 40\o"CurrentDocument"ListNode.h 40\o"CurrentDocument"CircularList.h 41\o"CurrentDocument"Test.cpp 52\o"CurrentDocument"順序棧 55\o"CurrentDocument"Test.cpp 60\o"CurrentDocument"鏈?zhǔn)綏?61\o"CurrentDocument"LinkStack.h 63\o"CurrentDocument"Test.cpp 67\o"CurrentDocument"7.順序隊(duì)列 69\o"CurrentDocument"Test.cpp 758、鏈?zhǔn)疥?duì)歹ij 77\o"CurrentDocument"QueueNode.h 77\o"CurrentDocument"LinkQueue.h 78\o"CurrentDocument"9、優(yōu)先級(jí)隊(duì)列 85\o"CurrentDocument"QueueNode.h 85\o"CurrentDocument"Test.cpp 94\o"CurrentDocument"10、串 97\o"CurrentDocument"MyString.h 97\o"CurrentDocument"MyString.cpp 100\o"CurrentDocument"11、二叉樹(shù) 117\o"CurrentDocument"BinTreeNode.h 117\o"CurrentDocument"Test.cpp 138\o"CurrentDocument"12、線索二叉樹(shù) 141\o"CurrentDocument"ThreadNode.h 141\o"CurrentDocument"ThreadTree.h 143\o"CurrentDocument"13、堆 157\o"CurrentDocument"MinHeap.h 157\o"CurrentDocument"14、哈夫曼樹(shù) 166\o"CurrentDocument"BinTreeNode.h 166\o"CurrentDocument"BinaryTree.h 169\o"CurrentDocument"Test.cpp 182\o"CurrentDocument"QueueNode.h 183\o"CurrentDocument"LinkQueue.h 184\o"CurrentDocument"BTreeNode.h 211\o"CurrentDocument"BTree.h 215\o"CurrentDocument"test.cpp 239\o"CurrentDocument"17、圖 242\o"CurrentDocument"MinHeap.h 242Edge.h 247\o"CurrentDocument"Vertex.h 248\o"CurrentDocument"Graph,h 250\o"CurrentDocument"test.cpp 27518、排序 278\o"CurrentDocument"Data.h 278\o"CurrentDocument"LinkQueue.h 289\o"CurrentDocument"Sort.h 2941、順序表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;)intFind(Typex)const;intIsElement(Typex)const;intInsert(Typex,inti);intRemove(Typex);intIsEmpty(){returnm_ncurrentsize==-l)intIsFull(){returnm_ncurrentsize==m_i)//getthelength//findthepositionofx//isitinthelist//insertdata//deletedatanmaxsize-1;TypeGet(inti){//gettheithdatareturni<0||i>m_ncurrentsize?(cout<<"can'tfindtheelement"<<endl,0):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<<"can'tfindtheelementyouwanttofcout<<"can'tfindthereturn-1;}template<typenameType>intSeqList<Type>::IsElement(Typex)const{if(Find(x)==-l)return0;return1;}template<typenameType>intSeqList<Type>::Insert(Typex,inti){if(i<0||i>m_ncurrentsize+l||m_ncurrentsize==m_nmaxsize-l){cout<<"theoperateisillegal"<<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>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];::Remove(Typex){m_ncurrentsize―;continue;}i++；)if(size==m_ncurrentsize){cout<<"can'tfindtheelementyouwantreturn0;)return1;}template<typenameType>voidSeqList<Type>for(inti=0;i<=m_ncurrentsize;i++)cout<<i+l<<":\t"<<m_elements[i]<<endl;toremove”<<endl;::Print(){cout?endl?endl;}Test.cpp#include<iostream>#include"SeqList.h"usingnamespacestd;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)?"can'tbefound":"Betest.Remove(7);test.Print();test.Remove(9);test.Print();test.Remove(0);test.Print();return0;}單鏈表foundn)<<0<<endl<<endl;ListNode.htemplate<typenameType>classSingleList;template<typenameType>classListNode{private:friendtypenameSingleList<Type>;ListNode():m_pnext(NULL){}ListNode(constTypeitem,ListNode<Type>?ListNode()m_pnext=NULL;*next=NULL):m_data(item),m_pnext(next){}pxiblic:TypeGetData();friendostream&operator<<<Type>(?streams,ListNode<Type>&);private:Typem_data;ListNode*m_pnext;}；template<typenameType>TypeListNode<Type>::GetData(){returnthis->m_data;}template<typenameType>ostream&operator<<(ostream&os,ListNode<Type>&out){os<<out.m_data;returnos;}SingleList.h#include"ListNode.h"template<typenameType>classSingleList{pxiblic:SingleList():head(newListNode<Type>()){}~SingleList(){MakeEmpty();deletehead;)public:voidMakeEmpty();//makethelistemptyintLength();intLength();ListNode<Type>*Find(intn);boolInsert(Typeitem,intn=0);TypeRemove(intn=0);boolRemoveAl1(Typeitem);TypeGet(intn);voidPrint();//getthelengthListNode<Type>*Find(Typevalue,intn);//findthdnthdatawhichisequaltovalue//findthenthdata//insertthedatainthenthposition//removethenthdata//removeallthedatawhichisequaltoitem//getthenthdata//printthelistprivate:ListNode<Type>*head;}；template<typenameType>voidSingleList<Type>::MakeEmpty(){ListNode<Type>*pdel;while(head->m_pnext!=NULL){pde1=head->m_pnext;head->m_pnext=pde1->m_pnext;deletepdel;))template<typenameType>intSingleList<Type>::Length(){ListNode<Type>*pmove=head->m_pnext;intcount=0;while(pmove!=NULL){pmove=pmove->m_pnext;count++;)returncount;}template<typenameType>ListNode<Type>*SingleList<Type>::Find(intn){if(n<0){cout<<"Thenisoutofboundary"<<endl;returnNULL;)ListNode<Type>*pmove=head->m_pnext;for(inti=0;i<n&&pmove;i++){pmove=pmove->m_pnext;)if(pmove==NULL){cout<<"Thenisoutofboundary"<<endl;returnNULL;)returnpmove;)template<typenameType>ListNode<Type>*SingleList<Type>::Find(Typevalue,intn){if(n<l){cout<<"Thenisillegal"<<endl;returnNULL;)ListNode<Type>*pmove=head;intcount=0;while(count!=n&&pmove){pmove=pmove->m_pnext;if(pmove->m_data==value){count++;}if(pmove==NULL){cout<<"can'tfindtheelement"<<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;2008-9-3return0;)pnode->m_pnext=pmove->m_pnext;pmove->m_pnext=pnode;return1;}template<typenameType>boolSingleList<Type>: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;:RemoveAll(Typeitem){continue;}pmove=pmove->m_pnext;pdel=pdel->m_pnext;)return1;}template<typenameType>TypeSingleList<Type>:if(n<0){cout<<"can'tfindtheelement"<<endl;exit(1);)ListNode<Type>*pmove=head,*pdel;for(inti=0;i<n&&pmove->m_pnext;i++){:Remove(intn){pmove=pmove->m_pnext;)if(pmove->m_pnext==NULL){cout<<"can'tfindtheelement"<<endl;exit(1);)pde1=pmove->m_pnext;pmove->m_pnext=pdel->m_pnext;Typetemp=pdel->m_data;deletepdel;returntemp;}template<typenameType>TypeSingleList<Type>if(n<0){cout<<"Thenisoutofboundary"<<endl;exit(1);)ListNode<Type>*pmove=head->m_pnext;for(inti=0;i<n;i++){pmove=pmove->m_pnext;if(NULL==pmove){cout<<"Thenisoutofboundary"<<endl;exit(1);})returnpmove->m_data;}template<typenameType>voidSingleList<Type>::：Print(){ListNode<Type>*pmove=head->m_pnextcout<<"headn;while(pmove){cout<<" >"<<pmove->m_data;pmove=pmove->m_pnext;)cout<<" >over"<<endl<<endl<<endl;}test.cpp#include<iostream>usingnamespacestd;#include"SingleList.h"intmain()(SingleList<int>list;for(inti=0;i<20;i++){list.Insert(i*3,i);}for(inti=0;i<5;i++){list.Insert(3,i*3);)cout<<"theLengthofthelist.Print();list.Remove(5);listisn?list.Length()<<endl;cout<<"theLengthofthelistis"<<list.Length()<<endl;list.Print();list.RemoveAll(3);cout<<"theLengthofthelistis'*<<list.Length()<<endl;list.Print();cout<<"Thethirdelementis"<<list.Get(3)<<endl;cout<<*list.Find(18,1)<<endl;list.Find(lOO);list.MakeEmpty();cout<<"theLengthofthelistis"<<list.Length()<<endl;list.Print();return0;}雙向鏈表NodeList.htemplate<typenameType>classDoublyList;template<typenameType>classListNode{private:friendclassDoublyList<Type>;ListNode():m_pprior(NULL),m_pnext(NULL){}ListNode(constTypeitem,ListNode<Type>*prior=NULL,ListNode<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;}；template<typenameType>TypeListNode<Type>returnthis->m_data;}DoubleList.h#include"ListNode.h"template<typenameType>classDoublyList{public:DoublyList():head(newListNode<Type>()){head->m_pprior=head;head->m_pnext=head;)^DoublyList(){::GetData(){//theheadnodepointtoitselfMakeEmpty();deletehead;)pxiblic: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=pde1->m_pnext;deletepdel;)head->m__pnext=head;head->m_pprior=head;)template<typenameType>intDoublyList<Type>::Length(){ListNode<Type>*pprior=head->m_pprior,*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;}template<typenameType>ListNode<Type>*DoublyList<Type>::Find(intn=0){if(n<0){cout<<"Thenisoutofboundary"<<endl;returnNULL;)ListNode<Type>*pmove=head->m_pnext;for(inti=0;i<n;i++){pmove=pmove->m_pnext;if(pmove==head){cout<<"Thenisoutofboundary"<<endl;returnNULL;}returnpmove;}template<typenameType>boolDoublyList<Type>::Insert(Typeitem,intn){if(n<0){cout<<"Thenisoutofboundary"<<endl;return0;}ListNode<Type>*newnode=newListNode<Type>(item),*pmove=head;if(newnode==NULL){cout<<"ApplicationErorr!"<<endl;exit(1);)for(inti=0;i<n;i++){//findthepositionforinsertpmove=pmove->m_pnext;if(pmove==head){cout<<'*Thenisoutofboundary"<<endl;return0;})//insertthedatanewnode->m_pnext=pmove->m_pnext;newnode->m_pprior=pmove;pmove->m_pnext=newnode;newnode->m_pnext->m_pprior=newnode;return1;}template<typenameType>TypeDoublyList<Type>::IRemove(intn=0){if(n<0){cout<<"Thenisoutofboundary"<<endl;exit(1);)ListNode<Type>*pmove=head,*pdel;for(inti=0;i<n;i++){//findthepositionfcpmove=pmove->m_pnext;if(pmove==head){cout<<"Thenisoutofboundary"<<endl;exit(1);})//deletethedatapdel=pmove;deletepmove->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>::(if(n<0){cout<<"Thenisoutofboundary"<<endl;exit(1);)ListNode<Type>*pmove=head;for(inti=0;i<n;i++){pmove=pmove->m_pnext;Set(intn=0){if(pmove==head){cout<<"Thenisoutofboundary"<<endJexit(1);})returnpmove->m_data;}template<typenameType>voidDoublyList<Type>ListNode<Type>*pmove=head->m_pnext;cout<<"head";while(pmove!=head){cout<<" >"<<pmove->m_data;pmove=pmove->m_pnext;)::Print(){cout<<" >over"<<endl<<endl<<endl;}template<typenameType>ListNode<Type>*DoublyList<Type>::FindData(Typeitem){ListNode<Type>*pprior=head->m_pprior,*pnext=head->m_pnext;while(pprior->m_pnext!=pnext&&pprior!=pnext){//findthedatainthetwodirectionif(pprior->m_data==item){returnpprior;}if(pnext->m_data==item){returnpnext;}pprior=pprior->m_pprior;pnext=pnext->m_pnext;)cout<<"can'tfindthereturnNULL;}Test.cpp#include<iostream>#include"DoublyList.h"usingnamespacestd;intmain()DoublyList<int>list;elementn<<endl;38for(inti=0;i<20;i++){list.Insert(i*3,i);)cout<<"theLengthofthelistis"<<list.Length()<<endl;list.Print();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();cout<<list.FindData(54)->GetData()<<endl;cout<<"Thethirdelementis"<<list.Get(3)<<endl;list.MakeEmpty();cout<<"theLengthofthelistis"<<list.Length()<<endl;list.Print();return0;}循環(huán)鏈表ListNode.htemplate<typenameType>classCircularList;template<typenameType>classListNode{private:friendclassCircularList<Type>;ListNode():m_pnext(NULL){}ListNode(constTypeitem,ListNode<Type>*next=NULL):m_data(item),m_pnext(next){}?ListNode(){m_pnext=NULL;)private:Typem_data;ListNode*m_pnext;}；CircularList.h#include"ListNode.h"template<typenameType>classCircularList{public:CircularList():head(newListNode<Type>()){head->m_pnext=head;)^CircularList(){MakeEmpty();deletehead;)pxiblic:voidMakeEmptyO;//clearthelistintLength();//getthelengthListNode<Type>*Find(Typevalue,intn);//findthenthdatawhichisequaltovalueListNode<Type>*Find(intn); //findthenthdataboolInsert(Typeitem,intn=0); //insertthedataintothenthdataofthelistTypeRemove(intn=0); //deletethenthdataboolRemoveAll(Typeitem); //deleteallthedataswhichareequaltovalueTypeGet(intn);//getthenthdatavoidPrint();//printthelistprivate:ListNode<Type>*head;}；template<typenameType>voidCircularList<Type>::MakeEmpty(){ListNode<Type>*pdel,*pmove=head;while(pmove->m_pnext!=head){pde1=pmove->m_pnext;pmove->m__pnext=pdel->m_pnext;deletepdel;))template<typenameType>intCircularList<Type>::Length(){ListNode<Type>*pmove=head;intcount=0;while(pmove->m_pnext!=head){pmove=pmove->m_pnext;count++;)returncount;}template<typenameType>ListNode<Type>*CircularList<Type>::Find(intn){if(n<0){cout<<"Thenisoutofboundary"<<endl;returnNULL;)ListNode<Type>*pmove=head->m_pnext;for(inti=0;i<n&&pmove!=head;i++){pmove=pmove->m_pnext;if(pmove==head){cout<<"Thenisoutofboundary"<<endl;returnNULL;)returnpmove;}template<typenameType>ListNode<Type>*CircularList<Type>::Find(Typevalue,intn){if(n<l){cout<<"Thenisillegal"<<endl;returnNULL;)ListNode<Type>*pmove=head;intcount=0;while(count!=n){pmove=pmove->m_pnext;if(pmove->m_data==value){count++;}if(pmove==head){cout<<"can'tfindtheelement"<<endl;returnNULL;})returnpmove;}template<typenameType>boolCircularList<Type>if(n<0){cout<<"Thenisoutofboundary"<<endl;::Insert(Typeitem,intn){return0;)ListNode<Type>*pmove=head;ListNode<Type>*pnode=newListNode<Type>(item)if(pnode==NULL){cout<<"Applicationerror!"<<endl;exit(1);}for(inti=0;i<n;i++){pmove=pmove->m_pnext;if(pmove==head){cout<<"Thenisoutofboundary"<<endl;return0;}2008-9-3pnode->m_pnext=pmove->m_pnext;pmove->m_pnext=pnode;return1;}template<typenameType>boolCircularList<Type>: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;:RemoveAll(Typeitem){}pmove=pmove->m_pnext;pdel=pdel->m_pnext;)return1;}template<typenameType>TypeCircularList<Type>if(n<0){cout<<"can'tfindtheelement"<<endl;exit(1);)ListNode<Type>*pmove=head,*pdel;for(inti=0;i<n&&pmove->m_pnext!=head;i++){pmove=pmove->m_pnext;::Remove(intn){)if(pmove->m_pnext==head){cout<<"can'tfindtheelement"<<endl;exit(1);)pde1=pmove->m_pnext;pmove->m_pnext=pdel->m_pnext;Typetemp=pdel->m_data;deletepdel;returntemp;}template<typenameType>TypeCircularList<Type>if(n<0){cout<<"Thenisoutofboundary"<<endl;::Get(intn){exit(1);)ListNode<Type>*pmove=head->m_pnext;for(inti=0;i<n;i++){pmove=pmove->m_pnext;if(pmove==head){cout<<"Thenisoutofboundary"<<endl;exit(1);})returnpmove->m_data;}template<typenameType>voidCircularList<Type>ListNode<Type>*pmove=head->m_pnext;::Print(){cout<<"head";while(pmove!=head){cout<<" >"<<pmove->m_data;pmove=pmove->m_pnext;)cout<<" >over"<<endl<<endl<<endl;}Test.cpp#include<iostream>#include"CircularList.h"usingnamespacestd;intmain()(CircularList<int>list;for(inti=0;i<20;i++){list.Insert(i*3fi);)cout<<"theLengthofthelist.Print();for(inti=0;i<5;i++){list.Insert(3,i*3);)cout<<"theLengthofthelist.Print();list.Remove(5);listisn<<list.Length()<<endl;listisn?list.Length()<<endl;cout<<"theLengthofthelist.Print();cout<<"theLengthofthelist.Print();list.RemoveAll(3);listis"<<list.Length()<<endl;cout<<"theLengthofthelist.Print();cout<<"Thecout<<"theLengthofthelist.Print();cout<<"Thethirdelementis"<<list.Get(3)<<endl;listis"<<list.Length()<<endl;list.MakeEmpty();cout<<"theLengthofthelistis"cout<<"theLengthofthelist.Print();return0;}順序棧SeqStack.htemplate<typenameType>classSeqStack{public:SeqStack(intsz):m_ntop(_1),m_nMaxSize(sz){m_pelements=newType[sz];if(m_pelements==NULL){cout<<"ApplicationError!"<<endl;exit(1);2008-9-3)~SeqStack(){delete[]m_pelements;)public:voidPush(constTypeitem);//pushdataTypePop();TypeGetTop()const;voidPrint();voidMakeEmpty(){m_ntop=-l;//popdata//getdata//printthestack//makethestackemptyboolIsEmpty()const{2008-9-3returnm_ntop==-l;boolIsFull()const{returnm_ntop==m_nMaxSize-1;private:intm_ntop;Type*m_pelements;intm_nMaxSize;template<typenameType>voidSeqStack<Type>::Push(constTypeitem){if(IsFull()){cout<<"Thestackisfull!"<<endl;)Returnm_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>::cout<<"bottom";for(inti=0;i<=m_ntop;i++){cout<<" >"<<m_pelements[i];)cout?" >top"<<endl<<endl<<endl;Print(){Test.cpp#include<iostream>usingnamespacestd;#include"SeqStack.h"intmain(){SeqStack<int>stack(10);intinit[10]={l,2,6,9,0,3,8,7,5,4}for(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;鏈?zhǔn)綏tackNode.htemplate<typenameType>classLinkStack;template<typenameType>classStackNode{private:friendclassLinkStack<Type>;StackNode(Typedt,StackNode<Type>*next=NULL)private:Typem_data;StackNode<Type>*m_pnext;};:m_data(dt),m_pnext(next){}Linkstack.h#include"StackNode.h"template<typenameType>classLinkStack{public:LinkStack():m_ptop(NULL){}?LinkStack(){MakeEmpty();)pxiblic:voidMakeEmpty(); //makethestackemptyvoidPush(constTypeitem);//pushthedataTypePop();//popthedataTypePop();2008-9-3TypeGetTop()const;voidPrint();boolIsEmpty()const{returnm_ptop==NULL;)private:StackNode<Type>*m_ptop;}；template<typenameType>vojStackNode<Type>*pmove;while(m_ptop!=NULL){//getthedata//printthestackIdLinkStack<Type>::MakeEmpty(){m_ptop=m_ptop->m_pnext;deletepmove;)}template<typenameType>voidLinkStack<Type>m_ptop=newStackNode<Type>(item,m_ptop);)template<typenameType>TypeLinkStack<Type>if(IsEmpty()){cout?"Thereisnoelements!"<<endl;exit(1);)returnm_ptop->m_data;::Push(constTypeitem){::GetTop()const{}template<typenameType>TypeLinkStack<Type>if(IsEmpty()){cout<<"Thereisnoelements!"<<endl;exit(1);)StackNode<Type>*pdel=m_ptop;m_ptop=m_ptop->m_pnext;Typetemp=pdel->m_data;deletepdel;returntemp;}template<typenameType>voidLinkStack<Type>::Pop(){::Print(){StackNode<Type>*pmove=m_ptop;cout<<"buttom";while(pmove!=NULL){cout<<" >"<<pmove->m_data;pmove=pmove->m_pnext;)cout?" >top"<<endl<<endl<<endl;}Test.cpp#include<iostream>usingnamespacestd;#include"Linkstack.h"intmain(){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;}7.順序隊(duì)列2008-9-3SeqQueue.htemplate<typenameType>classSeqQueue{public:SeqQueue(intsz):m_nrear(0),m_nfront(0),m_ncount(0),m_nMaxSize(sz){m_pelements=newType[sz];if(m_pelements==NULL){cout<<"ApplicationError!"<<endl;exit(1);})?SeqQueue(){delete[]m_pelements;)voidMakeEmpty(); //makethequeueempty71boolIsEmpty();boolIsFull();boolAppend(constTypeitem); //insertdataTypeDelete(); //deletedataTypeGet(); //getdatavoidPrint(); //printthequeueprivate:intm_nrear;intm_nfront;intm_ncount;intm_nMaxSize;Type*m_pelements;）；2008-9-3template<typenameType>voidSeqQueue<Type>::MakeEmpty(){this->m_ncount=0;this->m_nfront=0;this->m_nrear=0;}template<typenameType>boolSeqQueue<Type>::IsEmpty(){returnm_ncount==0;)template<typenameType>boolSeqQueue<Type>::IsFull(){returnm_ncount==m_nMaxSize;}template<typenameType>boolSeqQueue<Type>if(IsFull()){cout<<"Thequeueisfull!"<<endl;return0;)m_pelements[m_nrear]=item;m_nrear=(m_nrear+l)%m_nMaxSize;m_ncount++;return1;}template<typenameType>TypeSeqQueue<Type>if(IsEmpty()){cout<<"Thereisnoelement!'*<<endl;exit(1);::Append(constTypeitem){::Delete(){)Typetemp=m_pelements[m_nfront];m_nfront=(m_nfront+l)%m_nMaxSize;m_ncount——;returntemp;}template<typenameType>TypeSeqQueue<Type>if(IsEmpty()){cout<<"Thereisnoelement!"<<endl;exit(1);)returnm_pelements[m_nfront];template<typenameType>voidSeqQueue<Type>::Print(){cout<<"front";for(inti=0;i<m_ncount;i++){cout<<" >"<<m_pelements[(m_nfront+i+m_nMaxSize)%m_nMaxSize];)cout?" >rear"?endl?endl?endl;}Test.cpp#include<iostream>usingnamespacestd;#include"SeqQueue.h"intmain(){SeqQueue<int>queue(10);intinit[10]={l,6,9,0,2,5,8,3,7,4}for(inti=0;i<5;i++){queue.Append(init[i]);)queue.Print();cout<<queue.Delete()<<endl;queue.Print();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、鏈?zhǔn)疥?duì)列QueueNode.htemplate<typenameType>classLinkQueue;template<typenameType>classQueueNode{private:friendclassLinkQueue<Type>;QueueNode(constTypeitem,QueueNode<Type>:m_data(item),m_pnext(next){}private:Typem_data;QueueNode<Type>*m_pnext;｝；*next=NULL)數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)LinkQueue.h#include"QueueNode.h"template<typenameType>classLinkQueue{public:LinkQueue():m_prear(NULL),m_pfront(NULL){}?LinkQueue(){MakeEmpty();)voidAppend(constTypeitem);//insertdataTypeDelete(); //deletedataTypeGetFront(); //getdatavoidPrint();voidMakeEmpty(); voidPrint();//printthequeuejmptyboolIsEmpty()const{returnm_pfront==NULL;)private:QueueNode<Type>*m_prear,*m_pfront;}；template<typenameType>voidLinkQueue<Type>QueueNode<Type>*pdel;while(m_pfront){pdel=m_pfront;m_pfront=m__pfront->m_pnext;deletepdel;::MakeEmpty(){)}template<typenameType>voidLinkQueue<Type>::Append(constTypeitem){if(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<<"Thereisnoelement!"<<endl;exit(1);)QueueNode<Type>*pdel=m_pfront;Typetemp=m_pfront->m_data;m_pfront=m_pfront->m_pnext;deletepdel;returntemp;}template<typenameType>TypeLinkQueue<Type>::G<if(IsEmpty()){cout<<"Thereisnoelement!"<<endl;exit(1);)returnm_pfront->m_data;3tFront(){template<typenameType>voidLinkQueue<Type>QueueNode<Type>*pmove=m_pfront;cout<<"front";while(pmove){cout<<" >"<<pmove->m_data;pmove=pmove->m_pnext;cout?" >rear"?endl?endl?endl;Test.cpp#include<iostream>::Print(){usingnamespacestd;#include"LinkQueue.h"intmain(){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、優(yōu)先級(jí)隊(duì)列QueueNode.htemplate<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.htemplate<typenameType>classCompare{〃處理一畿就大Jpublic:staticboolIt(Typeiteml,Typeitem2);}；template<typenameType>boolCompare<Type>::It(Typeiteml,Typeitem2){returniteml<item2;}structSpecialData{friendostream&operator<<(ostream&,SpecialData&);intm_ntenor;intm_npir;}；ostream&operator<<(ostream&os,SpecialData&out){os<<out.m_ntenor<<" "<<out.m_npir;returnos;}classSpecialCmp{ //處理特殊比較大小，用戶可添加適當(dāng)?shù)念恜ublic:staticboolIt(SpecialDataiteml,SpecialDataitem2);}；boolSpecialCmp::It(SpecialDataiteml,SpecialDataitem2){returniteml.m_npir<item2.m_npir;

PriorityQueue.h#include"QueueNode.h"#include"Compare.hntemplate<typenameType,typenameCmp>classPriorityQueue{//CmpisDesignedforcomparepublic:PriorityQueue():m__prear(NULL),m_pfront(NULL){}~PriorityQueue(){MakeEmpty();)voidAppend(constTypeitem);voidAppend(constTypeitem);//insertdataTypeDelete(); //deletedataTypeGetFront(); //getdatavoidPrint(); //printthequeueboolIsEmpty()const{returnm_pfront==NULL;)private:QueueNode<Type,Cmp>*m_prear,*m_