第一章 数据结构及其基本概念

数据结构及其基本概念 福建师大 数计院

第一章 数据结构及其基本概念

1.1什么是数据结构(What is Data Structure)

数据结构是信息的组织方式。

数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即

一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理

上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分

数据在计算机内部的存储安排。数据结构是信息的一种组织方式，好的数据结构可以提高算法的效率

，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。从学

科角度来讲，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关

系和操作等等的学科。

[二]数据结构学科的研究对象 (The Object of Data Structure Research)

数据结构作为一门学科，主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此

，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（即算法）。通常

，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构的研究不仅

涉及到计算机硬件的研究，比如存储装置和存取方法，而且解决编译原理、操作系统、数据库系统的

数据元素在存储器中的分配问题的重要基础。

1.2 基本概念与学科术语(Basic Concepts and Terminologies)

数据（Data）:是一个集合的概念，是对客观事物的符号表示，在计算机科学中是指所有能被输入到计

数据结构及其基本概念 福建师大 数计院

算机中，并被计算机处理的符号的总称。是计算机处理的信息的某种特定的符号表示形式。

数据元素（Data Element）:是数据的基本单位，数据中的一个“个体”。又称为“记录”或者“表目

”。

数据项（Data Item）：数据的不可分割的最小单位。数据元素是数据项的集合。

数据对象（Data Object）：是性质相同的数据元素的集合，是数据的一个子集。

[总结]

数据项组成数据元素，数据元素组成数据对象，数据对象组成数据

数据结构（Data Structure）：是相互之间存在一种或多种特定关系的数据元素的集合。它包括三个

方面：数据元素的逻辑结构、存储结构和相适应的运算（操作）。

数据元素之间的逻辑关系被称为数据元素的逻辑结构，可以用一个二元组表示：

Data_Structure = (D, S) // Data_Structure= (Data-part, Logic-Structure-Part)

这里D是数据元素的集合，S是定义在D（或其他集合）上的关系的集合，

S = { R │ R : D×D×...}。

数据的逻辑结构可归结为以下四类:

（1）集合结构

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

（2）线性结构

结构中的数据元素之间存在一个对一个的前趋后继关系

在此种结构下：

有且仅有一个元素无前趋元素

有且仅有一个元素无后继元素

数据结构及其基本概念 福建师大 数计院

其余任何一个元素均有且仅有一个前趋有且仅有一个后继元素。

（3）树形结构

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

任何一个节点最多有一个前趋，可以有多个后继，是一种典型的非线性结构

（4）图状结构（网状结构）

结构中的数据元素之间存在多个对多个的关系

这种结构的特征是任何一个元素可以有多个前趋，也可以有多个后继，是一种多对多的前趋后继关系

表和树是最常用的两种高效数据结构，许多高效的算法可以用这两种数据结构来设计实现。表是线

性结构的（全序关系），树(偏序或层次关系)和图（局部有序(weak/local orders)）是非线性结构。

数据结构在计算机中的表示（又称为映像）称为数据的存储结构（物理结构）

数据结构的物理结构是指逻辑结构的存储映像(image)。数据结构 DS 的物理结构 P 对应于从 DS 的

数据元素到存储区M（维护着逻辑结构S）的一个映射：

PD,S) -- > M

存储器模型：一个存储器 M 是一系列固定大小的存储单元，每个单元 U 有一个唯一的地址 A(U)，该

地址被连续地编码。每个单元 U 有一个唯一的后继单元 U'=succ(U)。

P 的四种基本映射模型：顺序（sequential）、链接（linked）、索引（indexed）和散列（hashing

）映射。因此，我们至少可以得到4×4种可能的物理数据结构：

sequential (sets)

linked lists

indexed trees

数据结构及其基本概念 福建师大 数计院

hashing

graphs

需要指出的是：并不是所有的可能组合都合理。

数据结构DS上的操作：所有的定义 …… 此处隐藏：3842字，全部文档内容请下载后查看。喜欢就下载吧 ……