C++实现双向链表

  1 #pragma once
  2 #include<string>
  3 
  4 namespace sichdc {
  5 
  6     class SLinklist {
  7         // 双向链表
  8 
  9     private:
 10 
 11         std::string name;    // 对象名（与链表实现无关）
 12 
 13         class Node {
 14             // 双向链表的节点
 15             // 将节点类定义为内部类，这样链表的用户使用链表时就不要顾虑链表的内部实现
 16 
 17         private:
 18 
 19             
 20             int nameid;        // 表示对象的名称的整数
 21 
 22             int value;        // 节点的值
 23             Node* prev;        // 指向前一个节点的指针
 24             Node* next;        // 指向下一个节点的指针
 25 
 26         public:
 27 
 28             static int count;    // 记录Node对象存在的个数
 29 
 30             Node();
 31             // 无参构造函数
 32             Node(int v, Node* p, Node* n);
 33             // 带参构造函数
 34             ~Node();
 35             // 析构函数，和链表实现无关
 36 
 37             void SetValue(int v);
 38             // 设置value的值
 39             int GetValue();
 40             // 返回value的值
 41             void SetPrev(Node* p);
 42             // 设置前置节点
 43             Node* GetPrev();
 44             // 返回前置节点的地址
 45             void SetNext(Node* n);
 46             // 设置后置节点
 47             Node* GetNext();
 48             // 返回后置节点的地址
 49         };
 50 
 51         Node* head;        // 链表的头指针，指向链表的第一个元素
 52         int size;
 53 
 54     public:
 55 
 56         SLinklist(std::string n);
 57         // 构造函数
 58 
 59         ~SLinklist();
 60         /*
 61         * 链表的实现涉及动态内存分配，所以要在析构函数中回收内存
 62         */
 63 
 64         bool IsEmpty();
 65         // 判空
 66 
 67         bool Insert(int place, int value);
 68         /*
 69         * 向链表中place位置插入值为value的节点
 70         * 原place位置的元素后移
 71         */
 72         bool DeleteByPlace(int place);
 73         /*
 74         * 根据位置删除链表中的元素
 75         */
 76         bool DeleteByValue(int value);
 77         /*
 78         * 根据值删除链表中的元素
 79         */
 80         int Search(int value);
 81         /*
 82         * 查找链表中是否存在相应元素
 83         * 返回链表中值为value的第一个元素在链表中的位置
 84         */
 85 
 86         int Size();
 87         /*
 88         * 返回链表中元素的数量
 89         */
 90         void ShowInfo();
 91         /*
 92         * 先从前向后输出链表中的所有元素
 93         * 再从后向前输出链表中的所有元素
 94         */
 95     };
 96 
 97     class SLinklistTest {
 98 
 99     public:
100         void Test();
101     };
102 }

  1 #include"sichlinklist.h"
  2 
  3 #include<iostream>
  4 
  5 
  6 namespace sichdc {
  7 
  8     int SLinklist::Node::count = 0;
  9     SLinklist::Node::Node() {
 10 
 11         nameid = count;
 12         count++;
 13 
 14         value = 0;
 15         prev = nullptr;
 16         next = nullptr;
 17 
 18         std::cout << "SLinklist::Node  " << nameid << "被创建" << std::endl;
 19     }
 20     SLinklist::Node::Node(int v, Node* p, Node* n) {
 21 
 22         nameid = count;
 23         count++;
 24 
 25         value = v;
 26         prev = p;
 27         next = n;
 28 
 29         std::cout << "SLinklist::Node  " << nameid << "  值：" << value << "被创建" << std::endl;
 30     }
 31     SLinklist::Node::~Node() {
 32 
 33         count--;
 34         std::cout << "SLinklist::Node  " << nameid << "  值：" << value << "被销毁" << std::endl;
 35     }
 36     void SLinklist::Node::SetValue(int v) { value = v; }
 37     int SLinklist::Node::GetValue() { return value; }
 38     void SLinklist::Node::SetPrev(SLinklist::Node* p) { prev = p; }
 39     SLinklist::Node* SLinklist::Node::GetPrev() { return prev; }
 40     void SLinklist::Node::SetNext(SLinklist::Node* n) { next = n; }
 41     SLinklist::Node* SLinklist::Node::GetNext() { return next; }
 42 
 43     SLinklist::SLinklist(std::string n) {
 44 
 45         name = n;
 46         head = nullptr;
 47         size = 0;
 48     }
 49     SLinklist::~SLinklist() {
 50 
 51         Node* temp = nullptr;
 52         for (int i = 0; i < size; ++i) {
 53 
 54             // std::cout << "定位：~Slinklist()" << std::endl;
 55 
 56             temp = head;
 57             head = head->GetNext();
 58             delete temp;
 59         }
 60     }
 61     bool SLinklist::IsEmpty() { return size == 0 && head == nullptr; }
 62     bool SLinklist::Insert(int place, int value) {
 63 
 64         Node* n = new Node();    // n指向的节点存储在动态内存区，不会在函数退出时被销毁
 65         n->SetValue(value);
 66 
 67         if (IsEmpty()) {
 68             // 特殊情况，插入空链表
 69 
 70             if (place == 0) {
 71 
 72                 n->SetPrev(nullptr);
 73                 n->SetNext(nullptr);
 74                 
 75                 head = n;
 76 
 77                 size++;
 78                 return true;
 79             }
 80             else {
 81 
 82                 delete n;
 83                 return false;
 84             }
 85         }
 86         if (place == 0) {
 87             // 特殊情况，插入到链表头
 88 
 89             n->SetPrev(nullptr);
 90             n->SetNext(head);
 91 
 92             head->SetPrev(n);
 93 
 94             head = n;
 95 
 96             size++;
 97             return true;
 98         }
 99         if (place < 0 || place >= size) {
100             // 插入位置不存在
101 
102             delete n;
103             return false;
104         }
105         if (place > 0 && place < size) {
106             // 一般情况
107 
108             Node* temp{};
109             temp = head->GetNext();
110             for (int i = 1; i < size; ++i) {
111 
112                 if (i == place) {
113 
114                     n->SetPrev(temp->GetPrev());
115                     n->SetNext(temp);
116 
117                     temp->GetPrev()->SetNext(n);
118 
119                     temp->SetPrev(n);
120                     
121                     size++;
122                     return true;
123                 }
124 
125                 temp = temp->GetNext();
126             }
127         }
128 
129         return false;
130     }
131     bool SLinklist::DeleteByPlace(int place) {
132 
133         if (place < 0 || place >= size) { return false; }    // 不能删除不存在的位置
134 
135         Node* temp{};    // 遍历链表的指针
136         temp = head;
137         for (int i = 0; i < size; ++i) {
138 
139             if (i == place) {
140 
141                 if (i == 0 && i == size - 1) {
142                     // 链表中只有一个元素
143 
144                     head = nullptr;
145                     delete temp;
146 
147                     size--;
148                     return true;
149                 }
150                 if (i == 0) {
151                     // 删除链表首元素
152 
153                     head = temp->GetNext();
154                     temp->GetNext()->SetPrev(nullptr);
155 
156                     delete temp;
157 
158                     size--;
159                     return true;
160                 }
161                 if (i == size - 1) {
162                     // 删除链表尾元素
163 
164                     temp->GetPrev()->SetNext(nullptr);
165 
166                     delete temp;
167 
168                     size--;
169                     return true;
170                 }
171                 if (i > 0 && i < size - 1) {
172                     // 删除链表一般元素
173 
174                     temp->GetPrev()->SetNext(temp->GetNext());
175                     temp->GetNext()->SetPrev(temp->GetPrev());
176 
177                     delete temp;
178 
179                     size--;
180                     return true;
181                 }
182             }
183 
184             temp = temp->GetNext();
185         }
186 
187         return false;
188     }
189     bool SLinklist::DeleteByValue(int value) {
190 
191         Node* temp{};    // 遍历链表的指针
192         temp = head;
193         for (int i = 0; i < size; ++i) {
194 
195             if (temp->GetValue() == value) {
196 
197                 if (i == 0 && i == size - 1) {
198 
199                     head = nullptr;
200 
201                     delete temp;
202                     size--;
203                     return true;
204                 }
205                 if (i == 0) {
206                     // 删除链表首元素
207 
208                     head = temp->GetNext();
209                     temp->GetNext()->SetPrev(nullptr);
210 
211                     delete temp;
212 
213                     size--;
214                     return true;
215                 }
216                 if (i == size - 1) {
217                     // 删除链表尾元素
218 
219                     temp->GetPrev()->SetNext(nullptr);
220 
221                     delete temp;
222 
223                     size--;
224                     return true;
225                 }
226                 if (i > 0 && i < size - 1) {
227                     // 删除链表一般元素
228 
229                     temp->GetPrev()->SetNext(temp->GetNext());
230                     temp->GetNext()->SetPrev(temp->GetPrev());
231 
232                     delete temp;
233 
234                     size--;
235                     return true;
236                 }
237             }
238 
239             temp = temp->GetNext();
240         }
241 
242         return false;
243     }
244     int SLinklist::Search(int value) {
245 
246         Node* temp{};    // 遍历链表的指针
247         temp = head;
248         for (int i = 0; i < size; ++i) {
249 
250             if (temp->GetValue() == value) { return i; }
251 
252             temp = temp->GetNext();
253         }
254 
255         return -1;
256         // 链表中不存在指定元素
257     }
258     int SLinklist::Size() { return size; }
259     void SLinklist::ShowInfo() {
260 
261         using namespace std;
262 
263         if (IsEmpty()) {
264 
265             cout << "链表为空\n" << endl;
266             return;
267         }
268 
269         Node* temp{};    // 遍历链表的指针
270         temp = head;
271         cout << "正序：";
272         cout << temp->GetValue() << ", ";
273         while (temp->GetNext() != nullptr) {
274 
275             temp = temp->GetNext();
276             cout << temp->GetValue() << ", ";
277         }
278         cout << endl;
279 
280         cout << "逆序：";
281         cout << temp->GetValue() << ", ";
282         while (temp->GetPrev() != nullptr) {
283 
284             temp = temp->GetPrev();
285             cout << temp->GetValue() << ", ";
286         }
287         cout << "\n" << endl;
288     }
289 
290     void SLinklistTest::Test() {
291 
292         using namespace std;
293 
294         SLinklist sll{ "sll" };
295 
296         string cmd{};    // 用于接受用户命令
297         cout << "_> ";
298         cin >> cmd;
299         while (cmd != "退出") {
300 
301             if (cmd == "空链表") {
302 
303                 cout << (sll.IsEmpty() ? "空链表" : "非空链表") << "\n" << endl;
304             }
305             else if (cmd == "链表大小") {
306 
307                 cout << sll.Size() << "\n" << endl;
308             }
309             else if (cmd == "插入") {
310 
311                 int p{};
312                 int v{};
313                 cout << "输入位置：";
314                 cin >> p;
315                 cout << "输入数据：";
316                 cin >> v;
317                 cout << sll.Insert(p, v) << "\n" << endl;
318             }
319             else if (cmd == "按位置删除") {
320 
321                 int p{};
322                 cout << "输入位置：";
323                 cin >> p;
324                 cout << sll.DeleteByPlace(p) << "\n" << endl;
325             }
326             else if (cmd == "按值删除") {
327 
328                 int v{};
329                 cout << "输入值：";
330                 cin >> v;
331                 cout << sll.DeleteByValue(v) << "\n" << endl;
332             }
333             else if (cmd == "查找") {
334 
335                 int v{};
336                 cout << "输入值：";
337                 cin >> v;
338                 cout << sll.Search(v) << "\n" << endl;
339             }
340             else if (cmd == "检查") {
341 
342                 sll.ShowInfo();
343             }
344             else {
345 
346                 cout << "不支持当前命令！" << "\n" << endl;
347             }
348 
349             cout << "_> ";
350             cin >> cmd;
351         }
352     }
353 }

 1 #include"sichlinklist.h"
 2 #include<iostream>
 3 
 4 int main() {
 5 
 6     using namespace std;
 7     using sichdc::SLinklistTest;
 8 
 9     cout << "## 程序开始 ##\n";
10 
11     SLinklistTest sllt{};
12     sllt.Test();
13 
14     cout << "## 程序结束 ##\n";
15     return 0;
16 }