数据结构部分

线性数据结构

数组(Array)

  • 定义：连续内存空间存储同类型数据
  • 特点：随机访问，固定大小
  • 操作：插入、删除、查找、遍历、排序

链表(Linked List)

  • 单向链表：每个节点存储数据和后继指针
  • 双向链表：每个节点存储数据和前驱、后继指针
  • 循环链表：尾节点指向头节点
  • 操作：插入、删除、查找、遍历、排序

栈(Stack)

  • 定义：后进先出(LIFO)的线性表
  • 操作：压栈(push)、出栈(pop)、获取栈顶(top)
  • 应用：函数调用、表达式求值、括号匹配

队列(Queue)

  • 定义：先进先出(FIFO)的线性表
  • 类型：普通队列、循环队列、双端队列
  • 操作：入队(enqueue)、出队(dequeue)
  • 应用：任务调度、缓冲区管理

非线性数据结构

树(Tree)

二叉树(Binary Tree)

  • 完全二叉树
  • 满二叉树
  • 遍历：前序、中序、后序、层序

二叉搜索树(BST)

  • 定义：左子树小于根节点，右子树大于根节点
  • 操作：插入、删除、查找
  • 平均时间复杂度：O(log n)

平衡二叉树(AVL Tree)

  • 定义：任意节点的左右子树高度差不超过1
  • 操作：左旋、右旋、插入、删除

红黑树(Red-Black Tree)

  • 特点：自平衡的二叉搜索树
  • 性质：根黑、叶黑、红子黑、黑高相等
  • 应用：STL容器实现

字典树(Trie)

  • 特点：用于存储和检索字符串
  • 应用：前缀匹配、自动补全

哈夫曼树(Huffman Tree)

  • 特点：带权路径长度最小的二叉树
  • 应用：数据压缩

图(Graph)

  • 表示：邻接矩阵、邻接表
  • 类型：有向图、无向图、带权图
  • 遍历：深度优先(DFS)、广度优先(BFS)
  • 算法：最短路径、最小生成树

堆(Heap)

  • 类型：最大堆、最小堆
  • 特点：完全二叉树
  • 操作：插入、删除最值、建堆
  • 应用：优先队列、堆排序

哈希表(Hash Table)

  • 定义：通过哈希函数将键映射到数组
  • 冲突解决：链地址法、开放地址法
  • 应用：快速查找、缓存系统