//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);
}
}
}
}
