devbox
代码创作者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

4----双向链表

作者：代码创作者 | 2024-02-02 12:41:06

赞

踩

双向链表

//由于某些问题，代码可能无法运行，但是实现是全部正确的，大家冲！冲！冲！

考察知识点：

操作符重载；双向链表（文末有总结哦）

任务描述：

在不使用C++ STL中的list的情况下来完成以下的操作。

双向链表是一种链表结构，和普通的单向链表不同，它的每个链表节点不仅包含next指针，还包含一个back指针指向前一个节点，如下所示：（图片来自知乎）

//List Node.h

  1.   struct Element
  2. {
  3.     int num;
  4.     // 可以添加任何你需要的数据类型,但与本关测评无关
  5.     bool operator==(const Element e) const;//
  6. };
  7. bool operator==(const Element e) const
  8. {    
  9.     return num==e.num;
  10.  
  11. }
  12.  
  13. class ListNode
  14. {
  15.     Element e;
  16.     ListNode *back = nullptr;
  17.     ListNode *next = nullptr;
  18.     ListNode();
  19.     ListNode(const Element &e_);
  20.     friend class List; // 为便于测评，这里设置为友元
  21. };

这段代码首先定义了一个结构体 Element：

其中包含一个整型变量 num 和一个重载了 == 运算符的成员函数 operator==。

这段代码还定义了一个名为 ListNode 的类，其中包括以下成员：

1. Element e：数据成员，表示节点存储的元素。

2. ListNode *back：指向前一个节点的指针，默认值为 nullptr。

3. ListNode *next：指向后一个节点的指针，默认值为 nullptr。

4. ListNode()：默认构造函数，不接收参数，用于创建一个空节点。

5. ListNode(const Element &e_)：构造函数，接收一个元素 e_，用于创建一个存储该元素的节点。

6. friend class List：声明 List 类为友元类，以便 List 类可以访问 ListNode 类的私有成员。

而双向循环链表则是首尾相接的双向链表。

List是一个双向循环链表，它的定义如下：(具体实现如下)

//List.h

  1. #include <iostream>
  2. #include "ListNode.h"
  3.  
  4. class List
  5. {
  6.     ListNode head; // 加入默认头节点,使得代码逻辑更统一
  7.                    // 在进行链表操作时,你需要对head取地址
  8.     size_t size_;  // 可以自行使用,不做要求
  9. public:
  10.     // 构造和析构
  11.     List();                         // 默认构造函数,head的next和back应该指向自己
  12.     List(const List &l_);           // 拷贝构造函数,内部深拷贝
  13.     ~List();                        // 析构函数,要求释放空间,析构后的head和size变量不做要求
  14.     void operator=(const List &l_); // 赋值操作符,内部深拷贝
  15.  
  16.     size_t size() { return size_; };
  17.  
  18.     // 访问和更改,返回访问或更改是否成功
  19.     bool push_front(const Element &e); // 在头节点的next处插入e,分配空间失败时返回false
  20.     bool push_back(const Element &e);
  21.     bool pop_front(); // 弹出头节点的next节点并释放,不可弹出时返回false
  22.     bool pop_back();
  23.     bool remove(const Element &e);               // 删除链表中所有值为e的节点并释放,成功删除返回true
  24.     bool insert(const Element &e, ListNode *ln); // 在节点ln后插入e,分配空间失败时返回false,测试用例中给定的ln均合法
  25.     void erase(ListNode *ln);                    // 从链表中删除节点ln,释放ln的空间,测试用例中给定的ln均合法
  26.  
  27.     ListNode *operator[](size_t i); // 获取正向第i个节点(从0开始,不包括head)的指针,不存在则返回空
  28.  
  29.     // 遍历输出
  30.     void print(); // 正向(next)输出链表中的元素num,不包括head,空格分隔,换行符结尾;空则输出换行符
  31. };

//List.cpp

  1. #include "List.h"
  2. using namespace std;
  3. List::List()
  4. {
  5.     size_=0;
  6.     //注意，head是一个List Node类的对象，但head.next是一个指针，所以head要取地址
  7.     head.next = &head;
  8.     head.back = &head;
  9. }
  10.  
  11. List::List(const List &l_)//自己定义拷贝构造函数，负责深拷贝（在上一章我们谈过Vector）
  12. {
  13.     size_ = l_.size_;
  14.     head.e.num = l_.head.e.num;//拷贝值
  15.  
  16.     ListNode *curr = l_.head.next;//现在指向l_的第一个节点
  17.     ListNode *prev = &head;//指向head
  18.     while (curr != &l_.head) //
  19.     {
  20.         ListNode *new_node = new ListNode(curr->e);
  21.         /*这句代码创建了一个新的ListNode对象，将其地址存储在指针变量new_node中。该对象的值被设置为curr指针所指向的节点的值curr->e。这个操作可以用于复制链表节点，以便在链表中插入新节点或进行其他操作。*/
  22.         prev->next = new_node;
  23.         new_node->back = prev;
  24.         prev = new_node;
  25.         curr = curr->next;
  26.     }
  27.     prev->next = &head;
  28.     head.back = prev;
  29.    // prev=nullptr;//将两个指针赋值为nullptr
  30.    // curr=nullptr;
  31. }
  32.  
  33. List::~List()
  34. {//析构函数
  35.     ListNode *current = head.next;
  36.     while (current != &head)//来个浅浅的判断
  37.      {
  38.         ListNode *Next = current->next;//一般链表问题画图理解可能更形象一点
  39.         ListNode *pre=current;
  40.         head.next=Next;
  41.         Next->back=&head;
  42.         current = Next;
  43.         delete pre;
  44.        // Next=nullptr;
  45.       // delete next;
  46.     }
  47.     //current=nullptr;//将current置为空，其实也无所谓啦
  48.     size_=0;
  49. }
  50.  
  51. void List::operator=(const List &l_)
  52. {
  53.     if(&l_!=this){
  54.         
  55.         // Delete the existing nodes in the current list
  56.         ListNode *curr = head.next;
  57.         while(curr != &head){
  58.             ListNode *temp = curr;
  59.             curr = curr->next;
  60.             delete temp;     
  61.             //可能有的读者会认为这种写法不严谨，其实也没错，因为反正要删除所有结点，链表中断也可以，因为最后只剩一个head
  62.         }
  63.         size_ = 0;
  64.  
  65.         // Copy the nodes from the input list
  66.         ListNode *curr_input = l_.head.next;
  67.         while(curr_input != &l_.head){
  68.             push_back(curr_input->e);
  69.             curr_input = curr_input->next;
  70.         }
  71.      //   curr_input=nullptr;
  72.  
  73.     }
  74.     else return;
  75. }
  76. //以下4个函数建议画图理解
  77. bool List::push_front(const Element &e)
  78. {
  79.     ListNode *ln = new ListNode(e);
  80.     if(ln == nullptr) return false;
  81.     ln->next = head.next;
  82.     ln->back = &head;
  83.     head.next->back = ln;
  84.     head.next = ln;
  85.     size_++;
  86.     return true;
  87. }
  88. bool List::push_back(const Element &e)
  89. {
  90.     ListNode *ln = new ListNode(e);
  91.     if(ln == nullptr) return false;
  92.     ln->back = head.back;
  93.     ln->next = &head;
  94.     head.back->next = ln;
  95.     head.back = ln;
  96.     size_++;
  97.     return true;
  98. }
  99.  
  100. bool List::pop_front()
  101. {
  102.     if (head.next == nullptr||head.next == &head)//此处要注意最后一次的情况
  103.      {
  104.         return false;
  105.     }
  106.     ListNode* ln = head.next;
  107.     head.next = ln->next;
  108.     ln->next->back = &head;
  109.     delete ln;
  110.     size_--;
  111.     return true;
  112. }
  113.  
  114. bool List::pop_back()
  115. {
  116.     if(head.back == &head ||head.back == nullptr) // list is empty
  117.         return false;
  118.     ListNode *temp = head.back;
  119.     head.back = temp->back;
  120.     temp->back->next = &head;
  121.     delete temp;
  122.     size_--;
  123.     return true;
  124. }
  125.  
  126. bool List::remove(const Element &e)
  127. {
  128.     ListNode *current = head.next;
  129.     ListNode *prev = &head;
  130.     bool found = false;
  131.     while (current != &head) {
  132.         if (current->e == e) //用到了operator==这个重载函数
  133.         {
  134.             prev->next = current->next;
  135.             current->next->back = prev;
  136.             delete current;
  137.             current = prev->next;
  138.             found = true;
  139.             size_--;
  140.         } else {
  141.             prev = current;
  142.             current = current->next;
  143.         }
  144.     }
  145.     return found;
  146. }
  147. bool List::insert(const Element &e, ListNode *ln)
  148. {
  149.     ListNode *new_node = new ListNode(e);
  150.     if (new_node == nullptr) //判断分配空间是否成功
  151.     {
  152.         return false;
  153.     }
  154.     new_node->next = ln->next;
  155.     new_node->back = ln;
  156.     ln->next->back = new_node;
  157.     ln->next = new_node;
  158.     size_++;
  159.     return true;//其实这里和前面的push_front函数很像
  160. }
  161. void List::erase(ListNode *ln)
  162. {
  163.     ln->back->next = ln->next;
  164.     ln->next->back = ln->back;
  165.     delete ln;
  166.     size_--;
  167. }
  168.  
  169. ListNode* List::operator[](size_t i)//重载[]
  170. {
  171.     if (i >= size_) {
  172.         return nullptr;//千万不要越界
  173.     }
  174.     ListNode *current = head.next;
  175.     //这里j用size_t类型，一般数组的循环计数变量都是无符号整数 
  176.     for (size_t j = 0; j < i; j++)
  177.     {
  178.         current = current->next;
  179.     }
  180.     return current;
  181. }
  182.  
  183. void List::print() {
  184.     ListNode *current = head.next;
  185.     while (current != &head) {
  186.         cout << current->e.num << " ";//C++的输入输出以后会讲
  187.         current = current->next;//链表结点数据的循环打印，
  188.     }
  189.     cout << endl;
  190. }

//test-example

  1. /**
  2.  * 测试push_front push_back
  3.  * 注意:同样需要保证构造函数、析构函数和print正确实现
  4.  */
  5. void test1()
  6. {
  7.     List l;
  8.     l.push_front({2});
  9.     l.push_back({3});
  10.     l.push_front({1});
  11.     l.push_back({4});
  12.     l.print();
  13. }
  14. /** 输出
  15.  * 1 2 3 4
  16.  */
  17. /**
  18.  * 测试pop_front pop_back
  19.  */
  20. void test2()
  21. {
  22.     List l;
  23.     l.push_back({1});
  24.     l.push_back({2});
  25.     l.pop_front();
  26.     l.print();
  27.     l.push_back({4});
  28.     l.push_front({3});
  29.     l.pop_back();
  30.     l.print();
  31. }
  32. /** 输出
  33.  * 2
  34.  * 3 2
  35.  */
  36. /**
  37.  * 测试pop_front pop_back
  38.  */
  39. void test3()
  40. {
  41.     List l;
  42.     l.push_back({7890});
  43.     l.pop_back();
  44.     l.pop_front();
  45.     l.push_front({2});
  46.     l.push_back({3});
  47.     l.push_front({1});
  48.     l.push_back({4});
  49.     l.print();
  50.     l.pop_front();
  51.     l.pop_back();
  52.     l.print();
  53.     l.pop_back();
  54.     l.pop_front();
  55.     l.print();
  56. }
  57. /** 输出
  58.  * 1 2 3 4
  59.  * 2 3
  60.  *
  61.  */
  62. /**
  63.  * 测试remove
  64.  */
  65. void test4()
  66. {
  67.     List l;
  68.     l.push_front({1});
  69.     l.push_front({2});
  70.     l.push_front({3});
  71.     l.push_front({1});
  72.     l.push_front({3});
  73.     l.push_front({1});
  74.     l.print();
  75.     l.remove({1});
  76.     l.print();
  77.     l.remove({2});
  78.     l.print();
  79. }
  80. /** 输出
  81.  * 1 3 1 3 2 1
  82.  * 3 3 2
  83.  * 3 3
  84.  */
  85. /**
  86.  * 测试insert和earse
  87.  */
  88. void test5()
  89. {
  90.     List l;
  91.     l.push_back({1});
  92.     l.push_back({2});
  93.     l.push_back({3});
  94.     l.push_back({4});
  95.     l.push_back({5});
  96.     l.push_back({6});
  97.     l.print();
  98.     l.insert({23},l[1]);
  99.     l.insert({56},l[5]);
  100.     l.print();
  101.     l.erase(l[5]);
  102.     l.erase(l[1]);
  103.     l.print();
  104. }
  105. /** 输出
  106.  * 1 2 3 4 5 6
  107.  * 1 2 23 3 4 5 56 6
  108.  * 1 23 3 4 56 6
  109.  */
  110. /**
  111.  * 测试拷贝构造函数和赋值操作符
  112.  */
  113. void test6()
  114. {
  115.     List l;
  116.     l.push_back({1});
  117.     l.push_back({2});
  118.     l.push_back({3});
  119.     l.push_back({4});
  120.     l.push_back({5});
  121.     l.push_back({6});
  122.     List l_cp=l;
  123.     l.remove({4});
  124.     l.remove({2});
  125.     List l_assign;
  126.     l_assign=l;
  127.     l_cp.print();
  128.     l_assign.print();
  129. }
  130. /** 输出
  131.  * 1 2 3 4 5 6
  132.  * 1 3 5 6
  133.  */

总结：

1 .==操作符重载是一种自定义类型的比较方式，可以通过重载==操作符来实现。重载后的==操作符可以用于比较两个对象是否相等。

下面是一个示例代码，演示了如何重载==操作符：

  1. #include <iostream>
  2.  class MyClass { 
  3. public:
  4.  int value;
  5.  MyClass(int v) : value(v) {}
  6.  bool operator==(const MyClass& other) const { return value == other.value; } 
  7. }; 
  8. int main() 
  9. { 
  10. MyClass a(10); 
  11. MyClass b(20);
  12. MyClass c(10); 
  13. if (a == b) 
  14. { std::cout << "a and b are equal" << std::endl; } 
  15. else 
  16. { std::cout << "a and b are not equal" << std::endl; }
  17.  if (a == c) 
  18. { std::cout << "a and c are equal" << std::endl; }
  19.  else
  20. { std::cout << "a and c are not equal" << std::endl; } 
  21. return 0; }

输出结果为：

a and b are not equal        a and c are equal

可以看到，重载后的==操作符可以用于比较两个MyClass对象的value是否相等。

2. 编程技巧

当题目中的有些接口十分相似，或者有些接口则可以用来实现另一些接口时，最好灵活地决定接口的实现顺序，或者使用接口来实现接口，从而减轻编程压力。

3. new和delete是C++中用于动态分配内存和释放内存的操作符。new用于在堆上分配内存，返回指向分配内存的指针；delete用于释放动态分配的内存，将指向该内存的指针传递给delete操作符即可释放该内存。在使用new和delete时，需要注意内存泄漏和空指针的问题。同时，可以通过重载new和delete函数来实现自定义内存管理。（在上一讲中我们谈论了new的相关知识点，所以此处不再赘述）。

4.

双向链表是一种链式数据结构，每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。双向链表可以从头到尾或从尾到头遍历，而单向链表只能从头到尾遍历。

双向链表的优点是可以快速访问前一个节点和后一个节点，但缺点是需要更多的空间来存储指针。

以下是双向链表的常见操作：

  1. 插入节点：在双向链表中插入一个节点，需要将新节点的前一个节点的指针指向新节点，新节点的后一个节点的指针指向新节点，新节点的指针指向前一个节点和后一个节点。

  2. 左图为一种方式。

  3. 删除节点：在双向链表中删除一个节点，需要将该节点的前一个节点的指针指向该节点的后一个节点，该节点的后一个节点的指针指向该节点的前一个节点。

  4. 查找节点：在双向链表中查找一个节点，可以从头到尾或从尾到头遍历链表，直到找到目标节点。

  5. http://t.csdn.cn/pM4hd这是某位大佬的讲解。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/55346
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号