✨ 基本概念和术语

🐱‍🏍 数据结构的基本概念和术语

1. 数据(Data)是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称（集合）。
   是信息的载体；是对客观事物的符号化表示；可以被计算机识别、存储和加工。数据不仅仅包含整型、实型等数值类型，还包含图形、图像、声音、视频及动画等非数值类型。
   对于整型、实型等数值类型,可以进行数值计算；对于字符数据类型，就需要进行非数值的处理。而声音、图像、视频等其实是可以通过编码的手段变成字符数据来处理的。

2. 数据元素(DataElement)是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
   在有些情况下，数据元素也称为元素、记录、节点、顶点等。如前一节示例中的一名学生记录，树中棋盘的一个格局（状态），以及图中的一个顶点等。

3. 数据项(Data Item)是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

【数据项是“数据的最小单位。但真正讨论问题时，数据元素才是数据结构中建立数据模型的着眼点。就像我们讨论一部电影时，是讨论这部电影角色这样的数据元素”，而不是针对这个角色的姓名或者年龄这样的“数据项”去研究分析。】

1. 数据对象(DataObject)是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0, ±1,±2,…}, 字母字符数据对象是集合C={‘A’,‘B’, …‘Z’,‘a’,‘b’, …， ‘z’}, 学生基本信息表也可以是一个数据对象。

由此可以看出，不论数据元素集合是无限集（如整数集），或是有限集（如字母字符集），还是由多个数据项组成的复合数据元素（如学生表）的集合，只要集合内元素的性质均相同，都可称之为一个数据对象。

说了数据结构中的数据那数据结构中的结构又是什么呢？

🎶 数据的结构

结构，简单的理解就是关系，比如分子结构，就是说组成分子的原子之间的排列方式。

严格点说，结构是指各个组成部分相互搭配和排列的方式。

在现实世界中，不同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。

那数据结构是什么？

• 数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

🎂数据结构包含的内容

数据结构包含以下三个方面的内容

1. 数据元素之间的逻辑关系， 也称为逻辑结构。
2. 数据元素及其关系在内存中的表示（又称为映像），称为数据的物理结构或数据的存储结构。
3. 数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现。

👔数据结构的两个层次

1. 逻辑结构

数据的逻辑结构是从逻辑关系上描述数据，

它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

数据的逻辑结构有两个要素：一是数据元素；二是关系。

2. 物理结构（存储结构）

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

它是数据结构在计算机中的表示。

• 逻辑结构与存储结构的关系

1. 存储结构是逻辑关系的映像与元素本身的映像。
2. 逻辑结构是数据结构的抽象， 存储结构是数据结构的实现。

两者综合起来建立了数据元素之间的结构关系。

🎟逻辑结构的种类

逻辑结构的种类有两种划分方法

划分方法一：

一、线性结构

有且只有一个开始和终端结点，并且所有结点最多只有一个直接前趋和一个直接后继。

例如：线性表、栈、队列、串

二、非线性结构

一个结点可能有多个直接前趋和直接后继 例如树、图

划分方法二：

一、集合结构

结构中的数据元素之间除了同属于一个集合的关系外，无任何其他关系。

二、线性结构

结构中的数据元素之间存在着一对一的线性关系。

三、树形结构

结构中的数据元素之间存在着一对多的层次关系

四、图形结构/网状结构

结构中的数据元素之间存在着多对多的任意关系。

🎏存储结构的种类

1. 顺序存储结构

顺序存储结构是把数据元素存放在连续的存储单元里，数据元素之间的逻辑关系是通过数据元素的位置。(在前面的数据元素就存在前面；在后面的数据元素就存在后面)

C语言用数组来实现顺序存储结构

2. 链式存储结构

用一组任意的存储单元存储数据元素(可能连续也可能不连续)，数据元素之间的逻辑关系用指针来表示(用指针存放后继元素的存储地址)

C语言中用指针来实现链式存储结构

3. 索引存储结构

在存储节点信息的同时，还建立附加索引

索引表中的每一项称为一个索引项，索引项的一般形式是：(关键字，地址）

关键字是能唯一标识一个结点的那些数据项。

若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index)。若一组结点在索引表中只对应一个索引项，则该索引表称之为稀疏索引（Sparse Index)。

4. 散列存储结构

根据结点的关键字直接计算出该结点的存储地址。

👕数据类型

数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。

（数据类型 = 值的集合 + 值集合上的一组操作 ）

说到数据类型其实我们并不陌生，在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量、常量或表达式、C语言中函数的参数、返回值，明确说明它们所属的数据类型。

C语言中：

提供int,char,float,double等基本数据类型；

数组、结构、共用体、枚举等构造数据类型；

还有指针、空（void)类型，用户也可用typedef自己定义数据类型。

而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示。

• 数据类型明显或隐含地规定了程序执行期间变量或表达式的取值范围、存储方式以及允许进行的运算。

例如，C语言中定义变量i为int类型，就表示是[min,max]范围的整数，[-32768～32767,16位]

在这个整数集上可以进行+、-、*、/、%的操作，而不能进行其他数据类型比如字符串的一些操作，而实型变量也有自己的取值范围和相应运算，比如取模运算是不能用于实型变量的。

• 在C语言中，数据类型可以分为两类：

原子类型：是不可以再分解的基本类型，包括整型、实型、字符型等

结构类型：由若干个类型组合而成，是可以再分解的。

🧵抽象数据类型

你在这幅图中看到了什么？

相信大多数人会说看到的圆，其实这就是抽象。我们看到了他的本质，而去掉了一些非本质的东西，比如大小颜色，线条的粗细，空心还是实心。

那什么是圆呢？

圆是到某个点距离相等的点的集合这个定点就是圆心，距离就是半径，我们就可以描述这个圆的一些相关信息了

运算:构造圆、求面积、求周长

抽象数据类型(Abstract Data Type, ADT)一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。

• 由用户定义，从问题抽象出数据模型（逻辑结构）
• 还包括定义在数据模型上的一组抽象运算（相关操作）
• 不考虑计算机内的具体存储结构与运算的具体实现算法

抽象数据类型的形式化定义

抽象对象可用（D, S, P）三元组【离散数学上的概念】表示。

其中D是数据对象

S是D上的关系集 (数据对象之间的关系构成的集合，数据对象与数据对象之间可能有多种关系构成了这个集合)

P是对D的基本操作集

🎨抽象数据的举例说明

比如求圆的面积的操作area ( 操作的名字 ) ( r ) ( 操作的参数 )

对图形进行一个缩放 n 倍 scale ( G ( 被操作的图形 ), n ) 对图形进行缩放，它当然也会返回一个图形 G’ = scale ( G, n ) 返回值要赋值给 G 写成 scale（ &G, n ）

基本操作定义格式说明：

“参数表”：赋值参数，只为操作提供输入值。

引用参数以 “&” 打头，除可提供输入值外，还将返回操作结果。

“初始条件” 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略。

“操作结果” 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。

抽象数据类型的概念与面向对象方法的思想是一致的。

抽象数据类型独立于具体实现，将数据和操作封装在一起，使得用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据，从而实现了信息隐藏。

🛒小结