数据结构

什么是数据结构

是相互之间存在一种或多种特定关系的数据元素的集合。

说白了就是数据的集合、但是集合里面的数据之间存在特地的关系(这翻译得好像没说一样)

数据结构的逻辑结构

是指数据元素之间的相互关系

• 集合结构：集合中的数据元素除了同属一个集合外、它们之间没有其他关系。
  
  网络异常，图片无法展示

  |
  image-20200923103251902
• 线性结构：线性结构中的数据元素之间是一对一的关系
  
  网络异常，图片无法展示

  |
  image-20200923103304092
• 树形结构：树形结构中的数据元素之间存在一种一对多的层次关系
  
  网络异常，图片无法展示

  |
  image-20200923103708563
• 图形结构：图形结构的数据元素是多对多的关系
  
  网络异常，图片无法展示

  |
  image-20200923104315239

数据结构的物理结构

指数据的逻辑结构在计算机存储形式

• 顺序存储结构：是把数据元素存放在地址连续的存储单元里、其数据间的逻辑关系和物理关系是一致的
• 链式存储结构：是把数据元素存放在任意的存储单元、这组存储单元可以是连续的、也可以是不连续的

数据类型

数据类型指的是一组性质相同的值的集合以及定义在此集合上的一些操作的总称

数据类型可以分为两类

• 原子类型：是不可以再分解的基本类型、包括整型、浮点型、字符
• 结构类型：由若干个类型组合而成、是可以再分解的、比如整型数组是由若干个整型数据组成的

算法

什么是算法

算法是解决特定问题的求解步骤的描述。在计算机中表现为指令的有限序列、并且每条指令表示一个或多个操作。

算法的特性

算法的五个特性：输入、输出、有穷性、确定性、可行性

• 算法具有零个或多个输入、算法至少有一个或多个输出、算法是一定需要输出的、不需要输出、要你这个算法干嘛
• 有穷性：指算法执行有限的步骤之后、自动结束而不会出现无限循环、并且每一个步骤在可接受的时间内完成。
• 确定性：算法的每一步都具有明确的含义、不会出现二义性。相同的输入只能有唯一的输出结果
• 可行性：算法的每一步都必须是可行的、也就是说、每一步都能够通过执行有限次数来完成

算法设计的要求

• 正确性
• 可读性
• 健壮性
• 时间效率高、存储量低

算法的时间复杂度

在进行算法分析时、语句总的执行次数 T(n) 是关于问题规模 n 的函数、进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。

算法的时间复杂度、也就是算法的时间量度、记作 T(n) = O(f(n))、他表示随问题规模 n 的增大、算法执行时间的增长率和 f(n) 的增长率相同。其中 f(n) 是问题规模 n 的某个函数。

使用大写 O() 来体现算法的时间复杂度记法。

一般情况下、随着 n 的增大、T(n) 增长最慢的算法称为最优算法

O(1) 常数阶、O(n)线性阶、O(n^2)平方阶、O(logn)对数阶

常见的时间复杂度

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

• 常数阶
• 对数阶
• 线性阶
• 
  
• 平方阶
• 指数阶
• 阶乘阶

最坏情况与平均情况

最坏情况运行时间是一种保证、那就是运行时间将不会再坏了。这是一种最重要的需求、通常、除非特别制定、我们提到的运行时间都是最坏情况的运行时间

平均运行时间是所有情况中最油意义的、因为他是期望运行时间。

算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现、算法空间复杂度的计算公式记住:S(n)=O(f(n)) 。其中 n 为问题的规模，f(n)为语句关于n所存储空间的函数。

线性表

零个或多个数据元素的有限序列

首先 它是一个序列、也就是说元素之间是有顺序的、若元素存在多个、则第一个元素无前驱、最后一个元素无后继，其他每个元素都有且仅有一个前驱和一个后继。线性表强调的另一个点是有限。

线性表的顺序存储结构

线性表的顺序存储结构、指的是用一段地址连续的存储单元依次存储线性表的数据元素

优缺点

• 随机访问
• 无须为表示表中之间的逻辑关系而增加额外的存储空间
• 插入和删除元素需要移动大量的对象
• 当线性表长度变化比较大的时候、难以确定存储空间的大小
• 造成空间的碎片

线性表的链式存储结构

对单链表结构和顺序存储结构做对比

• 存储分配方式

• 顺序存储结构是使用一段连续对存储单元一次存储线性表的数据元素的
• 单链表采用链式存储结构、用一组任意的存储单元存放线性表的元素

• 查找

• 顺序存储结构O(1)
• 单链表O(n)

• 插入和删除

• 顺序存储结构需要平均移动表长一半的元素、时间为O(n)
• 单链表在找出某位置之后、插入和删除时间仅为O(1)

• 空间性能

• 顺序存储结构、预分配、大了浪费、小了发生溢出
• 单链表不需要预分配、元素个数不受限制

栈和队列

栈是限定仅在表尾进行插入和删除操作的线性表

队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表

栈

首先它是一个线性表、也就是说、栈元素具有线性关系、即前驱后继关系、只不过它是一种特殊的线性表而已。定义中说在线性表的表尾进行插入和删除的操作、这里的表尾是只栈顶、而不是栈底。

栈的应用-递归

直接或间接的调用函数自己本身。

递归出口：没过递归定义必须至少有一个条件、满足时递归不再进行，即不再引用自身而是返回值推出。

栈的应用-四则运算表达式求值

一种不需要括号的后缀表达法、我们也可以把它称为逆波兰。后缀表达式就是所有的符号都是在要运算数字的后面出现。

队列

线性表有顺序存储、栈是线性表、所以有这两种存储方式。同样队列作为一种特殊的线性表，也同样存在这两种存储方式。

循环队列

解决假溢出的办法就是后面满了、就再从头开始、也就是头尾相接的循环、我们把这种头尾相接的顺序存储结构称为循环队列。

串

串是由零个或多个字符组成的有限序列、又名叫字符串。

KMP

KMP 模式匹配算法就是为了不必要的回溯不会发生

树

树是由n(n>=0)个结点的有限集，n=0时称为空树。在任意一棵非空树中，

• 有且仅有一个特定的称为根的结点
• 当n>1时、其余节点可分为m(m>0)个互不相交的有限集 T1、T2、T3。其中每个集合本身又是一棵树、并且称为根的子树

image-20201009111011138

网络异常，图片无法展示

|

image-20201009111026048

结点分类

结点拥有的子树数称为结点的度。度为0度结点称为页结点或终端结点。度不为0的结点称为非终端结点。

除根结点外、分支结点也称为内部结点

树的度是树内部各结点的度的最大值

结点间关系

结点的子树称为该结点的孩子、相应地、该结点称为孩子的双亲。

树的其他概念

结点的层次、从根开始定义起、根为第一层、根的孩子喂第二层。

树中结点的最大层次称为树的深度

image-20201009132552841

如果将树中结点的各子树看成从左至右是有次序的、不能互换的、则称该树为有序树、否则称为无序树。

森林是m棵互不相交的树的集合。

二叉树

是 n 个结点的有限集合、该集合或者为空集、或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树的特点

• 每个结点最多有两棵子树、所以二叉树中不存在度大于2的结点
• 左子树和右子树是有顺序的、次序不能颠倒
• 即使树中只有一棵子树、也要区分它是左子树还是右子树。

特殊二叉树

• 斜树
  所有结点都只有左子树的二叉树叫做左斜树。所有结点只有右子树的二叉树叫右斜树。这两者统称为斜树
  
• 满二叉树
  在一棵二叉树中、如果所有分支结点都存在左子树和右子树、并且所有叶子都在同一层上、这样的二叉树称为满二叉树
  
• 完全二叉树对于一棵具有 n 个结点的二叉树按层序编号、如果编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全、那么这棵二叉树称为完全二叉树。

• 叶子结点只能出现在最下两层
• 最下层的叶子一定集中在左部连续位置
• 倒数第二层、如果有叶子结点、一定是在右部连续位置
• 如果结点度为1、则该结点只有左子树、不存在只有右子树的情况
• 同样结点数的二叉树、完全二叉树深度最少

二叉树性质

• 在二叉树的第i层上至多有2^(i-1)个结点
• 深度为k的二叉树至多有2^k - 1 个结点

遍历二叉树

二叉树的遍历是指从根结点出发、按照某种次序依次访问二叉树中所有结点、使得每个结点被访问一次且仅被访问一次。

• 前序遍历
  二叉树为空、则空操作返回、否则先访问根结点，然后前序遍历左子树、再前序遍历右子树。
  
• 中序遍历
  二叉树为空、则空操作返回、否则从根结点开始(注意并不是先访问根结点)、中序遍历根结点的左子树、然后访问根结点、最好中序遍历右子树
  
• 后序遍历
  二叉树为空、则空操作返回、否则从左到右先叶子后结点的方式遍历访问左右子树、最后访问根结点
  
• 层序遍历
  二叉树为空、则空操作返回、否则从树的第一层、也就是根结点开始访问、从上到下逐层遍历、在同一层中从左到右顺序对结点进行访问