C++ 数据结构

简介

数据结构是计算机科学中的一个基本概念，用于存储和组织数据，以便能够高效地访问和修改。合理选择和使用数据结构可以显著提高程序的性能。

在本章中，我们将介绍一些常用的 C++ 数据结构，包括数组、链表、栈、队列和树等，并探讨它们的特点、优势以及适用场景。

数组

定义与特性

数组是一种线性数据结构，它将一系列元素按顺序存储在连续的内存空间中。每个元素通过索引（通常是整数）进行访问，索引从0开始。数组具有以下特点：

• 固定大小：创建数组时需要指定其大小，且大小不能改变。
• 随机访问：可以通过索引快速访问或修改数组中的任意元素。
• 内存连续：数组元素在内存中是连续存储的，因此访问速度快。

示例代码

// www.javascriptcn.com code example
#include <iostream>

int main() {
    int arr[5]; // 创建一个包含5个整数的数组
    for (int i = 0; i < 5; i++) {
        arr[i] = i * i; // 将数组元素初始化为平方值
    }

    std::cout << "数组元素：" << std::endl;
    for (int i = 0; i < 5; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

链表

定义与特性

链表也是一种线性数据结构，但它通过指针链接节点而非连续存储。链表的特点如下：

• 动态大小：可以根据需要添加或删除节点，从而改变链表的大小。
• 顺序访问：只能按照顺序依次访问链表中的元素，无法像数组那样通过索引随机访问。
• 内存不连续：链表的各个节点可以分散存储在内存的不同位置。

单向链表

单向链表的每个节点包含数据部分和指向下一个节点的指针。

节点定义

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

插入节点

// www.javascriptcn.com code example
void insertNode(Node*& head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = nullptr;

    if (head == nullptr) {
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

删除节点

// www.javascriptcn.com code example
void deleteNode(Node*& head, int key) {
    Node* temp = head;
    Node* prev = nullptr;

    if (temp != nullptr && temp->data == key) {
        head = temp->next;
        delete temp;
        return;
    }

    while (temp != nullptr && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == nullptr) return;

    prev->next = temp->next;
    delete temp;
}

栈

定义与特性

栈是一种特殊的线性数据结构，遵循后进先出（LIFO）的原则。栈的操作主要有两种：压栈（push）和弹栈（pop）。栈通常用于实现递归算法、表达式求值和函数调用管理等。

示例代码

// www.javascriptcn.com code example
#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;
    s.push(1); // 向栈顶添加元素
    s.push(2);
    s.push(3);

    std::cout << "栈顶元素：" << s.top() << std::endl; // 获取栈顶元素
    s.pop(); // 弹出栈顶元素
    std::cout << "新的栈顶元素：" << s.top() << std::endl;

    std::cout << "栈是否为空：" << s.empty() << std::endl; // 判断栈是否为空
    return 0;
}

队列

定义与特性

队列也是一种线性数据结构，遵循先进先出（FIFO）的原则。队列的主要操作包括入队（enqueue）和出队（dequeue），常用于任务调度、缓冲机制等场景。

循环队列

循环队列是一种特殊的队列形式，当队列达到最大容量时，新元素会被插入到队列的起始位置，形成“循环”。

定义队列

// www.javascriptcn.com code example
#define MAX_SIZE 100
class Queue {
public:
    Queue() { front = rear = -1; }
    bool isFull() const { return ((front == 0 && rear == MAX_SIZE - 1) || front == rear + 1); }
    bool isEmpty() const { return (front == -1); }
    void enqueue(int value);
    int dequeue();
private:
    int front, rear;
    int arr[MAX_SIZE];
};

void Queue::enqueue(int value) {
    if (isFull()) {
        std::cout << "队列已满" << std::endl;
        return;
    }
    if (front == -1) front = 0;
    rear = (rear + 1) % MAX_SIZE;
    arr[rear] = value;
}

int Queue::dequeue() {
    if (isEmpty()) {
        std::cout << "队列为空" << std::endl;
        return -1;
    }
    int item = arr[front];
    if (front == rear) {
        front = rear = -1;
    } else {
        front = (front + 1) % MAX_SIZE;
    }
    return item;
}

树

定义与特性

树是一种非线性的数据结构，由有限个结点组成，其中有一个称为根的特殊结点，其余结点分为若干互不相交的子集，每个子集本身也是一棵树。树具有以下特点：

• 层次关系：树的结构使得它可以表示层次关系。
• 分支结构：树的每个节点可以有多个子节点。
• 无环：树中没有环路。

二叉树

二叉树是最常见的树形结构之一，每个节点最多有两个子节点。

二叉树节点定义

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

前序遍历

void preorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    std::cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

中序遍历

void inorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);
    std::cout << root->val << " ";
    inorderTraversal(root->right);
}

后序遍历

void postorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    std::cout << root->val << " ";
}

以上便是对几种常用数据结构的简要介绍和示例代码。这些数据结构在实际编程中应用广泛，理解它们的工作原理对于提升编程技能非常重要。