程序设计基础包含编程语言、数据结构和算法设计与分析等内容。数据结构是提高程序设计技术和算法设计水平的关键。本书涉及经典数据结构及其算法，可作为数据结构课程学习的参考教材。内容共分三部分：第一部分包含数据结构和算法分析相关的概念、术语和抽象数据类型（ADT）描述方法（第1章）；第二部分讨论经典数据结构及相关算法（第2～7章）；第三部分讨论排序和查找类问题及其相关算法（第8～9章）。本书取材经典，内容呈现方式简洁，概念表述清晰，算法设计与描述严格遵守输入-处理-输出（IPO）规范，案例图表展示清楚。每章配有课外习题，方便读者掌握并运用所学内容。

更多科学出版社服务，请扫码获取。

1984～1991，四川大学学士、硕士； 2000～2003，中国科学院博士。 1991年迄今，历任四川师范大学助教、讲师、副教授、教授，计算数学和计算机科学与技术硕士生导师，数学科学学院教授委员会委员，信息与计算科学专业省一流专业负责人。算法分析与设计（数据挖掘、实时系统）在 SCI、EI 等期刊及国际会议上发表学术论文40余篇。先后主持、参与国家 级和省部级项目6项（含教改项目3项），累计指导硕士研究生50余人。四川省计算机协会理事，成都市龙泉驿区政协第七届委员、第八届常委，九三学社四川师范大学委员 会副主任委员

目录
第1章 绪论 1
1.1 数据结构 1
1.1.1 数据结构的一般概念 1
1.1.2 不同类型的问题对应的数据结构描述模型 2
1.1.3 数据结构研究的发展历史、内容与趋势 5
1.2 数据结构的相关概念与术语 6
1.2.1 基本概念和术语 6
1.2.2 数据结构模型描述实例分析 8
1.2.3 其他概念和术语 9
1.2.4 ADT的结构及定义方法 13
1.2.5 多形数据类型 15
1.3 ADT的表示与实现 15
1.4 算法及其分析与评价 19
1.4.1 算法及其特征 19
1.4.2 算法设计的基本要求 19
1.4.3 算法的时间效率度量方法 20
1.4.4 常见的时间复杂度函数增长率分析 22
1.4.5 算法的空间复杂度 23
1.4.6 算法方案选择的时空辩证关系 23
课外习题 23
第2章 集合与线性表 26
2.1 集合及其逻辑结构特点 26
2.2 集合的ADT描述 26
2.3 集合的表示和实现 27
2.4 线性表及其逻辑结构特点 29
2.5 线性表的ADT描述 30
2.6 线性表的顺序表示和实现 33
2.7 线性表的链式表示和实现 35
2.7.1 线性链表的概念 35
2.7.2 (动态)单链表的表示和实现 37
2.7.3 (静态)单链表的表示和实现 40
2.7.4 循环链表 44
2.7.5 双向链表 44
2.8 线性表的应用实例 47
课外习题 51
第3章 堆栈和队列 54
3.1 堆栈 54
3.1.1 现实生活中的例子 54
3.1.2 堆栈的逻辑结构特点 55
3.1.3 堆栈结构的抽象数据类型定义 56
3.1.4 堆栈结构的表示与实现方法 56
3.2 堆栈的应用 61
3.3 *堆栈与递归 68
3.3.1 递归与递归函数 68
3.3.2 n阶Hanoi塔问题 69
3.4 队列 72
3.4.1 队列的逻辑结构特点 72
3.4.2 队列的抽象数据类型定义 73
3.4.3 队列的表示与实现方法 73
3.4.4 循环队列 76
3.4.5 关于队列问题的进一步讨论 79
课外习题 80
第4章 字符串 83
4.1 字符串的类型定义 83
4.1.1 字符串的基本概念 83
4.1.2 字符串的逻辑结构特点与类型定义 84
4.2 字符串的表示和实现 85
4.2.1 定长顺序存储表示 85
4.2.2 动态顺序存储表示 86
4.2.3 块链存储表示 89
4.3 *字符串的模式匹配算法 91
4.3.1 问题的提出 91
4.3.2 KMP算法 92
4.4 字符串操作应用实例 95
4.4.1 文本编辑系统 95
4.4.2 *词索引表的建立 96
课外习题 97
第5章 数组和广义表 98
5.1 数组类型的一般定义 98
5.2 数组类型的一般表示与实现 99
5.3 矩阵的压缩存储与运算 101
5.3.1 有特殊规律的矩阵 101
5.3.2 取值稀疏的矩阵 103
5.4 广义表 112
5.4.1 广义表概述 112
5.4.2 广义表的ADT定义 113
5.4.3 广义表的存储结构 114
5.4.4 *广义表的递归算法实现 116
5.5 *广义表的应用——m元多项式的表示 120
课外习题 122
第6章 树和二叉树 125
6.1 树的概念及基本术语 125
6.1.1 树的概念 125
6.1.2 树的表示方法 126
6.1.3 树结构问题描述的基本术语 128
6.1.4 树的ADT定义 129
6.2 二叉树 130
6.2.1 二叉树概述 130
6.2.2 二叉树的性质 133
6.2.3 二叉树的存储结构 133
6.2.4 线性链表的存储结构实现和基本操作的函数声明 135
6.3 二叉树的遍历和线索二叉树 135
6.3.1 二叉树的遍历 135
6.3.2 二叉树遍历算法的应用 137
6.3.3 线索二叉树 139
6.4 树和森林 143
6.4.1 树的存储结构 143
6.4.2 森林与二叉树的转换 147
6.4.3 树和森林的遍历 148
6.5 哈夫曼树及其应用 148
6.5.1 哈夫曼树 148
6.5.2 哈夫曼编码 151
课外习题 156
第7章 图 158
7.1 图的定义及基本术语 158
7.1.1 基本术语 158
7.1.2 图的ADT描述 161
7.2 图的存储结构 162
7.2.1 引入 162
7.2.2 数组表示法 162
7.2.3 邻接表表示法 165
7.2.4 十字链表表示法 167
7.2.5 邻接多重表表示法 169
7.3 图的遍历 170
7.3.1 深度优先搜索算法 171
7.3.2 广度优先搜索算法 172
7.4 图的连通性问题 173
7.4.1 无向图的连通分量和生成树 173
7.4.2 *有向图的强连通分量 174
7.4.3 最小生成树 174
7.4.4 *关节点和重连通分量 178
7.5 有向无环图及其应用 181
7.5.1 TOP排序 183
7.5.2 关键路径 186
7.6 最短路径 190
7.6.1 单源点最短路径求解 190
7.6.2 全部顶点对的最短路径求解 193
课外习题 195
第8章 内部排序 199
8.1 基本概念 199
8.2 插入排序 200
8.2.1 直接插入排序 200
8.2.2 直接插入排序的改进算法 201
8.2.3 Shell排序 206
8.3 快速排序 207
8.4 选择排序 210
8.4.1 简单选择排序 210
8.4.2 树形选择排序 212
8.4.3 堆排序 213
8.5 归并排序 216
8.6 基数排序 217
8.6.1 多关键字排序 217
8.6.2 链式基数排序 219
8.7 各种内部排序方法的比较与优化 222
课外习题 226
第9章 查找 229
9.1 基本概念 229
9.2 静态查找表 230
9.2.1 静态查找表的ADT定义 230
9.2.2 顺序表的顺序查找 230
9.2.3 有序顺序表的查找 232
9.2.4 *静态最优查找树的查找 235
9.2.5 索引顺序表的查找 236
9.3 动态查找表 237
9.3.1 动态查找表的ADT定义 237
9.3.2 基于二叉树的排序树和平衡二叉树 238
9.3.3 *B-树和B+树 248
9.3.4 *键树 253
9.4 Hash表 257
9.4.1 Hash表概述 257
9.4.2 Hash函数的构造方法 258
9.4.3 Hash冲突处理方法 262
9.4.4 Hash表的查找效率分析 265
课外习题 266
参考文献 268
附录 269