前言

唤我沈七就好啦。
算下来应该是有两周没更新了。
是因为最近一直在研究数据结构这部分内容。
因为还是个大一菜狗之前还没有接触过数据结构这方面的知识，
所以一直在不断试错里寻找这方面的入门途径。
最后在《大话数据结构》和算法基础课双料辅助下，才勉强知道了点东西。
下面来分享一下最近我的学习成果。
_{（说到这儿安利一下《大话数据结构》这本书，对初学者超级友好。电子书有需要的同学找不到资源的话可以私信我。）}

还是那句话。
蒟蒻因为实在是太弱了，肯定免不了错误百出。
欢迎批评指正，期待共同成长！

什么是数据结构？

这个问题在《大话数据结构》中笔者讲的非常清楚。

我们将 “数据结构” 分开来看。

先看数据

数据:是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。
比如我们现在常用的搜索引擎，一般会有网页、MP3、图片、视频等分类。
我们这里说的数据，其实就是符号，而且这些符号必须具备两个前提:
① 可以输入到计算机中。
② 能被计算机程序处理。
对于整型、实型等数值类型，可以进行数值计算。
对于字符数据类型，就需要进行非数值的处理。
而声音、图像、视频等其实是可以通过编码的手段变成字符数据来处理的。

再看结构

结构：简单的理解就是关系，
比如分子结构，就是说组成分子的原子之间的排列方式。严格点说，结构是指各个组成部分相互搭配和排列的方式。
在现实世界中，不同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。

这时候我们就得到了数据结构的基本定义。

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

在计算机中，数据元素并不是孤立、杂乱无序的，而是具有内在联系的数据集合。数据元素之间存在的一种或多种特定关系。
具体是什么样的关系，这正是我们下面要讨论的问题。

一些术语

_{阅读之后的文章你需要了解以下术语。}

1 .数据项：数据项是构成数据元素不可分割的最小单位。
2 .数据元素：数据的基本单位，一个数据元素可由若干数据项组成。
在这里插入图片描述
3 .数据对象：数据对象是具有相同性质数据元素的集合，是数据的子集

在这里插入图片描述
按照视点的不同，我们把数据结构分为逻辑结构和物理结构。

逻辑结构

逻辑结构:是指数据对象中数据元素之间的相互关系。
其实这也是我们今后最需要关注的问题。逻辑结构分为以下四种:

1 .集合结构：结构中的数据元素除了同属于一种类型外，别无其它关系。类似于数学里面的集合。
在这里插入图片描述

2 .线性结构：结构中的数据元素之间存在一对一的关系。
在这里插入图片描述

3 .树形结构：结构中的数据元素之间存在一对多的层次关系。
在这里插入图片描述

4 .图形结构：结构中的数据元素之间存在多对多的关系。
在这里插入图片描述

从之前的例子也可以看出，逻辑结构是针对具体问题的，是为了解决某个问题。在对问题理解的基础上，选择一个合适的数据结构表示数据元素之间的逻辑关系。"

储存结构

储存结构:是指数据的逻辑结构在计算机中的存储形式。
数据是数据元素的集合，那么根据物理结构的定义，实际上就是如何把数据元素存储到计算机的存储器中。
数据元素的存储结构形式有两种:顺序存储和链式存储。
1 . 顺序存储
顺序存储结构:是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。（如图1-5-5）
在这里插入图片描述
我们熟悉的数组其实就是顺序储存结构的代表。
当你告诉计算机，你要建立一个有9个整型数据的数组时，计算机就在内存中找了片空地，
按照一个整型所占位置的大小乘以9，开辟一段连续的空间。
于是第一个数组数据就放在第一个位置，第二个数据放在第二个，这样依次摆放。

2 .链式存储
如果就是这么简单和有规律，一切就好办了。可实际上，我们免不了要对这个数组内部的元素进行增删改查，使得整个结构时刻都处于变化中。
显然，面对这样时常要变化的结构，顺序存储是不科学的。那怎么办呢?链式存储的出现很好的解决了这一问题。
链式存储结构:是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。
数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。（这里未必一定要指针来记录存放数据元素的地址，也可以通过数组记录下一个元素所在的下标，这点我会在下一章模拟链表时详细讲解）。
在这里插入图片描述显然，链式存储就灵活多了，数据存在哪里不重要，只要有一个指针存放了相应的地址就能找到它了。