干货 | 数据结构的基本概念介绍

文案 向柯玮
排版 邓发珩

疫情尚未结束，大家继续坚守在家呀！响应钟爷爷的号召，祝大家健健康康！

前言

各位看客老爷们，宅在家里快乐！

对于数据结构，这个熟悉而又陌生的名词，我相信很多人都不能很准确地说出它的定义，它包含哪些内容，它有什么用，它应该怎么学……

对于算法，这个熟悉而又陌生的名词，我相信很多人也都不能很准确地说出它的定义，它包含哪些内容，它有什么用，它应该怎么学……

不用着急，在接下来的一段时间里，小玮会陪着大家一起探究数据结构与算法的魅力！

有一句在程序猿中流传很久的话：'If you give someone a program, you will frustrate them for a day; if you teach them how to program, you will frustrate them for a lifetime'.     

翻译过来的意思：如果你交给某人一个程序，你会折磨他一天；如果你教会某人如何写程序，你将会折磨他一辈子。

而我可能就是那一位会折磨大家一辈子的人，hhhh。

今天是数据结构与算法系列的第一篇，数据结构的相关概念介绍。

本篇文章中，小玮会陪着大家了解数据结构的起源，一些基本概念和术语，一些结构……那么我们开始吧。

起源

在很久以前，人们只是单纯地把计算机理解为数值计算的工具，就感觉它只能用来计算。

所以才很早的时候，人们要使用计算机解决问题，一般都是从某个具体问题中抽象出一个适当的数据模型，然后再设计一个算法来解这个模型，然后再编写程序，得到一个软件。

但是实际上，我们很多时候都并不是为了解决一个数值的问题，而是需要一种些更科学有效的手段（表，树和图等数据结构）的帮助，才可以更好地处理问题。

所以数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。

大约是在上世纪七十年代，各种各样的大型程序出来了，软件也开始相对独立，结构程序设计成为程序设计方法学的主要内容。

其实一个程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。

总的来说，程序设计=数据结构+算法。

基本概念和术语

》数据

是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符，声音，图像，视频等非数值类型。

举个简单的例子来说，在搜索引擎中，一般会有网页、音频、图片等分类。就包括了上述的各种数据。

在这个位置，我们所说的数据，其实就是符号，而这些符号必须要满足以下两个条件：

1. 可以输入到计算机中。

2. 能被计算机程序处理。

如果是数值类型数据，我们可以直接进行计算，如果是非数据类型，就可以通过编码的方式变成字符数据来处理。

》数据元素

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

举个例子来说，在一个人群里面，它的数据元素是什么？没错，当然是人啊。

》数据项

一个数据可以由多个数据项组成，而数据项就是一个数据的最小组成单位，打个比方来说一个人的最小组成单位是什么？是手，耳，口……吧？

》数据对象

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

什么叫做性质相同？就是数据元素具有相同数量和类型的数据项。打个比方说，人拥有姓名，生日，性别等相同的数据项。

》数据结构

说了这么多，我们的主角终于登场了。结构，其实就是关系的意思，打个比方说一辆车的结构，就是内部各种配件的组装关系。

在现实生活中，不同的数据元素之间是存在某些特定的关系的。我们把这些关系成为结构。

那么数据结构呢？就是相互之间存在一种或者多种关系的数据元素的集合。

为了编写出一个优质的程序，我们必须处理好不同数据之间的关系。而这就是我们研究数据结构的意义所在。

结构

》逻辑结构

是指数据对象中数据元素之间抽象的相互关系。这也是以后我们最需要考虑的东西。它主要分为四类。集合结构，线性结构，树形结构，图形结构。

1. 集合结构

在这个结构中的元素，除了在同一个集合里面，没有任何别的关系。如图所示。

2. 线性结构

在这个结构中的元素之间都是一对一的关系，像一条线一样。如图所示。

3. 树形结构

在这个结构中的元素之间存在一种一对多的关系层次关系，有一点需要注意，他们的父母只有一个，但是后代可以有多个。

但是计算机的树和现实中的树是有区别的：

(现实中的树 VS 计算机科学中的树)

4. 图形结构

在这个结构中的元素是多对多的关系。分为有向和无向图。在这里给出无向图的图示。

不同的逻辑结构对应不同的具体问题，为了解决具体的问题，我们在对问题充分理解的基础上会选择合适的逻辑结构去表示其中元素的关系。

》物理结构

大家不用多想，觉得这是什么高大上的东西。物理结构简单的来说，其实就是数据的逻辑结构在计算机中的储存方式。它主要分为顺序储存和链式储存。

1. 顺序储存

就是把数据元素存放在地址连续的存储单元中，其数据间的逻辑关系和物理关系一致，如图所示。

其实这种储存结构很容易理解，就和排队占位一样的，大家都按一定的顺序排好，谁也不要插别人的队。举一个例子，我们在学习c++的时候，数组就是这样的储存方式。

2. 链式储存

首先，我们思考一个问题，在排队的时候，如果有人突然离开了，或者是说有人情况很紧急，需要插队，就会涉及到整个队伍的变化。

如果是顺序储存的话，是不是非常不方便？你需要让后面的全部发生变化，这是一种非常不科学的储存。那么科学的是什么呢？就是我们的链式储存。

链式储存结构就是把各种数据元素存放到任意的储存单元中，这组储存单元可以是连续的也可以是不连续的。他们之间的联系是通过指针来实现的。

这种结构我们用生活中例子来说。去银行办理业务，我们需要取号，我们关注的不是别的号码有没有被叫到，我们只会关心我们前面的一个号码有没有被叫到，叫到了你就知道下一个是你了。

说到这个链式结构，我想到了小时候看的电影里面的间谍，他们都是一对一的联系，如果其中某一个人不见了，那么整条链都断了。大家可以根据这个例子去理解一下这种结构。

抽象数据类型

说到这个，我想通过两个方面来介绍，数据类型和抽象数据类型。

》数据类型

它是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

这样说其实并不是很容易理解，我们通俗地来讲其实就是int，float……等等这样的类型，它规定了这个数据的范围，同时也规定了这个数据能够进行的操作。

那么数据类型有什么用作用呢？举一个例子来讲，不同经济条件的人会买不同价位的服饰，有的人会买几万的衣服，而有的会买几十的衣服，而商家会按照不同的需求提供不同的衣服。

有的人可能觉得这个和咱们int，float这些不一样。那么我们再举一个例子。你的电脑的内存不是无限大的吧？如果你的数据全是int范围内的，但是你却分配了float的内存给它们，后果是什么？白白浪费了很多空间吧？

》抽象数据类型

当我们对数据类型进行抽象以后，就有了抽象数据类型。它具体是指一个数学模型及定义在该模型上的一组操作。

举一个例子来说，同样是整型的数据，在手机上，在电脑上，在计算器中，可能实现的方式就不一样。但是不可否认的是，它们都是整型数据。在我们这些设计程序的人眼中，它们其实都是一样的。这就是因为我们把它抽象了出来。

所以抽象数据类型就在于在这种数据类型的数学特征。当然，它不仅仅是指这种数学模型，它同时也定义了相关的操作。

比如，对于拳皇这款游戏，我们用整型浮点型等表示玩家的身高体重，并对里面的人物定义了相关的攻击防御方法等一系列招式。

一个抽象数据类型定义了一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。

其实在我看来，抽象数据类型其实就是对整个程序中的问题进行分解，把它们分解成多个规模小且容易处理的问题。

为了便于我们在之后的推文中对抽象数据类型进行规范化的描述，下面给出标准格式。

ADT 抽象数据结构类型名Data     数据元素之间逻辑关系的定义Operation    操作1        操作条件        结果描述    操作2        操作条件        结果描述        ……endADT

到这个位置，其实我们已经大致的了解了数据结构一些基本的方面。这个时候大家肯定仍然对于这一门学科充满困惑，没关系。后面还有很多内容，小玮会慢慢陪大家进行学习！

大家在刚开始学习的时候肯定会觉得难学，这是很正常的，但是万事开头难，对吧？加油！

下期推文中，我们会一起了解算法的相关内容。让我们一起期待吧！