第1章 绪论 1
1.1什么是数据结构 1
1.1.1数据结构的产生与发展 2
1.1.2数据和数据结构 3
1.1.3数据的逻辑结构 3
1.1.4数据的存储结构 4
1.1.5数据类型 6
1.2算法与算法分析 6
1.2.1算法 6
1.2.2算法设计的目标 6
1.2.3算法的时间复杂度 7
1.2.4算法的空间复杂度 10
1.3本章小结 10
1.4习题 11
第2章 线性表 13
2.1线性表的定义 13
2.2线性表的顺序存储结构——顺序表 13
2.2.1顺序表的特点 13
2.2.2数组 14
2.2.3 System.Collections.ArrayList 16
2.2.4类型安全 22
2.3线性表的链式存储结构——链表 23
2.3.1单向链表 24
2.3.2循环链表 29
2.3.3双向链表 34
2.4本章小结 38
2.5实训指导：虚拟线性表 39
2.6习题 48
第3章 栈和队列 51
3.1栈 51
3.1.1栈的概念及操作 51
3.1.2 System.Collections.Stack 52
3.1.3栈的应用 54
3.1.4双向栈 55
3.2队列 56
3.2.1队列的概念及操作 56
3.2.2循环队列 57
3.2.3 System.Collections.Queue 58
3.3本章小结 61
3.4实训指导：虚拟循环队列 62
3.5习题 67
第4章 串 69
4.1串的基本概念 69
4.2 String 69
4.3 System.Text.StringBuilder 70
4.4串的模式匹配 72
4.4.1 Brute-Force算法 72
4.4.2 KMP算法 74
4.5本章小结 83
4.6实训指导：求最长公共子串 83
4.7习题 85
第5章 树 88
5.1树的基本概念 89
5.1.1树的定义 89
5.1.2树的表示 89
5.1.3树的基本术语 90
5.2二叉树 91
5.2.1二叉树的基本概念 91
5.2.2二叉树的存储结构 92
5.3二叉树的遍历 94
5.3.1二叉树的深度优先遍历 94
5.3.2二叉树的广度优先遍历 98
5.4线索二叉树 100
5.4.1线索二叉树的定义 100
5.4.2中序线索二叉树 101
5.5树和森林 105
5.5.1树的存储结构 105
5.5.2森林、树、二叉树的相互转换 107
5.6可绘制二叉树的设计 109
5.6.1二叉树结点的位置关系 110
5.6.2接口设计 110
5.6.3二叉树绘制类的设计 112
5.6.4实现可绘制二叉树 115
5.7二叉树画树算法 117
5.7.1满二叉树画法 117
5.7.2界内画法 120
5.7.3最小面积画法 121
5.8本章小结 126
5.9实训指导：虚拟二叉树 126
5.10习题 137
第6章 图 139
6.1基本概念和术语 139
6.2图的存储结构 142
6.2.1邻接矩阵表示法 142
6.2.2邻接表表示法 143
6.3图的遍历 147
6.3.1深度优先搜索遍历 148
6.3.2广度优先搜索遍历 150
6.3.3非连通图的遍历 151
6.4生成树和最小生成树 152
6.4.1生成树 152
6.4.2最小生成树 153
6.4.3普里姆算法 153
6.4.4克鲁斯卡尔算法 157
6.5最短路径 161
6.5.1单源点最短路径 161
6.5.2所有顶点之间的最短路径 165
6.6本章小结 168
6.7实训指导：迷宫最短路径问题 168
6.8习题 176
第7章 查找 179
7.1查找的基本概念 179
7.2顺序查找 179
7.3二分查找 180
7.3.1二分查找的基本原理 180
7.3.2二分查找的算法实现 181
7.3.3 Array.BinarySearch方法 183
7.3.4剖析System.Collections.SortedList 183
7.4分块查找 188
7.5二叉查找树 188
7.5.1二叉查找树的定义 189
7.5.2二叉查找树的查找 189
7.5.3二叉查找树的插入 190
7.5.4二叉查找树的删除 191
7.5.5二叉查找树的代码实现 192
7.6本章小结 196
7.7实训指导：Array.BinarySearch的使用 196
7.8习题 199
第8章 哈希表 201
8.1概念引入 201
8.2构造哈希函数的方法 204
8.2.1直接定址法 204
8.2.2数字分析法 204
8.2.3除留余数法 205
8.3哈希冲突解决方法 205
8.3.1闭散列法（开放地址法） 206
8.3.2开散列法（链地址法） 208
8.4剖析System.Collections.Hashtable 209
8.4.1 Hashtable的实现原理 209
8.4.2 Hashtable的代码实现 211
8.5剖析Dictionary＜TKey，TValue＞ 220
8.5.1 Dictionary＜TKey，TValue＞类实现原理 220
8.5.2 Dictionary＜TKey， TValue＞的代码实现 224
8.6本章小结 229
8.7实训指导：虚拟哈希表 229
8.8习题 235
第9章 排序 237
9.1排序的基本概念 237
9.2插入排序 237
9.2.1直接插入排序 237
9.2.2希尔排序 239
9.3交换排序 241
9.3.1冒泡排序 241
9.3.2快速排序 242
9.4选择排序 244
9.4.1直接选择排序 244
9.4.2堆排序 245
9.5归并排序 248
9.5.1二路归并排序 248
9.5.2二路归并排序的实现 249
9.6本章小结 250
9.7实训指导：使用IComparer＜T＞接口进行排序 250
9.8习题 255
第10章 综合实训——八数码问题 258
10.1什么是八数码问题 258
10.2八数码问题的解析 258
10.2.1从初始状态到达目标状态是否有解 258
10.2.2使用什么方法求解八数码问题的最优解 259
10.2.3如何避免重复访问一个状态 260
10.2.4怎样记录查找路径 260
10.2.5使用什么数据结构表示棋盘状态 261
10.3设计目标 262
10.4界面设计 263
10.5代码编写 263
10.5.1 MoveDirection.cs 263
10.5.2 AIResult.cs 263
10.5.3 HashHelpers.cs 264
10.5.4 SimpleDictionary.cs 265
10.5.5 NumSwitch.cs 268
10.5.6 IEightNumAI.cs 270
10.5.7 BFS_AI.cs 270
10.5.8 MainForm.cs 272
10.6调试运行 279
10.7思考与改进 279
参考文献 280