C++实现单链表的构造

首先，我们需要了解单链表的基本概念。单链表是一种数据结构，它由一系列节点组成，每个节点包含两个部分：数据域和指针域。数据域用于存储节点的数据，指针域则指向下一个节点的地址。单链表的最后一个节点的指针域指向空地址，表示链表的结束。

下面就是C++实现单链表的构造的完整攻略：

定义节点结构体

首先我们需要定义一个节点的结构体，它包含两个成员，分别是数据域和指针域。具体代码如下所示：

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

其中，int data代表节点的数据，Node* next代表指向下一个节点的指针。

实现链表的插入操作

链表的插入操作是指向链表中添加一个节点。链表的插入操作分为两种情况，分别是在链表的头部插入节点和在链表的尾部插入节点。具体代码如下所示：

在链表头部插入节点：

void insertNodeAtBeginning(Node* &head, int data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = head;
    head = newNode;
}

在链表尾部插入节点：

void insertNodeAtEnd(Node* &head, int data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = nullptr;
    if (head == nullptr) {
        head = newNode;
    } else {
        Node* curr = head;
        while (curr->next != nullptr) {
            curr = curr->next;
        }
        curr->next = newNode;
    }
}

在这里，Node* &head代表链表的头指针。对于在链表头部插入节点的函数void insertNodeAtBeginning(Node* &head, int data)来说，我们需要先申请一个新的节点newNode，将新节点的数据域赋值为要插入的数据，将新节点的指针域指向当前的头结点，并将头指针指向新节点。

对于在链表尾部插入节点的函数void insertNodeAtEnd(Node* &head, int data)，我们首先也是需要申请一个新节点newNode，将新节点的数据域赋值为要插入的数据，将新节点的指针域指向空地址，接下来，我们需要判断链表是否为空，如果为空，直接将头指针指向新节点。如果链表不为空，我们需要遍历整个链表，找到最后一个节点，将该节点的指针域指向新节点。

实现链表的删除操作

链表的删除操作是指从链表中删除一个节点。对于链表的删除操作，我们需要分情况讨论。分为删除头节点、删除尾节点和删除中间节点。具体代码如下所示：

删除头节点：

void deleteNodeAtBeginning(Node* &head) {
    if (head == nullptr) {
        cout << "链表为空，无法进行删除操作" << endl;
        return;
    }
    Node* temp = head;
    head = head->next;
    delete temp;
}

删除尾节点：

void deleteNodeAtEnd(Node* &head) {
    if (head == nullptr) {
        cout << "链表为空，无法进行删除操作" << endl;
        return;
    }
    if (head->next == nullptr) {
        Node* temp = head;
        head = nullptr;
        delete temp;
        return;
    }
    Node* prev = nullptr;
    Node* curr = head;
    while (curr->next != nullptr) {
        prev = curr;
        curr = curr->next;
    }
    prev->next = nullptr;
    delete curr;
}

删除中间节点：

void deleteNode(Node* &head, int data) {
    if (head == nullptr) {
        cout << "链表为空，无法进行删除操作" << endl;
        return;
    }
    Node* prev = nullptr;
    Node* curr = head;
    while (curr != nullptr && curr->data != data) {
        prev = curr;
        curr = curr->next;
    }
    if (curr == nullptr) {
        cout << "需要删除的节点不存在" << endl;
        return;
    }
    if (prev == nullptr) {
        head = curr->next;
    } else {
        prev->next = curr->next;
    }
    delete curr;
}

在这里，对于删除头节点的函数void deleteNodeAtBeginning(Node* &head)来说，我们首先需要判断链表是否为空，如果为空，打印错误信息并直接返回，如果链表不为空，则将头指针指向头节点的下一个节点，并释放头节点所占用的内存。

对于删除尾节点的函数void deleteNodeAtEnd(Node* &head)来说，我们同样需要判断链表是否为空，如果为空则打印错误信息并直接返回。如果链表的长度为1，则将头指针置为空，直接释放头节点所占用的内存。否则，我们需要遍历链表，找到倒数第二个节点，将倒数第二个节点的指针域指向空地址，并释放最后一个节点所占用的内存。

对于删除中间节点的函数void deleteNode(Node* &head, int data)来说，我们需要先遍历链表，找到要删除的节点的前一个节点。如果要删除的节点不存在，则打印错误信息并直接返回。如果要删除的节点是头节点，则需要将头指针指向头节点的下一个节点。如果要删除的节点不是头节点，则需要将要删除的节点的前一个节点的指针域指向要删除的节点的下一个节点，并释放要删除的节点所占用的内存。

完整代码示例如下所示：

#include <iostream>

using namespace std;

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

void insertNodeAtBeginning(Node* &head, int data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = head;
    head = newNode;
}

void insertNodeAtEnd(Node* &head, int data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = nullptr;
    if (head == nullptr) {
        head = newNode;
    } else {
        Node* curr = head;
        while (curr->next != nullptr) {
            curr = curr->next;
        }
        curr->next = newNode;
    }
}

void deleteNodeAtBeginning(Node* &head) {
    if (head == nullptr) {
        cout << "链表为空，无法进行删除操作" << endl;
        return;
    }
    Node* temp = head;
    head = head->next;
    delete temp;
}

void deleteNodeAtEnd(Node* &head) {
    if (head == nullptr) {
        cout << "链表为空，无法进行删除操作" << endl;
        return;
    }
    if (head->next == nullptr) {
        Node* temp = head;
        head = nullptr;
        delete temp;
        return;
    }
    Node* prev = nullptr;
    Node* curr = head;
    while (curr->next != nullptr) {
        prev = curr;
        curr = curr->next;
    }
    prev->next = nullptr;
    delete curr;
}

void deleteNode(Node* &head, int data) {
    if (head == nullptr) {
        cout << "链表为空，无法进行删除操作" << endl;
        return;
    }
    Node* prev = nullptr;
    Node* curr = head;
    while (curr != nullptr && curr->data != data) {
        prev = curr;
        curr = curr->next;
    }
    if (curr == nullptr) {
        cout << "需要删除的节点不存在" << endl;
        return;
    }
    if (prev == nullptr) {
        head = curr->next;
    } else {
        prev->next = curr->next;
    }
    delete curr;
}

int main() {
    Node* head = nullptr;
    insertNodeAtBeginning(head, 3);
    insertNodeAtBeginning(head, 2);
    insertNodeAtBeginning(head, 1);
    insertNodeAtEnd(head, 4);
    deleteNode(head, 3);
    deleteNodeAtBeginning(head);
    deleteNodeAtEnd(head);
    Node* curr = head;
    while (curr != nullptr) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

上面的代码中，我们首先定义了一个头指针Node* head，表示链表的头节点，随后我们向头部插入节点1、2、3，向尾部插入节点4，接下来我们删除了节点3，删除了头节点，并删除了尾节点，最后我们通过遍历链表的方式将链表中的所有节点输出。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C++实现单链表的构造 - Python技术站