Python算法图解

算法是软件开发必不可少的要素之一。从机器学习、人工智能到数据存储、界面展示等都要用到算法。数据结构是算法的基础，数组、字典、堆、栈、链表、树、图等数据结构就像建造一座楼所需要的梁、柱子、墙、楼板、楼梯等组件，根据需要用各种算法把它们组装起来，最终开发成一个可用的项目或产品。“数据结构与算法”课程目前在各高校均有开设，但多偏向理论教学，与开发实践有一定距离。本书用图解方式讲解算法，利于读者理解；以IT企业面试题作为案例，贴合企业实际需求。全书内容包括：

数据结构；

递归；

栈和队列；

链表；

数组；

树结构；

堆结构；

散列表；

字典树；

图结构；

排序。

本书是一部论述使用Python语言描述数据结构与算法的新形态图书,采用图解方式和Python语言来描述各类算法的实现过程,讲解通俗易懂,易于理解,切实做到深入浅出。同时,针对企业的用人需求本书提供了丰富的面试题,具有很强的实战性。

本书共分11章,包括数据结构的分类和基本运算、递归、栈和队列、链表、数组、树结构、堆结构、散列表、字典树、图和排序算法。读者使用时,学习顺序未必全按书中章节安排,可以依照自己的需求,做适当调整。

为方便读者学习,作者专门录制了配套的微课视频,并提供配套程序代码,供读者使用。本书既适合有一定编程基础的初学者,也适合想巩固相关算法知识的软件开发人员,同时也适合作为各高校计算机专业“数据结构与算法”课程的教材。

何韬 现任TCL教育科技有限责任公司资深工程师。曾就职于互爱（北京）、用友软件、大唐电信、IBM等IT企业，主持及参与过多个大型IT产品和项目的开发，有丰富的IT产品设计和开发经验。目前致力于IT教育领域，努力把IT实战开发经验与教学有机结合起来，服务于IT产业人才培养。

苗俊东 京东集团零售生态业务中心全渠道生态部资深开发工程师

做了近十年开发，遇到最多的就是各种算法问题。当年在学校算法学得不怎么好，工作后不得不边干边补。从实践中学，无疑是最扎实的学法，但也是最艰难的历练。如果当年有一本如同《Python算法图解》的算法书籍，一定能少走很多弯路，希望这本书能帮到更多在编程道路上前行的开发者。

戴君 北京同城必应科技有限公司闪送项目架构师、统筹调度系统技术负责人

《Python算法图解》是一本非常直观的算法解析书。我将会在图书出版后第一时间推荐给新入职场的同事，虽然很多同事已经有丰富的开发经验，但依然有必要进一步夯实自己的算法基础。这部图解形式的算法图书可以供开发者在繁忙的工作之余随手翻阅，理解算法的精髓，开卷有益。

彭天拓 北京云住养科技有限公司创始人，智慧养老社区产品技术负责人

在程序开发过程中，经常要根据需求做出各种判断，把需求转换成可操作的数学模型。这时，算法功底的强弱直接决定了数学模型设计的好坏，好的设计可以事半功倍，坏的设计可能导致整个项目拖延甚至事故，所以我们在招聘新员工的时候尤其强调应聘者的算法设计能力。非常希望有更多类似《Python算法图解》这样的书籍帮助程序员夯实算法基础，提高编程水平。

李少方 北京二六三企业通信有限公司企业通信事业部产品中心数据支撑部技术主管

程序开发有点像建造大楼，按照需求进行架构设计的人员是设计师，按照设计图纸把砖块砌成墙体的是“码农”。在程序开发过程中，设计师也很难考虑到所有的细节。所以码农们需要理解设计框架，必须掌握算法知识，这是企业对程序员的基本要求。《Python算法图解》为IT从业者提供了有益的算法知识，愿更多的人能从书中受益。

第1章数据结构的分类和基本运算

1．1数据的逻辑结构

1．2数据的存储结构

1．3数据结构的基本运算

第2章递归

2．1递归调用

2．2递归方式打印九九乘法表

2．3舍罕王赏麦

2．4递归遍历文件

2．5递归实现斐波那契数列

2．6循环实现斐波那契数列

2．7兔子繁殖问题

第3章栈和队列

3．1栈结构

3．2用栈做十进制与二进制的转换

3．3最小栈

3．4队列

3．5两个栈实现一个队列

3．6以递归方式反转一个栈

3．7递归加栈实现汉诺塔

第4章链表

4．1链表结构

4．2单向链表

4．2．1单向链表的追加和遍历

4．2．2单向链表的随机访问

4．2．3单向链表的随机插入

4．2．4单向链表的随机删除

4．2．5从尾到头打印单向链表

4．2．6反转一个单向链表

4．2．7反转单向链表中索引n~m处节点

4．2．8合并多个链表

4．2．9合并两个有序链表

4．2．10相交链表

4．2．11判断两个链表是否相交

4．2．12构造带环的单向链表

4．2．13判断链表是否有环并找出环的闭合点

4．3单向循环链表

4．3．1单向循环链表的追加和遍历

4．3．2约瑟夫环

4．4双向链表

4．4．1双向链表的追加和遍历

4．4．2双向链表的随机插入和删除

4．4．3双向链表实现插值法排序

4．5双向循环链表

4．5．1双向循环链表的追加和遍历

4．5．2双向循环链表的随机插入和随机删除

第5章数组

5．1数组结构

5．2消除数组中重复元素

5．3求数组中的最大值和次大值

5．4求一个数组的支点元素

5．5求数组的幸运值

5．6在数组中实现二分法查找

5．7求无序数组中最长连续子串的长度

5．8求数组中出现次数超过总数一半的数

5．9环路加油站问题

第6章树结构

6．1树、森林、二叉树

6．2二叉排序树

6．2．1二叉排序树的插入与中序遍历

6．2．2二叉排序树的深度优先遍历和广度优先遍历

6．2．3二叉排序树的前序遍历

6．2．4二叉排序树的后序遍历

6．2．5二叉排序树的广度优先遍历

6．2．6二叉排序树的节点删除

6．2．7二叉排序树的按层遍历

6．2．8求二叉树的最大深度、最小深度

6．2．9求二叉树中任意两个节点之间的最低公共祖先

6．3满二叉树

6．3．1满二叉树的构建

6．3．2判断一棵二叉树是不是满二叉树

6．4完全二叉树

6．4．1完全二叉树的插入

6．4．2查看完全二叉树

6．4．3判断一棵二叉树是不是完全二叉树

6．5平衡二叉树(AVL树)

6．5．1平衡二叉树的节点插入

6．5．2平衡二叉树的节点删除

6．6红黑树(RBTree)

6．6．1红黑树的插入

6．6．2红黑树的遍历操作

6．6．3红黑树的删除操作

6．6．4完整代码实现

6．6．5红黑树练习题

第7章堆结构

7．1堆

7．2二叉堆

7．2．1二叉堆的插入

7．2．2二叉堆的遍历

7．2．3二叉堆的删除

7．3大(小)顶堆

7．3．1大(小)顶堆的插入

7．3．2大(小)顶堆的堆排序

第8章散列表

8．1散列表(哈希表)

8．2散列函数

8．3求两数组交集

8．48个方向

第9章字典树

9．1字典树结构

9．2字典树的存入

9．3字典树的检索

9．4遍历字典树中的键

第10章图

10．1图结构

10．2图的表示

10．2．1邻接矩阵

10．2．2邻接表

10．2．3邻接矩阵和邻接表的使用场景

10．2．4边的权重

10．3图结构的代码实现

10．3．1邻接矩阵方式

10．3．2邻接表方式

10．4图的遍历

10．4．1图结构的深度优先遍历和广度优先遍历

10．4．2图遍历的代码实现

10．5生成树和最小生成树

10．5．1Prim算法求取最小生成树

10．5．2最小生成树的代码实现

第11章排序算法

11．1排序算法的几个基本概念

11．1．1排序的稳定性和不稳定性

11．1．2排序的时间复杂度

11．1．3排序的空间复杂度

11．2冒泡排序

11．3选择排序

11．4插入排序

11．5希尔排序

11．6归并排序

11．7快速排序

11．8计数排序

11．9桶排序

11．10基数排序

11．1110种常见排序算法的复杂度

“数据结构与算法”是计算机专业的一门基础课程，从事软件开发工作的人员基本都会用到其中的知识。但对于一个在企业工作二十多年的程序老鸟而言，遇到的算法盲或半盲比比皆是。

曾经和一位高校教计算机课程的讲师聊天，他竟然问我： “学数据库为什么要懂数据结构？”。在他看来，学数据库只要学会SQL语句也就够了。然而学生如果去企业面试，其中常被问到的问题是： “怎样在海量数据中高效地查询？”如今电商、微博、头条等网站动辄在万亿条记录中搜索，这样的运算量用SQL语句无法处理。

目前计算机人才市场两极分化严重。一些只需要简单的计算机操作或写界面布局的职位大量过剩，而懂算法，会优化，能结合业务实际提出更优解决方案的人才却很稀缺。面试者会在面试环节遇到很多算法题正是这种市场需求的反映。

写作本书的初衷是为了帮助读者系统掌握Python算法。但随着写作过程的深入，笔者认为一本书不足以让读者在未来的职业生涯中游刃有余地运用算法工具解决实际发生的问题。比如对于游戏中的寻路算法、模拟运动中的碰撞检测、电商中的商品推荐、自动驾驶中的临近识别等功能，如果没有一定的实战经验，根本看不出这些功能中哪里会用到哪些数据结构或算法，所以本书的定位仅是帮助读者入门。

本书采用图解的方式一步步描述具体算法，这种方式在数据结构与算法类图书中不多见，但笔者认为这种方式比单纯的文字描述更直观。由于笔者水平所限，书中难免会有疏漏，恳请读者多提宝贵意见。

编者2021年2月