c++实现双向链表

  1 #ifndef DOUBLE_LINK_HXX
  2 #define DOUBLE_LINK_HXX
  3 
  4 #include   5 using namespace std;
  6 
  7 templateclass T> 
  8 struct DNode 
  9 {
 10     public:
 11         T value;
 12         DNode *prev;
 13         DNode *next;
 14     public:
 15         DNode() { }
 16         DNode(T t, DNode *prev, DNode *next) {
 17             this->value = t;
 18             this->prev  = prev;
 19             this->next  = next;
 20            }
 21 };
 22 
 23 templateclass T> 
 24 class DoubleLink 
 25 {
 26     public:
 27         DoubleLink();
 28         ~DoubleLink();
 29 
 30         int size();
 31         int is_empty();
 32 
 33         T get(int index);
 34         T get_first();
 35         T get_last();
 36 
 37         int insert(int index, T t);
 38         int insert_first(T t);
 39         int append_last(T t);
 40 
 41         int del(int index);
 42         int delete_first();
 43         int delete_last();
 44 
 45     private:
 46         int count;
 47         DNode *phead;
 48     private:
 49         DNode *get_node(int index);
 50 };
 51 
 52 templateclass T>
 53 DoubleLink::DoubleLink() : count(0)
 54 {
 55     // 创建“表头”。注意：表头没有存储数据！
 56     phead = new DNode();
 57     phead->prev = phead->next = phead;
 58     // 设置链表计数为0
 59     //count = 0;
 60 }
 61 
 62 // 析构函数
 63 templateclass T>
 64 DoubleLink::~DoubleLink() 
 65 {
 66     // 删除所有的节点
 67     DNode* ptmp;
 68     DNode* pnode = phead->next;
 69     while (pnode != phead)
 70     {
 71         ptmp = pnode;
 72         pnode=pnode->next;
 73         delete ptmp;
 74     }
 75 
 76     // 删除"表头"
 77     delete phead;
 78     phead = NULL;
 79 }
 80 
 81 // 返回节点数目
 82 templateclass T>
 83 int DoubleLink::size() 
 84 {
 85     return count;
 86 }
 87 
 88 // 返回链表是否为空
 89 templateclass T>
 90 int DoubleLink::is_empty() 
 91 {
 92     return count==0;
 93 }
 94 
 95 // 获取第index位置的节点
 96 templateclass T>
 97 DNode* DoubleLink::get_node(int index) 
 98 {
 99     // 判断参数有效性
100     if (index0 || index>=count)
101     {
102         cout "get node failed! the index in out of bound!"  endl;
103         return NULL;
104     }
105 
106     // 正向查找
107     if (index 2)
108     {
109         int i=0;
110         DNode* pindex = phead->next;
111         while (i++  index) {
112             pindex = pindex->next;
113         }
114 
115         return pindex;
116     }
117 
118     // 反向查找
119     int j=0;
120     int rindex = count - index -1;
121     DNode* prindex = phead->prev;
122     while (j++  rindex) {
123         prindex = prindex->prev;
124     }
125 
126     return prindex;
127 }
128 
129 // 获取第index位置的节点的值
130 templateclass T>
131 T DoubleLink::get(int index) 
132 {
133     return get_node(index)->value;
134 }
135 
136 // 获取第1个节点的值
137 templateclass T>
138 T DoubleLink::get_first() 
139 {
140     return get_node(0)->value;
141 }
142 
143 // 获取最后一个节点的值
144 templateclass T>
145 T DoubleLink::get_last() 
146 {
147     return get_node(count-1)->value;
148 }
149 
150 // 将节点插入到第index位置之前
151 templateclass T>
152 int DoubleLink::insert(int index, T t) 
153 {
154     if (index == 0)
155         return insert_first(t);
156 
157     DNode* pindex = get_node(index);
158     DNode* pnode  = new DNode(t, pindex->prev, pindex);
159     pindex->prev->next = pnode;
160     pindex->prev = pnode;
161     count++;
162 
163     return 0;
164 }
165 
166 // 将节点插入第一个节点处。
167 templateclass T>
168 int DoubleLink::insert_first(T t) 
169 {
170     DNode* pnode  = new DNode(t, phead, phead->next);
171     phead->next->prev = pnode;
172     phead->next = pnode;
173     count++;
174 
175     return 0;
176 }
177 
178 // 将节点追加到链表的末尾
179 templateclass T>
180 int DoubleLink::append_last(T t) 
181 {
182     DNode* pnode = new DNode(t, phead->prev, phead);
183     phead->prev->next = pnode;
184     phead->prev = pnode;
185     count++;
186 
187     return 0;
188 }
189 
190 // 删除index位置的节点
191 templateclass T>
192 int DoubleLink::del(int index) 
193 {
194     DNode* pindex = get_node(index);
195     pindex->next->prev = pindex->prev;
196     pindex->prev->next = pindex->next;
197     delete pindex;
198     count--;
199 
200     return 0;
201 }
202 
203 // 删除第一个节点
204 templateclass T>
205 int DoubleLink::delete_first() 
206 {
207     return del(0);
208 }
209 
210 // 删除最后一个节点
211 templateclass T>
212 int DoubleLink::delete_last() 
213 {
214     return del(count-1);
215 }
216 
217 #endif