《图解算法-使用Python》阅读笔记

写在前面

• 书籍介绍：暂无。
• 我的简评：暂无。
• ！！福利：文末有书籍地址、笔记思维导图、相关资料下载地址哦

第1章 进入算法的世界

1.1.生活中到处都是算法

• 定义

• 韦氏词典：在有限步骤内解决数学问题的程序

• 计算机领域：为了解决某项工作或某个问题，所需要有限数量的机械性或重复性指令与计算步骤

• 条件

• 5个：输入、输出、明确性、有限性、有效性

• 时间复杂度

• 一种“估算”的方法来衡量程序或算法的运行时间

1.2.常见算法简介

• 1.分治法

• 核心思想是将一个难以解决的大问题依照相同的概念，分割成两个或更多地子问题，以便各个击破

• 2.递归法

• 和分治法很像一对孪生兄弟，都是将一个复杂的算法问题进行分解，让规模越来越小，最终使子问题容易求解

• 2个条件：一个可以反复执行的递归过程；一个可以离开递归执行过程的出口

• 3.贪心法

• 从某个起点开始，在每一个解决问题步骤中使用贪心原则，即采取在当前状态下最有利或最优化的选择，不断的改进该答案，持续在每一步骤中选择最佳的方法，并且逐步逼近给定的目标

• 4.动态规划法

• 如果一个问题答案与子问题相关的话，就能将大问题拆解成各个小问题，其中与分治法最大不同的地方是可以让每一个子问题的答案存储起来，以供下次求解时直接取用

• 5.迭代法

• 无法使用公式一次求解，而需要使用迭代，例如用循环去重复执行程序代码的某些部分来得到答案

• 6.枚举法

• 核心思想是列举所有的可能。根据问题要求，逐一列举问题的解答，或者为了便于解决问题，把问题分为不重复、不遗漏的有限种情况，逐一列举各种情况，并加以解决，最终达到解决整个问题的目的

• 7.回溯法

• 一种可以找出所有（或一部分）解得一般性算法，同时避免枚举不正确的数值

第2章 常用的数据结构

2.1.认识数据结构

• 数据：指的是一种未经处理的原始文字、数字、符号或图形等

• 信息：利用大量的数据，经过有系统的整理、分析、筛选处理而提炼出来的，而且具有参考价格以及提供决策依据的文字、数字、符号或图表

• 数据结构主要表示数据在计算机内存中所存储的位置及其模式

• 通常分为以下几类：基本数据类型、结构化数据类型、抽象数据类型

2.2.数据结构的种类

• 1.数组

• 一排紧密相邻的可数内存，可提供一个能够直接访问单一数据内容的计算方法

• 2.链表

• 由许多相同数据类型的数据项按特定顺序排列而成的线性表

• 特点是各个数据项在计算机内存中的位置是不连续且随机存放的，优点是数据的插入或删除都相当方便

• 3.堆栈

• 一组相同数据类型的组合，具有“后进先出”的特性，所有的操作均在堆栈结构的顶端进行

• 4.队列

• 一种“先进先出”的数据结构，和堆栈一样都是一种有序线性表的抽象数据类型

2.3.树形结构

• 1.树的基本观念

• 由一个或一个以上的几点所组成

• 度数、层数、高度、树叶或终端节点、父节点、子节点、祖先和子孙、兄弟节点、非终端节点、同代、森林

• 2.二叉树

• 由有限节点所组成的集合，此集合可以为空集合，或由一个树根及其左右两个子树所组成

2.4.图形结构简介

• 由“顶点”和“边”所组成的集合

• 无向图、有向图

2.5.哈希表

• 一种存储记录的连续内存，通过哈希函数的应用，可以快速存取及查找数据

• 相关名词：桶、槽、碰撞、溢出、哈希表、同义词、加载密度、完美哈希

• 哈希函数设计原则：1、降低碰撞和溢出的产生；2、哈希函数不宜过于复杂，越容易计算越佳；3、尽量把文字的键值转换成数字的键值，以利于哈希函数的运算；4、计算出的值，尽量均匀分布在每一个桶中

第3章 排序算法

3.1.认识排序

• 将一组数据，按特定规则调换位置，使数据具有某种顺序关系（递增或递减）

• 排序的好处：数据较容易阅读；数据较利于统计和整理；可大幅减少数据查找的时间

3.2.冒泡排序法

• 从第一个元素开始比较相邻元素的大小，若大小顺序有误，则对调后再进行下一个元素的比较，就仿佛气泡逐渐从水底逐渐冒出到水面上一样

3.3.选择排序法

• 反复从未排序的数列中取出最小的元素，加入到另一个数列中，最后的结果即为已排序的数列

3.4.插入排序法

• 将数组中的元素，逐一与已排序好的数据进行比较，前两个元素先排好，再将第三个元素插入适当的位置，重复此步骤，直到排序完成

3.5.希尔排序法

• 将数据区分成特定间隔的几个小区块，以插入排序法排完区块内的数据后再逐渐减少间隔的距离

3.6.合并排序法

• 针对已排序好的两个或两个以上的数列（或数据文件）通过合并的方式，将其组合成一个大的且已排好序的数列（或数据文件）

3.7.快速排序法

• 先在数据中找到一个虚拟的中间值，并按此中间值将所有打算排序的数据分为两部分。其中，小于中间值得数据放在左边，大于中间值得数据放在右边，再以同样的方式分别处理左、右两边的数据，直到排序完为止

3.8.基数排序法

• 与之前所讨论的排序法不太一样，并不需要进行元素间的比较操作，而是属于一种分配模式排序方式

第4章 查找与哈希算法

4.1.常见查找算法的介绍

• 影响查找时间长短的主要因素有算法、数据存储的方式及结构

• 1.顺序查找法

• 将数据一项一项地按顺序逐个查找，所以不管数据顺序如何，都得从头到尾遍历一次

• 优点：文件在查找前不需要进行任何的处理与排序

• 缺点：查找速度较慢

• 2.二分查找法

• 将数据分割成两等份，再比较键值与中间值得大小，如果键值小于中间值，可确定要查找的数据在前半段，否则在后半部分

• 3.插值查找法

• 二分查找法的改进版，按照数据位置的分布，利用公式预测数据所在的位置，再以二分法的方式渐渐逼近

4.2.常见的哈希法简介

• 哈希法是使用哈希函数来计算一个键值所对应的地址，进而建立哈希表格，然后依靠哈希函数来查找到各个键值存放在表格中的地址，查找速度与数据多少无关，在没有碰撞和溢出的情况下，一次读取即可完成

• 哈希函数设计原则上，至少必须符合计算速度快与碰撞频率尽量低的两个特点

• 1.除留余数法

• 最简单的哈希函数是将数据除以某一个常数后，取余数来当索引

• 2.平方取中法

• 先计算数据的平方，之后再取中间的某段数字作为索引

• 3.折叠法

• 将数据转换成一串数字后，先将这串数字拆分几个部分，再将它们加起来，就计算出这个键值的Bucket Address（桶地址）

• 4.数字分析法

• 适用于数据不会更改，且为数字类型的静态表。在决定哈希函数时先逐一检查数据的相对位置和分布情况，将重复性高的部分删除

4.3.碰撞与溢出问题的处理

• 1.线性探测法

• 当发生碰撞情况时，若该索引对应的存储位置已有数据，则以线性的方式玩后寻找空的存储位置，一旦找到位置就把数据放进去

• 缺点：就是相类似的键值会聚集在一起

• 2.平方探测法

• 在平方探测中，当溢出发生时下一次查找的地址是(f(x)+i^2) mod B与(f(x)-i^2) mod B，即让数据值加或减i的平方

• 3.再哈希法

• 一开始就先设置一系列的哈希函数，如果使用第一种哈希函数出现溢出时就改用第二种，如果第二种也出现溢出则改用第三种，一直到没有发生溢出为止

第5章 数组与链表算法

数据存储结构

• 静态数据结构：使用连续分配的内存空间来存储有序表中的数据。优点：设计相当简单，而且读取与修改表中任意一个元素的时间都是固定的；缺点：删除或加入数据时，需要移动大量的数据

• 动态数据结构：使用不连续的内存空间存储具有线性表特性的数据。优点：数据的插入或删除都相当方便，不需要移动大量数据；缺点：设计时较为麻烦，也无法随机读取

5.1.矩阵

• 1.矩阵相加

• 2.矩阵相乘

• 3.转置矩阵

5.2.建立单向链表

• 1.连接功能

• 2.节点删除

• 3.反转

第6章 堆栈与队列算法

6.1.用数组实现堆栈

• 好处是设计算法相当简单

6.2.用链表实现堆栈

• 优点是随时可以动态改变链表长度，有效利用内存资源，缺点是设计的算法较为复杂

6.3.汉诺塔问题

• 使用递归法与堆栈概念来解决问题

6.4.八皇后问题

• 结合堆栈和回溯两种数据结构

6.5.用数组实现队列

• 好处是算法相当简单，缺点是数组大小无法根据队列的实际需要来动态申请

6.6.用链表实现队列

6.7.双向队列

• 允许队列两端中的任意一端都具备删除或加入功能，而且无论左右两端的队列，队首与队尾指针都是朝队列中央来移动

6.8.优先队列

• 一种不必遵守队列特性FIFO（先进先出）的有序线性表，其中每一个元素都赋予一个优先级，加入元素时可任意加入，但有最高优先级者则最先输出

第7章 树形结构及其算法

特殊的二叉树结构：满二叉树、完全二叉树、斜二叉树、严格二叉树

7.1.用数组实现二叉树

7.2.用链表实现二叉树

7.3.二叉树遍历

• 中序遍历（左中右）、后序遍历（左右中）、前序遍历（中左右）

7.4.二叉树节点的查找

7.5.二叉树节点的插入

7.6.二叉树节点的删除

7.7.堆积树排序法

• 选择排序法的改进版，可以减少在选择排序法中的比较次数，进而减少排序时间

第8章 图的数据结构及其算法

图除了被应用在数据结构中最短路径搜索、拓扑排序外，还能应用在系统分析中以时间为评审标准的性能评审技术

8.1.图的遍历

• 1.深度优先遍历

• 有点类似于前序遍历，从图的某一顶点开始遍历，被访问过的顶点就做上已访问的记号，接着遍历此顶点所有相邻且未访问过的顶点中的任意一个顶点，并做上已访问的记号，再以该点为新的起点继续进行深度优先的搜索

• 结合了递归和堆栈两种数据结构的技巧

• 2.广度优先遍历

• 从图的某个顶点开始遍历，被访问过的顶点就做上已访问的记号。接着遍历此顶点的所有相邻且未访问过的顶点中德任意一个顶点，并做上已访问的记号，再以该点为新的起点继续进行广度优先的遍历

• 使用队列和递归的技巧

8.2.最小生成树（MST）

• 计算连通网络中每个顶点所需的最少花费

• 1.Prim算法

• 2.Kruskal算法

8.3.图的最短路径法

• 计算连通树中任意两顶点的路径花费最少的路径

• 1.Dijkstra算法与A*算法

• 2.Floyd算法

写在后面

• pdf书籍、笔记思维导图、资料打包下载地址：暂无
• 思维导图在线查看：点击打开
• 得到电子书地址：暂无