数据结构教程 C#语言描述PDF电子书下载

第1章 绪论 1

1.1什么是数据结构 1

1.1.1数据结构的定义 1

1.1.2数据的逻辑结构 2

1.1.3数据的存储结构 5

1.1.4数据的运算 8

1.1.5数据结构和数据类型 10

1.2算法及其描述 15

1.2.1什么是算法 15

1.2.2算法描述 16

1.3算法分析 18

1.3.1算法的特性和算法设计的目标 18

1.3.2算法时间效率分析 19

1.3.3算法存储空间分析 22

1.4数据结构的目标 22

本章小结 23

练习题1 23

第2章 线性表 26

2.1线性表的定义 26

2.1.1什么是线性表 26

2.1.2线性表的抽象数据类型描述 27

2.2线性表的顺序存储结构 27

2.2.1线性表的顺序存储结构——顺序表 27

2.2.2顺序表基本运算的实现 28

2.3线性表的链式存储结构 36

2.3.1线性表的链式存储结构——链表 36

2.3.2单链表 37

2.3.3双链表 47

2.3.4循环链表 52

2.4线性表的应用 58

本章小结 65

练习题2 66

第3章 栈和队列 70

3.1栈 70

3.1.1栈的定义 70

3.1.2栈的顺序存储结构及其基本运算的实现 71

3.1.3栈的链式存储结构及其基本运算的实现 75

3.1.4栈的应用 78

3.2队列 88

3.2.1队列的定义 89

3.2.2队列的顺序存储结构及其基本运算的实现 90

3.2.3队列的链式存储结构及其基本运算的实现 95

3.2.4队列的应用 99

本章小结 102

练习题3 102

第4章串 106

4.1串的基本概念 106

4.1.1什么是串 106

4.1.2串的抽象数据类型 107

4.2串的存储结构 108

4.2.1串的顺序存储结构——顺序串 108

4.2.2串的链式存储结构——链串 113

4.3串的模式匹配 120

4.3.1 Brute-Force算法 121

4.3.2 KMP算法 123

本章小结 129

练习题4 130

第5章 数组和广义表 131

5.1数组 131

5.1.1数组的定义 131

5.1.2数组的存储结构 132

5.1.3特殊矩阵的压缩存储 134

5.2稀疏矩阵 137

5.2.1稀疏矩阵的三元组表示 137

5.2.2稀疏矩阵的十字链表表示 141

5.3递归 144

5.3.1递归的定义 144

5.3.2何时使用递归 145

5.3.3递归模型 146

5.3.4递归算法设计的步骤 147

5.3.5递归算法转换为非递归算法 149

5.4广义表 152

5.4.1广义表的定义 152

5.4.2广义表的存储结构 154

5.4.3广义表的运算 155

本章小结 161

练习题5 161

第6章 树和二叉树 163

6.1树 163

6.1.1树的定义 163

6.1.2树的逻辑结构表示方法 164

6.1.3树的基本术语 165

6.1.4树的性质 166

6.1.5树的基本运算 167

6.1.6树的存储结构 168

6.2二叉树 170

6.2.1二叉树的定义 171

6.2.2二叉树的性质 172

6.2.3二叉树与树、森林之间的转换 174

6.2.4二叉树的存储结构 177

6.2.5二叉树的基本运算及其实现 179

6.2.6二叉树的遍历 182

6.2.7二叉树的构造 200

6.2.8线索二叉树 205

6.3哈夫曼树 210

6.3.1哈夫曼树的定义 210

6.3.2哈夫曼树的构造算法 211

6.3.3哈夫曼编码 213

本章小结 216

练习题6 216

第7章图 220

7.1图的基本概念 220

7.1.1图的定义 220

7.1.2图的基本术语 221

7.2图的存储结构和基本运算的实现 223

7.2.1邻接矩阵存储方法 224

7.2.2邻接表存储方法 225

7.3图的遍历 230

7.3.1图的遍历的概念 231

7.3.2深度优先遍历 231

7.3.3广度优先遍历 233

7.3.4非连通图的遍历 235

7.3.5图遍历算法的应用 236

7.4图的应用 244

7.4.1生成树和最小生成树 244

7.4.2最短路径 252

7.4.3拓扑排序 260

7.4.4 AOE网与关键路径 262

本章小结 269

练习题7 269

第8章 查找 274

8.1查找的基本概念 274

8.2线性表的查找 275

8.2.1顺序查找 276

8.2.2折半查找 277

8.2.3索引存储结构和分块查找 280

8.3树表的查找 285

8.3.1二叉排序树 285

8.3.2平衡二叉树 293

8.3.3 B-树 299

8.3.4 B+树 304

8.4哈希表查找 306

8.4.1哈希表的基本概念 306

8.4.2哈希函数构造方法 306

8.4.3哈希冲突的解决方法 307

8.4.4哈希表查找及性能分析 310

本章小结 314

练习题8 314

第9章 内排序 317

9.1排序的基本概念 317

9.2插入排序 319

9.2.1直接插入排序 319

9.2.2折半插入排序 322

9.2.3希尔排序 323

9.3交换排序 325

9.3.1冒泡排序 325

9.3.2快速排序 327

9.4选择排序 330

9.4.1简单选择排序 331

9.4.2堆排序 332

9.5归并排序 336

9.6基数排序 338

9.7各种内排序方法的比较和选择 342

本章小结 350

练习题9 350

第10章 外排序 353

10.1外排序概述 353

10.2磁盘排序 354

10.2.1磁盘排序过程 354

10.2.2生成初始归并段 355

10.2.3多路平衡归并 357

10.2.4最佳归并树 360

本章小结 364

练习题10 364

附录A部分练习题参考答案 366

参考文献 368