您现在的位置是:首页 >技术交流 >C++ 链表概述网站首页技术交流

C++ 链表概述

C__Try 2023-07-01 04:00:02
简介C++ 链表概述

背景

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

概念

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

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

class Node {
public:
    int data;
    Node* next;
};

or 

typedef struct Node {
    int data;
    struct Node *next;
}

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

构建链表:

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

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

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

添加节点

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

// 向链表尾部添加一个新节点
void addNode(Node* head, int data) {
    Node* p = head;
    while (p->next != nullptr) {
        p = p->next;
    }
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = nullptr;
    p->next = newNode;
}

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

查询节点

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

Node* findNode(Node* head, int value) {
    Node* p = head->next; // 从头节点的下一个节点开始遍历
    while (p != nullptr) {
        if (p->data == value) { // 找到了目标节点
            return p;
        }
        p = p->next;
    }
    // 没有找到目标节点,返回nullptr
    return nullptr;
}

删除节点

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

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

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

去除重复节点

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

非hash去重

void removeDuplicates(Node* head) {
    Node* p = head;
    while (p != nullptr) {
        Node* q = p->next;
        Node* prev = p; // 上一个非重复节点
        while (q != nullptr) {
            if (p->data == q->data) {
                prev->next = q->next; // 将当前节点从链表中删除
                delete q;
                q = prev->next; // 将指针移动到下一个节点
            } else {
                prev = q; // 更新上一个非重复节点
                q = q->next; // 将指针移动到下一个节点
            }
        }
        p = p->next; // 将指针移动到下一个节点
    }
}

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

hash去重

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

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

排序

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

class Node {
public:
    int data;
    Node* next;
};

Node* bubbleSortList(Node* head) {
    if (!head || !head->next) return head; // 链表为空或只有一个节点,直接返回

    Node *cur = head, *tail = nullptr;
    while (tail != head->next) { // tail 指向未排序部分的第一个节点
        while (cur->next != tail) {
            if (cur->data > cur->next->data) { // 如果相邻两个节点顺序不对,则交换它们的值
                int temp = cur->data;
                cur->data = cur->next->data;
                cur->next->data = temp;
            }
            cur = cur->next;
        }
        tail = cur; // 更新 tail,向前移动一位
        cur = head; // cur 重新指向链表头节点
    }
    return head;
}

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

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

用例测试

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

#include "set.h"
#include <iostream>
#include <unordered_set>
class Node {
public:
    int data;
    Node* next;
};


// 向链表尾部添加一个新节点
void addNode(Node* head, int data) {
    Node* p = head;
    while (p->next !=  nullptr) {
        p = p->next;
    }
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next =  nullptr;
    p->next = newNode;
}

Node* findNode(Node* head, int value) {
    Node* p = head->next; // 从头节点的下一个节点开始遍历
    while (p != nullptr) {
        if (p->data == value) { // 找到了目标节点
            return p;
        }
        p = p->next;
    }
    // 没有找到目标节点,返回nullptr
    return nullptr;
}

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

//void removeDuplicates(Node* head) {
//    Node* p = head;
//    while (p != nullptr) {
//        Node* q = p->next;
//        Node* prev = p; // 上一个非重复节点
//        while (q != nullptr) {
//                if (p->data == q->data) {
//                        prev->next = q->next; // 将当前节点从链表中删除
//                        delete q;
//                        q = prev->next; // 将指针移动到下一个节点
//                    } else {
//                        prev = q; // 更新上一个非重复节点
//                        q = q->next; // 将指针移动到下一个节点
//                    }
//            }
//        p = p->next; // 将指针移动到下一个节点
//    }
//}

void removeDuplicates(Node* head) {
    std::unordered_set<int> hash; // 哈希表,用于存储每个节点的值
    Node* p = head;
    Node* prev = nullptr; // 上一个非重复节点
    while (p != nullptr) {
        if (hash.count(p->data)) { // 如果当前节点的值在哈希表中出现过
            prev->next = p->next; // 删除当前节点
            delete p;
            p = prev->next; // 将指针移动到下一个节点
        } else {
            hash.insert(p->data); // 将当前节点的值加入到哈希表中
            prev = p; // 更新上一个非重复节点
            p = p->next; // 将指针移动到下一个节点
        }
    }
}

Node* bubbleSortList(Node* head) {
    if (!head || !head->next) return head; // 链表为空或只有一个节点,直接返回

    Node *cur = head, *tail =  nullptr;
    while (tail != head->next) { // tail 指向未排序部分的第一个节点
        while (cur->next != tail) {
            if (cur->data > cur->next->data) { // 如果相邻两个节点顺序不对,则交换它们的值
                int temp = cur->data;
                cur->data = cur->next->data;
                cur->next->data = temp;
            }
            cur = cur->next;
        }
        tail = cur; // 更新 tail,向前移动一位
        cur = head; // cur 重新指向链表头节点
    }
    return head;
}

void printList(Node* head) {
    Node* p = head;
    while (p !=  nullptr) {
        std::cout << p->data << " ";
        p = p->next;
    }
    std::cout << std::endl;
}

int main() {

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

    addNode(head, 5);
    addNode(head, 3);
    addNode(head, 9);
    addNode(head, 1);
    addNode(head, 7);

    std::cout << "Before sorting: ";
    printList(head);

    if (findNode(head, 9)) {
        std::cout << "Found 9 in the list" << std::endl;
    }

    Node *target = findNode(head, 3);
    if (target != nullptr) {
        deleteNode(head, target);
        std::cout << "After removing 3: ";
        printList(head);
    }

    bubbleSortList(head);
    std::cout << "After sorting: ";
    printList(head);

    return 0;
}
//int a[5] {1, 2, 3, 4, 5}, b[5] = {1, 3, 6, 7, 8};
//int x1[2] = {1, 2}, x2[5] {1, 2, 3};
//bool bl;
//Set c(a, 5);
//Set d(b, 5);
//Set e(x1, 5);
//Set f(x2, 5);
//
//Set g;
//std::cout << "Set c: "; c.display();
//std::cout << "Set d: "; d.display();
//
//g = c + d;
//std::cout << "Set g: "; g.display();

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。