深入解析：嵌入式第二十三篇——数据结构基本概念

一、数据结构的定义

数据结构是计算机中存储、组织数据的方式，旨在实现高效的数据访问和修改。它包含数据元素之间的逻辑关系、物理存储方式以及相关操作。

二、数据结构的基本知识

1、线性数据结构

（1）数组：连续内存存储相同类型元素，支持随机访问。

（2）链表：通过指针链接的节点组成，分为单向链表、双向链表和循环链表。

（3）栈：后进先出（LIFO）结构，支持压栈（push）和弹栈（pop）操作。

（4）队列：先进先出（FIFO）结构，包含普通队列、双端队列和优先队列。

2、非线性数据结构

（1）树：层次结构，常见类型包括二叉树、二叉搜索树、AVL树和堆。

（2）图：由顶点和边组成，分为有向图和无向图，常用邻接矩阵或邻接表存储。

3、基本操作

（1）插入：添加新数据元素。

（2）删除：移除指定数据元素。

（3）查找：检索特定元素的位置或值。

（4）遍历：按顺序访问所有元素。

（5）排序：按特定规则重新排列元素。

4、时间复杂度

（1）定义

时间复杂度用于描述算法运行时间随输入规模增长的变化趋势，通常用大O符号（O）表示。它关注的是最坏情况下或平均情况下操作次数的增长率，而非具体运行时间。

（2）常见时间复杂度类型

O(1) 常数时间
算法的执行时间不随输入规模变化。例如访问数组元素、哈希表查询。

O(log n) 对数时间
执行时间与输入规模的对数成正比。例如二分查找、平衡二叉树的搜索。

O(n) 线性时间
执行时间与输入规模成线性关系。例如遍历数组、链表。

O(n log n) 线性对数时间
常见于高效排序算法，如快速排序、归并排序。

O(n²) 平方时间
通常出现在嵌套循环中，如冒泡排序、选择排序。

O(2ⁿ) 指数时间
常见于穷举算法，如解决某些递归问题（斐波那契数列的朴素递归实现）。

（3）时间复杂度的计算方法

规则1：忽略低阶项
例如，T(n) = 3n² + 2n + 1 的时间复杂度为 O(n²)，仅保留最高阶项。

规则2：忽略常数系数
例如，T(n) = 5n³ 的时间复杂度为 O(n³)。

规则3：循环嵌套的乘法原则
单层循环的时间复杂度通常为 O(n)，嵌套循环则为各层循环复杂度的乘积。例如：

for i in range(n):       # O(n)for j in range(n):   # O(n)print(i, j)      # 总复杂度 O(n²)

（4）与其他复杂度概念的对比

空间复杂度
描述算法所需内存随输入规模的增长趋势，同样用大O表示法。例如，递归调用栈的空间复杂度可能为 O(n)。

平均情况与最坏情况
快速排序的平均时间复杂度为 O(n log n)，但最坏情况下（如已排序数组）可能退化为 O(n²)。

常见的时间复杂度所耗时间的大小排序
O(1)