数据结构（C/C++版）

《数据结构 : C/C  版》结合编著者多年教学经验，从计算机学科发展和相关应用的实际需求出发，对各种常用的数据结构，从逻辑结构、存储结构、数据处理等方面进行深入细致的解剖和分析，使读者更容易理解基本概念和知识，能够轻松地设计算法以便对相关信息进行处理。《数据结构 : C/C  版》共分10章，第1章作为《数据结构 : C/C  版》的综述和基础，介绍数据结构的基本概念、算法分析的方法及与算法描述有关的C  知识；2～7章分别讨论线性表、栈与队列、串、数组和广义表、树与二叉树和图等数据结构的定义、表示和实现；第8章～9章分别介绍查找和内部排序的各种方法和实现算法；第10章为文件，介绍各类文件的组织结构及其操作。书末附录介绍一个用C  描述的顺序表类。《数据结构 : C/C  版》采用C/C  语言作为数据结构和算法的描述语言，《数据结构 : C/C  版》所有算法和程序代码均在VC  6.0环境下调试通过。

《数据结构 : C/C 版》结合编著者多年教学经验，从计算机学科发展和相关应用的实际需求出发，对各种常用的数据结构，从逻辑结构、存储结构、数据处理等方面进行深入细致的解剖和分析，使读者更容易理解基本概念和知识，能够轻松地设计算法以便对相关信息进行处理。《数据结构 : C/C 版》共分10章，第1章作为《数据结构 : C/C 版》的综述和基础，介绍数据结构的基本概念、算法分析的方法及与算法描述有关的C 知识；2～7章分别讨论线性表、栈与队列、串、数组和广义表、树与二叉树和图等数据结构的定义、表示和实现；第8章～9章分别介绍查找和内部排序的各种方法和实现算法；第10章为文件，介绍各类文件的组织结构及其操作。书末附录介绍一个用C 描述的顺序表类。《数据结构 : C/C 版》采用C/C 语言作为数据结构和算法的描述语言，《数据结构 : C/C 版》所有算法和程序代码均在VC 6.0环境下调试通过。

目录
第1章 绪论 1
1.1 数据结构的产生和发展 1
1.1.1 数据结构的产生 1
1.1.2 数据结构的发展 1
1.2 数据结构的研究对象 2
1.3 基本概念和术语 4
1.4 数据结构与算法的关系 9
1.5 算法与算法分析 10
1.5.1 算法概述 10
1.5.2 算法的描述方法 11
1.5.3 算法设计目标 12
1.5.4 算法效率的度量 13
1.6 与算法描述有关的C     知识 16
1.6.1 C     的输入和输出 16
1.6.2 函数 18
1.6.3 对象和类 20
1.6.4 变量的引用类型 24
1.6.5 运算符重载 25
1.6.6 数据类型相关说明 27
1.6.7 两个相关的头文件 28
本章小结 30
习题1 31
第2章 线性表 34
2.1 线性表的基本概念 34
2.1.1 线性表的定义 34
2.1.2 线性表的抽象数据类型 35
2.2 线性表的顺序存储和基本操作 39
2.2.1 线性表的顺序存储—顺序表 39
2.2.2 顺序表的基本操作 41
2.2.3 顺序表基本操作的算法分析 47
2.3 线性表的链式存储和基本操作 48
2.3.1 链式存储的概念 48
2.3.2 单链表概述 49
2.3.3 单链表的基本操作 51
2.3.4 单链表基本操作的算法分析 59
2.3.5 双向链表 59
2.3.6 循环链表 63
2.4 顺序表和链表的综合比较 66
2.4.1 存储分配方式 66
2.4.2 时间性能比较 66
2.4.3 空间性能比较 66
2.5 静态链表 67
2.6 线性表算法设计举例 69
2.6.1 顺序表算法设计举例 69
2.6.2 单链表算法设计举例 72
本章小结 78
习题2 78
第3章 堆栈与队列 81
3.1 堆栈 81
3.1.1 堆栈的基本概念 81
3.1.2 堆栈的顺序存储和基本操作 82
3.1.3 堆栈的链式存储和基本操作 91
3.2 堆栈的应用举例 95
3.3 队列 104
3.3.1 队列的基本概念 104
3.3.2 队列的顺序存储和基本操作 106
3.3.3 队列的链式存储和基本操作 114
3.3.4 其他队列 119
3.4 队列的应用举例 120
习题3 131
第4章 串 133
4.1 串的基本概念 133
4.1.1 串的定义 133
4.1.2 串的抽象数据类型 134
4.2 串的顺序存储和基本操作 136
4.2.1 串的顺序存储—顺序串 136
4.2.2 顺序串的基本操作 137
4.3 串的链式存储和基本操作 146
4.3.1 串的链式存储—链式串 146
4.3.2 链式串的基本操作 147
4.4 串的模式匹配算法 156
4.4.1 Brute-Force算法 156
4.4.2 KMP算法 157
4.5 串的应用举例 162
本章小结 173
习题4 173
第5章 数组和广义表 175
5.1 数组的基本概念 176
5.1.1 数组的定义 176
5.1.2 数组的抽象数据类型 176
5.2 数组的存储结构 177
5.2.1 一维数组的存储 177
5.2.2 多维数组的存储 178
5.3 数组的顺序存储表示和基本操作 179
5.3.1 数组的顺序存储表示 179
5.3.2 数组的基本操作 180
5.3.3 数组的应用举例 184
5.4 矩阵的压缩存储 188
5.4.1 特殊矩阵的压缩存储 188
5.4.2 稀疏矩阵的压缩存储 191
5.5 广义表 208
5.5.1 广义表的基本概念 208
5.5.2 广义表的存储结构 211
5.5.3 广义表的基本操作 214
本章小结 223
习题5 223
第6章 树和二叉树 227
6.1 树 227
6.1.1 树的基本概念 227
6.1.2 树的存储结构 233
6.1.3 树的基本操作 238
6.2 二叉树 246
6.2.1 二叉树的基本概念 246
6.2.2 二叉树的存储结构 251
6.2.3 二叉树的遍历 254
6.2.4 二叉树的其他操作 260
6.3 线索二叉树 270
6.3.1 线索二叉树的基本概念 270
6.3.2 线索二叉树的存储结构 271
6.3.3 线索二叉树的线索化 272
6.3.4 线索二叉树的基本操作 275
6.4 哈夫曼树 279
6.4.1 哈夫曼树的基本概念 279
6.4.2 构造哈夫曼树 282
6.4.3 哈夫曼编码 285
6.5 树、森林与二叉树的转换 289
6.5.1 树与二叉树的转换 289
6.5.2 森林与二叉树的转换 291
6.6 树的应用举例─PATRICIA tree 292
本章小结 296
习题6 297
第7章 图 301
7.1 图的基本概念 301
7.1.1 图的基本定义 301
7.1.2 图的基本术语 302
7.1.3 图的抽象数据类型 306
7.2 图的存储结构 307
7.2.1 邻接矩阵 308
7.2.2 邻接表 310
7.2.3 十字邻接表 312
7.2.4 邻接多重表 313
7.2.5 边集数组 314
7.3 图的实现 315
7.3.1 邻接矩阵存储结构下图基本操作的实现 315
7.3.2 邻接表存储结构下图基本操作的实现 326
7.4 图的遍历 336
7.4.1 深度优先遍历 337
7.4.2 广度优先遍历 339
7.5 *小生成树 344
7.5.1 *小生成树的概念 344
7.5.2 普里姆算法 346
7.5.3 克鲁斯卡尔算法 353
7.6 *短路径 357
7.6.1 *短路径的概念 357
7.6.2 从一顶点到其余各顶点的*短路径 358
7.6.3 每对顶点之间的*短路径 364
7.7 拓扑排序 369
7.7.1 拓扑排序的概念 369
7.7.2 拓扑排序的算法 371
7.8 关键路径 374
7.8.1 关键路径的概念 374
7.8.2 顶点事件的发生时间 375
7.8.3 求关键路径的算法 376
7.8.4 求关键路径的算法描述 379
本章小结 383
习题7 383
第8章 查找 389
8.1 查找的基本概念 389
8.2 静态查找 390
8.2.1 顺序查找 390
8.2.2 二分查找 392
8.2.3 索引查找 394
8.3 动态查找 397
8.3.1 二叉排序树 398
8.3.2 平衡二叉树 406
8.3.3 B_树和B 树 411
8.4 哈希表查找 420
8.4.1 哈希表查找的基本概念 420
8.4.2 哈希函数的构造方法 421
8.4.3 哈希冲突的解决方法 423
8.4.4 哈希表的操作 426
8.4.5 哈希表查找的性能分析 436
本章小结 437
习题8 438
第9章 排序 441
9.1 排序的基本概念 441
9.2 插入排序 443
9.2.1 直接插入排序 443
9.2.2 谢尔排序 445
9.3 选择排序 447
9.3.1 直接选择排序 447
9.3.2 堆排序 449
9.4 交换排序 455
9.4.1 冒泡排序 455
9.4.2 快速排序 457
9.5 归并排序 460
9.6 基数排序 463
9.7 各种内排序方法的性能比较 466
9.8 外排序 468
9.8.1 外存信息的存取 468
9.8.2 外排序的过程 469
9.8.3 多路平衡归并 471
9.8.4 初始归并段的生成 473
9.8.5 **归并树 474
本章小结 476
习题9 476
第10章 文件 481
10.1 文件概述 481
10.1.1 文件的存储介质 481
10.1.2 文件的基本概念 482
10.2 顺序文件 484
10.3 索引文件 486
10.4 ISAM文件 487
10.5 VSAM文件 490
10.6 哈希文件 491
10.7 多关键字文件 493
10.7.1 多重表文件 493
10.7.2 倒排文件 494
10.8 文件的应用举例 494
本章小结 495
习题10 496
参考文献 499
附录 用面向对象的方法（C  的类）描述顺序表类 500

《数据结构 : C/C  版》结合编著者多年教学经验，从计算机学科发展和相关应用的实际需求出发，对各种常用的数据结构，从逻辑结构、存储结构、数据处理等方面进行深入细致的解剖和分析，使读者更容易理解基本概念和知识，能够轻松地设计算法以便对相关信息进行处理。《数据结构 : C/C  版》共分10章，第1章作为《数据结构 : C/C  版》的综述和基础，介绍数据结构的基本概念、算法分析的方法及与算法描述有关的C  知识；2～7章分别讨论线性表、栈与队列、串、数组和广义表、树与二叉树和图等数据结构的定义、表示和实现；第8章～9章分别介绍查找和内部排序的各种方法和实现算法；第10章为文件，介绍各类文件的组织结构及其操作。书末附录介绍一个用C  描述的顺序表类。《数据结构 : C/C  版》采用C/C  语言作为数据结构和算法的描述语言，《数据结构 : C/C  版》所有算法和程序代码均在VC  6.0环境下调试通过。

数据结构,教材,C语言,程序设计,教材

第1章 绪论
　　1.1 数据结构的产生和发展
　　计算机的主要功能是处理数据，这些数据绝不是杂乱无章的，而是有着某种内在联系。只有分清楚数据的内在联系，合理地组织数据，才能对它们进行有效的处理。尤其是目前大型程序的出现、软件的相对独立、结构化程序设计和面向对象程序设计方法的应用，使人们越来越重视数据的有效组织和处理。程序设计的实质就是对确定的问题选择出一种好的数据结构和一种好的算法。由此可见，“数据结构”是计算机学科和相关应用学科的学习中一门必不可少的课程。
　　1.1.1 数据结构的产生
　　数据结构是随着电子计算机的产生和发展而发展起来的一门较新的计算机学科。计算机的发展，在*近20年来是非常快的，这种发展体现在计算机本身硬件特性的优化上，如运算速度不断提高、信息存储量日益扩大、价格逐步下降，而且更重要的是其应用范围的拓广。早期计算机主要用于科学计算，其处理对象是纯数值型的信息，20世纪60年代后，计算机广泛用于情报检索、企业管理、系统工程，乃至人类社会活动的一切领域，处理对象除了纯数值型的信息外，还有非数值型的信息，如字符、图像、声音和视频等。因此，为了设计出效率高、可靠性好的程序，不仅需要对程序设计方法进行系统研究，而且需要研究程序加工的对象，即各种数据的特性及相互之间的关系，这样，就促进了数据结构的产生和发展。
　　1968年，Knuth所著《计算机程序设计艺术》**卷“基本算法”较系统地阐述了数据的逻辑结构和存储结构及其操作，开创了“数据结构”的课程体系。同年，“数据结构”作为一门独立的课程在计算机科学的学位课程中开始出现。20世纪70年代中期到80年代初，各种版本的数据结构著作相继出现。
　　1.1.2 数据结构的发展
　　数据结构的发展与程序设计密切相关。
　　1）程序设计的实质是数据表示和数据处理
　　例如，学生成绩管理系统，需要将学生的成绩信息存储到计算机中，并实现增、删、改、查、统计等功能。实现这个系统需要考虑两个关键问题：
　　（1）数据表示。如何将数据从机外表示转化为机内表示，存储在计算机（内存）中。
　　（2）数据处理。如何处理机内表示的数据，实现问题求解（或完成处理要求）。
　　“数据结构”课程主要讨论数据表示和数据处理过程中的基本问题。
　　2）数据结构起源于程序设计，并随着程序设计的发展而发展
　　程序设计和数据结构的发展阶段分为无结构化阶段、结构化阶段和面向对象阶段，在各种阶段，计算机处理的对象和数据间的关系都在发生着变化，主要体现在表1.1中。
　　表1.1 程序设计和数据结构的发展
　　由以上数据结构的发展过程可以看出，数据结构随着程序设计的发展而发展，并且始终是程序设计的基础与核心。
　　3）数据结构的未来发展
　　数据结构将继续随着程序设计的发展而发展，同时面向各专门领域的数据结构也会得到研究和发展，如多维图形数据结构等，各种实用的高级数据结构被研究出来，各种空间数据结构也在探索和研究中。
　　1.2 数据结构的研究对象
　　就像生物学把自然界的所有生物作为自己的研究对象一样，计算机科学把问题作为自己的研究对象，研究如何用计算机来解决人类所面临的各种问题。
　　用计算机求解问题的一般过程如图1.1所示。
　　图1.1 计算机求解问题的一般过程
　　其中关键的环节如下：
　　（1）抽象出问题的模型；
　　（2）求该模型的解。
　　抽象是一种思考问题的方式，它隐藏了复杂的细节，只保留实现目标所必需的信息。
　　模型就是为了理解事物而对事物进行的抽象，是对事物的一种无歧义的书面描述。通常，模型由一组图形符号和组织这些符号的规则组成。模型是对一个想法或问题进行形式化、特征化、可视化的思维方法，以便更好地理解问题。
　　总体来说，可以将问题分为两类：
　　（1）数值问题。
　　抽象出的模型是数学方程，问题求解的核心是数值计算。例如，给定利率，计算如何存款才能得到较多的利息？其模型是一元二次方程。
　　（2）非数值问题。
　　例1.1 学籍管理问题。
　　如图1.2所示，学籍管理中每个学生的信息由学号、姓名、性别、出生日期和政治面貌组成，计算机的主要操作就是按照某个特定要求对学籍文件进行处理（如给定学号查询某个学生的相关信息等）。在这类文档管理的数学模型中，计算机处理的对象之间存在着的是一种*简单的线性关系，即一对一的关系，这类数学模型可称为线性的数据结构。
　　图1.2 学籍管理问题及其模型
　　例1.2 人-机对弈问题。
　　计算机之所以能和人对弈是因为有人将对弈的策略事先存入了计算机。因为对弈的过程是在一定规则下随机进行的，所以为使计算机能灵活对弈，就必须对对弈过程中所有可能发生的情况及相应的对策都加以考虑，并且一个“好”的棋手在对弈时不仅要看棋盘当时的状态，还应能预测棋局发展的趋势，甚至*后的结局。因此，在对弈问题中，计算机操作的对象是对弈过程中可能出现的棋盘状态—格局。如图1.3所示，每一个方框为一个格局，而格局之间的关系是由比赛规则决定的。通常，这个关系不是线性的，因为从一个棋盘格局可以派生出几个格局。例如，从图1.3所示的顶层格局可以派生出5个格局，而从每一个新的格局又可以派生出4个可能出现的格局。因此，若将从对弈开始到结束整个过程中所有可能出现的格局都画在一张图上，可以得到一棵倒长的“树”。“树根”是对弈开始之前的棋盘格局，而所有的“叶子”就是可能出现的结局，对弈的过程就是从“树根”沿“树杈”到某个“叶子”的过程。“树”可以是某些非数值计算问题的数学模型，它也是一种数据结构，反映的是数据之间一对多的关系。
　　图1.3 人-机对弈问题及其模型
　　例1.3 教学计划编排问题及其模型。
　　在教学编排问题中，排课必须考虑到课程的先后关系，某门课程可能需要学完几门先修课程后才能开设，如图1.4中，“数据结构”的先修课程有“离散数学”和“程序设计语言”；而这门课程又可能是其他课程的先修课程，如“数据结构”是“数据库原理”的先修课程，如何排课才是可行的？
　　图1.4 教学计划编排问题及其模型
　　通常，这类问题的数学模型是一种称为“图”的数据结构，它反映的是数据之间的多对多的关系。例如，在此例中，可以用图中的一个顶点表示一门课程，而课程之间的关系以两个顶点之间的带箭头的连线表示，如c1→c4表示c1是c4的先修课程，排课的问题转化为在有向图中寻求一条可以通行的路径。
　　诸如此类的问题很多，在此不再一一列举。总的来说，这些问题的数学模型都不是用通常的数学分析的方法得到的，因而无法用数学的公式或方程来描述，这就是计算机求解问题过程中的“非数值计算”，而这些非数值问题抽象出的模型是表、树、图之类的数据结构，而不是数学方程，非数值问题求解的核心是数据处理，而不是数值计算。数据结构讨论的正是这类问题求解过程中所涉及的现实世界实体对象的描述、信息的组织方法及其相应操作的实现。
　　1.3 基本概念和术语
　　数据 数据（data）是客观事物的符号表示，在计算机科学中是指输入计算机中被计算机程序加工处理的符号的总称，它是计算机加工的原料的总称。因此，对计算机科学而言，数据的含义极为广泛，如一个数值、一个单词、一句话、一篇文章、一幅图画、一段声音、一段视频等都被称为数据。
　　数据元素 数据元素（data element）是数据的基本单位，即数据这个集合中的一个客体。在计算机中通常将数据元素作为一个整体进行考虑。每一个数据元素可以只有一个数据项［内存中称为域（field）］，也可以由若干个数据项组成。例如，一个整数“6”或一个字符“A”都是一个数据元素，只有一个数据项；而如图1.2所示的学籍管理问题中，每个学生的情况就用一个数据元素表示，其中的学号、姓名、性别、出生日期、政治面貌则分别为一个数据项。
　　数据项 数据项是数据的不可分割的*小单位。
　　数据元素的同义语有结点（node）、顶点（vertex）和记录（record）等。它们的名称虽然不同，但所表示的意义却是一样的，都代表着数据的基本单位。不过，顺序结构中多用“元素”，链式结构中多用“结点”，而在图和文件中又分别使用“顶点”和“记录”。
　　总结：（1）一般来说，能独立、完整地描述客观世界的一切实体都是数据元素，如一个通讯录、一场球赛、一场报告会等；
　　（2）数据元素是讨论数据结构时涉及的*小数据单位，其中的数据项一般不予考虑；
　　（3）数据、数据元素、数据项之间是包含关系，数据由数