目 录 1
第一章数据结构与算法 1
§1.1数据结构的概念 1
§1.1.1什么是数据结构 1
§1.1.2为什么要学习数据结构 2
§1.1.3数据结构的分类 2
§1.2算法 4
§1.2.1算法的概念 4
§1.2.2算法的分析 5
§1.2.3设计算法的基本步骤 9
§1.2.4数据结构与算法的关系 9
§1.2.5算法设计中所用的语言 10
习题 12
第二章串 14
§2.1串的概念 14
§2.2串的存贮结构 15
§2.3.3求子串的运算 16
§2.3.2求串的长度运算 16
§2.3串的运算 16
§2.3.1串的联接运算 16
§2.3.4定位运算 17
§2.3.5置换运算 17
§2.4串的模式匹配 18
习题 22
第三章线性表 23
§3.1线性表的定义及运算 23
§3.2线性表的存贮结构 24
§3.3栈 25
§3.3.1栈的定义及其运算 25
§3.3.2栈的应用 27
§3.3.3多个栈的情况 30
§3.4队列 33
§3.4.1队列的定义及运算 33
§3.4.2队列的顺序表示 34
§3.4.3循环队列 35
习题 36
第四章链表 39
§4.1线性表的链接分配 39
§4.2链接的栈和队列 45
§4.3可利用空间表 46
§4.4循环链表 47
§4.5多项式加法 48
§4.6等价关系的处理 54
§4.7双重链表和动态存贮管理 58
§4.8广义表 67
习题 69
第五章数组 72
§5.1数组的顺序分配 72
§5.2稀疏数组 76
§5.3正交链表与稀疏数组 79
习题 83
第六章树 85
§6.1树和树的存贮结构 85
§6.1.1树的定义 86
§6.1.2基本术语 86
§6.1.3树的存贮结构 87
§6.2二叉树 88
§6.2.1二叉树的递归定义 88
§6.2.2二叉树的性质 88
§6.2.3二叉树的存贮结构 92
§6.3遍历二叉树 93
§6.3.1前序遍历 94
§6.3.2中序遍历 94
§6.3.3后序遍历 97
§6.4线索二叉树 97
§6.5对一般树及森林的研究 103
§6.5.1一般树的二叉树表示 103
§6.5.2森林的二叉树表示 105
§6.5.3树和森林的遍历 106
§6.5.4树的其它表示法 107
§6.6树的路径长度及哈夫曼算法 111
§6.6.1树的路径长度 111
§6.6.2 哈夫曼树 114
§6.7树的应用 117
§6.7.1集合的表示法 117
§6.7.2判定树 121
习题 123
第七章图 125
§7.1图的基本概念 125
§7.2图的存贮结构 128
§7.2.1图的矩阵表示 128
§7.2.2图的邻接表表示 130
§7.2.3图的其它表示形式 132
§7.3.1图的遍历 134
§7.3图的遍历和求图的连通分量 134
§7.3.2求图的连通分量 138
§7.4有向图的处理 138
§7.4.1单源最短路径 139
§7.4.2每对结点之间的最短路径 142
§7.4.3拓扑排序 143
§7.4.4关键路径 146
§7.5无向图的处理 149
习题 152
第八章内部排序 154
§8.1插入排序 154
§8.2归并排序 156
§8.3快速排序 161
§8.4选择排序 164
§8.5堆排序 168
§8.6基数排序 172
习题 175
§8.7各种内排序方法比较 175
第九章外部排序 177
§9.1外部设备简介 177
§9.1.1磁带 177
§9.1.2磁盘 178
§9.2.2一路平衡归并排序 178
§9.3多路平衡归并排序 181
§9.4多阶段归并排序 182
§9.5初始归并段的产生 184
§9.6最佳归并排序 187
习题 189
第十章数据查找 190
§10.1查找及其效率 190
§10.2顺序查找 191
§10.3二分查找 192
§10.4二叉排序树查找 195
§10.5哈希查找 197
§10.5.1哈希函数的构造技术 198
§10.5.2 哈希冲突的处理方法 200
§10.5.3哈希法的分析 205
10.6分块查找 206
习题 210
第十一章文件 211
§11.1文件的基本概念 211
§11.1.1术语 211
§11.1.2文件的存贮与组织 212
§11.2顺序文件 213
§11.3随机组织文件 215
§11.3.1直接存取文件 215
§11.3.2索引文件 217
§11.3.3链表文件 222
§11.4 B－树 223
习题 226
第十二章数据结构示例 228
参考文献 250