《数据结构原理》求取 ⇩

目录1

导论1

第一章　数组1

1.1　一维数组1

1.2　二维数组2

1.2.1　二维数组的存贮3

1.2.2　三角阵与带状矩阵4

1.3　多维数组8

1.4　稀疏矩阵11

1.4.1　三元组表示方法11

1.4.2　稀疏矩阵的转置12

1.4.3　稀疏矩阵的乘法16

习题21

第二章　线性表24

2.1　线性表24

2.1.1　线性表的顺序存贮25

2.1.2　线性表的操作26

2.2　栈的定义及基本操作34

2.3　队列的定义及基本操作40

2.4　栈的应用45

2.4.1　求算术表达式的值45

2.4.2　迷宫问题51

习题57

3.1　线性链表59

3.1.1　线性链表59

第三章　链表59

3.1.2　线性链表的操作61

3.1.3　例子——多项式相加67

3.2　链接栈和链接队列71

3.3　环形链表和双向链表74

3.3.1　环形链表74

3.3.2　双向链表77

3.3.3　例子——订票系统80

3.4.1　十字链表表示法87

3.4　十字链表87

3.4.2　十字链表表示的稀疏矩阵的运算89

习题95

第四章　内部排序97

4.1　插入排序98

4.1.1　直接插入排序98

4.1.2　二分插入排序101

4.1.3　希尔（Shell）排序103

4.2　选择排序106

4.2.1　直接选择排序106

4.2.2　树形选择排序107

4.2.3　堆排序108

4.3　交换排序115

4.3.1　冒泡排序115

4.3.2　快速排序118

4.4　基数排序123

4.5　合并排序127

4.6　关于内部排序的实用考虑132

习题142

第五章　树145

5.1　基本术语145

5.2　一般树152

5.2.1　树的存贮结构152

5.2.2　树的遍历155

5.2.3　树的线性表示161

5.3　二叉树165

5.3.1　一般树转换成相应的二叉树167

5.3.2　二叉树的遍历170

5.3.3　二叉树的顺序存贮178

5.3.4　二叉树的其它操作实例187

5.3.5　计算二叉树的数目189

5.4　穿线二叉树194

5.4.1　穿线二叉树的操作196

5.4.2　穿线排序201

5.5　树的应用205

习题213

第六章　图216

6.1　图的术语和存贮结构216

6.1.1 引言216

6.1.2　术语217

6.1.3　图的存贮结构220

6.2　图的遍历和图的连通分量227

6.2.1　深度优先搜索法227

6.2.2　广度优先搜索法229

6.2.3　图的连通分量230

6.3　生成树和最小代价生成树232

6.4　最短路径和传递闭包237

6.4.1　从一个源点到其它各顶点的最短路径238

6.4.2　每一对顶点之间的最短路径243

6.4.3　传递闭包246

6.5.1　拓扑排序249

6.5　关键路径249

6.5.2　关键路径257

习题265

第七章　查找269

7.1　线性表的查找270

7.1.1　顺序查找法270

7.1.2　二分查找法272

7.1.3　分块查找法274

7.2.1　查找树277

7.2　查找树277

7.2.2　丰满查找树282

7.2.3　平衡查找树284

7.3　最佳查找树295

7.3.1　最佳查找树295

7.3.2　最佳叶子查找树303

7.4　回溯法309

7.4.1　背包问题310

7.4.2　骑士周游问题317

7.5　数字查找树和Trie查找323

7.6　Hash查找330

7.6.1　hash函数331

7.6.2　处理冲突的方法332

习题340

第八章　外部排序342

8.1　存贮设备342

8.1.1　磁带342

8.1.2　磁盘344

8.2　磁盘排序346

8.2.1　K路合并349

8.2.2　并行操作的缓冲区处理355

8.2.3　初始顺串的生成362

8.3　磁带排序366

8.3.1　平衡合并排序369

8.3.2　多阶段合并排序373

习题377

第九章　文件379

9.1　文件的基本概念379

9.1.1　文件与记录379

9.1.2　文件的逻辑特性381

9.1.3　文件的物理表示384

9.2　索引技术385

9.2.1　柱面-盘面索引386

9.2.2　B树索引389

9.2.3　杂凑索引409

9.3　文件的组织形式410

9.3.1　顺序文件410

9.3.2　随机文件411

9.3.3　链接文件414

9.3.4　倒排文件418

9.3.5　存贮管理420

习题422

参考文献426