软考中级-软件设计师 数据结构与算法

考点

在软考中，数据结构与算法的考点主要集中在以下方面：

• 基本概念：掌握各类数据结构的定义、特点和应用场景。
• 常用算法的理解与应用：尤其是排序算法和查找算法的实现及复杂度分析。
• 递归与分治思想：通过实际案例理解递归和分治的原理和用法。
• 算法效率分析：理解时间复杂度和空间复杂度，能够分析给定算法的效率。

数据结构基础

数据结构是指一组数据的存储和组织方式，决定了数据的操作效率。主要包括线性结构和非线性结构，具体如下：

线性结构

线性结构的数据按顺序排列，典型的数据结构包括数组、链表、栈和队列。

• 数组：一种定长数据结构，优点是可以通过索引快速访问元素，但删除和插入操作的效率较低。
• 链表：由节点构成的链式存储结构，适合动态数据管理。链表分为单链表、双链表和循环链表，操作灵活，但需要额外的存储空间存放指针。
  反转链表

#include <iostream>
using namespace std;struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;ListNode* curr = head;while (curr != nullptr) {ListNode* nextTemp = curr->next;curr->next = prev;prev = curr;curr = nextTemp;}return prev;
}int main() {ListNode* head = new ListNode(1);head->next = new ListNode(2);head->next->next = new ListNode(3);head->next->next->next = new ListNode(4);head->next->next->next->next = new ListNode(5);ListNode* reversed = reverseList(head);while (reversed) {cout << reversed->val << " ";reversed = reversed->next;}return 0;
}
// 输出: 5 4 3 2 1

• 栈：一种“后进先出”（LIFO, Last In First Out）的数据结构，适用于递归和逆序操作。
• 队列：一种“先进先出”（FIFO, First In First Out）的数据结构，适合需要按顺序处理的场景。队列有普通队列、双端队列和循环队列等变种。

非线性结构

非线性结构的数据排列方式更为复杂，主要包括树、图等。

• 树：一种层次结构，每个节点有一个父节点和多个子节点。常见的树包括二叉树、平衡树、B树和红黑树等。树结构用于表达层级关系，适合快速查找和动态排序。
  使用递归计算二叉树的深度

/* 输入1/ \2   3/ \
4   5
*/
#include <iostream>
using namespace std;struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};int maxDepth(TreeNode* root) {if (!root) return 0;int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);return max(leftDepth, rightDepth) + 1;
}int main() {TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);cout << "最大深度: " << maxDepth(root);return 0;
}
// 输出: 最大深度: 3

• 图：一种更加复杂的非线性结构，由顶点和边构成，可以表示节点间的多对多关系。图分为无向图和有向图，广泛应用于网络连接、地图导航等场景。

常见算法

算法是解决特定问题的步骤集合，软考中级软件设计师考试常考的算法包括排序、查找、递归、分治和贪心算法等。

排序算法

排序算法是将数据按照一定顺序排列的过程。常见的排序算法包括：

• 冒泡排序：每次相邻比较交换，复杂度为 $O(n^2)$ 适用于小规模数据。是一种稳定的排序算法。

#include <iostream>
#include <vector>
using namespace std;void bubbleSort(vector<int>& arr) {int n = arr.size();for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {swap(arr[j], arr[j + 1]);}}}
}int main() {vector<int> arr = {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);for (int i : arr) cout << i << " ";return 0;
}
// 输出: 11 12 22 25 34 64 90

• 选择排序：每次选择最小（或最大）元素放到正确位置，复杂度为$O(n^2)$ 。是一种不稳定的排序算法。

#include <iostream>
#include <vector>
using namespace std;void selectionSort(vector<int>& arr) {int n = arr.size();for (int i = 0; i < n - 1; i++) {int min_index = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[min_index]) {min_index = j;}}swap(arr[i], arr[min_index]);}
}int main() {vector<int> arr = {64, 25, 12, 22, 11};selectionSort(arr);for (int i : arr) cout << i << " ";return 0;
}
// 输出: 11 12 22 25 64

• 插入排序：每次将一个元素插入已排序的部分，复杂度为$O(n^2)$ ，对少量元素时高效。是一种稳定的排序算法。

#include <iostream>
#include <vector>
using namespace std;void insertionSort(vector<int>& arr) {int n = arr.size();for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}
}int main() {vector<int> arr = {12, 11, 13, 5, 6};insertionSort(arr);for (int i : arr) cout << i << " ";return 0;
}
// 输出: 5 6 11 12 13

• 快速排序：分治算法的典型应用，通过选择“基准”将数据分割成两部分，复杂度为 $O(nlogn)$。是一种不稳定的排序算法，最坏的情况是数据基本有序的时候，时间复杂度为$O(n^2)$。

#include <iostream>
#include <vector>
using namespace std;int partition(vector<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++;swap(arr[i], arr[j]);}}swap(arr[i + 1], arr[high]);return i + 1;
}void quickSort(vector<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() {vector<int> arr = {3, 6, 8, 10, 1, 2, 1};quickSort(arr, 0, arr.size() - 1);for (int i : arr) cout << i << " ";return 0;
}
// 输出: 1 1 2 3 6 8 10

• 归并排序：也是分治算法，通过递归将数据不断分割、排序后合并，复杂度为 $O(nlogn)$。是一种稳定的排序算法。

#include <iostream>
#include <vector>
using namespace std;void merge(vector<int>& arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;vector<int> L(n1), R(n2);for (int i = 0; i < n1; i++) L[i] = arr[left + i];for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];
}void mergeSort(vector<int>& arr, int left, int right) {if (left >= right) return;int mid = left + (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);
}int main() {vector<int> arr = {12, 11, 13, 5, 6, 7};mergeSort(arr, 0, arr.size() - 1);for (int i : arr) cout << i << " ";return 0;
}
// 输出: 5 6 7 11 12 13

• 堆排序：基于堆这种特殊的树结构进行排序，复杂度为$O(nlogn)$。是一种不稳定的排序算法。

#include <iostream>
#include <vector>
using namespace std;// 调整堆，使得以i为根节点的子树满足最大堆性质
void heapify(vector<int>& arr, int n, int i) {int largest = i;       // 初始化 largest 为根节点int left = 2 * i + 1;  // 左子节点int right = 2 * i + 2; // 右子节点// 如果左子节点存在且大于根节点if (left < n && arr[left] > arr[largest]) {largest = left;}// 如果右子节点存在且大于当前最大节点if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大值不是根节点，则交换并继续堆化if (largest != i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}// 主函数，使用堆排序对数组进行排序
void heapSort(vector<int>& arr) {int n = arr.size();// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 一个个取出元素进行排序for (int i = n - 1; i > 0; i--) {// 将当前堆顶（最大值）移到数组末尾swap(arr[0], arr[i]);// 调整剩余堆heapify(arr, i, 0);}
}int main() {vector<int> arr = {12, 11, 13, 5, 6, 7};heapSort(arr);cout << "排序后的数组: ";for (int i : arr) cout << i << " ";return 0;
}
// 输出: 5 6 7 11 12 13

查找算法

查找算法用于在数据集合中寻找特定元素，常见的查找算法有：

• 顺序查找：逐个检查每个元素，复杂度为 O(n)，适用于无序数据。

#include <iostream>
#include <vector>
using namespace std;int linearSearch(const vector<int>& arr, int target) {for (int i = 0; i < arr.size(); i++) {if (arr[i] == target) {return i;  // 找到目标元素，返回其索引}}return -1;  // 未找到返回 -1
}int main() {vector<int> arr = {10, 20, 30, 40, 50};int target = 30;int index = linearSearch(arr, target);if (index != -1)cout << "元素 " << target << " 在索引 " << index << " 处";elsecout << "元素未找到";return 0;
}
// 输出: 元素 30 在索引 2 处

• 二分查找：要求数据有序，通过不断将搜索范围缩小一半，复杂度为 O(logn)。

#include <iostream>
#include <vector>
using namespace std;int binarySearch(const vector<int>& arr, int target) {int left = 0, right = arr.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;  // 找到目标值，返回索引}if (arr[mid] < target) {left = mid + 1;  // 目标值在右半部分} else {right = mid - 1; // 目标值在左半部分}}return -1;  // 未找到返回 -1
}int main() {vector<int> arr = {10, 20, 30, 40, 50};int target = 40;int index = binarySearch(arr, target);if (index != -1)cout << "元素 " << target << " 在索引 " << index << " 处";elsecout << "元素未找到";return 0;
}
// 输出: 元素 40 在索引 3 处

• 哈希查找：通过散列函数将键值直接映射到位置，查找效率高，但需要合理的哈希函数和冲突处理策略。

#include <iostream>
#include <unordered_map>
using namespace std;int hashSearch(const unordered_map<int, int>& hashTable, int target) {if (hashTable.find(target) != hashTable.end()) {return hashTable.at(target);  // 找到目标值，返回索引}return -1;  // 未找到返回 -1
}int main() {vector<int> arr = {10, 20, 30, 40, 50};unordered_map<int, int> hashTable;// 将数组元素存入哈希表中，键为元素值，值为索引for (int i = 0; i < arr.size(); i++) {hashTable[arr[i]] = i;}int target = 30;int index = hashSearch(hashTable, target);if (index != -1)cout << "元素 " << target << " 在索引 " << index << " 处";elsecout << "元素未找到";return 0;
}
// 输出: 元素 30 在索引 2 处

递归算法

    递归是指一个函数调用自身的方式，适合解决结构相似的问题。常见的递归算法包括斐波那契数列、阶乘计算、全排列等。

递归的基本思想是将问题分解成更小的子问题。实现递归算法时，必须定义好递归出口，以避免无限递归。

分治算法

    分治法将大问题分解成多个小问题分别求解，再将小问题的解合并得到原问题的解。快速排序和归并排序就是典型的分治法应用。

分治算法的一般步骤为：

1. 将大问题划分为若干子问题；
2. 递归解决每个子问题；
3. 合并子问题的结果。

动态规划

    动态规划是一种将复杂问题分解为多个子问题，通过保存子问题的解避免重复计算的策略，适合有重叠子问题和最优子结构的情况。

常见动态规划问题有背包问题、最长公共子序列、矩阵链乘法等。

贪心算法

    贪心算法是一种每一步选择当前最优解的策略，适合求解一些局部最优即全局最优的问题。例如：活动选择问题、最小生成树（Prim算法和Kruskal算法）等。

复杂度分析

算法复杂度分为时间复杂度和空间复杂度。

1. 时间复杂度：衡量算法执行时间随输入规模增长的变化。常见的时间复杂度有常数阶 $O(1)$、对数阶 $O(logn)$、线性阶 $O(n)$、平方阶$O(n^2)$ 等。
2. 空间复杂度：衡量算法运行时所需的额外空间。需要在设计算法时平衡时间和空间的效率。