数据结构和算法 笔记

概述

数据结构

• 按形状：集合、线性结构(1:1)、树形结构(1:n)、图状或网状结构(n:n)
• 按存储方式：逻辑结构、物理（存储）结构（顺序、链式）

任何一个算法的设计取决于选定的逻辑结构，实现依赖于采用的存储结构。

算法

• 特性：有穷性、确定性、可行性、输入、输出
• 算法效率的度量：事后统计、事前分析
• 复杂度分析：时间复杂度、空间复杂度

线性表

顺序表(顺序存储结构)

• 优点：存储单元连续，存储密度高，可随机存取
• 缺点：时间耗费在移动元素上，插入和删除操作需要移动表长一半的元素
• 类型：数组(列主序和行主序)、矩阵(压缩存储)

链表(链式存储结构)

存储单元任意，不能堆数据元素进行随机访问，插入和删除操作需要从头结点起查找被插入或删除结点的前驱结点，并修改这些结点的指针域，查找过程平均移动指针域为表长的一半，移动指针域操作比移动元素操作花费的时间少得多。

• 单向链表：一个指针域，只能从表中头结点出发
• 双向链表：两个指针域，可以从表中任意结点出发
• 循环链表：表尾结点的指针指向表中第一个结点

若要以复杂度为 O(1) 的时间代价将两个单链表链接成一个单链表，则这两个单链表分别为一个结点、任意结点。

栈和队列

• 存储：顺序存储和链式存储
• 栈：栈顶、栈底，仅操作栈顶(push & pop)，后进先出
• 队列：对尾、对头，对尾插入、对头删除，先进先出
• 双端队列：插入和删除在表的两端进行
• 循环队列：通常，循环队列比非循环队列的空间使用率要高

树

• 结点的度：结点拥有的子树数
• 叶子结点：度为0的结点
• 树的度：树内各结点的度的最大值
• 树的深度或高度：树中结点的最大层次

空间划分树比较:

二叉树

• 存储：顺序存储和链式存储
• 结点的度小于或等于2，二叉树第i层上至多有 \(2^{i-1}\) 个结点，深度为k的二叉树至多有 \(2^k-1\) 个结点
• 边的数目+1 = 点的数目
• 遍历：前序遍历、中序遍历、后序遍历

满二叉树和完全二叉树

• 满二叉树：深度为k，且有 \(2^k-1\) 个结点的二叉树
• 完全二叉树：采用顺序存储结构既简单又节省空间，具有n个结点的完全二叉树的深度为 \(\lfloor \log_2 (n+1) \rfloor\)

二叉排序树和堆

• 二叉排序树：左子树上所有结点均小于根结点，右子树上所有结点均大于根结点
• 堆：小根堆(孩子结点都大于父母结点)、大根堆(孩子结点都小于父母结点)

BSP Tree

KD Tree

四叉树

八叉树

图和网

• 类型：有向图、无向图、连通图
• 度：度、入度、出度
• 存储：邻接矩阵、邻接表
• 搜索：深度优先搜索、广度优先搜索
• 一个连通图的 生成树 是一个极小连通子图，它包含图中的全部顶点，但只有构成一棵树的 n − 1 条边；生成树的各边的权值总和称为生成树的权；把权值最小的生成树称为 最小生成树；若图中边上的权值各不相同，则该图的最小生成树是唯一的
• AOV网、AOE网、拓扑排序

1、除了 拓扑排序 外，判定一个 有向图存在回路 的方法还有 深度优先搜索 。

2、若无向图G中每个顶点的度至少为2，则G必存在回路。

3、无向图的邻接矩阵为对称阵。

查找

• 找到指定元素所需要进行的关键字比较次数的期望值称为 查找成功时平均查找长度：

  \[ ASL = \sum_{i=1}^nP_iC_i \]

静态查找

• 折半查找法：折半查找判定树，查找每个元素所进行的元素之间的比较次数小于或等于对应的“判定树”的深度；折半查找适用于数据元素按值有序排列并顺序存储的线性表，不适用于单链表，因为查找单链表结点时只能从头指针开始逐步搜索。

动态查找

• 二叉排序树(二叉查找树BST)
• 平衡二叉树
• B_树
  • 树中每个结点最多有m棵子树
  • 若根结点不是叶子结点，则最少有两颗子树
  • 除根结点之外的所有非终端结点最少有 \(\lceil \frac{m}{2} \rceil\) 棵子树

哈希(散列)表

1、在一般情况下，冲突处理方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子：

\[ 装填因子 \alpha = \frac{表中装入的记录数}{哈希表的长度} \]

2、由经验得知，为了降低发生散列冲突的可能性，在采用除留余数法构造的散列函数 \(H(k) = k \texttt{MOD} p\) 中，\(p\) 的取值最好是 一个质数或不包含小于20的质数的合数。

排序

内排序

• 插入排序
• 选择排序：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾，以此类推，直到所有元素均排序完毕
• 冒泡排序
• 谢尔排序
• 快速排序
• 堆积排序

外排序