学习要求
概念和术语
数据结构的基本概念:数据、数据元素、数据结构、数据的逻辑结构、物理结构、算法等。
基本概念和术语
【1】
数据 (Data) 是信息的载体，能够被计算机识别、存储和加工处理。
数据元素(Data Element) 是数据的基本单位，有时数据元素也称为元素、节点、顶点、记录。
数据结构(Data Structure) 指的是数据之间的相互关系，即数据的组织形式。数据结构异步包括以下三个方面的内容：
数据结构一般包括以下三个方面的内容：数据的逻辑结构、数据的存储结构、数据的运算。
① 数据的逻辑结构(Logical Structure)，表示数据元素之间的逻辑关系。数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。
② 数据的存储结构(Storage Structure)，表示数据元素及其关系存储在计算机存储器。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。
③ 数据的运算，即对数据施加的操作。（最常用的检索、插入、删除、更新、排序等。）
常常将数据的逻辑结构简称为数据结构。
【2】
数据类型(Data Type)是高级程序设计语言提供的一种概念。所谓数据类型，是一个值的集合在这些值上定义的一组操作的总称。例如 C 语言中的 int 类型，以及 int 表示的最大最小值范围、int 可以进行加减乘除等操作。
数据类型有两种，一种是原子类型，一种是结构类型。原子类型其值不可拆解，例如大多数语言中都有的浮点型(float、double)、整形(int、long)等。结构类型其值可以被分解为若干个成分，如 C 语言的 数值、结构等类型。
【3】
抽象数据类型(Abstract Data Type，ADT)指抽象数据的组织和与之相关的操作。它可以看作是数据在逻辑结构及其在逻辑结构上定义的操作。抽象数据类型可以看作是描述问题的模型，它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在 ADT 里定义的某些操作来访问其中的数据，从而实现了信息隐藏。
ADT 相对于是在概念层/抽象层上描述问题，在面向对象语言中，相对于接口、抽象类。而类则是在实现层上描述问题，类是 ADT 的实现。
ADT 的主要意义是将数据和操作封装起来，使得用户程序只能在 ADT 里定义的某些操作来访问其中的数据，从而实现了信息隐藏。
谈一下 C# 中的属性。C# 、Java 中都有属性这一概念，例如 C# 定义一个属性：public int a{get;set;}。在 C# 中，真正存储数据的都是字段，属性是我们字段定义的一种存取操作设计。因此，一个类中，字段属于数据，属性可以看作是数据的操作。
【4】
在数据结构中，为了表示数据的存储，出现了很多种结构形式。无论哪种存储结构，都是由多个元素组成的，这些元素之间的逻辑关系可以有统一的术语表示。
A - B - C
一个数据结构中，最先开始的第一个结点，称为开始结点。而最后一个称为终端结点；对于数据结构中的任何一个结点 A，如果 A 在 B 的前面并且两者相邻，则称 A 为 B 的直接前趋(Immediate Predecessor)；如果一个 结点 C，C 与 B 相邻且 C 在 B 的后面，则称 C 为 B 的直接后继(Immediate Successor)。开始结点没有直接前趋；终端结点没有直接后继。
【5】
数据的逻辑结构有两大类：
（1）线性结构
如果结构是非空集(即具有元素)，具有以下特征：
① 集合中必存在唯一一个开始结点。
② 集合中必存在我要一个终端结点。
③ 除最后一个元素外，其它数据元素都有唯一一个直接后继。
④ 除第一个元素外，其它数据都有唯一一个直接前趋。
（2）非线性结构
非线性结构中每个结点都可能有多个直接前趋和直接后继。
注意，数据的逻辑结构有两大类，线性结构、非线性结构；而数据的逻辑结构有四种：
1.集合结构：数据元素之间都没有逻辑关系。
2.线性结构：数据元素之间存在着“一对一”的线性关系的数据结构。1：1.
3.树形结构：数据元素之间定义了层次关系。1：N。
4.图状结构(网格结构)：数据元素之间定义了网状关系。M：N。
【6】
数据的存储结构有四种基本方法：
顺序存储方法、链接存储方法、索引存储方法、散列存储方法。
（1）顺序存储方法：
把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来
体现。通常借助程序语言的数组描述，存储时使用一块连续的空间。
（2）链接存储方法：
该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。通常借助于
程序语言的指针类型描述。
（3）索引存储方法：
该方法通常在储存结点信息的同时，还建立附加的索引表。索引表由若干索引项组成，若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引，稠密索引中索引项的地址指示结点所在的存储位置。
若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引，稀疏索引中索引项的地址指示一组结点的起始存储位置。索引项的一般形式是：(关键字、地址)。
关键字是能唯一标识一个结点的那些数据项。
图来源：https://blog.csdn.net/weixin_43507410/article/details/112463344
（4）散列存储方法：
该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。散列又称为哈希、Hash。
测试
注：当前没有学到的内容，专题后面的文章会继续学到。读者答题不需要纠结。
1．下列选项中，属于逻辑结构的是
A．线性表
B．链表
C．顺序栈
D．循环队列
逻辑结构：集合、线性(如线性表)、图、树；
存储结构：顺序、链接(如链表)、索引、散列；
栈、链，都是存储结构；循环队列是一种顺序存储结构。
逻辑结构有线性结构(线性表)、非线性结构。
2．数据结构分为逻辑结构和存储结构，下列数据结构中不属于存储结构的是
A．线性链表
B．二叉链表
C．栈与队列
D．循环队列
线性链表是线性表的链式存储结构；二叉链表是二叉树的链式存储结构；栈与队列分别是特殊的线性表；循环队列是队列的一种顺序存储结构。可知，线性链表、二叉链表、循环队列均属于存储结构，而栈与队列属于逻辑结构。
3．针对线性表逻辑上相邻的两个元素，下列叙述中，正确的是( )
A.采用顺序存储时一定相邻，采用链式存储时也一定相邻
B.采用顺序存储时一定相邻，采用链式存储时不一定相邻
C.采用顺序存储时不一定相邻，采用链式存储时一定相邻
D.采用顺序存储时不一定相邻，采用链式存储时也不一定相邻
4．下列选项中，不属于线性结构的是
A．网
B．栈
C．队列
D．线性表
5．下列选项中，不属于线性结构的是
A．网 B．栈 C．队列 D．线性表
栈、队列、线性表都是线性结构。
6．下列选项中，与数据存储结构直接相关的是
A. 线性表
B. 双向链表
C. 二叉树
D. 有向图
答案：1，A；2，C；3，B；4，A；5，A；6，B。
