正所谓"巧妇难为无米之炊"，在强大的计算机，也是需要有"米"下锅才可以干活的，否则就是一具没有灵魂的躯壳。对于计算机而言，这个"米"就是数据。在计算机刚诞生时，那时还没有鼠标、键盘、磁带等工具，人们通过纸带(回想下初中的磁悬浮滑块实验)来进行数据的输入与输出。没有数据的输入，计算机的计算能力就无法体现，这也验证了数据的重要性。
1.数据结构的基本概念
1.1 数据
? 数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。例如，证书、实数、字符串都是数据，除了这些还包含声音、图像、视频等非数值类型的数据。
? 数据输入的计算机中的核心目的，是对其进行处理、计算。对于数值类型的数据，我们可以进行数值计算，如加减乘除；另一方面对于图像、视频等数据，也是可以对其进行处理计算的，如计算机视觉，是以图片作为数据输入的。
1.2 数据元素
? 数据元素是数据的基本单位，是数据结构这门课讨论的最小单位，在计算机程序中通常作为一个整体进行考虑和处理。
1.3 数据项
? 数据项是数据不可分割的最小单位。
? 有时，一个数据元素可由若干个数据项组成。例如，一本书的数目信息为一个数据元素，而书目信息中的每一项（如书名、作者、ISBN等）为一个数据项。
? 一般在数据结构中，我们讨论问题时，数据元素才是建立模型时的着眼点。就像我们讨论电影时，我们会去讨论某一个角色（数据元素），而不会过多的去纠结每个角色的姓名、年龄、性别、身高…等具体属性（数据项）。
1.4 数据对象
? 数据对象是性质相同的数据元素的集合，是数据的一个子集。比如，大写字母就是一个数据对象，这个集合是{‘A’, ‘B’, ‘C’, ‘D’ … ‘Z’}。
? 我们以一个例子来讲解下，下面这张图是一个学生信息表，整个学生的信息表可以称之为学生数据的集合（数据对象）；每一行即为一个学生的具体信息，为数据元素；每一行的学号、姓名、性别等信息，就是每个数据元素中的数据项。
? 我们可以用数据库的概念来理解。多个字段(column、数据项)构成一个数据元素(Row)；多条数据元素（row，记录）组成数据的集合（Table）；所有的表共同组成一个数据库（Database，数据）。
1.5 数据结构
? 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构包含三方面内容：逻辑结构、存储结构和对数据的运算。
? 在计算机中，数据元素并不是孤立、杂乱无序的，而是具有内在联系的数据集合。数据元素之间存在一种或多种特定的关系，也就是数据的组织形式。
1.5.1 数据的逻辑结构
? 数据的逻辑结构是对数据之间关系的描述，它与数据的存储结构无关，同一种逻辑结构可以有多种存储结构。数据的逻辑结构主要有以下四种。
- 集合结构
集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。各个数据元素是"平等"的，它们的共同属性是"同属于一个集合"。
- 线性结构
线性结构中的数据元素之间存在一对一的关系。线性结构是一个数据元素的有序集合，其有一下四个基本特征：①集合中必存在唯一的一个"第一个元素"；②集合中必存在唯一的一个"最后一个元素"；③除却最后一个元素外，其他数据元素均有唯一的一个"后继"；④除却第一个元素外，其他数据元素均有唯一的一个"前驱"；
- 树形结构
树形结构中的数据元素之间存在一对多的层次关系。
- 图形结构
图形结构中的数据元素之间存在多对多的关系。
? 归纳起来，数据的逻辑结构主要分为两单类：线性结构、非线性结构（集合、树形、图形结构）。
1.5.2 数据的物理结构
? 说完数据的逻辑结构，我们来一起看下物理结构，也可以称之为存储结构。
? 物理结构，是数据的逻辑结构在计算机中的表示(又称映像)。它包含数据元素的表示和关系的表示。
? 数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。对应两种不同的存储结构，分别是顺序存储结构、链式存储结构。顺序映像是借助数据元素在在存储器中的相对位置来表示数据元素之间的逻辑关系；非顺序映像是借助指针表示数据元素之间的逻辑关系。更细分开来，数据结构中有以下四种常用的存储方法：
- 顺序存储方法：把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。
- 链式存储方法：不要求逻辑上相邻的节点在物理位置上也相邻，结点之间的逻辑关系是由福建的指针字段表示的。
- 索引存储方法：索引存储方法是在存储结点信息时，除了建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引项的一般形式是<关键字，地址>。关键字标识唯一一个结点，地址作为指向结点的指针。
- 散列存储方法：散列存储的基本思想是根据结点的关键字通过散列函数直接计算出该节点的存储地址。
? 链式存储、索引存储、散列存储，本质上都是链式存储方式。对于链式存储，因为会涉及到指针，索引同学们可能都会有恐惧心里，其实指针并没有想象中这么可怕。我们通过一个例子来稍微理解下指针，谍战电影相信大家都看过，如永远那么经典的《潜伏》、《无间道》，组织上为了保护自己打入地方内部的间谍，都是通过上一级单线联系，这种联系，我们就可以称之为指针，只有你的上一级（前驱）才知道你的存在。当然这种方式也存在缺点，如果前驱节点损坏、或丢失，那么后续的所有节点就不可寻回了。正如无间道中，黄秋生扮演的阿sir遇害后（指针信息丢失），无人在知晓梁朝伟其实是个间谍，梁也无法证明自己的警察身份。
1.5.3 两种方式优缺点对比
? 顺序存储、链式存储都有各自的优缺点，没有最好的存储方式，只有更适用的。了解其优缺点，根据实际情况选择适用的结构，就非常重要了，这也是一个考点。
? 1.顺序存储
? 优点：存储密度高(=1)，除存储数据外无须额外空间；随机访问，数据读取方便，只需要知道第一个元素的地址，然后根据index就能找到相应位置的数据；
? 缺点：要求占用连续的存储空间，存储只能预先进行；不利于结点的删除和插入；
? 2.链式存储
? 优点：链表的结点可以散落在内存的任意位置（不需要地址连续），且不需要提前分配好所有的存储空间；结点的插入、删除操作方便
? 缺点：存储密度（<1）低于顺序存储，除存储数据外需要空间用于存储后继结点的地址；不支持数据的随机访问，查找指定位置的结点时，需要从头指针开始遍历；
2.算法的基本概念
? 目前，主流思想仍认为：程序=数据结构+算法。上面我们讲完了数据结构的基本概念，下面我们简单的介绍下算法的一些基本概念。
2.1 算法
? 算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照要求设计好的有限的确切的计算序列。一般而言，算法可以使用自然语言、或者伪代码进行描述，只要能讲清、并且能让别人看懂。
2.2 算法的特性
? 一个算法应具有以下5个重要的特征
- 有穷性：一个算法必须保证执行有限步之后结束。如果我们写的代码陷入了死循环，那么我们的代码就不具备有穷性，执行我们的代码会一直运行无法运行结束，计算机的资源也就会被一直占用，无法释放。
- 确定性：算法的每一步骤必须有明确的定义，不会出现二义性。算法需要保证相同的输入结果，只能有唯一的输入，类似于f(x)只能映射唯一的y值。（类似于抛硬币的概率问题不算）
- 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况。
- 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。
- 可行性：算法中的所有操作都必须通过已经实现的基本操作进行运算，并在有限次内实现，而且人们用笔和纸做有限次运算后也可完成。换言之，算法中的每一步都是可执行的，每一步都能通过有限的次数完成。
2.3 算法的设计目标
? 算法是一个问题的解题步骤。在初中时，我们就追求解法1、解法2，并去追求更简单的解法，那么我们在设计算法时，也就是同理可得啦。算法也不是唯一的，并不具备标准答案。但算法也有自己的设计目标，有优秀的算法评价标准。下面我们一起来看下吧。
- 正确性：要求算法能够正确地执行预先规定的功能和性能要求。这是最重要也是最基本的要求。
- 可读性：要求算法易于他人阅读、理解。可以通过增加注释，增加可读性。
- 健壮性：要求算法有很好的容错性，能够对不合理的数据进行检查。要求算法能处理不合理数据，及对一些异常可以做到正确的处理。这也是测试同学们重点关注的方向了。
- 高效率与低存储量：算法的效率主要指算法的执行时间。算法的存储容量是指算法执行过程中所需要的最大存储空间。高效率与低存储量这两者都与问题的规模有关。
? 关于算法的时间复杂度和空间复杂度，由于篇幅原因，就不在此处讲解了，有兴趣的同学可以关注我的后续博客。
? 又到了分隔线以下，本文到此就结束了，本文内容全部都是由博主自己进行整理并结合自身的理解进行总结，如果有什么错误，还请批评指正。
? 本专栏为数据结构知识，喜欢的话可以持续关注，如果本文对你有所帮助，还请还请点赞、评论加关注。
? 有任何疑问，可以评论区留言。
