数据结构

第1章绪论1
1.1基本术语1
1.2算法的概念4
1.3算法描述6
1.4算法分析7
1.4.1时间复杂度8
1.4.2空间复杂度11
1.5算法设计的基本步骤11
习题12

第2章线性表15
2.1线性表的概念和基本操作15
2.1.1线性表的定义15
2.1.2线性表的基本操作17
2.2线性表的顺序存储结构18
2.2.1数组——线性表的顺序存储结构18
2.2.2数组中基本操作的实现19
2.2.3操作的时间分析22
2.3线性表的链式存储结构23
2.3.1单链表和指针23
2.3.2单链表的基本操作25
2.3.3链表的实现30
2.3.4单链表的其他操作31
2.4循环链表及其操作33
2.5双向链表及其操作36
2.5.1双向链表的构造36
2.5.2双向链表的插入与删除算法37
习题39

第3章堆栈和队列43
3.1堆栈的概念及操作43
3.1.1堆栈的定义43
3.1.2堆栈的有关操作44
3.2堆栈的顺序存储结构45
3.3堆栈的链式存储结构47
3.4堆栈的应用举例49
3.4.1算术表达式的求值49
3.4.2在递归问题中的应用51
3.5队列的概念及操作52
3.5.1队列的定义52
3.5.2队列的有关操作53
3.6队列的顺序存储结构53
3.7队列的链式存储结构57
3.8综合实例——算符优先算法59
习题63

第4章数组65
4.1数组的定义和操作65
4.2数组的顺序存储结构66
4.3特殊矩阵的压缩存储68
4.3.1对称矩阵的压缩存储68
4.3.2对角矩阵的压缩存储69
4.4稀疏矩阵的表示法70
4.4.1三元组表示法70
4.1.2稀疏矩阵的顺序存储71
4.1.3稀疏矩阵的链式存储71
4.1.4稀疏矩阵的运算*73
习题76

第5章字符串77
5.1字符串的概念和基本操作77
5.1.1字符串的定义77
5.1.2字符串的基本操作78
5.2字符串的存储结构79
5.2.1字符串的顺序存储结构80
5.2.2字符串的链式存储结构81
5.3字符串操作的实现82
习题84

第6章广义表85
6.1广义表的定义85
6.2广义表的存储结构87
6.3广义表的操作88
习题89

第7章树与二叉树91
7.1树的概念91
7.1.1树的定义91
7.1.2树的逻辑表示法93
7.1.3树的基本术语94
7.1.4树的基本操作95
7.2二叉树96
7.2.1二叉树的定义96
7.2.2二叉树的基本操作97
7.2.3二叉树的性质98
7.3二叉树的存储结构101
7.3.1二叉树的顺序存储结构101
7.3.2二叉树的链式存储结构102
7.4二叉树的遍历104
7.4.1遍历的概念104
7.4.2遍历的算法106
7.5线索二叉树*108
7.5.1二叉树的线索化108
7.5.2利用线索进行遍历111
7.6二叉排序树112
7.6.1二叉排序树的定义112
7.6.2二叉排序树的查找113
7.6.3二叉排序树的插入和生成114
7.6.4二叉排序树中结点的删除117
7.7哈夫曼树120
7.7.1哈夫曼树的基本术语120
7.7.2哈夫曼树的构造121
7.7.3哈夫曼编码122
7.8树和森林123
7.8.1树的存储结构124
7.8.2二叉树与树.森林之间的转换126
习题127

第8章图131
8.1图的基本概念131
8.1.1图的定义131
8.1.2图的基本术语132
8.1.3图的基本操作135
8.2图的存储结构136
8.2.1邻接矩阵（数组）136
8.2.2邻接表137
8.2.3邻接多重表138
8.2.4邻接表的生成算法140
8.3图的遍历140
8.3.1DFS和BFS的基本思想141
8.3.2DFS和BFS算法142
8.3.3非连通图的遍历148
8.3.4DFS和BFS算法的应用149
8.4网的最小生成树*151
8.5最短路径*154
8.6拓扑排序156
习题160

第9章查找165
9.1顺序查找165
9.2二分查找167
9.3分块查找170
9.4树表的查找*173
9.5哈希表查找180
9.5.1哈希表180
9.5.2哈希函数的构造方法181
9.5.3冲突解决的方法183
习题186

第10章排序189
10.1排序的概念189
10.2插入排序190
10.3快速排序191
10.4选择排序197
10.5归并排序202
10.6小结203
习题204

实验指导书207
实验一顺序表的插入与删除207
实验二单链表的插入与删除208
实验三堆栈的操作208
实验四二叉排序树的构造与查找209
实验五冒泡排序210
实验六快速排序211

参考文献212