数据结构概述

墨蓝 2022-05-31 08:38 233阅读 0赞

说起数据结构，估计接触过编程的朋友们都不会陌生的。有人曾说过这样一句话，如果一个程序员只懂得编程而不知道数据结构，那么他一辈子估计只能做一个最底层的coder了。可见数据结构在我们程序设计中的重要性了。

那么我们就从最基础的概念开始逐步去了解和学习数据结构。

既然数据结构把数据摆在首位，估计不只是为了叫着好听吧，巧妇难为无米之炊，没有数据自然谈不上结构了。那么到底什么是数据呢？

**数据**  
用来描述客观事物的符号，是计算机可以操作的对象，能够输入计算机并且能被计算机识别和处理的符号集合。

显而易见，能够称之为数据的事物应该具有一下两个特征：  
1.能够输入到计算机中  
2.能够被计算机识别处理

数据不仅仅是我们在程序语言中经常用到的整形，实型等数据类型，还包括各种音频视频等非数值类型。

那么数据是由什么组成的呢？那么我们就必须在了解一下数据元素这个概念了。

**数据元素**  
数据元素是组成数据并且具有一定意义的单位，在计算机中通常被当作一个整体来处理的。还有一些教程会称之为记录。

那么我们在往下追探数据元素的组成-数据项  
**数据项**  
一个数据元素可能由一个数据项组成，也可能由多个数据项组成。总之，我们需要记住一点，数据项是数据概念中不可分割的最小单位。另外，在我们实际的使用过程中，如果我们要建立数据模型，那么我们的入手点应该是数据元素，而不是数据项。

接下要说的是数据对象这个概念，它呢是我们要主要讨论的数据结构的子集。  
**数据对象**  
具有相同性质的数据元素的集合，是数据的子集。

那么什么才算的上具有相同性质的数据元素呢？简单的来说就是指数据元素具有相同类型，数量的数据项。举个例子，比如我们学生都有班级，姓名，学校，年龄等相同的数据项。

**数据结构**  
说了这么多的废话，终于要提到数据结构了。数据结构官方一点的定义就是：  
*是存在一种或者多种特定关系的数据元素的集合*

根据概念中的定义，我们将这种特定关系按照逻辑结构和物理结构进行划分。

**逻辑结构**  
*数据对象中数据元素之间的相互关系*  
具体的又可以划分为四个类型：

1.集合结构  
*数据元素只是同属于一个集合，它们之间并没有任何关系*  
这种关系就像数学中的集合概念，这里在普及一下数学概念了：

集合（简称集）是数学中一个基本概念，它是集合论的研究对象，集合论的基本理论直到19世纪才被创立。最简单的说法，即是在最原始的集合论——朴素集合论中的定义，集合就是“确定的一堆东西”。集合里的“东西”，叫作元素。
    由一个或多个确定的元素所构成的整体叫做集合。若x是集合A的元素，则记作x∈A。集合中的元素有三个特征：1.确定性（集合中的元素必须是确定的）。 2.互异性（集合中的元素互不相同）。例如：集合A={
       1，a}，则a不能等于1）。 3.无序性（集合中的元素没有先后之分），如集合{
       3,4,5}和{
       3,5,4}算作同一个集合。

2.线性结构  
*数据元素是一对一的关系*

这里我们同样可以参考一下数学中的概念或许可以更好的理解这个概念。

线性结构是一个有序数据元素的集合。[1] 
    常用的线性结构有：线性表，栈，队列，双队列，数组，串。
    
    特征
    1．集合中必存在唯一的一个"第一个元素"；
    2．集合中必存在唯一的一个"最后的元素"；
    3．除最后元素之外，其它数据元素均有唯一的"后继"；
    4．除第一元素之外，其它数据元素均有唯一的"前驱"。
    数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。
    如（a0,a1,a2,.....,an）,a0为第一个元素，an为最后一个元素，此集合即为一个线性结构的集合。

3.树形结构  
*数据元素之间存在一对多的层次关系*  
树形结构指的是数据元素之间存在着“一对多”的树形关系的数据结构，是一类重要的非线性数据结构。在树形结构中，树根结点没有前驱结点，其余每个结点有且只有一个前驱结点。叶子结点没有后续结点，其余每个结点的后续节点数可以是一个也可以是多个。另外，数学统计中的树形结构可表示层次关系。树形结构在其他许多方面也有应用。可表示从属关系、并列关系

看个例子：  
![这里写图片描述][70]

4.图形结构  
图形结构，简称“图”。一种复杂的数据结构。数据元素间的关系是任意的。其他数据结构(如树、线性表等)都有明确的条件限制，而图形结构中任意两个数据元素间均可相关联。常用来研究生产流程、施工计划、各种网络建设等问题。

![这里写图片描述][70 1]

**物理结构**  
所谓的物理结构也称为存结构，它是逻辑结构在计算机中具体的存储方式。

根据这个定义我们不难理解，物理结构的本质就是如何把数据元素存储在计算机的存储器中。而这种存储结构应该正确的反映出逻辑结构。

而数据元素的存储方式可以分为顺序存储和链式存储两种

1.顺序存储  
*把数据放在地址连续的存储单元中，其数据之间的逻辑关系和物理关系是一致的。*

比如我们常见的数组就是这种顺序存储的典范。  
![这里写图片描述][70 2]

2.链式存储  
*数据元素存放在任意的存储单元中，可以是连续的，也可以是不连续的。*

采用链式存储结构，其数据元素的存储关系不能反映出其逻辑关系，所以在这种情况下，我们需要一个额外的信息来记录其逻辑关系，那就是存放数据元素的地址指针。

![这里写图片描述][70 3]

[70]: /images/20220531/688055705dbe42748aa9f8d7753b2400.png
[70 1]: /images/20220531/833f2a8a4737427e9ba2db1d04809b56.png
[70 2]: /images/20220531/14403c15f1424c579f56e51cc862066a.png
[70 3]: /images/20220531/20541650eaf94c849d840a61a6c620a1.png