数据结构与算法

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其关系的学科。

包括：逻辑结构， 存储结构 ，运算结构

什么是数据结构？

存储结构是逻辑结构在计算机中的实际表现，称为物理结构。它包括数据元素的表示和关系的表示。

什么是存储结构？

将内容放在连续的容器中，依照他们之间的相对位置来存储。（里面的数据是不具备关系的）

顺序结构

利用数据元素之间引用或者指针来建立关系（里面的数据随机分配）

链式结构

图示

数据结构（存储结构）

算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。

什么是算法？

数据是客观现实在计算机中的符号表现，一切可以运用计算并可以被计算机识别的符号就被称为数据。

什么是数据？

数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。

什么是数据元素？

数据元素中的一项被称为数据项，若干个数据项组成了数据元素。

什么是数据项？

数据结构（运算结构即算法）

程序=数据结构+算法

什么是程序？

时间复杂度是指程序执行的时间粒子的个数

什么时程序复杂度？

常数阶O(1) （没有循环一句话只跑一次）

对数阶O(logN) （循环为对应的while循环 里面的数值越来越靠近终止条件）

线性阶O(n) （for循环）

线性对数阶O(nlogN) （for循环+while循环）

平方阶O(n²) （俩个for循环）

立方阶O(n³) （三个for循环）

K次方阶O(n^k) （k次循环）

指数阶(2^n) （越来越多 ）

标准写法

时间复杂度

空间复杂度是指开辟的内容空间个数

什么是空间复杂度？

空间复杂度

衡量程序优劣

程序

数据结构与算法基本概述

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

什么是线性表？

有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2

有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1。

除第一个节点外，线性表中的其它结点ai(2≤i≤n)都有且仅有一个直接前趋ai-1。

除最后一个节点外，线性中的其它节点ai(1≤i≤n-1) 都有且仅有一个直接后继a i+1

线性表的特点

线性表的操作（接口）

有序 下标 长度不可变 存储同一类型数据

特点

数组操作

数组

单向链表的设计 （增删改）

单向链表

双向链表

链表 （依照元素的关系来建立联系

栈是一个特殊的线性表，他的特点为先进后出，后进先出。添加操作称为入栈，删除操作出栈。操作的位置永远是栈顶。栈底是第一次进入元素。当栈中没有元素称为空栈。

概述

栈的接口

使用数组来实现栈

使用链表实现栈

实现栈

解决迷宫寻路问题

栈

队列属于特殊的线性表，他主要特点是只允许在一端做插入（入队）另一端做删除（出队）。他是一个先进先出（FIFO）的容器。

队列接口

数组实现

顺序队列

链表实现

链式队列

队列

线性表

串就是字符串是由一个个的字符组成的有限序列。（char数组作为底层实现）

字符串概述

串接口

String类型 里面的char数组的长度由你的值来绝对StringBuffer 线程安全 长度可变 值的长度+16 （缓冲区）StringBuilder 线程不安全 长度可变 值的长度+16

实现类

串

树又被称为二叉树，由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成的一个树状结构。

术语

一棵非空二叉树的第i层上最多有2 i-1 个结点（i≥1）(每层节点数)

一棵深度为k的二叉树中，最多具有2 k -1个结点（总的节点数量）

对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有: n0＝n2＋1(叶子节点数)

具有n个结点的完全二叉树的深度k为[log 2 n]+1 （深度）

对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：（1）如果i>1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i＝1，则序号为i的结点是根结点，无双亲结点。（2）如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i>n，则序号为i的结点无左孩子。（3）如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；如果2i＋1>n，则序号为i的结点无右孩子。

此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为（i－1）/2，左孩子的编号为2i＋1，右孩子的编号为2i＋2。

性质

底层使用数组来实现

顺序二叉树

使用链表来实现二叉树（俩个单向链表）

链式二叉树

左边只能放比自己小的右只能放比自己大的

红黑树

翻转二叉树

哈夫曼树（haffman） 他又被称为最优二叉树（寻宝）。根据权值判断。对于多个叶节点，且带有权值。进行计算得出带权路径最小的为最优二叉树

各个(叶节点的权值*叶节点的路径长度)的总和=带权路径

哈夫曼树权值越大的叶节点离根节点越近，权值越小离根远

带权路径

由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F＝{T1，T2，…，Tn}；

在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；

在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；

重复步骤（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树

构建过程

哈夫曼树

树

无向图: 俩个顶点之间没有指向的图叫做无向图。有向图：俩个顶点之间有指向的图叫做有向图.加权图：对应的边存在权值叫做加权图。顶点集：图中具有相同特性的数据元素的集合称为顶点集边（弧）：边是一对顶点间的路径，通常带箭头的边称为弧弧头：每条箭头线的头顶点表示构成弧的有序对中的后一个顶点，称为弧头或终点弧尾：每条箭头线的尾顶点表示构成弧的有序对中的前一个顶点，称为弧尾或始点。度：在无向图中的顶点的度是指连那个顶点的边的数量。在有向图中，每个顶点有两种类的的度：出度和入度。出度：我指向别人的边的个数入度：箭头指向我边的个数权：有些图的边（或弧）附带有一些数据信息，这些数据信息称为边 （或弧）的权（weigh）.完全图：所有的顶点的度都一样，且如果有向那么对应的出度和入度也一致有很少条边或弧的图称为稀疏图，反之称为稠密图。

专业术语

使用邻接矩阵（array）实现

dfs深度优先搜索算法（先一条走到底 直到走不通了 回溯 标识是否已经走过）

bfs广度优先搜索算法（层级遍历 一层一层的往下走 ）

使用链表实现（顶点使用数组 顶点包含边 边链表）

他是用来解决有向图的最短赋权路径，或者是无向图的单源赋权最短路径。

狄克斯特拉算法（最短路径）

图

冒泡排序(逐层往上冒 每次交换位置)

选择排序（选一个值 跟其他的所有比较）

插入排序(后面跟前面的比)

快速排序（冒泡排序的升级）

1.分类 利用间距(递减的)分类（数组长度/2）（最后到达的值为1）循环

.分组 （多个为一组）循环

组内排序 （组内元素进行排序）循环

希尔排序（插入排序的升级

将每一个元素拆分为独立的个体 进行合并 在合并的过程中进行交换为止

归并排序的速度在大量数据计算中是最快的。

归并排序

如果顺序表为无序表，那么只能用顺序查找。

采用链式存储结构的线性表，只能采用顺序查找。

顺序查找（遍历所有的内容查找）

.二分法查找（基于排序好的数组）

分块查找要求把顺序表分成若干块，每一块中的键值存储顺序是任意的，但要求“分块有序”，前一块中的最大键值小于后一块中最小键值。即块间结点有序，块内结点任意。

分块查找（分成对应的模块 分好的模块必须是有序的）

左子节点要小于双亲节点 右子节点要大于双亲节点。没有键值相等的节点。

二叉排序树

利用key生成的hashcode码（key进行hash函数的出来的地址）来进行区分的。如果hash函数生成的俩个地址是相同的话，就会导致hash冲突。

写多个hash函数，当前hash函数出现冲突，继续调用下一个hash函数。

再哈希法

解决hash冲突

找到生成的地址p，去检索这个地址，当这个地址p出现冲突，在原本的p上去探测一个新的地址p1。直到没有冲突为止。

开放定址法

在对应的有冲突的地址之上建立一个新的链表，将相同的有冲突的地址使用链表来装起来。

链表法（链地址法）

将hash表分为基础表和溢出表，将有冲突的放到溢出表。

公共溢出区

哈希表（散列表）

搜索查找

排序算法

数据结构与算法