数据结构（C语言描述）

在新世纪计算机的高速发展和广泛应用，使得计算机成为一门热门专业，并迫切要求人们使用计算机来处理各项工作和日常事务。

“数据结构”是一门综合性的计算机专业基础课，它涉及数学、计算机软件和计算机硬件等三方面的知识，与高级编程语言、离散数学和软件工程有着密切联系。学习本课程的目的就是形成一种如何将现实生活中的问题用计算机来解决的思路、方法。对于具体的问题，先对它进行分析，抽象出一个适当的数学模型，然后设计解此数学模型的相应算法，最后给出源程序，经过调整、测试得到最终结果。

本书采用C语言作为描述数据结构和算法的工具，利用了C语言的语言简洁、紧凑，使用方便、灵活和生成目标代码质量高，程序执行效率高等特点。还有一点就是C语言编写的程序在C++中运行时程序本身不需要做很大的改动。

本书是按照教材的体例编写的，在内容的组织和描述上遵循了学习的规律。其知识点与本科院校保持一致，注重学科体系完整性。全书共10章，布局上共分三大部分，主要以逻辑结构为主线。第一部分：第1章，交代了学习本课程的意义、数据结构的基本知识及本课程的主体框架。第二部分：第2章、第3章、第4章、第5章、第6章和第7章，介绍了线性结构、树型结构和图型结构三种结构的特征、存储结构及各种操作的实现。第三部分：第8章、第9章和第10章，给出了典型的查找、排序算法和一些案例分析，应用前面章节所学知识解决实际问题。每章都有小结，作为本章内容的总结。除了总结每章还配有习题，分为选择题、填空题、应用题、写算法和上机实践题等多种题型。选择题和填空题是对基本知识的考核，应用题是对基本知识的应用，写算法题包含各章节中所学数据结构的各种操作的实现，上机实践题主要作为实践环节内容。通过多种类型的习题达到对本章所学知识巩固的目的。

本教材的讲授学时可为54至72学时，实践学时可为16学时左右。教师可根据实际情况选讲或不讲目录页中带*号的章节。

本书由斯庆巴拉主编，孙沛任副主编。各章主要编写人员分工如下：第1章、第2章和第10章由斯庆巴拉编写，第6章由孙沛编写，第3章和第4章由刘威编写，第5章和第7章由肖宏涛编写，第8章和第9章由孙琦编写。参与本书大纲讨论、部分内容编写、实例程序调试等工作的还有安志远、李建义、李杰、王静、王慧莹、张保国、张宏伟等。

在本书的编写过程中，阅读了大量的参考资料，从中吸取了许多宝贵经验，在此表示感谢。尽管已经尽了最大的努力来避免错误的发生，但限于水平和时间，书中不妥和错误在所难免，恳请各位专家、读者批评指正。笔者的E-mail为：siqing@nciae.edu.cn。

编者

2005年7月

序
前言
第1章 学习数据结构课程的意义 1
本章学习目标 1
1.1 实例：高校选修课程管理 1
1.1.1 问题描述 1
1.1.2 问题的分析 2
1.1.3 学习本课程的意义 3
1.2 数据结构的主要内容 3
1.2.1 基本概念和术语 3
1.2.2 数据结构定义 4
1.2.3 逻辑结构的表示方法 5
1.3 算法和算法分析 7
1.3.1 算法定义 7
1.3.2 算法分析 8
本章小结 10
习题 10
第2章 线性表 14
本章学习目标 14
2.1 实例：学生信息的存储 14
2.1.1 问题描述 14
2.1.2 问题的分析 14
2.1.3 实现算法 15
2.2 线性表的逻辑结构 16
2.2.1 线性表的逻辑结构 16
2.2.2 线性表的基本操作 17
2.3 线性表的顺序存储 17
2.3.1 顺序存储方式 17
2.3.2 各种操作的实现 18
2.4 线性表的链式存储 23
2.4.1 链式存储方式 23
2.4.2 各种操作的实现 25
2.4.3 循环单链表 28
2.4.4 双向链表 28
2.5 动态存储管理 30
2.5.1 存储管理的任务 30
2.5.2 内存的动态分配和回收 31
2.6 应用举例：线性表的建立与合并 34
2.6.1 线性表的建立 34
2.6.2 线性表的合并 36
2.6.3 线性表的逆置 37
2.6.4 线性表各种操作的综合实践 39
本章小结 44
习题 45
第3章 栈和队列 47
本章学习目标 47
3.1 实例：药店药品柜的管理 47
3.1.1 问题描述 47
3.1.2 问题分析 47
3.2 逻辑结构及特征 47
3.2.1 栈的基本概念 48
3.2.2 队列的基本概念 49
3.3 栈的存储结构 50
3.3.1 栈的顺序存储 50
3.3.2 栈的链式存储 52
3.4 队列的存储结构 55
3.4.1 队列的顺序存储 55
3.4.2 队列的链式存储 58
3.5 应用举例 61
3.5.1 表达式中的括号匹配的检验 61
3.5.2 递归 61
3.5.3 栈和队列的各种操作的综合实践 63
本章小结 67
习题 68
第4章 串 70
本章学习目标 70
4.1 串类型的定义 70
4.2 串的存储结构 70
4.2.1 串的顺序存储 71
4.2.2 串的链式存储 72
4.2.3 串的索引存储 72
4.3 串的操作 73
4.3.1 串常用操作的实现 74
4.3.2 模式匹配操作 82
本章小结 87
习题 87
第5章 数组 89
本章学习目标 89
5.1 数组 89
5.1.1 一维数组 89
5.1.2 多维数组 89
5.2 数学中的应用 91
5.2.1 稀疏矩阵 91
*5.2.2 特殊矩阵 97
5.3 广义表 99
5.3.1 基本概念 99
5.3.2 广义表的存储结构 100
*5.3.3 广义表的运算 102
本章小结 107
习题 107
第6章 树 110
本章学习目标 110
6.1 实例1：文件目录管理 110
6.1.1 问题描述 110
6.1.2 问题分析 110
6.1.3 实现算法 111
6.2 树的逻辑结构和存储结构 112
6.2.1 树的逻辑结构 112
6.2.2 树的相关术语 113
6.3 树的遍历 113
6.3.1 先根遍历 114
6.3.2 后根遍历 114
6.3.3 按层遍历 114
6.4 实例2：通信中电文编码 115
6.4.1 问题描述 115
6.4.2 问题分析 115
6.4.3 实现算法 116
6.5 二叉树的定义和存储结构 117
6.5.1 二叉树的定义 117
6.5.2 二叉树的性质 118
6.5.3 二叉树的存储结构 119
6.6 二叉树遍历 121
6.6.1 先根遍历 121
6.6.2 中根遍历 123
6.6.3 后根遍历 124
6.6.4 按层遍历 125
6.6.5 二叉树遍历的应用 126
6.7 树与二叉树的转换 127
6.7.1 树的存储结构 127
6.7.2 树与二叉树的转换 129
6.7.3 森林与二叉树的转换 131
6.8 应用举例 132
*6.8.1 线索二叉树 132
6.8.2 二叉排序树 134
6.8.3 哈夫曼树 136
6.8.4 二叉树的综合实例 137
本章小结 141
习题 142
第7章 图 146
本章学习目标 146
7.1 实例：求城市间最短路径 146
7.1.1 问题描述 146
7.1.2 问题分析 146
7.2 图的逻辑结构和特征 148
7.2.1 图的逻辑结构 148
7.2.2 图的特征 149
7.3 图的存储结构 151
7.3.1 邻接矩阵 151
7.3.2 邻接表 153
*7.3.3 十字链表 155
*7.3.4 边集数组 156
*7.3.5 邻接多重表 157
7.4 图的遍历 158
7.4.1 深度优先搜索 158
7.4.2 广度优先搜索 159
7.5 最小生成树 160
7.5.1 克鲁斯卡尔算法 161
7.5.2 普里姆算法 163
7.6 应用举例 166
7.6.1 求源点到其余各顶点间的最短路径 166
7.6.2 拓扑排序 168
本章小结 172
习题 173
第8章 典型查找算法 176
本章学习目标 176
8.1 实例：学生分配座位 176
8.1.1 问题描述 176
8.1.2 问题分析 176
8.1.3 实现算法 177
8.1.4 基本概念 178
8.2 静态查找 178
8.2.1 顺序查找 179
8.2.2 折半查找 179
8.2.3 分块查找 182
8.3 动态查找 183
8.3.1 二叉排序树查找 183
8.3.2 二叉平衡树 185
8.4 散列查找 186
8.4.1 散列存储和散列函数的构造方法 186
8.4.2 解决冲突的方法 188
8.4.3 散列查找实现算法和性能分析 190
本章小结 192
习题 193
第9章 典型排序算法 195
本章学习目标 195
9.1 实例：统计学生成绩表 195
9.1.1 问题描述 195
9.1.2 问题分析 196
9.1.3 实现算法 196
9.1.4 排序定义及相关概念 197
9.2 插入排序 198
9.2.1 直接插入排序 198
9.2.2 折半插入排序 199
*9.2.3 希尔排序 199
9.3 选择排序 201
9.3.1 直接选择排序 201
9.3.2 堆排序 202
9.4 交换排序 205
9.4.1 冒泡排序 205
9.4.2 快速排序 206
9.5 归并排序和基数排序 208
9.5.1 归并排序 208
*9.5.2 基数排序 211
9.6 比较各种内排序方法 214
9.6.1 各种内排序方法的比较 214
9.6.2 各种内排序方法的选择 215
9.7 外排序 216
9.7.1 外排序的基本过程 216
*9.7.2 多路归并排序 217
本章小结 218
习题 219
第10章 案例分析 222
本章学习目标 222
10.1 约瑟夫问题 222
10.1.1 问题描述 222
10.1.2 问题分析 222
10.1.3 函数设计 223
10.1.4 上机调试 224
10.2 迷宫求解 225
10.2.1 问题描述 225
10.2.2 问题分析 225
10.2.3 函数设计 226
10.2.4 上机调试 229
10.3 排队问题 230
10.3.1 问题描述 230
10.3.2 问题分析 231
10.3.3 函数设计 231
10.3.4 上机调试 234
10.4 教学计划中的课程编排 236
10.4.1 问题描述 236
10.4.2 问题分析 237
10.4.3 函数设计 237
10.4.4 上机调试 240
10.5 简单的学籍管理系统 241
10.5.1 问题描述 241
10.5.2 问题分析 242
10.5.3 函数设计 242
10.5.4 上机调试 246
本章小结 248
习题 249
参考文献 250

1. 数据结构（Python语言描述） [曹岳辉　刘卫国　康松林　编著]
2. 数据结构——C语言（微课版） [主编 梁海英]
3. 数据结构（C语言版）习题解答及实训指导 [李根强 谢月娥]
4. 数据结构（C语言版） [主编 李根强 刘浩 谢月娥]
5. 数据结构（Java版） [主编 李云平]
6. 数据结构 [主编 韩利凯 朱浩悦]
7. 数据结构（C语言版）（第三版） [主编 库波 曹静]
8. 数据结构（Java版） [孙琳 张宇]
9. 数据结构 [许绘香 段明义]
10. 数据结构（C语言描述） [李素若 陈万华 游明坤 编著]
11. 数据结构习题解答及上机指导 [李素若 琚辉 严永松 编著]
12. 数据结构（C++描述）习题解答及实习指导 [李根强 谢月娥 主编]
13. 数据结构（C语言版）学习指导与习题解答 [赵坚 姜梅 主编]
14. 数据结构 [陆勤 主编 ]
15. 数据结构（C++描述） [李根强 主 编]
16. 数据结构（C++版）--习题解答及实习指导 [李根强 主编]
17. 数据结构算法--Visual C++ 6.0程序集 [侯识忠 等编著]
18. 数据结构算法--C++ Builder 6.0程序集 [侯识忠 等编著]
19. 数据结构（C语言版）学习指导与习题解答 [赵坚 姜梅 主编]
20. 数据结构（C语言版） [赵坚 姜梅 主编]
21. 数据结构（C++版）（第二版） [李根强]
22. 数据结构（C++版）（第二版）习题解答及实训指导 [李根强]
23. 数据结构——用C语言描述 [蔡明志 编著]
24. 数据结构（C++版） [李根强 主编]
25. 数据结构--用C语言描述（第二版） [宁正元 易金聪 编著]
26. 数据结构（C语言描述） [马秋菊 主编]
27. 数据结构（C/C++描述） [阮宏一 主编]
28. 数据结构--C语言描述（第二版） [王路群 主编]
29. 数据结构、算法与应用（Java语言描述） [[美]Sartaj Sahni（萨尔塔杰.萨]
30. 数据结构实验程序 [智东杰 主 编]