第一章 绪论 1
第一节 引言 1
第二节 数据结构的基本概念 1
第三节 算法的概念、算法描述和算法分析 3
一、算法的概念 3
二、算法描述 4
三、算法分析 5
习题 6
第二章 线性表和数组 7
第一节 线性表及其存储表示 7
一、线性表 7
二、线性表的存储表示 8
第二节 线性表的查找、插入和删除 9
一、线性表的查找 10
二、线性表的插入和删除 12
第三节 栈和队列 14
一、栈的结构及运算 14
二、计算表达式——栈的应用举例 17
三、队列的结构及运算 19
第四节 数组的顺序分配 24
第五节 稀疏矩阵 27
第六节 线性表的应用举例 30
习题 37
第三章 链表 39
第一节 线性链表的存储表示 39
第二节 线性链表的建立、查找、插入和删除 40
一、线性链表的建立和查找 40
二、线性链表的插入和删除 45
第三节 链栈和链队列 49
一、链栈的结构及运算 49
二、链队列的结构及运算 50
第四节 循环链表 52
一、循环链表的结构 52
二、循环链表的查找、插入和删除 52
第五节 双向链表 62
一、双向链表的结构 62
二、双向链表的查找、插入和删除 63
第六节 链表的应用 68
一、多项式相加问题 68
二、约瑟夫环问题 74
习题 77
第四章 串 78
第一节 串的基本概念 78
第二节 串的基本运算 79
第三节 串的存储结构 81
一、串的静态存储结构 81
二、串的动态存储结构 82
第四节 串基本操作的实现 84
一、求子串定位函数index(s，t) 84
二、求替换运算replace(a，b，c) 85
第五节 串操作应用——文本编辑 86
习题 88
第五章 树 89
第一节 一般树的概念 89
一、一般树的定义 89
二、基本术语 89
三、树的存储结构 90
第二节 二叉树 92
一、二叉树的基本概念 92
二、二叉树的性质 94
三、二叉树的存储 95
第三节 二叉树的遍历 97
一、二叉树的遍历方式 97
二、遍历算法 97
三、由数据序列恢复二叉树 99
第四节 线索二叉树 103
一、线索二叉树的结构 103
二、线索二叉树的检索 104
第五节 二叉树的应用——表达式树 106
一、表达式树的概念 106
二、构造表达式树的方法 106
三、构造表达式树的算法 107
第六节 二叉排序树 109
一、二叉排序树的结构 109
二、建立二叉排序树的算法 109
三、在二叉排序树中删除结点 111
四、二叉查找树 113
第七节 哈夫曼树 113
一、树的路径长度和带权路径长度 113
二、哈夫曼树和哈夫曼算法 115
第八节 二叉树与树、森林之间的转换 117
一、二叉树与树之间的转换 117
二、二叉树与森林之间的转换 119
习题 120
第六章 图 122
第一节 基本术语 122
第二节 图的存储结构 124
一、邻接矩阵 124
二、邻接链表 125
三、多重邻接表 127
第三节 遍历图 128
一、深度优先搜索法 128
二、广度优先搜索法 129
第四节 最短路径 131
一、从某个源点到其他各顶点的最短路径 131
二、求每一对顶点之间的最短路径 135
第五节 拓扑排序 138
一、AOV网 138
二、拓扑排序的方法 139
第六节 关键路径 141
习题 142
第七章 查找 144
第一节 顺序查找 145
第二节 折半查找 146
第三节 分块查找 150
第四节 哈希法 151
一、哈希法查找的概念 151
二、哈希函数的构造 152
三、解决冲突的方法 155
第五节 各种查找方法的比较及应用 160
一、各种查找方法的比较 160
二、应用举例 161
习题 165
第八章 排序 166
第一节 插入排序 167
一、直接插入排序 167
二、希尔排序 169
第二节 选择排序 171
一、直接选择排序 171
二、堆排序 172
第三节 交换排序 177
一、冒泡排序 177
二、快速排序 178
第四节 归并排序 181
第五节 各种排序方法的比较及应用 184
一、各种排序方法的比较 184
二、应用举例 185
习题 189
第九章 文件 191
第一节 文件的基本知识 191
一、文件的概念 191
二、文件的存储介质 191
三、文件的种类 193
四、文件的操作 193
第二节 文件的结构 194
一、顺序文件 194
二、索引文件 195
三、索引顺序文件ISAM 196
习题 199
实验 200
实验一 线性表的查找、插入、删除 200
实验二 线性链表的查找、插入、删除 200
实验三 循环链表的操作 204
实验四 串操作运算 209
实验五 线索二叉树的检索 213
实验六 二叉排序树的建立及中序遍历 215
实验七 最短路径的实现 216
实验八 查找练习 217
实验九 学生成绩管理 218
参考文献 220