数据结构概论.docx

1、21 世纪高职高专规划教材计算机系列数据结构概论尹绍宏董卿霞苑春苗编著清华大学出版社 北京交通大学出版社北京内 容 简 介本书详细地介绍了各种类型的数据结构，以及查找和排序的方法。对每一种数据结构，主要讲述其基本 概念，各种存储结构，以及不同存储结构下的各种操作的实现，并用 C 语言对其算法进行实现。对查找和排 序的各种不同方法除讲述其方法外，还给出了用 C 语言实现的算法程序，并对不同的算法给出了定性的分析 和比较。本书既注重理论又注重实践，并配有大量的习题和实习题，内容丰富、概念清楚、通俗易懂，既可用于 教学，又便于读者自学。本书可以作为大专院校计算机应用及相关专业的教材，也可以供从事计算

2、机技术与应用工作的科技人员 使用。版权所有，翻印必究。 本书封面贴有清华大学出版社激光防伪标签，无标签者不得销售。图书在版编目（CIP）数据数据结构概论 / 尹绍宏，董卿霞，苑春苗编著北京 ：清华大学出版社；北京交通 大学出版社，2004.5（21 世纪高职高专规划教材计算机系列）ISBN 7-81082-289-6数尹董苑数据结构高等学校：技术学校教材 TP311.12中国版本图书馆 CIP 数据核字（2004）第 018557 号责任编辑：韩 乐特邀编辑：朱 宇出 版 者：清 华 大 学出 版社邮编：100084电话：010-62776969 北京交通大学出版社邮编：100044电话：01

3、0-51686045，62237564印 刷 者：北京瑞达方舟印务有限公司 发 行 者：新华书店总店北京发行所开本：185260 印张：15字数：374 千字版次：2004 年 5 月第 1 版2004 年 5 月第 1 次印刷书号：ISBN 7-81082-289-6 / TP110印数：00015000 册定价：21.00 元出 版 说 明高职高专教育是我国高等教育的重要组成部分，它的根本任务是培养生产、建设、管理 和服务第一线需要的德、智、体、美全面发展的高等技术应用型专门人才，所培养的学生在 掌握必要的基础理论和专业知识的基础上，应重点掌握从事本专业领域实际工作的基本知识 和职业技能，

4、因而与其对应的教材也必须有自己的体系和特色。为了适应我国高职高专教育发展及其对教学改革和教材建设的需要，在教育部的指导下， 我们在全国范围内组织并成立了“21 世纪高职高专教育教材研究与编审委员会”（以下简称 “教材研究与编审委员会”）。“教材研究与编审委员会”的成员单位皆为教学改革成效较 大、办学特色鲜明、办学实力强的高等专科学校、高等职业学校、成人高等学校及高等院校 主办的二级职业技术学院，其中一些学校是国家重点建设的示范性职业技术学院。为了保证规划教材的出版质量，“教材研究与编审委员会”在全国范围内选聘“21 世纪 高职高专规划教材编审委员会”（以下简称“教材编审委员会”）成员和征集教材

5、，并要求 “教材编审委员会”成员和规划教材的编著者必须是从事高职高专教学第一线的优秀教师或 生产第一线的专家。“教材编审委员会”组织各专业的专家、教授对所征集的教材进行评选， 对列选教材进行审定。目前，“教材研究与编审委员会”计划用 23 年的时间出版各类高职高专教材 200 种， 范围覆盖计算机应用、电子电气、财会与管理、商务英语等专业的主要课程。此次规划教材 全部按教育部制定的“高职高专教育基础课程教学基本要求”编写，其中部分教材是教育部新世纪高职高专教育人才培养模式和教学内容体系改革与建设项目计划的研究成果。此 次规划教材编写按照突出应用性、实践性和针对性的原则编写并重组系列课程教材结构

6、，力 求反映高职高专课程和教学内容体系改革方向；反映当前教学的新内容，突出基础理论知识 的应用和实践技能的培养；适应“实践的要求和岗位的需要”，不依照“学科”体系，即贴 近岗位群，淡化学科；在兼顾理论和实践内容的同时，避免“全”而“深”的面面俱到，基 础理论以应用为目的，以必要、够用为度；尽量体现新知识、新技术、新工艺、新方法，以 利于学生综合素质的形成和科学思维方式与创新能力的培养。此外，为了使规划教材更具广泛性、科学性、先进性和代表性，我们希望全国从事高职 高专教育的院校能够积极加入到“教材研究与编审委员会”中来，推荐“教材编审委员会” 成员和有特色、有创新的教材。同时，希望将教学实践中的

7、意见与建议及时反馈给我们，以 便对已出版的教材不断修订、完善，不断提高教材质量，完善教材体系，为社会奉献更多更 新的与高职高专教育配套的高质量教材。此次所有规划教材由全国重点大学出版社清华大学出版社与北京交通大学出版社联 合出版。适合于各类高等专科学校、高等职业学校、成人高等学校及高等院校主办的二级职 业技术学院使用。21 世纪高职高专教育教材研究与编审委员会2004 年 3 月前言随着计算机技术的不断发展，计算机在各个领域都得到了广泛的应用。但在应用过程中， 都会涉及数据的组织与程序的编写等问题，都会用到各种各样的数据结构，特别是对非数值 型数据的表示，各种操作算法的实现，都离不开数据结构课

8、程的内容。因此，数据结构一直 是各高等院校计算机专业教学内容中的一门主要的专业基础课程。本书是在作者多年教学经验的基础上编写而成的。在编写过程中，从内容和结构入手， 进行了精心的设计。在内容选择方面，全面地反映了数据结构各个方面的内容，突出了概念、 方法和应用，既注重基本原理的介绍，又注重实践能力的培养；在结构的安排方面，以逻辑 结构为主要线索，对每一种数据结构都是按照基本概念和定义，顺序存储结构的表示及各基 本操作的实现和链式存储结构的表示及各基本操作的实现，以及应用这几个方面详细地进行 介绍。这样便于对各种结构的学习，掌握各种结构的特点及它们之间的关系。书中还配有大 量的例题、习题和实习题

9、供学生练习，以加深对各知识点的理解。书中的算法全部采用 C 语 言描述，所给出的程序均已在计算机上运行通过，并给出了程序的运行结果，以便读者了解 算法的实质和基本思想。全书分为 10 章，第 1 章介绍了数据、数据结构、抽象数据类型及算法的概念和性能分析等基本概念；第 2 章至第 6 章主要讨论了各种线性结构及其应用，包括线性表、栈、队列、串、二维数组和广义表；第 7 章和第 8 章讨论了非线性结构及其应用，重点讨论了树和二叉 树、图的基本概念及其应用；第 9 章讨论了各种内部排序的方法，以及每种排序方法的性能、 特点和适用场合；第 10 章讨论了不同存储结构下的各种查找方法及不同查找方法的性

10、能分析。 在每一章的后面都附有习题和实习题，可以检验读者的学习效果，培养程序设计能力。王炜、杨清永、高海明、王宇鑫、苏丽华、赵金英、黎剑兵等也参加了程序的调试及部 分文档的整理工作。由于作者水平有限，书中难免会有错漏和疏忽，殷切希望广大读者予以批评指正。编者2004 年 4 月21 世纪高职高专规划教材计算机系列 编审委员会成员名单主 任 委 员李兰友边奠英副主任委员周学毛崔世钢王学彬丁桂芝赵伟 韩瑞功汪志达委员 （按姓名笔画排序）马 辉 万志平 万振凯 王永平 王建明 尤晓 丰继林 尹绍宏 左文忠 叶 华 叶 伟 付晓光 付慧生 冯平安 江 中 佟立本 刘 炜 刘建民 刘 晶 曲建民 孙培民

11、 邢素萍 华铨平 吕新平 陈小东 陈月波 李长明 李 可 李志奎 李 琳 李源生 李群明 李静东 邱希春 沈才梁 宋维堂 汪 繁 张文明 张权范 张宝忠 张家超 张 琦 金忠伟 林长春 林文信 罗春红 苗长云 竺士蒙 周智仁 孟德欣 柏万里 宫国顺 柳 炜 钮 静 胡敬佩 姚 策 赵英杰 高福成 贾建军 徐建俊 殷兆麟 唐 健 黄 斌 章春军 曹豫莪 程 琪 韩广峰 韩其睿 韩 劼 裘旭光 童爱红 谢 婷 曾瑶辉 管致锦 熊锡义 潘玫玫 薛永三 操静涛 鞠洪尧目录第 1 章绪论11.1基本概念和术语11.2发展历程41.3算法和算法描述51.3.1 概念和特性51.3.2 算法设计要求51.3

12、.3 算法描述61.4算法的性能分析71.4.1 时间复杂度71.4.2 空间复杂度9小结9习题9实习10第 2 章线性表112.1概念和定义112.1.1 概念112.1.2 定义122.2顺序存储结构122.2.1 顺序表的存储表示132.2.2 顺序表的基本操作的实现132.3链式存储结构172.3.1 单链表的存储表示172.3.2 单链表基本操作的实现182.3.3 循环链表的表示和基本操作的实现222.3.4 双向链表的表示和基本操作的实现222.4应用举例242.4.1 顺序表242.4.2 单链表26小结28习题29实习31第 3 章栈323.1概念和定义32I3.2顺序存储表

13、示333.2.1 顺序栈的存储表示333.2.2 顺序栈基本操作的实现343.3链式存储结构363.3.1 链栈的存储表示363.3.2 链栈基本操作的实现363.4应用举例38小结42习题42实习44第 4 章队列454.1概念和定义454.2顺序存储结构464.2.1 顺序队列的存储表示464.2.2 顺序队列基本操作的实现464.2.3 循环队列494.3链式存储结构504.3.1 链队列的存储表示504.3.2 链队列基本操作的实现514.4应用举例53小结54习题55实习56第 5 章串575.1概念和定义575.2顺序存储结构595.2.1 定长顺序串的存储表示及操作的实现595.

14、2.2 堆存储表示及操作的实现615.3块链存储表示655.4应用举例65小结67习题67实习68第 6 章二维数组和广义表696.1二维数组概念和定义696.2二维数组的顺序存储结构706.3矩阵的压缩存储706.3.1 概念716.3.2 特殊矩阵的压缩存储71II6.3.3 稀疏矩阵的顺序存储表示和基本操作的实现726.3.4 稀疏矩阵的链式存储表示和基本操作的实现796.4广义表的概念和定义826.5广义表的操作和链式存储结构82小结85习题86实习88第 7 章树与二叉树897.1树的概念897.1.1 定义897.1.2 表示方法907.1.3 基本概念和常用术语917.2二叉树9

15、27.2.1 概念和定义927.2.2 性质937.2.3 存储结构947.2.4 遍历957.2.5 二叉树的线索化997.3树和森林1047.3.1 树的存储结构1047.3.2 树和森林的遍历1067.3.3 树、森林与二叉树的转换1077.4哈夫曼树1087.4.1 概念和定义1087.4.2 哈夫曼树的构造1097.4.3 哈夫曼编码的实现112小结115习题115实习116第 8 章图1188.1图的概念1188.1.1 定义1188.1.2 基本概念和常用术语1198.2存储结构1208.2.1 邻接矩阵表示及各操作的实现1218.2.2 邻接表的表示及各操作的实现1258.3图

16、的遍历1318.3.1 深度优先搜索1318.3.2 广度优先搜索134III8.4生成树和最小生成树1358.4.1 生成树的概念和分类1358.4.2 最小生成树的概念和实现方法1368.5AOV 网及其应用1438.5.1 概念1438.5.2 拓扑排序1438.6AOE 网及其应用1488.6.1 概念1488.6.2 关键路径1488.7最短路径1558.7.1 任意源点到其余各点的最短路径1558.7.2 任意两点间的最短路径159小结160习题160实习162第 9 章排序1639.1概念及分类1639.2插入排序1649.2.1 直接插入排序1649.2.2 折半插入排序167

17、9.2.3 2-路插入排序1699.2.4 希尔排序1709.3交换排序1729.3.1 冒泡排序1739.3.2 快速排序1759.4选择排序1789.4.1 简单选择排序1789.4.2 树型选择排序1819.4.3 堆排序1829.5K-路归并排序1869.6基数排序1909.7内部排序方法的比较1919.7.1 时间性能1929.7.2 空间性能1929.7.3 稳定性1929.7.4 排序方法的选择193小结193习题194实习195IV第 10 章查找19610.1概念19610.2顺序存储结构查找19810.2.1 顺序查找19810.2.2 折半查找20010.2.3 分块查找

18、20310.3树存储结构查找20610.3.1 二叉排序树20610.3.2 B-树21010.4哈希表查找21210.4.1 基本概念21310.4.2 哈希函数的构造方法21310.4.3 解决冲突的方法21510.4.4 查找方法218小结221习题221实习222习题答案223参考文献225V第 1 章绪论本章要点：回 数据结构的基本概念和术语回 数据结构的发展过程及其所处地位回 算法和算法的描述回 算法的性能分析1.1基本概念和术语数据结构是计算机专业的专业基础课之一，是一门十分重要的核心课程。计算机的所 有系统软件和应用软件都需要用到各种类型的数据结构。要想编写出一个好的程序，仅仅

19、 学习计算机语言是不够的，必须扎实地掌握数据结构的基本知识和基本技能。同时，它也 是学习计算机专业其他课程，如操作系统、数据库原理与应用和软件工程等所必需的基础 知识。掌握好数据结构方面的知识，对于增强我们解决实际问题的能力将会有很大帮助。事实 上，一个好的程序无非是选择了一个合理的数据结构和一个好的算法，而好的算法的选择在 很大程度上取决于描述实际问题的数据结构。所以，学好数据结构课程是进一步提高程序设 计水平的关键之一。随着计算机应用领域的不断扩大，非数值计算问题已跃居主导地位，简单的数据类型已 远远不能满足需要，各数据元素之间的复杂联系不再是普通数学方程式所能表达的了。因此 简单地说，数

20、据结构就是研究非数值计算的程序设计问题中，计算机的操作对象，以及它们 之间的关系和操作等的学科。下面将对一些在以后章节中使用的基本概念和术语加以定义和 解释。1数据数据是人们利用文字符号、数字符号及其他规定的符号，对现实世界的事物及其活动所做的抽象描述。例如，文字、数字和符号都是数据。 2数据元素数据元素是数据的基本单位。例如，学生是一个数据元素。有些时候，一个数据元素可 以由若干个数据项组成，数据项是具有独立含义的数据最小单位，称为字段或域。例如，作 为数据元素的学生由学号、姓名、性别和班级等数据项组成。3数据对象数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集第

21、 1 章 绪论9合0，1，2，字符数据对象是集合A，B，Z。4数据结构数据结构是指数据及其相互之间的联系，可以看做是相互间存在一种或多种特定关系的 数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样 或那样的关系，这种数据元素之间的关系称为结构。根据数据元素间的不同特性关系，通常 有下面 4 类基本结构。（1）集合结构 集合结构的数据元素之间的关系是“属于同一个集合”，它是元素间关系最为松散的一种结构。如图 1-1(a)所示。（2）线性结构 线性结构的数据元素之间存在一对一的关系，如图 1-1(b)所示。（3）树型结构 树型结构的数据元素之间存在一对多的关系，如图

22、 1-1(c)所示。（4）图状结构 图状结构的数据元素之间存在多对多的关系，图状结构又称网状结构，如图 1-1(d)所示。图 1-1 基本数据结构图5数据类型数据类型是与数据结构密切相关的一个概念，容易引起混淆。数据类型最早出现在高级 语言中，是对数据的取值范围，每一数据的结构，以及允许执行的操作的一种描述，它刻画 了程序中操作对象的特性。每一种程序语言都定义有自己的数据类型，在用程序语言编写的 程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。所谓数据类型，是一 个值的集合，以及在这些值上定义的一组操作的总称。数据类型可以分为简单类型和结构类型两种。简单类型中的每个数据（即简单数

23、据）都 是无法再分割的整体，如一个整数、实数、字符、指针、枚举量等都是无法再分割的整体， 所以它们所属的类型均为简单类型。结构类型由简单类型按照一定的规则构造而成，并且结 构类型中可以包含结构类型，所以一种结构类型中的数据（即结构数据）可以分解为若干个 简单数据或结构数据，每个结构数据仍可再分。例如，C 语言中的数组是一种结构类型，它是由固定个数的同一类型的数据顺序排列而成。结构体也是一种结构类型，它是由固定个数 的不同类型的数据顺序排列而成。数据类型也可以被定义为一种数据结构和能够对该数据结构进行的操作的集合。对于简 单类型，其数据结构就是相应取值范围内的所有数据，每一个数据值是不可分的独立

24、整体， 因而数据值内部也就无结构可言。对于结构类型，其数据结构就是相应元素的集合。6抽象数据类型抽象数据类型（Abstract Data Type，ADT）是指一个数学模型，以及定义在该模型上的 一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部的表示方 式及实现无关，即它独立于具体实现。一个 ADT 定义可描述为ADT抽象数据类型名数据对象：数据对象的定义/* 对数据元素的说明*/ 数据关系：数据关系的定义/* 对数据元素之间逻辑关系的描述*/ 基本操作：基本操作的定义/* 对该抽象数据类型允许进行的操作的描述*/操作 1/* 对本操作的初始条件、参数的类型、操作的功能

25、 和操作结果的描述*/ 操作 2 ADT 抽象数据类型名 抽象数据类型可以看做是描述问题的模型，其优点是将数据和操作封装在一起，使用户程序只能通过在 ADT 里定义的某些操作来访问其中的数据，从而实现了信息隐蔽。 数据结构包括数据的逻辑结构和物理结构。数据的逻辑结构可以看做是从具体问题中抽象出来的数学模型，与数据的存储无关，是独立于计算机的。数据元素之间的逻辑关系称为 数据的逻辑结构。我们研究数据结构的目的是为了在计算机中实现对它的操作，为此还需要 研究如何在计算机中表示一个数据结构。数据结构在计算机中的表示称为数据的物理结构， 又称为数据的存储结构。它研究的是数据结构在计算机中的实现方法，包

26、括数据元素及其关 系在计算机中的表示。数据的逻辑结构有线性结构和非线性结构两大类。线性结构的逻辑特征是，若结构是非空集，则有且只有一个开始结点和一个终端结点， 并且除第一个结点之外，每个结点都有且只有一个直接前驱，除最后一个结点之外，每个结 点都有且只有一个直接后继。线性表就是典型的线性结构。非线性结构的逻辑特征是，一个结点可能有多个直接前驱和多个直接后继。树和图的结 构就是典型的非线性结构。数据的存储结构可以采用顺序存储、链式存储、索引存储和散列存储 4 种方法。顺序存储方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点间的逻 辑关系由存储单元的邻接关系来体现。由此得到的存储表示

27、称为顺序存储结构。顺序存储结 构一般借助于程序设计语言的数组来描述。链式存储方法不要求逻辑上相邻的结点在物理位置上亦相邻，其结点间的逻辑关系是由 附加的指针域表示的。由此得到的存储表示称为链式存储结构。链式存储结构一般借助于程 序设计语言的指针类型来描述。索引存储方法通常是在存储结点信息的同时建立一个索引表，索引表中的每一项称为索 引项，它一般包括关键字和地址两项内容，关键字是唯一能标识一个结点的数据项。建立索 引表时，可以是每个结点在索引表中都有一个索引项，也可以是一组结点在索引表中只对应 于一个索引项。索引存储方法便于检索操作。散列存储方法的基本思想是根据结点的关键字直接计算出该结点的存储

28、地址。上述 4 种基本的存储方法，既可以单独使用，也可以混合起来对数据进行存储使用。 对于同一种逻辑结构，采用不同的存储方法，可以得到不同的存储结构，应根据具体要求 而定。1.2 发展历程数据结构作为一门独立的课程是从 1968 年才开始设立的。在此之前，它的某些内容曾在 其他课程中有所阐述。1968 年，在美国一些大学的计算机系的教学计划中，虽然把数据结构 规定为一门课程，但对课程的范围仍没有明确的规定。当时，数据结构几乎与图论，特别是 与表、树的理论为同义语。随后，数据结构的概念被扩充到包括网络、集合代数论、关系等 方面，从而变成了现在称之为离散结构的内容。由于数据必须在计算机中进行处理，

29、因此， 不仅需要考虑数据本身的数学性质，而且还必须考虑数据的存储结构，这就进一步扩大了数 据结构的内容。近年来，随着数据库系统的不断发展，在数据结构课程中又增加了文件管理（特别是大型文件的组织等）的内容。1968 年，美国唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从 20 世纪 60年代末到 70 年代初，出现了大型程序，软件也相对独立，结构化程序设计成为程序设计方法 学的主要内容，人们就越来越重视数据结构，认为程序设计的实质是对确定的问题选择一种 好的结构，再加上设计一种好的算法。从 70 年代中期到 80

30、年代初，各种版本的数据结构著 作相继出现。目前在我国，数据结构也已经不仅仅是计算机专业的教学计划中的核心课程之一，而是 其他非计算机专业的主要选修课程之一。数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及计算 机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且与计算机软件的研 究有着更密切的关系，无论是编译原理还是操作系统，都涉及数据元素在存储器中的分配 问题。在研究信息检索时也必须考虑如何组织数据，以便数据元素更为方便地查找和存取。 因此，可以认为数据结构是介于数学、计算机硬件和计算机软件之间的一门核心课程。在 计算机科学中，数据结构不仅是一般程序设计（特别

31、是非数值计算的程序设计）的基础， 而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重 要基础。今后，数据结构还将继续发展，一方面，向各专门领域中特殊问题的数据结构的研究方 向发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点讨论数据结构，这一发 展方向已成为新的趋势，越来越为人们所重视。1.3算法和算法描述计算机软件的最终结果都是以程序形式表现的，数据结构的各种操作都是以算法形式描 述的。数据结构、算法和程序是密不可分的，它们之间的关系可以表示为数据结构 + 算法 = 程序1.3.1 概念和特性数据元素之间具有逻辑关系和物理关系。与此对应，有逻辑结构上的操作

32、功能和具体存储结构上的操作实现。我们把具体存储结构上的操作实现方法称为算法。确切地说，算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条 指令表示计算机的一个或多个操作。一个算法具有以下 5 个重要特性。 有穷性。一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可以在有穷时间内完成。 确定性。算法中的每一条指令都必须具有确切的含义，不会产生二义性。 可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。 输入。一个算法有零个或多个输入。这些输入取自于某个选定的对象的集合。 输出。一个算法有一个或多个输出。这些输出是与输入有某些特定关系的量。

33、没有输出的算法是没有意义的。 算法与程序不同，程序可以不满足上述的有穷特性。例如，一个操作系统（如 DOS 或Windows）在用户未操作之前一直处于“等待”的循环中，直到出现新的用户操作为止。但 一般的程序则不能出现这种情况。另外，程序中的指令必须是机器可执行的，而算法中的指 令则无此限制。算法代表了对问题的解，程序则是算法在计算机上特定的实现。一个算法若 用程序设计语言来描述，它就是一个程序。在计算机科学的研究中，算法与数据结构是相辅相成的。解决某一特定类型问题的算法可以选定不同的数据结构，而选择是否恰当将直接影响算法的效率。1.3.2 算法设计要求算法与数据结构的优劣直接相关。设计一个好

34、的算法通常需要满足以下要求。 1正确性 一个正确的算法是指在合法的数据输入下，要求算法能在有限的运行时间内得出正确的结果。这是最重要也是最基本的准则。2可使用性 要求算法能够很方便地使用。该特性称为用户友好性。 3可读性算法最主要的目的是阅读与交流，并将它转换成可实现的程序在计算机中执行。算法应 当是可读的，即可读性好。在保证算法正确的前提下，应该强调算法的可读性。为了达到这 个要求，算法的逻辑必须是清晰的、简单的和结构化的。4健壮性要求算法具有很好的容错性，即能够对错误的情况进行处理，对不合理的数据进行检查，并做出适当的反应或进行处理，不会经常出现异常中断或死机现象。5效率算法的效率主要指算

35、法执行时计算机资源的消耗，包括存储单元和运行时间的开销。前 者称为算法的空间复杂度，后者称为算法的时间复杂度。对于同一个问题，在相同的数据规 模下，如果有多个算法可以使用，则执行时间短的算法效率最高，所需存储空间少的算法较 好。通常，两者是矛盾的一对，节约算法的执行时间，往往以牺牲更多的空间作为代价；而 为了节省空间可能需要耗费更多的计算时间，因此我们只能根据具体情况有所侧重。若程序 使用较少，则力求算法简单易懂；对于需要反复多次使用的程序，应尽可能选用快速的算法； 若所求问题的数据量较大，机器的存储空间又较小，则在设计算法时应主要考虑如何节省空 间。1.3.3算法描述算法的描述有多种方式，可

36、以用自然语言、计算机程序语言或其他语言来说明，但要求 该说明必须能够精确地描述计算过程。一般地，描述算法最恰当的语言是介于自然语言和程 序语言之间的伪语言，它的控制结构比较容易理解和表达。在这里，考虑到易于上机验证算 法和提高读者的实际程序设计能力，本书中我们采用 C 语言描述算法。C 语言是一种高效、 灵活和精炼的高级程序设计语言，优点是类型丰富、语句简捷，编写的程序结构化程度高、 可读性强。常用的用于描述算法的 C 语言语句如下。（1）输入语句scanf(,)；（2）输出语句printf(,)；（3）赋值语句变量名 = 表达式；（4）条件语句if()；或者if() else ；（5）循环语

37、句while()；或者do；while()；或者for(；) ；（6）返回语句return()；（7）定义函数语句(,)；（8）调用函数语句(,)；1.4算法的性能分析在一个算法设计好之后，还需要对其进行分析，以确定该算法的优劣。一个算法的质量 优劣将直接影响到算法乃至程序的效率。算法性能分析的目的在于尽可能地选择一个合适的 算法。对一个算法进行评价的性能指标主要是算法的时间复杂度和空间复杂度。1.4.1时间复杂度时间复杂度又称计算复杂度，是一个算法运行时间的相对量度。算法的运行时间是指在 计算机上从开始到结束运行所花费的时间，应该是算法中每条语句的执行时间之和。而每条 语句的执行时间是该语句

38、的执行次数（也称为频度）与该语句执行一次所需时间的乘积。因 为每条语句执行一次所需时间取决于机器本身的硬件和软件环境，与算法无关，所以我们假 设每条语句执行一次所需的时间都是单位时间。这样，一个算法的时间耗费就是该算法中所 有语句的频度之和。显然，在一个算法中，进行基本操作的总的次数越少，其运行时间也就相对地越少；次 数越多，其运行时间也就相对地越多。所以，通常用算法中所包含的简单操作次数来描述算 法的时间复杂度，以此衡量一个算法的运行时间性能。一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数，用 T(n)表示。 若有某个辅助函数 f(n)，使得当 n 趋近于无穷大时，T(n

39、)/f(n)的极限值为不等于零的常数，则 称 f(n)是 T(n)的同数量级函数。记作T(n) = O(f(n)称 O(f(n)为算法的渐进时间复杂度，简称时间复杂度。式中的 f(n)一般取算法中频度最大的语句频度。下面举例说明如何计算算法的时间复杂度。【例 1-1】将 a 和 b 变量的内容互换。t=a; a=b; b=t;上面 3 条语句的频度都是 1，该程序的执行时间是一个与问题规模 n 无关的常数，因此， 算法的时间复杂度为常数阶，记作 T(n)=O(1)。事实上，只要算法的执行时间不随着问题规模 n 的增加而增长，即使算法中有上千条语句，其执行时间也只不过是一个较大的常数，此时， 算

40、法的时间复杂度也是 O(1)。【例 1-2】求 1n 所有自然数的和。主要语句为 sum=0; for(i=1;i=n;i+)sum=sum+i;一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，而忽略该语句中步长 加 1、终值判断控制转移等成分。因此，上面程序段中频度最大的语句是，其频度 f(n)=n， 所以该程序段的时间复杂度为 T(n)=O(n)，称为线性阶。【例 1-3】分析下面程序段的时间复杂度。 a=0; b=0; for(i=1;i=n;i+) a+; for(j=1;j=n;j+) for(k=1;k=n;k+) b+;根据前面的分析可知，上面程序段中频度最大的语句是，

41、其频度 f(n)=n2，所以该程序 段的时间复杂度为 T(n)=O(n2)，称为平方阶。由此可见，当有若干个循环语句时，算法的时间 复杂度是由嵌套层数最多的循环语句中最内层语句的频度 f(n)决定的。【例 1-4】分析如下程序段的时间复杂度。 a=0; for(i=1;i=n;i+) for(j=1;j=i;j+) for(k=1;k=j;k+) a+;显然，上面程序段中频度最大的语句是，在程序中，内循环的执行次数虽然与问题的 规模 n 没有直接的关系，但却与外层循环变量的取值有关，而最外层循环的次数直接与 n 有 关，因此可以从内层循环向外层分析语句的执行次数，通过计算得出该程序段的时间复杂

42、 度为 T(n)=O(n3)，称为立方阶。算法的时间复杂度（用 f(n)表示）采用数量级的形式表示后，将对求一个算法的 f(n)带来很大方便。这时，只需要分析影响一个算法时间复杂度的主要部分即可，不必对每一步都进行详细分析。算法的时间复杂度按数量级递增的次序排列，依次为常数阶 O(1)，对数阶 O(lb n)，线性 阶 O(n)，线性对数阶 O(n lb n)，平方阶 O(n2)，立方阶 O(n3)，k 次方阶 O(nk)、指数阶 O(2n) 和 n 的阶乘阶 O(n!)等形式。随着问题规模 n 的不断增大，时间复杂度不断增大，算法的执行 效率不断降低，也即数量级越高，则算法的效率越低。1.4

43、.2空间复杂度与时间复杂度类似，一个算法的空间复杂度是指该算法在计算机内执行时所需存储空间 的度量。它也是问题规模 n 的函数，记作S(n) = O(f(n)一个算法在计算机存储器上所占用的存储空间应该包括：存储算法本身所占用的空间， 算法的输入、输出数据所占用的空间和算法在运行过程中临时占用的空间三个方面。存储算法本身所占用的空间与算法的长度成正比，要想减少这方面的存储空间，就必须 编写出较精炼的算法。输入、输出数据所占用的空间是由求解的问题所决定的，不随算法的 不同而改变。但算法在运行过程中临时占用的存储空间是因算法的不同而不同的。在这里， 我们一般讨论的是除正常占用内存单元以外的辅助存储单元的开销。算法的空间复杂度的计算方法与时间复杂度的计算方法类似，不再赘述。 算法的时间复杂度和空间复杂度合称为算法的复杂度。小结本章介绍了数据结构的基本概念和常用术语，数据结构的地位及作用，算法、算法的描 述及算法性能的分析。基本学习要点如下。（1）掌握数据结构的定义，数据的逻辑结构、存储结构的概念及