第1章 绪论 1
1.1从问题到程序 1
1.2有关概念和术语 3
1.3算法及算法分析 6
1.3.1算法特性 6
1.3.2算法描述 7
1.3.3算法分析 8
1.4关于数据结构的学习 10
本章小结 12
习题1 12
第2章 线性表 15
2.1线性表的逻辑结构 15
2.1.1线性表的定义 15
2.1.2线性表的基本操作 15
2.2线性表顺序存储及其操作的实现 16
2.2.1顺序表 16
2.2.2顺序表基本操作的实现 18
2.2.3顺序表的其他操作举例 21
2.3线性表的链式存储及其操作的实现 23
2.3.1单链表 23
2.3.2单链表基本操作的实现 25
2.3.3循环链表 31
2.3.4双向链表 31
2.3.5单链表的其他操作举例 33
2.4典型例题 35
本章小结 37
习题2 38
第3章 栈和队列 40
3.1栈 40
3.1.1栈的定义及其基本运算 40
3.1.2栈的存储结构和基本运算的实现 41
3.1.3栈的应用举例 43
3.1.4栈与递归的实现 47
3.2队列 51
3.2.1队列的定义及其基本运算 51
3.2.2队列的存储结构和基本运算的实现 52
3.2.3队列应用举例 57
3.3典型例题 58
本章小结 60
习题3 61
第4章 串和数组 65
4.1串 65
4.1.1串的基本概念 65
4.1.2串的基本运算 66
4.1.3串的存储结构及其基本运算的实现 67
4.1.4串的其他运算举例 69
4.2数组 70
4.2.1数组的逻辑结构和基本操作 70
4.2.2数组的存储结构 71
4.2.3稀疏矩阵 72
4.2.4矩阵的其他运算举例 76
4.3典型例题 76
本章小结 78
习题4 78
第5章 树与二叉树 81
5.1树的概念与基本操作 81
5.1.1树的定义及相关术语 81
5.1.2树的基本操作 83
5.2二叉树 83
5.2.1二叉树的基本概念 83
5.2.2二叉树的主要性质 85
5.2.3二叉树的存储结构与基本操作 86
5.2.4二叉树的遍历 89
5.2.5二叉树的其他操作举例 94
5.3树与森林 97
5.3.1树的存储 97
5.3.2树、森林与二叉树的相互转换 99
5.3.3树和森林的遍历 101
5.4最优二叉树——哈夫曼树 103
5.4.1哈夫曼树的基本概念 103
5.4.2哈夫曼树的构造算法 104
5.4.3哈夫曼编码 105
5.4.4哈夫曼编码的算法实现 107
5.5典型例题 108
本章小结 110
习题5 111
第6章 图 114
6.1图的基本概念 114
6.1.1图的定义和术语 114
6.1.2图的基本操作 116
6.2图的存储结构 117
6.2.1邻接矩阵 117
6.2.2邻接表 119
6.3图的遍历 120
6.3.1深度优先搜索 120
6.3.2广度优先搜索 122
6.4图的应用 123
6.4.1最小生成树 123
6.4.2最短路径 127
6.4.3拓扑排序 130
6.5典型例题 133
本章小结 137
习题6 137
第7章 查找 141
7.1基本概念与术语 141
7.2静态查找表 142
7.2.1静态查找表结构 142
7.2.2顺序查找 143
7.2.3有序表的折半查找 144
7.2.4分块查找 146
7.3动态查找表 147
7.4哈希表 151
7.4.1哈希表与哈希方法 151
7.4.2常用的哈希函数构造方法 152
7.43处理冲突的方法 153
7.4.4哈希表的查找算法 156
7.4.5哈希表的性能分析 156
7.5典型例题 157
本章小结 163
习题7 163
第8章 排序 167
8.1基本概念 167
8.2三种简单的排序方法 168
8.2.1直接插入排序 168
8.2.2冒泡排序 169
8.2.3简单选择排序 172
8.3希尔排序 173
8.4快速排序 174
8.5堆排序 177
8.6归并排序 179
8.7各种排序方法的比较与讨论 181
8.8典型例题 182
本章小结 185
习题8 186
第9章 实验 190
实验1顺序表的基本操作 190
实验2链表的基本操作 195
实验3栈的基本操作 201
实验4队列的基本操作 207
实验5字符串的基本操作 217
实验6二叉树的基本操作 222
实验7树的遍历和哈夫曼树 227
实验8图的基本操作 234
实验9排序 240
实验10查找 245
参考文献 251