LIST类结构
1 template <typename Object> 2 class List 3 { 4 private: 5 struct Node//所有都是公有的 6 { 7 Object data; 8 Node *prev; 9 Node *next; 10 11 Node(const Object & d = Object(),Node *p = NUll,Node *n = Null): 12 data(d) , prev(p) , next(n) 13 { 14 } 15 }; 16 public: 17 class const_iterator 18 { 19 public: 20 const_iterator() : current(NULL){} 21 const Object & operator* () const 22 { 23 return retrieve(); 24 } 25 const_iterator & operator++ ( ) const 26 { 27 current = current->next; 28 return *this; 29 } 30 const_iterator & operator++( int ) 31 { 32 const_iterator old = *this; 33 ++(*this); 34 return old; 35 } 36 bool operator == (const const_iterator * rhs) const 37 { 38 return current == rhs.current; 39 } 40 bool operator != (const const_iterator & rhs) const 41 { 42 return !(*this == rhs); 43 } 44 45 protected: 46 Node *current; 47 48 Object & retrieve() cosnt 49 { 50 return current->data; 51 } 52 const_iterator(Node *p) : current(p) 53 { 54 } 55 friend class List<Object>; 56 }; 57 class iterator : public const_iterator 58 { 59 public: 60 iterator() 61 { 62 } 63 Object & operator* () 64 { 65 return retrieve(); 66 } 67 const Object & operator* () const 68 { 69 return const_iterator::operator*(); 70 } 71 iterator & operator++() 72 { 73 iterator old = *this; 74 ++(*this); 75 return old; 76 } 77 78 protected: 79 iterator(Node *p) : const_iterator(p) 80 { 81 } 82 83 friend class List<object>; 84 }; 85 public: 86 List() 87 { 88 init(); 89 } 90 List(const List & rhs) 91 { 92 init(); 93 *this = rhs; 94 } 95 ~List() 96 { 97 clear(); 98 delete head; 99 delete tail; 100 } 101 const List & operator =(const List & rhs) 102 { 103 if(this == &rhs) 104 return *this; 105 clear(); 106 for(const_iterator itr = rhs.begin();itr!=rhs.end();++itr) 107 push_back(*itr); 108 return *this; 109 } 110 void init() 111 { 112 theSize = 0; 113 head = new Node; 114 tail = new Node; 115 head->next = tail; 116 tail->prev = head; 117 } 118 119 iterator begin() 120 { 121 return iterator(head->next); 122 } 123 const_iterator begin() const 124 { 125 return const_iterator(head->next); 126 } 127 iterator end() 128 { 129 return iterator(tail); 130 } 131 const_iterator end() const 132 { 133 return const_iterator(tail); 134 } 135 136 int size() const 137 { 138 return theSize; 139 } 140 bool empty() const 141 { 142 return size() == 0; 143 } 144 void clear() 145 { 146 while(!empty()) 147 pop_front(); 148 } 149 Object & front() 150 { 151 return *begin(); 152 } 153 const Object & front() const 154 { 155 return *begin(); 156 } 157 Object & back() 158 { 159 return *--end(); 160 } 161 const Object & back() const 162 { 163 return *--end(); 164 } 165 void push_front(const Object & x) 166 { 167 insert(begin(),x); 168 } 169 void push_back(const Object & x) 170 { 171 insert(end(),x); 172 } 173 void pop_front() 174 { 175 erase(begin()); 176 } 177 viod pop_back() 178 { 179 erase(end()); 180 } 181 182 iterator insert(iterator itr,const Object & x) 183 { 184 } 185 iteratro erase(iterator itr ) 186 { 187 } 188 iterator erase(iterator start,iterator end) 189 { 190 } 191 192 private: 193 int theSize; 194 Node *head; 195 Node *tail; 196 197 void init() 198 { 199 } 200 }
本文转自博客园xingoo的博客,原文链接:20120918-LIST类定义《数据结构与算法分析》,如需转载请自行联系原博主。