第1章绪论 1.1数据结构的地位 计算机诞生之初用于科学计算，现在主要用于数据处理。数据处理就是对现实世界中的 原始数据进行处理，最后得到人们所需的数据。但是由于很多原始数据是杂乱无章的，首先 得把它转化成有组织的数据，然后在这个有组织的数据的基础之上编写算法，得到人们所需 的数据。通俗地说，怎样把原始数据转化成有组织的数据，就是数据结构这门课的研究内容： 单有算法构成不了程序，只有加上数据结构之后，它才成为程序。不会数据结构，就不会编 写出程序。数据结构的地位如图1-1所示 原始数据 所需数据 原始数据 有组织的数据 一所需数据 数据结构 程 图1一1数据结构的地位 我们知道，虽然每个人都懂得英语的语法与基本类型，但是对于同样的题目，每个人写 出的作文，水平却高低不一。程序设计也和写英语作文一样，虽然程序员都懂得语言的语法 与语义，但是对于同样的问题，程序员写出来的程序不一样。有的人写出来的程序效率很高， 有的人却用复杂的方法来解决一个简单的问题。当然，程序设计水平的提高仅仅靠看几本程 序设计书是不行的。只有多思索、多练习，才能提高自己的程序设计水平：否则，书看得再 多，提高也不大。记得刚学程序设计时，常听人说程序设计水平要想提高，最重要的是多看 别人写的程序，多去思考问题。从别人写的程序中，我们可以发现效率更高的解决方法：从 思考问题的过程中，我们可以了解解决问题的方法常常不只一个。运用先前解决问题的经验， 来解决更复杂更深入的问题，是提高程序设计水平的最有效途径。数据结构正是前人在思索 问题的过程中所想出的解决方法。一般而言，在学习程字设计一段时间后，学习"数据结构" 便能让你的程序设计水平上一个台阶。如果只学会了程序设计的语法和语义，那么你只能解 决程序设计三分之一的问题，而且运用的方法并不是最有效的。但如果学会了数据结构的概 念，就能在程序设计上，运用最有效的方法来解决绝大多数的问题
1 第 1 章 绪论 1.1 数据结构的地位 计算机诞生之初用于科学计算，现在主要用于数据处理。数据处理就是对现实世界中的 原始数据进行处理，最后得到人们所需的数据。但是由于很多原始数据是杂乱无章的，首先 得把它转化成有组织的数据，然后在这个有组织的数据的基础之上编写算法，得到人们所需 的数据。通俗地说，怎样把原始数据转化成有组织的数据，就是数据结构这门课的研究内容； 单有算法构成不了程序，只有加上数据结构之后，它才成为程序。不会数据结构，就不会编 写出程序。数据结构的地位如图 1-1 所示： 图 1－1 数据结构的地位 我们知道，虽然每个人都懂得英语的语法与基本类型，但是对于同样的题目，每个人写 出的作文，水平却高低不一。程序设计也和写英语作文一样，虽然程序员都懂得语言的语法 与语义，但是对于同样的问题，程序员写出来的程序不一样。有的人写出来的程序效率很高， 有的人却用复杂的方法来解决一个简单的问题。当然，程序设计水平的提高仅仅靠看几本程 序设计书是不行的。只有多思索、多练习，才能提高自己的程序设计水平；否则，书看得再 多，提高也不大。记得刚学程序设计时，常听人说程序设计水平要想提高，最重要的是多看 别人写的程序，多去思考问题。从别人写的程序中，我们可以发现效率更高的解决方法；从 思考问题的过程中，我们可以了解解决问题的方法常常不只一个。运用先前解决问题的经验， 来解决更复杂更深入的问题，是提高程序设计水平的最有效途径。数据结构正是前人在思索 问题的过程中所想出的解决方法。一般而言，在学习程序设计一段时间后，学习"数据结构" 便能让你的程序设计水平上一个台阶。如果只学会了程序设计的语法和语义，那么你只能解 决程序设计三分之一的问题，而且运用的方法并不是最有效的。但如果学会了数据结构的概 念，就能在程序设计上，运用最有效的方法来解决绝大多数的问题
1.2基本概念和术语 1.2.1关于数据结构的几个基本概念 1.数据(daa):是对客观事物的符号表示，所有能输入到计算机中，被计算机程序识别 和处理的符号的总称。计算机程序处理各种各样的数据，可以是数值数据，如整数、 实数或复数：也可以是非数值数据，如字符、文字、图形、图像、声音等 2.数据元素(data element):数据结构的基本组成单位。数据结构研究的就是数据 元素以及数据元素之间的关系。一个数据元素可由一个或若干个数据项组成。 例如：描述一个学生信息的数据元素可由下列数据项组成： 姓名学号班号性别出生日期入学成绩 3数据对象Data Object)):是性质相同的数据元素的集合。 整数的数据对象是{-3，-2，-1,0,1,2,3，.} 英文字符类型的数据对象是{A,B,C,D,E,F,. 学生管理信息系统的数据对象是学校全体学生的集合 ,4数据结构（Data_Structure)相互之间存在一种或多种特定关系的数据元素的集合。 1.2.2数据结构的种类 根据数据元素之间关系的不同特性，有下列四类基本结构： 1.集合结构。在集合结构中，数据元素间的关系除了"属于同一个集合“外，别无任何 关系如图1-2所示：特别注意的是：数据元素之间有内在关系，但对于我们所研究的问题没 用，我们不去研究，我们也认为它们之间没关系。整数集合中的数据元素{3,2,1,0， 1,2,3,.除同属于一个集合外，别无任何关系。 O 图1一2集合结构 2.线性结构。该结构的数据元素之间存在着一对一的关系。每个数据元素有0个或 个前驱，0个或一个后继。如图13所示： ○
2 1.2 基本概念和术语 1.2.1 关于数据结构的几个基本概念 1.数据（data）：是对客观事物的符号表示，所有能输入到计算机中，被计算机程序识别 和处理的符号的总称。计算机程序处理各种各样的数据，可以是数值数据，如整数、 实数或复数；也可以是非数值数据，如字符、文字、图形、图像、声音等。 2.数据元素（data element）：数据结构的基本组成单位。数据结构研究的就是数据 元素以及数据元素之间的关系。一个数据元素可由一个或若干个数据项组成。 例如：描述一个学生信息的数据元素可由下列数据项组成： 姓名 学号 班号 性别 出生日期 入学成绩 3.数据对象(Data Object)：是性质相同的数据元素的集合。 整数的数据对象是{.-3，-2，-1，0，1，2，3，.} 英文字符类型的数据对象是{A，B，C，D，E，F，.} 学生管理信息系统的数据对象是学校全体学生的集合。 4.数据结构（ Data_Structure）相互之间存在一种或多种特定关系的数据元素的集合。 1.2.2 数据结构的种类 根据数据元素之间关系的不同特性，有下列四类基本结构： 1. 集合结构。在集合结构中，数据元素间的关系 除了"属于同一个集合"外，别无任何 关系,如图 1-2 所示：特别注意的是：数据元素之间有内在关系，但对于我们所研究的问题没 用，我们不去研究，我们也认为它们之间没关系。整数集合中的数据元素{.-3，-2，-1，0， 1，2，3，.}除同属于一个集合外，别无任何关系。 图 1－2 集合结构 2. 线性结构。该结构的数据元素之间存在着一对一的关系。每个数据元素有 0 个或一 个前驱，0 个或一个后继。如图 1-3 所示：
图1一3线性结构 3.树型结构。该结构的数据元素之间存在着一对多的关系。一个元素可有多个后继， 但只有0个或一个前驱。如图14所示： 图1一4树形结构 4.图形结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。 数据元素可以有多个前驱，也可以有多个后继。如图1-5所示： 图1一5图形结构 1.2.3数据结构的形式化定义 数据结构是一个二元组：Data-Structure-=(D,S)其中：D是数据元素的有限集，S是D 上关系的有限集。通俗一点说：D是数据元素的集合，S是数据元素之间关系的集合 例：复数的数据结构定义如下： Complex=(C,R) 其中：C是含两个实数的集合(C1,C2】,分别表示复数的实部和虚部，R={P;,P是 定义在集合上的一种有序关系{〈C1,C2)}二者不能互换。 上面数据结构定义D部分是对数据元素的一种数学描述(C1和C2是实数)，r部分描 3
3 图 1－3 线性结构 3. 树型结构。该结构的数据元素之间存在着一对多的关系。 一个元素可有多个后继， 但只有 0 个或一个前驱。如图 1-4 所示： 图 1－4 树形结构 4. 图形结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。 数据元素可以有多个前驱，也可以有多个后继。如图 1-5 所示： 图 1－5 图形结构 1.2.3 数据结构的形式化定义 数据结构是一个二元组： Data-Structure=(D，S)其中：D 是数据元素的有限集，S 是 D 上关系的有限集。通俗一点说：D 是数据元素的集合，S 是数据元素之间关系的集合。 例:复数的数据结构定义如下： Complex=(C，R) 其中：C 是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部， R={P}，P 是 定义在集合上的一种有序关系{〈C1，C2〉}二者不能互换。 上面数据结构定义 D 部分是对数据元素的一种数学描述（C1 和 C2 是实数）， r 部分描
述的是数据元素之间的逻辑关系({(C1,C2》,是一种有序关系，C1和C2不能互换)： 并不涉及在计算机中如何表示它，把(D,S)定义的数据结构称之为数据的逻辑结构。研究数 据结构的目的就是为了利用计算机对数据进行更为高效的处理，所以必须研究在计算机中如 何表示它，数据结构在计算机中的表示称为数据的物理结构。 1.2.4数据的物理结构 如果在机器语言的层面上讨论，什麼都是用"O"1"来表示。本课程在高级语言JAVA语 言层面上讨论，研究的是数据元素以及它们之间的关系在JAVA虚拟处理器中的表示。 1、数据元素的表示 单个数据项组成的数据元素利用JAVA语言固有的基本数据类型来表示。JAVA语言固有 的基本数据类型：整型、字符型、字符串型、双精度型等等。 例如：复数数据结构中的数据元素可用JAVA语言固有的双精度型型表示。由多个数据 项组成的数据元素利用JVA语言中的自己定义的类或结构来表示。 2、数据元素之间关系的表示 顺序存储：把数据元素按一定的规则放在一组地址连续的存储单元中，通过元素的存储 位置来体现数据元素之间的逻辑关系。逻辑上相邻的数据元素存储位置上也相邻。 以线性数据结构abcd为例： 线性数据结构abcd的顺序存储，把数据元素abcd放在一组地址连续的存储单元中，通 过元素的存储地址是否相邻来表示数据元素在逻辑上是否相邻：如图16所示： 存储地址 内存单元 图1一6顺序存储 链式存储：把数据元素结点中加一个引用域，通过指示元素存储地址的引用（©语言称 为指针)来体现数据元素的逻辑关系。逻辑上相邻的数据元素物理位置上不一定相邻。 线性数据结构abcd的顺序存储，把数据元素结点中加一个引用域，通过指示元素存储地 址的引用（©语言称为指针）来体现数据元素的逻辑关系。逻辑上相邻的数据元素物理位置
4 述的是数据元素之间的逻辑关系（{〈C1，C2〉}，是一种有序关系，C1 和 C2 不能互换）； 并不涉及在计算机中如何表示它，把(D，S)定义的数据结构称之为数据的逻辑结构。 研究数 据结构的目的就是为了利用计算机对数据进行更为高效的处理，所以必须研究在计算机中如 何表示它，数据结构在计算机中的表示称为数据的物理结构。 1.2.4 数据的物理结构 如果在机器语言的层面上讨论，什麽都是用"0""1" 来表示。本课程在高级语言-JAVA 语 言层面上讨论，研究的是数据元素以及它们之间的关系在 JAVA 虚拟处理器中的表示。 1、数据元素的表示 单个数据项组成的数据元素利用 JAVA 语言固有的基本数据类型来表示。JAVA 语言固有 的基本数据类型：整型、字符型、字符串型、双精度型等等。 例如：复数数据结构中的数据元素可用 JAVA 语言固有的双精度型型表示。由多个数据 项组成的数据元素利用 JAVA 语言中的自己定义的类或结构来表示。 2、数据元素之间关系的表示 顺序存储：把数据元素按一定的规则放在一组地址连续的存储单元中，通过元素的存储 位置来体现数据元素之间的逻辑关系。逻辑上相邻的数据元素存储位置上也相邻。 以线性数据结构 abcd 为例： a b c d 线性数据结构 abcd 的顺序存储，把数据元素 abcd 放在一组地址连续的存储单元中，通 过元素的存储地址是否相邻来表示数据元素在逻辑上是否相邻；如图 1-6 所示： 图 1－6 顺序存储 链式存储：把数据元素结点中加一个引用域，通过指示元素存储地址的引用（c 语言称 为指针）来体现数据元素的逻辑关系。逻辑上相邻的数据元素物理位置上不一定相邻。 线性数据结构 abcd 的顺序存储，把数据元素结点中加一个引用域，通过指示元素存储地 址的引用（c 语言称为指针）来体现数据元素的逻辑关系。逻辑上相邻的数据元素物理位置
上不一定相邻。如图1-7所示： head a→b□c□→d 存储地址 内容 直接后继存储地 100 b 120 120 160 首元泰位置， 144 100 160 NULL 图1一7链式存储 1.2.5抽象数据类型ADT 抽象数据类型就是在数据的逻辑结构基础上加上一组操作。为什麽还要研究操作呢？因 为针对不同的数据类型，定义于其上的操作也不一样。以JAVA语言中的int,string,Boolean 数据结构为例：lnt:有加、减、乘、除等操作.String:有取子串等操作Boolean有与、或、 非操作 在后面的章节中，研究每一种数据结构，都是从抽象数据类型开始。 和数据结构的形式定义相对应，抽象数据类型可用以下三元组表示ADT=D,S,P; 其中D是数据对象，S是D上的关系集，P是对D的基本操作集。本书采用以下格 式定义抽象数据类型： ADT抽象数据类型{ 数据对象：<数据对象的定义 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> }ADT抽象数据类型名 其中基本操作的定义： 基本操作名（参数表） 初始条件：<初始条件描述 操作结果：<操作结果描述> "初始条件“描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败， 并返回相应出错信息。"操作结果“说明了操作正常完成之后，数据结构的变化状况和英返回 的结果。若初始条件为空，则省略之。 5
5 上不一定相邻。如图 1-7 所示： head a b c d 图 1－7 链式存储 1.2.5 抽象数据类型 ADT 抽象数据类型就是在数据的逻辑结构基础上加上一组操作。为什麽还要研究操作呢？因 为针对不同的数据类型，定义于其上的操作也不一样。以 JAVA 语言中的 int，string，Boolean 数据结构为例：Int：有加、减、乘、除等操作.String：有取子串等操作.Boolean 有与、或、 非操作. 在后面的章节中，研究每一种数据结构，都是从抽象数据类型开始。 和数据结构的形式定义相对应，抽象数据类型可用以下三元组表示 ADT={D, S, P} 其中 D 是数据对象，S 是 D 上的关系集， P 是对 D 的基本操作集。本书采用以下格 式定义抽象数据类型： ADT 抽象数据类型{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> }ADT 抽象数据类型名 其中基本操作的定义： 基本操作名（参数表） 初始条件：<初始条件描述> 操作结果：<操作结果描述> "初始条件"描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败， 并返回相应出错信息。"操作结果"说明了操作正常完成之后，数据结构的变化状况和英返回 的结果。若初始条件为空，则省略之