常见数据结构和算法
时间复杂度
数据结构
1.线性结构
1.1 顺序表
利用数据的连续存储单位
顺序表
不定长
1.2 链表存储
每个结点应包含：数据域（自身的数据结构） 指针域（指向下个结点的地址）
1.3 栈：FILO 先进后出
栈的应用：
辗转相除取余数法：
举例2:用于匹配括号是否完整
左括号入栈，后括号判断左括号匹配则出栈，若最后结果栈为空，则说明匹配完整。
1.4 队列：FIFO
1.4.1 链队列：FIFO
链式结构实现
1.4.2 循环队列 ：FIFO
数组实现 用指针分别指向队头 队尾
2 树 二叉树
用链表的形式：
2.1 二叉树定义和性质
最多有2个子节点，次序不能任意颠倒：左子树 右子树
完全二叉树：
2.2 二叉树的存储
完全二叉树和满二叉树：用数组
一般二叉树，最好用 链式存储
2.3 二叉树的遍历
递归方式
-
(1) 方式一 递归的方式
-
(2) 方式二 中序
-
(3) 方式二 后序
非递归 使用堆栈
中序–算法思路：
举例思路：
层序遍历 二维结构的线性化
二维变成一位的思想：
使用存储结构：堆栈 队列
举例思路：
- A 入栈 ------- 栈内：A
- BC入栈 A 出 ------- 栈内：BC ------ 输出结果：A
- DF出 B出 ------- 栈内：CDF ------ 输出结果：AB
- GI入 C出 ------- 栈内：DFGI ------ 输出结果：ABC
- 。。。
代码实现：
查找方法
1. 顺序查找
2. 二分法
3.散列查找 = hash查找
例如要找巴顿，根据映射函数：f（巴顿） 找到巴顿的存储地址，然后根据地址找到相关信息。
栈和队列求解迷宫问题
问题：
- 建立数据结构：
- 定义栈
- 思想：
代码：
找某点的可走出口：
判断结束：
但上面不一定是最短路径
可参考别的，找出最短路径
图论
存储方式：矩阵 单链表
深度优先
深度优先
广度优先：
层次得搜索
求最小生成树的方法之一 – prim
举例
最短路径求解–Dijkstra地基斯特拉算法 利用贪心算法（使得结果接近最近最优，即实现整体最优）
算法
排序算法
- 插入排序
- 快速排序
- 冒泡排序
- 选择排序
数模
聚类
主成分分析
在这个图里面，可以看出，X轴的相关性比较大，Y轴不大，所以可以重新组合，减少Y
轴的依赖
关键在于找特征值
例如：
主成分结果输出如下：
即，十三个成分，可以从前3个主成分 可以表示这个表达式。
从上面可以看出，第一影响因素就是市场经济综合因素，第二是劳动者动力因素 三十气候因素。
层次分析
https://www.bilibili.com/video/av20238704/?p=3