学习数据结构的目的是为了了解计算机处理对象的特性,将实际问题中所涉
及的处理对象在计算机中表示出来,并对它们进行处理。对于计算机专业的学生,
不学习数据结构,几 乎无法继续前行,因为几乎所有的程序和软件都要用到某种
或某些数据结构。例如,在 面向对象程序设计中,一个对象在严格意义上来说就
是一个数据结构,而哪个程序不使用对象呢?可以这样说,不懂数据结构,就编
不出什么像样的程序和软件。
此外,数据结构在软件工程和计算机学科的其他领域也发挥着非常重要甚至
是极为关键的作用。例如,对大型数据库的管理、为互联网提供索引服务、云计
算和云存储等都需要广泛使用数据结构。在软件工程领域,数据结构被单独提取
出来,作为软件设计与实现过程的一个阶段。
3.1.2
基本概念和术语
在系统地学习数据结构知识之前,先来学习一下数据、数据元素、数据项等
基本概念和术语的确切含义。
数据(
Data
)
是信息的载体,能够被计算机识别、存储和加工处理。它是计
算机程序加工的原料,应用程序处理各种各样的数据。计算机科学中,数据就是
计算机加工处理的对象,它可以是数值数据,也可以是非数值数据。数值数据是
一些整数、实数或复数,主要用于工程计算、科学计算和商务处理等;非数值数
据包括字符、文字、图形、图像和语音等。
数据元素(
Data Element
)
是数据的基本单位。在不同的条件下,数据元素
又可称为元素、结点、顶点和记录等。例如,学生信息检索系统里学生信息表中
的一个记录、计算机系统组成结构中状态树的一个状态以及最短路径问题中的一
个顶点等,都被称为一个数据元素。
有时,一个数据元素可由若干个数据项组成。例如,学生信息检索系统中学
生信息表的每一个数据元素都是一个学生记录,它包括学生的学号、姓名、性别、
专业和年级数据项。这些数据项可以分为两种:一种叫做初等数据项,如学生的
性别、年级等,这些数据项是数据处理时不能再分割的最小单位;另一种叫做组
合数据项,如学生的成绩,它可以再划分为由多门不同课程成绩组成的更小项。
数据项(
Data Item
)
是组成数据元素的有独立含义且不可分割的最小单位,
如表 1-1 中的学号、姓名和年级等都是数据项。数据项有名和值之分,数据项名
是一个数据项的标识,用变量定义,而数据项值是它的一个可能取值。例如,表
1-1 中的 2011010001 是数据项“学号”的一个取值。数据项具有一定的类型,依数
据项的取值类型而定。
数据对象(
Data Object
)
是相同性质的数据元素的集合,是数据集合的一
个子集。在某个具体问题中,数据元素具有相同的性质(但元素值不一定相等),
属于同一个数据对象,数据元素是数据元素类的一个实例。例如,在最短路径问
题中,所有的顶点都是一个数据元素类,顶点 A 和顶点 B 各自代表一个城市,
是该数据元素类中的两个实例,其数据元素的值分别为 A 和 B。
数据结构(
Data Structure
)
是指互相之间存在着一种或多种特定关系的数
据元素的集合。在计算机中,数据元素不是孤立的,它们之间存在着这样或那样
的关系,这种数据元素之间的关系称为结构。一个数据结构包含两个要素:一个