第1章 概述 1
1.1什么是数据结构 1
1.2基本概念和术语 1
1.3算法描述和算法分析 3
1.3.1算法的概念 3
1.3.2算法设计的要求 4
1.3.3算法的描述 5
1.3.4算法性能的评价 5
1.4本课程学习指导 6
1.5本章小结 7
1.6习题 7
第2章 线性表 8
2.1什么是线性表 8
2.2线性表的顺序存储结构及其算法 9
2.2.1线性表的顺序存储结构 9
2.2.2顺序表的运算 10
2.2.3顺序表应用——班级考勤统计 13
2.3线性表的链式存储结构 15
2.3.1动态内存分配及其管理 15
2.3.2线性链表 17
2.3.3循环链表 26
2.3.4双向链表 27
2.3.5静态链表 29
2.4线性链表的应用——一元多项式的表示及加法运算 30
2.5本章小结 33
2.6习题 33
2.7实训题 35
实训一 学生基本信息 35
实训二 线性链表的基本操作 35
第3章 栈和队列 36
3.1栈 36
3.1.1栈的定义 36
3.1.2栈的存储结构及其基本运算 37
3.1.3栈的应用 41
3.2队列 44
3.2.1队列的定义 44
3.2.2队列的存储结构及其基本运算的实现 45
3.2.3队列的应用 52
3.3本章小结 55
3.4习题 56
3.5实训题 56
实训一 表达式求值 56
实训二 商品货架管理 57
第4章 数组和字符串 58
4.1数组 58
4.1.1数组的定义和操作 58
4.1.2数组的顺序存储和访问 59
4.1.3数组的类型的实现 61
4.1.4特殊矩阵的压缩存储 62
4.2串 66
4.2.1字符串的基本操作 67
4.2.2定长字符串的实现 68
4.2.3可变长字符串的实现 73
4.2.4字符串的模式匹配 77
4.2.5字符串应用举例 79
4.3本章小结 81
4.4习题 81
4.5实训题 83
实训一 字符串操作 83
实训二 稀疏矩阵转置 83
第5章树 84
5.1树 84
5.1.1树的基本概念 84
5.1.2树的基本术语 85
5.1.3树的基本运算 86
5.2二叉树 86
5.2.1二叉树的概念 86
5.2.2二叉树的性质 87
5.2.3二叉树的存储结构 89
5.2.4遍历二叉树 92
5.2.5哈夫曼树和哈夫曼编码 94
5.2.6应用实例 98
5.3树和森林 103
5.3.1树的存储结构 104
5.3.2树、森林与二叉树的转换 106
5.3.3树和森林的遍历 109
5.4本章小结 110
5.5习题 111
5.6实训题 112
实训 二叉树的应用 112
第6章图 113
6.1图的定义和基本术语 113
6.1.1图的定义 113
6.1.2图的基本术语 114
6.2图的存储结构 117
6.2.1邻接矩阵 117
6.2.2邻接表 118
6.3图的遍历 120
6.3.1深度优先搜索（DFS） 120
6.3.2广度优先搜索（BFS） 122
6.4图的应用 125
6.4.1最小生成树 125
6.4.2最短路径 128
6.5拓扑排序 135
6.5.1 AOV网 135
6.5.2拓扑排序 136
6.6本章小结 139
6.7习题 140
6.8实训题 141
实训 图的存储和遍历 141
第7章 排序 143
7.1基本概念 143
7.2插入排序 144
7.2.1直接插入排序 144
7.2.2希尔排序 146
7.3交换排序 148
7.3.1冒泡排序 148
7.3.2快速排序 149
7.4选择排序 151
7.4.1简单选择排序 152
7.4.2堆排序 153
7.5归并排序 156
7.6基数排序 159
7.6.1多关键字排序 159
7.6.2链式基数排序 160
7.7排序方法的比较 164
7.8本章小结 165
7.9习题 166
7.10实训题 166
实训 排序算法的实现 166
第8章 查找 168
8.1查找的基本概念 168
8.2基于线性表的查找方法 169
8.2.1顺序查找法 169
8.2.2折半查找法 170
8.2.3分块查找法——索引顺序查找 172
8.3树表查找法 173
8.3.1二叉排序树 173
8.3.2平衡二叉树 178
8.4哈希表查找 185
8.4.1哈希表与哈希查找 185
8.4.2构造哈希函数的方法 186
8.4.3处理冲突的方法 188
8.4.4哈希表的查找分析 194
8.5本章小结 196
8.6习题 196
8.7实训题 199
实训 查找的实现 199
附录 200
参考文献 260