目录
配套资源
第1章绪论1
1.1认识数据结构1
1.1.1图书馆书目自动检索系统1
1.1.2人机对弈2
1.1.3比赛时间安排2
1.2基本概念和术语4
1.3算法与算法分析8
1.3.1算法的概念8
1.3.2算法的描述方式9
1.3.3算法评价标准11
1.3.4算法分析11
1.4“数据结构”课程的形成和发展14
课后练习15
第2章线性表16
2.1线性表的定义及逻辑结构16
2.1.1线性表的定义、概念16
2.1.2线性表的常用运算17
2.1.3线性表的ADT描述17
2.2线性表的顺序存储结构及算法17
2.2.1线性表的顺序存储结构17
2.2.2线性表的顺序存储算法18
2.3线性表的链式存储结构及算法23
2.3.1线性表的链式存储结构23
2.3.2线性表的链式存储算法24
2.4线性表的应用40
2.4.1链表的合并40
2.4.2一元多项式的相加43
2.5顺序表和链表的比较47
课后练习48第3章栈49
3.1栈的定义及逻辑定义49
3.1.1栈的定义49
3.1.2栈的常用运算50
3.1.3栈的ADT描述50
3.2栈的顺序存储结构及运算51
3.2.1栈的顺序存储结构51
3.2.2顺序栈的操作52
3.2.3顺序栈的例子55
3.3栈的链式存储及运算56
3.3.1栈的链式存储结构56
3.3.2链栈的操作57
3.3.3顺序栈与链栈小结61
3.4两栈共享62
3.5栈与递归67
3.5.1栈的举例67
3.5.2递归69
3.6栈的应用71
3.6.1回文71
3.6.2表达式括号匹配72
3.6.3算术表达式求值74
课后练习83
第4章队列84
4.1队列的概念及特征84
4.1.1队列的概念84
4.1.2队列的特征84
4.1.3队列的常用运算85
4.1.4队列的ADT描述85
4.2队列与计算机系统85
4.2.1解决主机与外部设备之间速度不匹配的问题85
4.2.2解决由多用户引起的资源竞争问题86
4.3队列的顺序存储结构与操作86
4.3.1队列的顺序存储结构86
4.3.2顺序队列的操作87
4.3.3顺序队列的溢出及解决方法91
4.4循环队列93
4.4.1循环队列存储及表示93
4.4.2循环队列的操作94
4.5队列的链式存储结构与操作97
4.5.1队列链式存储结构97
4.5.2链队列的两种形式97
4.5.3链队列的操作98
4.5.4循环队列和链队列的对比101
4.6队列的应用102
4.6.1舞伴问题102
4.6.2小猫钓鱼游戏105
4.6.3刘谦魔术揭秘108
课后练习110
第5章数组、特殊矩阵111
5.1数组的逻辑结构及ADT描述111
5.1.1数组的概念111
5.1.2数组的逻辑结构111
5.1.3数组的操作112
5.1.4数组的ADT描述114
5.2数组的顺序存储结构及运算114
5.2.1二维数组的顺序存储114
5.2.2三维数组的顺序存储116
5.2.3n维数组的顺序存储116
5.2.4数组的顺序存储小结116
5.3特殊矩阵的压缩存储117
5.3.1对称矩阵的压缩存储117
5.3.2三角矩阵的压缩存储118
5.3.3带状矩阵的压缩存储119
5.4稀疏矩阵的压缩存储120
5.4.1稀疏矩阵的定义120
5.4.2稀疏矩阵的存储结构120
5.5线性结构小结121
课后练习122
第6章树和二叉树123
6.1树的概念124
6.1.1树的定义124
6.1.2树的数据结构定义及ADT描述125
6.1.3树的基本术语126
6.1.4树的表示方法127
6.1.5树的存储结构129
6.2二叉树131
6.2.1二叉树的定义性质131
6.2.2二叉树的存储结构134
6.2.3二叉树的遍历141
6.2.4二叉树的应用157
6.3树、森林与二叉树的关系172
6.3.1树、森林与二叉树的转换172
6.3.2树的遍历174
课后练习175
第7章查找176
7.1查找的基本概念176
7.2静态查找177
7.2.1顺序查找177
7.2.2折半查找180
7.2.3分块查找184
7.3动态查找188
7.3.1树状查找188
7.3.2散列查找196
课后练习202
第8章排序204
8.1排序的基本概念204
8.1.1排序204
8.1.2排序的分类204
8.1.3排序的特性205
8.1.4排序的时间开销205
8.2排序算法205
8.2.1插入排序205
8.2.2交换排序211
8.2.3选择排序219
8.2.4归并排序225
8.2.5基数排序228
8.3排序算法比较229
课后练习230
第9章图231
9.1图的概念231
9.1.1图的定义231
9.1.2图的分类232
9.1.3图的基本术语232
9.2图的存储235
9.2.1邻接矩阵存储结构236
9.2.2邻接表存储结构240
9.2.3图存储结构小结245
9.3图的遍历246
9.3.1深度优先搜索法246
9.3.2广度优先搜索法248
9.4图的应用254
9.4.1最小生成树254
9.4.2最短路径261
9.4.3拓扑排序262
课后练习265
参考文献266
