第1章 绪论 1
1.1基本概念 1
1.1.1数据和数据结构 1
1.1.2数据类型 3
1.1.3抽象数据类型 3
1.1.4数据结构的符号描述举例 4
1.2算法和算法描述 5
1.2.1概念和特性 5
1.2.2算法设计要求 6
1.2.3算法描述 6
1.3算法的性能分析 7
1.3.1时间复杂度 7
1.3.2空间复杂度 9
1.3.3分析算法时间复杂度举例 9
1.4习题 10
第2章 线性表 12
2.1线性表的含义及ADT描述 12
2.2顺序存储结构 14
2.2.1顺序表的存储表示 14
2.2.2顺序表基本操作的实现 15
2.2.3顺序表基本操作的时间复杂度分析 19
2.2.4顺序表的优缺点 19
2.2.5顺序存储结构的应用 19
2.3链式存储结构 21
2.3.1单链表的存储表示 21
2.3.2单链表基本操作的实现 23
2.3.3循环链表的表示和基本操作的实现 28
2.3.4双向链表的表示和基本操作的实现 31
2.3.5链式存储结构的应用 32
2.4习题 36
第3章 栈和队列 37
3.1栈 37
3.1.1栈的定义及ADT描述 37
3.1.2栈的顺序存储结构 38
3.1.3栈的链式存储结构 40
3.1.4栈的应用 42
3.2队列 45
3.2.1队列的定义及ADT描述 45
3.2.2队列的顺序存储结构 46
3.2.3队列的链式存储结构 49
3.2.4队列的应用 52
3.3习题 56
第4章 串和数组 59
4.1串 59
4.1.1串的定义及ADT描述 59
4.1.2串的顺序存储结构 60
4.1.3串的链式存储结构 64
4.1.4串的应用 65
4.2数组 68
4.2.1数组的定义及ADT描述 68
4.2.2数组的存储结构 70
4.2.3矩阵的压缩存储 73
4.2.4矩阵转置 79
4.2.5数组的应用 82
4.3习题 85
第5章 树和二叉树 88
5.1树 88
5.1.1树的概念及ADT描述 88
5.1.2树的存储结构 90
5.1.3综合应用举例 93
5.2二叉树 94
5.2.1二叉树的概念及ADT描述 94
5.2.2二叉树的性质 95
5.2.3二叉树的存储结构 98
5.2.4遍历二叉树 101
5.2.5遍历算法的应用 104
5.2.6树、森林与二叉树的转换 106
5.2.7二叉树的综合应用 110
5.3树和森林的遍历 113
5.3.1树的遍历 113
5.3.2森林的遍历 113
5.3.3树和森林的遍历应用 114
5.4哈夫曼树及应用 115
5.4.1哈夫曼树 115
5.4.2判定树 117
5.4.3前缀编码 118
5.5习题 120
第6章图 121
6.1图的概述 121
6.1.1图的概念 121
6.1.2图的ADT描述 124
6.2图的存储结构 125
6.2.1邻接矩阵 125
6.2.2邻接表 126
6.2.3应用举例 128
6.3图的遍历 129
6.3.1深度优先遍历 129
6.3.2广度优先遍历 130
6.3.3应用举例 131
6.4最小生成树问题 131
6.4.1图的生成树和最小生成树 131
6.4.2最小生成树构造 132
6.4.3应用举例 135
6.5有向无环图及应用 136
6.5.1基本定义 136
6.5.2拓扑排序 137
6.5.3关键路径 140
6.6习题 146
第7章 查找 149
7.1基本概念 149
7.2静态查找 150
7.2.1顺序查找 150
7.2.2折半查找 152
7.2.3折半查找的应用 154
7.3动态查找 155
7.3.1二叉排序树 155
7.3.2二叉排序树的查找 156
7.3.3二叉排序树的插入 157
7.3.4二叉排序树的删除 159
7.3.5二叉排序树的应用 161
7.4哈希表 163
7.4.1哈希表的概念 163
7.4.2哈希函数的构造 164
7.4.3冲突处理的方法 166
7.4.4哈希表查找及分析 168
7.4.5哈希表查找的应用 169
7.5习题 171
第8章 排序 172
8.1基本概念 172
8.2插入排序 173
8.2.1直接插入排序 173
8.2.2希尔排序 175
8.2.3应用举例 177
8.3交换排序 178
8.3.1冒泡排序 178
8.3.2快速排序 180
8.3.3应用举例 184
8.4选择排序 185
8.4.1简单选择排序 185
8.4.2堆排序 187
8.4.3应用举例 190
8.5归并排序 193
8.5.1归并排序的基本思想 193
8.5.22-路归并排序算法 193
8.5.3应用举例 195
8.6基数排序 195
8.6.1基数排序的基本思想 195
8.6.2链式基数排序算法 199
8.6.3应用举例 201
8.6.4排序方法的简单比较 201
8.7习题 202
附录 实验指导 204
实验一 通讯录管理信息系统模拟 204
实验二 模拟停车场管理 211
实验三 图的应用 217
参考文献 228