绪论

数据结构

数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。

逻辑结构

线性结构

一般线性表：线性表

特殊线性表：栈、队列、字符串

线性表的推广：数组、广义表

非线性结构

树结构：树、二叉树

图结构：有向图、无向图

集合结构

存储结构

顺序存储

逻辑上连续，物理上连续

优点：

  1. 随机访问高效：通过下标可直接访问元素，时间复杂度为 **O(1)**。
  2. 内存连续，缓存友好：数据连续存放，充分利用 CPU 缓存机制，访问效率高。
  3. 空间开销小：仅需存储数据，无需额外指针字段，内存利用率高。

缺点：

  1. 插入/删除效率低：在中间或头部操作时，需移动大量元素，时间复杂度为 **O(n)**。
  2. 固定容量：需预先分配连续内存空间，扩容需复制全部数据，动态扩展成本高。
  3. 内存浪费：若预分配空间过大，可能造成内存冗余。
链式存储

逻辑上不要求连续，物理上⼀定连续

优点：

  1. 动态内存分配：无需预先分配固定空间，按需动态扩展，内存利用率高。
  2. 插入/删除高效：仅需修改指针指向，时间复杂度为 **O(1)**（需先定位到操作位置）。
  3. 灵活性强：支持多种衍生结构（如双向链表、循环链表）。

缺点：

  1. 无法随机访问：查找元素需从头遍历，时间复杂度为 **O(n)**。

  2. 额外空间开销：每个节点需存储指针字段，占用更多内存。

  3. 内存碎片化：节点非连续存储，缓存命中率低，访问速度较慢。

算法的效率

算法是为了解决某类问题而规定的一个有限长的操作序列。

算法时间复杂度

一般情况，算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间量记作: T(n)=O(f(n))

算法空间复杂度

所⽤到的临时空间⼤⼩