C++中实现队列类链式存储与栈类链式存储的代码示例
队列类链式存储
代码:
linkqueue.hpp
//队列类 #pragmaonce #include"linklist.hpp" template<typenameT> classLinkQueue { public: LinkQueue(); ~LinkQueue(); public: intclear(); intappend(T&t); intretieve(T&t); intheader(T&t); intlength(); protected: LinkList<T>*m_list; }; template<typenameT> LinkQueue<T>::LinkQueue() { m_list=newLinkList<T>; } template<typenameT> LinkQueue<T>::~LinkQueue() { clear(); deletem_list; m_list=NULL; } template<typenameT> intLinkQueue<T>::clear() { Tt; while(m_list->getLen()>0){ m_list->del(0,t); } return0; } template<typenameT> intLinkQueue<T>::append(T&t) { returnm_list->insert(t,m_list->getLen()); } template<typenameT> intLinkQueue<T>::retieve(T&t) { returnm_list->del(m_list->getLen()-1,t); } template<typenameT> intLinkQueue<T>::header(T&t) { returnm_list->get(0,t); } template<typenameT> intLinkQueue<T>::length() { returnm_list->getLen(); }
main.cpp
//队列类测试程序 #include<iostream> #include<cstdio> #include"linkqueue.hpp" usingnamespacestd; structStudent { charname[32]; intage; }; voidplay() { Students1,s2,s3; s1.age=21; s2.age=22; s3.age=23; LinkQueue<Student>lq;//创建队列 lq.append(s1);//入队列 lq.append(s2); lq.append(s3); Studenttmp; lq.header(tmp); cout<<"headerofqueue:"<<tmp.age<<endl; cout<<"lengthofqueue:"<<lq.length()<<endl; while(lq.length()>0){ lq.retieve(tmp); cout<<tmp.age<<""; } cout<<endl; lq.clear(); } intmain() { play(); return0; }
栈类链式存储
linkstack.hpp
//栈类 #pragmaonce #include"linklist.hpp" template<typenameT> classLinkStack { public: LinkStack(); ~LinkStack(); public: intclear(); intpush(T&t); intpop(T&t); inttop(T&t); intsize(); protected: LinkList<T>*m_list; }; template<typenameT> LinkStack<T>::LinkStack() { m_list=newLinkList<T>; } template<typenameT> LinkStack<T>::~LinkStack() { clear(); deletem_list; m_list=NULL; } template<typenameT> intLinkStack<T>::clear() { Tt; while(m_list->getLen()>0){ m_list->del(0,t); } return0; } template<typenameT> intLinkStack<T>::push(T&t) { returnm_list->insert(t,0); } template<typenameT> intLinkStack<T>::pop(T&t) { returnm_list->del(0,t); } template<typenameT> intLinkStack<T>::top(T&t) { returnm_list->get(0,t); } template<typenameT> intLinkStack<T>::size() { returnm_list->getLen(); }
main.cpp
//链式存储栈类的测试程序 #include<iostream> #include<cstdio> #include"linkstack.hpp" usingnamespacestd; structStudent { charname[32]; intage; }; voidplay() { Students1,s2,s3; s1.age=21; s2.age=22; s3.age=23; LinkStack<Student>ls;//创建栈 //入栈 ls.push(s1); ls.push(s2); ls.push(s3); //获取栈顶元素 Studenttmp; ls.top(tmp); cout<<"topofstack:"<<tmp.age<<endl; cout<<"sizeofstack:"<<ls.size()<<endl; //出栈 while(ls.size()>0){ ls.pop(tmp); } ls.clear(); } intmain() { play(); return0; }
linklist.h
//链表类 #pragmaonce #include<iostream> #include<cstdio> usingnamespacestd; template<typenameT> structNode { Tt; Node<T>*next; }; template<typenameT> classLinkList { public: LinkList(); ~LinkList(); public: intclear(); intinsert(T&t,intpos); intget(intpos,T&t); intdel(intpos,T&t); intgetLen(); protected: Node<T>*header; intlength; }; template<typenameT> LinkList<T>::LinkList() { header=newNode<T>; header->next=NULL; length=0; } template<typenameT> LinkList<T>::~LinkList() { Node<T>*tmp=NULL; while(header){ tmp=header->next; deleteheader; header=tmp; } } template<typenameT> intLinkList<T>::clear() { ~LinkList(); LinkList(); return0; } template<typenameT> intLinkList<T>::insert(T&t,intpos) { Node<T>*cur=NULL; //对pos的容错处理 if(pos>=length){ pos=length; } cur=header; for(inti=0;i<pos;++i){ cur=cur->next; } //把上层应用的t结点缓存到容器中 Node<T>*node=newNode<T>; node->next=NULL; node->t=t;//把t缓存到容器中 node->next=cur->next; cur->next=node; ++length; return0; } template<typenameT> intLinkList<T>::get(intpos,T&t) { Node<T>*cur=NULL; if(pos>=length){ return-1; } cur=header; for(inti=0;i<pos;++i){ cur=cur->next; } t=cur->next->t;//把pos位置的结点赋值给t return0; } template<typenameT> intLinkList<T>::del(intpos,T&t) { Node<T>*cur=NULL; if(pos>=length){ return-1; } cur=header; for(inti=0;i<pos;++i){ cur=cur->next; } Node<T>*ret=NULL; ret=cur->next; t=ret->t;//把缓存的结点给上层应用t //删除操作 cur->next=ret->next; --length; deleteret;//注意释放内存,因为insert的时候newNode<T> return0; } template<typenameT> intLinkList<T>::getLen() { returnlength; }