前言
作为一个计算机专业出身的码农，当初没有好好学习这门课程，每当提起，深感羞愧。
学如逆水行舟，不进则退。浑浑噩噩的过了这么久，回头看看，好多东西要么忘了要么就是当初压根没学好，想找好点的工作也压根够不到人家的门槛。现在想再提升下自己的编码水平，就趁着这次机会，把这门让我羞愧难当的课程也再次学习一遍吧。
另外，我现在特别忍不住想问一句，当初学校让我们在刚入门还没有任何基础的情况下学习这门课究竟是出于什么样的考虑？
基本概念
数据结构 + 算法 = 程序
在 [ 这里 ] 看到一位老师写的很通俗的例子：
遇到一个实际问题，需要解决两个事情：
- 如何将数据存储在计算机中；
- 用什么方法策略解决问题。
前者是数据结构，后者是算法。只有数据结构没有算法，相当于只把数据存储到计算机中而没有有效的方法去处理，就像一幢只有框架的烂尾楼；若只有算法，没有数据结构，就像沙漠里的海市蜃楼，只不过是空中楼阁罢了。
数据
数据是所有能够输入到计算机中表示客观事物并被计算机程序处理的符号。
数据元素
数据的基本单位，例如图书馆藏书数据中，每一本书的数据都算是一个数据元素。
数据项（数据域）
数据元素中，有独立含义的最小单位。例如书名、作者。
数据对象
数据对象是性质相同的数据元素的集合，是数据的一个子集。例如整数数据对象是集合 N = {0，±1，±2，…}，字母字符数据对象是集合 C = {'A'，'B'，…，'Z'}
数据结构
数据结构是计算机存储、组织数据的方式。是相互之间存在一种或多种“关系”的数据元素的集合，结构是指数据元素之间的关系。
包含三个方面：逻辑结构，存储结构和数据的运算。
逻辑结构和存储结构
数据结构包括逻辑结构和存储（映像）结构。两者的关系就像肉体和灵魂。
逻辑结构是数据元素之间的关系，存储结构是数据元素及其关系在计算机中的存储方式。
例如小明同学和小勇同学是表兄弟，这是他们之间的逻辑关系，他们在教室里面的位置是挨着坐，还是分开坐，对角交叉坐，这是他们的存储结构。
逻辑结构的基本分类
根据逻辑结构（关系）的不同特性，可以分为 4 类基本结构：
集合
所有数据元素之间除了“同属于一个集合”的关系外别无其他关系。
线性结构
数据元素之间存在一对一关系。emm…手串。
树形结构
数据元素之间存在一对多关系。比如家族族谱。
图状结构或网状结构
数据元素之间存在多对多关系。比如地图。
存储结构的基本分类
根据数据元素及其关系在计算机中存储的不同方式，这里可以分为 2 类：
顺序存储
顺序存储在计算机的存储器中是连续的，从 a1 到 an 中间没有任何空格和间断。
这种存储方式很容易访问，因为它们的位置都是固定连续的，取数据时通过地址即可完成。
优点是读取快，节省存储空间。
缺点是空间有限制，删除数据时需要操作大量的数据。
适用场景：大量查询操作。
顺序存储
链式存储
链式存储不需要占据一整块存储空间，通过元素存储地址的指针来确定数据元素之间的关系。
优点是插入和修改方便，使用灵活。
缺点是存储空间利用率低。
试用场景：大量写操作
链式存储
数据运算
数据运算包括运算的定义和实现。
示例：
以人为例，假设有一个运算是计算人的颜值。
颜值 = 五官的漂亮程度之和 （运算的定义 针对逻辑结构）
通过计算机读取每个人的五官的信息，然后相加得到颜值 （运算的实现 针对存储结构）
数据类型
数据类型规定了变量或表达式的取值范围，以及在这些值上能够进行的操作。是为了节省内存空间和提高内存使用效率而存在的。
数据类型是一个值的集合和这个集合上的一组操作的统称。
抽象数据类型
抽象数据类型和数据类型其实是一个概念，但它是一个数学模型和操作。
数据结构可以用一个二元组来表示，即 Data_Structure = {D，S}，D 是数据元素集，S 是 D 上的关系。
而抽象数据模型可以用一个三元组表示，ADT = {D，S，P}，P 是基本操作集。
也就是说，数据结构 + 操作 = 抽象数据类型。
ADT 抽象数据类型名｛
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义> 创建、更新、销毁等
｝
抽象数据类型的分类
根据值的不同特性，可以分为三种：
原子类型
整型、实型、字符型等不可拆分的类型。
固定聚合类型
值由确定数目的成分按某种结构组成的变量。
例如 student 抽象数据类型可以由姓名、学号、成绩 3 个成分按照先后顺序组成。
可变聚合类型
与固定聚合类型相比，构成可变聚合类型值的成分的数目不确定。
例如定义一个“字符序列”，其中序列长度是可变的，我们并不知道会有多少个字符来组成这个序列。
多形数据类型
多形数据类型是指数据元素的类型不确定。
比如一个栈，可以是char，也可以double。
小结
本小节主要知识点为数据结构、数据项、数据元素的基本概念；逻辑结构、存储结构的概念及分类；数据类型和抽象数据类型的概念及分类。
数据结构
部分内容来自 趣学算法
网友评论