数据结构基础

数据结构基础.png

逻辑结构: 数据与数据之间的逻辑关系

• 集合结构: 公共汽车上的所有乘客，存放在仓库中的产品。集合中的主要操作有查找和排序，如哈希表

• 线性结构: 堆，栈，一维数组，字符串，线性表，双队列，串

• 树形结构: 一对多
  一棵树（tree）是由n（n>0）个元素组成的有限集合，其中：
  （1）每个元素称为结点（node）；
  （2）有一个特定的结点，称为根结点或根（root）；
  （3）除根结点外，其余结点被分成m（m>=0）个互不相交的有限集合，而每个子集又都是一棵树（称为原树的子树）

• 图形结构：多对多，比树形结构更复杂，树形结构中，结点间具有分支层次关系，每一层上的结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。而在图形结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的

物理结构：

• 顺序存储结构
  - 适用于查询
  - 内存地址一定是连续
  - 比链式节省空间

• 链式存储结构:
  - 查询慢，适用于增删改
  - 内存地址不一定是连续

相关面试题： 最短路径, 图形结构(※还不会，学完来看看)

数据结构与算法之间的关系

时间复杂度

1，用常数1取代运行中所有常数 3-> 1

2，在修改运行次数函数中，取最高阶乘 n³⁺²ⁿ2+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老师