模板實(shí)現(xiàn)鏈表

//test.h #include <iostream> #include <cstdio> #include <assert.h> using namespace std;template <class T> struct ListNode {ListNode* _prev;ListNode* _next;T _data;ListNode(const T& x):_prev(NULL),_next(NULL),_data(x){} };template <class T> class List {typedef ListNode<T> Node; public:List();~List();//l(l1)//l.List(this, l1)List(const List<T>& l);List<T>& operator = (const List<int>& l);void Clean();void Insert(Node* pos, const T& x);void Erase(Node* pos);void PushFront(T x);void PushBack(T x);void PopBack();void PopFront();void Print(); protected:Node* _head; };//test.cc #include "test.h" template <class T> List <T>::List() {_head = new Node(T());_head -> _next = _head;_head -> _prev = _head; }template <class T> List <T>::~List() {Clean();delete _head; }//l(l1) //l.List(this, l1) template <class T> List<T>::List(const List<T>& l) {_head = new Node(T());_head -> _next = _head -> _prev = _head;Node* cur = l._head -> _next;while(cur != l._head){PushBack(cur -> _data);cur = cur -> _next;} }template <class T> List <T>& List <T>::operator = (const List<int>& l) {_head = l._head;return *this; }template <class T> void List <T>::Clean() {Node* cur = _head -> _next;while(cur != _head){Node* next = cur -> _next;delete cur;cur = next;} }template <class T> void List <T>::Insert(Node* pos, const T& x) {assert(pos);Node* new_node = new Node(x);Node* prev = pos -> _prev;Node* next = pos;new_node -> _next = next;next -> _prev = new_node;prev -> _next = new_node;new_node -> _prev = prev; }template <class T> void List <T>::Erase(Node* pos) {assert(pos != _head);Node* prev = pos -> _prev;Node* next = pos -> _next;prev -> _next = next;next -> _prev = prev;delete [] pos; }template <class T> void List <T>::PushFront(T x) {Insert(_head -> _next, x); }template <class T> void List <T>::PushBack(T x) {Insert(_head -> _prev -> _next, x); }template <class T> void List <T>::PopBack() {Erase(_head -> _prev); }template <class T> void List <T>::PopFront() {Erase(_head -> _next); }template <class T> void List <T>::Print() {Node* cur = _head -> _next;while(cur != _head){cout << cur -> _data << " ";cur = cur -> _next;}cout << endl; }

模板實(shí)現(xiàn)隊(duì)列

//test.cc #include "test.h"template <class T> Vector<T>::Vector():_start(NULL),_finish(NULL),_endofstorage(NULL) { }template <class T> //v1(v) Vector <T>::Vector(const Vector <T>& v) {size_t size = v.Size();T* start = new T[size];delete [] _start;_start = start;_finish = _start + size;_endofstorage = _start + v.Capacity; }template <class T> Vector <T>& Vector <T>::operator = (const Vector <T>& v) {swap(_start, v._start);swap(_finish, v._start);swap(_endofstorage, v._endofstorage);return *this; }template <class T> void Vector <T>::Expand(size_t new_capacity) {if(new_capacity > Capacity()){size_t size = Size();T* tmp = new T[new_capacity];if(_start){for(int i = 0; i < (int)size; i++){tmp[i] = _start[i]; }delete [] _start;}_start = tmp;_finish = _start + size;_endofstorage = _start + new_capacity;} }template <class T> void Vector <T>::Reserve(size_t size) {Expand(size); }template <class T> const T& Vector <T>::operator [] (size_t pos)const {return _start[pos]; } template <class T> size_t Vector <T>:: Size() {return _finish - _start; }template <class T> void Vector <T>::Insert(size_t pos, const T& x) {assert(pos <= Size());if(_finish == _endofstorage){size_t new_capacity = Capacity() == 0 ? 3 : Capacity() * 2;Expand(new_capacity);}T* end = _finish - 1;while(end >= _start + pos){*(end + 1) = *end; --end;}*end = x;++_finish; }template <class T> void Vector <T>::PushFront(const T& x) {if(Size() == Capacity()){size_t new_capacity = Capacity() == 0 ? 3 : 2 * Capacity();Expand(new_capacity);}T* end = _finish;for(; end >= _start; --end){*(end + 1) = *(end);}*_start = x;++_finish; } template <class T> void Vector <T>::PushBack(const T& x) {if(_finish == _endofstorage){size_t new_capacity = Capacity() == 0 ? 3 : 2 * Capacity();Expand(new_capacity);}*_finish = x;++_finish; }template <class T> void Vector <T>::Erase(size_t pos) {assert(pos < Size());T* start = _start + pos;while(start < _finish)// TODO{*start = *(start + 1);start++;}--_finish; }template <class T> void Vector <T>::ReSize(size_t size, const T& value) {Expand(size);memset(_start, value, sizeof(T) * size); }template <class T> size_t Vector <T>::Capacity() {return _endofstorage - _start; }template <class T> Vector <T> ::~Vector() {if(_start){delete [] _start;} }template <class T> bool Vector <T> ::Empty() {return _start == _finish; }template <class T> void Vector<T>::PopBack() {Erase(Size() - 1); }template <class T> void Vector <T>::PopFront() {Erase(0); }template <class T, class Container> void Queue <T, Container>::Push(const T& x) {_con.PushBack(x); }template <class T, class Container> void Queue<T, Container>::Pop() {_con.PopFront(); }template <class T> T& Vector<T>::Front() {if(_start != NULL){return *_start;} }template <class T, class Container> T& Queue <T, Container>::Front() {return _con.Front(); }template <class T, class Container> bool Queue <T, Container>::Empty() {return _con.Empty(); } //test.h #include <iostream> #include <cstdio> #include <assert.h> #include <string.h> using namespace std;#define TESTHEADER printf("\n==============%s===========\n", __FUNCTION__)template <class T> class Vector { public:Vector();~Vector();Vector(const Vector <T>& v);Vector& operator = (const Vector <T>& v);void Reserve(size_t size);void ReSize(size_t size, const T& value = T());const T& operator [] (size_t pos) const;void Insert(size_t pos, const T& x);void PushFront(const T& x);void PushBack(const T& x);void Erase(size_t pos);size_t Capacity();bool Empty();size_t Size();void PopBack();void PopFront();T& Front(); protected:void Expand(size_t size); protected:T* _start;T* _finish;T* _endofstorage; };template <class T, class Container> class Queue { public:void Push(const T& x);void Pop();T& Front();bool Empty(); protected:Container _con; };

模板實(shí)現(xiàn)棧

//test.h #include <iostream> #include <cstdio> #include <assert.h> #include <string.h> using namespace std;#define TESTHEADER printf("\n==================%s==================\n", __FUNCTION__) template <class T> class Vector { public:Vector();~Vector();Vector(const Vector <T>& v);Vector& operator = (const Vector <T>& v);void Reserve(size_t size);void ReSize(size_t size, const T& value = T());const T& operator [] (size_t pos) const;void Insert(size_t pos, const T& x);void PushFront(const T& x);void PushBack(const T& x);void Erase(size_t pos);size_t Capacity();bool Empty();size_t Size();void PopBack();void PopFront();const T& Back(); protected:void Expand(size_t size); protected:T* _start;T* _finish;T* _endofstorage; };template<class T, class Container> class Stack { public:void Push(const T& x);void Pop();const T& Top();bool Empty(); protected:Container _con; }; //test.cc #include "test.h" template <class T> Vector<T>::Vector():_start(NULL),_finish(NULL),_endofstorage(NULL) { }template <class T> //v1(v) Vector <T>::Vector(const Vector <T>& v) {size_t size = v.Size();T* start = new T[size];delete [] _start;_start = start;_finish = _start + size;_endofstorage = _start + v.Capacity; }template <class T> Vector <T>& Vector <T>::operator = (const Vector <T>& v) {swap(_start, v._start);swap(_finish, v._start);swap(_endofstorage, v._endofstorage);return *this; }template <class T> void Vector <T>::Expand(size_t new_capacity) {if(new_capacity > Capacity()){size_t size = Size();T* tmp = new T[new_capacity];if(_start){for(int i = 0; i < (int)size; i++){tmp[i] = _start[i]; }delete [] _start;}_start = tmp;_finish = _start + size;_endofstorage = _start + new_capacity;} }template <class T> void Vector <T>::Reserve(size_t size) {Expand(size); }template <class T> const T& Vector <T>::operator [] (size_t pos)const {return _start[pos]; } template <class T> size_t Vector <T>:: Size() {return _finish - _start; }template <class T> void Vector <T>::Insert(size_t pos, const T& x) {assert(pos <= Size());if(_finish == _endofstorage){size_t new_capacity = Capacity() == 0 ? 3 : Capacity() * 2;Expand(new_capacity);}T* end = _finish - 1;while(end >= _start + pos){*(end + 1) = *end; --end;}*end = x;++_finish; }template <class T> void Vector <T>::PushFront(const T& x) {if(Size() == Capacity()){size_t new_capacity = Capacity() == 0 ? 3 : 2 * Capacity();Expand(new_capacity);}T* end = _finish;for(; end >= _start; --end){*(end + 1) = *(end);}*_start = x;++_finish; } template <class T> void Vector <T>::PushBack(const T& x) {if(_finish == _endofstorage){size_t new_capacity = Capacity() == 0 ? 3 : 2 * Capacity();Expand(new_capacity);}*_finish = x;++_finish; }template <class T> const T& Vector<T>::Back() {return _start[Size() - 1]; }template <class T> void Vector <T>::Erase(size_t pos) {assert(pos < Size());T* start = _start + pos;while(start < _finish)// TODO{*start = *(start + 1);start++;}--_finish; }template <class T> void Vector <T>::ReSize(size_t size, const T& value) {Expand(size);memset(_start, value, sizeof(T) * size); }template <class T> size_t Vector <T>::Capacity() {return _endofstorage - _start; }template <class T> Vector <T> ::~Vector() {if(_start){delete [] _start;} }template <class T> bool Vector <T> ::Empty() {return _start == _finish; }template <class T> void Vector<T>::PopBack() {Erase(Size() - 1); }template <class T> void Vector <T>::PopFront() {Erase(0); }/////////////////////////////////////////////////////////////////////////////////////////////// //模板參數(shù)實(shí)現(xiàn)容器適配器 ///////////////////////////////////////////////////////////////////////////////////////////////template<class T, class Container> void Stack<T, Container>::Push(const T& x) {_con.PushFront(x); }template<class T, class Container> void Stack<T, Container>::Pop() {_con.PopBack(); }template<class T, class Container> bool Stack<T, Container>::Empty() {_con.Empty(); }template<class T, class Container> const T& Stack<T, Container>::Top() {return _con.Back(); }

總結(jié)

以上是生活随笔為你收集整理的模板实现栈队列以及链表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。