首页 > 图书中心 > 数据结构算法解析

目录

目??录

第1章  数据结构绪论 1

1.1  简单的编程问题 1

1.2  简单的算法设计 4

1.2.1  枚举法编程 4

1.2.2  递推法编程 8

1.2.3  递归法编程 11

1.2.4  迭代法编程 13

1.2.5  动态规划法编程 16

1.3  简单的算法分析 17

1.3.1  语句的执行频度 17

1.3.2  时间复杂度度量 18

1.3.3  有关算法分析的选择题 20

第2章  线性表 26

2.1  线性表的概念 26

2.1.1  线性表的定义 26

2.1.2  线性表的应用 26

2.2  顺序表 28

2.2.1  顺序表的结构 28

2.2.2  顺序表的基本操作 28

2.2.3  顺序表的相关算法 31

2.3  链表 42

2.3.1  单链表的结构 42

2.3.2  单链表的基本运算 42

2.3.3  单链表的相关算法 50

2.4  循环单链表 80

2.4.1  循环单链表的定义 80

2.4.2  循环单链表的基本运算 81

2.4.3  循环单链表的相关算法 86

2.5  双向链表 90

2.5.1  双向链表的定义与结构 90

2.5.2  双向链表的基本运算 90

2.5.3  双向链表的相关算法 93

2.5.4  异或双向链表 99

2.6  静态链表 105

2.6.1  静态链表的结构定义 105

2.6.2  静态链表的基本运算 105

2.7  线性表的应用实例 109

2.7.1  约瑟夫问题求解 109

2.7.2  用位向量表示集合 111

2.7.3  用有序链表表示集合 115

2.7.4  多项式的链表存储表示 124

2.7.5  大整数运算 136

第3章  栈和队列 146

3.1  栈 146

3.1.1  栈的概念 146

3.1.2  顺序栈 148

3.1.3  链式栈 160

3.2  队列 165

3.2.1  队列的定义及基本运算 165

3.2.2  顺序队列 166

3.2.3  链式队列 177

3.2.4  双端队列 182

3.2.5  优先队列 188

3.3  栈和队列的应用 191

3.3.1  栈在数制转换和括号配对中的应用 191

3.3.2  栈在表达式计算中的应用 193

3.3.3  栈和队列的其他应用 199

3.3.4  优先队列的应用 209

3.4  栈与递归 214

3.4.1  递归的概念 214

3.4.2  分治法与递归 215

3.4.3  减治法与递归 217

3.4.4  回溯法与递归 227

3.4.5  贪心法 234

3.4.6  动态规划法 235

第4章  多维数组、字符串与广义表 240

4.1  多维数组 240

4.1.1  一维数组 240

4.1.2  二维数组 263

4.2  特殊矩阵与稀疏矩阵 277

4.2.1  特殊矩阵与稀疏矩阵的概念 277

4.2.2  特殊矩阵相关的算法 281

4.2.3  稀疏矩阵相关的算法 287

4.3  字符串 301

4.3.1  字符串的概念 301

4.3.2  顺序串相关的算法 304

4.3.3  堆分配串相关的算法 308

4.3.4  块链存储字符串相关的算法 323

4.3.5  模式匹配算法 327

4.4  广义表 333

4.4.1  广义表的概念 333

4.4.2  头尾表示广义表相关的算法 335

4.4.3  层次表示广义表相关的算法 342

第5章  树与二叉树 348

5.1  树的基本概念 348

5.1.1  树的概念 348

5.1.2  树的双亲存储表示 349

5.1.3  树的子女链表存储表示 353

5.1.4  树的子女-兄弟链表存储表示 361

5.1.5  树的标准链表表示 367

5.1.6  树的广义表存储表示 367

5.2  二叉树及其存储表示 370

5.2.1  二叉树的概念 370

5.2.2  二叉树的顺序存储结构 372

5.2.3  二叉树的链式存储结构 376

5.3  二叉树的遍历 384

5.3.1  二叉树遍历的基本运算 384

5.3.2  创建二叉树的算法 388

5.3.3  二叉树遍历的非递归算法 403

5.3.4  二叉树遍历相关的算法 417

5.3.5  表达式树 445

5.4  线索二叉树 453

5.4.1  线索二叉树的结构定义 453

5.4.2  中序线索二叉树 454

5.4.3  先序和后序线索二叉树 461

5.5  树与森林的遍历 467

5.5.1  树与森林遍历的概要 467

5.5.2  基于树的双亲表示的遍历算法 468

5.5.3  基于子女链表表示的树的遍历算法 472

5.5.4  基于子女-兄弟链表表示的树的遍历算法 476

5.6  Huffman树 486

5.6.1  Huffman树及其结构定义 486

5.6.2  Huffman树相关的算法 487

5.6.3  Huffman编码相关的算法 489

5.6.4  最佳判定树相关的算法 493

5.7  堆 495

5.7.1  堆的结构定义 495

5.7.2  小根堆的基本运算 495

5.7.3  小根堆相关的算法 498

5.8  并查集 504

5.8.1  并查集的结构定义 504

5.8.2  并查集主要操作的实现 505

第6章  图 509

6.1  图的基本概念 509

6.1.1  图的基本定义与特征 509

6.1.2  图算法实例 510

6.2  图的存储表示 511

6.2.1  图的邻接矩阵表示 511

6.2.2  图的邻接表表示 522

6.2.3  无向图的邻接多重表表示 534

6.2.4  有向图的十字链表表示 538

6.2.5  关联矩阵 541

6.3  图的遍历 544

6.3.1  深度优先搜索 544

6.3.2  广度优先搜索 549

6.3.3  图顶点间的路径 550

6.3.4  图的连通性与生成树 565

6.3.5  双连通图的关节点 578

6.4  最小生成树 579

6.4.1  最小生成树的概念与定义 579

6.4.2  最小生成树相关的算法 580

6.5  最短路径 592

6.5.1  最短路径的概念 592

6.5.2  单源最短路径相关的算法 593

6.5.3  所有顶点间最短路径相关的算法 605

6.6  拓扑排序和关键路径 613

6.6.1  AOV网与拓扑排序 613

6.6.2  AOE网与关键路径 618

6.7  图的其他应用 623

6.7.1  算术表达式的计算 623

6.7.2  二部图 627

6.7.3  渡河问题 629

6.7.4  四色问题 633

第7章  查找 635

7.1  查找的概念与简单查找方法 635

7.1.1  查找的概念 635

7.1.2  顺序查找 635

7.1.3  折半查找 640

7.1.4  斐波那契查找与插值查找 644

7.1.5  静态树表查找 646

7.1.6  跳表 651

7.2  二叉查找树 655

7.2.1  二叉查找树的概念 655

7.2.2  二叉查找树基本运算的实现 655

7.2.3  二叉查找树相关的算法 659

7.2.4  中序线索二叉查找树 677

7.3  AVL树 680

7.3.1  AVL树的概念 680

7.3.2  AVL树相关算法 680

7.4  B树与B+树 690

7.4.1  分块查找与索引表 690

7.4.2  B树 696

7.4.3  B+树 703

7.5  其他查找树 711

7.5.1  红黑树 711

7.5.2  伸展树 722

7.5.3  双链树 727

7.5.4  Trie树 732

7.6  散列法 737

7.6.1  散列法的概念 737

7.6.2  散列法的应用 739

7.6.3  用开地址法解决冲突 743

7.6.4  用链地址法解决冲突 749

第8章  排序 753

8.1  排序的概念与算法 753

8.1.1  排序的概念 753

8.1.2  计数排序算法 753

8.2  插入排序 755

8.2.1  直接插入排序 755

8.2.2  折半插入排序 758

8.2.3  希尔排序 760

8.3  交换排序 761

8.3.1  逆序与交换 761

8.3.2  起泡排序 763

8.3.3  快速排序 769

8.4  选择排序 783

8.4.1  简单选择排序 783

8.4.2  堆排序 789

8.4.3  锦标赛排序 793

8.5  归并排序 797

8.5.1  两路归并 797

8.5.2  递归二路归并排序 805

8.5.3  迭代的二路归并排序 807

8.6  桶排序 813

8.6.1  多排序码的概念 813

8.6.2  MSD桶排序 813

8.6.3  LSD桶排序 817

8.7  链表排序 819

8.7.1  链表排序方法 819

8.7.2  双向链表排序 826

8.7.3  静态链表排序 827

8.8  其他排序算法 834

8.8.1  选择算法 834

8.8.2  地址排序 837

8.9  外排序 841

8.9.1  输入输出缓冲区 841

8.9.2  多路平衡归并 843

8.9.3  初始归并段的生成 845

8.9.4  磁带归并排序 853

8.9.5  最佳归并树 855

参考文献 859

数据结构算法解析

  

目    录

  

·X·

  

·IX·?

  

     

  

  

版权所有(C)2023 清华大学出版社有限公司 京ICP备10035462号 京公网安备11010802042911号

联系我们 | 网站地图 | 法律声明 | 友情链接 | 盗版举报 | 人才招聘