关于数据结构
什么是数据结构？
- 逻辑结构：描述数据之间的关系
- 物理结构：描述数据存储的方式
为什么需要数据结构？
以有效的方式处理数据，主要体现在存储和检索方面。
数据结构的分类
逻辑结构
1，集合结构
例如一个集合中包含橘子，苹果和香蕉。
集合具有三大特性：
- 唯一性
- 互斥性
- 无序性
2，线性结构
元素存在一对一的相互关系
3，树形结构
元素存在一对多的相互关系
4，图形结构
元素存在多对多的相互关系
物理结构
顺序存储
逻辑上相邻的节点物理上也相邻【查询效率高，插入删除效率低】
链式存储
逻辑上相邻的节点物理上不一定相邻【插入删除效率高，查询效率低】
索引存储
除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
用结点的索引号来确定结点存储地址，其优点是检索速度快，缺点是增加了附加的索引表,会占用较多的存储空间。
散列存储
又称hash存储。由节点的关键码值决定节点的存储地址。
散列是数组存储方式的一种发展，相比数组，散列的数据访问速度要高于数组，因为可以依据存储数据的部分内容找到数据在数组中的存储位置，进而能够快速实现数据的访问，理想的散列访问速度是非常迅速的。散列存储的时间复杂度为O（1），数组为O（n）。
线性结构 VS 非线性结构
线性结构：元素之间存在一对一的关系
- 数组
- 链表
- 堆栈
- 队列
非线性结构：元素之间存在一对多，多对多的关系
- 树
- 图
关于算法
什么是算法？
来自搜狗百科：
简单来说，算法就是解决问题的方式，而时间复杂度和空间复杂度可以衡量算法的性能。
【举个栗子】
假设你要从上海到北京，那么怎么去就是一个待解决的问题。
提出两种方案，乘火车，坐飞机。这两种方式就是来解决去北京的问题的，可以理解为算法。
但是火车和飞机是有区别的，乘火车价格更低，但耗时长，乘飞机耗时短，但价格贵。
价格和时间可以类比算法的时间复杂度（算法完成需要多久），空间复杂度（完成算法需要多大内存空间）。
为什么需要算法？
算法和设计模式类似，属于经验之谈，是经前人们应用后总结的一种解决问题的方式。
而在经过大范围的应用和普及之后，就会变成一种标准。
而经验的作用就是用来学习，应用，改进的。
开源的时代，有种思想叫别造轮子。就好像爱迪生发明了电灯，后人并不会去把发明的过程花几十年重复一遍，而是去学习原理，在此基础上进行改进，扩展应用，钨丝灯到现在色彩斑斓的灯就是很好的例子。
对于算法来说，同样如此。如果不是专门研究算法的工程师，对于算法领域更多的是使用，而不是创造。
算法的衡量标准
时间复杂度：算法运行到完成需要的时间
时间复杂度是一个渐进值，
x=1;y=2; //执行两次 for(int i =0 ;i<n ;i++) { x++; //执行n次 } for(int i =0 ;i<n ;i++) { for(int j =0;j<m;j++) { y++; // 执行n的方次 } }
程序总共执行的次数为：n+n+2，取渐进值
时间复杂度T(n)=O(n)
- 空间复杂度：算法执行过程中需要的内存空间大小