作者：秦锋 汤亚玲 主编
出版社：高等教育出版分社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
数据结构(C++语言版)试读：
前言
写出高质量的程序是每个软件开发者追求的目标。要达到这个目标，仅靠学习几门高级语言是远远不够的，正如一个人仅靠认识几个汉字绝不会写出好文章一样。数据结构这门课程正是开启程序设计知识宝库的金钥匙，其主要目的是培养学生将现实世界抽象为数据和数据模型的能力以及利用计算机进行数据存储和数据加工的能力。
数据结构在计算机科学的各领域中应用十分广泛，如编译系统中要使用栈、语法树等，操作系统中要使用队列、存储管理表、目录树等，数据库系统中要使用线性表、链表、索引树等，人工智能中要使用广义表、检索树、图等。同样，在面向对象的程序设计、计算机图形学、多媒体技术、软件工程等领域，都会用到各种不同的数据结构。因此，学好“数据结构”这门课，能掌握更多的程序设计技巧，并能评价出算法的优劣，为以后学习计算机专业课程及走上工作岗位从事计算机大型软件开发打下良好的基础。
本书内容共 10章。第 1章介绍了数据结构与算法等一些基本概念，并对算法描述及算法分析做了简单说明，介绍了衡量算法优劣的主要因素：时间复杂度和空间复杂度的求法。第2章简单介绍了C++基本知识，让熟悉C语言但对C++比较陌生的读者能迅速掌握C++的基本要点，为后续章节的学习打下基础。第3章～第5章介绍了线性表、栈、队列、串等的线性结构的逻辑特性、存储结构，以及常用的操作算法的实现和基本应用。第6章～第8章介绍了多维数据、广义表、树、二叉树、图等非线性结构的逻辑特征，在计算机中的存储表示，一些常用算法实现及基本应用。第 9章～第 10章介绍了在计算机中使用非常广泛的排序和查找两种运算，对一些常用的查找、排序算法进行了详细描述，并给出了实现的算法及效率分析。
本书的特点是采用面向对象程序设计语言，即C++语言作为算法的描述语言，所有算法都已经在 VC++6.0 环境下上机调试通过。由于篇幅所限，大部分算法都以单独的函数形式给出；若读者要运行这些算法，还必须给出一些变量的说明及主函数来调用所给的函数。为方便读者对算法的理解和验证，书中尽量避免采用复杂的C++机制，如函数模板、类模板、虚基类、多重继承等，只采用通俗易懂的类定义、数据封装和对象指针及简单的继承等基本机制，让读者更多地关注算法本身的设计思想。“数据结构”是一门实践性很强的课程。读者在进行理论学习的同时，需要动手编写大量的程序并上机调试，以加深对所学知识的理解，也只有这样才能提高自己的编程能力。书中配有丰富的各种类型的习题。对于每章的算法设计题，希望读者思考并有选择地上机验证。
为方便教学，本书免费为授课教师提供电子教案和习题解答，可在人民邮电出版社教学服务与资源网（www.ptpedu.com.cn）上进行下载。
目前，“数据结构”是我国高校计算机专业的核心课程之一，也是其他信息类专业如信息管理、通信工程、信息与计算科学等的必修课程之一。正因为它在计算机培养计划中的重要地位，大多数高校计算机专业研究生入学考试都将“数据结构”作为必考课程之一。
本书可作为高等院校计算机类或信息类相关专业“数据结构”课程教材，建议理论课时为50～70学时，上机及课程设计等实践课时为20～30学时。各院校可根据本校的专业特点和学生的实际情况，适当增删。
本书由秦锋、汤亚玲任主编，负责全书的编撰和整理，以确保各章节内容的完整和风格的统一；由陈桂芬、章曙光、汪军、林芳、司秀丽、陈学进、秦飞任副主编。
其中，第1章、第7章由秦锋编写，第8 章由汤亚玲编写，第6章由陈桂芬编写，第9章由章曙光编写，第4章由汪军编写，第10章由林芳编写，第3章由司秀丽编写，第5章由陈学进编写，第2章由秦飞编写。全书由秦锋、汤亚玲负责修改并统稿。
因编者水平有限，书中难免有不足甚至错误之处，敬请广大读者批评指正！
建议或者意见请联系fqin@ahut.edu.cn、tangyl@ahut.edu.cn。编者2014年6月
第1章 绪论
教学提示：数据结构主要研究4方面的问题：（1）数据的逻辑结构，即数据之间的逻辑关系；（2）数据的物理结构，即数据在计算机内的存储方式；（3）对数据的加工，即基于某种存储方式的运行算法；（4）算法的分析，即评价算法的优劣。本章重点介绍数据结构研究问题所涉及的基本知识和概念。
教学目标：了解研究数据结构的目的及相关基本概念和术语，掌握算法基本概念和算法评价依据——时间复杂度和空间复杂度。
1.1 数据结构的概念
软件设计是计算机学科各领域的核心。在计算机发展的早期，软件设计所处理的数据都是整型、实型等简单数据，绝大多数的应用软件都是用于数值计算。随着信息技术的发展，计算机逐渐进入金融、商业、管理、通信及制造业等行业，广泛地应用于数据处理和过程控制。计算机加工处理的对象也由纯粹的数值型数据发展到字符、表格和图像等各种具有一定结构的数据，这就给程序设计带来一些新的问题。为了设计出一个结构好而且效率高的程序，必须研究数据的特性、相互关系及对应的存储表示，并利用这些特性和关系设计出相应的算法和程序，这正是数据结构课程研究的内容。
1.1.1 什么是数据结构
用计算机解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编写出程序进行调试、测试，直至得到最终的解答。
由于早期计算机所涉及的运算对象是简单的整型、实型或布尔类型数据，程序设计者的精力主要集中于程序设计的技巧上，无须重视数据结构。随着计算机应用领域的扩大和软、硬件技术的发展，非数值计算问题显得越来越重要。据统计，当今用计算机处理的非数值计算性问题占90%以上的机器时间，如图书资料的检索、职工档案管理、博弈游戏等，这类问题涉及的数据结构相当复杂，数据元素之间的相互关系无法用数学方程或数学公式来描述。这类问题的处理对象中的各分量不再是单纯的数值型数据，更多的是字符、字符串或其他编码表示的信息。因此，首要的问题是把处理对象中的各种信息按其逻辑特性组织起来，再研究如何把它们存储到计算机中。只有做完了这些工作，才能设计解决具体问题的算法，并编写出相应的程序。下面列举的具体问题就属于这一类。【例1.1】学生成绩查询。
假定要编写一个计算机程序以查询某大学或某地区学生英语四级考试成绩。解决此问题，首先要构造一张成绩登记表，表中每个登记项至少有3个信息：准考证号、姓名与考试成绩。写出查找算法的好坏，取决于这个登记表的结构及存储方式。最简单的方式是把表中的信息按照某种次序（如登记的次序）依次存储在计算机内一组连续的存储单元中。用高级语言表述，就是把整个表作为一个数组，表的每项（一个人的准考证号、姓名与考试成绩）是数组的一个元素。按准考证号查找时，从表的第一项开始，依次查对准考证号，直到找出指定的准考证号或确定表中没有要找的准考证号为止。这种查找算法对于一个规模不大的学校或许是可行的，但对于一个有几十万甚至几百万考生的省份或地区就不适用了。因此，一种常见的做法是把成绩登记表按照准考证号从小到大排序（见表1-1），并存储在计算机内一组连续的存储单元中，在查找时可以采用折半查找算法（第9章有详细介绍），查找速度可大大提高。表1-1 英语四级成绩表
从这个例子可以看出，成绩登记表如何构造、如何存储在计算机内存中将直接影响查找算法的设计以及算法的执行效率。表1-1是为解决英语四级成绩查询问题而建立的数学模型。这类模型的主要操作是按照某个特定要求（如给定姓名或准考证号等）对登记表进行查询。诸如此类的还有人事档案管理、图书资料管理等。这类文档管理的数学模型中，计算机处理的对象之间通常存在一种简单的线性关系，故这类数学模型可称为线性的数据结构。【例1.2】判定树问题。
有8枚硬币，分别用a、b、c、d、e、f、g、h表示，其中有且仅有一枚硬币是伪造的，假硬币的质量和真硬币的质量不同，可能轻，也可能重。现要求设计算法，用最少的比较次数挑选出假硬币，并同时确定这枚假硬币的质量比其他硬币的质量是重还是轻。
该问题的解决似乎比较难，借助一种叫作判定树的数据结构，将此问题的求解过程描述成图1.1。很容易看出，只要比较3次就能找出答案。图中字母H和L分别表示假硬币较其他真硬币重、轻。图1.1 判定树
显然，这种树结构不是线性结构，它比线性结构复杂。【例1.3】最小代价问题。
假设几个村庄之间要架设输电线路，根据电能的可传递性，并不需要在每对村庄之间架设线路。如何用最小代价架设线路让每个村庄都能用上电。
处理此类问题需要用到图这种数据结构。用顶点代表村庄，每对顶点之间的边代表村庄之间的线路，边的权值代表线路的建设费用，如图 1.2 所示。只要把这个图的有关信息存储在计算机中，利用图论中最小生成树算法，在此图中找出不能形成回路的n−1条边，并使得权值最小。显然，这种图结构比树结构更加复杂。图1.2 输电线路示意图
从上述3个例子可见，描述非数值计算问题的数学模型不再是数学方程或数学公式，而是诸如表、树、图之类的数据结构。从这些例子也可以看出，非数值计算问题的求解往往比较复杂，涉及数据的逻辑结构、数据存储、数据加工等。这也正是“数据结构”这门课程所要研究的内容。
1.1.2 学习数据结构的意义
数据结构是计算机科学与技术专业的核心基础课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付众多复杂课题的。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。学好“数据结构”这门课程，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。
数据结构作为一门独立的课程，最早是由美国开设的。1968年，美国唐• 欧• 克努特教授开创了数据结构的最初体系。他所著的《计算机程序设计技巧》第一卷《基本算法》，是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。20世纪60年代末至70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，数据结构的地位显得更为重要。人们认为，程序设计的实质是对确定的问题选一个好的结构，加上一种好的算法。当时，数据结构几乎和图论，特别是表、树的理论为同义语。随后，数据结构这个概念被扩充到包括图、集合、格、关系等方面，从而变成现在称为“离散结构”的内容。然而，由于数据必须在计算机中进行处理，因此，不仅要考虑数据本身的数学特性，还要考虑数据的存储结构，这就进一步扩大了数据结构的内容。
瑞士计算机科学家沃斯（N.Wirth）教授曾以“算法+数据结构=程序”作为他的一本著作的名称。可见，程序设计的实质是对实际问题选择一种好的数据结构，并设计一个好的算法。
数据结构的研究不仅涉及计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且与计算机软件的研究有着密切的关系。无论是编译程序还是操作系统，都涉及如何组织数据，使检索和存取数据更为方便。因此，可以认为，数据结构是介于数学、计算机硬件和软件三者之间的一门核心课程。
目前，数据结构是我国高校计算机专业的核心课程之一，也是其他信息类专业如信息管理、通信工程、信息与计算科学等的必修课程之一。
1.2 基本概念和术语
本节将对一些基本概念和术语加以定义和解释，这些概念和术语将在以后的章节中多次出现。
1.2.1 数据与数据元素
数据（Data）是对客观事物的符号表示，它能被计算机识别、存储和加工处理。它是计算机程序加工的“原料”。例如，一个代数方程求解程序所用到的数据是整数和实数，一个编译程序处理的对象是字符串（源程序）。在计算机科学中，数据的含义相当广泛。如客观世界中的声音、图像等，经过某些处理也可被计算机识别、存储和处理，因而它们也属于数据的范畴。
数据元素（Data Element）是数据的基本单位，有时也称为元素、结点、顶点、记录。一个数据元素可能由若干数据项（Data Item）组成。例如，例1.1 中的英语四级成绩表中，每个人的准考证号、姓名与成绩组成了一个数据元素，即一个数据元素包含3个数据项。整个英语四级成绩表就是计算机程序要处理的数据。数据项是最小标识单位，有时也称为字段、域或属性。数据元素也可以仅有一个数据项。
数据结构（Data Structure）是指数据元素之间的相互关系，即数据的组织形式。它一般包括以下3方面的内容：（1）数据元素之间的逻辑关系，也称为数据的逻辑结构（Logical Structure）。它独立于计算机，是数据本身所固有的。（2）数据元素及逻辑关系在计算机存储器内的表示方式，称为数据的存储结构（Storage Structure）。它是逻辑结构在计算机存储器中的映射，必须依赖于计算机。（3）数据运算，即对数据施加的操作。运算的定义直接依赖于逻辑结构，但运算的实现必须依赖于存储结构。
1.2.2 数据的逻辑结构
数据的逻辑结构是从逻辑关系上描述数据，不涉及数据在计算机中的存储，是独立于计算机的。可以说，数据的逻辑结构是程序员根据具体问题抽象出来的数学模型。数据中元素通常有下列四种形式的逻辑关系。（1）集合：任何两个元素之间都没有逻辑关系，每个元素都是孤立的。（2）线性结构：结构中的元素之间存在一对一的关系，即所谓的线性关系。例 1.1 中的四级考试成绩表就是一个线性结构。在这个结构中，元素（由一个人的准考证号、姓名和考试成绩组成）的排列十分有序，第一个元素之后紧跟着第二个元素，第二个元素之后紧跟着第三个元素，以此类推，整个结构就像一条“链”，故有“线性结构”之称。（3）树形结构：结构中的数据元素之间存在一对多的关系，如例 1.2 中的判定树。这种结构像自然界中倒长的“树”一样，呈分支、层次状态。在这种结构中，元素之间的逻辑关系通常称作双亲与子女关系。例如，家谱、行政组织结构等都可用树形结构来表示。（4）图状结构：结构中的元素之间存在多对多的关系。也就是说，元素间的逻辑关系可以是任意的，如例 1.3 的数学模型。在这种结构中，元素间的逻辑关系也称作邻接关系。通常将集合、树形结构、图状结构归纳为非线性结构。因此，数据的逻辑结构可分为两大类，即线性结构和非线性结构。
1.2.3 数据的存储结构
数据的存储结构是指数据在计算机内的表示方法，是逻辑结构的具体实现。因此，存储结构应包含两方面的内容，即数据元素本身的表示与数据元素间逻辑关系的表示。数据的存储结构有下列4种基本方式。（1）顺序存储：将数据元素依次存储于一组地址连续的存储单元中，元素间的逻辑关系由存储单元的位置直接体现，由此得到的存储表示称为顺序存储结构（Sequential Storage Structure）。高级语言中，常用一维数组来实现顺序存储结构。该方法主要用于线性结构。非线性结构也可通过某种线性化的处理，实现顺序存储。（2）链接存储：将数据元素存储在一组任意的存储单元中，用附加的指针域表示元素之间的逻辑关系，由此得到的存储表示称为链接存储（Linked Storage Structure）。使用这种存储结构时，往往把一个数据元素及附加的指针一起称作一个结点。高级语言中，常用指针变量实现链接存储。（3）索引存储：该方法的特点是在存储数据元素的同时，还可以建立附加的索引表。索引表中每一项称为索引项。索引项的一般形式是：（关键字，地址）。关键字是指能唯一标识数据元素的数据项。若每个数据元素在索引表中均有一个索引项，则该索引表称为稠密索引（DenseIndex）。若一个索引项对应一组数据元素，则该索引表称为稀疏索引（SparseIndex）。（4）散列存储：该方法是依据数据元素的关键字，用一个事先设计好的函数计算出该数据元素的存储地址，然后把它存入该地址中。这种函数称为散列函数，由散列函数计算出的地址称为散列地址。
上述4种存储方式既可单独使用，也可组合使用。逻辑结构确定后，采取何种存储结构，要根据具体问题而定，主要的考虑因素是运算方便、算法效率与空间的要求。例如为了提高查找例1.1中英语四级成绩表的效率，也可以采用索引存储方式，将姓张的、姓李的、姓王的……考生成绩分别按照姓氏存储在一起，同时建一个姓氏索引表。如果要查找李某的成绩，先到索引表中找到姓李的考生存储首地址，再去查找李某的成绩。
存储结构的描述与程序设计语言有关。用机器语言描述，则存储结构是数据元素在存储器中的物理位置；用高级语言描述，则不必涉及计算机的内存地址，可用类型说明来描述存储结构。
1.2.4 数据运算
数据运算是对数据施加的操作。每种逻辑结构都有一个基本运算的集合。例如，最常用的基本运算有检索（查找）、插入、删除、更新、排序等。因为这些运算是在逻辑结构上施加的操作，因此它们同逻辑结构一样也是抽象的，只规定“做什么”，无须考虑“如何做”。只有确定存储结构后，才能考虑“如何做”。简言之，运算在逻辑结构上定义，在存储结构上实现。
必须注意，数据结构包含逻辑结构、存储结构和运算三方面的内容。同一逻辑结构采用不同存储结构，得到的是不同的数据结构，常用不同的数据结构名来标识它们。例如，线性结构采用顺序存储时称为顺序表，采用链接存储时则称为链表。同样，同一逻辑结构定义不同的运算也会导致不同的数据结构。例如，若限制线性结构的插入、删除在一端进行，则该结构称为栈；若限制插入在一端进行，而删除在另一端进行，则称为队列。更进一步，若栈采用顺序存储结构，则称为顺序栈；若栈采用链式存储结构，则称为链栈。顺序栈与链栈也是两种不同的数据结构。
1.2.5 数据类型
数据类型（DataType）是和数据结构密切相关的一个概念，几乎所有高级语言都提供这一概念。数据类型是一个值的集合和在这个集合上定义的一组操作的总称。例如，C++中的整型变量，其值集为某个区间上的整数（区间大小依赖于不同的机器），定义在其上的操作为加、减、乘、除和取模等运算。
按“值”可否分解，可把数据类型分为两类。（1）原子类型：其值不可分解，如 C++的基本类型（整型、字符型、实型、枚举型）、指针类型和空类型。（2）结构类型：其值可分解成若干成分（或称分量），如 C++的数组类型、结构类型等。结构类型的成分可以是原子类型，也可以是某种结构类型。可以把数据类型看作程序设计语言已实现的数据结构。
引入数据类型的目的，从硬件角度考虑，是作为解释计算机内存中信息含义的一种手段；对用户来说，实现了信息的隐蔽，即将一切用户不必了解的细节都封装在类型中。例如，用户在使用整数类型时，既不需要了解整数在计算机内如何表示，也不必了解其操作（如两个整数相加）硬件是如何进行的。
1.2.6 抽象数据类型
抽象数据类型（Abstract Data Type，ADT）是指一个数学模型，以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。也就是说，不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。
抽象数据类型和数据类型实质上是一个概念。例如，整数类型是一个ADT，其数据对象是指能容纳的整数，基本操作有加、减、乘、除和取模等。尽管它们在不同处理器上的实现方法可以不同，但由于其定义的数学特性相同，在用户看来都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。
但在另一方面，抽象数据类型的范畴更广。它不再局限于前述各处理器中已定义并实现的数据类型，还包括用户在设计软件系统时自己定义的数据类型。为了提高软件的重用性，在近代程序设计方法学中，要求在构成软件系统的每个相对独立的模块上，定义一组数据和施于这些数据上的一组操作，并在模块的内部给出这些数据的表示及其操作的细节，而在模块的外部使用的只是抽象的数据及抽象的操作。这也就是面向对象的程序设计方法。
抽象数据类型的定义可以由一种数据结构和定义在其上的一组操作组成，而数据结构又包括数据元素间的关系，因此抽象数据类型一般可以由元素、关系及操作三种要素来定义。
抽象数据结构的特征是使用与实现相分离，实行封装的信息隐蔽。也就是说，在抽象数据类型设计时，把类型的定义与其实现分离开来。
1.3 算法和算法分析
1.3.1 算法定义及描述
数据运算是通过算法来描述的，因此讨论算法是数据结构课程的重要内容之一。
算法（Algorithm）是对特定问题求解步骤的描述，是指令的有限序列，其中每条指令表示一个或多个操作。对于实际问题，不仅要选择合适的数据结构，还要有好的算法，才能更好地求解问题。
一个算法必须具备下列5个特性。（1）有穷性：一个算法对于任何合法的输入必须在执行有穷步骤之后结束，且每步都可在有限时间内完成。（2）确定性：算法的每条指令必须有确切含义，不能有二义性。在任何条件下，算法只有唯一的一条执行路径，即对相同的输入只能得出相同的结果。（3）可行性：算法是可行的，即算法中描述的操作均可通过已经实现的基本运算的有限次执行来实现。（4）输入：一个算法有零个或多个输入，这些输入取自算法加工对象的集合。（5）输出：一个算法有一个或多个输出，这些输出应是算法对输入加工后合乎逻辑的结果。
程序与算法十分相似，但程序不一定要满足有穷性。例如，操作系统启动后，即使没有作业要处理，它仍然会处于等待循环中，以等待新的作业进入，所以不满足有穷性。另外，沃斯（N.Wirth）的“数据结构+算法=程序”公式意味着，可终止的程序的执行部分才是算法。
算法可以使用各种不同的方法来描述。
最简单的方法是使用自然语言。用自然语言来描述算法的优点是简单且便于人们对算法的阅读；缺点是不够严谨，容易产生二义性。
可以使用程序流程图、N-S图等算法描述工具。其特点是描述过程简洁明了。
用以上两种方法描述的算法不能直接在计算机上执行。若要将它转换成可执行的程序，还有一个编程的问题。
可以直接使用某种程序设计语言来描述算法。不过直接使用程序设计语言并不容易，而且不太直观，常常需要借助注释才能使人看明白。
为了解决理解与执行之间的矛盾，人们常常使用一种称为伪码语言的描述方法来进行算法描述。伪码语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而比自然语言更接近程序设计语言。它虽然不能直接执行，但很容易被转换成高级语言。本书采用C++语言作为描述数据结构和算法的工具，但在具体描述时有所简化，如常常将类型定义和变量定义省略。考虑到部分读者有C语言的基础但对C++不太熟悉，本书的第2章重点介绍C++的基础知识。
1.3.2 算法评价
什么是好的算法？同一个问题可能有多种求解的算法，到底哪个更优？通常对算法的评价按照下面4个指标来衡量。（1）正确性（Correctness）：算法的正确性主要有4个层次的要求，第一层次是指算法没有语法错误，第二层次是指算法对于几组输入数据能够得出满足规格说明要求的结果，第三层次是指算法对于精心选择的苛刻并带有刁难性的几组输入数据能够得出满足规格说明要求的结果，第四层次是指算法对于一切合法的输入数据都能得出满足规格说明要求的结果。显然，达到第四层次的正确性是非常困难的，因为所有不同输入数据的数量大得惊人，一一验证的方法既不可取也不现实。要证明一个算法完全正确还不是件容易的事情，目前也只处于理论研究阶段。当今对于大型软件进行专业测试，达到第三层次的正确性就认为该软件是合格产品。（2）可读性（Readability）：指算法要便于人们阅读、交流与调试。可读性好有助于人们对算法的理解；晦涩难懂的算法易于隐藏错误且难以调试和修改。
在此提供几个在程序编写上提高可读性的方法，以帮助读者建立起良好的编写风格。
①注释：一份良好的程序，除了程序本身外，最重要的是要有一份完整的程序说明文件。一份没有注释的程序，宛如一部天书，常常会让负责维护的程序员搞不懂设计者的设计思想。一份注释完整的程序，除了设计者自己阅读和排错上的方便外，更容易让人了解设计者的程序，并赞叹其在程序设计上的巧思与创意。通常，选择在重要的程序语句后面加上一个注释内容。
请读者将下面这一段程序与以前编写过的程序比较一下，看看这个程序是不是更容易读懂。
//= = = = = = = = = = Program Description= = = = = = = = = =
//程序名称：sum.c
//程序目的：设计一个计算二维数组每行元素之和的程序
//Written By Hua Li
//= = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
#include void RowSum(int A[][4], int nrow) //计算二维数组A每行元素值的和，nrow是行数 { for(int i = 0; i < nrow; i++) { for(int j = 1; j < 4; j++) A[i][0] += A[i][j]; //每行和保存于数组A的第0列 } } void main(void) //主函数 { int Table[3][4] = {{1,2,3,4},{2,3,4,5},{3,4,5,6}}; //定义并初始化数组 for(int i = 0; i < 3; i++) //输出数组元素 { for(int j = 0; j < 4; j++) cout << Table[i][j] << " "; cout << endl; } RowSum(Table,3); //调用子函数，计算各行和 for(i = 0; i < 3; i++) //输出计算结果 { cout << "Sum of row " << i << " is " < } } ②变量命名：编程时常常需要定义变量，变量的取名不可随意。假设想要写一个计算学生成绩的程序，程序中需要用户输入学生学号、语文成绩、英语成绩、数学成绩，最后再计算出3科的平均成绩。此时如果程序中的变量声明为： int x; int A,B,C; int D; 没有人会看懂这几个变量代表什么。即使在程序之初就注明X代表学生学号、A代表语文成绩、B代表英语成绩、C代表数学成绩、D代表3科平均成绩，在程序编写或维护过程中，也会很容易忘记它们的含义。如果把这5个变量声明为： int studentNum; //学生学号 int chinese; //语文成绩 int english; //英语成绩 int math; //数学成绩 int average; //3科平均成绩 这样是不是比较清楚易懂呢？因为变量的声明通常会在某一个特定的区域（如程序开头），如果在变量之后再加上一些注释说明，这样在编写或修改程序之际，变量声明的区域就像一个小字典，提供给设计者所有在此程序中的输入和输出信息。 ③程序缩排：在程序中经常会用到一些条件式语句或循环结构，这个语句包含了 C++语言中区块（Block），也就是一群单一语句的集合，通常以“{”及“}”来划分。“{”表示区块的开始，“}”表示区块的结束，在区块划分上有两种设计的风格。 一种是把开头的“{”与语句放在同一行，“}”要与第一行语句对齐，如： for(i=0 ; i<10 ; i++ ) { cout< if(key == data[i]) //查找到数据时 return i; counter++; //计数器递增 } 另一种是把开头的“{”不与语句放在同一行，“}”要与“{”对齐，如： for(i=0 ; i<10 ; i++ ) { cout< if(key == data[i]) //查找到数据时 return i; counter++; //计数器递增 } 这两种格式都可以，但第二种格式更规范，程序可读性更强。 另外程序中最好有缩排，可以帮助程序员减少排错的时间。缩排通常在一些区块、条件语句、循环结构上产生出层次的关系。缩排通常空 2 个空格、4 个空格或 8 个空格。其中以 4 个空格最佳。 ④段落：程序中除了子程序以外，还有一些专为某一个目的所写的语句，这些语句的个数不等。在编写程序时，不同目的语句之间最好插入一个空白行，再加上注释，这可让程序有段落的感觉，在排错时也较容易找出错误。（3）健壮性（Robustness）：当输入数据非法或运行环境改变时，算法能恰当地做出反应或进行处理，不会产生莫名其妙的输出结果。为此，算法中应对输入数据和参数进行合法性检查。例如，从键盘输入三角形的三条边的长度，求三角形的面积。当输入的3个值不能组成三角形时，不应继续计算，应该报告输入出错并进行处理。处理的方法应是返回一个表示错误或错误性质的值，并中止程序的执行，以便在更高的抽象层次上进行处理。（4）时空效率（Efficiency）：要求算法的执行时间尽可能短，占用的存储空间尽可能少。但这两者往往相互矛盾，节省了时间可能牺牲空间，反之亦然。设计者应在时间与空间两方面有所平衡。 评价算法优劣的4个指标，除“正确性”外，其他都不是硬性指标，有时指标间甚至互相抵触，很难做到十全十美，因此只能根据具体情况有所侧重。例如，若算法使用次数少，则力求可读性；若算法需重复多次使用，则力求节省时间；若问题的数据量很大，机器的存储量又较小，则力求节省空间。下面的算法分析主要讨论算法的时间性能以及空间性能。 1.3.3 算法性能分析与度量 可以用算法的时间复杂度与空间复杂度来评价算法的优劣。 将一个算法转换成程序并在计算机上执行时，其运行所需要的时间主要取决于下列因素。（1）硬件的速度，如使用PC还是小型机。（2）书写程序的语言。实现语言的级别越高，其执行效率就越低。（3）编译程序所生成目标代码的质量。代码优化较好的编译程序，其所生成的程序质量较高。（4）问题的规模。例如，求100以内的素数与求1000以内的素数，其执行的时间必然是不同的。 显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，定义时间复杂度如下。 一个算法的时间复杂度（Time Complexity）是指算法运行从开始到结束所需要的时间。这个时间就是该算法中每条语句的执行时间之和，而每条语句的执行时间是该语句执行次数（也称为频度）与执行该语句所需时间的乘积。但是，当算法转换为程序之后，一条语句执行一次所需的时间与机器的性能及编译程序生成目标代码的质量有关，是很难确定的。为此，假设执行每条语句所需的时间均为单位时间。在这一假设下，一个算法所花费的时间就等于算法中所有语句的频度之和。这样就可以脱离机器的硬、软件环境而独立地分析算法所消耗的时间。【例1.4】求两个N阶方阵的乘积C=A*B的算法如下。 #define N 100 void matrixMultiply(int A [N][N],int B[N][N],int C[N][N]) { ①for(i=0;i ② for(j=0; j ③ { C[i][j]=0; n2 ④ for(k=0;k ⑤ C[i][j]=C[i][j]+A[i][k]*B[k][j]; n } } 其中右边列出的是各语句的频度，n是方阵的阶数（N，问题的规模）。语句①是循环控制语句，它的频度由循环条件“i 综合上述分析，可以确定上述算法的执行时间（语句的频度之和）是32 T(n)=2n+3n+2n+1 显然，它是方阵阶数n的函数。 一般而言，一个算法的执行时间是求解问题的规模 n（如矩阵的阶数、线性表的长度）的函数，这是因为问题的规模往往决定了算法工作量的大小。但是，我们不关心它是个怎样的函数，只关心它的数量级量度，即它与什么简单函数f(n)是同一数量级的，即T(n)=O(f(n))。其中“O”是数学符号，其数学定义如下。 如果存在正的常数C和n，使得当n≥n时都满足0≤T(n)≤C*f(n)，00则称T(n)与f(n)是同一数量级的，并记作T(n)=O(f(n))。 算法的执行时间T(n)=O(f(n))为该算法的时间复杂度。它表示随着问题规模n的增大，该算法执行时间的增长率和 f (n)的增长率相同。 对于上面的例子，当n→∞时3 根据“O”的定义可知T(n)=O(n)，所以例1.4中求两个方阵之积3的算法的时间复杂度是O(n)。 一般而言，我们总是以算法的时间复杂度来评价一个算法时间性能的好坏。也就是说，对解决同一问题的不同算法，其时间性能可以宏观地评价。例如，用两个算法 A和 A求解同一问题，它们的时间1223耗费分别是T(n)=100n+5000n+3，T(n)=2n。如果问题规模n不太12大，则二者的时间花费也相差不大；若问题规模 n 很大，如 n=10 000，则二者的时间花费相差很大。二者的差别从时间复杂度上一目23了然，因为T(n)=O(n)，T(n)=O(n)，所以算法A的时间性能优于121算法A。2 如果一个算法的所有语句的频度之和是问题规模n的多项式，即k 则按“O”的定义可知T(n)=O(n)，称该算法为k次方阶算法。特别地，如T(n)=C，其中C为常数，即算法耗费的时间与问题规模n无关，则记T(n)=O(1)，称该算法为常数阶算法。 常见的时间复杂度，按数量级递增排序有：常数阶O(1)、对数阶23nO(logn)、线性阶O(n)、平方阶O(n)、立方阶O(n)、指数阶O(2)。2指数阶算法的执行时间随n的增大而迅速放大，所以其时间性能极差，当n稍大时我们就无法忍受，如汉诺塔问题。常见的时间复杂度有： 由于算法的时间复杂度仅刻画了算法执行时间的数量级，为了简化对算法时间性能的分析，通常的做法是，从算法中选取一种对于所研究的问题来说是最基本的操作，并以该基本操作执行的次数作为算法的时间度量。例如，对于例1.4，“乘法”运算是矩阵相乘问题的基3本操作，从语句⑤可见，该操作重复执行n次，所以例1.4中算法的3时间复杂度是O(n)。 显然，被选用的基本操作应是其重复执行次数与算法的执行时间成正比例的。例如，在查找或排序问题的算法中，通常选择“关键字比较”操作作为算法时间度量的基本操作。关键字比较次数越多，算法所花的时间也越多。 在多数情况下，被选的基本操作是含在嵌套层数最多的最内层循环体中。在这种情况下，该循环体的执行次数就可作为算法的时间度量。如下程序段： x=0; y=0; for(k=1;k<=n;k++) x=x+1; for(i=1;i<=n;i++) for(j=1;j<=n;j++) y=y+1; 其中嵌套层数最多的最内层的循环体是语句“y=y+1”，它应执22行n次。所以该程序段的时间复杂度是O(n)，其他语句可以不必理会。 有时，最内层循环的执行次数与问题的规模n并无直接关系，但却与外层循环变量的取值有关，而最外层循环次数直接与n有关。在这种情况下，可以由最内层循环开始向外计算出最内层循环体的执行次数。例如，有下列程序段： x=0； for(i=2;i<=n;i++) for(j=2;j<=i-1;j++) { x=x+1; a[i][j]=x; } 其最内层循环体执行的次数分别是0次，1次，2次，3次，···，n−1次。2 所以该程序段的时间复杂度是O(n)。 有时，算法的时间复杂度不仅与问题的规模有关，还与输入数据有关。例如，在数组A[n]中查找给定值k的算法如下： i=n-1； while(i=0 && A[i]!=k) i=i-1； return i； 前面已说过，查找算法通常选用键值比较为基本操作，故可选条件判断“A[i]!＝k”作基本操作。当然，选语句“i=i−1”作基本操作也是可以的，结果相同。这个操作的执行次数取决于数组A中有没有值为k的元素。若有，这个值为k的元素又在数组中哪个位置；显然，若数组中无值为k的元素，则操作“A[i]!=k”的执行次数为n；若A[n-1]等于k，则该操作的执行次数为1。所以，该算法在最坏情况下的时间复杂度为O(n)，最好情况下的时间复杂度是O(1)。因此，有时我们会对算法的平均（或称期望）时间复杂度感兴趣。所谓平均时间复杂度，是指所有可能的输入数据在等概率出现的情况下算法的平均执行时间。当算法的平均时间复杂度难以确定时，就以算法的最坏时间复杂度作为算法的时间复杂度，因为它是算法执行时间的一个上界，保证了算法的执行时间不会比它更长。 有些算法的时间复杂度需要分析和计算，特别是一些递归算法。【例1.5】有如下递归算法fact(n)，分析其时间复杂度。 fact(int n) {if(n<=1)return(1); (1) else return(n*fact(n-1)); (2) } 设fact(n)的运行时间复杂度函数是T(n)，该函数中语句（1）的运行时间是O(1)，语句（2）的运行时间是T(n−1)+O(1)，其中O(1)为基本运行时间，因此： 如果n≤1 T(n)=O(1) 如果n1 T(n)=T(n−1)+O(1) 则 T(n)=T(n-1)+O(1)=T(n−2)+2*O(1)=T(n−3)+3*O(1)=… =T(1)+(n−1)*O(1)=n*O(1)=O(n) 即fact(n)的时间复杂度为O(n)。 类似于算法的时间复杂度，本书以空间复杂度（Space Complexity）作为算法所需存储空间的量度，记作S(n)=O(f(n))。 其中，n为问题的规模。请注意，这里所说的算法所需的存储空间，通常不含输入数据和程序本身所占的存储空间，而是指算法对输入数据进行运算所需的辅助工作单元和存储为实现计算所需信息的辅助空间。这类空间也称额外空间。算法的输入数据所占的空间是由具体问题决定的，一般不会因算法不同而改变。算法本身占用的空间不仅和算法有关，而且和编译程序产生的目标代码的质量有关，所以也难以讨论。算法所占的额外空间却与算法的质量密切相关，好的算法既节省时间又节省额外空间。有时，算法的输入数据所占的空间不是由问题本身决定的，而是由算法决定的。在这种情况下，算法所需的存储空间应包括输入数据的存储空间。 空间复杂度的度量和时间复杂度的度量一样，这里就不再赘述。 在大多数算法设计中，时间效率和空间效率很难兼得，设计者往往要根据具体问题进行取舍，有时会用更多的存储空间来换取时间，有时也会浪费时间来获取较少的存储空间。【例1.6】若矩阵A中存在某个元素a满足：a是第i行中最小值m×nijij且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写算法找出A中的所有鞍点。 方法一 基本思路：用枚举法，对矩阵中的每一个元素 a进行判ij别。若 a是第 i 行的最小数，则继续判别，看它是否也是第j列的最ij大数，如果成立则是鞍点。当a不是第i行的最小数或者不是第j列的ij最大数，则选择下一个元素继续。显然，矩阵A用一个二维数组表示，算法如下。 void saddle(int A[][n],int m,int n) //求m行n列矩阵的鞍点，smin为true时 { //表示A[i][j]是第i行最小数，smax为true时表示A[i][j]是第j列的最大数 int i,j,k,smin,smax; for(i=0;i for(j=0;j { k=0； smin=true; //可定义true为1，false为0 while (k if(A[i][k]= A[i][j])k++; else smin=false; if(smin) { k=0; smax = true; while (k if (A[k][j]<=A[i][j]) k++; else smax = false; } if (smin && smax) cout<< "A["< } } 时间效率分析： 双重循环体内有两个并列的 while 循环语言。第一个 while 循环执行 O(N)次，第二个 while循环最多执行O(M)次。所以总的时间效率应该是O(M×N×(M+N))。 空间效率： 除矩阵A用二维数组存储外，还用了几个辅加空间作为中间变量，所以空间效率为O(1)。 方法二 第一种方法采用枚举法，时间效率较差，能否设计一个时间效率较优的算法呢?可以通过增加辅助空间来提高时间效率，具体方法如下：先将矩阵每行每列的最小数和最大数求出来，并存放在B[n]和C[m]两个一维数组中，如图1.3所示。图1.3 增加两个辅助向量 然后对B[n]和C[m]的每对元素进行比较，假定B[j]和C[i]相等（见图1.4），则A[i][j]一定是鞍点。图1.4 鞍点示意图 可以证明如下： 因为C[i]是第i行的最小数， 所以A[i][j]≥C[i]。 又因为B[j]是第j列的最大数， 所以A[i][j]≤B[j]。 根据B[j]和C[i]相等，得出A[i][j]==B[j]==C[i]， 即A[i][j]既是第i行的最小数，又是第j列的最大数。具体算法如下。 void Saddle(int A[][n],int m,int n) {int i,j,k; int B [n],C[m]; //求每行的最小数 for(i=o;i C[i]=A[i,o]; for(j=1;j if C[i]A[i,j] C[i]=A[i,j] } //求每列的最大数 for(j = 0;j B[j] = A[o,j]; for(i = 1;i if B[j] } //求所有鞍点 for(i = 0;i for(j = 0;j if(C[i] = =B[j] cout<< "A["< } 时间效率分析： 本算法共有3小段并列的函数。 求每行的最小数 O(M×N) 求每列的最大数 O(M×N) 求所有鞍点 O(M×N) 所以总的时间效率 O(M×N) 显然空间效率为： O(M+N) 结论：比较这两种算法，第一种节省存储空间，但时间效率差；第二种算法正好相反。这是典型的空间换时间算法实例之一。 本章小结 数据类型有两种，即原子类型（如整型、字符型、实型、布尔型等）和结构类型。原子类型不可再分解，结构类型由原子类型或结构类型组成。 数据元素是数据的一个基本单位，通常由若干个数据项组成。 数据项是具有独立含义的最小标识单位，有时也称域或字段。其数据可以是一个原子类型，也可以是结构类型。 数据结构研究的是数据的表示和数据之间的关系。从逻辑上讲，数据结构有集合类型、线性结构、树结构和图4种。从物理实现上讲，数据有顺序结构、链式结构、索引结构和散列结构4种。理论上，任意一种数据逻辑结构都可以用任何一种存储结构来实现。 在集合结构中，不考虑数据之间的任何关系，它们处于无序的、各自独立的状态。在线性结构中，数据之间是1对1的关系。在树结构中，数据之间是1对多的关系。在图结构中，数据之间是多对多的关系。 算法的评价指标主要为正确性、健壮性、可读性和时空效率4方面。 习题 一、选择题 1．算法的计算量的大小称为计算的（ ）。 A．效率 B．复杂性 C．现实性 D．难度 2．算法的时间复杂度取决于（ ）。 A．问题的规模 B．待处理数据的初态 C．A和B 3．一个算法应该是（ ）。 A．程序 B．问题求解步骤的描述 C．要满足5个基本特性 D．A和C 4．下面关于算法说法错误的是（ ）。 A．算法最终必须由计算机程序实现 B．为解决某问题的算法与为该问题编写的程序含义是相同的 C．算法的可行性是指指令不能有二义性 D．以上选项都是错误的 5．从逻辑上可以把数据结构分为（ ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 6．程序段 FOR(i=n-1;i=0;i--) FOR(j=1;j<=n;j++) IF A[j]A[j+1] A[j]与A[j+1]对换; 其中，n为正整数，则最后一行的语句频度在最坏情况下是（ ）。 A．O(n) B．O(nlogn)3 C．O(n)2 D．O(n) 二、填空题 1．数据结构主要包含______、______和运算3个方面的内容。 2．对于给定的n个元素，可以构造出的逻辑结构有______、______、______、______4种。 3．沃斯（N.Wirth）教授曾以“______+______=程序”作为他的一本著作的名称。 4．评价算法优劣的4个指标是______、______、______、______。 5．一个算法具有 5 个特性：______、______、______、有零个或多个输入、有一个或多个输出。 三、判断题 1．数据元素是数据的最小单位。（ ） 2．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ） 3．算法的优劣与算法描述语言无关，但与所用计算机有关。（ ） 4．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ） 5．算法可以用不同的语言描述，如果用C语言或Pascal语言等高级语言来描述，则算法实际上就是程序了。（ ） 6．程序一定是算法。（ ） 7．数据结构的抽象操作的定义与具体实现有关。（ ） 四、应用题 1．数据结构是一门研究什么内容的学科？ 2．试举一个数据结构的例子，叙述其逻辑结构、存储结构和运算三方面的内容。 3．数据类型和抽象数据类型是如何定义的？二者有何相同和不同之处？抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？ 4．评价一个好的算法，你是从哪几方面来考虑的？ 5．解释下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构、算法、算法的时间复杂度、算法的空间复杂度。 6．设n为正整数，用大“O”记号，将下列程序段的执行时间表示为n的函数。（1）int sum1(int n) { int p=1,s=0; for(int i=1;i<=n;i++){ p*=I; s+=p; } return s; }（2）int sum2(int n) { int s=0; for(int i=1;i<=n;i++){ int p=1; for(int j=1;j<=i;j++) { p*=j; s+=p; } } return s; }（3）int fun(int n) { int i=1,s=1; while(s s+=++i; return i; } 第2章 C++程序设计基础知识 教学提示：C语言是面向过程的语言，因此用C语言编写的程序必然包含一组函数以及这些函数所处理的数据。由于C语言没有提供数据抽象及封装功能，函数与数据分散在程序的不同地方，因此程序中很难分清哪些函数处理了哪些数据。此外，C语言在数据授权访问、函数重载、继承、多态等方面也无能为力，使得程序结构容易变得十分复杂，且难以维护。 作为C语言的超集，C++提供了数据的封装与抽象功能，为程序员提供了定义新的数据类型的简单而强大的工具。新的数据类型中既包含数据内容，又包含对数据内容的操作。把它封装起来以后，数据类型本身能控制外界对它的数据成员的访问。C++本身的功能十分强大而复杂。作为“数据结构”教材的一部分，本章将介绍一些必要的且适用的C++基础知识。 教学目标：熟练掌握C++的输入/输出方法、函数的引用参数传递；熟练掌握类的定义、类与对象的关系、类与对象的使用；熟悉构造函数、析构函数的定义及其含义；熟练掌握动态内存分配、指向对象的指针、对象数组、指向对象的指针数组；掌握简单的类继承方法，并理解虚函数的概念。 2.1 C++的基本操作 C++是在C语言的基础上为支持面向对象程序设计而研制的一种编程语言。C++包含C语言的全部特征和优点，同时添加了对面向对象编程（Object Oriented Programming，OOP）的完全支持。在C语言中所学的知识对C++是完全适用的。本节重点就不同于C语言的C++新特性进行描述。 2.1.1 C++的基本输入与输出 C++中的基本输入/输出仍然可以用C语言中的相关函数，如printf，scanf，puts，gets等。但在使用这些函数前必须先包含头文件stdio.h，即要在程序中加上#include 在C++中，数据输入和输出还可以分别使用系统所提供的输入流对象cin和输出流对象cout来完成。在使用前，程序的开头应加上#include 1．数据输出cout 使用cout输出数据的语句格式是： cout<<表达式1<<表达式2<<……<<表达式n;
试读结束[说明：试读内容隐藏了图片]