台湾中文娱乐在线天堂 C++面向对象编程：链表插入与有序链表建立详解

引言

在面向对象C++程序设计中，链表是一种重要的数据结构，掌握其插入操作和有序链表的建立对于提升编程技能至关重要。本文将详细讲解链表的插入及有序链表的建立方法。

链表的基本概念

链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表分为单链表、双链表和循环链表等。

单链表结构

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

链表的插入操作

链表的插入操作分为头插法、尾插法和中间插入三种情况。

头插法

void insertAtHead(ListNode*& head, int value) {
    ListNode* newNode = new ListNode(value);
    newNode->next = head;
    head = newNode;
}

尾插法

void insertAtTail(ListNode*& head, int value) {
    ListNode* newNode = new ListNode(value);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    ListNode* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    temp->next = newNode;
}

中间插入

void insertAtMiddle(ListNode*& head, int value, int position) {
    ListNode* newNode = new ListNode(value);
    if (position == 0) {
        newNode->next = head;
        head = newNode;
        return;
    }
    ListNode* temp = head;
    for (int i = 0; temp != nullptr && i < position - 1; i++) {
        temp = temp->next;
    }
    if (temp == nullptr) return;
    newNode->next = temp->next;
    temp->next = newNode;
}

有序链表的建立

有序链表是指链表中的节点按某种顺序排列。建立有序链表的关键在于插入节点时保持顺序。

插入节点保持顺序

void insertInOrder(ListNode*& head, int value) {
    ListNode* newNode = new ListNode(value);
    if (head == nullptr || head->val >= value) {
        newNode->next = head;
        head = newNode;
        return;
    }
    ListNode* temp = head;
    while (temp->next != nullptr && temp->next->val < value) {
        temp = temp->next;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

示例代码

以下是一个完整的示例代码，展示了如何插入节点和建立有序链表。

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

void insertAtHead(ListNode*& head, int value) {
    ListNode* newNode = new ListNode(value);
    newNode->next = head;
    head = newNode;
}

void insertAtTail(ListNode*& head, int value) {
    ListNode* newNode = new ListNode(value);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    ListNode* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    temp->next = newNode;
}

void insertInOrder(ListNode*& head, int value) {
    ListNode* newNode = new ListNode(value);
    if (head == nullptr || head->val >= value) {
        newNode->next = head;
        head = newNode;
        return;
    }
    ListNode* temp = head;
    while (temp->next != nullptr && temp->next->val < value) {
        temp = temp->next;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr" << endl;
}

int main() {
    ListNode* head = nullptr;
    insertInOrder(head, 10);
    insertInOrder(head, 5);
    insertInOrder(head, 20);
    printList(head);
    return 0;
}

总结

通过本文的学习，读者应掌握了链表的插入操作和有序链表的建立方法。这些知识对于解决实际编程问题具有重要意义。希望读者能够通过实践进一步巩固所学内容。

参考文献

• 《C++ Primer》

• 《数据结构与算法分析》