从0开始学C++ 第二十七课 数据结构入门 - 数组与链表

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

学习目标：

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

学习内容：

1. 数组（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
     

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

2. 链表（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
     

   • 使用场景：链表适合于元素数量变动较大的情况，便于插入和删除元素，但访问特定位置的元素较慢。

链表遍历与插入

1. 链表的遍历

   • 链表的遍历意味着按照链表的指针从头到尾访问每个节点。
   • 遍历通常使用循环或递归来完成。

2. 链表中的数据插入

   • 链表中的数据可以在头部、尾部或任意给定节点后插入。
   • 插入操作需要更改节点的指针以维护链表的结构。

链表的节点定义示例（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++）：

1. 在头部插入：

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

2. 在尾部插入：

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;
}

3. 在给定节点后插入：

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;
}

练习题：

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

#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;
}