数据结构与算法

空间复杂度

最好

最坏

平均

均摊

时间复杂度

复杂度分析

线性表‌线性结构：数据元素之间是一对一的关系。

顺序栈

链式栈

栈

限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一端为栈顶，另一端是栈底。

性质：后进先出

「栈」是一种后进先出的线性表。

插入：若有一元素想往int[n]的第k个位置插入数据，需要在k-n的位置往后移。最好情况时间复杂度 O(1)

最坏情况复杂度为O(n)

平均负责度为O(n)

1） 插入：从最好O(1) 最坏O(n) 平均O(n)2） 插入：数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把心的元素，插入到第k个位置，此处复杂度为O(1)。3） 删除：从最好O(1) 最坏O(n) 平均O(n)4） 多次删除集中在一起，提高删除效率

 数组（Array）是一种线性表数据结构。‌它用一组连续的内存空间，来存储一组‌具有相同类型的数据。

 连续的内存空间和相同类型的数据(随机访问的前提)。

优点：两限制使得具有随机访问的特性缺点：删除，插入数据效率低。

对内存空间要求高，需要一块连续的内存空间

数组

每个节点只包含一个指针，即后继指针。

单链表有两个特殊的节点，即首节点和尾节点。‌为什么特殊？用首节点地址表示整条链表，尾节点‌的后继指针指向空地址null。

性能特点：插入和删除节点的时间复杂度为O（1），‌查找的时间复杂度为O(n)。

单链表

节点除了存储数据外，还有两个指针分别指向前一个节点地址‌（前驱指针prev）和下一个节点地址（后继指针next）。

首节点的前驱指针prev和尾节点的后继指针均指向空地址。

性能特点：和单链表相比，存储相同的数据，需要消耗更多的存储空间。

双向链表

除了尾节点的后继指针指向首节点的地址外均与单链表一致。

适用于存储有循环特点的数据，比如约瑟夫问题。

循环链表

链表

链表中的每一个内存块被称为节点Node。‌节点除了存储数据外，还需记录链上下‌一个节点的地址，即后继指针next。

插入、删除数据效率高O(1)级别（只需更改指针指向即可），‌随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。

和数组相比，内存空间消耗更大，因为每个存储数据的节点‌都需要额外的空间存储后继指针。

链表的内存结构是不连续的内存空间，‌是将一组零散的内存块串联起来，从‌而进行数据存储的数据结构。

队列

数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

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

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

数据结构的逻辑结构：数据对象中数据元素之间的相互关系，分为线性结构、树形结构、图形结构以及集合结构。

数据结构的物理结构：数据的逻辑结构在计算机中的存储形式，分为顺序存储和链式存储（不连续存储）。

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

算法五个基本特性：输入、输出、有穷性、确定性和可行性。

常见概念

数据元素之间存在一对多的层次关系

度：结点拥有的子树数

树的度：树内各结点的度的最大值

叶结点/终端结点：度为0的结点

树的深度/高度：树中结点的最大层次

树形结构

是N（N>=0）个结点的有限集合，该集合或为空集（空二叉树），‌或者由一个根结点和两颗互不相交的、分别称为根结点的左子树‌和右子树的二叉树组成。

二叉树

所有分支结点都存在左子树和右子树，并且所有非叶子节点都在同一层上

满二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号i（1<= i <= n）的结点与同样深度的满二叉树中的编号i 的结点在二叉树的位置完全相同，则这棵二叉树称为完全二叉树

完全二叉树

树

每个结点最多只有两颗子树

左右子树是有顺序的

即使某结点只有一颗子树，也要区分是右子树还是左子树

二叉树的特点

无向图

有向图

图的邻接矩阵的存储方式是用两个数组来实现的，一个一维数组存储顶点信息，‌一个二维数组存储线（无向图）或弧（有向图）的信息。

邻接矩阵

邻接表存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。

邻接表

图的存储

图‌图(Graph)是由顶点和连接顶点的边构成的离散结构。

邻接(adjacency)：邻接是两个顶点之间的一种关系。

关联(incidence)：关联是边和顶点之间的关系。

两个重要关系：

数据结构与算法