第1 章数据结构的基本概念 - 华信教育资源网.pdfVIP

第 1 章 数据结构的基本概念 本章学习目标 通过对本章内容的学习，学生应该能够做到： 1．了解：数据结构在计算机数据处理中的作用；基于面向对象描述数据结构算法 的优势，以及“对象=数据结构+算法”的概念。 2．理解：数据结构研究的数据之间的逻辑关系、数据在计算机内部的存储结构， 以及在数据的各种结构上实施有效操作或处理（算法）等概念和相互关系。 3．掌握：数据结构的相关基本概念与术语；面向对象的基本概念和基本思想。 计算机已经深入到人类社会的各个领域，计算机的应用已不再局限于科学计算，而是 更多地用于控制、管理及数据处理等非数值计算的处理工作。与此相应，计算机加工处理 的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据，这就给程序设 计带来一些新的问题。为了编写出一个好的程序，必须分析待处理对象的特性以及它们之 间存在的关系，这就是“数据结构”这门学科形成和发展的背景。分析数据对象之间的逻 辑关系，并用计算机存储结构体现出这些逻辑结构并操作这些数据，就是数据结构这门课 程要解决的问题。 1.1 数据结构的概念和术语 在讨论数据结构之前，让我们先掌握几个与数据结构密切相关的概念和术语。 数据 （Data ）：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计 算机中并被计算机处理的符号的总称。它是信息的载体，是计算机程序加工的“原料”。对 计算机科学而言，数据的含义极为广泛。一般来说，数据主要有两大类：一类是数值数据， 包括整数、实数、复数等，主要用于工程、科学计算和商业事务处理；另一类是非数值数 据，主要包括字符、字符串、图像、声音等，它们可以通过编码而转变为可被计算机处理 的数据。 数据元素 （Data Element ）：数据元素是数据的基本单位，在计算机程序中通常作为一 个整体进行考虑和处理。一个数据元素可由若干个数据项组成，例如，一个学生的基本信 息为一个数据元素，可以包括学号、姓名、性别、年龄、成绩、家庭地址等多个数据项。 数据项是数据处理中不可分割的最小单位。 数据对象 （Data Object ）：数据对象是性质相同的数据元素的集合，是数据的一个子 集。例如：英文字母数据对象可以是集合 L={ ‘A ’，‘B ’，‘C’，…，‘Z ’}，整数数据对 象可以是集合 N={32767，32766，…，1，0，1，2 ，…，32768} 。 数据结构 （Data Structure ）：数据结构是相互之间存在一种或多种特定关系的数据元 素的集合。在任何问题中，数据元素都不是孤立存在的，在它们之间存在某种关系，这种 数据元素相互之间的关系称为结构。 根据数据元素之间关系的不同特性，通常有如图 1.1.1 所示四类基本结构。 （1）集合 这种结构中的数据元素是无序且没有重复的元素，它们之间除了“同属于 一个集合”的关系外，无其他关系。 （2 ）线性结构 这种结构中的数据元素之间存在一个对一个的关系，所有的数据成员 按某种次序排列在一个序列中，除第一个元素外，每个元素都有一个且仅有一个直接前驱， 第一个数据元素没有直接前驱；除最后一个元素外，每个元素都有一个且仅有一个直接后 继，最后一个数据元素没有直接后继。 （3 ）树形结构 这种结构中的数据元素之间存在一个对多个的关系。 （4 ）图状结构或网状结构 这种结构中的数据元素之间存在多个对多个的关系。 图 1.1.1 四类基本结构 数据结构是一个二元组： Data_Structure = (D ，S) 其中，D 是数据元素的有限集，S 是 D 上关系的有限集。 上述结构定义中，关系描述的是数据元素之间的逻辑关系，因此，又称为数据的逻辑 结构。然而，讨论数据结构的目的是为了在计算机中实现对它的操作，因此，我们还需研 究如何在计算机中表示它。 数据结构在计算机中的表示称为数据的物理结构，又称为存储结构，它包括数据元素 的表示和关系的表示。在计算机中表示信息的最小单位是二进制的一位，叫作位。在计算 机中，我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素，通常称这个 位串为元素或结点。当数据元素由若干