【趣学算法】Day2-数据结构入门篇

14天阅读挑战赛
努力是为了不平庸~
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！

---

上一篇我们提到为什么要学算法？

【趣学算法】Day1-为什么要学算法？_跟着飞哥学编程的博客-CSDN博客

数据结构 + 算法 = 程序

从上面的公式中，可以看到，数据结构和算法是相辅相成的，二者密不可分。

接下来，我就带大家了解一下什么是数据结构？

目录

1、概念

1.1、数据

1.2、数据元素

1.3、数据项

1.4、数据对象

1.5、数据结构

2、数据结构的存在意义

3、数据结构的三要素

3.1、逻辑结构

3.1.1、集合

3.1.2、线性结构

3.1.3、树形结构

3.1.4、图形结构

3.2、存储结构

3.2.1、顺序存储

3.2.2、链式存储

 3.2.3、散列存储

3.2.4、索引存储

3.3、运算

4、总结

---

1、概念

数据结构是计算机存储、组织数据的方式。

学习数据结构之前，我们先了解几个基本术语概念：

1.1、数据

数据是指所有能输入到计算机中的描述客观事物的符号，包括文本、声音、图像、符号等等。

在计算机系统中，数据以二进制信息单元0、1的形式表示。 

1.2、数据元素

数据元素是数据的基本单位，也称节点或记录。在计算机程序中通常作为一个整体进行考虑和处理。

1.3、数据项

数据项表示有独立含义的数据最小单位，也称域。若干个数据项构成一个数据元素，数据项是数据的不可分割的最小单位。

如下图 1-1 中所表示的数据元素与数据项：

 图1-1

1.4、数据对象

数据对象是指相同特性的数据元素的集合，是数据的一个子集。

1.5、数据结构

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

数据结构：是带“结构”的数据元素的集合，结构指数据元素之间存在的关系。

2、数据结构的存在意义

1）数据结构研究的问题是将带有关系的数据存储在计算机中，并进行相关操作。

2）各种数据抽象只是数据的不同组织形式，一切都为了方便程序访问数据和提高程序性能而使用。

3）各种结构之所以这样定义，就是为了通过以不同方法组织数据来改善、来提高程序性能和数据访问速度。

4）在程序中，定义没有实际价值，真正有价值的是那种组织思想和操作方法；但如果没有定义，就不会有这样的对象（实际可以是变量、常量等实实在在的数据操作客体），所以最少也得要知道这些结构（起码是名字）。

另外数据结构它跟什么编程语言是没有关系的，数据结构是一种抽象的组织数据元素的方式。

3、数据结构的三要素

数据结构包含：逻辑结构、存储结构（物理结构）和运算三个要素。

3.1、逻辑结构

逻辑结构是数据元素之间的关系，数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从实际问题中抽象出来的数学模型。

数据结构的逻辑结构有以下 4 种：

3.1.1、集合

数据元素之间除“同属于一个集合”外，无其他关系。

集合中的元素是离散、无序的，就像是鸡圈中的小鸡一样，可以随意走动，他们之间没有关系，仅仅是在一个鸡圈里面。 

集合虽然是一种数据结构，但是数据结构的着重点是研究数据之间的关系，所以，集合应该属于离散数学的集合论内容。

3.1.2、线性结构

线性结构就像是一辆火车，把各个车厢串联起来，有头有尾。

有唯一的开始和唯一的结束，除第一个元素外，每个元素都有唯一的前置节点；除了最后一个元素外，每个元素都有唯一的直接的后置节点元素。

线性结构，一个对一个，如线性表、栈、队列、数组、广义表。

3.1.3、树形结构

树形结构就像是一颗倒立的树，树根可以发出多个分支，每个分支也可以继续发出分支，树枝和树枝之间是不相交的。

 

一个对多个的关系。

3.1.4、图形结构

图形结构就像是我们常见的渔网一样，任何一个节点都可能和其他节点有关系，就像一张错综复杂的网。

 图形结构就是多对多的关系。

3.2、存储结构

存储结构指的是，数据元素及其关系在计算机中的存储方式。

存储结构可以分为 4 种：顺序存储、链式存储，散列存储和索引存储。

3.2.1、顺序存储

顺序存储是指逻辑上相邻的元素在计算机内部的存储位置也是相邻的。

比如一个家里的兄弟姐妹之间，不仅是连续的兄弟姐妹关系，而且，他们的住址也是连续挨着的。

所以，顺序存储采用一段连续的存储空间，将逻辑上相邻的元素存储在连续的空间内，中间不允许有断开的空间。

顺序存储可以快速定位第几个元素的地址，但是插入和删除时需要移动大量的元素。

顺序存储 

3.2.2、链式存储

链式存储是指逻辑上相邻的元素在计算机内的存储位置不一定是相邻的。

比如，一个家里兄弟姐妹之间，住址不在一起挨着，但是他们各自知道对方的具体地址信息。

所以把这种存储方式称为链式存储。

链式存储就像是一个铁链子，一环扣一环才能连在一起。每个节点除了数据域，还有一个指针域，记录下一个元素的存储地址。

链式存储

 3.2.3、散列存储

散列存储，又称为哈希（Hash）存储，由节点的关键码值决定节点的存储地址。用散列函数确定元素的存储位置与关键码之间的对应关系。

散列存储

例如：假设散列表的地址范围为 0~9，散列函数为 H(Key) = key%10。输入关键码序列：（14,10,12,17,11,15,19），构造散列表:。

14%10 = 4：存储在下标为 4 的位置，

10%10 = 0：存储在下标为 0 的位置，

以此类推，（12,17,11,15,19）存储下标为（2,7,1,5,9）。

 散列表

散列存储可以通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

3.2.4、索引存储

索引存储：不仅建立存储节点信息，还建立附加索引表来标识节点的地址。索引表由若干索引项组成。

如果每个节点在索引表中都有一个索引项，则该索引表称为稠密索引；

若一组节点在索引表中只对应于一个索引项，则该索引表称为稀疏索引； 

索引项的一般形式是关键字、地址。

 索引存储

在搜索引擎中，需要按某些关键字的值来查找记录，为此可以按关键字建立索引，这种索引称为倒排索引。

为什么叫倒排索引？因为正常情况下，都是由记录来确定某个属性的值，而这里是根据属性值来查找记录。

这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。带有倒排索引的文件称为倒排索引文件，又称为倒排文件。倒排文件可以实现快速检索，索引存储是目前搜索引擎最常用的存储方法。

3.3、运算

运算包含：初始化、查找、取值、插入、删除、遍历等等。

4、总结