从0开始学C++ 第二十七课数据结构入门

这篇具有很好参考价值的文章主要介绍了从0开始学C++ 第二十七课数据结构入门 - 数组与链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第二十七课：数据结构入门 - 数组与链表

学习目标：

理解数组的基本概念和操作。
掌握链表的基本结构与特点。
学会在C++中定义和操作数组和链表。
了解数组和链表的基本使用场景。

学习内容：

数组（Array）

概念：数组是一种线性数据结构，用一段连续的内存空间来存储一系列相同类型的元素。
参数用法：
- 索引（Index）：数组中每个元素的位置，通常从0开始。
- 长度（Length）：数组中元素的数量，确定数组大小的属性。

代码示例：

#include <iostream>
using namespace std;

int main() {
    int arr[5] = {1, 2, 3, 4, 5}; // 声明并初始化一个整型数组

    // 访问并打印数组元素
    for (int i = 0; i < 5; i++) {
        cout << "Element at index " << i << ": " << arr[i] << endl;
    }

    return 0;
}

预计输出效果：

Element at index 0: 1
Element at index 1: 2
Element at index 2: 3
Element at index 3: 4
Element at index 4: 5

使用场景：数组通常用于存储固定数目的元素，适合快速地通过索引查询元素。

链表（LinkedList）

概念：链表是一种线性结构，由一系列不必在内存中连续存储的元素组成，每个元素均包含数据部分和指向下一个元素的指针。
参数用法：
- 节点（Node）：链表中的元素，包含数据和指向下一个节点的指针。
- 头指针（Head）：指向链表的第一个节点的指针。

代码示例：

#include <iostream>
using namespace std;

// 定义链表节点结构体
struct Node {
    int data;
    Node* next;
};

// 打印链表函数
void printList(Node* n) {
    while (n != nullptr) {
        cout << n->data << " ";
        n = n->next;
    }
    cout << endl;
}

int main() {
    Node* head = new Node();
    Node* second = new Node();
    Node* third = new Node();

    head->data = 1; // 赋值
    head->next = second; // 指向下一个节点

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = nullptr;

    printList(head); // 打印链表

    return 0;
}

预计输出效果：
```
1 2 3
```
使用场景：链表适合于元素数量变动较大的情况，便于插入和删除元素，但访问特定位置的元素较慢。

链表遍历与插入

链表的遍历
- 链表的遍历意味着按照链表的指针从头到尾访问每个节点。
- 遍历通常使用循环或递归来完成。
链表中的数据插入
- 链表中的数据可以在头部、尾部或任意给定节点后插入。
- 插入操作需要更改节点的指针以维护链表的结构。

链表的节点定义示例（C++）：

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

遍历链表示例（C++）：

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

链表中数据插入示例（C++）：

在头部插入：

ListNode* insertAtHead(ListNode* head, int x) {
    ListNode* newNode = new ListNode(x);
    newNode->next = head;
    head = newNode;
    return head;
}

在尾部插入：

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

在给定节点后插入：

void insertAfterNode(ListNode* prevNode, int x) {
    if(prevNode == nullptr) {
        cout << "The given previous node cannot be null." << endl;
        return;
    }
    ListNode* newNode = new ListNode(x);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

练习题：

实现一个单链表，并定义一个函数遍历此链表。
写出一个函数，在单链表的头部插入一个节点。
写出一个函数，在单链表的尾部插入一个节点。
写出一个函数，在单链表的某个节点后插入一个新节点。

#include <iostream>

class ListNode {
public:
    int val;
    ListNode *next;

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

class SinglyLinkedList {
public:
    ListNode *head;

    SinglyLinkedList() : head(nullptr)    // 遍历链表
    void traverseList() {
        ListNode *temp = head;
        while (temp != nullptr) {
            std::cout << temp->val << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }

    // 在头部插入节点
    void insertAtHead(int x) {
        ListNode *newNode = new ListNode(x);
        newNode->next = head;
        head = newNode;
    }

    // 在尾部插入节点
    void insertAtTail(int x) {
        ListNode *newNode = new ListNode(x);
        if (head == nullptr) {
            head = newNode;
        } else {
            ListNode *temp = head;
            while (temp->next != nullptr) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
    }

    // 在某个节点后插入新节点
    void insertAfterNode(ListNode *prevNode, int x) {
        if (prevNode == nullptr) {
            std::cout << "The given previous node cannot be null." << std::endl;
            return;
        }
        ListNode *newNode = new ListNode(x);
        newNode->next = prevNode->next;
        prevNode->next = newNode;
    }
};

int main() {
    SinglyLinkedList list;

    // 在链表头部插入节点
    list.insertAtHead(5);
    list.insertAtHead(3);
    list.insertAtHead(1);

    // 在链表尾部插入节点
    list.insertAtTail(7);
    list.insertAtTail(9);

    // 遍历链表
    list.traverseList();

    // 在链表中第一个节点后插入新节点
    list.insertAfterNode(list.head, 2);

    // 再次遍历链表
    list.traverseList();

    return 0;
}