C++数据结构与算法的基础知识和经典算法汇总

1. 基础知识

1.1 数据结构

数据结构是计算机存储、组织数据的方式。这里列出常见的数据结构，包括但不限于：

• 数组
• 链表
• 栈
• 队列
• 树
• 哈希表

1.2 算法

算法是解决问题的步骤和方法。下列是常见的算法：

• 排序算法
• 查找算法
• 字符串算法
• 图算法

1.3 复杂度

复杂度是算法性能的度量。常见的复杂度表示法有O(n)、O(logn)、O(n^2)等。其中，O(n)表示复杂度与问题规模n成正比，O(logn)表示复杂度与n的对数成正比，O(n^2)表示复杂度与n的平方成正比。

2. 经典算法汇总

2.1 排序算法

排序算法将一组无序数据按一定规则排序。这里列出几种常见的排序算法，包括但不限于：

• 冒泡排序
• 选择排序
• 插入排序
• 快速排序
• 归并排序

示例:

冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就交换位置。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

C++代码如下：

void bubble_sort(int arr[], int n) {
    for(int i=0; i<n-1; i++) {  //需要排序n-1次
        for(int j=0; j<n-i-1; j++) {
            if(arr[j] > arr[j+1]) {  //相邻元素比较
                swap(arr[j], arr[j+1]);  //元素交换
            }
        }
    }
}

快速排序

快速排序是一种高效的排序算法，它基于分治的思想，将大问题分成小问题进行解决。快速排序的核心在于选取一个基准元素，并将比它小的元素放到它的左边，比它大的元素放到它的右边，然后再分别对左右子区间进行递归排序，直到每个子区间只剩下一个元素。

C++代码如下：

void quick_sort(int arr[], int left, int right) {
    if(left >= right) return;   //递归终止条件
    int i = left, j = right, pivot = arr[left];
    while(i < j) {
        while(i < j && arr[j] >= pivot) j--;
        if(i < j) swap(arr[i++], arr[j]);
        while(i < j && arr[i] <= pivot) i++;
        if(i < j) swap(arr[i], arr[j--]);
    }
    arr[i] = pivot;
    quick_sort(arr, left, i-1);
    quick_sort(arr, i+1, right);
}

2.2 查找算法

查找算法是在数据集合中寻找特定元素的算法。这里列出几种常见的查找算法，包括但不限于：

• 顺序查找
• 二分查找
• 哈希查找

示例：

二分查找

二分查找，也称折半查找，是一种基于比较的查找算法。二分查找适用于有序数组，它通过将目标值与数组中间元素比较，从而将搜索范围缩小一半，接着不断地将搜索范围折半，直到找到目标元素或者确定目标元素不存在。

C++代码如下：

int binary_search(int arr[], int left, int right, int target) {
    while(left <= right) {
        int mid = left + (right-left)/2;
        if(arr[mid] == target) return mid;
        else if(arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

3. 总结

数据结构与算法是计算机科学的核心领域之一，它们应用广泛，是高效编程的关键。掌握数据结构与算法，对于编程能力的提升和职业发展都具有重要意义。