Aritalab:Lecture/Programming/Cpp/LinkedList
From Metabolomics.JP
< Aritalab:Lecture | Programming | Cpp(Difference between revisions)
(New page: ;ヘッダーファイル list.hh <pre> #ifndef LIST_HH #define LIST_HH class list_node; typedef list_node* lnode; class list_node { private: list_node(const list_node&); list_node...) |
m |
||
Line 7: | Line 7: | ||
typedef list_node* lnode; | typedef list_node* lnode; | ||
+ | // list_nodeは実際の値を入れるコンテナ | ||
class list_node { | class list_node { | ||
private: | private: | ||
− | list_node(const list_node&); | + | list_node(const list_node&); //外部利用を防ぐためprivate指定 |
− | list_node& operator=(const list_node&); | + | list_node& operator=(const list_node&);//外部利用を防ぐためprivate指定 |
public: | public: | ||
void* key; | void* key; | ||
Line 19: | Line 20: | ||
}; | }; | ||
+ | // lnode_listクラスはlist_nodeコンテナをpush/popする。コンテナ中身の型は感知しない。 | ||
class lnode_list { | class lnode_list { | ||
protected: | protected: | ||
Line 29: | Line 31: | ||
lnode_list& operator=(const lnode_list&); | lnode_list& operator=(const lnode_list&); | ||
virtual ~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 | + | lnode pop(); |
void push (lnode); | void push (lnode); | ||
void append(lnode); | void append(lnode); | ||
− | + | void clear(); | |
virtual void* inf(lnode x) { return x->key; } | virtual void* inf(lnode x) { return x->key; } | ||
− | |||
int size() const { return list_size; } | int size() const { return list_size; } | ||
bool empty() const { return (list_size == 0); } | bool empty() const { return (list_size == 0); } | ||
}; | }; | ||
+ | //listクラスはユーザが与える型Tを取り扱う。実際のリスト操作はlnode_listに任せる。 | ||
template<class T> | template<class T> | ||
class list: public lnode_list { | class list: public lnode_list { | ||
private: | private: | ||
− | void* copy_key(void*& x) const { return (void*) new T(x); } | + | void* copy_key(void*& x) const { return (void*) new T(x); } |
void clear_key(void*& x) const { delete x; } | void clear_key(void*& x) const { delete x; } | ||
− | |||
public: | public: | ||
list() {} | list() {} | ||
− | ~list() { clear(); } | + | ~list() { lnode_list::clear(); } |
list(const list& x) { lnode_list::operator=(x); } | list(const list& x) { lnode_list::operator=(x); } | ||
list& operator=(const list& x) | list& operator=(const list& x) | ||
{ lnode_list::operator=(x); return *this; } | { lnode_list::operator=(x); return *this; } | ||
− | + | ||
− | + | ||
− | + | ||
void push(const T&) | void push(const T&) | ||
− | { lnode v = new list_node(copy_object(x)); push( v ); } | + | { lnode v = new list_node(copy_object(x)); push(v); } |
void pop() | void pop() | ||
− | { lnode x = lnode_list:: | + | { lnode x = lnode_list::pop(); clear_key(x->key); delete x; } |
const T& peek() const { return inf(list_head); } | const T& peek() const { return inf(list_head); } | ||
− | const T& inf(lnode x) const { return | + | const T& inf(lnode x) const { return (T&)(x->key); } |
} | } | ||
#endif | #endif | ||
Line 70: | Line 73: | ||
<pre> | <pre> | ||
#include "list.hh" | #include "list.hh" | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
lnode_list::lnode_list(const lnode_list& x) | lnode_list::lnode_list(const lnode_list& x) | ||
Line 104: | Line 91: | ||
} | } | ||
− | lnode lnode_list:: | + | 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; | lnode x = list_head; | ||
Line 112: | Line 110: | ||
if (list_head) | if (list_head) | ||
list_head->list_pred =0; | list_head->list_pred =0; | ||
− | else | + | else |
list_tail =0; | list_tail =0; | ||
x->list_succ =0; | x->list_succ =0; | ||
Line 122: | Line 120: | ||
void lnode_list::push(lnode x) | void lnode_list::push(lnode x) | ||
{ | { | ||
− | if (list_size | + | if (list_size++ > 0) |
list_head->list_pred = x; | list_head->list_pred = x; | ||
else | else | ||
Line 134: | Line 132: | ||
void lnode_list::append(lnode x) | void lnode_list::append(lnode x) | ||
{ | { | ||
− | if (list_size | + | if (list_size++ > 0) |
list_tail->list_succ = x; | list_tail->list_succ = x; | ||
else | else |
Latest revision as of 12:17, 7 October 2010
- ヘッダーファイル 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; }