链表模板、队列模板、顺序表模板、栈模板、
//利用容器适配器实现栈和队列#pragmaonce#include<iostream>#include<string>#include<cassert>usingnamespacestd;template<typenameT>structNode{public:Node(constT&d):_next(NULL),_prev(NULL),_data(d){}T_data;Node<T>*_next;Node<T>*_prev;};template<typenameT>classLinkList{public:LinkList():_head(NULL),_tail(NULL){}LinkList(constLinkList<T>&list);LinkList<T>&operator=(LinkList<T>list);~LinkList();voidPushBack(constT&d);voidPushFront(constT&d);voidPopBack();voidPopFront();voidInsert(Node<T>*addr,constT&d);//在当前结点后面插入元素Node<T>*Search(constT&d);voidRemove(constT&d);voidRemoveAll(constT&d);voidSort();voidDisplay();size_tSize();T&GetFront(){assert(_head);return_head->_data;}T&GetBack(){assert(_tail);return_tail->_data;}private:Node<T>*_head;Node<T>*_tail;};template<typenameT>size_tLinkList<T>::Size(){Node<T>*cur=_head;size_tcount=0;while(cur){count++;cur=cur->_next;}returncount;}template<typenameT>LinkList<T>::LinkList(constLinkList<T>&list):_head(NULL),_tail(NULL){Node<T>*cur=list._head;while(cur){PushBack(cur->_data);cur=cur->_next;}}template<typenameT>LinkList<T>&LinkList<T>::operator=(LinkList<T>list){std::swap(_head,list._head);std::swap(_tail,list._tail);return*this;}template<typenameT>LinkList<T>::~LinkList(){Node<T>*cur=_head;while(cur){_head=_head->_next;deletecur;cur=_head;}_tail=NULL;}template<typenameT>voidLinkList<T>::PushBack(constT&d){Node<T>*NewHead=newNode<T>(d);if(NULL==_head){_head=NewHead;_tail=NewHead;}else{_tail->_next=NewHead;NewHead->_prev=_tail;_tail=_tail->_next;}}template<typenameT>voidLinkList<T>::PushFront(constT&d){Node<T>*NewHead=newNode<T>(d);if(NULL==_head){_head=NewHead;_tail=NewHead;}else{NewHead->_next=_head;_head->_prev=NewHead;_head=NewHead;}}template<typenameT>voidLinkList<T>::PopBack(){if(NULL==_head){return;}elseif(NULL==_head->_next){delete_tail;_head=NULL;_tail=NULL;}else{Node<T>*cur=_tail;_tail=_tail->_prev;_tail->_next=NULL;deletecur;}}template<typenameT>voidLinkList<T>::PopFront(){if(NULL==_head){return;}elseif(NULL==_head->_next){delete_tail;_head=NULL;_tail=NULL;}else{Node<T>*cur=_head;_head=_head->_next;_head->_prev=NULL;deletecur;}}template<typenameT>voidLinkList<T>::Insert(Node<T>*addr,constT&d)//在当前结点后面插入元素{Node<T>*NewNode=newNode<T>(d);if(_head==addr){NewNode->_next=_head;_head->_prev=NewNode;_head=NewNode;}elseif(_tail==addr){PushBack(d);}else{NewNode->_next=addr->_next;addr->_next->_prev=NewNode;addr->_next=NewNode;NewNode->_prev=addr;}}template<typenameT>Node<T>*LinkList<T>::Search(constT&d){Node<T>*cur=_head;while(cur){if(cur->_data==d){returncur;}cur=cur->_next;}returnNULL;}template<typenameT>voidLinkList<T>::Remove(constT&d){Node<T>*cur=Search(d);if(cur==_head){PopFront();}elseif(cur==_tail){PopBack();}else{cur->_prev->_next=cur->_next;cur->_next->_prev=cur->_prev;deletecur;}}template<typenameT>voidLinkList<T>::RemoveAll(constT&d){while(Search(d)!=NULL){Remove(d);}}template<typenameT>voidLinkList<T>::Sort(){Node<T>*end=_tail;while(_head!=end){Node<T>*cur=_head;intflag=1;while(cur!=end){if(cur->_data>cur->_next->_data){Ttmp=cur->_data;cur->_data=cur->_next->_data;cur->_next->_data=tmp;flag=0;}cur=cur->_next;}if(flag){return;}end=end->_prev;}}template<typenameT>voidLinkList<T>::Display(){Node<T>*cur=_head;while(cur){cout<<cur->_data<<"";cur=cur->_next;}cout<<endl;}
#include"LinkList.h"template<typenameT,template<class>classContainer>classQueue{public:voidPush(constT&d);voidPop();T&Front();T&Back();size_tSize();boolEmpty();voidDisplay(){while(!Empty()){cout<<Front()<<"";Pop();}cout<<endl;}private:Container<T>_con;};template<typenameT,template<class>classContainer>voidQueue<T,Container>::Push(constT&d){_con.PushBack(d);}template<typenameT,template<class>classContainer>voidQueue<T,Container>::Pop(){_con.PopFront();}template<typenameT,template<class>classContainer>T&Queue<T,Container>::Front(){return_con.GetFront();}template<typenameT,template<class>classContainer>T&Queue<T,Container>::Back(){return_con.GetBack();}template<typenameT,template<class>classContainer>size_tQueue<T,Container>::Size(){return_con.Size();}template<typenameT,template<class>classContainer>boolQueue<T,Container>::Empty(){return_con.Size()==0;}
#pragmaonce#include<iostream>#include<cstring>#include<string>#include<cassert>usingnamespacestd;template<typenameT>classSeqlist{public:Seqlist();Seqlist(constSeqlist<T>&seq);Seqlist&operator=(Seqlist<T>seq);~Seqlist();voidPushBack(constT&d);voidPushFront(constT&d);voidPopBack();voidPopFront();voidInsert(intindex,constT&d);intSearch(constT&d);voidRemove(constT&d);voidRemoveAll(constT&d);voidSort();voidReserve(intn);voidDisplay();intGetSize();T&operator[](intindex);private:voidCheckCapacity(intn=0);private:T*_pdata;int_sz;int_capacity;};template<typenameT>T&Seqlist<T>::operator[](intindex){assert(index>=0);assert(index<_sz);return_pdata[index];}template<typenameT>intSeqlist<T>::GetSize(){return_sz;}template<typenameT>Seqlist<T>::Seqlist():_sz(0),_capacity(0),_pdata(NULL){}template<typenameT>Seqlist<T>::Seqlist(constSeqlist<T>&seq){_pdata=newT[seq._capacity];for(inti=0;i<seq._sz;i++){_pdata[i]=seq._pdata[i];}_sz=seq._sz;_capacity=seq._capacity;}template<typenameT>Seqlist<T>&Seqlist<T>::operator=(Seqlist<T>seq){swap(_pdata,seq._pdata);_sz=seq._sz;_capacity=seq._capacity;return*this;}template<typenameT>Seqlist<T>::~Seqlist(){if(_pdata!=NULL){delete[]_pdata;_pdata=NULL;_sz=0;_capacity=0;}}template<typenameT>voidSeqlist<T>::CheckCapacity(intn=0){if(_sz==_capacity||n>_capacity){intNewCapacity=2*_capacity+1;if(n>_capacity){NewCapacity=n;}T*tmp=newT[NewCapacity];for(inti=0;i<_sz;i++){tmp[i]=_pdata[i];}delete[]_pdata;_pdata=tmp;_capacity=NewCapacity;}}template<typenameT>voidSeqlist<T>::PushBack(constT&d){CheckCapacity();_pdata[_sz++]=d;}template<typenameT>voidSeqlist<T>::PushFront(constT&d){CheckCapacity();//memmove(_pdata+1,_pdata,sizeof(T)*_sz);for(inti=_sz;i>0;i--){_pdata[i]=_pdata[i-1];}_pdata[0]=d;_sz++;}template<typenameT>voidSeqlist<T>::PopBack(){_sz--;}template<typenameT>voidSeqlist<T>::PopFront(){//memmove(_pdata,_pdata+1,sizeof(T)*(--_sz));for(inti=0;i<_sz-1;i++){_pdata[i]=_pdata[i+1];}_sz--;}template<typenameT>voidSeqlist<T>::Insert(intindex,constT&d){assert(index>=0);assert(index<_sz);CheckCapacity();//memmove(_pdata+index+1,_pdata+index,sizeof(T)*(_sz-index));for(inti=_sz;i>index;i--){_pdata[i]=_pdata[i-1];}_sz++;_pdata[index]=d;}template<typenameT>intSeqlist<T>::Search(constT&d){inti=0;for(i=0;i<_sz;i++){if(_pdata[i]==d){returni;}}return-1;//没找到返回-1}template<typenameT>voidSeqlist<T>::Remove(constT&d){intindex=Search(d);if(index==-1){return;}else{//memmove(_pdata+index,_pdata+index+1,sizeof(T)*(_sz-index-1));for(inti=index;i<_sz-1;i++){_pdata[i]=_pdata[i+1];}_sz--;}}template<typenameT>voidSeqlist<T>::RemoveAll(constT&d){while(Search(d)!=-1){Remove(d);}}template<typenameT>voidSeqlist<T>::Reserve(intn){CheckCapacity(n);}template<typenameT>voidSeqlist<T>::Sort(){intend=_sz-1;for(inti=0;i<_sz-1;i++){intflag=1;intk=end;for(intj=0;j<end;j++){if(_pdata[j]>_pdata[j+1]){Ttmp=_pdata[j];_pdata[j]=_pdata[j+1];_pdata[j+1]=tmp;flag=0;k=j;}}if(flag==1){return;}end=k;}}template<typenameT>voidSeqlist<T>::Display(){for(inti=0;i<_sz;i++){cout<<_pdata[i]<<"";}cout<<endl;}
#include"Seqlist.h"template<typenameT,template<class>classContainer>classStack{public:boolEmpty();voidPush(constT&d);voidPop();T&Top();intSize();voidDisplay(){while(!Empty()){cout<<Top()<<"";Pop();}cout<<endl;}private:Container<T>_con;};template<typenameT,template<class>classContainer>boolStack<T,Container>::Empty(){return_con.GetSize()==0;}template<typenameT,template<class>classContainer>voidStack<T,Container>::Pop(){_con.PopBack();}template<typenameT,template<class>classContainer>voidStack<T,Container>::Push(constT&d){_con.PushBack(d);}template<typenameT,template<class>classContainer>intStack<T,Container>::Size(){return_con.GetSize();}template<typenameT,template<class>classContainer>T&Stack<T,Container>::Top(){intsz=_con.GetSize()-1;return_con[sz];}
声明：本站所有文章资源内容，如无特殊说明或标注，均为采集网络资源。如若本站内容侵犯了原著者的合法权益，可联系本站删除。
