数据结构实用教程（第二版）

定　　价：32 元

丛书名：普通高等院校计算机专业（本科）实用教程系列

• 作者：徐孝凯
• 出版时间：2006/9/1
• ISBN：9787302133971
• 出 版 社：清华大学出版社

• 中图法分类：TP311.12 
• 纸张：胶版纸
• 版次：1
• 开本：16

内容简介

本书是为全国高等院校计算机及相关专业开设数据结构课程而精心组织和编著的一本实用教材。它从1999年出版以来，一直深受广大读者和专家的好评，相继被许多高校选定为教科书和考研参考书，并被列选为国家级“十一五”规划教材。这次对本书进行了认真和全面的修订，形成第2版，相信会得到更广泛的认可，对数据结构学科的教学和发展产生积极的影响。
本书从计算机学科发展和应用的实际需要出发，对各种常用的数据结构，从逻辑结构、存储结构、运算种类、运算方法和算法等各个方面进行了深入细致的解剖和分析，使读者更容易理解基本概念和知识，能够轻松地进行算法设计和上机操作的训练，大大提高软件开发与设计的专业能力。
另外，与本书配套的习题参考解答也一并被修订和出版，为广大自学读者提供方便。

序 言

序 言
时光更迭、历史嬗递。中国经济以她足以令世人惊叹的持续高速发展驶入了一个新的世纪，一个新的千年。世纪之初，以微电子、计算机、软件和通信技术为主导的信息技术革命给我们生存的社会所带来的变化令人目不暇接。软件是优化我国产业结构、加速传统产业改造和用信息化带动工业化的基础产业，是体现国家竞争力的战略性产业，是从事知识的提炼、总结、深化和应用的高智型产业；软件关系到国家的安全，是保证我国政治独立、文化不受侵蚀的重要因素；软件也是促进其他学科发展和提升的基础学科；软件作为20世纪人类文明进步的最伟大成果之一，代表了先进文化的前进方向。美国政府早在1992年“国家关键技术”一文中提出“美国在软件开发和应用上所处的传统领先地位是信息技术及其他重要领域竞争能力的一个关键因素”，“一个成熟的软件制造工业的发展是满足商业与国防对复杂程序日益增长的要求所必需的”，“在很多国家关键技术中，软件是关键的、起推动作用（或阻碍作用）的因素”。在1999年1月美国总统信息技术顾问委员会的报告“21世纪的信息技术”中指出“从台式计算机、电话系统到股市，我们的经济与社会越来越依赖于软件”，“软件研究为基础研究方面最优先发展的领域。”而软件人才的缺乏和激烈竞争是当前国际的共性问题。各国、各企业都对培养、引进软件人才采取了特殊政策与措施。
为了满足社会对软件人才的需要，为了让更多的人可以更快地学到实用的软件理论、技术与方法，我们编著了《普通高等院校计算机专业（本科）实用教程系列》。本套丛书面向普通高等院校学生，以培养面向21世纪计算机专业应用人才（以软件工程师为主）为 目标，以简明实用、便于自学、反映计算机技术最新发展和应用为特色，具体归纳为以下几点：
1．进透基本理论、基本原理、方法和技术，在写法上力求叙述详细，算法具体，通俗易懂，便于自学。
2．理论结合实际。计算机是一门实践性很强的科学，丛书贯彻从实践中来到实践中去的原则，许多技术理论结合实例讲解，以便于学习理解。
3．本丛书形成完整的体系，每本教材既有相对独立性，又有相互衔接和呼应，为总的培养目标服务。
4．每本教材都配以习题和实验，在各教学阶段安排课程设计或大作业，培养学生的实战能力与创新精神。习题和实验可以制作成光盘。
为了适应计算机科学技术的发展，本系列教材将本着与时俱进的精神不断修订更新，及时推出第二版、第三版……
新世纪曙光激人向上，催人奋进。江泽民同志在十五届五中全会上的讲话：“大力推进国民经济和社会信息化，是覆盖现代化建设全局的战略举措。以信息化带动工业化，发挥后发优势，实现社会生产力的跨越式发展”，指明了我国信息界前进的方向。21世纪日趋开放的国策与更加迅速发展的科技会托起祖国更加辉煌灿烂的明天。

孙家广
2004年1月
第二版前言
本书第一版出版至今已近7年，随着计算机数据结构学科的不断发展和教学的改革需要，在第一版的基础上，整理和加工形成了第二版。
第一版教材深受读者的喜爱，连续14次印刷，发行7万余册，被许多高校选定为教材和考研参考书。有许多读者在网站上发表评论，赞扬本书的风格和特色。
第二版对第一版的内容进行了优化和适当增删，并对一些章节进行了调整，由第1版中的8章修订为10章。原来的第5章“树”，改为第5章的“树和二叉树”和第6章的“特殊二叉树”两章，原来的第6章“图”，改为第7章“图”和第8章“图的应用”两章。
在第二版教材中，增加了“堆”结构的内容、集合结构的内容、线性表应用的内容、栈与队列应用的内容等；扩充了栈与递归应用的实例、二叉树和树查找运算的算法、生成哈夫曼树的算法、对B_树的插入算法等；修改了从二叉搜索树中删除结点的算法、对外存文件进行排序的算法等。当然还对许多内容进行了修改，力争反映该学科的先进性和科学性，反映作为教材的系统性、实用性和可读性。
第2版的内容较丰富，在目录、例题或习题中带星号“*”的内容可以不作为讲授内容和教学要求，留给学生自学。
书中所有算法和程序都在Visual C++ 6.0开发环境下调试运行通过，使得其正确性和有效性得到了进一步验证。
数据结构教材的内容包括两个层面：逻辑层面和实现层面。在逻辑层面上，介绍的是各种数据结构的特点，在每种数据结构上进行插入、删除、查找、遍历等相应运算的方 法，不涉及在计算机上实现运算的算法；在实现层面上，讨论的是如何把对数据结构进行运算的方法和步骤转换为用一种计算机程序设计语言描述的算法，并能够实际运行和得到验证。逻辑层面的学习是基本的和必需的，实现层面的学习是进一步的，对于计算机及信息类专业的学生，这两步都要学，而且都要学好，对于经管农林等类的学生，则应侧重 第1步。
数据结构课程是一门理论性和实践性都很强的课程，只有通过亲自编写算法、上机运行和调试程序，才能够加深理解和掌握所学的知识，提高程序设计和软件研发能力。
使用此教材，最好具有C++语言的基础，因为书中描述的数据类型和算法都是按照C++语言的规则编写的。当然，若是只具有其他计算机语言的基础，则使用该书时应同时自学C++语言。对于一般读者来说，只要有任一种计算机语言的基础，再自学任何其他计算机语言都是不困难的。
与本书配套的《数据结构实用教程习题参考解答》也同时改版，将同此主教材一并出版发行。与本书配套的《数据结构课程实验》一书暂时不需改版，仍可继续与这本第二版主教材配套使用。
在由清华大学出版社组织的此套系列教材中，本人还编著了《C++语言基础教程》一书，该书已重印十多次，便于自学，读者反映较好，并被列选为国家“十一五”规划教材，不妨推荐给读者参考。
衷心希望通过这次改版，使《数据结构实用教程》一书更加受到读者的爱戴和好评，也同时希望读者继续给予批评指正，本人深表谢意！
作者电子邮箱：[e-mail]，联系电话：[phone]。


徐孝凯
2006年8月


第一版前言
数据结构是普通高校计算机专业和信息管理专业一门必修的核心课程。它的主要任务是讨论现实世界中数据（即事物的抽象描述）的各种逻辑结构、在计算机中的存储结构以及进行各种非数值运算的算法，目的是使学生掌握数据组织、存储和处理的常用方法，为以后进行软件开发和学习后续专业课程打下基础。
数据的逻辑结构分为集合结构、线性结构、树结构和图结构4种。数据的存储结构分为顺序结构、链接结构、索引结构和散列结构4种。对数据进行的非数值运算主要包括插
入、删除、查找、排序、输入和输出等。需要特别指出：数据的存储结构既适用于内存，
也适用于外存，不仅要学会对内存数据操作的算法，而且要学会对外存数据（文件）操作的算法，这样才能够解决实际软件开发的问题，达到学以致用的目的。
在已经出版的众多数据结构教材中，对每一种数据结构类型进行相应运算的算法描述通常是粗略的，离真正用一种计算机语言上机实现还有相当的距离，特别在外存文件的操作上更是如此。本套教材在这方面做了彻底的改变，所给出的每一算法都利用C/C++语言给出了具体的实现，算法的正确性和有效性得到了实际的检验，这样就突出了实用性，使教材更便于教学，特别是自学，克服了以往同类教材只重视理论而轻视算法具体实现的 缺陷。
本套教材包含3本，第一本为主教材《数据结构实用教程》，第二本为实验教材《数据结构课程实验》，第三本为辅助教材《数据结构实用教程习题参考解答》。主教材共分为8章，依次为绪论、线性表、稀疏矩阵和广义表、栈和队列、树、图、查找和排序。在第1章的绪论中，1.2节为算法描述，对于C++语言比较熟悉的教学班和读者，此内容可作为自学阅读内容。主教材没有专门给出文件一章，这是因为，可把文件（这里只讨论磁盘文件）看作存储在外存上的数组，通过文件流操作函数既可顺序存取文件内容，也可随机存取文件中任何位置上的信息块，如何使用文件已经在C/C++语言中学习过，在数据结构课程中只是应用问题，所以不必单列一章介绍。实验教材给出了10个数据结构应用的典型例题，并给出了相应的参考程序。辅助教材给出了主教材中每章习题的大部分参考解答，最后附加了两个综合题，它们是针对不同文件的插入、删除和查找操作的，目的是培养学生对所学知识的实际应用能力。
本人一直从事数据结构的教学和研究工作，编著过多本教材，清华大学出版社已经出版的《数据结构简明教程》一书就是其代表作。现在这套教材是本人多年教学经验的结晶，是对以往教材的继承、丰富和发展，希望能够对数据结构课程的教学起到良好的作用，使读者能够得到满意的收获。
本套教材是根据计算机专业和信息管理专业本科培养目标，对数据结构课程教学的要求编写的。由于内容叙述细致，算法描述具体，便于自学，所以删除部分内容后可作为相应专科学生的教材。具体如何删减，应由办学单位和任课教师定夺。
学习本套教材应具有C语言或C++语言的基础。若只学习过C语言，则应在学习本课程的过程中补充C++语言的输入/输出操作、文件流操作、运算符重载等有关内容。
本课程总学时应安排在80～100学时之间，其中讲授与上机学时之比应为2∶1左右，有条件的学生要尽量多上机。
承蒙北京大学计算机系许卓群教授和北京石油大学计算机系陈明教授认真审阅了本套教材的全部书稿，提出了宝贵的意见，在此谨向他们表示衷心感谢。
尽管本人做了很大的努力，但由于水平有限，加之时间仓促，错误和不足之处在所难免，敬请授课教师和广大读者批评指正。
电子邮箱地址：[e-mail]，联系电话：[phone]。

徐孝凯
1999年10月

目 录

目 录
第1章 绪论1
1.1 常用术语1
1.2 算法描述11
1.3 算法评价13
*1.4 与算法描述有关的C++知识19
1.4.1 包含文件语句20
1.4.2 数据类型28
1.4.3 函数36
1.4.4 运算符重载41
习题143
第2章 线性表48
2.1 线性表的定义和抽象数据类型48
2.1.1 线性表的定义48
2.1.2 线性表的抽象数据类型49
2.1.3 操作举例50
2.2 线性表的顺序存储和操作实现51
2.2.1 线性表的顺序存储结构51
2.2.2 顺序存储下的线性表操作的实现53
*2.3 线性表应用举例62
2.4 线性表的链接存储结构67
2.5 线性表操作在单链表上的实现75
*2.6 多项式计算83
2.6.1 多项式表示与求值83
2.6.2 两个多项式相加88
习题291
第3章 集合、稀疏矩阵和广义表94
3.1 集合的定义和抽象数据类型94
3.1.1 集合定义94
3.1.2 集合的抽象数据类型94
3.2 集合的顺序存储结构和操作实现95
3.3 集合的链接存储结构和操作实现102
3.4 稀疏矩阵108
3.4.1 稀疏矩阵的定义108
3.4.2 稀疏矩阵的存储结构110
*3.4.3 稀疏矩阵的运算113
3.5 广义表120
3.5.1 广义表的定义120
3.5.2 广义表的存储结构122
3.5.3 广义表的运算123
3.5.4 简单程序举例127
习题3128
第4章 栈和队列131
4.1 栈131
4.1.1 栈的定义131
4.1.2 栈的抽象数据类型131
4.2 栈的顺序存储结构和操作实现132
4.3 栈的链接存储结构和操作实现136
4.4 栈的简单应用举例138
4.5 算术表达式的计算142
4.5.1 算术表达式的两种表示142
4.5.2 后缀表达式求值的算法144
4.5.3 把中缀表达式转换为后缀表达式的算法146
4.6 栈与递归150
4.7 队列160
4.7.1 队列的定义160
4.7.2 队列的抽象数据类型161
4.7.3 队列的顺序存储结构和操作实现162
4.7.4 队列的链接存储结构和操作实现165
*4.8 队列应用举例169
习题4173
第5章 树178
5.1 树的概念178
5.1.1 树的定义178
5.1.2 树的表示180
5.1.3 树的基本术语181
5.1.4 树的性质182
5.2 二叉树183
5.2.1 二叉树的定义183
5.2.2 二叉树的性质184
5.2.3 二叉树的抽象数据类型186
5.2.4 二叉树的存储结构187
5.3 二叉树遍历189
5.4 二叉树其他运算193
5.5 树的存储结构和运算198
5.5.1 树的抽象数据类型198
5.5.2 树的存储结构199
5.5.3 树的运算201
习题5207
第6章 特殊二叉树212
6.1 二叉搜索树212
6.1.1 二叉搜索树的定义212
6.1.2 二叉搜索树的抽象数据类型212
6.1.3 二叉搜索树的运算213
6.2 堆220
6.2.1 堆的定义220
6.2.2 堆的抽象数据类型221
6.2.3 堆的存储结构221
6.2.4 堆的运算222
6.3 哈夫曼树227
6.3.1 基本术语227
6.3.2 构造哈夫曼树228
*6.3.3 哈夫曼编码231
*6.4 线索二叉树234
6.4.1 二叉树的线索化234
6.4.2 利用线索进行遍历238
*6.5 平衡二叉树241
6.5.1 平衡二叉树的定义241
6.5.2 平衡二叉树的调整242
习题6247
第7章 图249
7.1 图的概念249
7.1.1 图的定义249
7.1.2 图的基本术语250
7.1.3 图的抽象数据类型253
7.2 图的存储结构254
7.2.1 邻接矩阵254
7.2.2 邻接表257
7.2.3 边集数组262
7.3 图的遍历264
7.3.1 深度优先搜索遍历264
7.3.2 广度优先搜索遍历267
7.3.3 非连通图的遍历269
习题7271
第8章 图的应用273
8.1 图的生成树和最小生成树273
8.1.1 生成树和最小生成树的概念273
8.1.2 普里姆算法275
8.1.3 克鲁斯卡尔算法278
8.2 最短路径281
8.2.1 最短路径的概念281
8.2.2 从一顶点到其余各顶点的最短路径282
*8.2.3 每对顶点之间的最短路径286
8.3 拓扑排序290
8.3.1 拓扑排序的概念290
8.3.2 拓扑排序算法293
*8.4 关键路径296
8.4.1 顶点事件的发生时间296
8.4.2 计算关键路径的方法和算法299
习题8302
第9章 查找305
9.1 查找的概念305
9.2 顺序表查找306
9.2.1 顺序查找306
9.2.2 二分查找307
9.3 索引查找311
9.3.1 索引的概念311
9.3.2 索引查找算法314
*9.3.3 分块查找316
9.4 散列查找317
9.4.1 散列的概念317
9.4.2 散列函数319
9.4.3 处理冲突的方法321
9.4.4 散列表的运算324
9.5 B树查找328
9.5.1 B_树定义328
9.5.2 B_树查找330
9.5.3 B_树插入332
9.5.4 B_树删除335
*9.5.5 对B_树的其他运算337
*9.5.6 B+树简介340
习题9341
第10章 排序343
10.1 排序的基本概念343
10.2 插入排序344
10.2.1 直接插入排序345
*10.2.2 希尔排序346
10.3 选择排序347
10.3.1 直接选择排序347
10.3.2 堆排序348
10.4 交换排序352
10.4.1 气泡排序352
10.4.2 快速排序354
10.5 归并排序357
*10.6 各种内排序方法的比较360
*10.7 外排序362
10.7.1 外排序的概念362
10.7.2 外排序算法364
习题10371