第1章 绪论 1
1.1什么是数据结构 1
1.2概念、术语 2
1.3算法的描述及分析 3
1.3.1算法的描述方法 3
1.3.2时间复杂度 4
1.3.3空间复杂度 5
1.3.4算法分析实例 5
习题1 6
第2章 线性表 8
2.1逻辑结构 8
2.2顺序存储结构 9
2.2.1顺序存储结构的概念 9
2.2.2顺序存储结构下的操作 10
2.2.3效率分析 11
2.2.4顺序存储结构的特点 12
2.3链式存储结构 12
2.3.1链式存储结构的概念 12
2.3.2链式存储结构下的操作 13
2.3.3链式存储结构的特点 18
2.4单向循环链表 18
2.5双向链表 20
2.6一元多项式的存储、运算 22
习题2 25
第3章 栈和队列 27
3.1栈、队列的应用背景 27
3.1.1栈的应用背景 27
3.1.2队列的应用背景 27
3.2堆栈 27
3.2.1栈的定义和基本运算 27
3.2.2栈的表示和实现 28
3.2.3栈的应用 32
3.3队列 40
3.3.1队列的定义及运算 40
3.3.2队列的存储结构 41
3.3.3队列的应用 44
习题3 45
第4章串 47
4.1串及其操作 47
4.1.1串的逻辑结构 47
4.1.2基本运算 48
4.2串的存储结构 48
4.2.1顺序存储结构 48
4.2.2链式存储结构 49
4.2.3堆存储结构 50
4.3串的基本运算实现 51
4.4串的模式匹配运算 52
4.4.1 BF算法（Brute-Force） 52
4.4.2无回溯的模式匹配算法（KMP算法） 56
习题4 59
第5章 数组和广义表 60
5.1数组的定义、运算 60
5.2数组的顺序存储结构 61
5.3矩阵的压缩存储 62
5.3.1特殊矩阵 62
5.3.2稀疏矩阵 64
5.4广义表 69
5.4.1广义表定义 70
5.4.2广义表的存储结构 70
5.4.3广义表的基本操作 72
习题5 73
第6章 树 75
6.1树结构的定义和基本操作 75
6.1.1树的定义 75
6.1.2树的基本术语 76
6.1.3树的基本操作 76
6.2二叉树 77
6.2.1定义及其操作 77
6.2.2二叉树的性质 77
6.2.3二叉树的存储结构 78
6.3遍历二叉树 80
6.3.1二叉树遍历的递归算法 80
6.3.2二叉树遍历的非递归算法 82
6.3.3二叉树的层次遍历算法 84
6.3.4遍历算法的应用 85
6.4树和森林 88
6.4.1树的存储结构 88
6.4.2树与二叉树的转换 91
6.4.3森林与二叉树的转换 91
6.5树的应用 92
6.5.1二叉排序树 92
6.5.2哈夫曼树以及应用 96
习题6 99
第7章 图 101
7.1图的定义和术语 101
7.2图的存储结构 103
7.2.1邻接矩阵 103
7.2.2邻接表 104
7.3图的遍历 106
7.3.1深度优先搜索DFS （Depth First Search） 106
7.3.2广度优先搜索BFS （Breadth First Search） 108
7.4生成树 109
7.4.1概念 109
7.4.2最小生成树（最小支撑树） 110
7.5最短路径 114
7.5.1求某源点到其余各顶点的最短路径 114
7.5.2每对顶点之间的最短路径 116
7.6拓扑排序 117
7.6.1顶点活动网 117
7.6.2拓扑排序 117
习题7 120
第8章 查找 122
8.1线性表的查找 122
8.1.1顺序查找 122
8.1.2折半查找 122
8.1.3分块查找 124
8.2树表的查找 125
8.2.1二叉查找树 125
8.2.2二叉平衡树 126
8.2.3 B_树 129
8.3哈希表 132
8.3.1哈希表的定义 132
8.3.2哈希函数的构造 133
8.3.3冲突处理方法 135
8.3.4查找及分析 137
习题8 137
第9章 排序 139
9.1插入排序 139
9.1.1直接插入排序 139
9.1.2希尔排序 140
9.2交换排序 141
9.2.1冒泡（简单交换排序） 141
9.2.2快速排序 142
9.3选择排序 144
9.3.1直接选择排序 144
9.3.2树形选择排序 145
9.4归并排序 148
习题9 148
附录A 实验 150
实验一 线性表的顺序存储实验 150
一、实验目的 150
二、实验内容 150
实验二 单链表实验 154
一、实验目的 154
二、实验内容 154
实验三 栈、队列的实现及应用 160
一、实验目的 160
二、实验内容 160
实验四 串及数组的实验 169
一、实验目的 169
二、实验内容 169
实验五 二叉树的基本操作 176
一、实验目的 176
二、实验内容 176
实验六 查找 182
一、实验目的 182
二、实验内容 182
实验七 排序 187
一、实验目的 187
二、实验内容 187
参考书目 194