数据结构与算法

还是需要找个时间把算法都撸一遍才行

栈(Stack)、队列(Queue)和向量(Vector)

 链表

  单链表

  双向链表

  环形链表

  带哨兵节点的链表

哨兵节点(sentinel)是一个哑元节点(dummy node),可以简化边界条件。是一个附加的链表节点,该节点作为第一个节点,它的值域中并不存储任何东西,只是为了操作的方便而引入的

   有哨兵

    需要头部一个额外空间,不需要额外判断

   无哨兵

    不需要额外空间,增删改查需要额外判断为不为空

 栈

  栈的基本概念

  栈的性质

   后进先出

   压入栈~

  栈ADT及其顺序

  链接实现

   非连续存储空间,当前位置同时存储下一个的位置

  栈的应用

   括号匹配

    匹配到(的时候开一个栈,到)结束##最简单的一个处理方案的思想

   表达式计算

构成的树是同一个树,只是可以三种方式来解读

    前缀

     -*+3456

    中缀

     (3+4)*5-6

    后缀

     34+5*6-

  栈与递归

   递归与工作栈

   比如斐波那契数列

 队列

  队列的基本概念

  队列的性质

   先进先出

   末尾进入,队头出去

  队列ADT及其顺序

  链接实现

   就是个最小堆

  队列的应用

   树的层次遍历

   计算机系统中的资源竞争

 向量

  向量基本概念

   动态数组

  向量性质

  tips

   removeAll与retainAll都有以集合为集筛选的功能,将集合里的元素全部去除或保留

   删除元素会使size为0,但capacity不会重新分配

   toArray方法

    默认创建等长数组放完元素

    放入指定数组会将数组内容部分的替换

     一般尽可能多的替换

     指定数组长度大于vector的size的时候数组(vector的size的索引处会被设置成null)

     这也许算是一个陷阱吧

      实际上可能主要是起到一个分隔的作用

  向量ADT及其数组、链接实现

 树的基本概念和术语

  基本概念

  前序遍历

   根节点-->左子树-->右子树

  中序遍历

   左子树-->根节点-->右子树

  后序遍历

   左子树-->右子树-->根节点

  层次序遍历

   一层一层的

   用队列实现很合适

   具体实现

    利用队列

    顺序

     从左向右

     从上向下

    加入队列

    出队

    添加左右子节点

    重复操作

 二叉树

  定义

  性质

  普通树与二叉树的转化

   树本身满足拓扑排序

   (1)加线。就是在所有兄弟结点之间加一条连线;

   (2)抹线。就是对树中的每个结点,只保留他与第一个孩子结点之间的连线,删除它与其它孩子结点之间的连线;

   (3)旋转。就是以树的根结点为轴心,将整棵树顺时针旋转一定角度,使之结构层次分明。

   

   至于二叉树生成之后是什么样子这里不做考虑,AVL可以对它做比较好的调整

 存储结构

  完全树以数组形式存储

  存储

   顺序存储

    数组什么的

   链式存储

    指针

    Node

  表示方法

   父节点表示法

    存储父节点的位置索引

    

   子节点表示法

    存储第一个子节点的位置

    子节点存储它兄弟节点的位置

    

    前两者结合起来

    

   兄弟节点表示法

    父节点有指向所有子节点的指针

    常用的左右子树那种结构

 应用

  Huffman树的定义与应用

  其他应用,搜索相关,结构优化等

查找(search)

 概念

  没什么好说的~~

 线性关系结构查找

  顺序查找

  二分查找

 Hash查找

  常见Hash函数(非正式用途,仅理论学习)

   直接定址法

    简单,均匀,不产生冲突

    需要事先知道关键字的分布

    一般就是个映射关系(函数)

   除留余数法

    取模

     质数的选取很重要

    可能会有冲突

   数字分析法

    存在大量重复数据的不能用来做哈希值

   平方取中法

    关键字的平方

    取中间几位作为哈希值

   折叠法

    关键词分割之后处理

    处理完叠加

   随机数法

    与key有关的伪随机数构建hashtable

    考虑到的参数有关键词,哈希表长度等等

   似乎也没啥学习的必要2333

  hash冲突

   数据对应哈希值碰撞了

  解决冲突的方法

   开散列方法/拉链法

    链表实现

    优点

     ①拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;

     ②由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

     ③开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;

     ④在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结 点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

    缺点

     指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

   闭散列方法/开址定址法

    线性探测法

     dii=1,2,3,…,m-1

     冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表

    二次探测法

     di=12,-12,22,-22,…,k2,-k2 ( k<=m/2 )

     冲突发生时,在表的左右进行跳跃式探测,比较灵活

    伪随机序列法

     di=伪随机数序列。

     应建立一个伪随机数发生器,(如i=(i+p) % m),并给定一个随机数做起点

    再哈希法

     再散列法

      构造多个哈希函数

      Hi=RH1(key) i=1,2,…,k

      当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

     建立公共溢出区

      将哈希表分为基本表和溢出表两部分,发生冲突的元素都放入溢出表中。

    eg.

     例如,已知哈希表长度m=11,哈希函数为:H(key)= key % 11,则H(47)=3,H(26)=4,H(60)=5,假设下一个关键字为69,则H(69)=3,与47冲突。

     如果用线性探测再散列处理冲突,下一个哈希地址为H1=(3 + 1)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 + 2)% 11 = 5,还是冲突,继续找下一个哈希地址为H3=(3 + 3)% 11 = 6,此时不再冲突,将69填入5号单元。

     如果用二次探测再散列处理冲突,下一个哈希地址为H1=(3 + 12)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 - 12)% 11 = 2,此时不再冲突,将69填入2号单元。

     如果用伪随机探测再散列处理冲突,且伪随机数序列为:2,5,9,……..,则下一个哈希地址为H1=(3 + 2)% 11 = 5,仍然冲突,再找下一个哈希地址为H2=(3 + 5)% 11 = 8,此时不再冲突,将69填入8号单元。

  二次聚集现象

   在二次探测的基础上产生

   因为冲突之后寻找的位置也是相对聚集的

   解决方案

    双平方探测法

    再哈希法,不用二次探测

  设置表的大小为4K+3的素数很重要

   参考

   https://blog.csdn.net/zhishengqianjun/article/details/79087525#23-%E6%A3%80%E9%AA%8C

 BST树(Binary Search Tree)

  定义

  性质

  ADT及其实现

  BST树算法

   查找

   插入

   删除

 AVL平衡树

  定义

   带有平衡条件的二叉查找树

  分类

   单旋转

   双旋转

  性质

  ADT及其实现

  平衡树算法

   查找

   插入

   (删除)

  平衡因子的概念

 优先队列

  用堆实现的,所以和下面一个一起吧(只看下面一个就好了

  增删改查的处理细节

 堆

  定义

   自底向上

  堆的生成

  调整算法

  范围查询

排序

 基本概念

 Boring

  冒泡排序

   emmmmmmmm

   鸡尾酒排序

    双向冒泡,提高了一些效率

 常用排序算法思想

  插入排序

   插入

   折半插入

    一种优化的思路

  希尔排序

步长排序

   增量序列

    步长序列

   按步长分类,步长缩小,最后变成插入排序

  选择排序

就比如一直找最小的元素,然后排序

   字面意思

   按大小找元素,放到新组里

   按顺序排好

  快速排序

   选取一个元素(枢纽元)

    左中右三个取中间值

    降低选取不好的影响

   分治

    枢纽元交换到末尾

    左右开始将大于小于枢纽元的元素分开

    遍历完成枢纽元和右侧最终位置交换

    分割

    对左右区块分别做这个操作

  合并排序(归并排序)

二分

排序

合并

   merge,分治合并

  桶排序

先可以按区间分出一堆桶

分别塞入

对不为空的桶排序

排完再直接合并

当数据分布相对于桶而言均匀,效率最高

(即块分的比较好)

   相近元素结合

   排序

  基数排序

按位分割

LSD

分割之后再合并

对高位分割

再合并

MSD

从高位开始

   将元素按位分割

   LSD(最低有效位)

    适用于位数少的

    每次分割完合并再分割上一级

    Least Significant Digit

   MSD(最高有效位)

    适用于位数多的

    使用子桶

    Most Siginificant Digit

 外部排序

  是个很有意思的课题~~

  虽然不考就是了

图论

 基本概念

  无向图

  有向图

   有向无环图(Directed Acyclic Graph,DAG)

  常用符号及含义

   G

    Graph 图

   V

    Vertex 顶点

   E

    Edge 边

   digraph

    有向图

   adjacent

    邻接

   weight

    权重

   cost

    值

   path

    路径

   length

    一般指路径的长度

   underlying graph

    基础图

     有向图的边去掉方向之后的图是基础图

   complete graph

    完全图

     图的每一对顶点间都存在一条边的图

   连通

    强连通

     有向图每一个顶点到其他顶点都存在一条路径

    弱连通

     基础图是连通的

    连通的

     无向图每一个顶点到其他顶点都存在一条路径

   weighted path length

    赋权路径长

     按权重来计算路径长度,数值,可能还有正负之分

   unweighted path length

    无权路径长

     路径长度,权重默认为1

   negative-cost cycle

    负值圈

   biconnected

    双连通的

     连通无向图删除任意一个节点之后仍然连通则为双连通图

     删除了使得连通无向图不再连通的顶点叫割点

   深度优先搜索中的几种边

    背向边

    前向边

     从树的一个节点通向一个后裔

    交叉边

     把不直接相关的两个树节点连接起来

 存储结构

  邻接矩阵

   二维数组表示

    对应每一条边有一个值对应

    存在为1

    不存在为-1

    空间需求为Θ(V^2)

   适用于稠密表

  邻接表

   表存储

    对于每一个顶点,存储所有邻接的顶点

    空间需求O(|E|+|V|)

 遍历

  广度优先遍历

   找所有路径

   O(V)+O(E)=O(V+E)

   比较最短的时候,受限于路径节点数目和权重啥的(尤其是权重)可能会有欠缺

   适用于要计算非加权图中的最短路径

  深度优先遍历

   找最短路径

   计算每个节点周围最短路径的消耗的同时,更新当前可用路径

   所有节点计算完毕的同时,得出结果

   有负数圈时不适用

   应用

    找割点

    欧拉回路

    检测有向图是否是无圈图

    检测有向图是否是强连通的

  emmm,就是都有局限性来着,有个比较好的算法叫贝尔曼福德算法,美滋滋~~

 最小生成树

  基本概念

   无向图

    首先G必须是连通的,才会存在最小生成树

    该图连接G的所有顶点的边构成的树且总价值最低

  常用算法

   Prim算法

无向图上运行,所以需要存储两次节点之间的权

由选择的节点开始生长

堆的构造节省开销的原因因为省掉了其中已经有的元素

    连续的一步步长成,找最近的邻近节点

    无向图上运行

    不用堆 O(V^2)

    二叉堆 O(|E|og|V|)

   Kruskal算法

    连续的按照最小的权选择边

    最坏运行情况 O(|E|log|E|)此时|E|=O(V^2),即运行时间也可以看成O(|E|log|V|)

 最短路径问题

  单源最短路径

  广度优先遍历算法

按层处理顶点

距开始点最近的顶点首先被求值

而最远的那些顶点最后被求值

  Dijkstra算法

每个阶段选取距离最短的邻接节点

   贪婪算法

   解决赋权图的问题

  Floyd算法

原理是动态规划

使用邻接矩阵

每个点更新可达点的长度

   初始化邻接矩阵

   然后一个点一个点判断到可达点的当前最短通路

   可以解决负权的问题

   不可解决负权回路的问题

   复杂度

    时间O(N^3)

    空间O(N^2)

   参考

    https://blog.csdn.net/jeffleo/article/details/53349825

  拓扑排序

   对于有向无环图而言

   具体做到哪一步

    基本排好序

    在排好序的基础上根据邻接关系,推导出一个多叉树样子的东西

  Bellman Fold算法

   实际上只是检测了有没有负环,并没有解决负环的问题

   原理

    松弛

    负边权操作

    负环判定

 常用

  所有顶点的度为偶数的连通图必然有一个欧拉回路

  哈密尔顿圈问题

算法代码及基本时间复杂度分析

 加法规则

 乘法规则

 几个常用符号的定义

  f(n)表示某一算法在输入大小为n的情况下的工作效率,n趋向于很大的时候与另一行为已知的函数g(n)比较

  1)如果limf(n)/g(n)=0,则称f (n)在数量级上严格小于g(n),记为f (n)=o( g(n))。

  2)如果limf(n)/g(n)=无穷,则称f (n)在数量级上严格大于g(n),记为f (n)=w( g(n))。

  3)如果limf(n)/g(n)=c,这里c为非0常数,则称f (n)在数量级上等于g(n),即f (n)和g(n)是同一个数量级的函数,记为:f (n)=Θ( g(n))。

  4)如果f (n)在数量级上小于或等于g(n),则记为f (n)=O( g(n))。

  5)如果f(n)在数量级上大于或等于g(n),则记为f (n)=Ω( g(n))。

优先级标注表示暂时还没有太了解的东西暂时不学多半因为当时身体状态遭不住,,,

排序算法复杂度分析

普通树与二叉树的转化

读源代码增强记忆