第1章 绪论 1
1.1数据结构的基本概念 1
1.1.1基本术语 1
1.1.2数据结构 2
1.1.3研究数据结构的方法 5
1.2抽象数据类型 5
1.2.1数据类型 5
1.2.2抽象数据类型 6
1.3算法 7
1.3.1算法概述 7
1.3.2算法描述 8
1.3.3算法性能评价 10
1.4本章小结 11
练习题1 12
第2章 线性表 14
2.1线性表的定义及其基本操作 14
2.1.1线性表的定义 14
2.1.2线性表的基本操作 14
2.2线性表的顺序存储结构及基本操作的实现 15
2.2.1顺序表 15
2.2.2顺序表基本操作的实现 17
2.2.3顺序表应用举例 19
2.3线性表的链式存储结构及基本操作的实现 21
2.3.1单链表的基本概念 21
2.3.2单链表基本操作的实现 22
2.3.3循环链表 28
2.3.4双向链表 29
2.4顺序表和链表的比较 31
2.5本章小结 32
练习题2 33
第3章 栈和队列 36
3.1栈 36
3.1.1栈的定义及其基本操作 36
3.1.2栈的顺序存储结构及操作的实现 37
3.1.3栈的链式存储结构及操作的实现 39
3.2栈与递归 40
3.2.1递归的基本概念 41
3.2.2递归的实现 41
3.2.3递归设计 42
3.3栈的应用 43
3.3.1数据转换 43
3.3.2表达式求值 44
3.4队列 49
3.4.1队列的定义及基本操作 49
3.4.2队列的顺序存储结构及基本操作的实现 50
3.4.3队列的链式存储结构及基本操作的实现 54
3.5队列的应用 56
3.5.1报数问题 56
3.5.2打印杨辉三角形 57
3.6本章小结 58
练习题3 59
第4章 数组和矩阵 61
4.1数组 61
4.1.1数组的定义 61
4.1.2数组的顺序存储结构 61
4.2特殊矩阵的压缩存储 64
4.2.1对称矩阵 64
4.2.2三角矩阵 66
4.2.3带状矩阵 66
4.3稀疏矩阵的压缩存储 67
4.3.1三元组表 68
4.3.2十字链表 70
4.4本章小结 72
练习题4 72
第5章串 74
5.1串的定义及基本操作 74
5.1.1串的定义 74
5.1.2串的基本操作 75
5.2串的存储结构 75
5.2.1串的顺序存储结构 76
5.2.2串的链式存储结构 77
5.3串的模式匹配 78
5.3.1 Brute-Force算法 78
5.3.2 KMP算法 80
5.4串的应用 82
5.5本章小结 84
练习题5 84
第6章 广义表 86
6.1广义表的定义及基本操作 86
6.1.1广义表的定义 86
6.1.2广义表的基本操作 87
6.2广义表的存储结构 87
6.2.1头尾表示法 88
6.2.2孩子兄弟表示法 88
6.3广义表基本操作的实现 89
6.4本章小结 91
练习题6 91
第7章 树与二叉树 93
7.1树 93
7.1.1树的定义 93
7.1.2树的基本术语 94
7.1.3树的表示 95
7.1.4树的基本操作 95
7.2二叉树 96
7.2.1二叉树的基本概念 96
7.2.2二叉树的性质 97
7.2.3二叉树的基本操作 98
7.2.4二叉树的存储 99
7.3二叉树的遍历 101
7.3.1先序遍历 101
7.3.2中序遍历 102
7.3.3后序遍历 102
7.3.4层次遍历 102
7.4线索二叉树 103
7.4.1线索二叉树的概念 103
7.4.2线索化二叉树 104
7.5哈夫曼树及其应用 106
7.5.1哈夫曼树的定义 107
7.5.2哈夫曼树的构造 107
7.5.3哈夫曼树的构造算法 108
7.5.4哈夫曼树的应用 109
7.6树、森林和二叉树的转换 113
7.6.1树的存储结构 113
7.6.2树、森林转换成二叉树 115
7.6.3二叉树还原成树或森林 116
7.7本章小结 116
练习题7 117
第8章图 120
8.1图的基本概念 120
8.1.1图的意义 120
8.1.2图的相关术语 120
8.1.3图的基本操作 124
8.2图的存储结构 124
8.2.1 邻接矩阵 124
8.2.2 邻接表 126
8.2.3十字链表 127
8.3图的遍历 129
8.3.1深度优先搜索遍历 129
8.3.2广度优先搜索遍历 130
8.4最小生成树 132
8.4.1生成树和最小生成树 132
8.4.2普里姆（Prim）算法 133
8.4.3克鲁斯卡尔（Kruskal ）算法 134
8.5最短路径 136
8.5.1从一个源点到其他各顶点的最短路径 137
8.5.2每对顶点之间的最短路径 139
8.6本章小结 140
练习题8 141
第9章 查找 144
9.1查找的基本概念 144
9.2静态查找 146
9.2.1顺序查找 146
9.2.2折半查找 147
9.2.3分块查找 149
9.3动态查找 150
9.3.1二叉排序树 150
9.3.2平衡二叉树 155
9.3.3 B-树 156
9.4哈希查找 157
9.4.1哈希查找的基本概念 158
9.4.2哈希函数的构造 158
9.4.3解决冲突的方法 159
9.5本章小结 161
练习题9 161
第10章 排序 164
10.1排序的基本概念 164
10.2插入排序 165
10.2.1直接插入排序 165
10.2.2希尔排序 167
10.3交换排序 168
10.3.1冒泡排序 168
10.3.2快速排序 169
10.4选择排序 171
10.4.1简单选择排序 171
10.4.2堆排序 173
10.5归并排序 176
10.6基数排序 178
10.6.1基数排序的基本概念 178
10.6.2链式基数排序 179
10.7外部排序 182
10.7.1归并排序法 182
10.7.2多路平衡归并 183
10.8本章小结 184
练习题10 185
参考文献 187