软件架构设计：数据结构与算法

一、数据结构概述

1. 数据结构的定义
   • 数据结构是数据元素之间的关系及其操作的集合。
2. 数据结构的分类
   • 逻辑结构：集合、线性结构、树形结构、图形结构。
   • 存储结构：顺序存储、链式存储、索引存储、散列存储。
3. 常见数据结构
   • 数组、链表、栈、队列、树、图、哈希表。

二、线性结构

1. 数组
   • 特点：连续存储、随机访问。
   • 操作：插入、删除、查找。
2. 链表
   • 单链表：每个节点包含数据和指向下一个节点的指针。
   • 双向链表：每个节点包含指向前后节点的指针。
   • 操作：插入、删除、查找。
3. 栈
   • 特点：后进先出（LIFO）。
   • 操作：入栈（push）、出栈（pop）、查看栈顶（peek）。
4. 队列
   • 特点：先进先出（FIFO）。
   • 操作：入队（enqueue）、出队（dequeue）。
   • 循环队列：解决普通队列的空间浪费问题。

三、树形结构

1. 树的基本概念
   • 节点、根节点、叶子节点、深度、高度。
2. 二叉树
   • 满二叉树：所有非叶子节点都有两个子节点。
   • 完全二叉树：除最后一层外，其他层都是满的。
   • 二叉搜索树（BST）：左子树的值小于根节点，右子树的值大于根节点。
3. 树的遍历
   • 前序遍历、中序遍历、后序遍历、层次遍历。
4. 平衡二叉树
   • AVL树：通过旋转操作保持平衡。
   • 红黑树：通过颜色标记保持平衡。
5. 堆
   • 最大堆：父节点的值大于子节点。
   • 最小堆：父节点的值小于子节点。
   • 应用：优先队列、堆排序。

四、图形结构

1. 图的基本概念
   • 顶点、边、有向图、无向图、权重。
2. 图的存储
   • 邻接矩阵、邻接表。
3. 图的遍历
   • 深度优先搜索（DFS）、广度优先搜索（BFS）。
4. 最短路径算法
   • Dijkstra算法（单源最短路径）。
   • Floyd算法（多源最短路径）。
5. 最小生成树
   • Prim算法、Kruskal算法。

五、查找算法

1. 顺序查找
   • 时间复杂度：O(n)。
2. 二分查找
   • 时间复杂度：O(log n)。
   • 前提：数据有序。
3. 哈希查找
   • 哈希函数的设计、冲突处理方法（开放地址法、链地址法）。

六、排序算法

1. 基本排序算法
   • 冒泡排序：时间复杂度O(n²)。
   • 选择排序：时间复杂度O(n²)。
   • 插入排序：时间复杂度O(n²)。
2. 高效排序算法
   • 快速排序：时间复杂度O(n log n)。
   • 归并排序：时间复杂度O(n log n)。
   • 堆排序：时间复杂度O(n log n)。
3. 其他排序算法
   • 希尔排序：基于插入排序的改进。
   • 基数排序：适用于非负整数。

七、算法设计

1. 分治法
   • 将问题分解为若干子问题，递归求解后合并结果。
   • 应用：归并排序、快速排序。
2. 动态规划
   • 将问题分解为重叠子问题，保存子问题的解。
   • 应用：背包问题、最长公共子序列。
3. 贪心算法
   • 每一步选择当前最优解，最终得到全局最优解。
   • 应用：最小生成树、最短路径。
4. 回溯法
   • 通过试探和回退寻找问题的解。
   • 应用：八皇后问题、图的着色问题。

八、常见考点与题型

1. 选择题：
   • 考察基本概念，如数据结构的特点、算法的时间复杂度。
2. 设计题：
   • 设计数据结构或算法解决特定问题。
3. 分析题：
   • 分析算法的时间复杂度、空间复杂度。

九、备考建议

1. 掌握核心概念：
   • 理解常见数据结构和算法的基本原理。
2. 熟悉算法实现：
   • 编写常见算法（如排序、查找、图遍历）的代码。
3. 结合实际应用：
   • 了解数据结构与算法在实际系统中的应用场景。
4. 多做真题：
   • 通过历年真题熟悉考试题型和难度。