章绪论1
1.1什么是数据结构1
1.2数据结构的概念及有关术语1
1.3算法和算法分析5
习题 7
第2章线性表9
2.1线性表的定义9
2.2线性表的基本运算9
2.3顺序存储结构线性表10
2.3.1线性表的顺序存储结构10
2.3.2顺序存储结构线性表的基本运算11
2.3.3顺序存储结构线性表的应用15
2.4链式存储结构线性表20
2.4.1单链表20
2.4.2循环链表28
2.4.3双向链表29
2.4.4静态链表30
2.4.5链式存储结构线性表的应用31
2.5小结38
习题 38
第3章栈和队列42
3.1栈42
3.1.1栈的定义及基本运算42
3.1.2顺序存储结构栈的基本运算42
3.1.3链式存储结构栈的基本运算45
3.1.4栈的应用实例47
3.1.5栈与递归48
3.2队列50
3.2.1队列的定义及基本运算50
3.2.2顺序存储结构队列的基本运算50
3.2.3链式存储结构队列的基本运算53
3.2.4队列的应用55
3.3小结57
习题 58
第4章串61
4.1串的概念及基本运算61
4.1.1串的基本概念61
4.1.2串的基本运算62
4.2顺序存储结构串的运算63
4.2.1串的定长顺序存储结构63
4.2.2定长顺序存储结构串的基本运算64
4.3串的堆分配存储结构及其运算66
4.3.1串的堆分配存储结构66
4.3.2堆分配存储结构串的运算66
4.4串的链式存储结构及基本运算68
4.4.1串的链式存储结构68
4.4.2链串的基本运算69
4.5串的模式匹配70
4.5.1简单模式匹配算法——BF算法70
4.5.2无回溯的模式匹配算法——KMP算法72
*4.5.3next函数的改进77
4.6小结79
习题 79
第5章数组和广义表81
5.1数组81
5.1.1数组的定义及逻辑结构81
5.1.2数组的存储结构83
5.1.3特殊矩阵的压缩存储84
5.1.4数组应用举例88
5.2广义表91
5.2.1广义表的定义91
5.2.2广义表的存储结构93
5.2.3广义表基本操作实现94
5.2.4广义表应用举例97
5.3小结98
习题 99
第6章树和二叉树102
6.1树的定义及有关术语102
6.1.1树的定义102
6.1.2常用术语102
6.2二叉树103
6.2.1二叉树的定义103
6.2.2二叉树的性质105
6.2.3二叉树的存储结构105
6.2.4二叉树的遍历107
6.2.5线索二叉树113
6.2.6哈夫曼树117
6.3树和森林122
6.3.1树的存储结构122
6.3.2树或森林与二叉树的转换124
6.3.3树和森林的遍历125
6.4小结126
习题 126
第7章图130
7.1图的定义及有关术语130
7.2图的存储结构134
7.2.1邻接矩阵134
7.2.2邻接表137
7.2.3十字链表139
*7.2.4邻接多重表141
7.3图的遍历143
7.3.1深度优先搜索143
7.3.2广度优先搜索145
7.3.3图的连通性148
7.4最小生成树150
7.4.1普里姆算法150
7.4.2克鲁斯卡尔算法153
7.5有向无环图及其应用156
7.5.1拓扑排序156
7.5.2关键路径161
7.6最短路径166
7.6.1单源最短路径166
7.6.2每一对顶点之间的最短路径169
7.7图的应用实例172
7.8小结174
习题 175
第8章查找180
8.1 查找的有关概念180
8.2线性表的查找181
8.2.1顺序查找181
8.2.2二分查找182
8.2.3分块查找184
8.3树表的查找185
8.3.1二叉排序树185
8.3.2平衡二叉树190
8.3.3B-树193
8.3.4B+树196
8.4哈希查找197
8.4.1哈希表的概念及哈希函数的构造197
8.4.2哈希表的建立199
8.4.3冲突的处理方法199
8.4.4哈希查找的实现201
8.5小结202
习题 203
第9章排序206
9.1排序的有关概念206
9.2插入排序207
9.2.1直接插入排序207
9.2.2折半插入排序208
9.2.3希尔排序209
9.3交换排序211
9.3.1冒泡排序211
9.3.2快速排序212
9.4选择排序214
9.4.1简单选择排序214
9.4.2堆排序216
9.5归并排序219
9.6基数排序221
9.7多关键字排序223
9.8小结224
习题 225
参考文献229

“数据结构”是计算机科学及相关学科的一门核心专业基础课，主要讨论各种数据结构在计算机中的存储表示及算法实现，是一门集技术性、理论性和实践性于一体的课程。本书综合了诸多院校的课程教学大纲以及教育部2018年考研大纲中《计算机学科专业基础综合考试大纲》进行编写，书中所有算法描述均采用标准C语言。教材内容安排合理，难易程度适中，讲解深入浅出。每部分内容都配备有对应的程序实例和丰富的习题，可有效增强读者对经典算法的理解和运用能力。全书共9章，内容包括绪论、线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、排序。本书主要面向本科及大中专计算机及相关专业的在校学生和具有C语言程序设计基础的数据结构自学者，既可作为高校数据结构课程的教材，又可供从事软件设计和开发的技术人员参考。