本文还有配套的精品资源，点击获取

简介：《C C++常用算法手册》系统介绍了C和C++中常用的算法，重点讲解了数据结构在算法中的应用，并结合C++ STL展示了算法的实现与应用，旨在提升程序员解决复杂问题的效率。本书包含了丰富的示例和练习，帮助读者深入理解算法的时间和空间复杂度分析，并通过实践加强理解。覆盖排序、搜索、图算法、动态规划、树算法、字符串处理、数论与组合数学以及贪心算法等多个领域，强调递归和迭代、指针与引用的使用，以及内存管理。最终目标是增强读者的编程能力和问题解决技巧。

1. C和C++常用算法概述

在当今IT行业，C和C++语言由于其高性能、灵活的内存管理和接近硬件的操作能力，成为了许多系统级应用和游戏开发的首选。掌握C和C++中的常用算法，是构建高效、稳定应用的基础。本章将带你概述C/C++中的基础算法，为深入学习后续章节打下坚实的基础。

1.1 C/C++算法的重要性

C和C++算法是解决问题的一系列定义明确的指令集合。在C/C++中，算法通常用于数据结构的操作，如排序、搜索、插入、删除等。掌握这些算法对于编写优化代码至关重要，因为它们直接影响程序的运行效率和资源消耗。

1.2 算法的分类

算法可以根据其目的和特性进行分类。C/C++中的算法大致可以分为以下几类：

• 基本算法：如遍历、统计、查找和比较等。
• 排序算法：如冒泡排序、选择排序、插入排序、快速排序、归并排序等。
• 搜索算法：如线性搜索、二分搜索等。
• 复杂算法：如动态规划、贪心算法、回溯算法等。

通过本章的学习，你将了解这些算法的基本原理和实现，为解决实际问题提供工具和思路。让我们开始探索C和C++中常用的算法世界。

2. 基本数据结构理解

2.1 线性结构

2.1.1 数组

数组是编程中最基本的数据结构之一，它是一种线性数据结构，用于存储相同类型元素的集合。数组中的元素可以通过索引直接访问，索引从0开始。

在C++中，数组的声明和初始化通常如下所示：

int myArray[5] = {1, 2, 3, 4, 5};

这里声明了一个名为 myArray 的数组，包含5个整数元素。每个元素可以通过 myArray[i] 的形式访问，其中 i 是元素的索引。

数组的使用场景

数组适用于需要频繁通过索引访问元素的场景，因为它的随机访问性能非常优秀。数组还适用于元素数量固定不变的场景，因为它在内存中是一块连续的空间。

数组的限制

尽管数组在内存中分配是一块连续的空间，提高了访问速度，但这同样也是数组的限制所在。当数组空间不足以存储更多的数据时，需要进行数组的复制和重新分配，这个过程会带来性能开销。另外，数组的大小在声明之后是不可变的，这限制了数组的灵活性。

2.1.2 链表

链表是一种动态的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表允许在运行时动态地插入和删除元素。

单向链表是最简单的链表结构，每个节点有数据和一个指向下个节点的指针：

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

链表的每个节点通过指针连接，因此链表不保证元素在内存中连续存储，这使得链表的随机访问性能不如数组，但插入和删除操作更加灵活。

链表的使用场景

链表最适合于元素数量不固定的情况，例如实现队列和堆栈等数据结构。链表的节点可以按需分配和释放，适应不同的内存使用情况。

链表的限制

由于链表的元素不是连续存储，因此它不能像数组那样直接通过索引访问元素，这使得链表的随机访问性能较差。此外，链表的每个节点都需要额外存储指针信息，这增加了内存的使用。

2.1.3 栈

栈是一种后进先出（LIFO, Last In First Out）的数据结构，它只允许在表的一端进行插入和删除操作。

在C++中，可以使用数组或者链表实现栈的功能。栈的几个基本操作通常为 push() （进栈）、 pop() （出栈）、 top() （查看栈顶元素）和 isEmpty() （检查栈是否为空）。

使用数组实现栈的基本结构如下：

#define MAXSIZE 100
int stack[MAXSIZE];
int top = -1;

void push(int item) {
    if (top >= MAXSIZE - 1)
        cout << "Stack overflow\n";
    else
        stack[++top] = item;
}

int pop() {
    if (top < 0) {
        cout << "Stack underflow\n";
        return -1;
    }
    else
        return stack[top--];
}

栈的使用场景

栈的后进先出性质使其在实现函数调用、表达式求值等场景非常有用。例如，编译器在编译过程中会使用栈来管理变量的作用域。

栈的限制

栈是受限的线性结构，仅支持在一端进行操作。这种限制使得栈并不适用于那些需要对元素进行随机访问的场景。

2.1.4 队列

队列是一种先进先出（FIFO, First In First Out）的数据结构，它允许在一端添加元素，在另一端删除元素。

与栈类似，队列的基本操作通常为 enqueue() （入队）、 dequeue() （出队）、 front() （查看队首元素）和 isEmpty() （检查队列是否为空）。

使用数组实现队列的基本结构如下：

#define MAXSIZE 100
int queue[MAXSIZE];
int front = 0;
int rear = -1;

void enqueue(int item) {
    if (rear >= MAXSIZE - 1)
        cout << "Queue overflow\n";
    else
        queue[++rear] = item;
}

int dequeue() {
    if (front > rear) {
        cout << "Queue underflow\n";
        return -1;
    }
    else
        return queue[front++];
}

队列的使用场景

队列广泛应用于各种场景，如操作系统的进程调度、打印任务的管理、网络数据包的传输等，其中先进先出的性质是核心要求。

队列的限制

像栈一样，队列也是一种受限的线性结构，其限制了在队列中元素的访问和操作。当需要对队列进行复杂的操作时（例如随机删除元素），队列可能不是最佳的数据结构选择。

2.2 非线性结构

2.2.1 树的基本概念和分类

树是一种非线性数据结构，它模拟了自然界中树的结构。在树形结构中，每个节点都可以有零个或多个子节点，这样的节点被称为子节点，而没有子节点的节点被称为叶节点。

树的基本组成部分

• 节点（Node） ：树中的基本单元，包含数据和指向子节点的指针。
• 边（Edge） ：节点之间的连接线。
• 根节点（Root） ：树中没有父节点的特殊节点。
• 叶节点（Leaf） ：没有子节点的节点。
• 子树（Subtree） ：任何节点及其后代构成的集合。

树的分类

• 二叉树 ：每个节点最多有两个子节点的树。
• 满二叉树 ：除叶节点外，每个节点都有两个子节点的二叉树。
• 完全二叉树 ：除了最后一层外，其他层都是满的，并且最后一层的节点都靠左排列。
• 平衡二叉树（AVL树） ：任何两个子树的高度差不超过1的二叉树。
• 红黑树 ：一种自平衡的二叉查找树。
• B树和B+树 ：用于数据库和文件系统中，优化了磁盘读写操作。

2.2.2 图的表示和应用

图是由一组顶点和连接顶点的边组成的非线性数据结构。图可以用来表示现实世界中许多复杂的关系，如社交网络、交通网络和通信网络等。

图的表示方法

• 邻接矩阵 ：一个二维数组，行和列分别表示顶点，如果顶点i和顶点j之间有边则matrix[i][j]为1，否则为0。
• 邻接表 ：一个顶点列表，每个顶点都存储一个链表，链表中存储与该顶点相邻的顶点。

图的应用

• 社交网络 ：如Facebook、LinkedIn等社交网络中的用户和好友关系可以用图表示。
• 网络路由 ：路由器之间的网络路径可以使用图来模拟。
• 推荐系统 ：在电商网站中，根据用户的购买历史推荐商品可以用图的算法实现。

图的算法

• 深度优先搜索（DFS） ：沿着图的边深入探索尽可能远，直到到达一个没有未访问的邻居的节点，然后回溯。
• 广度优先搜索（BFS） ：逐层访问所有邻接节点。
• 最短路径算法 ：如Dijkstra算法和Floyd-Warshall算法，用于找出图中两点之间的最短路径。

在接下来的章节中，我们将深入探讨非线性结构中树和图的更多细节和应用实例，包括它们的具体实现和优化策略。

3. 排序算法与STL的sort函数

3.1 排序算法原理

排序算法是计算机科学中的一项基础技术，广泛应用于数据处理和软件开发领域。理解排序算法原理对于提升数据处理效率和优化软件性能至关重要。

3.1.1 快速排序的原理和实现

快速排序（Quick Sort）是一种分而治之的排序算法，它通过一个划分操作将数据分为独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再递归地对这两部分数据分别进行快速排序，以达到整个序列有序。

快速排序的平均时间复杂度为O(nlogn)，在平均情况下表现优异。以下是一个快速排序的实现示例：

#include <iostream>
#include <vector>

void quickSort(std::vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int pivot = nums[left];  // 选择基准点，这里选择最左边的元素
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] > pivot) j--;  // 从右向左找到第一个小于基准的元素
        if (i < j) nums[i++] = nums[j];  // 将其放到左边
        while (i < j && nums[i] <= pivot) i++;  // 从左向右找到第一个大于基准的元素
        if (i < j) nums[j--] = nums[i];  // 将其放到右边
    }
    nums[i] = pivot;  // 将基准放到中间位置
    quickSort(nums, left, i - 1);  // 对左部分进行递归排序
    quickSort(nums, i + 1, right);  // 对右部分进行递归排序
}

int main() {
    std::vector<int> data = {10, 7, 8, 9, 1, 5};
    quickSort(data, 0, data.size() - 1);
    for (int num : data) {
        std::cout << num << " ";
    }
    return 0;
}

快速排序的关键在于划分操作，该操作将数组分为两部分，并确定基准元素的最终位置。在上述代码中，基准元素选为最左边的元素， i 和 j 分别指向数组的两端，并不断向中间靠拢，直到找到所有需要交换的元素。

3.1.2 归并排序的原理和实现

归并排序（Merge Sort）是另一种有效的排序算法，它采用分治策略将数据分成更小的部分，先对这些部分分别排序，然后将结果归并起来。

归并排序的时间复杂度在最好、最坏和平均情况下均为O(nlogn)，特别适合于链表等数据结构。下面是一个归并排序的实现示例：

#include <iostream>
#include <vector>

void merge(std::vector<int>& nums, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    std::vector<int> L(n1), R(n2);

    for (int i = 0; i < n1; i++)
        L[i] = nums[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = nums[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            nums[k] = L[i];
            i++;
        } else {
            nums[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        nums[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        nums[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(std::vector<int>& nums, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
}

int main() {
    std::vector<int> data = {12, 11, 13, 5, 6, 7};
    mergeSort(data, 0, data.size() - 1);
    for (int num : data) {
        std::cout << num << " ";
    }
    return 0;
}

在归并排序中， merge 函数是核心，它将两个已排序的序列合并为一个。这个函数首先创建临时数组 L 和 R 来存储两个子序列，然后逐步合并这些序列，最后将合并后的结果复制回原数组。

3.1.3 堆排序的原理和实现

堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法。二叉堆可以被看作一个完全二叉树，其每个节点的值都不大于（或不小于）其子节点的值。

堆排序分为两个阶段：建立堆和排序。建立堆的时间复杂度为O(n)，排序的时间复杂度为O(nlogn)。下面是堆排序的实现：

#include <iostream>
#include <vector>

void heapify(std::vector<int>& nums, int n, int i) {
    int largest = i;  // 初始化最大为根
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    // 如果左子节点大于根节点
    if (left < n && nums[left] > nums[largest])
        largest = left;

    // 如果右子节点比最大的还大
    if (right < n && nums[right] > nums[largest])
        largest = right;

    // 如果最大不是根节点
    if (largest != i) {
        std::swap(nums[i], nums[largest]);
        heapify(nums, n, largest);
    }
}

void heapSort(std::vector<int>& nums) {
    int n = nums.size();
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(nums, n, i);
    // 一个个从堆顶取出元素
    for (int i = n - 1; i > 0; i--) {
        std::swap(nums[0], nums[i]);
        heapify(nums, i, 0);
    }
}

int main() {
    std::vector<int> data = {12, 11, 13, 5, 6, 7};
    heapSort(data);
    for (int num : data) {
        std::cout << num << " ";
    }
    return 0;
}

heapify 函数用来维护堆的性质，它通过比较父节点和其子节点的值，来决定是否需要交换它们，直到达到最大堆或最小堆的要求。堆排序中，首先通过 heapify 建立最大堆，然后通过不断取堆顶元素，并调整剩余元素以维持堆的性质来完成排序过程。

4. 搜索算法与图算法

4.1 线性搜索和二分搜索

4.1.1 线性搜索的原理和实现

线性搜索是最基本的搜索算法，它通过从数组的一端到另一端依次检查每个元素来查找目标值。它不需要数据事先排序，但效率较低，其时间复杂度为O(n)，其中n是数据集中元素的数量。

以下是线性搜索的简单实现代码：

#include <iostream>
using namespace std;

int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // 返回找到目标值的索引
        }
    }
    return -1; // 如果没有找到，则返回-1
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    int index = linearSearch(arr, size, target);
    if (index != -1) {
        cout << "找到目标值的索引: " << index << endl;
    } else {
        cout << "未找到目标值" << endl;
    }
    return 0;
}

在执行逻辑上， linearSearch 函数接受一个整型数组 arr 、数组的大小 size 和目标值 target 作为参数。该函数遍历数组，比较每个元素与目标值。如果找到目标值，函数返回当前索引；如果没有找到，函数返回-1。这个函数的执行过程非常直观，适合对未排序数据的搜索。

4.1.2 二分搜索的原理和实现

与线性搜索不同，二分搜索算法要求数据必须是有序的。它通过比较数组的中间元素与目标值，来判断目标值是在中间元素的左侧还是右侧，然后决定是继续在左侧还是右侧的子数组中搜索。由于每次比较都将搜索范围减半，因此二分搜索的时间复杂度为O(log n)，显著优于线性搜索。

下面展示了二分搜索的实现代码：

#include <iostream>
using namespace std;

int binarySearch(int arr[], int size, int target) {
    int low = 0, high = size - 1;
    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; // 如果没有找到，则返回-1
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    int index = binarySearch(arr, size, target);
    if (index != -1) {
        cout << "找到目标值的索引: " << index << endl;
    } else {
        cout << "未找到目标值" << endl;
    }
    return 0;
}

在这段代码中， binarySearch 函数采用迭代的方式实现了二分搜索。函数初始化 low 和 high 两个指针，分别指向数组的首尾。然后在一个循环中不断计算中间位置 mid 并比较中间元素与目标值。如果中间元素不是目标值，根据比较结果调整 low 和 high 的值，继续搜索。如果找到了目标值，返回其索引；如果未找到，最终返回-1。

二分搜索通过减少搜索范围极大地提高了搜索效率，特别是在处理大数据集时，它比线性搜索更快。然而，在使用二分搜索之前，必须确保数据集是有序的，否则这个算法将不适用。

5. 高级算法技巧与实战应用

5.1 动态规划

动态规划是解决复杂问题的一个强大工具，特别是问题可以分解为重叠子问题，并且这些子问题的解可以通过简单的规则从其他子问题的解中构造出来时。动态规划的关键在于找到问题的最优子结构，并且存储这些子问题的解以避免重复计算。

5.1.1 背包问题的动态规划解法

背包问题是一个典型的动态规划问题，要求在限定的总重量内，如何选取物品以达到最大价值。

一个简单的0-1背包问题的动态规划解法如下：

#include <iostream>
#include <vector>
using namespace std;

int knapsack(int W, const vector<int>& wt, const vector<int>& val, int n) {
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int w = 1; w <= W; ++w) {
            if (wt[i-1] <= w) {
                // 可以选择放入或不放入背包
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
            } else {
                // 不能放入背包
                dp[i][w] = dp[i-1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    int n = 4; // 物品数量
    vector<int> wt = {10, 20, 30, 40}; // 物品重量
    vector<int> val = {60, 100, 120, 120}; // 物品价值
    int W = 50; // 背包最大承重

    cout << "The maximum value in the knapsack is " << knapsack(W, wt, val, n);
    return 0;
}

上述代码中， dp[i][w] 表示前 i 个物品在限制重量为 w 的情况下能达到的最大价值。通过这个二维数组 dp ，我们可以回溯地找出构成最大价值的物品组合。

5.1.2 最长公共子序列

最长公共子序列问题也是动态规划的经典应用，可以用来比较两个序列的相似度。

#include <iostream>
#include <vector>
using namespace std;

int lcs(string X, string Y) {
    int m = X.length(), n = Y.length();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (X[i-1] == Y[j-1]) {
                dp[i][j] = 1 + dp[i-1][j-1];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    return dp[m][n];
}

int main() {
    string X = "ABCBDAB", Y = "BDCAB";
    cout << "Length of Longest Common Subsequence is " << lcs(X, Y);
    return 0;
}

上述代码中的 dp[i][j] 存储了 X[0..i-1] 和 Y[0..j-1] 的最长公共子序列的长度。通过填充这个二维数组，我们可以找到最长的公共子序列。

5.1.3 斐波那契数列的动态规划优化

斐波那契数列是一个经典的递归问题，但是递归方法的时间复杂度很高，可以通过动态规划来优化。

#include <iostream>
#include <vector>
using namespace std;

int fibonacci(int n, vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];

    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo);
    return memo[n];
}

int main() {
    int n = 10;
    vector<int> memo(n+1, -1);
    cout << "Fibonacci number " << n << " is " << fibonacci(n, memo);
    return 0;
}

上述代码中，我们使用了一个数组 memo 来存储已经计算过的斐波那契数列的值，避免重复计算，这样就将原本指数级的时间复杂度降低到了线性时间。

动态规划是一种非常重要的算法技巧，它要求我们能够识别问题中的重叠子问题，并有效地存储和利用子问题的解。在掌握了动态规划的基础知识后，解决实际问题时可以考虑是否可以应用该技巧，以达到更高效的算法实现。

本文还有配套的精品资源，点击获取

简介：《C C++常用算法手册》系统介绍了C和C++中常用的算法，重点讲解了数据结构在算法中的应用，并结合C++ STL展示了算法的实现与应用，旨在提升程序员解决复杂问题的效率。本书包含了丰富的示例和练习，帮助读者深入理解算法的时间和空间复杂度分析，并通过实践加强理解。覆盖排序、搜索、图算法、动态规划、树算法、字符串处理、数论与组合数学以及贪心算法等多个领域，强调递归和迭代、指针与引用的使用，以及内存管理。最终目标是增强读者的编程能力和问题解决技巧。

本文还有配套的精品资源，点击获取