共计 4226 个字符，预计需要花费 11 分钟才能阅读完成。
仁厚光明的地母呵，愿在你怀里永安她的魂灵！—《阿长与山海经》鲁迅
从新视角来对待旧问题，则须要创造性思维。— 爱因斯坦
前言
咱们先不看数据结构，权且能够将数据当做一个限定词，单纯来看构造，仅以构造来看，构造是什么？构造一次呈现在各个行业，比方修建构造，人体构造，物质构造。那构造是什么:
构造是指在一个零碎或者资料之中，相互关联的元素的排列、组织 –《维基百科》
直观上能被人所感触到的是就是屋宇的构造，在走入一间房子，各个房间之间的排列。再进入到卧室，家具之间的排列。如果设计的好，那么这个房间通常状况下会让刚进来的人充斥好感。那么如果排列摆放的不好，那么就可能让人对这个房间产生不好的感觉。比方将卧室灯的开关不放在床边，对立放在门口，这样在睡觉的时候，你就不得再下床，将灯关掉。个别的设计是门口放一一个开关，这样设计的目标是为了在进门的时候就间接能将灯关上。因为修建面向的始终是人，所以咱们总会讲宜居的修建。
那么咱们尝试在构造下面加上数据，那么就能够得出类比数据结构的定义，在一些数据之中，数据之间的排列、组织。在计算机科学中，这个数据是涵盖比拟广的名词，咱们以日常十分罕用的 ctrl+z(撤销操作)来阐明，咱们的一个一个操作被操作系统记录成了上面这种模式:
以工夫为轴线，最先的操作在最上面，这样咱们 ctrl+ z 的时候就能复原到离以后工夫最近的操作。通常这种组织数据结构的模式，咱们个别称之为栈(也有称之为堆栈)，先进后出，在这个场景下，操作也是数据，数据在计算机科学的含意是多种多样的，可能在其余畛域数据更偏差于数字多一点。这种组织数据的模式也是合乎直觉的。
咱们在来看一下数据结构在维基百科中的定义:
在计算机科学中，数据结构（英语：data structure）是计算机中存储、组织数据的形式。
这次的类比剖析，看来咱们类比的方向是正确的，这个存储咱们能够了解为容器，我想起之前和我共事之前的一次下厨，他从家带来了一桶泡菜，这个桶我过后记得是那种油桶，就是口比拟细，他过后让我取点酸豆角，这一度让我很苦楚，因为用筷子夹进去真的很不容易，咱们能够将泡菜里的菜了解为数据结构中的数据，存储就由那个油桶来实现，组织数据的形式没有什么法则。悄悄的吐槽一下，那这个数据结构设计的就蛮不合理的，除了在运输的时候，显的略微不便一点，然而要吃的时候是真的不不便。
数据结构简论
程序所要解决的数据
学过程序设计的都晓得，用人脑驱动计算机的形式是编程。瑞士驰名的计算机科学家，赫赫有名的 Pascal 之父尼古拉斯·沃斯 (Niklaus Wirth) 就变成的概念，提出了一个驰名的公式，并由此取得了计算机科学界的最高荣誉 ” 图灵奖 ”，公式仅仅有一行文字:
Algorithm(算法) + Data Structures(数据结构) = Program(程序)
软件程序倒退到明天，咱们能够说这个公式并不是那么大的恰如其当，因为软件前面开始跟上工程了这个名词，思考的因素更多了。编程首先要解决两个问题: 算法设计和数据结构设计(许多高级语言都内置了相当成熟的数据结构，但这并不代表学习数据结构曾经失去了意义，一方面这是考点，另一方面它也的确可能帮忙咱们解决不少问题)。算法是解决问题的策略，而数据结构是形容问题信息的数据模型，程序则是计算机依照解决问题的策略解决问题信息的一组指令集。
咱们程序设计的目标就是让计算机帮忙人们主动地实现所要解决的简单工作，计算机科学与技术的基本问题就是 – 什么可能被自动化以及无效的自动化? 具体的由理论的问题到最终的计算机求解，要通过怎么的过程？
咱们经常要剖析的就是，问题模型中信息蕴含的数据是什么、数据间的分割是什么、以什么样的模式存储在计算机中，剖析后造成数据结构。在上世纪三四十年代，最后创造电子计算机的目标是进行迷信和工程计算，其解决的对象是纯数值性的信息，通常人们把这类问题称之为数值计算(具体的说就是无效利用计算机求解数学问题近似解的办法与过程)。
近十几年来，随着计算机的疾速倒退，这不仅体现在计算机本身性能一直进步，更重要的是可输出到计算机中的数据，其领域被极大扩充，比方，符号、声音、图像等多种信息都能够通过编码存储到计算机中，与此对应，计算机的解决对象也从简略的纯数值型信息倒退到具备肯定构造的信息，计算机的应用领域也在不断扩大。
所谓的 ” 非数值计算 ” 问题，是为了辨别后面提到的 ” 数值问题 ” 而言的，非数值问题波及的数据及数据间的互相关系(留神这里的互相关系，粗略的说咱们能够认为，数据和数据之间的关系形成了数据结构)，个别无奈用数学公式、方程等形容。如排序问题，检索问题等。须要另外设计数据的形容办法和相应的算法来解决。
举个例子，求 π 的值咱们就能够认为是数值运算的典型问题。对于非数值运算，让咱们来看一下现实生活的一个理论场景，比如说打电话，通常当初的智能手机的通讯录都是按姓氏首字母的拼音来进行排序的，这样也能疾速查找。这是事实上就是一个非数值问题，咱们在查找数据，每个数据由姓名 + 电话形成，咱们在查找的时候，查找策略就有如下几种:
- 程序查找(一个一个查找，如果这个人的姓名的首字母排名靠前还算比拟侥幸，然而如果可怜排在最初，比如说姓张，如果就要查找到最初能力找到你要分割的人)
- 依据拼音首字母查找，而后在程序查找。然而这样其实这会有些问题，如果你姓张的敌人比拟多，那可能你还是要查找一段时间(个别的智能手机都反对按名字来搜寻，事实上这是另一种搜寻策略)
再比方咱们日常司空见惯的红绿灯，咱们天然会提出这么一个问题，在十字路口，要设置几种色彩的交通灯能力放弃失常的程序，这个问题咱们很快就能得出答案，两种。然而如果输出到计算机中呢？让计算机来求解，就不是一个容易的问题了。首先要解决的问题是如何把题目中的信息存储到计算机中，而后在此基础上能力设计算法求解。
咱们来尝试来解决一下这个问题，或者说将问题所波及的信息建模而后输出到计算机，路口如下图:
问题波及的对象，四个路口 ABCD，及相应的通路。用 AC 示意 A 到 C 有一条路线。某方向通行时，另外某些方向不能通行。AC-BD 示意 AC、BD 不能同时通行。假如左拐通行规定和直行统一、右拐随时都容许。依据以上剖析咱们能够画出上面的路线图:
这种构造咱们在数据结构中个别称之为图数据结构，每个路线咱们称之为一个结点。
咱们再来看下计算机的文件目录，咱们晓得一个文件夹能够蕴含一个文件夹，能够这样层层包下去，在操作系统中咱们也是将每个文件目录形象成一个结点，则这个文件目录的结构图就如下所示:
这在数据结构中通常被称作树，最下面的文件咱们称之为根结点。
数据结构的引入
从后面的例子咱们能够看出，非数值问题中的树、图等构造模型，无奈用方程式等加以形容，因而解决此类问题的要害不再是剖析数学和计算方法，而是先找出问题中要解决的数据及数据之间的分割、组织模式、存储形式、示意办法等，再设计出适宜计算机解题的模型。
个别认为，数据结构是由数据元素根据其自身外在的逻辑组织分割组织起来的。对数据元素间的逻辑关系的形容称为数据的逻辑构造 (下面咱们提到的树与图就能够认为是逻辑构造); 数据必须存储在计算机内，数据的存储构造是数据结构的实现模式。是计算机内的示意；除此之外，探讨一个数据结构必须同时探讨在该类型上执行的运算才有意义。一个逻辑存储构造(有的时候咱们也称之为 abstract data type)) 能够有多种存储构造，在不同的存储构造之上，数据处理的效率是不同的。
数据结构的基本概念
通过下面的探讨置信各位同学对数据结构曾经有了一些根本的意识，上面咱们来介绍一些数据结构的罕用术语:
数据(Data)
在计算机科学中，数据是指所有能输出到计算机中并被计算机程序解决的符号的总称。
数据元素(Data Element)
数据的根本单位，也称 ” 元素 ” 和 ” 结点 ”，在计算机程序中通常作为一个整体进行思考和解决。一个元素能够蕴含多个数据项。
数据项(Data Item)
数据项是具备独立含意的最小标识单位，是数据最根本的、不可再分的数据单位
数据结构
由某一数据对象及该对象中所有数据成员之间关系的组成。
数据机构蕴含三个因素: 数据的逻辑构造、数据的存储构造、数据的运算。
数据的逻辑构造
数据的逻辑构造，反映了咱们对数据含意的解释，它能够用一组数据以及这些数据之间的关系示意。数据的逻辑关系又分为以下几种类型:
汇合
只是被放在一个容器中，像我下面提到的泡酸菜一样，菜与菜之间没有什么分割。
线性构造
结点间的关系是一对一的，像是排队一样，也像是的撤销操作。
树形构造。
结点间是一对多的关系，像下面的文件目录一样。
图形构造
结点间是多对多的关系，像下面的图构造一样。
数据的存储构造
数据的存储构造又称为物理构造，是数据及其逻辑构造在计算机中示意办法，指数据如何在计算机中寄存，本质上是内存单元调配，在具体实现时用计算机语言中的数据类型(Data Type)。
这里的数据类型咱们也能够了解为容器，对于整数咱们采取一个容器，对于小数咱们也独自采纳一个容器。常见的数据存储形式有四类：
顺序存储构造
用一组间断的存储单元来顺次存储数据元素，数据之间的逻辑关系由元素的存储相邻地位来体现。
数组是一种常见的数据存储构造链式存储构造
在每一个数据元素中减少指针项(没指针的通过援用)，以记录数据元素间的逻辑关系。
索引存储构造
在存储结点信息的同时，建设一个附加的索引表，相似于字典中的索引项。
散列存储构造
散列存储形式，以结点的关键字为自变量，通过函数关系，间接计算出该结点的存储地址。
数据的运算
数据的运算有两个方面的定义，运算的定义与运算的实现，运算的定义，取决于数据的逻辑构造，晓得了问题中的数据及数据间的分割，咱们就能够设计相应的数据处理办法, 个别常见的运算操作有如下这些:
- 初始化: 对存储构造设置初始值，或者申请存储空间
- 判空: 判断存储空间是否未寄存有效值的状态
- 求长度: 统计元素个数
- 查找: 判断是否蕴含指定元素
- 遍历: 按某种秩序拜访所有的元素，每个元素只拜访一次
- 取值: 获取指定元素值
- 插入: 减少指定元素
- 删除: 删除指定元素
写在最初
本篇就拉开了数据结构与算法学习的尾声，我的想法是在解说算法题目之前，先将根底打牢。有些文字兴许只有有一些经历能力懂得一样，就像初中学习的鲁迅学生的文章《阿长与山海经》一样。有的时候，总须要经验，能力有所领会。
参考资料
- 《数据结构与算法剖析新视角》周幸妮 任智源 马彦卓 樊凯 编著
- 《低等代数扼要教程》蓝以中
