数据结构基础.png
逻辑结构: 数据与数据之间的逻辑关系
集合结构: 公共汽车上的所有乘客，存放在仓库中的产品。集合中的主要操作有查找和排序，如哈希表
线性结构: 堆，栈，一维数组，字符串，线性表，双队列，串
树形结构: 一对多
一棵树（tree）是由n（n>0）个元素组成的有限集合，其中：
（1）每个元素称为结点（node）；
（2）有一个特定的结点，称为根结点或根（root）；
（3）除根结点外，其余结点被分成m（m>=0）个互不相交的有限集合，而每个子集又都是一棵树（称为原树的子树）图形结构：多对多，比树形结构更复杂，树形结构中，结点间具有分支层次关系，每一层上的结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。而在图形结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的
物理结构：
顺序存储结构
- 适用于查询
- 内存地址一定是连续
- 比链式节省空间链式存储结构:
- 查询慢，适用于增删改
- 内存地址不一定是连续
相关面试题： 最短路径, 图形结构(※还不会，学完来看看)
数据结构与算法之间的关系
时间复杂度
1，用常数1取代运行中所有常数 3-> 1
2，在修改运行次数函数中，取最高阶乘 n3+2n2+5 -> O(n^3)
常用术语:
指数阶(eg: 2^n)除非n非常小，否则这种消耗过大，实际开发中不会考虑
时间复杂度.png
O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(n^n)
空间复杂度
计算辅助空间,输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外得辅助变量所占额外空间
eg:
该算法将一位数组a的n个数逆序存放到原数组中，则该空间复杂度为O(1)
for (i = 0; i < n / 2; i++) {
t = a[I];
a[i] = a[n-i-1];
a[n-i-1] = t;
}
下列不同算法将一位数组a的n个数逆序存放到原数组中，则该空间复杂度为O(n)
for(i=0;i<n;i++) b[i] = a[n-i-1];
for(i=0;i<n;i++) a[i] = b[i];
感谢CC老师
