本文为L_Ares个人写作，包括图片皆为个人亲自操作，以任何形式转载请表明原文出处。

在这几年写代码的过程中，可能最心痛的就是当初上大学没有好好的学习数据结构这门课，学的统统还给了老师，而在真正的进入到开发之后，发现无论是面试，还是平常的开发，还有对一些底层框架的理解都离不开数据结构。可以说，数据结构就是程序开发的骨架，没有这个骨架，程序开发就变成了一滩烂肉。

程序设计 = 数据结构 + 算法。

那么本节就开始系统的回顾一下数据结构的内容，本文很多的内容是自学的，如有错误敬请指出，万分感谢。

那么第一节，就了解一下，数据结构的基本概念和术语。

一、数据的基础名词

1. 数据

什么是数据？

数据是一个符号，它可以描述客观的事物，它是计算机可以认知的对象，是计算机可以识别的、可以操作的、可以处理的符号集合。

想要进入这个符号集合，那么必须要满足两个基本条件：

• 能被输入进计算机

• 能被计算机处理

2. 数据元素

数据元素是组成数据的、有一定意义的基本单位。在计算机中通常整体的处理，也被称作记录。

举个例子：在人类中，人是基本单位，那么人类就可以是数据，人就可以是数据元素。

3. 数据项

数据项是组成数据元素的单位，是数据的最小单位。

虽然这里说数据项是数据的最小单位，但是实际的开发中，我们通常还是以数据元素作为建立数据模型的根基。

为什么还是以数据元素作为根基呢？原因很简单，举个例子：你在吃水果的时候，你会说吃苹果，吃梨，你不会说吃葡萄不吐葡萄皮，你的关注点在于某个水果，而不是水果的皮，或者水果的核。

4. 数据对象

数据对象是性质相同的数据元素的集合，是数据的子集。

举个例子：在我们创建一个数组的时候，会被要求，数组里面存储相同类型的数据，那么这个数组就是数据对象，相同类型就是性质。

一张图总结，数据、数据对象、数据元素、数据项的关系:

图片.png

二、数据结构的基础名词

• 概念 : 结构，是组成结构的各个成分之间的搭配和排列的方式。

在我们的现实中，不同数据元素之间不是相互独立的，而是存在着一些特定的关系，这些关系，就是结构。

那么数据结构是什么？

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

根据我们视点的不同，数据结构可以分成两类:

• 逻辑结构
• 物理结构

1. 逻辑结构

概念 ： 逻辑结构是数据对象中，数据元素与数据元素的逻辑关系。

逻辑结构分为以下4种：

1.1 集合结构

什么是集合结构？如下图：

图片.png

集合结构中的数据元素，除了同处一个集合，没有其他的关系。它们是"平等关系"，它们共同的属性就是都属于同一个集合。

1.2 线性结构

图片.png

线性结构中的元素是一对一的关系。

常见的线性结构 ：

• 数组、链表 —— 线性结构
• 队列、栈 —— 特殊的线性结构。
  区别: 队列是先进先出(FIFO)、栈是先进后出(FILO)
• 字符串 —— 特殊的线性结构。它的存储内容只能是字符串。

1.3 树形结构

图片.png

树形结构中的元素，存在着一对多的关系。

常见的树形结构 : 二叉树、B+、B-、红黑树、哈希曼树。

1.4 图形结构

图片.png

图形结构中的数据元素，存在着多对多的关系。

可以看出，逻辑结构之中的数据元素，或多或少的都存在着一些逻辑关联。

2. 物理结构

概念 : 物理结构，有的人也称之为存储结构，指的是数据的逻辑结构在计算机的内存中的存储形式。

数据的存储结构应当正确的反映数据元素之间的逻辑关系，所以物理结构的重点和难点就是如何存储数据元素之间的逻辑关系才是正确的。

物理结构的数据存储结构有两种：顺序存储结构和链式存储结构。

2.1 顺序存储结构

如下图：

图片.png

顺序存储结构是一段连续的存储空间，数据元素的存储地址之间需要连续。逻辑关系上相邻的元素，它们的物理存储位置也要相邻。

比如数组，我们在初始化一个数组的时候，计算机会在内存上找到一块空地，把你想要存放入数组的元素的大小计算好，然后乘以元素的个数，计算出这个数组需要多少的内存空间，然后开辟这么大的连续的内存空间。

所以，数组中的元素也是按照顺序的依次摆放。

2.2 链式存储结构

图片.png

逻辑上是连续的数据元素，在存储的时候，物理存储位置不一定是连续的，链式存储结构中的数据元素，会存储一个指针来寻找相关联的数据元素的位置。链式存储结构的存储空间是动态的。

链式存储结构的优缺点：

• 优点 :
  (1). 不需要开辟一段固定的存储空间，因为它的存储空间是动态的。
  (2). 数据发生改变后，比如修改，删除都不需要移动数据的内存位置，只需要改变数据元素的指针指向对象。

• 缺点 :
  无法随机的存取元素，如果在链式存储结构中遍历元素，则需要遍历所有的元素。如果指向某个数据元素的数据元素全都没了，那么没有人知道之前被指向的这个数据元素到底是谁。

从逻辑结构和物理结构的特点可以看出来，逻辑结构针对的是具体的逻辑关系问题，而物理结构则是如何在计算机中存储数据元素和它们的逻辑关系的。

三、数据类型

数据类型是指，一组性质相同的值的集合，以及定义在此集合上的一些操作的总称。

数据类型是按照值的不同来划分的。在高级的语言中，变量、常量、表达式都有它们自己的取值范围。数据类型就是用来说明这些变量、常量、表达式的取值范围，以及它们可以进行的操作。

1. 抽象

抽象是指取出事物具有的普遍性的本质。

抽象就是把注意力集中到了问题的特征上，忽略掉与问题本质无关的因素，仅仅保留与实现目标的必要元素，忽略掉其他的细节。

2. 抽象数据类型

抽象数据类型是指一个数学模型及定义在该模型上的一组操作。这个数学模型只考虑数据的一组逻辑特性，不需要考虑它在计算机内部怎么表示或者实现。

抽象的意义在于数据类型的数学抽象特性。

抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。

抽象数据类型的标准格式:

ADT 抽象数据类型名

Data

    数据元素之间，逻辑关系的定义

Operation

   操作1:

            初始条件
            操作结果的描述

   操作2:

          ......

   操作n:

            ......

endADT