#ifndef _TOU_H_ #define _TOU_H_ template<class T> struct DNode { public: T value; DNode* prev; DNode* next; public: DNode() {} DNode(T t, DNode*prev, DNode*next) { this->value = t; this->prev = prev; this->next = next; } }; template<class T> class TOU { public: TOU(); ~TOU(); int size(); int is_empty(); T get(int index); T get_first(); T get_last(); int insert(int index, T t); int insert_first(T t); int insert_end(T t); int del(int index); int delete_first(); int delete_last(); private: int count; DNode<T>*phead; private: DNode<T>* get_node(int index); }; template<class T >//给这个容器中进行计数 TOU<T>::TOU() :count(0) { //创建表头,注意:表头没有内存数据 phead = new DNode<T>(); phead->next = phead->prev = pthread; } //析构函数 template<class T> TOU<T>::~TOU() { //删除所有节点 DNode<T>* ptmp; DNode<T> pnode = phead->next; while (pnode != phead) { ptmp = pnode; pnode = pnode->next; delete ptmp; } //删除表头 delete phead; phead = NULL; } //返回节点个数 template<class T> int TOU<T>::size() { return count; } //获取index位置上的节点 template<class T> DNode<T>* TOU<T>::get_node(int index) { //判断参数有效性 if (index < 0 || index >= count) { cout << "参数越界" << endl; return NULL; } //正向查找 if(index <= count/2) { int i = 0; DNode<T>* pindex = phead->next; while (i++ < index) { pindex = pindex->next; } return pindex; } //反向查找 int j = 0; int rindex = count - index - 1; DNode<T>* prindex = phead->prev; while (j++ < rindex) { prindex = prindex->prev; } return prindex; } //获取第index位置上的节点的值 template<class T> T TOU<T>::get(int index) { return get_ node(index)->value; } //获取最后一个节点的值 template<class T> T TOU<T>::get_last() { return get_node(count - 1)->value; } //将节点插入到第index位置之前 template<class T> int TOU<T>::insert(int index, T t) { if (index == 0) return insert_first(t); DNode<T>* pindex = get_node(index); DNode<T>* pnode = new DNode<T>(t, pindex->prev, pindex); pindex->prev->next = pnode; pindex->prev = pnode; count++; return 0; } //将节点追加到链表的末尾 template<class T> inline int TOU<T>::append_last(T t) { DNode<T>* pnode = new DNode<T>(t, phead->prev, phead); phead->prev->next = pnode; phead->prev = pnode; count++; return 0; } //删除index位置上的节点 template<class T> int TOU<T>::del(int index) { DNode<T>*pindex = get_node(index); pindex->next->prev = pindex->prev; pindex->prev->next = pindex->next; delete pindex; count--; return 0; } //删除第一个节点 template<class T> int TOU<t>::delete_first() { return del(0); } //删除最后一个节点 template<class T> int TOU<T>::delete_last() { return del(count - 1); } #endif /* 在上面的事列中,我将双链表的声明,和实现都放在头文件中。而编程规范告诉我们, 将类,的声明和实现分离,在头文件中只包含声明,而在实现文件 .cpp中负责实现。 那么为什么这么做那?因为在双链表的实现中,我们采用了模板, 但是C++编译器不支持对模板的分离式编译!简单的说,如果在TOU.h 中声明,而在tou.CPP中进行实现的话,会报错! C++不支持对template的分离式编译 */