6.2数据结构基础

《6.2数据结构基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.2数据结构基础信息在计算机内部是以编码的形式表示，存储在一组有独立地址并且在物理上相互独立的内存单元中。这种简单的组织方式与我们日常数据处理中设想的一些数据的组织方式并不一样。例如，有关学生的信息可能是一张含有姓名、学号、性别、年龄、专业等数据的表来表示，每个学生的信息对应表的一行，每项内容是一列。象这样的数据如何在计算机中有效地表示来呢？也就是如何将这样一张表用内存中的一系列单元来表示呢？这就是数据结构(datastructure)需要研究的内容。数据结构试图探索一条可以把用户从实际数据存储的细节（存储单元和地址）中解脱出来，并且允许用户通过更方便的方式访问信息的途径

2、。实现这种途径的最主要方式就是抽象。所谓抽象(abstract)就是抽取出问题的本质，而屏蔽相关的细节。抽象的优点是：一方面具有良好的普适性，另一方面使程序员可以不用关心细节而专注于算法的设计。6.2.1抽象数据类型与数据结构随着计算机应用技术的发展，计算机加工处理的对象也由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据。所谓数据间的结构实际上就是数据元素之间存在的关系(relation)。首先，我们先来看一下数据元素间的关系问题。设数据元素集合为A，数据元素之间的关系实际上可抽象地表示为一个集合R。R={（ai,aj）

3、ai,aj属于数据元素集合A}例如，a、b

4、、c、d、e这5个人组成的集合为A，其中a、b、c3人是好朋友，d、e2人也是好朋友。这样，定义A上的“好朋友”关系就可以用以下集合来表示：“好朋友”={（a、b），（a、c）、（b、c），（d、e）}所以，一般来说，数据元素间的任何关系最终都可以用元素对的集合来表示。根据数据元素之间关系的不同特性，通常有以下三类基本的数据间的结构（如图6.3）：a1a2a3……an-1an（a)线性结构a1a2a3a1a4a5a2a3a4a5a6a7a6a7（b)树形结构(c)图状结构图6.3数据间的结构类型（1）线性结构(linearstructure)。结构中的数据元素存在一对一的关

5、系，即在关系集合R中，每个元素ai只唯一地与另一个元素aj有关系（（ai,aj）∈R），因而线性结构中的数据元素形成了一个有序的序列(如图6.3a)；（2）树形结构(treestructure)。结构中的元素之间存在一对多的关系，但不存在多对多·255·的关系；即在关系集合R中，每个元素ai可能与多个元素aj有关系（（ai,aj）∈R），但对每一个元素aj，只能唯一地与另一个元素ai有关系(如图6.3b)。（3）图状结构或网状结构(graphstructure)。结构中的元素之间存在多对多的关系；即在关系集合R中，无论是ai还是aj都有可能与多个元素有关系(如图6.3c)。

6、结构反映了数据间的逻辑关系，也是对客观世界中多种多样数据的一种抽象。数据的逻辑结构在计算机程序中的实现就是数据的物理结构，又称存储结构。从程序设计的角度看，存储结构最终需要用程序设计语言所提供的手段来实现，也就是用程序设计语言所提供的手段来表达数据并实现对数据的操作。最主要的两种实现方式是数组(array)和链表(chainedlist)。有关数组和链表的基本知识将在本章的6.2.2和6.2.3中分别讨论。数据的逻辑结构反映的是数据间的关系，是静态的。对于利用计算机程序设计来求解问题的目标来说，不仅要关心数据是如何组织的，更重要的是在这些良好组织的数据上如何对数据进行处理，

7、即在数据结构上的操作。静态的对象（结构）和动态地作用于对象上的操作就构成了数据类型。数据类型是和数据结构密切相关的一个概念。它最早出现在高级程序设计语言中，用以刻画（程序）操作对象的特性。在用高级程序设计语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型（如整数类型）。类型明显或隐含地规定了在程序执行期间变量或表达式所有可能的取值范围（如，计算机所能表达的整数并不是可以无限大的），以及在这些值上允许进行的操作。因此，数据类型是一个值的集合和定义在这个值集上的一组操作的总称。例如，整数类型是一种数据类型，包含了两个方面的含义：（1）类型的对象，属于{…,-

8、2,-1,0,1,2,…}；（2）可使用于对象上的操作，有+、-、*、/。抽象数据类型(abstractdatatype)是指一个数学模型（对象）以及定义在该模型上的一组操作。抽象数据类型关心的是数据的逻辑特性，而不是物理特性。抽象数据类型本质上与数据类型是一样的。但数据类型一般指程序设计语言中提供的类型，而抽象数据类型还可以包括用户在软件设计中自己定义的数据类型。有了抽象数据类型之后，用户不用再关心任务是如何完成的，而是关心能够完成哪些任务。也就是说，抽象数据类型包含了一组定义（函数），使得编程者可以使用这些函数