【五分钟】001-数据结构概论

2021年3月3日 1797点热度 0人点赞 0条评论

内容纲要

学习要求

概念和术语

数据结构的基本概念:数据、数据元素、数据结构、数据的逻辑结构、物理结构、算法等。

基本概念和术语

【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.集合结构：数据元素之间都没有逻辑关系。