第1章 绪论 1
1．1 数据结构的基本概念和术语 1
1．1．1 引言 1
1．1．2 数据结构有关概念及术语 3
1．1．3 数据结构和抽象数据类型(ADT) 3
1．2 算法描述与分析 4
1．2．1 什么是算法 4
1．2．2 算法描述工具——C语言 5
1．2．3 算法分析技术初步 6
习题一 7
第2章 线性表 9
2．1 线性表的定义及其运算 9
2．1．1 线性表的定义 9
2．1．2 各种运算简介 9
2．2 线性表的顺序存储结构(向量) 10
2．2．1 顺序存储结构(向量) 10
2．2．2 向量中基本运算的实现 10
2．3 线性表的链表存储结构 12
2．3．1 单链表与指针 12
2．3．2 单链表的基本运算 13
2．4 循环链表和双向链表 17
2．4．1 循环链表 17
2．4．2 双向链表 18
2．4．3 顺序存储结构与链表存储结构的综合分析与比较 19
2．5 多项式相加问题 19
2．5．1 多项式相加的链表存储结构 19
2．5．2 多项式相加的算法实现 20
2．6 线性表的算法实现举例 21
2．6．1 实现线性表顺序存储结构及运算的C语言源程序 21
2．6．2 单链表处理的C语言源程序 23
习题二 25
第3章 栈和队列 26
3．1 栈 26
3．1．1 栈的定义及其运算 26
3．1．2 栈的顺序存储结构(向量) 27
3．1．3 栈的链表存储结构 30
3．1．4 栈的应用 31
3．2 队列 36
3．2．1 队列的定义及运算 36
3．2．2 队列的顺序存储结构(向量) 37
3．2．3 队列的链表存储结构 39
3．3 栈和队列的算法实现举例 42
习题三 46
第4章 串 47
4．1 串的基本概念 47
4．2 串的存储结构 48
4．2．1 串的顺序存储 48
4．2．2 串的链表存储 49
4．2．3 串变量的存储映象 50
4．3 串的运算 50
4．3．1 串的运算简介 50
4．3．2 串的匹配运算 53
4．4 文本编辑 56
习题四 58
第5章 数组和广义表 59
5．1 数组的基本概念 59
5．1．1 数组的概念 59
5．1．2 数组的顺序表示 61
5．1．3 特殊矩阵的压缩存储 62
5．2 稀疏矩阵的三元组存储 63
5．2．1 三元组表 64
5．2．2 稀疏矩阵的运算 64
5．3 稀疏矩阵的十字链表存储 66
5．3．1 十字链表的组成 67
5．3．2 十字链表的有关算法 68
5．4 广义表 69
5．4．1 广义表的概念和特性 69
5．4．2 广义表的存储结构 70
5．4．3 求广义表的深度 71
5．4．4 广义表的输出 73
5．4．5 建立广义表的存储结构 73
5．5 迷宫问题 75
习题五 78
第6章 树 80
6．1 树的基本概念和术语 80
6．1．1 树的定义 80
6．1．2 树的常用术语 81
6．1．3 树的表示方法 81
6．2 二叉树 82
6．2．1 二叉树的定义 82
6．2．2 二叉树的重要性质 82
6．2．3 二叉树的存储结构 83
6．2．4 二叉树二叉链表的一个生成算法 84
6．3 遍历二叉树 85
6．3．1 先根遍历 86
6．3．2 中根遍历 87
6．3．3 后根遍历 88
6．3．4 二叉树遍历算法的应用 90
6．4 线索二叉树 91
6．4．1 线索二叉树的基本概念 91
6．4．2 线索二叉树的逻辑表示图 92
6．4．3 中根次序线索化算法 93
6．4．4 在中根线索树上检索某结点的前趋或后继 95
6．4．5 在中根线索树上遍历二叉树 95
6．5 二叉树、树和森林 96
6．5．1 树的存储结构 96
6．5．2 树与二叉树之间的转换 96
6．5．3 森林与二叉树的转换 98
6．5．4 一般树或森林的遍历 99
6．6 树的应用 100
6．6．1 二叉排序树 100
6．6．2 哈夫曼树及其应用 103
6．7 二叉树的建立和遍历C语言源程序示例 107
习题六 110
第7章 图 111
7．1 图的基本概念和术语 111
7．1．1 图的基本概念 111
7．1．2 路径和回路 112
7．1．3 连通图 112
7．1．4 顶点的度 113
7．2 图的存储结构 113
7．2．1 邻接矩阵 113
7．2．2 邻接链表 114
7．3 图的遍历和求图的连通分量 115
7．3．1 图的建立 115
7．3．2 图的遍历 116
7．3．3 求图的连通分量 118
7．4 图的生成树 119
7．4．1 生成树的概念 119
7．4．2 最小生成树 119
7．4．3 普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法 121
7．5 最短路径 124
7．5．1 单源顶点最短路径问题求解 124
7．5．2 求有向网中每对顶点间的路径 126
7．6 有向无环图及应用 128
7．6．1 拓扑排序 128
7．6．2 关键路径 131
7．7 图的算法C语言程序实现举例 137
7．7．1 无向图的邻接表的建立和遍历 137
7．7．2 有向无环图的拓扑排序和求关键路径 140
习题七 145
第8章 查找 147
8．1 基本概念 147
8．2 静态查找表 148
8．2．1 顺序表的查找 148
8．2．2 有序表的查找 150
8．2．3 索引顺序表的查找 153
8．3 动态查找表 154
3．3．1 二叉排序树和二叉平衡树 154
8．3．2 B-树和B+树 160
8．4 哈希表及其查找 164
8．4．1 哈希表与哈希函数 164
8．4．2 构造哈希函数的常用方法 165
8．4．3 解决冲突的主要方法 167
8．5 哈希表算法实现C语言源程序 171
习题八 173
第9章 排序 175
9．1 排序基本概念 175
9．2 插入排序 175
9．2．1 直接插入排序 176
9．2．2 折半插入排序 176
9．2．3 希尔排序 177
9．3 交换排序 178
9．3．1 冒泡排序 178
9．3．2 快速排序 179
9．4 选择排序 182
9．4．1 简单选择排序 183
9．4．2 堆排序 183
9．5 归并排序 187
9．6 基数排序 188
9．7 内部排序总结 192
9．8 有关排序算法的C语言源程序 193
9．9 多路归并用于外排序的简介 198
习题九 200
第10章 文件 201
10．1 文件的基本概念 201
10．1．1 文件 201
10．1．2 外存储器及信息特点 203
10．2 文件的组织 204
10．2．1 顺序文件 205
10．2．2 散列文件 205
10．2．3 索引文件 206
10．2．4 索引顺序文件 207
10．3 多关键字文件 209
10．3．1 多重表文件 209
10．3．2 倒排文件 210
习题十 211
第11章 数据结构程序设计及其它 213
11．1 数据结构程序设计 213
11．1．1 算法书写规范 213
11．1．2 实习步骤规范 214
11．2 实习报告范例 216
第12章 数据结构与面向对象程序设计(OOP) 221
12．1 面向对象程序设计的引入 221
12．1．1 面向对象的基本概念 221
12．1．2 面向对象的程序设计方法概要 222
12．2 面向对象的数据结构程序设计举例 224
12．2．1 线性表的程序设计 225
12．2．2 堆栈的程序设计举例 229
附录 233
附录A C语言的运算符和结合性 233
附录B C语言常用语法提要 234
附录C C库函数 236
参考文献 239