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

C++ 链表概述_链表可以用来处理大量数据吗

作者：IT小白 | 2024-08-28 18:30:29

赞

踩

链表可以用来处理大量数据吗

背景

当需要存储大量数据并需要对其进行操作时，常常需要使用到链表这种数据结构。它可以用来存储一系列的元素并支持插入、删除、遍历等操作。

概念

一般来说，链表是由若干个节点组成的，每个节点包含了两个部分的内容：存储的数据本身和指向下一个节点的指针。这种数据结构，使得每个节点都可以访问它的数据，以及它后面的节点。

在C++中，链表可以通过定义一个节点类来实现。下面是一个简单的链表节点类的示例代码：

  1. class Node {
  2. public:
  3.     int data;
  4.     Node* next;
  5. };
  6.  
  7. or 
  8.  
  9. typedef struct Node {
  10.     int data;
  11.     struct Node *next;
  12. }

在上面的代码中，定义了一个名为"Node"的类（或者是结构体，下文默认使用class，操作起来类似），这个类包含了两个成员变量：一个整型数据"data"(常见的一般使用int作为存储数据的类型，也可以使用class或者struct等一些复合类型作为data)，以及一个指向下一个节点的指针"next"。这样，就可以使用这个节点类来构造一个链表了。

构建链表：

构建链表时，需要定义一个头节点，它指向链表的第一个元素。头节点通常不包含实际数据，只是用来记录链表的起点。下面是一个简单的创建链表的示例代码：

  1. Node* head = new Node(); // 定义头节点
  2. head->next = nullptr; // 将头节点的指针指向 NULL，表示链表为空

针对链表的操作，一般有添加节点、查询节点、删除节点、遍历节点、去除重复节点以及对链表排序等操作，下文将展开：

添加节点

接下来，可以向链表中添加节点，从而构建一个有数据的链表。下面是一个向链表中添加节点的示例代码：

  1. // 向链表尾部添加一个新节点
  2. void addNode(Node* head, int data) {
  3.     Node* p = head;
  4.     while (p->next != nullptr) {
  5.         p = p->next;
  6.     }
  7.     Node* newNode = new Node();
  8.     newNode->data = data;
  9.     newNode->next = nullptr;
  10.     p->next = newNode;
  11. }

在上面的代码中，定义了addNode函数，其中head是头结点的指针，data是需要插入的数据，该函数的作用是向链表的尾部添加一个新节点。在函数中，首先遍历链表，找到链表的最后一个节点，然后创建一个新的节点，将它的数据设置为传入的"data"参数，并将它添加到链表的末尾。

查询节点

这是一个查找对应节点的代码示例，假设需要查找一个值为value的节点：

  1. Node* findNode(Node* head, int value) {
  2.     Node* p = head->next; // 从头节点的下一个节点开始遍历
  3.     while (p != nullptr) {
  4.         if (p->data == value) { // 找到了目标节点
  5.             return p;
  6.         }
  7.         p = p->next;
  8.     }
  9.     // 没有找到目标节点，返回nullptr
  10.     return nullptr;
  11. }

删除节点

当需要在链表中查找节点或删除节点时，通常需要遍历链表，找到目标节点并进行相应的操作。下面是一个简单的删除节点的代码示例，假设需要删除的节点指针为target：

  1. void deleteNode(Node* head, Node* target) {
  2.     Node* p = head;
  3.     while (p->next != target) { // 找到目标节点的前一个节点
  4.         p = p->next;
  5.     }
  6.     p->next = target->next; // 将前一个节点的指针指向目标节点的下一个节点
  7.     delete target; // 释放目标节点的内存
  8. }

上面的代码中，定义了deleteNode函数，形参为一个头节点head和一个目标节点指针"target"，用来删除链表中的目标节点。函数首先遍历链表，找到目标节点的前一个节点，然后将前一个节点的指针指向目标节点的下一个节点，从而删除目标节点。最后，使用"delete"操作符释放目标节点的内存空间。

去除重复节点

最简单的方式就是使用set来实现去重。还有一种比较朴实无华的方式就是使用双重循环的方式来实现去重，不需要使用哈希表。这种方法的思路是：对于每个节点，遍历它后面的所有节点，如果找到与当前节点相同的节点，则将它从链表中删除。下面是一个示例代码：

非hash去重

  1. void removeDuplicates(Node* head) {
  2.     Node* p = head;
  3.     while (p != nullptr) {
  4.         Node* q = p->next;
  5.         Node* prev = p; // 上一个非重复节点
  6.         while (q != nullptr) {
  7.             if (p->data == q->data) {
  8.                 prev->next = q->next; // 将当前节点从链表中删除
  9.                 delete q;
  10.                 q = prev->next; // 将指针移动到下一个节点
  11.             } else {
  12.                 prev = q; // 更新上一个非重复节点
  13.                 q = q->next; // 将指针移动到下一个节点
  14.             }
  15.         }
  16.         p = p->next; // 将指针移动到下一个节点
  17.     }
  18. }

在上面的代码中，定义了一个removeDuplicates函数，形参为一个头节点head，用于删除链表中的重复节点。函数首先定义了一个指向当前节点的指针p，然后从头节点head开始遍历整个链表。对于每个节点p，定义一个指向它后面节点的指针q，然后遍历节点p后面的所有节点。如果找到一个与节点p的值相同的节点，则将它从链表中删除。否则，将指针q移动到下一个节点，并更新上一个非重复节点的指针prev。最后，将指针p移动到下一个节点。

hash去重

  1. #include <unordered_set>  // 需要放到开头去
  2. void removeDuplicates(Node* head) {
  3.     unordered_set<int> hash; // 哈希表，用于存储每个节点的值
  4.     Node* p = head;
  5.     Node* prev = nullptr; // 上一个非重复节点
  6.     while (p != nullptr) {
  7.         if (hash.count(p->data)) { // 如果当前节点的值在哈希表中出现过
  8.             prev->next = p->next; // 删除当前节点
  9.             delete p;
  10.             p = prev->next; // 将指针移动到下一个节点
  11.         } else {
  12.             hash.insert(p->data); // 将当前节点的值加入到哈希表中
  13.             prev = p; // 更新上一个非重复节点
  14.             p = p->next; // 将指针移动到下一个节点
  15.         }
  16.     }
  17. }

与上述函数一样，形参为头节点head，用于删除链表中的重复节点。函数首先定义了一个unordered_set类型的哈希表（也可以使用set来实现），用于存储每个节点的值。然后，遍历整个链表，对于每个节点，判断它的值是否在哈希表中出现过。如果出现过，则删除当前节点；否则将当前节点的值加入到哈希表中，并更新上一个非重复节点的指针。

排序

此处使用冒泡排序来写一个简单的示例。首先呢链表是不能像数组那样使用下标来访问元素，但是呢，我们可以通过修改节点的指针来改变链表的顺序，从而实现链表的排序。以下是代码示例：

  1. class Node {
  2. public:
  3.     int data;
  4.     Node* next;
  5. };
  6.  
  7. Node* bubbleSortList(Node* head) {
  8.     if (!head || !head->next) return head; // 链表为空或只有一个节点，直接返回
  9.  
  10.     Node *cur = head, *tail = nullptr;
  11.     while (tail != head->next) { // tail 指向未排序部分的第一个节点
  12.         while (cur->next != tail) {
  13.             if (cur->data > cur->next->data) { // 如果相邻两个节点顺序不对，则交换它们的值
  14.                 int temp = cur->data;
  15.                 cur->data = cur->next->data;
  16.                 cur->next->data = temp;
  17.             }
  18.             cur = cur->next;
  19.         }
  20.         tail = cur; // 更新 tail，向前移动一位
  21.         cur = head; // cur 重新指向链表头节点
  22.     }
  23.     return head;
  24. }

上述代码中，定义了一个名为"bubbleSortList"的函数，它接受一个链表的头节点指针。函数使用两个指针变量"cur"和"tail"来遍历链表，并对链表节点进行排序。内层循环通过比较相邻节点的值并交换它们的值，实现了冒泡排序的过程。注意，每次内层循环结束后，"tail"指向的是未排序部分的第一个节点，"cur"重新指向链表头节点。

冒泡排序的时间复杂度为O(n^2)，在链表中的实现中需要更多的指针操作，因此效率相对较低。但是，冒泡排序是一种稳定的排序算法，可以保留原有相同元素之间的相对位置。

用例测试

以下是全部代码的集合，并编写了用例对功能进行了测试

  1. #include "set.h"
  2. #include <iostream>
  3. #include <unordered_set>
  4. class Node {
  5. public:
  6.     int data;
  7.     Node* next;
  8. };
  9.  
  10.  
  11. // 向链表尾部添加一个新节点
  12. void addNode(Node* head, int data) {
  13.     Node* p = head;
  14.     while (p->next !=  nullptr) {
  15.         p = p->next;
  16.     }
  17.     Node* newNode = new Node();
  18.     newNode->data = data;
  19.     newNode->next =  nullptr;
  20.     p->next = newNode;
  21. }
  22.  
  23. Node* findNode(Node* head, int value) {
  24.     Node* p = head->next; // 从头节点的下一个节点开始遍历
  25.     while (p != nullptr) {
  26.         if (p->data == value) { // 找到了目标节点
  27.             return p;
  28.         }
  29.         p = p->next;
  30.     }
  31.     // 没有找到目标节点，返回nullptr
  32.     return nullptr;
  33. }
  34.  
  35. void deleteNode(Node* head, Node* target) {
  36.     Node* p = head;
  37.     while (p->next != target) { // 找到目标节点的前一个节点
  38.         p = p->next;
  39.     }
  40.     p->next = target->next; // 将前一个节点的指针指向目标节点的下一个节点
  41.     delete target; // 释放目标节点的内存
  42. }
  43.  
  44. //void removeDuplicates(Node* head) {
  45. //    Node* p = head;
  46. //    while (p != nullptr) {
  47. //        Node* q = p->next;
  48. //        Node* prev = p; // 上一个非重复节点
  49. //        while (q != nullptr) {
  50. //                if (p->data == q->data) {
  51. //                        prev->next = q->next; // 将当前节点从链表中删除
  52. //                        delete q;
  53. //                        q = prev->next; // 将指针移动到下一个节点
  54. //                    } else {
  55. //                        prev = q; // 更新上一个非重复节点
  56. //                        q = q->next; // 将指针移动到下一个节点
  57. //                    }
  58. //            }
  59. //        p = p->next; // 将指针移动到下一个节点
  60. //    }
  61. //}
  62.  
  63. void removeDuplicates(Node* head) {
  64.     std::unordered_set<int> hash; // 哈希表，用于存储每个节点的值
  65.     Node* p = head;
  66.     Node* prev = nullptr; // 上一个非重复节点
  67.     while (p != nullptr) {
  68.         if (hash.count(p->data)) { // 如果当前节点的值在哈希表中出现过
  69.             prev->next = p->next; // 删除当前节点
  70.             delete p;
  71.             p = prev->next; // 将指针移动到下一个节点
  72.         } else {
  73.             hash.insert(p->data); // 将当前节点的值加入到哈希表中
  74.             prev = p; // 更新上一个非重复节点
  75.             p = p->next; // 将指针移动到下一个节点
  76.         }
  77.     }
  78. }
  79.  
  80. Node* bubbleSortList(Node* head) {
  81.     if (!head || !head->next) return head; // 链表为空或只有一个节点，直接返回
  82.  
  83.     Node *cur = head, *tail =  nullptr;
  84.     while (tail != head->next) { // tail 指向未排序部分的第一个节点
  85.         while (cur->next != tail) {
  86.             if (cur->data > cur->next->data) { // 如果相邻两个节点顺序不对，则交换它们的值
  87.                 int temp = cur->data;
  88.                 cur->data = cur->next->data;
  89.                 cur->next->data = temp;
  90.             }
  91.             cur = cur->next;
  92.         }
  93.         tail = cur; // 更新 tail，向前移动一位
  94.         cur = head; // cur 重新指向链表头节点
  95.     }
  96.     return head;
  97. }
  98.  
  99. void printList(Node* head) {
  100.     Node* p = head;
  101.     while (p !=  nullptr) {
  102.         std::cout << p->data << " ";
  103.         p = p->next;
  104.     }
  105.     std::cout << std::endl;
  106. }
  107.  
  108. int main() {
  109.  
  110.     Node* head = new Node(); // 定义头节点
  111.     head->next =  nullptr; // 将头节点的指针指向  nullptr，表示链表为空
  112.  
  113.     addNode(head, 5);
  114.     addNode(head, 3);
  115.     addNode(head, 9);
  116.     addNode(head, 1);
  117.     addNode(head, 7);
  118.  
  119.     std::cout << "Before sorting: ";
  120.     printList(head);
  121.  
  122.     if (findNode(head, 9)) {
  123.         std::cout << "Found 9 in the list" << std::endl;
  124.     }
  125.  
  126.     Node *target = findNode(head, 3);
  127.     if (target != nullptr) {
  128.         deleteNode(head, target);
  129.         std::cout << "After removing 3: ";
  130.         printList(head);
  131.     }
  132.  
  133.     bubbleSortList(head);
  134.     std::cout << "After sorting: ";
  135.     printList(head);
  136.  
  137.     return 0;
  138. }
  139. //int a[5] {1, 2, 3, 4, 5}, b[5] = {1, 3, 6, 7, 8};
  140. //int x1[2] = {1, 2}, x2[5] {1, 2, 3};
  141. //bool bl;
  142. //Set c(a, 5);
  143. //Set d(b, 5);
  144. //Set e(x1, 5);
  145. //Set f(x2, 5);
  146. //
  147. //Set g;
  148. //std::cout << "Set c: "; c.display();
  149. //std::cout << "Set d: "; d.display();
  150. //
  151. //g = c + d;
  152. //std::cout << "Set g: "; g.display();

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

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

  

闽ICP备14008679号