第三部分：数据结构与算法（概述）

C++中的数据结构与算法是程序设计的重要组成部分，以下是一些常见的数据结构和算法及其在C++中的实现与应用：

一、数据结构

1. 数组（Array）

数组是一种线性数据结构，它存储一组相同类型的元素，这些元素在内存中是连续存储的。

在C++中，可以使用原生数组或者std::vector（动态数组）来表示。

示例（使用原生数组）

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

示例（使用std::vector）

#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

2. 链表（Linked List）

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

单链表示例（节点定义和链表操作）

// 单链表节点定义
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};
// 构建单链表
ListNode* createLinkedList() {
    ListNode* head = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    head->next = node2;
    node2->next = node3;
    return head;
}
// 遍历单链表
void traverseLinkedList(ListNode* head) {
    ListNode* current = head;
    while (current!= NULL) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

3. 栈（Stack）

栈是一种后进先出（LIFO）的数据结构。在C++中，可以使用std::stack来实现栈的操作。

示例（使用std::stack）

#include <stack>
#include <iostream>
int main() {
    std::stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    while (!s.empty()) {
        std::cout << s.top() << " ";
        s.pop();
    }
    std::cout << std::endl;
    return 0;
}

4. 队列（Queue）

队列是一种先进先出（FIFO）的数据结构。在C++中，可以使用std::queue来实现队列的操作。

示例（使用std::queue）

#include <queue>
#include <iostream>
int main() {
    std::queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    std::cout << std::endl;
    return 0;
}

5. 树（Tree）

树是一种非线性的数据结构，由节点和边组成，有一个根节点，每个节点可以有零个或多个子节点。二叉树是树结构的一种特殊形式，其中每个节点最多有两个子节点（左子节点和右子节点）。

二叉树节点定义和简单遍历示例

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 前序遍历二叉树
void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    std::cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

6. 图（Graph）

图是由顶点（节点）和边组成的数据结构，可以用来表示各种复杂的关系，如社交网络中的人际关系、交通网络中的道路连接等。图可以分为有向图和无向图。

简单的图表示（邻接矩阵）和深度优先搜索示例（针对无向图）

#include <iostream>
#include <vector>
// 使用邻接矩阵表示无向图
class Graph {
    public:
        Graph(int numVertices) : numVertices(numVertices) {
            adjMatrix.resize(numVertices, std::vector<int>(numVertices, 0));
        }
        void addEdge(int src, int dest) {
            adjMatrix[src][dest] = 1;
            adjMatrix[dest][src] = 1;
        }
        void dfs(int startVertex) {
            std::vector<bool> visited(numVertices, false);
            dfsUtil(startVertex, visited);
        }
    private:
        int numVertices;
        std::vector<std::vector<int>> adjMatrix;
        void dfsUtil(int vertex, std::vector<bool>& visited) {
            visited[vertex] = true;
            std::cout << vertex << " ";
            for (int i = 0; i < numVertices; ++i) {
                if (adjMatrix[vertex][i] == 1 &&!visited[i]) {
                    dfsUtil(i, visited);
                }
            }
        }
};

二、算法

1. 排序算法

冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，它通过反复比较相邻的元素并交换它们（如果它们的顺序错误），直到整个数组被排序。

#include <iostream>
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
int main() {
    int arr[] = {2, 1, 9, 8, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

快速排序（Quick Sort）

快速排序是一种高效的排序算法，它采用分治策略。选择一个元素作为枢轴（pivot），将数组分为两部分，小于枢轴的元素和大于枢轴的元素，然后对这两部分递归地进行排序。

#include <iostream>
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
int main() {
    int arr[] = {5, 4, 3, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

2. 搜索算法

线性搜索（Linear Search）

线性搜索是一种简单的搜索算法，它顺序地遍历数组中的元素，直到找到目标元素或者遍历完整个数组。

#include <iostream>
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; ++i) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 3;
    int result = linearSearch(arr, n, target);
    if (result!= -1) {
        std::cout << "Element found at index: " << result << std::endl;
    } else {
        std::cout << "Element not found." << std::endl;
    }
    return 0;
}

二分搜索（Binary Search）

二分搜索是一种用于有序数组的高效搜索算法。它每次比较中间元素与目标元素，然后根据比较结果决定在数组的左半部分还是右半部分继续搜索。

#include <iostream>
int binarySearch(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low+(high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 3;
    int result = binarySearch(arr, 0, n - 1, target);
    if (result!= -1) {
        std::cout << "Element found at index: " << result << std::endl;
    } else {
        std::cout << "Element not found." << std::endl;
    }
    return 0;
}

C++编程语言基础

• C++：从入门到工作的教程
• 这是我的第一个 C++程序！
• C++中main函数有什么作用？
• C++中 #include 指令的作用
• C++中常用的预处理指令
• C++中 iostream 头文件定义了什么
• C++名称空间（namespace）
• C++标准库中 std 命名空间定义了些什么
• C++常用的头文件
• C++源代码的发布方式
• C++变量名的定义、变量的作用、使用规范
• C++的关键字列表
• C++数据类型：整型（整数类型）
• 二进制补码、原码、反码
• C++数据类型：char字符型（整数类型）
• ASCII码表及C++字符函数库（cctype）
• 计算机汉字编码
• C++数据类型：bool类型（整数类型）
• C++中 const 限定符
• C++数据类型：浮点数
• C++运算符：算术运算符
• C++运算符：类型转换规则
• 计算机数据存储大小端模式
• C++运算符：位运算 与 bitset类库
• C++运算符：关系运算符与逻辑运算符
• C++流程控制：顺序、选择、循环、跳转语句
• C++函数的定义、参数传递、重载、嵌套
• C++数组：一维、二维、多维数组的运用
• C-style字符串、库函数 与 std::string对象
• C++数据类型：结构体（struct）
• C++数据类型：联合体（union）
• C++数据类型：枚举（enum）
• C++数据类型别名：typedef
• C++指针
• C++内存操作符：new分配 与 delete释放
• C++标准模板库（STL）容器、算法、迭代器
• C++标准模板库（STL）vector顺序容器
• C++标准模板库（STL）array固定容器
• C++标准模板库（STL）list双向链表容器
• C++标准模板库（STL）deque双端队列
• C++标准模板库（STL）集合 set 关联容器
• C++标准模板库（STL）map关联容器
• C++标准模板库（STL）unordered_set
• C++标准模板库（STL）unordered_map
• C++标准模板库（STL）algorithm算法库
• C++文件操作
• C++数学库（cmath）数学常量与数学函数
• C++模板：函数模板、类模板
• C++与SQLite3联合打造实用的应用程序
• C++实战开发中常用的库（概述）
• 第二部分：C++面向对象编程
• C++：类的定义与声明、类对象应用
• 第三部分：数据结构与算法（概述）
• 第一部分：C++语言简介与学习路线