数据结构基础 C语言版PDF|Epub|txt|kindle电子书版本下载

数据结构基础 C语言版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 基本概念1

1.1概观：系统生命周期1

1.2指针和动态存储分配3

1.2.1指针3

1.2.2动态存储分配4

1.2.3指针隐患6

1.3算法形式规范6

1.3.1综论6

1.3.2递归算法11

1.4数据抽象14

1.5性能分析17

1.5.1空间复杂度18

1.5.2时间复杂度20

1.5.3渐近记号（O，Ω，Θ）27

1.5.4实际复杂度33

1.6性能度量35

1.6.1定时35

1.6.2生成测试数据39

1.7参考文献和选读材料40

第2章 数组和结构41

2.1数组41

2.1.1数组的抽象数据类型41

2.1.2C语言的数组41

2.2数组的动态存储分配44

2.2.1一维数组44

2.2.2二维数组44

2.3结构体和联合体47

2.3.1结构体47

2.3.2联合体49

2.3.3结构的内部实现50

2.3.4自引用结构50

2.4多项式51

2.4.1多项式的抽象数据类型51

2.4.2多项式的表示52

2.4.3多项式加法55

2.5稀疏矩阵58

2.5.1稀疏矩阵的抽象数据类型58

2.5.2稀疏矩阵的表示58

2.5.3矩阵转置59

2.5.4矩阵相乘63

2.6多维数组的表示67

2.7字符串68

2.7.1字符串的抽象数据类型68

2.7.2C语言的字符串68

2.7.3模式匹配71

2.8参考文献和选读材料77

2.9补充习题78

第3章 栈与队列83

3.1栈83

3.2动态栈87

3.3队列88

3.4动态循环队列92

3.5迷宫问题95

3.6表达式求值98

3.6.1表达式98

3.6.2后缀表达式求值100

3.6.3中缀表达式转换成后缀表达式103

3.7多重栈与多重队列108

3.8补充习题111

第4章 链表113

4.1单向链表113

4.2用C语言表示单向链表115

4.3链式栈与链式队列121

4.4多项式124

4.4.1多项式表示124

4.4.2多项式加法125

4.4.3销毁多项式128

4.4.4循环链表与多项式129

4.4.5小结130

4.5其它链表操作133

4.5.1单向链表操作133

4.5.2循环链表操作134

4.6等价类135

4.7稀疏矩阵139

4.7.1稀疏矩阵表示139

4.7.2输入稀疏矩阵142

4.7.3输出稀疏矩阵144

4.7.4销毁稀疏矩阵144

4.8双向链表146

第5章 树149

5.1引论149

5.1.1术语149

5.1.2树的表示151

5.2二叉树154

5.2.1二叉树的抽象数据类型154

5.2.2二叉树的性质155

5.2.3二叉树的表示157

5.3遍历二叉树159

5.3.1中序遍历160

5.3.2先序遍历161

5.3.3后序遍历161

5.3.4非递归（循环）中序遍历162

5.3.5层序遍历163

5.3.6不设栈遍历二叉树163

5.4其它二叉树操作164

5.4.1复制二叉树164

5.4.2判断两个二叉树全等164

5.4.3可满足性问题165

5.5线索二叉树168

5.5.1线索168

5.5.2中序遍历线索二叉树169

5.5.3线索二叉树插入结点170

5.6堆172

5.6.1优先级队列172

5.6.2大根堆定义174

5.6.3大根堆插入操作174

5.6.4大根堆删除操作176

5.7二叉查找树178

5.7.1定义178

5.7.2二叉查找树的查找179

5.7.3二叉查找树的插入180

5.7.4二叉查找树的删除181

5.7.5二叉查找树的合并与分裂182

5.7.6二叉查找树的高度183

5.8选拔树185

5.8.1引子185

5.8.2优胜树186

5.8.3淘汰树187

5.9森林188

5.9.1森林转换为二叉树189

5.9.2遍历森林189

5.10不相交集合的表示190

5.10.1引子190

5.10.2合并与查找操作191

5.10.3划分等价类197

5.11二叉树的计数199

5.11.1不同态二叉树199

5.11.2栈置换200

5.11.3矩阵乘法201

5.11.4不同二叉树的数目203

5.12参考文献和选读材料204

第6章 图205

6.1图的抽象数据类型205

6.1.1引子205

6.1.2图的定义和术语206

6.1.3图的表示210

6.2图的基本操作216

6.2.1深度优先搜索216

6.2.2广度优先搜索217

6.2.3连通分量218

6.2.4生成树219

6.2.5重连通分量220

6.3最小代价生成树225

6.3.1Kruskal算法225

6.3.2Prim算法228

6.3.3Sollin算法229

6.4最短路径和迁移闭包230

6.4.1单源点至所有其它节点：边权值非负231

6.4.2单源点至所有其它节点：边权值正负无限制233

6.4.3所有节点两两之间的最短路径237

6.4.4迁移闭包238

6.5活动网络242

6.5.1活动节点（AOV）网络242

6.5.2活动边（AOE）网络247

6.6参考文献和选读材料253

6.7补充习题254

第7章 排序256

7.1动机256

7.2插入排序259

7.3快速排序261

7.4排序最快有多快264

7.5归并排序265

7.5.1归并265

7.5.2非递归归并排序266

7.5.3递归归并排序267

7.6堆排序270

7.7多关键字排序273

7.8链表排序和索引表排序277

7.9内部排序小结284

7.10外部排序289

7.10.1引子289

7.10.2k路归并291

7.10.3缓存与并行操作292

7.10.4生成多路数据298

7.10.5最优多路归并300

7.11参考文献和选读材料303

第8章 Hash法304

8.1引言304

8.2静态Hash法304

8.2.1Hash表304

8.2.2Hash函数305

8.2.3溢出处理307

8.2.4处理溢出方法的理论估计312

8.3动态Hash法315

8.3.1动态Hash法的动机315

8.3.2设目录的动态Hash法316

8.3.3不设目录的动态Hash法318

8.4Bloom滤波器320

8.4.1差异文件及其应用320

8.4.2设计Bloom滤波器321

8.5参考文献和选读材料323

第9章 优先级队列324

9.1单端优先级队列与双端优先级队列324

9.2左倾树325

9.2.1高度左倾树325

9.2.2权值左倾树330

9.3二项式堆332

9.3.1代价分摊332

9.3.2二项式堆的定义333

9.3.3二项式堆的插入333

9.3.4融合两个二项式堆334

9.3.5删除最小元334

9.3.6分析336

9.4Fibonacci堆338

9.4.1定义338

9.4.2F-堆的删除338

9.4.3减小关键字339

9.4.4上行切除339

9.4.5分析340

9.4.6F-堆与最短路径问题342

9.5配偶堆344

9.5.1定义344

9.5.2融合与插入344

9.5.3减小关键字值345

9.5.4删除最小元346

9.5.5删除任意元348

9.5.6实现细节349

9.5.7复杂度分析349

9.6对称最小-最大堆350

9.6.1定义与性质350

9.6.2SMMH的表示351

9.6.3SMMH的插入351

9.6.4SMMH的删除353

9.7区间堆358

9.7.1定义和性质358

9.7.2区间堆的插入359

9.7.3删除最小元360

9.7.4区间堆的初始化361

9.7.5区间堆操作的复杂度361

9.7.6区间外查找361

9.8参考文献和选读材料363

第10章 高效二叉查找树366

10.1最优二叉查找树366

10.2AVL树373

10.3红-黑树384

10.3.1定义384

10.3.2红-黑树的表示386

10.3.3红-黑树的查找386

10.3.4红-黑树的插入386

10.3.5红-黑树的删除389

10.3.6红-黑树的合并389

10.3.7红-黑树的分裂391

10.4Splay树393

10.4.1自底向上Splay树394

10.4.2自顶向下Splay树398

10.5参考文献和选读材料403

第11章 多路查找树405

11.1m-路查找树405

11.1.1定义和性质405

11.1.2m-路查找树的查找406

11.2B-树407

11.2.1定义和性质407

11.2.2B-树中数据元素的个数408

11.2.3B-树的插入409

11.2.4B-树的删除412

11.3B+-树419

11.3.1定义419

11.3.2B+-树的查找420

11.3.3B+-树的插入420

11.3.4B+-树的删除422

11.4参考文献和选读材料426

第12章 数字查找结构427

12.1数字查找树427

12.1.1定义427

12.1.2查找、插入、删除427

12.2二路Trie树与Patricia树428

12.2.1二路Trie树428

12.2.2压缩二路Trie树429

12.2.3Patricia树429

12.3多路Trie树434

12.3.1定义434

12.3.2Trie树的查找436

12.3.3取样策略437

12.3.4Trie树的插入439

12.3.5Trie树的删除439

12.3.6变长关键字440

12.3.7Trie树的高度440

12.3.8空间需求与其它结点结构440

12.3.9查找前缀及其应用443

12.3.10压缩Trie树444

12.3.11设skip域的压缩Trie树446

12.3.12设边标记的压缩Trie树446

12.3.13压缩Trie树的空间需求449

12.4后缀树450

12.4.1你见过基因串吗450

12.4.2后缀树数据结构450

12.4.3查！查！查子串！（后缀树的查找）453

12.4.4后缀树的妙用454

12.5Trie树与互连网的包转发455

12.5.1IP路由455

12.5.21-bit Trie树456

12.5.3固定步长Trie树457

12.5.4不定步长Trie树459

12.6参考文献和选读材料461

索引463