什么是数据结构

数据结构的起源
1968年美国的高纳德教授开创了一门新的课程《基本算法》，开创了数据结构和算法的先河，确定了数据结构和算法的基本体系。
数据结构不是一门研究数据计算的学科，而是研究数据与数据之间关系的，是一门研究非数值计算的学科，专注于数据的关系及操作。
程序=数据结构+算法，它在计算机界的地位相当于E=MC^2在物理界的地位。
数据结构的基本概念
数据：所有能输入到计算机中的描述客观事物的符号。
数据项：有独立含义的数据的最小单位。描述事物的其中一项指标。
数据元素：数据的基本单位，也称节点或记录，用于描述一个完整的事物。
数据结构：数据元素+数据关系组成的集合
算法：
狭义：数据结构所具有的功能。
广义：解决问题的方法。
数据结构的三个方面
数据的逻辑结构
数据的存储结构
数据结构的运算
四种基本的逻辑结构
集合结构：数据元素之间除了同属于一个集体外，没有关系
线性结构：数据元素之间存在一对一关系(数组)。
数组、链表、功能受限的表(栈、队列)
树型结构：数据元素之间存在一对多关系。
普通树、二叉树、完全二叉树、满二叉树、有序二叉树
图型结构：元素之间存在多对多关系
邻接表、表的遍历(深度优先、广度优先)、最短路径

数据结构
数据结构分为数据和结构
1.什么是数据：但凡能够被计算机存储、识别、和计算的东西都叫数据（二进制）。硬盘中：mp3、jpg、doc、avi等文件就是数据。“巧妇难为无米之炊”，不管你再大或者再牛逼的计算机，没有“米”来下锅，它也是无用的。而这个“米”就是数据。也就是说这里的数据其实是一种符号，而这些符号必须能被输入到计算机中，或者说能被计算机程序处理。
2.结构 ：就是数据和数据之间一种或多种的特定的关系。简单的来说就是关系，严格点来说是指各个组成部分相互搭配和排列的方式。在现实世界中，不同的数据元素之间不是独立的，而是存在特点的关系，我们将这些关系称为结构。
3.数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
它主要解决的问题：把零散的数据“整齐划一”方便后续的操作 。类似于现实生活中的垃圾分类，便于回收与处理。
数据结构的逻辑结构 ：是指数据对象中数据元素之间的相互关系，它是抽象的，它主要分为一下四种：
3.1集合结构：结合结构中的数据元素除了同属于一个集合外，他们之间没有其他关系。也就是说各个元素都是平等的，他们之间没有其他关系，只不过他们的共同属性是属于同一个集合。有点像数学中的集合。
3.2 线性结构：线性结构中的数据元素之间是一对一的关系。像是一个链表，不管是1或9作为尾结点或者头结点。
3.3 树形结构：树形结构中的数据元素之间存在一种一对多的层次关系。想到了族谱，也是这种树形结构。
3.4 图形结构：图形结构的数据元素是多对多关系。比如数据库中表与表的对应关系，多对多时，查询起来sql语句就有点复杂了。
如下图：

4.数据结构的 物理结构：很多书中也叫它存储结构，不管叫什么，只要理解了也就一回事。他是具体的，存在计算机里的。
物理结构：它是指数据的逻辑结构在计算机中的存储形式。数据是数据元素的集合
① 顺序存储结构：开辟一组连续的空间存储数据–数组 地址本身是连续的，保证了数据之间的关系。这种结构很简单，说白了，就是排队占位，每个人都有特定的位置，不允许插队操作。
② 链式存储数据：开辟一组随机的空间存储数据–节点 ~不仅要存储数据，还要存储下一个节点的位置一保证数据之间的关系。把数据元素存放在任意的存储单元里，这组存储单元是连续的，也可以是不连续的。这跟银行的排队系统就很像了，每个人去了先领号，领完号后，只需等待银行叫号，你过来就行，而不管你在哪，你在干什么。

算法
1.算法：官方定义是解决特定问题求解步骤的描述，在计算机中表现为指令的有序序列，并且每条指令表示一个或多个操作。简单来说就是解决问题的步骤
如何评价一个算法的好坏：设计算法要提高程序运行的效率，这里效率大都指算法的运行时间
2.事后统计方法：在程序运行完后，对运行时间进行比较。缺陷：必须先编好程序，再运行，如果处理的数据大，花费时间长；依赖计算机软硬件；
3.事前分析估算方法：在程序编制前，统计方法对算法进行估计

它是衡量算法好与坏，执行时间快与慢的标准。

等差数列求和
int n = 100; //执行一次，
int sum = (n+1)*n/2; 执行一次
循环求解
int sum = 0;//执行一次，
int n = 100; //执行一次，
for(int i = 1;i<n;i++) { //执行n+1次，
sun+=i; //执行n次，
}
① 常数阶O(1) 第一个代码执行了两次，但是复杂度却为O(1) ;
② 线性阶O(n)/忽略常数，忽略N的系数/2n+3，随着N的增大，循环里面执行的次数越多，那么此算法的执行次数为2N+3次，但是是时间复杂度为O（n），因为随着N的不断增大，这个3就显得微不足道了，如果N达到足够大，这个系数2也显得微不足道，因为数量级是一样的，因此最后的时间复杂度为O（n）。
③ 对数阶O(logn)：虽有循坏，虽也随着n的增大而增大，但是这种增大属于 加速度减小的加速运动
④ 平方阶O(n^2) 忽略常数，只保留幂高项，且忽略幂高项的系数