1.数据结构与算法常见概念：

数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
数据元素：是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构的逻辑结构：数据对象中数据元素之间的相互关系，分为线性结构、树形结构、图形结构以及集合结构。
数据结构的物理结构：数据的逻辑结构在计算机中的存储形式，分为顺序存储和链式存储（不连续存储）。

算法：解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
算法五个基本特性：输入、输出、有穷性、确定性和可行性。
算法时间复杂度O(n)：常数阶、线性阶、平方阶、对数阶、立方阶、nlogn阶、指数阶。
耗时排序：O(1)<O(logn)<O(n)<O(nlgn)<O( x 2 x^{2} x2)<O( x 3 x^{3} x3)<O( 2 n 2^{n} 2n)<O(n!)<O( n n n^{n} nn)

2.数据结构：

2.1线性结构：

基本概念

线性结构：数据元素之间是一对一的关系。
在这里插入图片描述
线性表：零个或多个数据元素的有限序列。
区分数组长度与线性表的长度：
数组长度是指存放线性表的存储空间的长度，存储分配后这个值是不变的。
线性表的长度是线性表中数据元素的个数，随着线性表的插入与删除，这个值是在变换的。
在这里插入图片描述 线性表的顺序存储：用一段连续的存储单元依次存储线性表的数据元素。（通常使用一维数组实现顺序存储结构）
线性表的链式存储：除了存储本身的信息之外，还需存储一个指示后继的信息。
顺序存储的插入步骤：
a.线性表长度大于等于数组长度，抛出异常
b.插入位置不合适，抛出异常（判断插入位置与0和最大值的大小）
c.从最后一个元素开始向前变量，将它们都向后移动一位
d.将要插入的元素填入指定位置
e.表长加一
顺序存储的删除步骤：
a.线性表是否为空
b.删除位置不合适，抛出异常（判断插入位置与0和最大值的大小）
c.取出删除元素
d.从删除元素的位置遍历到最后一个元素位置，将它们前移一位
e.表长减一
链式存储的插入与删除在链表中介绍
顺序存储和链式存储使用场景：如果频繁使用查找，很少进行插入和删除，易采用顺序存储。如果需要频繁插入和删除，易采用链式存储。

数组

数组及基本操作

字符串

字符串及基本操作

队列

队列及基本操作

栈

栈及基本操作

链表

链表及基本操作

2.2树形结构

基本概念

树形结构：数据元素之间存在一对多的层次关系
在这里插入图片描述
度：结点拥有的子树数
叶结点/终端结点：度为0的结点
树的度：树内各结点的度的最大值

结点间关系图：

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

二叉树：是N（N>=0）个结点的有限集合，该集合或为空集（空二叉树），或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
在这里插入图片描述
满二叉树：所有分支结点都存在左子树和右子树，并且所有非叶子节点都在同一层上

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

每个结点最多只有两颗子树
左右子树是有顺序的
即使某结点只有一颗子树，也要区分是右子树还是左子树

二叉树的性质：

在二叉树的第i层上至多有 2 i − 1 2^{i-1} 2i−1个结点（i>=1）
深度为k的二叉树至多有 2 k 2^{k} 2k-1个结点(k>=1)
对任何一棵二叉树T，如果其终端结点数为 n 0 n_{0} n0，此二叉树至多有 2 k 2^{k} 2k-1个结点
具有n个结点的完全二叉树的深度为[ l o g 2 log_{2} log2n]+1([x]表示不大于x的最大整数）
n个结点的完全二叉树按层序编号（参考上图），对任意一个结点i有：
a. 如果i=1,则i是二叉树的根，如果i>1,其双亲是[i/2]
b. 如果2i>n，则结点i无左孩子
c. 如果2i+1>n，则结点i无右孩子（否则其右孩子为2i+1）