数据结构

1、线性表

线性表按存储方式分为 顺序存储 和 链式存储，其 优缺点 不再赘述

线性表的基本操作：增删改查插计数等，注意链表的插入和删除等操作的指针指向顺序问题

链表有 单链表，循环链表，双向链表 等

2、栈与队列

栈：先进后出 的线性表
队列：先进先出 的线性表

栈的主要操作：出栈，入栈，取栈顶
栈分为 顺序栈、链栈

队列有 循环队列（注意判空判满的算法）、链队列、优先队列（有优先级的队列）

栈与队列的比较在此不再赘述

3、串与数组

串（通常指字符串）同样有 顺序存储 和 链式存储

串的常规算法有增删改查插截取比较等

模式匹配算法（在 s 主串中寻找 t 子串）：

• Brute-Force 算法
  子串以步长 1来一遍遍匹配
• KMP 算法

数组通常讨论 一维数组 和 二维数组

对称矩阵的压缩矩阵

三角矩阵的压缩矩阵

对角矩阵的压缩矩阵

稀疏矩阵的三元组表存储（数组下标、行下标、列下标、元素值）

4、树与二叉树

常用术语：
结点、结点路径、路径长度，结点的度，树的度、叶结点、分支结点、孩子结点、父结点、树的度...

二叉树：

• 概念
  • 满二叉树、完全二叉树
• 二叉树的存储：
  • 顺序存储结构：顺序表
  • 链式存储结构：定义结点类
• 树的遍历：先序遍历、中序遍历，后序遍历、层序遍历

哈夫曼树及哈夫曼编码：

• 解决的问题：有一堆带权值的结点，使带权路径总和最小
• 构造哈夫曼树：
  • 有 n 个结点，权值为
  • 选择其中最小的组成新的结点，权值为 wi，此时有 n-1 个结点，权值为
  • 再选择其中最小的两个，以此类推，得到哈夫曼树
• 哈夫曼编码：
  • 每个结点有其编码，左 0 右 1

树与僧林

• 树转换为二叉树：每个结点只保留最左孩子的度，所有孩子节点连接起来，并顺时针旋转一定角度
• 二叉树转换为树
• 森林转换为二叉树

树的存储结构：

• 双亲链表存储，属性有：data、parent
• 孩子链表存储，孩子以链表形式存储
• 双亲孩子链表存储
• 孩子兄弟链表存储