数据结构
#数据结构 2024-01-20

目录

数据结构是相互之间存在一种或多种特定关系的数据元素的集合
算法对特定问题求解步骤的一种描述

三要素：

  1. 逻辑结构
  2. 数据的运算
  3. 储存结构(物理结构，储存不同，运算的实现方法不同)

空间复杂度 运行时有程序代码内存（大小固定，与问题规模无关)，数据内存，
时间复杂度 平均情况假设每个基本事件概率相等，然后取平均数。

渐进分析 Asymptotic Analysis

数据是一个广义术语，代指各种类型信息

常用算法

  1. 分治Divide and Connquer
  2. 递归Recursion Algorithm
  3. 动态规划Dynamic Programmig
  4. 贪心算法Greedy Technique
  5. 回溯算法Back Tracking Method
  6. 分支界限Branch and Bound Method

存储方式

  1. 顺序储存
  2. 链式储存
  3. 索引储存(静态链表)
  4. 散列储存

算法必须是有穷的，程序可以是无穷的。

高效率，低储存量

时间复杂度按步数计算
常数1<对数logN<线性N<线性对数NlogN<平方N^2<立方N^3<指数x^N<阶乘N!<幂指N^N

尽管不能比较冒泡排序和选择排序，大 O 还是很重要的，因为它能够区分不同算法的长期增长率。
快速排序的每一轮处理其实就是将这一轮的基准数归位

最坏情况O 、最好情况Ω、平均情况Θ

树

树 具有层次关系的数据结构，是最小连通图
二叉树 子节点的最大个数是二
树和二叉树的转换 孩子兄弟表示法，firstchild作为左指针，nextsibling作为右指针。

中序遍历 指根中序遍历：左子树、根、右子树
分支节点 度不为零的结点，也称为非终端结点。
前缀编码 没有一个编码是另一个编码的前缀
哈夫曼树 给定一组具有确定权值的叶子结点，WPL最小的二叉树,亦称最优二叉树
堆 heap 是最高效的优先级队列
BST:binary sort tree 二叉排序树，二叉搜索树
  它的中序遍历存在有序性
binary balanced tree 平衡二叉树 AVL树，二叉平衡搜索树，
  左子树和右子树高度差不超过一。
  插入数据后调整最小的不平衡子树，利用左旋右旋
  平衡因子 左右子树高度差

所有结点都只有左子树的二叉树称为左斜树

层次遍历用队列

三叉链表 在二叉链表的基础上增加了一个指向亲代的指针域。

静态二叉链表 不用指针

优先队列 被出列的是优先级最高或低的元素的队列

选择树 Selection Tree,包括Winnner Tree和Loser Tree

并查集，Union-Find Disjoint Sets

用随意打乱的数据创建出来的树才有可能是比较平衡的。

红黑树 2-3-4树

栈

LIFO last in,first out

计算机调用栈 是用来记录每个调用中的函数的栈

共享栈 两个Stack(数组实现)共用同一片空间，从数组两头开始使用
后缀表达式 利用栈来实现

栈用来处理语法错误(括号错误)

卡特兰数 Catalan number 50

表达式求值

队列

FIFO fist in,first out

队列（空一位区分队满队空状态）用取余判断是否满了，（加数组）或者给每一位设置状态参数 ，(加大小量)一个存size的int

最小生成树

生成树(Spanning Tree) 连接V中所有顶点的一棵开放树（Free Tree，无环路的无向图）。
最小生成树(Minimum-cost Spanning Tree, MST) 在图G所有生成树中，代价(各边权值之和)最小的生成树称之，即包含全部顶点的极小连通子图。
prim算法 IMP:每次把到最小生成树的最短距离的点收入 时间复杂度O(V2),适用边稠密
kruskal IMP:每次加入一个最短边，并且保证不会形成回路。 时间复杂度O(ElogE)，适用边稀疏
双连通图 没有割点的图
强连通图 如果图中有一条有向回路，则任意两点间可互达，称之。
dijkstra算法 亦称SPF(shortest path first最短路径优先算法）
floyd算法 使任意两点间路径遍历一次，都尽量加入点缩短。

拓扑排序 偏序排序，IMP：每次取一个入度为零的点并删去关联的边，重复操作入队。

AOV：activity on vertex 在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。
AOE 带权有向图中，顶点表示事件，边表示活动，边上权表示活动的开销（如持续时间），则称之
  源点、汇点 仅有的一个入度为零的点，仅有的一个出度为零的点
  关键活动 从源点到汇点的WPL最大的路径称为关键路径，上边的活动称为关键活动
  最早发生时间 从源点开始的最短路径时间
  最迟发生时间 在不推迟整个工程完成的前提下，最迟发生的时间，从汇点开始推理
  利用拓扑排序确定每个事件的最早最晚开始时间，如果相等，则是个关键活动，加入关键路径中。

矩阵的储存

带状矩阵 当|i-j|>1时，aij=0.

图

图 是由顶点(vertex)的有穷非空集合和顶点之间边(edge)的集合组成的一种数据结构

极小连通子图 连通分量

图的遍历

  1. BFS
      广度优先生成树 BFS后路径形成的树
  2. DFS

最短路径

  1. Dijkstra算法 运行后找到的可能不是一条路径，而是分叉路径，但可以找到到任意点的最短路径。
  2. floyd算法 对每条边都尝试加入各个点看能不能缩短路径

有向无环图Directed Acyclic graph 题如其名，以把一部分子树合并的方法进行优化储存

邻接矩阵 adjacency matrix
  用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系
邻接表(链表表示)
  对于有向图的每个顶点vi，将从vi出发的弧到达的所有顶点链成一个单链表，称为顶点vi的出边表；
  再把所有出边表的指针和顶点信息的一维数组构成顶点表。
  入边表同理
十字链表( Orthogonal List ) 横向上是正邻接表，纵向上是逆邻接表
邻接多重表 类似于十字链表，但储存无向图。

查找(检索)

Average Search Length 平均查找长度 ASL,比较次数的期望值

静态查找表 只需查找，无需插入、删除操作

线性查找
折半查找 折半查找的判定树一定是平衡二叉树
分块查找
  均匀分块，块间有序，块内无序
  索引表中记录每个分块的最大关键字、分块的区间
  每个分块的内容可采用链式储存。
B树 多路平衡查找树 m-叉查找树
  除了根节点外任何非叶节点至少有 m/2上取整 个分叉，即至少有 m/2上取整-1 个关键字，B树的叶子必须在同一层上(对于任意节点，所有子树的高度都要
  相同)
B+树 经分块查找思想改造的B树，非终端节点只是记录端点，叶节点才是数据
散列表hash table
  装填因子表中记录数/散列表长度

拉链法、链地址法 当散列函数的值有冲突时，把所有的同义词储存在一个链表中
开放地址法 当散列函数的值有冲突时,把空余的地址利用起来
  1. 线性探测法
  2. 平方探测法散列表的长度必须是一个可以表示为4j+3的素数
  3. 伪随机序列法
再散列法 当散列函数的值有冲突时,用下一个散列函数计算地址

常见的散列函数

  1. 取余法用一个小于等于散列表长度的质数取余
  2. 直接定址法 哈希值设置为key的线性函数
  3. 数字分析法 取key的一部分作为散列地址
  4. 平方取中法 取key的平方的中间几位

排序

冒泡排序 每次把待排序中最小的冒到前边
快速排序 任取一个元素做基准，利用双指针进行一次划分

直接选择排序 每一次在待排序元素中选取关键字最小的元素加入有序子序列
锦标赛排序
堆排序 基于堆的排序，如基于大根堆进行下坠操作后取堆根入队列得到递增序列，

直接插入排序 每一次把待排序元素加入有序子数列的合适位置
折半插入排序 优化，插入时实现折半查找
Shell排序 将待排序表间隔d(逐渐减少到一) 的元素取到一起分为子表，对子表进行直接插入排序

归并排序
  递归式地把数组不断二分进行归并，可以把一个数组有序化
  归并把多个有序数组合并成一个数组。
基数排序 把关键字分为权重不同的关键字，所有的小关键字都在零到基数左范围内。小关键字组按权重从小到大利用队列对小关键字进行分配和搜集

稳定性 排序过程中尽量不改变原本相同元素的相对位置

外部排序
  操作系统是以”块”为单位对磁盘储存空间进行管理的，

  1. 构造归并段(从磁盘写入块并内部排序后写回磁盘)
  2. 两两归并(递归)
    优化多路归并
    优化减少初始归并段数量

败者树 直接比较k个归并段选出最值元素需要对比k-1次，构建败者树使关键字对比次数减少到 log k上取整 次
置换-选择排序 利用内存工作区构建一个筛选法则，每次内存工作区满了就重新开辟一个归并段
最佳归并树 即Huffman-k叉树，构建的归并树的带权路径长度WPL(weighted path length)最小
  虚段对于k-叉归并，若(初始归并段数量-1)%(k-1)!=0,则无法构成严格的k-叉归并树，则需要补充几个长度为零的虚段