Aritalab:Lecture/Programming/Cpp/LinkedList
From Metabolomics.JP
< Aritalab:Lecture | Programming | Cpp
- ヘッダーファイル list.hh
#ifndef LIST_HH #define LIST_HH class list_node; typedef list_node* lnode; // list_nodeは実際の値を入れるコンテナ class list_node { private: list_node(const list_node&); //外部利用を防ぐためprivate指定 list_node& operator=(const list_node&);//外部利用を防ぐためprivate指定 public: void* key; lnode list_pred; lnode list_succ; list_node(void* x=0x0) : key(x), list_pred(0), list_succ(0) {} ~list_node() {} }; // lnode_listクラスはlist_nodeコンテナをpush/popする。コンテナ中身の型は感知しない。 class lnode_list { protected: lnode list_head; lnode list_tail; int list_size; lnode_list() : list_head(0), list_tail(0), list_size(0) {} lnode_list(const lnode_list&); lnode_list& operator=(const lnode_list&); virtual ~lnode_list() {} virtual void* copy_key(void*& x) const{} // listクラスで上書きする virtual void clear_key(void*& x) const{} // listクラスで上書きする virtual lnode pred(lnode e) const { return (e ? e->list_pred : 0); } virtual lnode succ(lnode e) const { return (e ? e->list_succ : 0); } lnode pop(); void push (lnode); void append(lnode); void clear(); virtual void* inf(lnode x) { return x->key; } int size() const { return list_size; } bool empty() const { return (list_size == 0); } }; //listクラスはユーザが与える型Tを取り扱う。実際のリスト操作はlnode_listに任せる。 template<class T> class list: public lnode_list { private: void* copy_key(void*& x) const { return (void*) new T(x); } void clear_key(void*& x) const { delete x; } public: list() {} ~list() { lnode_list::clear(); } list(const list& x) { lnode_list::operator=(x); } list& operator=(const list& x) { lnode_list::operator=(x); return *this; } void push(const T&) { lnode v = new list_node(copy_object(x)); push(v); } void pop() { lnode x = lnode_list::pop(); clear_key(x->key); delete x; } const T& peek() const { return inf(list_head); } const T& inf(lnode x) const { return (T&)(x->key); } } #endif
- ソースファイル list.cc
#include "list.hh" lnode_list::lnode_list(const lnode_list& x) { list_head = list_tail =0; list_size =0; for(lnode i = x.head(); i != 0; i = x.succ(i)) append(new list_node( copy_key(i->key))); } lnode_list& lnode_list::operator=(const lnode_list& x) { if ( &x == this ) return *this; clear_all(); for(lnode i = x.head(); i != 0; i = x.succ(i)) append( new list_node( copy_key(i->key) ) ); return *this; } void lnode_list::clear() { for(lnode x, y = list_head; x = y, y = succ(y), x != 0;) { clear_key(x->key); delete x; } list_head = list_tail =0; list_size =0; } lnode lnode_list::pop() { lnode x = list_head; if (x) { list_head = x->list_succ; if (list_head) list_head->list_pred =0; else list_tail =0; x->list_succ =0; list_size--; } return x; } void lnode_list::push(lnode x) { if (list_size++ > 0) list_head->list_pred = x; else list_tail = x; x->list_pred = 0; x->list_succ = list_head; list_head = x; } void lnode_list::append(lnode x) { if (list_size++ > 0) list_tail->list_succ = x; else list_head = x; x->list_pred = list_tail; x->list_succ = 0; list_tail = x; }