C++语言教程

Appearance

C++ 数据结构 ​

数据结构是计算机存储、组织数据的方式。C++ 提供了丰富的数据结构，包括数组、链表、栈、队列、树、图等。

1. 数组 ​

数组是最基本的数据结构，用于存储相同类型的元素。

1.1 一维数组 ​

cpp
#include <iostream>

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    
    for (int i = 0; i < 5; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

1.2 二维数组 ​

cpp
#include <iostream>

int main() {
    int matrix[3][3] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            std::cout << matrix[i][j] << " ";
        }
        std::cout << std::endl;
    }
    
    return 0;
}

2. 链表 ​

链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

2.1 单向链表 ​

cpp
#include <iostream>

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

class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}
    
    void append(int data) {
        Node* new_node = new Node{data, nullptr};
        
        if (head == nullptr) {
            head = new_node;
        } else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = new_node;
        }
    }
    
    void print() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    LinkedList list;
    list.append(10);
    list.append(20);
    list.append(30);
    
    list.print();
    
    return 0;
}

2.2 双向链表 ​

cpp
#include <iostream>

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

class DoublyLinkedList {
private:
    Node* head;

public:
    DoublyLinkedList() : head(nullptr) {}
    
    void append(int data) {
        Node* new_node = new Node{data, nullptr, nullptr};
        
        if (head == nullptr) {
            head = new_node;
        } else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = new_node;
            new_node->prev = current;
        }
    }
    
    void print() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    DoublyLinkedList list;
    list.append(10);
    list.append(20);
    list.append(30);
    
    list.print();
    
    return 0;
}

3. 栈 ​

栈是一种后进先出（LIFO）的数据结构。

3.1 使用数组实现栈 ​

cpp
#include <iostream>

class Stack {
private:
    int* arr;
    int top;
    int capacity;

public:
    Stack(int size) : capacity(size), top(-1) {
        arr = new int[capacity];
    }
    
    ~Stack() {
        delete[] arr;
    }
    
    void push(int data) {
        if (top == capacity - 1) {
            std::cout << "栈已满" << std::endl;
            return;
        }
        arr[++top] = data;
    }
    
    int pop() {
        if (top == -1) {
            std::cout << "栈为空" << std::endl;
            return -1;
        }
        return arr[top--];
    }
    
    bool is_empty() {
        return top == -1;
    }
    
    bool is_full() {
        return top == capacity - 1;
    }
};

int main() {
    Stack stack(5);
    
    stack.push(10);
    stack.push(20);
    stack.push(30);
    
    while (!stack.is_empty()) {
        std::cout << stack.pop() << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

3.2 使用 STL 的 stack ​

cpp
#include <iostream>
#include <stack>

int main() {
    std::stack<int> stack;
    
    stack.push(10);
    stack.push(20);
    stack.push(30);
    
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;
    
    return 0;
}

4. 队列 ​

队列是一种先进先出（FIFO）的数据结构。

4.1 使用数组实现队列 ​

cpp
#include <iostream>

class Queue {
private:
    int* arr;
    int front;
    int rear;
    int capacity;

public:
    Queue(int size) : capacity(size), front(-1), rear(-1) {
        arr = new int[capacity];
    }
    
    ~Queue() {
        delete[] arr;
    }
    
    void enqueue(int data) {
        if (rear == capacity - 1) {
            std::cout << "队列已满" << std::endl;
            return;
        }
        if (front == -1) {
            front = 0;
        }
        arr[++rear] = data;
    }
    
    int dequeue() {
        if (front == -1 || front > rear) {
            std::cout << "队列为空" << std::endl;
            return -1;
        }
        return arr[front++];
    }
    
    bool is_empty() {
        return front == -1 || front > rear;
    }
    
    bool is_full() {
        return rear == capacity - 1;
    }
};

int main() {
    Queue queue(5);
    
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);
    
    while (!queue.is_empty()) {
        std::cout << queue.dequeue() << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

4.2 使用 STL 的 queue ​

cpp
#include <iostream>
#include <queue>

int main() {
    std::queue<int> queue;
    
    queue.push(10);
    queue.push(20);
    queue.push(30);
    
    while (!queue.empty()) {
        std::cout << queue.front() << " ";
        queue.pop();
    }
    std::cout << std::endl;
    
    return 0;
}

5. 树 ​

树是一种层次结构的数据结构，由节点和边组成。

5.1 二叉树 ​

cpp
#include <iostream>

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

class BinaryTree {
private:
    TreeNode* root;
    
    void inorder(TreeNode* node) {
        if (node != nullptr) {
            inorder(node->left);
            std::cout << node->data << " ";
            inorder(node->right);
        }
    }
    
    void preorder(TreeNode* node) {
        if (node != nullptr) {
            std::cout << node->data << " ";
            preorder(node->left);
            preorder(node->right);
        }
    }
    
    void postorder(TreeNode* node) {
        if (node != nullptr) {
            postorder(node->left);
            postorder(node->right);
            std::cout << node->data << " ";
        }
    }

public:
    BinaryTree() : root(nullptr) {}
    
    void insert(int data) {
        if (root == nullptr) {
            root = new TreeNode(data);
        } else {
            TreeNode* current = root;
            while (true) {
                if (data < current->data) {
                    if (current->left == nullptr) {
                        current->left = new TreeNode(data);
                        break;
                    }
                    current = current->left;
                } else {
                    if (current->right == nullptr) {
                        current->right = new TreeNode(data);
                        break;
                    }
                    current = current->right;
                }
            }
        }
    }
    
    void inorder_traversal() {
        inorder(root);
        std::cout << std::endl;
    }
    
    void preorder_traversal() {
        preorder(root);
        std::cout << std::endl;
    }
    
    void postorder_traversal() {
        postorder(root);
        std::cout << std::endl;
    }
};

int main() {
    BinaryTree tree;
    tree.insert(50);
    tree.insert(30);
    tree.insert(70);
    tree.insert(20);
    tree.insert(40);
    tree.insert(60);
    tree.insert(80);
    
    std::cout << "中序遍历: ";
    tree.inorder_traversal();
    
    std::cout << "前序遍历: ";
    tree.preorder_traversal();
    
    std::cout << "后序遍历: ";
    tree.postorder_traversal();
    
    return 0;
}

6. 哈希表 ​

哈希表是一种基于键值对的数据结构，可以快速查找、插入和删除。

6.1 使用 STL 的 unordered_map ​

cpp
#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> map;
    
    map["张三"] = 20;
    map["李四"] = 21;
    map["王五"] = 22;
    
    for (const auto& pair : map) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    return 0;
}

7. 图 ​

图是由节点（顶点）和边组成的数据结构。

7.1 邻接矩阵表示图 ​

cpp
#include <iostream>
#include <vector>

class Graph {
private:
    int num_vertices;
    std::vector<std::vector<int>> adj_matrix;

public:
    Graph(int num) : num_vertices(num), adj_matrix(num, std::vector<int>(num, 0)) {}
    
    void add_edge(int i, int j) {
        adj_matrix[i][j] = 1;
        adj_matrix[j][i] = 1;
    }
    
    void print() {
        for (int i = 0; i < num_vertices; i++) {
            for (int j = 0; j < num_vertices; j++) {
                std::cout << adj_matrix[i][j] << " ";
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    Graph graph(4);
    
    graph.add_edge(0, 1);
    graph.add_edge(0, 2);
    graph.add_edge(1, 2);
    graph.add_edge(2, 3);
    
    graph.print();
    
    return 0;
}

8. 示例：综合运用 ​

现在，让我们看一个综合运用各种数据结构的例子：

cpp
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>

int main() {
    // 数组
    std::cout << "数组:" << std::endl;
    int arr[] = {1, 2, 3, 4, 5};
    for (int i = 0; i < 5; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    std::cout << std::endl;
    
    // vector
    std::cout << "vector:" << std::endl;
    std::vector<int> vec = {10, 20, 30, 40, 50};
    for (int x : vec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    std::cout << std::endl;
    
    // 栈
    std::cout << "栈:" << std::endl;
    std::stack<int> stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;
    std::cout << std::endl;
    
    // 队列
    std::cout << "队列:" << std::endl;
    std::queue<int> queue;
    queue.push(10);
    queue.push(20);
    queue.push(30);
    while (!queue.empty()) {
        std::cout << queue.front() << " ";
        queue.pop();
    }
    std::cout << std::endl;
    std::cout << std::endl;
    
    // 哈希表
    std::cout << "哈希表:" << std::endl;
    std::unordered_map<std::string, int> map;
    map["张三"] = 20;
    map["李四"] = 21;
    map["王五"] = 22;
    for (const auto& pair : map) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    return 0;
}

小结 ​

C++ 数据结构包括：

  1. 数组：

    • 一维数组
    • 二维数组

  2. 链表：

    • 单向链表
    • 双向链表

  3. 栈：

    • 后进先出（LIFO）
    • 使用数组实现
    • 使用 STL 的 stack

  4. 队列：

    • 先进先出（FIFO）
    • 使用数组实现
    • 使用 STL 的 queue

  5. 树：

    • 二叉树
    • 二叉搜索树
    • 树的遍历：中序遍历、前序遍历、后序遍历

  6. 哈希表：

    • 基于键值对的数据结构
    • 快速查找、插入和删除
    • 使用 STL 的 unordered_map

  7. 图：

    • 由节点（顶点）和边组成
    • 邻接矩阵表示图

关键概念：

  • 数据结构：计算机存储、组织数据的方式
  • 数组：存储相同类型的元素
  • 链表：动态数据结构，由一系列节点组成
  • 栈：后进先出（LIFO）的数据结构
  • 队列：先进先出（FIFO）的数据结构
  • 树：层次结构的数据结构
  • 哈希表：基于键值对的数据结构
  • 图：由节点（顶点）和边组成的数据结构

掌握数据结构是编写高效 C++ 程序的基础，在后续章节中，我们将学习 C++ 的面向对象编程。

Copyright © 2025-2026 京公网安备 11010102000001号 京ICP备2024078128号-1