数据结构（用C语言描述）

全书各章均按照“学习要点→案例引入→提出问题→理论讲解→案例分析”的总体思路编写而成，力求体现以应用为主体，着重强调知识的理解和运用，实现高职高专教学以应用能力为主要培养目标，做到内容丰富、深入浅出、循序渐进，力求达到先进性、科学性、可读性、通俗性、实用性的有机结合。为帮助读者学习掌握数据结构知识，每种数据结构的引入不是从抽象的定义出发，而是从实例出发，通过对实例的分析、理解，总结出数据结构的特点及应用，使读者能迅速掌握数据结构的有关概念、存储结构、基本操作和有关算法实现。

  数据结构是计算机各专业的一门重要的核心专业基础课程。当用计算机来解决实际问题时，就要涉及到数据（Data）的表示及数据的处理，而数据表示与处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下坚实的基础，同时也提供必要的技能训练。本书在编写过程中保持了与本系列丛书其他书籍在知识结构上的系统性和编写风格上的一致性，进一步增强了本书的可读性。本书为高职高专规划教材，依据教育部关于“高职高专计算机教育教学基本要求”，结合高职高专的教学特点，全书各章均按照“学习要点→案例引入→提出问题→理论讲解→案例分析”的总体思路编写而成，力求体现以应用为主体，着重强调知识的理解和运用，实现高职高专教学以应用能力为主要培养目标，做到内容丰富、深入浅出、循序渐进，力求达到先进性、科学性、可读性、通俗性、实用性的有机结合。为帮助读者学习掌握数据结构知识，每种数据结构的引入不是从抽象的定义出发，而是从实例出发，通过对实例的分析、理解，总结出数据结构的特点及应用，使读者能迅速掌握数据结构的有关概念、存储结构、基本操作和有关算法实现。书中的例题都经过仔细的调试。每章都配有课后习题和实训题，供读者课外巩固所学的内容。

  本书共8章，内容包括：绪论、线性表、栈和队列、其他线性数据结构（串、数组）、树和二叉树、图、查找以及排序。本书第1章、第2章由王宇川、倪华锦编写，第3章、第4章由郭建东、吴嵘编写，第5章由王宇川、何曙辉编写，第6章由郭建东、何受倩编写，第7章由郭建东、罗捷斯编写，第8章由王宇川、田夏编写，全书由王宇川负责，罗捷斯、何曙辉协助统稿；由郭建东、王文莉、吴嵘等编辑校对，全书由张念主审。本书是作者有关学校与广州黑马软件科技有限公司“校企合作编写教材项目”，广州软件行业协会会长、广州黑马软件科技有限公司董事长兼总经理罗捷斯亲自参加了本书的编写。

  本书在编写过程中，得到了广东工贸职业技术学院、广东科贸职业技术学院、广州金桥管理干部学院、广州航海高等专科学校、广东轻工职业技术学院、广州黑马软件科技有限公司以及中国人民解放军后勤部一六一医院等单位的大力支持。本书适合于高职高专院校计算机各专业学生、成人继续教育和自学人员使用，*号部分为选修内容。由于时间仓促且作者水平有限，书中难免存在不妥和错误之处，恳请广大读者提出宝贵意见。

序
前言
第1章  绪论 1
1.1  什么是数据结构 1
1.1.1  概述 1
1.1.2  案例分析 2
1.2  基本概念和术语 4
1.3  数据结构课程的内容 5
1.3.1  数据类型 6
1.3.2  抽象数据类型 7
1.4  算法和算法分析 7
1.5  算法性能分析与度量 8
习题一 10
第2章  线性表 12
2.1  线性表的定义及逻辑结构 12
2.2  线性表的基本操作 13
2.3  线性表的顺序存储结构 14
2.3.1  顺序表 14
2.3.2  顺序表上基本运算的实现 15
2.3.3  案例分析 19
2.4  线性表的链式存储结构 23
2.4.1  单链表 24
2.4.2  单链表上的基本运算 25
2.4.3  循环链表 31
*2.4.4  双向链表 32
*2.4.5  静态链表 33
2.4.6　案例分析 34
2.5  顺序表和链表的比较 39
习题二 40
第3章  栈和队列 43
3.1  栈 43
3.1.1  栈的定义及基本运算 43
3.1.2  顺序栈 44
3.1.3  链栈 46
3.1.4  案例分析 47
3.2  队列 53
3.2.1  队列的定义及基本运算 53
3.2.2  队列的顺序存储结构 54
3.2.3  队列的链式存储 57
3.2.4　案例分析 59
习题三 63
第4章  其他线性数据结构 67
4.1  串 67
4.1.1  串的定义及基本操作 68
4.1.2  串的定长顺序存储结构及基本运算 69
*4.1.3  串的堆存储结构 71
4.1.4　案例分析 73
4.2  多维数组 75
4.2.1  数组的定义及基本操作 75
4.2.2  数组的内存映像 75
4.2.3　案例分析 77
4.3  矩阵的压缩存储 78
4.3.1  稀疏矩阵的压缩存储 78
4.3.2  案例分析 81
4.3.3  特殊矩阵的压缩存储 84
习题四 87
第5章  树和二叉树 90
5.1  树的定义和基本操作 90
5.1.1  树的定义 90
5.1.2  基本术语 92
5.1.3  树的基本操作 92
5.2  二叉树 92
5.2.1  二叉树的定义和基本操作 92
5.2.2  二叉树的性质 93
5.2.3  二叉树的存储 95
5.2.4  二叉树的基本操作及实现 98
5.2.5  二叉树的遍历方法及递归实现 100
5.2.6  二叉树遍历的非递归实现 103
5.2.7  由遍历序列恢复二叉树 106
5.3  树和森林 108
5.3.1  树的表示 108
5.3.2  树的存储结构 109
5.3.3  树、森林与二叉树的转换 113
5.3.4  树和森林的遍历 115
5.4  哈夫曼树和判定树 117
5.4.1  哈夫曼树的定义与构造方法 117
5.4.2  哈夫曼编码 118
5.4.3  判定树 119
5.5  案例分析 120
习题五 123
第6章  图 127
6.1  图的定义和术语 127
6.2  图的存储结构 131
6.2.1  邻接矩阵 131
6.2.2  邻接表表示法 133
6.3  图的遍历 136
6.3.1  深度优先搜索 136
6.3.2  广度优先搜索 139
6.4  图的应用 141
6.4.1  图的连通性 141
*6.4.2  生成树和生成森林 143
*6.4.3  关节点和重连通分量 145
6.4.4  最小生成树 147
6.4.5  最短路径 153
*6.4.6  AOV网与拓扑排序 157
6.5  案例分析 161
习题六 166
第7章  查找 168
7.1  基本概念与术语 168
7.2  静态查找表 171
7.2.1  静态查找表结构 171
7.2.2  顺序查找 171
7.2.3  有序表的折半查找 172
7.2.4  斐波那契查找 174
7.2.5  分块查找 175
7.2.6　案例分析 176
7.3  动态查找表 179
7.3.1  二叉排序树 179
7.3.2　案例分析 182
7.4  哈希表查找（杂凑法） 186
7.4.1  哈希表与哈希方法 186
7.4.2  常用的哈希函数 187
7.4.3  处理冲突的方法 189
7.4.4  哈希表的查找分析 191
习题七 192
第8章  排序 195
8.1  基本概念 195
8.2  插入排序 196
8.2.1  直接插入排序 196
8.2.2  希尔排序 196
8.2.3　案例分析 197
8.3  交换排序 200
8.3.1  冒泡排序 200
8.3.2  快速排序 202
8.3.3　案例分析 202
8.4  选择排序 205
8.4.1  简单选择排序 205
*8.4.2  堆排序 206
8.5  二路归并排序 208
8.6  基数排序 210
8.6.1  多关键码排序 210
8.6.2  链式基数排序 211
8.7  外排序 214
8.7.1  外部排序的方法 214
*8.7.2  多路平衡归并的实现 216
习题八 218
上机实训练习 221
第2章上机实训题 221
第3章上机实训题 222
第4章上机实训题 223
第5章上机实训题 224
第6章上机实训题 225
第7章上机实训题 226
第8章上机实训题 226

1. C语言同步案例习题精解 [主编 肖朝晖]
2. C语言程序设计（微课版） [主编　夏启寿]
3. C语言程序设计实践教程 [夏启寿]
4. 单片机应用技术项目教程（C语言版）（第三版） [主编　郭志勇]
5. 数据结构——C语言（微课版） [主编 梁海英]
6. C程序设计简明教程 [黄能耿 黄致远 编著]
7. C语言程序设计实验指导与实训 [主编 倪燃]
8. 单片机原理及应用技术（C语言版） [周国运 鲁庆宾 赵天翔 编著]
9. C#程序设计教程 [主编 李祥琴]
10. C#数据库编程技术 [主编　顾家铭]
11. 基于C#的可视化编程基础 [主编 张蕾蕾 黄健]
12. C语言程序设计 [主编　杨娟　万青]
13. 物联网编程与应用（C#） [主编　王浩　王伟旗]
14. C语言程序设计 [主编 王婧 刘政宇]
15. Visual Basic程序设计教程 [主编 郭秀娟 于全通]
16. C语言程序设计项目化教程 [主编 彭琦伟 周威]
17. C语言程序设计案例教程 [主 编 刘素芬 张建军 王宏斌]
18. Visual Basic.NET程序设计上机实践教程 [主编 何振林 罗奕]
19. Visual Basic.NET程序设计 [主编 何振林 罗奕]
20. C语言程序设计（第二版） [主编 丁红 王辉]
21. 数据结构（C语言版）习题解答及实训指导 [李根强 谢月娥]
22. 数据结构（C语言版） [主编 李根强 刘浩 谢月娥]
23. C语言程序设计习题与实验指导 [主编 甄增荣 张宾]
24. C语言程序设计 [主编 甄增荣 吕晓华]
25. 数据结构（Java版） [主编 李云平]
26. C语言程序设计 [主编 吴国凤]
27. C语言程序设计实训与习题指导 [吴国凤]
28. C语言同步练习及习题精解 [肖朝晖 王艳]
29. Visual Basic程序设计（第二版） [主编 白金牛 李慧萍 邢俊凤]
30. C++ STL基础案例教程 [钟琪 著]