第1章 绪论 1
1.1 引言 1
1.2 基本概念和术语 2
1.3 算法的描述和分析 3
1.3.1 算法的描述 3
1.3.2 算法设计的要求 3
1.3.3 算法的分析 4
习题1 5
第2章 线性表 7
2.1 线性表的定义和运算 7
2.1.1 线性表的逻辑结构 7
2.1.2 线性表的基本运算 7
2.2 线性表的顺序存储结构 8
2.2.1 顺序表的概念 8
2.2.2 顺序表上基本运算的实现 9
2.3.1 单链表及其基本运算 13
2.3 线性表的链式存储结构 13
2.3.2 循环链表 21
2.3.3 双向链表 22
2.4 顺序表与链表的比较 24
2.5 线性表应用举例 24
习题2 26
3.1 栈 28
3.1.1 栈的定义和运算 28
第3章 栈和队列 28
3.1.2 栈的顺序存储结构 29
3.1.3 栈的链式存储结构 32
3.2 栈的应用举例 34
3.3 队列 37
3.3.1 队列的定义和运算 37
3.3.2 队列的顺序存储结构 38
3.3.3 队列的链式存储结构 42
3.4 队列应用举例 44
习题3 47
第4章 串和数组 49
4.1 串及其运算 49
4.1.1 串的基本概念 49
4.1.2 串的基本运算 49
4.2 串的存储结构 50
4.2.1 串的顺序存储 50
4.2.2 串的链式存储 51
4.3 串运算的实现 51
4.4 串操作应用举例 56
4.5 数组的定义 57
4.6 数组的顺序表示和实现 58
习题4 59
第5章 树 60
5.1 树的基本概念 60
5.1.1 树的定义和基本操作 60
5.1.3 树的基本术语 61
5.1.2 树的表示方法 61
5.2 二叉树 62
5.2.1 二叉树的定义和基本操作 62
5.2.2 二叉树的性质 63
5.2.3 二叉树的存储结构 64
5.3 遍历二叉树 66
5.3.1 遍历算法描述 66
5.3.2 二叉树遍历应用举例 69
5.4 线索二叉树 71
5.5 树和森林 75
5.5.1 树的存储结构 75
5.5.2 树、森林和二叉树的转换 76
5.5.3 树和森林的遍历 77
5.6 哈夫曼树及其应用 79
5.6.1 哈夫曼树的概念 79
5.6.2 哈夫曼编码 81
习题5 82
6.1.2 图的术语 84
6.1.1 图的定义 84
第6章 图 84
6.1 图的基本概念 84
6.2 图的存储结构 86
6.2.1 邻接矩阵表示法 86
6.2.2 邻接表表示法 88
6.3 图的遍历 89
6.3.1 连通图的深度优先搜索遍历 89
6.3.2 连通图的广度优先搜索遍历 90
6.4 图的最小生成树 91
6.4.1 生成树的概念 91
6.4.2 网络的最小生成树 92
6.5 最短路径 96
6.6 拓扑排序 98
6.7 图的应用举例 101
习题6 103
7.1 查找的基本概念 105
第7章 查找 105
7.2 查找的基本方法 106
7.2.1 顺序查找 106
7.2.2 折半查找 107
7.2.3 索引顺序表的查找 108
7.3 二叉排序树的查找 109
7.4 散列表 112
7.4.1 散列表的概念 112
7.4.2 散列函数的构造方法 113
7.4.3 处理冲突的方法 115
7.4.4 散列表上的运算及其分析 116
7.5 查找操作应用举例 118
习题7 119
第8章 排序 121
8.1 排序的基本概念 121
8.2 插入排序 121
8.2.1 直接插入排序 122
8.2.2 希尔排序 123
8.3 交换排序 124
8.3.1 冒泡排序 125
8.3.2 快速排序 126
8.4 选择排序 128
8.4.1 直接选择排序 128
8.4.2 堆排序 129
8.5 归并排序 133
8.6 基数排序 135
8.6.1 多关键字排序 135
8.6.2 基数排序 136
8.7 各种内部排序方法的比较 138
8.8 排序应用举例 138
习题8 141
第9章 文件 143
9.1 文件的基本概念 143
9.2 顺序文件 144
9.3 索引文件 145
9.4 ISAM文件和VSAM文件 146
9.4.1 ISAM文件 146
9.4.2 VSAM文件 147
9.5 散列文件 148
9.6 多关键字文件 149
9.6.1 多重表文件 149
9.6.2 倒排文件 150
附录 数据结构实训内容和实训指导 151
实训1 线性表及其应用 153
实训2 栈、队列及其应用 156
实训3 数组与串 160
实训4 树及其应用 162
实训5 图及其应用 165
实训6 查找 168
实训7 排序 170
参考文献 175