模板实现 双向循环链表c++

xiaoxiao2021-02-28  6

//List.h #ifndef __LIST__ #define __LIST__ #include <iostream> #define debug(); cout<<__LINE__<<endl; using namespace std; //带头节点的 模板化双向循环链表不需要destory ,因为在用的时候才会模板实例化 // template <typename T> class List { private: struct Node { Node* prev; Node* next; T date; }; Node *Head;//头指针是操控链表的唯一支点 //由于命名不规范,需要切记: Head 指向的 都属于头 public: List( ); void insert(size_t pos, const T& value); void push_back(const T& value); void push_front(const T& value); void erase(size_t pos); void clear(); void get_value(size_t pos); size_t size( ); bool empty(); void print( ); ~List( ); }; template <typename T> List<T>::List() { Head = new Node; Head->date = 0; Head->prev = Head; Head->next = Head; } template<typename T> bool List<T>::empty() { if(Head->next == Head && Head->prev == Head ) return true; return false; } template<typename T> void List<T>::erase(size_t pos) { Node* p = Head->next; while(pos--) { p = p->next; } Head->date--; p->prev->next = p->next; p->next->prev = p->prev; delete p; p = NULL; } template<typename T> void List<T>::insert(size_t pos, const T& value) { if( pos == 0) push_front(value); else if((int)pos == Head->date) push_back(value); else { Node* p = Head->next; while(pos--) { p = p->next; } Node* tmp = new Node; Head->date++; tmp->date = value; tmp->prev = p->prev; tmp->next = p; p->prev->next = tmp; p->prev = tmp; } } template<typename T> void List<T>::get_value(size_t pos) { Node* p = Head->next; while(pos--) { p = p->next; } cout << p->date << endl; } template<typename T> void List<T>::push_back(const T& value) { Node* p = new Node; p->date = value; Head->date++; if( empty() ) { Head->next = Head->prev = p; p->prev = Head; p->next = Head; return; }       p->prev = Head;         p->next = Head->next;         Head->next->prev = p;         Head->next = p; }         template<typename T> void List<T>::print() {         if( empty() )                 return;         int temp = Head->date-1;         cout << Head->next->date;         for(Node* p = Head->next->next; temp; p=p->next, temp--)                 cout <<  ' ' << p->date;         cout << endl; }         template<typename T> void List<T>::clear() {         if(empty())                 return;         Node* p = Head->next;         while( p != Head )         {                 Node* tail = p->next;                 delete p;                 p = tail;         }         Head->date = 0;         Head->next = NULL;         Head->prev = NULL; }         template<typename T> List<T>::~List() {         clear();         delete Head;//比clear多删除了个头而已         Head = NULL; }         template<typename T> size_t List<T>::size() {         return Head->date; } #endif //list.cpp #include "list.h" #include <iostream> using namespace std; int main() { string str; cin >> str; if(str == "init_list")//不实例化就会出错。。。恶心恶心 { List<int> list; while(cin >> str) { if(str == "push_back") { int value; cin >> value; list.push_back( value ); } if(str == "print") { list.print(); } if(str == "push_front") { int value; cin >> value; list.push_front( value ); } if(str == "clear") { list.clear(); } if(str == "empty") { if(list.empty()) cout << "true" << endl; else cout << "false" << endl; } if(str == "destroy") { list.~List(); cout << "destroy" << endl; break; } if(str == "insert") { int pos, value; cin >> pos >> value; list.insert(pos, value); } if(str == "size") { cout << list.size() << endl; } if(str == "get_value") { int pos; cin >> pos; list.get_value(pos); } if(str == "erase") { int pos; cin >> pos; list.erase( pos); } } } }
转载请注明原文地址: https://www.6miu.com/read-2000036.html

最新回复(0)