原标题：读懂数据结构

原文来自：CSDN      原文链接：https://blog.csdn.net/qq_43763494/article/details/102642319

第一章 绪论

分析待处理对象的特性，以及各处理对象之间的关系

1.1 什么是数据结构

具体问题 –抽象出–>  数学模型 -->  设计算法 -->  编出程序 -->
测试、调整 –直至 -->
最终解答

如何抽象？
寻求数学模型的实质：分析问题，提取操作的对象，找出这些操作对象之间含有的关系，用数学语言加以描述。

20世纪70年代初，人们认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法
———————————————————
数据结构的研究涉及计算机硬件（特别是编程理论、存储装置和存取方法等）的研究范围，软件的研究：无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。
——————————————
多维图形数据结构——发展
——————————————
从ADT（抽象数据类型）的观点来讨论数据结构（DS），已成为一种新趋势。

1.2 基本概念和术语

D（数据 Data）能输入计算机，并能被程序处理的符号的总称。
DE（数据元素 Data Element）D的基本单位，DI（数据项 Data Item）最小单位。
DO（数据对象 Data Object）D的子集，DO中的DE具有相同的性质。
DS（数据结构 Data Structure）有特定关系的DE集合(至今数据结构仍没有一个被一致公认的定义，这里是本书的简单解释)
S（结构 Structure）DE之间的关系。

注：大写字母是我个人用来表示相关名词的，并非课本上的！

——————
四种基本S：
①集合：无他，只有“同在一个集合”这个关系。
②线性S：(DE之间关系)一对一。
③树形S：一对多。
④图形S或网状S：多对多。
——————————————
DS的形式定义为的：Data Structure = （D，S）二元组
其中 D：DE的有限集；
S：D上关系的有限集(集合里面是一个个关系)。
D = {DE1，DE2，……}
S = {R1，R2，……}  R：关系（Relationship）
R 描述的是DE之间的逻辑关系，因此又称D的逻辑结构。
讨论DS是为了要在计算机中实现对DS的操作，那么DS如何在计算机中表示呢？
DS在计算机中的表示（映像）称为D的物理结构，又称为存储结构。
存储结构包括：
①DE的表示
②R的表示
———————
位串：（若干个位(bit)组合而成）表示一个DE，称为E（元素 Element）或N（结点 Node）
若DE由若干个DI组成时，位串对应于各DI的子位串称为DF（数据域  Data Field）
因此，E或N可以看成是DE的映像(即DE的表示)。
————————————————
R的表示方法有两种：
①顺序映像 ②非顺序映像
并由此得到存储结构：
①顺序存储结构 ②链式存储结构
顺序映像的特点：借E在存储器中的相对位置来表示DE之间的逻辑关系( R )。
非顺序映像的特点：借助指示元素存储地址的指针（pointer）表示DE之间的逻辑关系。
这里还有一张图！！！！！！

任何一个算法的设计取决于选定的数据(逻辑)结构，而算法的实现依赖于采用的存储结构。

DT（数据类型 Data Type）刻画(程序)操作对象的特性，按“值”的不同特性分为原子类型(不可分解的)、结构类型(可分解的)。

ADT（抽象数据类型 Abstract Data Type）定义仅取决于它的一组逻辑特性，与实现无关。

近代程序设计方法学指出：一个软件系统的框架应建立在数据之上，而不是建立在操作之上（后者是传统的软件设计方法所为）。

在某种意义上，数据结构可以看成是“一组具有相同结构的值”，则结构类型可以看成由一种数据结构和定义在其上的一组操作组成。

ADT的形式定义：ADT = （D，S，P）三元组
其中 D：数据对象（DO）；
S：D上的关系集；
P：对D的基本操作集。
定义格式：
ADT 抽象数据类型名 {
数据对象：<DO的定义>
数据关系：<DR的定义>
基本操作：<基本操作的定义>
} ADT 抽象数据类型名
其中，DO和DR的定义用伪码描述，基本操作的定义格式为。。。包括基本操作名、初始条件和操作结果。
基本操作有两种参数：
①赋值参数：只为操作提供输入值
②引用参数：以&打头，除可提供输入值外，还将返回操作结果（将其输入然后返回？）

PDT（多形数据类型 Polymorphic data type）是指其值的成分不确定的数据类型，本书中讨论的各种数据类型大多是PDT。

类C语言：介于伪码和C之间的。

免责声明：本文来自互联网新闻客户端自媒体，不代表本网的观点和立场。

合作及投稿邮箱：E-mail:editor@tusaishared.com