正版现货新书 数据结构算法解析 9787302575122 殷人昆

通常，“数据结构与算法”是所有从事计算机系统研究和应用、计算机应用软件开发的科技人员必须学习和掌握的一门课程，是研究用计算机进行信息表示和处理的学科。
在计算机系统和与计算机相关的应用软件系统（亦称为APP）中，信息的表示和组织直接关系到信息处理程序的效率。随着计算机的普及、信息范围的拓宽、信息量的增加，使得许多系统程序和应用程序的规模和复杂性增加。
一个“好”的计算机程序，应当具有以下几个特性：
（1）正确性：即在给定条件下，输入合理的数据，程序运行的结果应是正确的，计算精确度应是满足预定要求的。
（2）健壮性：亦称鲁棒性，即在给定条件下，输入可能不合理的数据，程序应能做出正确的反应，包括检查输入的正确性，必要时能够自动纠正可能发生的错误。
（3）简单性：亦称程序的圈复杂度，即程序结构中分支、循环、子程序调用的总数越少越好；程序越简单，程序开发、修改越容易，运行的出错概率越小。
（4）高效性：亦称算法的时空效率，即算法的时间复杂度和空间复杂度越小越好，通常用程序规模n的大O表示O(n)来衡量。
（5）可读性：即算法或程序易读、易理解性。一个可读的程序应是简单的、模块化的、其接口应是显式的，即共享数据应该尽量通过接口传递，避免直接访问。
（6）结构性：即程序应是结构化的，仅使用标准的单入口、单出口的控制结构（顺序、分支、循环）编写程序，避免使用goto语句转来转去；信息结构尽量采用封装、信息隐蔽的原则实现对象化，使得错误局部化，从而使得程序易于编码、易于测试、易于修改。
要使数据结构和算法的设计达到以上要求的特性，不是一件易事。以往总有人说“数据结构课一听就懂，一做不会”，就是指数据结构的算法设计和编程入手困难。往往一种方法可以解决多种问题，一个问题可以用多种方法来解决，面对一个需要解决的问题该如何着手，没有一定的经验很难理清其中的逻辑。本书就是针对这个困难，收集了很多不同的题型，提供了解题思路和用C语言描述的解决代码，所有代码都在Visual C   6.0下调试通过。书中有些题是基本算法题，有些题是扩展思路的算法题，通过刷题，可以积累解决问题的经验，提高处理问题的能力。
关于刷题的必要性，本人有切身的体会。1978年全国首次恢复招收研究生，按照清华大学指定的考研科目，本人做了充分准备，针对考试科目找了不少题目，认真解出答案，终如愿考入清华大学。入学后学校搞了突然袭击，要求某月某日全体新生在主楼后厅再考一次数学和英语，本人把考研前做的题看了一遍，上阵赴考，第5个交卷，考了94分。
本书共分8章，内容覆盖了*高等学校计算机科学与技术专业教学指导委员会公布的《高等学校计算机科学与技术专业公共核心知识体系与课程》和*考试中心公布的《全国硕士研究生入学考试计算机科学与技术专业基础综合考试联考考试大纲》有关数据结构的所有知识点，同时也参考了美国IEEE计算教程2013的关于基本数据结构与算法的知识要求。
第1章数据结构绪论主要介绍数据结构算法设计与简单算法分析。在这一章中给出了有关枚举法、递推法、递归法、迭代法、动态规划法等几种简单算法，以及后面几章中常用的交换两个整数的值、求两个整数的较大者、按序输出三个整数的值的基础算法。
第2章线性表主要介绍线性表的逻辑表示和存储实现，以及线性表的应用算法。在这一章中给出了顺序表、链接表（单链表、循环单链表、双向链表、静态链表、“异或”双向链表）、线性表的应用实例（包括约瑟夫（Josephus）问题、用位向量和有序链表表示集合、多项式的链表存储表示及其运算、大整数的表示及其运算）的相关算法。
第3章栈和队列主要介绍栈和队列的逻辑表示和存储实现，以及栈和队列的应用算法。在这一章中给出了顺序栈和链式栈、循环队列和链式队列的各种实现，双端队列的实现，栈的应用（数制转换、括号配对、表达式的实现和计算）算法，栈和队列的应用（停车场模拟、铁道车厢调度、杨辉三角形打印、电路布线）算法，优先队列的应用算法。在这一章的栈与递归部分还给出了分治法与递归算法、减治法与递归算法、回溯法与递归算法、贪心法的实现与应用，递归到非递归的转换，以及动态规划法的应用算法。
第4章多维数组、字符串与广义表主要介绍一维数组、多维数组、字符串和广义表的实现和应用算法。在这一章中讨论了在考研和企业应聘中出现频率较高的算法，主要是基于数组实现的算法。此外，给出了许多特殊矩阵和稀疏矩阵的实现算法。在字符串部分包括了顺序串、堆式串和链式串的实现算法，以及数量较多的串应用算法，后给出了典型的串模式匹配算法。在广义表部分，给出了用头尾表示法和层次表示法实现广义表的算法。
第5章树与二叉树主要介绍树与二叉树的存储、遍历、转换以及应用。在这一章中包括了树与森林的双亲、子女链表、子女兄弟链表、广义表存储表示的实现算法，二叉树的顺序和链式存储表示，树与二叉树的遍历算法，构建树与二叉树的算法，表达式树的实现算法，线索二叉树的构建和遍历算法，Huffman树的构建、Huffman编码、二叉判定树的构建算法，堆的构建算法，并查集的操作算法等。
第6章图主要介绍图的存储、遍历、生成树等基本算法和应用算法的实现。在这一章中包括了图的邻接矩阵、邻接表、无向图的邻接多重表、有向图的十字链表、关联矩阵等存储表示的实现算法，图的DFS和BFS遍历的递归和非递归的实现算法，图中顶点间路径的求解算法，图的生成树和连通分量的求解算法，双连通图中关节点的计算算法等。在图的应用方面，给出了多个求解小生成树、短和长路径的算法、拓扑排序和关键路径的求解算法。此外还给出了用有向无环图计算表达式、二部图、渡河问题、四色问题的求解算法。
第7章查找主要介绍静态查找表、跳表、动态查找树，以及散列表相关的算法。在这一章中给出了静态查找表的各种查找算法（顺序查找、折半查找、斐波那契查找和插值查找、静态树表查找），跳表的构造、查找、插入和删除算法，动态查找树（二叉查找树、AVL树、B树和B 树、红黑树、伸展树、双链树、Trie树）的相关算法，散列表的相关算法。
第8章排序主要介绍各种内排序算法和外排序算法。在这一章中给出了大量内排序算法，包括插入排序（直接插入排序、折半插入排序、Shell排序），交换排序（起泡排序、鸡尾酒排序、梳排序、Batcher排序、奇偶交换排序、快速排序），选择排序（简单选择排序、二次选择排序、堆排序、锦标赛排序），二路归并排序和自然归并排序，桶排序（包括自顶向下的桶排序和自底向上的基数排序）。此外还包括了少量的链表排序算法、选择算法和地址排序算法。在外排序方面，给出了多路平衡归并排序算法、初始归并段的生成算法、磁带归并段算法和归并树算法。
“细节决定成败”。数据结构算法的设计灵活性很强，容易在细节上失分。因此，全面掌握数据结构的相关知识点并能合理运用，是学好数据结构课程的关键。
本书是作者本着作为一名教师，为学生“解惑”而编写的。所有习题都尽可能遵循软件工程要求，使用合理的和不合理的测试数据进行了测试。然而由于测试的不充分性，算法的实现程序仍然可能存在错误和疏漏，敬请读者批评指正。

作  者
2021年1月于清华园荷清苑

本书共分8章。第1章是介绍数据结构和算法的基本概念和算法分析的简单方法，以及C语言编程的要点。本书既可作为普通大学计算机科学与技术专业和软件工程专业本科生学习数据结构与算法课程的教材，也可以作为计算机专业考研的辅导教材或其他计算机或软件考试的复习教材，还可以作为供从事计算机或软件系统开发的人员参考的学习资料。

殷人昆，清华大学计算机系教授，1985年赴日本国东京理科大学做访问学者，研究方向为软件工程过程的质量管理和软件产品的质量评价。主要教学工作为计算机系大学本科“数据结构”、“软件工程”和研究生“软件工程设计与技术”、“软件项目管理”课程负责人，主持*―微软精品课程“数据结构”的建设。曾与人合作或单独编写和出版教材20余部，其中，《数据结构》教材被评为*普通高等教育“十一五”规划教材，并于2005年获“北京市精品教材”。曾在核心刊物和专业会议发表论文多篇，并参加或主持多项科研项母。

第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

本书共分8章。第1章是介绍数据结构和算法的基本概念和算法分析的简单方法，以及C语言编程的要点。本书既可作为普通大学计算机科学与技术专业和软件工程专业本科生学习数据结构与算法课程的教材，