数据结构

第1章绪论1
1.1数据结构的基本概念1
1.2抽象数据类型和软件构造方法4
1.3算法和算法的时间复杂度5
1.3.1算法5
1.3.2算法设计的目标7
1.3.3算法时间效率的度量7
1.4算法设计11
1.5算法书写规范14
1.6本课程内容概述14
习题一15

第2章线性表17
2.1线性表的抽象数据类型17
2.2线性表的顺序表示和实现18
2.2.1顺序表的存储结构18
2.2.2顺序表的操作实现19
2.2.3顺序表操作的效?
2.3线性表的链式表示和实现26
2.3.1单链表的存储结构26
2.3.2单链表的操作实现29
2.3.3单链表操作的效率分析34
2.3.4单链表应用举例35
2.3.5循环单链表36
2.3.6双向链表37
2.4设计举例40
2.5本章小结46
习题二47

第3章堆栈和队列49
3.1堆栈49
3.1.1堆栈和堆栈的抽象数据类型49
3.1.2堆栈的顺序表示和实现50
3.1.3堆栈的链式表示和实现53
*3.2堆栈应用--表达式计算58
3.3队列61
3.3.1队列和队列抽象数据类型61
3.3.2顺序队列62
3.3.3顺序循环队列的表示和实现63
3.3.4链式队列66
3.3.5队列的应用69
*3.4优先级队列71
3.4.1顺序优先级队列的设计和实现71
3.4.2优先级队列的应用74
3.5本章小结75
习题三76

第4章串79
4.1串79
4.1.1串及其基本概念79
4.1.2串的抽象数据类型80
4.1.3C语言的串函数81
4.2串的存储结构83
4.2.1串的顺序存储结构83
4.2.2串的链式存储结构84
4.3串基本操作的实现算法85
4.4串的模式匹配算法90
4.4.1BruteForce算法90
4.4.2KMP算法92
4.4.3BruteForce算法和KMP算法的比较96
4.5本章小结98
习题四99

第5章数组101
5.1数组的实现机制101
5.2动态数组的设计方法102
5.3特殊矩阵的压缩存储105
5.4稀疏矩阵的压缩存储106
5.4.1稀疏矩阵的三元组顺序表106
5.4.2稀疏矩阵的三元组链表110
5.5本章小结111
习题五112

第6章递归114
6.1递归的概念114
6.2递归算法的执行过程115
6.3递归算法的设计方法118
6.4递归过程和运行时栈120
6.5递归算法的效率分析122
*6.6递归算法到非递归算法的转换123
6.7设计举例126
6.7.1一般递归算法设计举例126
*6.7.2回溯法及设计举例129
6.8本章小结133
习题六134

第7章树和二叉树137
7.1树137
7.1.1树的定义137
7.1.2树的表示方法138
7.1.3树的抽象数据类型139
7.2二叉树140
7.2.1二叉树的定义140
7.2.2二叉树抽象数据类型141
7.2.3二叉树的性质141
7.3二叉树的设计和实现143
7.3.1二叉树的存储结构143
7.3.2二叉链存储结构下二叉树的操作实现145
7.3.3二叉树的遍历及其实现147
7.4线索二叉树151
7.5哈夫曼树153
7.5.1哈夫曼树的基本概念153
7.5.2哈夫曼编码问题155
*7.5.3哈夫曼编码问题设计和实现156
7.6树的存储结构.转换和遍历160
7.6.1树的存储结构160
7.6.2树与二叉树的转换162
7.6.3树的遍历163
7.7本章小结164
习题七165

第8章图168
8.1图的基本概念168
8.1.1图的基本概念168
8.1.2图的抽象数据类型170
8.2图的设计和实现171
8.2.1图的邻接矩阵存储结构171
8.2.2图的邻接表存储结构172
8.2.3邻接矩阵存储结构下图的操作实现173
8.3图的遍历177
8.3.1图的深度和广度优先遍历算法177
8.3.2图的深度和广度优先遍历算法设计和实现178
8.4最小生成树181
8.4.1最小生成树的基本概念181
8.4.2普里姆算法182
*8.4.3普里姆函数设计和实现183
8.4.4克鲁斯卡尔算法186
8.5最短路径187
8.5.1最短路径的基本概念187
8.5.2从一个顶点到其余各顶点的最短路径188
*8.5.3狄克斯特拉算法设计和实现189
8.6本章小结192
习题八192

第9章排序195
9.1排序的基本概念195
9.2插入排序197
9.2.1直接插入排序197
9.2.2希尔排序199
9.3选择排序201
9.3.1直接选择排序201
9.3.2堆排序202
9.4交换排序207
9.4.1冒泡排序207
9.4.2快速排序209
*9.5归并排序211
9.6综合应用举例214
9.7本章小结215
习题九216

第10章查找218
10.1查找的基本概念218
10.2静态查找表219
10.2.1顺序表219
10.2.2有序顺序表220
10.2.3索引顺序表222
10.3动态查找表224
10.3.1二叉排序树224
10.3.2B-树231
10.4哈希表235
10.4.1哈希表的基本概念235
10.4.2哈希函数构造方法237
10.4.3哈希冲突解决方法238
10.4.4哈希表设计举例239
10.5本章小结243
习题十244
附录A上机实习内容规范245
附录B上机实习范例246
参考文献257