下载掌阅APP，畅读海量书库
立即打开
在系统地学习数据结构知识之前，需要先了解一些概念和术语。
1.数据（Data）
数据是信息的载体，是所有能够被计算机识别、存储和加工处理的符号的总称。 它是计算机程序加工的原料，应用程序可以处理各种各样的数据。在计算机科学中，数据是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数和复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像和语音等。
2.数据项（Data Item）
数据项是具有独立含义的标识单位，是数据不可分割的最小单位。 例如，学生成绩表中的“学号”和“姓名”等。数据项有名和值之分，数据项名是一个数据项的标识，用变量定义，而数据项值是它的一个可能取值，表中“20221801”是数据项“学号”的一个取值。数据项具有一定的类型，依数据项的取值类型而定。
3.数据元素（Data Element）
数据元素是数据的基本单位。 在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。例如，考试查分系统的学生成绩表中的一个记录、棋盘布局问题中状态树的一个状态、教学计划编排问题中的一个顶点等，都被称为一个数据元素。
有时，一个数据元素可由若干个数据项组成。例如，学籍管理系统中学生信息表的每一个数据元素就是一个学生记录。它包括学生的学号、姓名、性别、籍贯、出生年月、成绩等数据项。这些数据项可以分为两种：一种叫作初等项，如学生的性别、籍贯等，这些数据项是在数据处理时不能再分割的最小单位；另一种叫作组合项，如学生的成绩，它可以再划分为数学、物理、化学等更小的项。通常，在解决实际应用问题时每个学生记录是被当作一个基本单位进行访问和处理的。
4.数据对象（Data Object）
数据对象或数据元素类（Data Element Class）是具有相同性质的数据元素的集合。 在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象（数据元素类），数据元素是数据元素类的一个实例。例如，在交通咨询系统的交通网中，所有的顶点是一个数据元素类，顶点A和顶点B各代表一个城市，是该数据元素类中的两个实例，其数据元素的值分别为A和B。
5.数据结构（Data Structure）
数据结构是指互相之间存在着一种或多种关系的数据元素的集合。 数据结构涉及数据元素之间的 逻辑关系 ，数据在计算机中的 存储方式 和在这些数据上定义的一组 运算 ，一般称这三个方面为数据的逻辑结构、数据的存储结构和数据的运算。
（1）数据的逻辑结构
在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的逻辑关系，这种数据元素之间的关系称为逻辑结构。数据的逻辑结构包含两个要素：一个是数据元素的集合，另一个是关系的集合。
在形式上，数据的逻辑结构通常可以采用一个二元组来表示：
Data_Structure=（D，R）
其中，D是数据元素的有限集，R是D上关系的有限集。
根据数据元素间关系的不同特性，数据的逻辑结构通常分为以下四类。
1） 集合 。在集合中，数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。
2） 线性结构 。该结构的数据元素之间存在着一对一的关系。
3） 树形结构 。该结构的数据元素之间存在着一对多的关系。
4） 图形结构 。该结构的数据元素之间存在着多对多的关系。 图形 结构也称作网状结构。
图1-3所示为上述四类基本逻辑结构的示意图。
图1-3 四类基本逻辑结构
a）集合 b）线性结构 c）树形结构 d）图形结构
由于集合是数据元素之间关系极为松散的一种结构，因此也可用其他结构来表示它。
数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，它与数据的存储结构无关。人们研究数据结构的目的是为了在计算机中实现对它的操作，为此还需要研究如何在计算机中表示一个数据结构。数据结构在计算机中的标识（又称映像）称为数据的物理结构，又称存储结构。它所研究的是数据的逻辑结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。
（2）数据的存储结构
数据的存储结构最常用的是顺序存储和链式存储两种方法。
1） 顺序存储方法 是把逻辑上相邻的元素存储在物理位置相邻的存储单元中，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助程序设计语言中的数组来实现。
2） 链式存储方法 对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过相关联的指示来表示，由此得到的存储表示称为链式存储结构。链式存储结构通常借助程序设计语言中的指针或引用来实现。
除了顺序存储方法和链式存储方法外，有时为了查找方便还采用索引存储方法和散列存储方法。
3） 索引存储方法 是在存储结点信息的同时，还建立附加的索引表。索引表中的每一项包含关键字和地址，关键字是能够唯一标识一个数据元素的数据项，地址指示出数据元素所在的存储位置。索引存储主要是针对数据内容的存储，而不强调关系的存储。索引存储方法主要面向查找操作。
4） 散列存储方法 是以数据元素的关键字的值为自变量，通过某个函数（散列函数）计算出该元素的存储位置。索引存储也是针对数据内容的存储方式。
以上四种存储方法中，顺序存储方法和链式存储方法是最基本和最常用的，索引存储方法和散列存储方法在具体实现时需要用到前两种方法。在实际应用中，一种逻辑结构可以有不同的存储方法，选用何种存储结构来表示相应的逻辑结构要视具体情况而定，主要考虑运算的实现及算法的时空要求。
（3）数据的运算
运算是对数据的处理。运算与逻辑结构紧密相连，每种逻辑结构都有一个运算的集合。运算的种类很多，根据操作的结果，可将运算分为两种类型。
1） 引用型运算 。这类运算不改变数据结构中原有数据元素的状态，只根据需要读取某些信息。
2） 加工型运算 。这类运算的结果会改变数据结构中原有数据的状态，如数据元素的内容和个数等。
数据的运算是定义在数据的逻辑结构上的，但运算的具体实现是在数据的存储结构上进行的。数据的运算是数据结构不可分割的一个方面，在数据的逻辑结构和存储结构给定之后，如果定义的运算集及运算的性质不同，也会导致完全不同的数据结构，如后面章节中将要介绍的线性表、栈和队列等。
1.数据类型（Data Type）
数据类型是和数据结构密切相关的一个概念 。它最早出现在高级程序设计语言中，用以刻画程序中操作对象的特性。在用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。类型显式地或隐含地规定了在程序执行期间变量或表达式所有可能的取值范围，以及在这些值上允许进行的操作。因此， 数据类型是一个值的集合和定义在这个值集上的一组操作的总称 。
在高级程序设计语言中， 数据类型可分为两类：一类是原子类型，另一类则是结构类型。原子类型的值是不可分解的 。例如，Java语言中的整型、字符型、浮点型、双精度型、布尔型等基本类型，分别用保留字int、char、float、double、boolean标识。而 结构类型的值是由若干成分按某种结构组成的 ，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。在某种意义上，数据结构可以看成是“一组具有相同结构的值”，而数据类型则可被看成是由一种数据结构和定义在其上的一组操作所组成的。
2.抽象数据类型（Abstract Data Type，ADT）
抽象数据类型是指一个数学模型及定义在该模型上的一组操作。 抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。也就是说，不论其内部结构如何变化，只要它的数学特性不变，都不会影响其外部的使用。
抽象数据类型和数据类型实质上是一个概念 。例如，各种计算机都拥有的整数类型就是一个抽象数据类型，尽管它们在不同处理器上占用的字节数不尽相同，整数运算的实现方法也可以不同，但由于其定义的数学特性相同，在用户看来都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。
此外， 抽象数据类型的范畴更广 ，它不再局限于前述各处理器中已定义并实现的数据类型，还包括用户在设计软件系统时自己定义的数据类型。为了提高软件的重用性，在近代程序设计方法学中，要求在构成软件系统的每个相对独立的模块上，定义一组数据和作用于这些数据上的一组操作，并在模块的内部给出这些数据的表示及其操作的细节，而在模块的外部使用的只是抽象的数据及抽象的操作。这就是面向对象的程序设计方法。
抽象数据类型可定义为由一种数据结构和定义在其上的一组操作组成，而数据结构又包括数据元素及元素间的关系。因此， 抽象数据类型一般可以由元素、关系及操作三种要素来定义 。
抽象数据类型的特征是使用与实现相分离，实行封装和信息隐蔽 。也就是说，在抽象数据类型设计时，把类型的定义与其实现分离开来。
根据抽象数据类型的构成，可采用如下的形式对其进行定义。
【例1-4】抽象数据类型“矩阵”的定义。
