数据结构知识体系总纲（线性表·树·图·查找·排序）思维导图

一、绪论与复杂度

• 数据、数据元素、数据项；逻辑结构与存储结构（顺序、链式、索引、散列）
• 抽象数据类型 ADT = 数据对象 + 关系 + 操作
• 时间复杂度：取最高阶项、忽略系数；常见阶 O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(2ⁿ)

二、线性表

• 随机访问 O(1)；插入删除平均移动 n/2 个元素，O(n)
• 动态扩容：容量不足时申请 2 倍空间并复制
• 单链表、双链表、循环链表、静态链表的结构差异

三、树与二叉树

• 第 i 层最多 2^(i-1) 个结点；深度 h 最多 2^h-1 个结点
• n₀ = n₂ + 1（叶子数 = 度为 2 的结点数 + 1）
• 完全二叉树父子下标：i 的左右孩子为 2i 与 2i+1，父为 ⌊i/2⌋

四、图

• 邻接矩阵：O(n²) 空间，适合稠密图，判边 O(1)

五、查找

六、排序

获取完整内容

• 付费内容：可交互导图、导出源文件与配套视频在亿卷 App 内提供