作者：周颜军王玉茹关伟洲编著
出版社：人民邮电出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
数据结构试读：
前言
数据结构是计算机学科的一门重要的专业基础课，也是一门核心课程。数据结构在计算机专业的诸门课程中起到相互衔接、承前启后的作用。它的先修课程有离散数学、程序设计语言（如 C/C++ 语言）等，同时它又是其后续课程，如操作系统、编译原理、数据库系统、人工智能等的重要基础。数据结构也是培养非计算机专业学生计算机素质和软件设计能力而重点选择的一门基础课。
数据结构课程的目的是介绍各种常用的数据结构，阐明各种数据结构之间的内在逻辑关系，讨论它们在计算机中的存储表示，以及对这些数据进行的操作和实际算法。不仅为读者学习后续软件课程提供必要的基础知识，而且更重要的是在软件设计和编程水平上得以进一步的提高。通过对不同存储结构和相应算法的分析对比及上机实践，增强读者根据实际问题特征选择合适的数据结构并掌握求解算法的时间、空间复杂性的能力。
本书是根据数据结构课程的教学大纲，在分析和借鉴国内外同类教材的基础上，结合作者多年讲授“数据结构”课程的教学经验和体会编写而成的。全书分为10章和3个附录：第1章是概论部分，主要介绍数据结构的基本概念和算法描述、算法分析等内容。第2章讨论线性表及线性表的顺序存储结构——顺序表，主要介绍向量、栈和队列三种数据结构及递归的实现机制。第3章讨论线性表的链接存储结构——链表，主要介绍单链表、双链表、循环链表、栈和队列等内容。第4章介绍串，主要介绍串的基本概念、串的存储结构、基本操作和模式匹配。第5章是树形结构，主要介绍树与二叉树两种数据结构。包括树（森林）和二叉树的概念、存储结构、树(森林)和二叉树的遍历、线索二叉树、堆、哈夫曼树和树形结构的应用问题。第6章介绍图结构，主要介绍图的基本概念、图的存储结构及图的遍历、最小（代价）生成树、最短路径、拓扑排序、关键路径等内容。第7章介绍多维数组和广义表，主要讨论多维数组、特殊矩阵的存储表示与寻址公式，稀疏矩阵的存储方式，以及广义表的概念、存储结构与运算。第8章介绍各种排序方法，包括排序的基本概念、直接插入排序、Shell 排序、折半插入排序、表插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序和外排序等内容。第9章介绍各种查找方法，主要讨论线性表的顺序查找、折半查找和分块查找，树形表有二叉排序树、最佳二叉排序树、AVL树、B-树与B+ 树，以及散列表的查找。第10 章文件结构，主要介绍有关文件的基本概念、顺序文件、索引文件、索引顺序文件、散列文件、多重表文件和倒排文件。为方便读者的学习，本书还安排了2 个附录。附录A 是“Visual C++ 6.0 集成开发环境介绍”，书中有的算法给出了对应的 C/C++程序和机器执行结果，习题中也有不少算法题。安排这部分内容是方便读者将算法转换为程序并上机运行，以加深对问题的理解和实际能力的提高。附录B是“常用字符与ASCII码对照表”，这在讨论字符类型数据（如：第4章串）时会用到。
本书力求叙述通俗易懂，严谨流畅，内容充实，示例丰富，符号、图表规范，既适合于教学又便于自学。本书注意数据结构和算法的有机结合，注重算法的完整性，在给出算法之前，对其实现的基本思想和要点都做了详细的讨论，算法除了有对应C/C++程序外，有的还给出了机器运行的结果，便于读者深入的理解和掌握。
本书的另一个特点是：对算法的描述采用多种方式，书中采用接近于自然语言的伪语言和C语言两种方式来同时描述算法。另外主要章节还给出了数据结构的ADT和C++的类描述（可从人民邮电出版社教学服务与资源网www.ptpedu.com.cn免费下载）。这不仅可以使读者从中学到多种描述算法的方法，也便于各类读者的使用。
本书是可作为普通高等学校计算机专业数据结构课程的教材，也可作为信息技术与管理等专业的教材和教学参考书；同时也可供从事计算机软件开发和计算机应用相关的工程技术人员参考。书中全部内容可在60～80学时内完成。“*”的章节可由教师根据授课时数进行取舍。
本书在编写过程中，得到了人民邮电出版社的大力支持，也得到了东北师范大学计算机科学与信息技术学院领导和同事的鼓励和帮助，在此一并表示诚挚的谢意。
由于时间仓促和作者水平有限，书中难免存在疏漏和错误，敬请读者批评指正。作者2013年6月
第1章 概论
用计算机解决各种实际问题的实质就是数据表示和数据处理，这也可以归结为对数据结构和算法的探讨。数据结构和算法是计算机科学中的两个基本问题，本章主要围绕这两个问题做概括性的介绍。
1.1 数据结构的概念
数据（data）是信息的载体，是描述客观事物的数字、字符以及所有能够输入到计算机中并被计算机程序处理的符号的集合。计算机能够处理多种形式的数据。主要分为两大类：一类是数值型的数据，主要用于工程和科学计算等领域；另一类是非数值数据，如字符型数据，以及图形、图像、声音等多媒体数据。
数据元素（data element）是表示数据的基本单位，是数据这个集合中的一个个体。在数据结构中数据元素经常称之为结点（node）。一个数据元素又可以由若干个数据项（data item）组成。数据项有两种：一种是初等项，是具有独立含义的最小标识单位；另一种是组合项，是具有独立含义的标识单位，它通常由一个或多个初等项和组合项组成。
数据对象（data object）是具有相同性质的数据元素的集合，是数据这个集合的一个子集。例如，整数数据对象可以是集合I ={ 0，±1，±2，… }。英文字母的数据对象可以是集合 letter ={ A, a, B, b, …, Z, z }。有些数据对象表现为复杂的形式，例如表1.1所示为一个单位职工工资情况的一个数据对象。表1.1 职工工资表
每个职工的工资情况占一行，每一行则是一个数据元素。每一个数据元素由编号、姓名、发给项（基本工资、工龄工资、交通补助）。扣除项（房租费、水电费、托儿费）、实发工资等数据项组成。其中发给项和扣除项为组合项，其他的数据项均为初等项。而这个工资表就是一个数据对象。
通常，数据对象中的数据元素不是孤立的，而是彼此相关的，它们彼此之间存在的相互关系称为结构。简单地说，数据结构就是要描述数据元素之间的相互关系，而一般并不着重于数据元素的具体内容。虽然数据结构至今还没有一个公认的标准定义，但一般数据结构都联系着：数据之间的逻辑关系、数据在计算机中的存储方式以及数据的运算（操作）三个方面。分别称为数据的逻辑结构（logical structure）、存储结构（storage structure）和运算（即对数据所施加的操作）集合，存储结构也称为物理结构（physical structure)。因此，数据结构可以定义为：按某种逻辑关系组织起来一批数据，以一定的存储方式把它存储于计算机的存储器之中，并在这些数据上定义了一个运算的集合，就叫作一个数据结构。
1.2 数据结构的组成与分类
1.2.1 数据的逻辑结构
数据的逻辑结构可以形式地描述为一个二元组
Data_ Structure =(D,R)
其中：D 是数据元素（结点）的有穷集合；R 是D 上关系的有穷集合，每个关系都是D 到D上的关系。在不发生混淆的情况下，通常把数据的逻辑结构直接称为数据结构。
例如，线性表的逻辑结构可以表示为
Linear _ List = ( D,R )
D={a0, a1,…,an-1}
R = { r }
r = {< ai-1, ai> | ai∈ D, 1 ≤ i ≤ n -1 }
即根据 r ，D 中的结点可以排成一个线性序列：
a0,a1,…,an-1
其中有序对
数据的逻辑结构可以分为两大类：一类是线性结构，另一类是非线性结构。
线性结构有且仅有一个开始结点和一个终端结点，并且每个结点至多只有一个前驱和一个后继。线性表是一种典型的线性结构。前面介绍的职工工资表就是一个线性表。
非线性结构中的一个结点可能有多个前驱和后继。如果一个结点至多只有一个前驱而可以有多个后继，这种结构就是树形结构。树形结构是一种非常重要的非线性结构。如果对结点的前驱和后继的个数都不作限制，即任何两个结点之间都可能有邻接关系，我们把这种结构就叫作图。图是更一般、更为复杂的一种数据结构。数据这几种逻辑结构如图1-1所示，图中的小圆圈表示结点，结点之间的连线代表逻辑关系，即相应数据元素之间有邻接关系。图1-1 基本的逻辑结构
1.2.2 数据的存储结构
数据的逻辑结构是从逻辑关系上来描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构属于用户的视图，是面向实际问题的。可以看作是从具体问题中抽象出来的数学模型，它反映了数据组织的“本质”，是数据组织的主要方面。抓住了这种本质，就可以根据解题需要重新组织数据，即把数据中的所有数据元素按所需的逻辑结构重新进行安排。例如，对于表1.1 表示职工工资情况的表格，既可以按照原样组织成线性表，也可以重新组织成树形结构，具体的选择应根据解题的需要来决定。数据的存储结构是数据的逻辑结构在计算机存储器中的实现，它是依赖于计算机的。也可以说，数据的存储结构是数据的逻辑结构用计算机语言的实现（或称为存储映象），它是依赖于计算机语言的。对机器语言而言，存储结构是具体的，但在数据结构中只在高级语言的层次上来讨论存储结构。
计算机的存储器（内存）是由有限多个存储单元组成的，每个存储单元都有一个唯一的地址，各存储单元的地址是连续编码的，每个存储单元 w 都有唯一的后继单元 w'= suc(w)。w和w' 称为相邻单元。一片连续的存储单元的整体称为存储区域（M），假设一个存储单元的长度为c，则有w' = suc(w)=w +c。
设有逻辑结构 B = ( D, R )，要把 B 存储在计算机中，就应该建立一个从D的结点到 M的单元的映象 f：D → M，即对于每一个 k ∈ D，都有唯一一个w∈ M，使得f(k)= w，w为结点k所占存储空间的首单元地址。这里使用LOC(k)表示结点 k 对应的存储单元的首地址。
数据的存储结构有以下四种基本的存储方式。
1．顺序存储方式
顺序存储方式是把逻辑上相邻的结点存储在物理位置也相邻的存储单元里，结点之间的逻辑关系用存储单元的邻接关系来体现，即在所存储的区域中原来逻辑上相邻的结点其物理位置也相邻。由此得到的存储表示称为顺序存储结构（sequential storage structure）。顺序存储主要用于线性结构，非线性结构也可以通过某种线性化的方法来实现顺序存储。通常顺序存储是用高级语言的一维数组来描述的。
2．链接存储方式
链接存储方式对逻辑上相邻的结点不要求在存储的物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段来表示的。由此得到的存储表示称为链接存储结构（linked storage structure），通常要借助于程序设计语言的指针类型来描述它。非线性结构常用链接存储方式，线性结构也可以使用链接存储方式。
3．索引存储方式
索引存储方式是在存储结点数据的同时，还需建立附加的索引表。索引表中的每一项称为索引项，一般由关键字和地址组成。关键字（key）是能够唯一标识一个结点的一个或多个字段。若每个结点在索引表中都有一个索引项，则该索引表称作为稠密索引（dense index）。若一组结点在索引表中只对应一个索引项，则把这样的索引表称作为稀疏索引（sparse index）。稠密索引中索引项的地址指示该结点的存储位置，而稀疏索引中索引项的地址则是指示一组结点的起始存储位置。
4．散列存储方式
散列存储方法就是根据结点的关键字通过反映结点与存储地址之间对应关系的函数直接计算出该结点的存储地址（或位置）。
这4种基本的存储方法形成了四种不同的存储结构，如图1-2所示。图1-2 4种基本的存储方式
如果结构所占用的存储区域都分配给了数据，则这样的存储结构称为紧凑结构，否则称为非紧凑结构。顺序存储方式是紧凑结构，而链接存储方式是非紧凑结构。
结构的存储密度（storage density）定义为数据本身所占的存储量与整个结构所占的存储量之比，即
显然，紧凑结构的存储密度为1，非紧凑结构的存储密度小于1。存储密度越大，则存储空间的利用率越高。但是，存储附加的信息也会带来运算上的方便。例如，在链表中，由于存储了指针，所以链表与顺序表相比，它进行插入和删除运算就会方便得多。这也体现了“牺牲空间来换取时间”的思想。
1.2.3 数据的运算（集合）
数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一个运算的集合。这些运算实际上是定义在抽象的数据上所施加的一系列的操作，所谓抽象的操作，是指我们只知道这些操作是“做什么”，而无需考虑“如何做”的问题。但运算的实现要在存储结构上进行，只有确定了的存储结构之后，我们才考虑如何具体实现这些运算（即算法）。如何描述算法的问题在本章后面讲述。
常见的一些运算有如下几种。（1）查找（检索）；（2）插入；（3）删除；（4）修改（更新）；（5）排序；（6）合并；（7）分拆等。
数据的逻辑结构、存储结构和运算（集合）是数据结构的三要素，三者之间既有区别、又有联系。严格地说，这三者共同构成了一个完整的数据结构。如果有两个数据结构被视为是相同的，则它们必须在逻辑结构、存储结构和运算集合三个方面均相同。只要有一个方面两者不相同，就把它们视为是不同的数据结构。例如，对于相同的逻辑结构―线性表，由于采用了不同的存储结构：一个采用了顺序存储结构，而另一个采用了链接存储结构，因而把它们看作是两种不同的数据结构，一个叫作顺序表，而另一个叫作链表。又例如，在顺序表中，两个数据结构的逻辑结构和存储结构均相同，但是定义的运算集合及其运算的性质不同，也导致出完全不同的数据结构，这就是我们在第 2 章里要讲述的向量、顺序栈和顺序队列。
1.3 数据类型与抽象数据类型
1.3.1 数据类型
数据类型（data type）是一组性质相同的值的集合以及在这些值上定义一组操作（运算）的总称。每一种计算机高级语言都有自己的数据类型定义。在通用的计算机高级语言中，一般都具有整数、实数（浮点数）、枚举、字符、字符串、指针、数组、记录（结构）、联合和文件等数据类型。如整数类型在计算机系统中通常用两个字节和四个字节表示，如果采用两个字节，则整数的表示范围在-32768～32767之间；如果采用四个字节，则整数的表示范围在-2 147 483 648～2 147 483 647之间。这依赖于具体的机器实现系统。除了定义整数的取值范围之外，还规定了对整数可施加的加、减、乘、除和取模等运算。
按值是否可“分解”，数据类型可分为简单类型（也称为初等类型或基本类型）和结构类型（或组合类型）两种。
简单类型中的每个数据都是无法再分割的整体，例如：
FORTRAN语言提供了整型、实型、复型和布尔型等简单数据类型；
PASCAL 语言提供了整型（integer）、实型（real）、字符型（char）、布尔型（boolean）和指针型（pointer）等简单数据类型；
C 语言提供了整型、实型（浮点型）、字符型、枚举类型、指针型和空类型等简单数据类型。
结构类型其值可分解为若干个成份（或称为分量），如 C 语言的数组、结构等数据类型。初等类型通常是由语言直接提供的，而组合类型则是由用户借助于语言提供的描述机制自己来定义的，它通常是由标准类型派生的，因此它也是一种导出类型。通常数据类型可以看作是程序设计语言中已实现的数据结构。
程序设计语言允许的数据类型越多，它的处理能力就越强、应用范围也越广。因此，程序设计语言所提供的数据类型的多寡，也是衡量程序设计语言功能强弱的一个重要指标。
1.3.2 抽象数据类型
抽象是对事物的简化描述，就是抽取反映问题本质的东西，而忽略非本质的一些细节。抽象可以分为不同的层次，低层次抽象可以作为高层次抽象的一种实现。抽象是人们理解复杂现象和求解复杂问题时经常使用的一种方法。
数据类型已经反映出对数据的抽象。例如，在计算机中使用二进制定点数和浮点数实现数据的存储和运算，而在汇编语言中使用者可以直接使用它们的自然表示，如123，1.4E10, 25.2 等，不必考虑它们实现的细节，它们是对二进制数据的抽象。在高级语言中，出现了整型、实型、字符型、指针等数据类型，给出了更高一级的数据抽象。随着抽象数据类型（abstract data type）和面向对象程序设计语言的出现，可以进一步定义出更高层次的数据抽象，各种表、树和图，甚至窗口和管理器等。这种数据抽象的层次为软件设计者提供了有力的手段，使设计者可以从抽象的概念出发，从整体上进行考虑，然后自顶向下，逐步展开，最后得到所需要的结果。
抽象数据类型是指抽象数据的组织和与之相关的操作。抽象数据类型通常是由用户自己定义，用以表示应用问题的数据模型，它可以看作是数据的逻辑结构及逻辑结构上定义的操作。
一个 ADT可形式描述为：
ADT 抽象数据类型名 {
Data
数据元素集合及数据元素之间的逻辑关系的描述
Operations
构造函数
Initial value: 用来初始化对象的数据
Process: 初始化对象
操作1
Input: 用户输入的数据
Preconditions: 系统执行本操作前数据所需的状态
Process: 对数据进行的处理
Output: 操作后返回的数据
Postconditions: 系统操作后数据的状态
操作2
……
操作n
……
} //ADT 抽象数据类型名
例1.1 圆的 ADT 描述。圆是平面上与圆心等距离的所有点的集合。从图形显示的角度看，圆的抽象数据类型应包括圆心和半径；但从计量的角度看，其抽象数据类型只需要半径。这里仅从计量的角度给出圆的 ADT ，它包括求圆的周长和面积的操作。
ADT Circle {
Data
非负实数，表示圆的半径
Operations
构造函数
Initial value: 圆的半径
Process: 给圆的半径赋初值
Circumference
Input: 无
Preconditions: 无
Process: 计算圆的周长
Output: 返回圆的周长
Postconditions: 无:
Area
Input: 无
Preconditions: 无
Process: 计算圆的面积
Output: 返回圆的面积
Postconditions: 无:
} //ADT Circle
抽象数据类型可以看作是描述问题的模型，它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在 ADT 里定义的某些操作来访问其中的数据，从而实现了信息屏蔽与隐藏。在 C++中，可以用类的说明来表示ADT，用类的实现来实现 ADT ，因此 C++中实现的类相当于数据的存储结构及其在存储结构上实现对数据的操作。
ADT 和类的概念反映了软件设计的两层抽象：ADT 相当于在概念层（抽象层）上描述问题，而类相当于在是实现层上描述问题。
本书在正文中还仍然用自然语言的方式来描述数据的逻辑结构，它对应用于在概念层（抽象层）上描述的 ADT。用 C 语言的类型定义来描述数据的存储结构，并用接近于自然语言的一种伪语言与 C/C++语言两种方式来描述对数据的操作（即算法）。这样来处理，可以使读者从中了解和学习到描述算法的多种方式。
1.4 算法的概念与描述
1.4.1 算法的概念
要让计算机求解问题，除了要选择恰当的数据结构之外，还需要制定出解决问题的切实可行的方法和步骤，这就是所谓的计算机算法。由于数据结构包含着运算集合，这些运算的实现是通过算法来完成的，本书在讨论各种数据结构的同时，还介绍了很多相关的算法。早在20世纪70年代，D.E.Knuth 就指出，计算机科学就是研究算法的学问。因此，算法也是本课程的重点内容之一。下面先介绍算法的概念。
算法（algorithm）是规则的有穷集合，这些规则规定了解决某一特定类型问题的一个运算（操作）序列。此外一个算法应当具有以下特性。（1）输入：一个算法必须有若干个输入（包括0个）。（2）输出：一个算法应该有一个或多个输出。（3）有穷性：一个算法必须总是在执行有穷步之后结束。（4）确定性：算法的每一步都应确切地、无歧义地定义。即对于每一种情况，需要执行的动作都应当严格的、清晰的规定。（5）可行性：算法中每一个运算都应是基本的、可行的，也就是说，它们原则上都是能够由人们仅用笔和纸做有穷次运算即可完成的。
需要指出的是，算法的含义与程序十分类似的，但也有明显的差别。一个程序并不一定需要满足上述的第3个特性（有穷性），例如操作系统，只要整个系统不受破坏，操作系统就无休止地为用户提供服务，永不结束。另外，程序应是用机器可执行的某种程序设计语言来书写的，而算法通常并没有这样的限制。
1.4.2 算法的描述
算法设计人员在构思和设计了一个算法之后，必须准确清楚地把这些所涉及的解题步骤记录下来，或提供交流，或编写成程序以供计算机来执行。
常用的描述算法的方式有自然语言、数学语言、流程图、伪语言和程序设计语言等。无论采用哪一种方式，都必须能够精确地描述计算过程。一般而言，描述算法最合适的语言是介于自然语言和程序设计语言之间的伪语言，它的控制结构往往非常类似于 Pascal、C 等程序语言，但其中可使用任何表达能力强的方法，使算法表达更加清晰和简捷，而不至于陷入具体的程序语言的某些细节。我们将采用这种接近于自然语言，并与 C 语言的控制结构又非常类似的伪语言（以下简称伪语言）来描述算法。同时考虑到读者易于上机验证算法和提高读者的编程能力，本书在给出算法的同时基本上也对应地给出了 C/C++语言的描述。由于上机环境设定在 Visual C++ 6.0 开发平台上，因此我们也使用了 C++的一些功能，如单行注释（//...）、引用（&）、存储空间的申请（new）与释放（delete），以及输入（cin）和输出（cout）等功能，这样可以避免 C 语言的繁琐和不便之处。
下面给出伪语言和要使用到的 C++对C 语言的部分扩充功能的概要说明。
一、用伪语言描述算法
1．算法的总体轮廓
一个算法应由算法标题、算法内容体、结束标记三部分组成。格式如下：
算法 <算法编号> <中文书写的算法名>
<英文书写的算法名>（<参数表>）
1．---------------------------------------------
2．---------------------------------------------
3．---------------------------------------------（1）-----------------------------------（2）------------------------------------
ⅰ）---------------------------
ⓐ---------------------
ⓑ---------------------
ⓒ---------------------
⋮
ⅱ）---------------------------
ⅲ）---------------------------（3）------------------------------------
⋮
4．----------------------------------------------
5．[ 算法结束 ] ▉
①上面给出的算法总体轮廓描述中，头两行为算法标题，算法标题应写在一行的中间，算法名应反映出该算法所能完成的主要功能。如果它不被其他算法所调用，算法标题的第二行可以省略。
②后面的各行共同组成了算法体，算法体的书写采用层次结构，并按上面的规定，分层的标明，书写时同一层按列对齐。
③算法右下角的黑方块记号“▉”为结束标志，表示整个算法的结束。
2．算法使用的主要语句（1）注释。
算法中的任何位置必要时可加入汉字书写的注释，说明其功能，注释的形式是用方括号括起来的作为解释说明用的汉字串，即
［汉字串］（2）赋值语句。
格式：变量名←表达式
例如：X ← 500
A[i] ← i+3（3）条件语句。
条件语句可以有如下两种格式：
格式1：若 条件
则 语句1
否则 语句2
格式2：若 条件
则 语句（4）循环语句。
ⓐ for语句
格式：循环 <循环变量>步长为<表达式1>，从<表示式2>到<表达式3>，反复执行
循环体
ⓑ while语句
格式：循环 当<条件>时, 反复执行
循环体
ⓒ do - while语句
格式：循环反复执行，当<条件>时
循环体（5）跳出循环语句。
格式：跳出循环
一个跳出循环语句只能跳出一层循环。（6）复合语句。
格式：语句1；语句2；…；语句n
即多个语句之间用分号分隔。（7）输出语句。
格式：PRINT( X )
其功能是将X的内容输出。（8）转向语句。
格式：转向 标号
基本上不用转向语句。（9）情况语句。
格式：分以下情况执行
情况1：语句1
情况2：语句2
……
情况n：语句n
其他情况：语句n+1（10） 结束语句。
格式：算法结束
下面看一个用伪语言书写算法的例子。
例1.2 求n ( <100)个整型元素中的最大元素。
设用 C 语言说明的存储结构如下：
#define m 100
int A[m];
int i, pos, n;
进入算法前，n个元素已存入数组A[0],A[1], …,A[n-1]之中，这里n应该小于m。
算法结束后，变量 pos的值即为最大元素在数组A中的下标位置，并以变参的形式返回。
算法1.1 寻找最大元素
findMax(A, n, pos)
1．[ 赋初值 ] pos ← 0
2．循环i步长为1，从1到n-1，执行
若A[pos] 则pos ← i 3．[ 算法结束 ] ▉ 二、用C语言描述算法 我们假定读者已具有 C 语言的基础，这里仅对少量使用的 C++的一些功能，如单行注释（ //...）、引用（&）、存储空间的申请（new）与释放（delete）以及输入/输出（I/O 流）等功能，作概要性的介绍。从中可以看到 C++语言的优点和方便之处。 1．注释（//） C++的注释也称单行注释，它为“//”之后的内容，直到换行。 例如：//这是一个C++的注释 另外，C++还兼容了C语言的注释，即一对符号“/*”与“*/”之间的内容。它可以占一行也可以占多行。 2．引用（&） 引用通常被认为是变量的别名。当建立引用时，程序用另一个变量或对象的名字将它初始化。对引用的改动，实际上是对目标的改动。 引用定义格式如下： <类型>&<引用名>=<变量名>; 例如：int i; int& k = i; i = 5; k = k+3; 这里，k 是一个引用，它是变量 i 的别名。所有在引用上所进行的操作，实质上就是对被引用者的操作。如上面程序片段执行后，实际上是变量i加3，使i值改变为 8。 引用的用途是：用来作为函数的参数和函数的返回值。下面我们举一个两个变量的值交换的例子说明这个问题。 例1.3 交换变量x和y的值。假设 x=5; y=10;调用 swap(x, y)后可实现两个变量x和y值的交换。 void swap( int& x1, int& y1) { int temp; temp = x1; x1 = y1; y1 = temp; } 由于在 C 语言中，函数的参数是以传值的方式进行的，如果不是引用方式，调用 swap(x,y) 后，变量x和y的值维持不变，没有实现交换。虽然，使用指针传递方式的swap( int* , int* )函数调用，能够达到预定的目的，但使用起来比较麻烦。 3．存储空间的申请（new）与释放（delete） new和delete是C++专有的操作符，任何使用malloc函数和free函数的地方都可以使用new和delete 运算符。malloc 函数和free 函数是 C/C++语言的标准库函数，而new 和delete 是C++的运算符。它们都可用于申请动态内存和释放内存。new 类似于函数 malloc( )，但比 malloc( )更简炼。new的操作数为数据类型，它可以带初始化值表或单元个数。new返回一个具有操作数的数值类型的指针。 它的格式是： pointer=new type; 或 pointer=new type[n]; 例如：int*p1,*p2,*p3; intnum=85; // …… p1=new int; //p1指向一个整型数 p2= int[200]; //p2指向存放200个整型数中的第一个数的空间位置 p3= int[num]; //分配85个整型数的存储空间， //p3指向85个整型数中的第一个数的空间位置 要释放由 new分配的内存就要使用 delete 运算符，如果 new 是以数组形式使用的，就要在指针名前加上空的方括号“[]”。 它的格式是： delete pointer; delete[] pointer; 例如：int *p1 = new int; int *p2 = new int[100]; //…… delete p1; delete[] p2; 使用 new 和 delete 具有以下优点： • 使用new和delete不必包含头文件（C语言中：#include • 在指针进行赋值之前无需显式转换类型，new 运算符将会自动返回正确的类型值。（C语言中：ptr = ( type*)malloc(element*sizeof(type));）。 • 更重要的是，new 和 delete 不仅仅分配内存块，当使用 new 和 delete 来分配对象时，它将自动调用该对象的构造函数；与之相对应，使用 delete 来释放内存时，将自动调用析构函数。 new和delete必须配对使用，malloc和free也是一样。 4．输入/输出（I/O流） 在 C++中，文件经常被看作流。当执行文件输入或输出时，可以一直发送或得到下一个字节。 在 C++的输入输出操作中，既可以使用流操作符（<<和>>），也可以使用 printf、scanf或其他在 stdio.h 头文件中定义的函数。流操作符提供了两种方便：一是如果使用默认的输入/输出格式，就不必使用格式指定符；二是它能够扩展流操作符，这样它们就能使用在类中。 例 1.4 编写输入两个单精度实数并输出两者之和的简单程序。下面是完成这一相同功能的两个程序。左边为 C++程序；右边为C程序。图1-3 输入与输出流的示意图 #include void main( ) { float x, y; cout << "Enter the first number:"; cin >> x; cout<< "Enter the second number:"; cin >> y; cout <<"The total is "<< x+y << endl; } #include void main( ) { float x, y; printf("Enter the first number:"); scanf("%f", &x); printf("Enter the second number:"); scanf("%f",&y); printf("The total is %f\n", x+y); } 注意上面使用流操作符cin和cout的程序与使用printf函数和scanf函数的程序之间的不同之处。 • 头文件是 iostream.h而不是stdio.h。 • 不需要格式指定符，这比printf函数和scanf函数用起来要简单。 • 在流操作符 cin 之中没有对操作数（变量）使用地址操作符（&），但在 scanf 函数中却必须使用。 • 数据流向标准输出设备（cout），它通常是指显示屏幕。 • 数据来自于标准输入（cin），它通常是指键盘。 • C++的流对象使用 endl输出一个回车，而 C需要使用\n ( C++同样也支持这种方式)。 输入/输出格式如下。 输入：cin>>变量>>变量>>…>>变量; 例如：cin>>a; cin>>x>>y>>z; 输出：cout <<表达式<<表达式<<…<<表达式; 或 cout <<表达式<<表达式<<…<<表达式<< endl; 例如：cout << a; cout <<"The total is"<< x+y-2; cout <<" s= "<< s << endl; 5．常量定义 通常的格式为： const type id =<初始化值>; 例如：用pi来表示π。 const float pi = 3.14159; 在 C 中，定义常量是用编译预定义指令（#define）通过宏替换的方法实现的。 例如： # define pi 3.14159 以上介绍了C++的部分功能，当然使用 C语言的对应功能也是可以实现的。 1.5 算法分析
1.5.1 算法性能的评价标准
数据结构的性能实际上是由实现它其中运算的算法来体现的。对于要解决的同一个问题，往往能编写出许多不同的算法。进行算法评价的目的，既在于从解决同一问题的不同算法中选择出较为合适的一种，又在于知道对现有的算法如何进行进一步的改进，从而设计出更好的算法。
判断一个算法的优劣，主要有以下几个标准。
1．正确性
正确性（correctness）是设计和评价一个算法的首要条件，一个正确的算法是指在合理的数据输入下，能够在有限的运行时间内得出正确的结果。即要求算法能够正确地执行预定的功能和性能要求。这就要求算法的编写者对问题的要求有正确的、深入的理解，并能对问题进行正确的、无歧义的描述和利用算法描述语言（如程序设计语言）正确地实现算法。
2．可读性
可读性（readability）是指一个算法供人们阅读的方便程度。这是理解、测试和修改算法的需要。一个可读性好的算法，应该是逻辑清晰、符合结构化和模块化的程序设计思想，所有的变量名和函数名的命名必须有实际含义，使人见名知意。在算法中应当适当添加注释，简要说明算法的功能、输入和输出参数的使用规则、重要数据的作用和算法中各程序段完成的主要功能等。必要时，还应当建立相应的文档。
3．健壮性
健壮性（robustness）是指在异常情况下，算法能够正常运行的能力。正确性与健壮性的区别在于：前者描述算法是在需求范围之内的行为，而后者描述算法是在需求范围之外的行为。健壮性包括：一是容错能力；二是恢复能力。容错能力是指发生异常情况时，系统不出错误的能力；而恢复能力则是指软件发生错误后重新运行时，能否恢复到没有发生错误前的状态的能力。健壮性要求在算法中对输入参数、打开文件、读文件记录，以及子程序调用状态进行自动检错和报错并通过与用户对话的方式来纠错的功能。这也叫做容错性或例外（异常）处理。一个完整的算法应该具备健壮性，能够对不合理的数据进行检查。但在编制算法的开始阶段，可以暂时不管它，集中精力考虑如何实现主要的功能，待到算法成熟时再追加它。
4．可用性
可用性（usability）是指用户使用软件的容易程度，亦称用户友好性。为便于用户使用，要求算法具有良好的界面，完备的用户文档。因此，算法的设计必须符合抽象数据类型和模块化的要求，最好所有的输入和输出都通过参数表显式地传递，尽量少用公共变量或全局变量，每个算法只完成一个功能。
5．效率
效率（efficiency）主要是指算法执行时计算机资源的消耗，包括运行时间和存储空间的开销，前者称为算法的时间代价，后者称为算法的空间代价。算法的效率与多种因素有关。例如，所用的计算机系统、可用的存储容量和算法的复杂性等。
算法的性能标准还有很多，如通用性、可移植性等，这些问题的详细讨论已超出了本课程的内容。在数据结构的课程中，我们在兼顾其他性能的基础上，主要考虑算法的效率，即主要讨论算法的时间代价和空间代价。
1.5.2 算法的复杂度
算法效率的度量通常采用算法的事前估计和事后测试两种方法。
一、算法的事后测试
因为计算机内部一般都有计时功能（如：时间函数 time()），不同算法的程序可以通过一组和若干组相同的统计数据以分辨优劣。但这种方法有两个缺陷：一是必须先运行依据算法编制的程序；二是所得时间的统计量依赖于计算机运行的速度、程序语言的级别、编译程序的优劣等环境因素，有时容易掩盖其算法本身的优劣。因此，通常采用另一种方法——事前估计。
二、算法的事前估计
算法的事前估计是通过算法的复杂性来评价算法的优劣，算法的复杂性与具体机器的运行环境和编译程序版本无关。它的大小只依赖于问题的规模，或者说是问题规模的函数。
一般将求解问题的输入量作为问题的规模，并用一个整数n来表示。问题的规模可以从问题的描述中找到。例如，在具有n个职工的工资表中进行查找操作，这个问题的规模就是n。矩阵乘积问题的规模是矩阵的阶数。而对于图结构问题的规模则是图中的顶点数和/或边数。
1．算法的时间复杂度
我们把计算机的一次执行，如一次赋值、一次判断、一次输入、一次输出等均看作是一个时间单位，而忽略它们之间在执行时间上的差异，即每条语句执行一次的时间均是单位时间。一个算法的耗费时间，应该是该算法中各个语句执行时间之和，而每个语句的执行时间就是该语句的执行次数。这样就可以独立于机器的软、硬件系统来分析算法的优劣。
算法的时间复杂度通常采用Ο( g(n)) 表示法。其定义为：
当且仅当存在正常数c和n0，对所有的n，当n≥n0时，使得T(n)≤c.g(n)成立，则称 T(n)=Ο( g(n))。
换句话说，Ο( g(n))给出了函数T(n)的上界（有多个上界时取上确界）。
T(n)=Ο(g(n))表示：随着问题规模 n 的增大，算法执行时间的增长率和 g(n)的增长率相同，或者说，两者具有相同的数量级。称作算法的时间复杂度增长的数量级为g(n)，算法的渐进时间复杂度(asymptotic time complexity)为Ο( g(n))，渐进时间复杂度通常简称为时间复杂度（性）。
下面看两个例子。
例1.5 n个整型元素求和的算法。
const int m=100;
int A[m], S;
int i, n; // n 小于 m
进入算法时，n 个元素已存入数组 A 之中。
伪语言描述：
算法1.2 元素求和
sum( A, n )
1． S ← 0
2．循环 i 步长为 1，从 0 到 n-1，执行
S ← S + A[i]
3．PRINT(S)
4．[ 算法结束 ] ▌
C/C++语言描述：
void sum( int A[], int n ) {
int i, S=0;
for ( i=0; i S = S + A[i]; cout<<"S = "<< S < } 上面的算法的时间复杂度为： T(n) = 1 + (n+1) + n + 1 = 2n + 3 =Ο(n)。 从上式可以得出： 此算法执行次数是 2n + 3 次，算法的时间复杂度是Ο(n)，也可以说是线性级（型）的。 例1.6 求两个n阶矩阵相乘的算法。 const int m=100; int A[m][m], B[m][m], C[m][m], S; int i, j, k, n; // n小于m 进入算法时，数据已存入矩阵 A 、B 之中。 伪语言描述： 算法1.3 矩阵相乘 MatrixMultiply ( A, B, C, n) 1．循环i步长为1，从0到n-1，执行 循环j 步长为 1，从0到n-1，执行（1）S ← 0（2）循环k步长为 1，从0到n-1，执行 S ← S +A[i][k]*B[k][j]（3）C[i][j ] ← S 2．[ 算法结束 ] ▌ C/C++语言描述： void MatrixMultiply ( int &A[ ][ ], int&B[][],int &C[ ][ ],int n ) { int i, j, k; for ( i=0; i for ( j=0; j S = 0; for ( k=0; k S=S+A[i][k]*B[k][j]; C[i][j] = S; } } 上面的算法的时间复杂度为223232 T(n) = (n+1) + n(n+1) + n+ n(n+1) +n+ n= 2n+ 4n+ 2n + 1 = 3O(n) 。 从上式可以得出：32 此算法的执行次数是 2n+ 4n+ 2n + 1 次。3 算法的时间复杂度是 O( n) ，也可以说是立方阶(型)的。 使用O表示法时，需要考虑关键操作的执行次数。如果最后给出的是渐进值，可直接考虑关键操作的执行次数，找出其与 n的函数关系T(n) = f (n)，从而得到渐进时间复杂度。323 假设f (n) = 4n+ 3n+ 2n + 7，当 n充分大时，T(n) = O(n) 。这32是因为当n很大时，与n相比，n与 n 的值往往不起决定作用，可以忽略不计。因此，只需保留最高次幂的项，常数系数与低次幂的项均可以忽略不计。 一般情况下，对于步长型循环语句只需考虑循环体中语句的执行次数，而忽略该语句中步长加 1、终值判断和控制转移等成份。当有若干个循环语句嵌套时，算法的时间复杂度是由最内层循环语句的循环体中的语句的执行次数（频度）来决定的。 有时，算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。例如，在一个一维数组从前向后顺序查找给定值K的算法中，它的主要工作是进行比较，如果数组中的第一个元素之就与给定值K相等，则执行比较的次数最少；如果数组中没有值为K的元素，则执行比较的次数最多。后一种情况耗费时间最多，是一种最坏的情况，在这种情况下耗费的时间是算法对于任何输入实例所用时间的上界。所以，如果不特殊说明，所讨论的时间复杂度均指最坏情况下的时间复杂度。有时，还需要讨论算法的平均（或期望）时间复杂度。所谓的平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的平均运行时间。 将常见的时间复杂度，按照数量级递增排列，依次为：23 O (1)、O ( log2n )、O (n)、O ( n log2n)、O (n)、O (n)、…、O n(2)等。 不同数量级的时间复杂度的取值和性状曲线分别如表1.2和图1-4所示。表1.2 各函数随n的增长函数值的变化情况图1-4 各函数的增长率 从表1.2和图1-4可见，我们应该尽可能选用小于或等于多项式阶 kO(n)的算法，而不希望选用指数阶的算法。 2．算法的空间复杂度 类似于算法的时间复杂度，可以用空间复杂度（space complexity）作为算法所需存储空间的量度，记作 S(n) = O(g(n)) 其中，n为问题的规模，g(n)为算法所处理的数据所需的存储空间与算法所需的辅助空间之和。 上式同样地表示出：随着问题规模n的增大，算法执行时所需存储空间的增长率与g(n)的增长率相同，称为算法的渐进空间复杂度（asymptotic space complexity），简称空间复杂度（性）。 在进行算法分析时，一般是重点讨论算法的时间代价，需要时也会讨论算法的空间代价。主要考虑的也只是算法运行时辅助空间的使用量，即除了算法所处理的数据之外所需的附加存储空间的大小，用以比较完成同一功能的几个算法之间的差异和它们的优劣。 一般地说，时间与空间是一个矛盾的统一体，往往可以用牺牲空间方法来换取时间，反之亦然。 1.6 本章小结 本章围绕两个计算机学科中的两个基本问题——数据结构与算法展开讨论。【本章的知识点】 一、数据结构方面 1．概念与术语。主要有数据、数据元素、数据项、数据类型、抽象数据类型、数据结构以及存储密度等。 2．数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系。概括如下。 • 逻辑结构包含线性结构（主要讨论线性表）与非线性结构（主要有树形、图、多维数组及广义表等）。 • 存储结构主要包含四种常用的存储表示方式 ，即：顺序存储、链式存储、索引存储和散列存储。 • 运算（操作）集合。常见的运算有：查找（检索）、插入、删除、修改（更新）、排序、合并与分拆等。 二、算法方面 1．概念部分。主要有算法、算法的时空复杂度、最好、最坏和平均时空复杂度等。 2．算法描述。主要使用伪语言和 C 语言两种书写方式，视其情况，可选择其中一种来书写（编制）算法。 3．算法分析。主要有事前分析与事后测试两种方法，重点掌握事前分析的方法，也就是对算法进行时间/空间复杂度分析。 以上两个方面的诸要素存在于整个数据结构的体系之中，在学习的过程中，应注意它们之间的联系与层次上的区别。如图1-5所示。图1-5 数据结构体系的层次关系 本章对全书内容进行了高度概括，读者应反复学习和经常回顾，因为它不仅是学习后续各章的重要基础，也能使读者从较高的认识视角对本课程有一个整体的把握。 习题 1．简述下列概念： 数据，数据元素，数据对象，数据结构，数据类型和抽象数据类型。 2．简述数据与信息的关系。 3．什么是数据的逻辑结构？什么是数据的存储结构（物理结构）？试述两者之间有何区别与联系。 4．试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算（集合）这三方面的内容。 5．线性结构与非线性结构的区别是什么？ 6．什么是算法？算法的特性是什么？试述算法与程序的区别。 7．算法的时间复杂度除与问题的规模相关外，还与哪些因素有关？ 8．设有两个算法在相同的系统环境上运行，其执行时间分别为2n100n和2，要使前者快于后者，n至少为多少？ 9．按增长率由小至大的顺序排列下列各函数： 10．请编写一个在100个元素的实数数组中，求最小元素的值及其下标的算法。 第2章 顺序表 线性结构是一种既简单又常用的数据结构，在线性结构中的任意一个结点至多只能有一个前驱与一个后继。线性表是一种典型的线性结构。 线性表（inear list）的逻辑结构可以描述为 L = ( D, R ) D={k0,k1,…,kn-1} R ={ r} r ={< ki-1, ki>| ki∈D, 1≤i≤n-1} 按照r，线性表可以排成一个线性序列：k0, k1,…,kn-1 因此，一个线性表是n (n ≥ 0)个数据元素（也称为结点）组成的有限序列。记为 L=(k0,k1,…,kn-1) 其中，L是表名；k0为起始结点，它没有前驱（predecessor），仅有一个后继（successor）；kn-1为终端结点，没有后继，仅有一个前驱；其余的每个结点 ki(i = 1, 2, … , n-2)都有且仅有一个前驱和一个后继。i称为表的序号。n是线性表中的结点个数，也称为表的长度。将n=0的线性表称作空表。 下面是几个线性表的例子。 Digit =( 0, 1, 2, 3, 4, 5, 6, 7, 8 ,9 ) Letter =( A, B, C, …, Z, a, b, …, z ) Months =( January, February, March, April, May, June, July, August, September, October, November, December) Color =( red, yellow, orange, green, black, blue, purple ) Dept =( 数学，计算机，物理，化学，生物，教育科学，中文，历史，外语 ) 在较为复杂的线性表中，一个结点可能由若干个数据项组成。例如，在表1.1 给出的“职工工资表”中，每个职工的信息就是一个结点，它是由编号、姓名、……、实发工资等数据项组成的。 结点是数据结构讨论的基本单位，在不同的结构中，常常有它不同的习惯叫法。在向量、数组中，习惯叫作元素；在图中，常叫作顶点；在文件中，叫作记录。在讨论线性表时，还经常把结点和表目当作同义词来混用，如第i个结点可以说成是第i个表目。 表目ki在线性表中的位置是通过下标i来反映的，我们说第i个表目，即指 ki，i称为该表目的索引（index）。 将一个线性表存放到计算机中，可以采用各种方法，最常用的存储方式有两种：顺序存储方式和链接存储方式。本章主要介绍线性表的顺序存储方式，线性表的的链接存储方式将在下一章讲述。 线性表的基本运算（操作）主要有如下几种。（1）初始化：即生成一个空的线性表。（2）创建一个线性表。（3）判断线性表是否为空。（4）求线性表中的结点个数，即求表长。（5）取线性表中的第i个结点。（6）查找线性表中值为x的结点。（7）在线性表的第 i 个位置上插入一个新结点。（8）删除线性表中的第i个结点。
试读结束[说明：试读内容隐藏了图片]