数据结构(C语言描述)(第2版)徐孝凯

第2版前言

数据结构是普通高等院校计算机及相关专业开设的一门主干基础课程，其教学内容主要包括数据的逻辑结构、存储（物理）结构及其相关运算。学习这门课程要解决的问题是： 如何把现实世界中存在的大量数据，在逻辑和物理上有效地组织起来，形成一个数据系统，进而实施有关运算，从中得到人们所需要的有用信息。

数据结构课程所涉及的内容非常广泛而精深，各种数据组织和运算方法层出不穷，但如何能够让学生在有限的时间内学习到这门课程更多更好的知识体系，发挥出画龙点睛、举一反三的作用，这是每位编写此类教材的作者必须要面对和深思的问题。

本人在编写这本教材的第2版时，也进行了认真的思考，在众多数据结构教材中找准自己教材的定位，突出自己教材的特色。本教材具有以下鲜明特色。

(1) 本书内容具有很强的连贯性和系统性。

(2) 第1章是全书的起步和总览，简明扼要，开门见山。本书第1章通过具体数据处理示例，自然引出各种典型的数据结构，让读者对看似高深的概念一目了然，为深入学习后面各章做好准备。

(3) 本书对数据的各种逻辑结构和存储结构的讨论，采用统一的、规范化的方法，便于读者理解和掌握，并且还能举一反三、触类旁通。

(4) 本书对每种数据结构的运算，都采用抽象数据类型和抽象存储类型，定义出统一接口（函数原型声明），具体在对运算的算法描述（函数定义）中采用什么具体的存储类型，将与调用此函数的接口完全无关，这样就很好地体现了当今软件开发中所必须具有的多态性、封装性、隐藏性等特点，有利于读者养成良好的软件开发习惯和提高软件开发水平。

(5) 本书对每一种运算的方法分析和C语言算法描述都尽量做到条理清晰、循序渐进、深入浅出，并在算法内部的各语句中，都给出了简要注释和提示，力求使读者更容易理解和掌握。

(6) 每章后面都配有丰富的、各类题型的习题，给学习者充足的练习天地，以便巩固和加深理解所学知识。

本书若有幸被选作教材或教学参考书，建议读者：

(1) 要从头到尾、按照章节内容的先后次序、一步一个脚印地阅读，并在阅读过程中富于联想和思考，这样才能收到事半功倍的学习效果。

(2) 对于自己不明白或有疑问的算法，除了认真分析外，还要上机调试和运行，从实际上机操作中得到真实体验和收获。

(3) 在做每章后面的习题时，要尽量独立思考和完成，必要时进行同学之间的交流和讨论，或者向老师寻求帮助。无论做得对与错，都是对自己学习效果和能力的检验和提高，都是大有裨益的。千万不要急着寻找现成的答案。不经过自己反复思考而得到的结果是不巩固的。

为了给任课教师和自学读者提供方便，本人把教材中所有习题的参考解答交给编辑，从而放到清华大学出版社读者网站上供下载。另外，若愿意与本人交流，可发电子邮件联系，xuxk@crtvu.edu.cn，还可通过编辑与笔者进行电话联系。

在本书构思和编写过程中，得到了中国石油大学陈明教授、首都师范大学王锁柱教授、中央民族大学曹永存教授、北京石油化工学院张晓明教授的热情关心、指导和帮助，本书的全部书稿得到了王锁柱教授不辞辛苦的审阅和修改，在此对各位专家表示真诚感谢！

由于本人学识水平有限，尽管做出了最大努力，但书中疏漏和不足之处在所难免，敬请专家和广大读者批评指正，本人不胜感激！

编者

2017年10月

第1版前言

数据结构主要研究数据的逻辑结构、在计算机中的存储结构，以及对数据进行各种非数值运算的方法和算法。数据的逻辑结构分为集合、线性、树（层次）、图（网状）4种基本结构，由它们可以构成任何所需要的较复杂的逻辑结构。数据的存储结构分为顺序、链接、索引、散列4种基本结构，同样由它们能够构成各种较复杂的存储结构。对数据进行的非数值运算主要包括查找、排序、插入、删除、修改、遍历等。对于同样的数据，若采用的逻辑结构和存储结构不同，对某一运算所采用的方法不同，则将得到不同的算法，进而在计算机上得到不同的运行时间和存储空间效率。通过该课程的学习，读者能够根据实际应用中对数据处理的要求，为数据选择和建立合适的逻辑结构和存储结构，接着选择和使用较好的数据处理方法，以及利用一种程序设计语言编写出相应的算法，最后在计算机系统上调试、运行和实现算法。

本书是根据一般计算机及相关专业对开设数据结构课程的知识结构要求编写的，它介绍的是数据结构学科成熟而实用的知识，摈弃那些深奥难懂而又过时不用的内容； 在写法上力求条理清楚、层次分明、内容连贯、循序渐进，便于阅读和自学；在各种运算方法和算法的分析上，力求细致、生动、深入、透彻，便于理解。

本书共包括9章。第1章概要介绍数据的逻辑结构和存储结构，以及算法的描述和评价。第2~4章主要介绍线性表、栈、队列、稀疏矩阵、广义表等线性数据结构的定义、存储结构，以及相应运算的方法和算法。第5、6章主要介绍树、二叉树、二叉搜索树、堆、哈夫曼树等树结构的定义和存储结构，以及建立、遍历、查找等运算的方法和算法。第7章主要介绍图的定义和存储结构，以及图的建立、遍历、求最小生成树、拓扑排序等运算的方法和算法。第8章主要介绍顺序、二分、索引、散列等查找的方法和算法。第9章主要介绍插入、选择、堆、快速、二路归并、外存文件等排序的方法和算法。

本书给出的所有算法和程序都在C语言运行环境下调试通过，同时，由于C++兼容C语言，本人也在VC++6.0环境下调试通过所有算法和程序，因此能够保证算法是正确和有效的。

本书每章后面都配有丰富的习题，同学们通过做练习和上机调试程序，能够巩固和提高所学知识，能够提高分析问题和解决问题的能力。由于数据结构习题一般较难，有时不太容易做出，为了使同学们得到帮助和受到启发，专门为本书配有习题参考解答一书，并同本书一同出版发行。当然，同学们要尽量独立思考完成作业，绝不能依赖现成的答案。

使用本书推荐讲授学时为64，上机实验学时为32，实验题目可采用教材中所给的调试程序，也可由实验指导教师指定。数据结构课程所涉及的内容较多，而教学时数有限，所以各任课教师可根据实际情况对本书中的内容进行取舍。另外，在每章习题中，加星号的习题较难，可以不做要求。

本书由徐孝凯教授和贺桂英副教授共同编写，在教学大纲构思和教材内容编写的过程中得到了巫家敏教授的真诚指导，得到了徐培忠和郑寅堃的热情帮助，在此谨向他们表示衷心感谢！

由于作者水平有限，不足之处在所难免，敬请同行专家和广大读者指正。

徐孝凯

2004年2月

目录

第1章绪论

1．1基本概念

1．2算法描述

1．3算法评价

习题

第2章集合

2．1集合的定义和运算

2．2集合的顺序存储结构和操作实现

2．3集合的链接存储结构和操作实现

2．3．1链接存储集合的概念

2．3．2集合运算在链接存储结构下的操作实现

习题

第3章线性表

3．1线性表的定义和运算

3．2线性表的顺序存储结构和操作实现

3．3链接存储的一般概念和方法

3．4线性表的链接存储结构和操作实现

习题

第4章栈和队列

4．1栈的定义和运算

4．2栈的顺序存储结构和操作实现

4．3栈的链接存储结构和操作实现

4．4栈的简单应用举例

4．5算术表达式的计算

4．5．1算术表达式的两种表示

4．5．2后缀表达式求值的算法

4．5．3把中缀表达式转换为后缀表达式的算法

4．6栈与递归

4．7队列

4．7．1队列的定义和运算

4．7．2队列的顺序存储结构和操作实现

4．7．3队列的链接存储结构和操作实现

4．7．4队列的应用简介

习题

第5章树和二叉树

5．1树的概念

5．1．1树的定义

5．1．2树的表示

5．1．3树的基本术语

5．1．4树的性质

5．2二叉树

5．2．1二叉树的定义

5．2．2二叉树的性质

5．2．3二叉树的抽象数据类型

5．2．4二叉树的存储结构

5．3二叉树遍历

5．4二叉树其他运算

5．5树的存储结构和运算

5．5．1树的抽象数据类型

5．5．2树的存储结构

5．5．3树的运算

习题

第6章二叉树应用

6．1二叉搜索树

6．1．1二叉搜索树的定义

6．1．2二叉搜索树的抽象数据类型

6．1．3二叉搜索树的运算

6．2堆

6．2．1堆的定义

6．2．2堆的抽象数据类型

6．2．3堆的存储结构

6．2．4堆的运算

6．3哈夫曼树

6．3．1基本术语

6．3．2构造哈夫曼树

6．3．3哈夫曼编码

习题

第7章图

7．1图的概念

7．1．1图的定义

7．1．2图的基本术语

7．1．3图的抽象数据类型

7．2图的存储结构

7．2．1邻接矩阵

7．2．2邻接表

7．2．3边集数组

7．3图的遍历

7．3．1深度优先搜索遍历

7．3．2广度优先搜索遍历

7．3．3非连通图的遍历

7．3．4图的遍历算法的上机调试

7．4图的其他运算

习题

第8章图的应用

8．1图的生成树和最小生成树

8．1．1生成树和最小生成树的概念

8．1．2普里姆算法

8．1．3克鲁斯卡尔算法

8．2最短路径

8．2．1最短路径的概念

8．2．2从图中一顶点到其余各顶点的最短路径

8．2．3图中每对顶点之间的最短路径

8．3拓扑排序

8．3．1拓扑排序的概念

8．3．2拓扑排序算法

8．4关键路径

8．4．1顶点事件的发生时间

8．4．2计算关键路径的方法和算法

习题

第9章查找

9．1查找的概念

9．2顺序表查找

9．2．1顺序查找

9．2．2二分查找

9．3索引查找

9．3．1索引的概念

9．3．2索引查找算法

9．3．3分块查找

9．4散列查找

9．4．1散列的概念

9．4．2散列函数

9．4．3处理冲突的方法

9．4．4散列表的运算

9．5B树查找

9．5．1B树定义

9．5．2B树查找

9．5．3B树插入

9．5．4B树删除

习题

第10章排序

10．1排序的基本概念

10．2插入排序

10．2．1直接插入排序

10．2．2希尔排序

10．3选择排序

10．3．1直接选择排序

10．3．2堆排序

10．4交换排序

10．4．1气泡排序

10．4．2快速排序

10．5归并排序

10．6各种内排序方法的比较

10．7外排序

10．7．1外排序概念

10．7．2外排序算法

习题

本书是利用C语言编写的一本数据结构教材，适合在学习C语言之后使用。书中介绍了各种常用的数据结构、对应的存储结构，以及对其进行各种典型运算的方法和算法； 并给出了丰富而实用的算法实例，这些实例都具有很好的可读性、结构化、模块化和时空有效性。通过深入学习和领会，能够大大提高读者的软件开发和设计能力。本书适合作为各级各类学校数据结构课程的教材或教学参考书，也适合软件开发人员参考。