06 数据结构与算法基础

数组

概念：长度固定的线性表，每个元素类型相同

考点：存储地址计算

矩阵

主要考察特殊矩阵的压缩存储问题：对称矩阵、三对角矩阵、稀疏矩阵

稀疏矩阵

矩阵坐标转换到数组坐标的解题技巧：带入特殊值

数据结构的定义

概念：计算机存储和组织数据的方式

逻辑结构划分

• 线性结构
• 非线性结构
  • 树
  • 图

线性表

分类

• 顺序表（一维数组形式）

• 链表（节点包含数据与指针）

  • 单链表
  • 循环链表
  • 双向链表

• 队列（先进先出）

  • 顺序队列
  • 循环队列

  

• 栈（先进后出）

链表的基本操作（删除和插入节点）

顺序存储和链式存储对比：

广义表

概念：线性表的推广，以递归的方式进行定义

广度（最外层括号包含的元素个数）、深度（包含括号的重数）

表头head（最外括号的第一个元素）、表尾tail（除去表头的其他所有部分）

串

字符串的基本数据元素是字符，是取值范围受限的线性表。

树与二叉树

结点的度：孩子数

数的度：所有结点度数最高的度

内部节点：非头节点和叶子节点

深度：最大的层数

二叉树

二叉树与树的区别：二叉树要区分左子树和右子树，树不用区分；二叉树节点的最大度为2

重要性质：n0=n2+1，其中n0为终端节点，n2为度为2的节点

特殊二叉树

• 满二叉树
• 完全二叉树（除最后一层，上面层都满；且最后一层从左到右没有中间缺失的情况）

二叉树遍历

• 前、中、后序遍历：差别在根节点前、中、后时候被访问

  • 前：根、左、右
  • 中：左、根、右
  • 后：左、右、根

• 层次遍历

反向构造二叉树

例题：

树转二叉树

原则：

• 孩子结点 -> 左子树结点
• 兄弟结点 -> 右孩子结点

除了挨个用【原则】分析，还可以用连线法：如上图的虚线图所示。将兄弟结点连起来，并将第一个孩子以外的孩子结点的连线去掉，然后旋转，得到最终的二叉树

查找二叉树（二叉排序树）

特点：

• 左孩子小于根
• 右孩子大于根
• 极大提高查找速度
• 中序遍历，可得到一个码递增的序列

操作：插入和删除结点

最优二叉树（哈夫曼树）

哈夫曼树：用于无损压缩

基本概念：

• 树的路径长度：每个节点到根节点的路径长度
• 权（每个结点的数值，一般表示出现的频度）
• 带权路径长度
• 树的带权路径长度（树的代价）

构造哈夫曼树：即构造带权路径长度最小的树

例题：

求解树的带权路径长度：将所有叶子结点的带权路径长度相加

线索二叉树

why：很多结点的左右指针是空的，可以利用这些空闲指针，来方便遍历

• 前序线索二叉树
• 中序线索二叉树
• 后序线索二叉树

构造线索二叉树：左右线索指针指向的是x序排列的前/后面的结点

平衡二叉树

定义：

• 左右子树深度相差不超过1
• 每个结点的平衡度（左子树深度-右子树深度）只能为-1，0，1

非平衡二叉树 -> 平衡二叉树

图

概念：由顶点集合V和边集合E组成

图与树最大的区别：树没有环路

分类：

• 有向图：有向边也称为弧
• 无向图
• 完全图（可连的边都连了）

特殊：

• 连通图：针对无向图，任意两顶点之间都有路径
• 强连通图：针对有向图，任意两顶点之间都有路径
• 网：边有权值的图

存储

• 邻接矩阵

• 邻接链表

图的遍历

• 深度遍历
• 广度遍历

根据邻接表进行遍历：广度是一个结点所连的线走到底，深度是连续试探第一个

拓扑排序

表示活动之间开始的先后关系

执行完把连线去掉，继续分析

图的最小生成树

使得留下来的边（n-1条，n为节点数）构成树（注意不能有环），权值总和最小

普利姆算法（以点为主）

分析：画图时实时将结点分成两个阵营，寻找到另一个阵营的最短边

克鲁斯卡尔算法（以边为主）

依次选择权最小的边，注意不要构成环。连接所有结点后，即生成结束

算法基础

算法的特性

算法的复杂度

顺序查找和二分查找

顺序查找

二分查找

前提：查找内容本身是有序排序的

散列表

冲突解决：

• 开放定址法（增量查找，1、线性探测再散列；2、二次探测再散列；3、随机探测再散列）
  • 缺点：可能集中在一块
• 链地址法：将每个值对应的用链表串起来

排序（重要）

稳定性：值相同的数，排序后，顺序是否不变

内/外排序：前者只在内存中，后者用到外存

直接插入排序

希尔排序

是直接插入排序的一种，但更复杂。

好处是：经过前几轮的组内直接插入排序，序列已基本有序。到最后一轮的全组直接插入排序时，调整顺序的次数会更少。

直接选择排序

堆排序

堆的概念

堆排列概念和步骤：

初建堆过程：

• 顺次将结点数组构成完全二叉树
• 调整为堆（从最后一个非叶子结点开始，而后分析最后第二个）
• 注意，有的结点调整需要向下继续调整

重新建堆过程：

• 把根结点取走
• 把堆的最后一个结点放到根结点
• 从根节点开始与子节点对比，一直往下

所以，诸如从大量数据中求前10小的元素，比较有优势

冒泡排序

快速排序

分析：

• 分治法
• 与基准比较

归并排序

一般是两两合并

基数排序

基数和关键字的分解有关

排序算法分析（常考）