Python 数据结构与算法详解

一、数据结构与算法

1、算法提出

1. 算法概念

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机按照确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。

算法是独立存在的一种解决问题的方法和思想。对于算法而言，实现的语言并不重要，重要的是思想。

算法可以有不同的语言描述实现版本（如 C 描述、C++ 描述、Python 描述等），我们现在是在用 Python 语言进行描述实现。

2. 算法的五大特性

1. 输入：算法具有 0 个或多个输入。
2. 输出：算法至少有 1 个或多个输出。
3. 有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成。
4. 确定性：算法中的每一步都有确定的含义，不会出现二义性。
5. 可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成。

如果 a+b+c=1000，且 a2+b2=c2（a、b、c 为自然数），如何求出所有 a、b、c 可能的组合?

第一次尝试：

import time

start_time = time.time()

# 三重循环
for a in range(1001):
    for b in range(1001):
        for c in range(1001):
            if a + b + c == 1000 and a**2 + b**2 == c**2:
                print("a:{}, b:{}, c:{}".format(a, b, c))

end_time = time.time()
print("used time: %f" % (end_time-start_time))
print("complete!")

运行结果：

a:0, b:500, c:500
a:200, b:375, c:425
a:375, b:200, c:425
a:500, b:0, c:500
used time: 620 seconds
complete!

第二次尝试：

import time

start_time = time.time()

# 两重循环
for a in range(1001):
    for b in range(1001):
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print("a:{}, b:{}, c:{}".format(a, b, c))

end_time = time.time()
print("used time: %f seconds" % (end_time-start_time))
print("complete!")

运行结果：

a:0, b:500, c:500
a:200, b:375, c:425
a:375, b:200, c:425
a:500, b:0, c:500
used time: 4 seconds
complete!

2、时间复杂度

1. 执行时间

1）执行时间反应算法效率

对于同一问题，我们给出了两种解决算法，在两种算法的实现中，我们对程序执行的时间进行了测算，发现两段程序执行的时间相差悬殊（620秒相比于4秒），由此我们可以得出结论：实现算法程序的执行时间可以反应出算法的效率，即算法的优劣。

2）单靠时间值绝对可信吗

假设我们将第二次尝试的算法程序运行在一台配置古老性能低下的计算机中，情况会如何？很可能运行的时间并不会比在我们的电脑中运行算法一的执行时间快多少。因此，单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的！

程序的运行离不开计算机环境（包括硬件和操作系统），这些客观原因会影响程序运行的速度并反应在程序的执行时间上。那么如何才能客观的评判一个算法的优劣呢？

2. 时间复杂度

我们假定计算机执行算法时每一个基本操作（即计算步骤）的时间是固定的一个时间单位，那么有多少个基本操作就代表会花费多少时间单位。当然，对于不同的机器环境而言，确切的单位时间是不同的，但是对于算法进行多少个基本操作（即花费多少时间单位）在规模数量级上却是相同的，由此可以忽略机器环境的影响而客观地反应算法的时间效率。

即时间复杂度就是用算法所需的步骤数量来衡量其效率。那么，如何来判定所需步骤数量的标准呢？此时可以使用“大 O 记法”。

3. 大 O 记法

对于算法的时间效率，我们可以用“大 O 记法”来表示，以下从数学上理解：

• 时间复杂度 —— T(n)：假设存在函数g，使得算法A处理规模为n的问题示例所用时间为 T(n)=O(g(n))，则称 O(g(n)) 为算法A的渐近时间复杂度，简称时间复杂度，记为 T(n)。
• “大O记法” —— g(n)：对于单调的整数函数 f，如果存在一个整数函数 g 和实常数 c>0，使得对于充分大的 n，总有 f(n)<=c*g(n)，就说函数 g 是 f 的一个渐近函数（忽略常数），记为 f(n)=O(g(n))。也就是说，在趋向无穷的极限意义下，函数f的增长速度受到函数 g 的约束，亦即函数 f 与函数 g 的特征相似。

通俗理解：当解决问题的计算步骤跟 n 相关时，把旁支末节（次要项和常数项）全部忽略掉，只留下最关键的特征（最高次项），就是大 O 表示法。

以上述引入的示例代码为例：

# 例1：a+b+c=1000，且 a^2+b^2=c^2（a,b,c 为自然数）
for a in range(1001):  # 基本计算步骤为1000次
    for b in range(1001):  # 1000次
        for c in range(1001):  # 1000次
            if a + b + c == 1000 and a**2 + b**2 == c**2:  # 1次
                print("a:{}, b:{}, c:{}".format(a, b, c))  # 1次

# 例2：如果改为 a+b+c=2000，且 a^2+b^2=c^2（a,b,c 为自然数）呢？

简单划分示例中的计算步骤数量：

• 例1：T = 1000 * 1000 * 1000 * 2
• 例2：T = 2000 * 2000 * 2000 * 2 
• 即：T(n) = n * n * n * 2 = n^3 * 2

当使用大 O 计法时，去掉相关系数 2，只会留下 n3，记为 g(n) = n3 。此时，可说T(n) = g(n)。

因此，即使相关系数有所变化，如T(n) = n * n * n * 2 = n3 * 10，我们也认为两者（n3 * 2 与 n3 * 10）效率“差不多”。

4. 最坏时间复杂度

分析算法时，存在几种可能的考虑：

• 算法完成工作最少需要多少基本操作，即最优时间复杂度。
• 算法完成工作最多需要多少基本操作，即最坏时间复杂度。
• 算法完成工作平均需要多少基本操作，即平均时间复杂度。

对于最优时间复杂度，其价值不大，因为它没有提供什么有用信息，其反映的只是最乐观最理想的情况，没有参考价值。

对于最坏时间复杂度，提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作。

对于平均时间复杂度，是对算法的一个全面评价，因此它完整全面的反映了这个算法的性质。但另一方面，这种衡量并没有保证，不是每个计算都能在这个基本操作内完成。而且，对于平均情况的计算，也会因为应用算法的实例分布可能并不均匀而难以计算。

因此，我们主要关注算法的最坏情况，亦即最坏时间复杂度。

5. 时间复杂度的几条基本计算规则

1. 基本操作，即只有常数项，认为其时间复杂度为 O(1)。
2. 顺序结构，时间复杂度按加法进行计算。
3. 循环结构，时间复杂度按乘法进行计算。
4. 分支结构，时间复杂度取各分支中的最大值。
5. 判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略。
6. 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度。

示例：

1 for a in range(n):  # 循环
2     for b in range(n):  # 循环
3         c = 1000 - a - b  # 基本操作
4         if a**2 + b**2 == c**2:  # 分支：要么进入分支中的print，要么退出
5             print("a:{}, b:{}, c:{}".format(a, b, c))  # 基本操作

其时间复杂度：T(n)

= n * n * (1 + max(1, 0))

= n^2 * 2

= O(n^2)

6. 算法分析

第一次尝试的算法核心部分：

1 for a in range(0, 1001):
2     for b in range(0, 1001):
3         for c in range(0, 1001):
4             if a**2 + b**2 == c**2 and a+b+c == 1000:
5                 print("a, b, c: %d, %d, %d" % (a, b, c))

时间复杂度：T(n) = O(n*n*n) = O(n^3)

第二次尝试的算法核心部分：

1 for a in range(0, 1001):
2     for b in range(0, 1001-a):
3         c = 1000 - a - b
4         if a**2 + b**2 == c**2:
5             print("a, b, c: %d, %d, %d" % (a, b, c))

时间复杂度：T(n) = O(n*n*(1+1)) = O(n*n) = O(n^2)

由此可见，我们尝试的第二种算法要比第一种算法的时间复杂度好得多。

7. 常见的时间复杂度

习惯上将 log2n （以 2 为底的对数）简写成 logn。 

8. 常见时间复杂度之间的关系

3、Python 内置类型性能分析

1. timeit 模块

Python3 中的 timeit 模块可以用来测试小段代码的运行时间。其中主要通过两个函数来实现：timeit 和 repeat，代码如下：

def timeit(stmt="pass", setup="pass", timer=default_timer,
           number=default_number, globals=None):
    """Convenience function to create Timer object and call timeit method."""
    return Timer(stmt, setup, timer, globals).timeit(number)

def repeat(stmt="pass", setup="pass", timer=default_timer,
           repeat=default_repeat, number=default_number, globals=None):
    """Convenience function to create Timer object and call repeat method."""
    return Timer(stmt, setup, timer, globals).repeat(repeat, number)

在上面的代码中可见，无论是 timeit 还是 repeat 都是先生成 Timer 对象，然后调用 Timer 对象的 timeit 或 repeat 函数。

在使用 timeit 模块时，可以直接使用 timeit.timeit()、tiemit.repeat()，还可以先用 timeit.Timer() 来生成一个 Timer 对象，然后再用 TImer 对象用 timeit() 和 repeat() 函数，后者再灵活一些。

上述两个函数的入参：

• stmt：用于传入要测试时间的代码，可以直接接受字符串的表达式，也可以接受单个变量，也可以接受函数。传入函数时要把函数申明在当前文件中，然后在 stmt = ‘func()’ 执行函数，然后使用 setup = ‘from __main__ import func’
• setup：传入stmt的运行环境，比如stmt中使用到的参数、变量，要导入的模块等。可以写一行语句，也可以写多行语句，写多行语句时要用分号；隔开语句。
• number：要测试的代码的运行次数，默认 100000 次，对于耗时的代码，运行太多次会比较慢，此时建议自己修改一下运行次数。
• repeat：指测试要重复几次，每次的结果构成列表返回，默认 3 次。

2. list 的操作测试

import timeit

# ----生成列表的效率----

def t1():
    l = []
    for i in range(1000):
        l = l + [i]

def t2():
    l = []
    for i in range(1000):
        l.append(i)

def t3():
    l = [i for i in range(1000)]

def t4():
    l = list(range(1000))


t1 = timeit.timeit("t1()", setup="from __main__ import t1", number=1000)
print("+ used time:{} seconds".format(t1))
print()
t2 = timeit.timeit("t2()", setup="from __main__ import t2", number=1000)
print("append used time:{} seconds".format(t2))
print()
t3 = timeit.timeit("t3()", setup="from __main__ import t3", number=1000)
print("[i for i in range(n)] used time:{} seconds".format(t3))
print()
t4 = timeit.timeit("t4()", setup="from __main__ import t4", number=1000)
print("list(range(n)) used time:{} seconds".format(t4))
print()

# ----pop元素的效率----

x = list(range(1000000))
pop_from_zero = timeit.timeit("x.pop(0)", setup="from __main__ import x", number=1000)
print("pop_from_zero used time:{} seconds".format(pop_from_zero))
print()
x = list(range(1000000))
pop_from_last = timeit.timeit("x.pop()", setup="from __main__ import x", number=1000)
print("pop_from_last used time:{} seconds".format(pop_from_last))

运行结果：

+ used time:3.7056619 seconds

append used time:0.46458129999999986 seconds

[i for i in range(n)] used time:0.18458229999999975 seconds

list(range(n)) used time:0.0845849000000003 seconds

pop_from_zero used time:0.5516430999999997 seconds

pop_from_last used time:0.0002724000000000615 seconds

3. list 内置操作的时间复杂度

通过顺序表实现。

4. dict 内置操作的时间复杂度

通过哈希表实现。

4、数据结构

需求：我们如何用 Python 中的类型来保存一个班的学生信息？ 如果想要快速的通过学生姓名获取其信息呢？

实际上当我们在思考这个问题的时候，我们已经用到了数据结构。列表和字典都可以存储一个班的学生信息，但是想要在列表中获取一名同学的信息时，就要遍历这个列表，其（最坏）时间复杂度为 O(n)。而使用字典存储时，可将学生姓名作为字典的键，学生信息作为值，进而查询时不需要遍历便可快速获取到学生信息，其时间复杂度为 O(1)。

我们为了解决问题，需要将数据保存下来，然后根据数据的存储方式来设计算法以实现数据的处理，那么数据的存储方式不同就会导致需要不同的算法进行处理。我们希望算法解决问题的效率越快越好，于是就需要考虑数据究竟如何保存的问题，这就是数据结构。数据结构是为算法服务的，具体选择什么数据结构，与期望支持的算法（操作）有关。

在上面的问题中我们可以选择 Python 中的列表或字典来存储学生信息。列表和字典就是 Python 内建帮我们封装好的两种数据结构。

1. 数据结构概念

数据是一个抽象的概念，将其进行分类后得到程序设计语言中的基本类型。如：int，float，char 等。数据元素之间不是独立的，存在特定的关系，这些关系便是结构。数据结构指数据对象中数据元素之间的关系。

Python 给我们提供了很多现成的数据结构类型，这些系统自己定义好的，不需要我们自己去定义的数据结构就叫做 Python 的内置数据结构，比如列表、元组、字典。而有些数据组织方式，Python 系统里面没有直接定义，需要我们自己去定义实现这些数据的组织方式，这些数据组织方式称之为 Python 的扩展数据结构，比如栈，队列等。

2. 算法与数据结构的区别

数据结构只是静态的描述了数据元素之间的关系。

高效的程序需要在数据结构的基础上设计和选择算法。

总结：算法是为了解决实际问题而设计的，数据结构是算法实现的容器。

3. 抽象数据类型（Abstract Data Type）

抽象数据类型（ADT）的含义是指一个数学模型以及定义在此数学模型上的一组操作。即把数据类型和数据类型上的运算捆在一起，进行封装。

引入抽象数据类型的目的是把数据类型的表示和数据类型的运算实现，与这些数据类型和运算在程序中的引用隔开，使它们相互独立。

最常用的数据运算有五种：

• 插入
• 删除
• 修改
• 查找
• 排序

二、算法思想

1、算法效率

算法，简单来说就是利用计算机解决问题的步骤。狭义的来讲，算法可看作是数据传递和处理的方法，就像是各种排序算法等。算法的应用不单体现在编程中，广义的来讲，算法更像是一种事物运行的逻辑和规则。

算法必须具备 5 个重要条件：

1. 输入：0 个或多个输入数据，这些输入必须有清楚的描述或定义。
2. 输出：至少会有一个输出结果，不可以没有输出结果。
3. 明确性：每一个质龄或步骤必须是简洁明确的。
4. 有效性：步骤清楚且可行，能让用户用纸笔计算而求出答案。
5. 有限性：在有限步骤后一定会结束，不能无限循环。

数据结构可以看作是算法实现的容器，通过一系列特殊结构的数据集合，能够将算法更为高效而可靠地执行起来。即数据结构是为算法服务的，具体选择什么数据结构，与期望支持的算法（操作）有关。

数据结构和相关的算法就是数据进入计算机进行处理的一套完整逻辑。

算法效率度量：

• 时间复杂度（Time Complexity）

时间复杂度决定了运行时间的长短。一个算法花费的时间与算法中语句的执行次数成正比。

• 空间复杂度（Space Complexity）

空间复杂度决定了计算时所需的空间资源多少，是对一个算法在运行过程中临时占用存储空间大小的度量。

一个算法在计算机存储上所占用的存储空间包括 3 个方面：

1. 存储算法本身所占用的存储空间（与算法书写的长短成正比）。
2. 算法的输入输出数据所占用的存储空间（由要解决的问题决定，是通过函数调用而来的，不随算法不同而改变）。
3. 算法在运行过程中临时占用的存储空间（因算法而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，称这种算法为“就地”（in-place）进行的，是节省存储的算法）。

2、枚举

先，最为简单的思想，枚举算法。枚举也叫穷举，顾名思义，就是穷尽列举。枚举思想的应用场景十分广泛，也非常容易理解。简单来说，枚举就是将问题所有可能的解，按照不重复、不遗漏的原则依次列举出来，然后一一带入问题检验，从而从一系列可能解中获得能够解决问题的精确解。

枚举虽然看起来简单，但是其实还是有一些容易被人忽视的考虑点。比方说待解决问题的「可能解/候选解」的筛选条件，「可能解」之间相互的影响，穷举「可能解」的代价，「可能解」的穷举方式等等。

很多时候实际上不必去追求高大上的复杂算法结构，反而大道至简，采用枚举法就能够很好地规避系统复杂性带来的冗余，同时或许在一定程度上还能够对空间进行缩减。

枚举思想的流程可以用下图来表示。通过实现事先确定好「可能解」，然后逐一在系统中进行验证，根据验证结果来对「可能解」进行分析和论证。这是一种很明显的结果导向型的思想，简单粗暴地试图从最终结果反向分析「可能解」的可行性。

不过，枚举思想的劣势当然也很明显。在实际的运行程序中，能够直接通过枚举方法进行求解的问题少之又少。而当「可能解」的筛选条件不清晰，导致「可能解」的数量和范围无法准确判断时，枚举就失去了意义。

然而当「可能解」的规模比较小，同时依次验证的过程容易实施时，枚举思想不失为一种方便快捷的方式。只不过在具体使用时，还可以针对应用场景对「可能解」的验证进行优化。

这种优化可以从两个方向入手：

1. 问题的简化，尽可能对需要处理的问题进行模型结构上的精简。这种精简具体可体现在问题中的变量数目，减少变量的数据，从而能够从根本上降低「可能解」的组合。
2. 对筛选「可能解」的范围和条件进行严格判断，尽可能的剔除大部分无效的「可能解」。

虽说如此，但是一般而言大部分枚举不可用的场景都是由于「可能解」的数量过多，无法在有限空间或有限时间内完成所有可能性的验证。不过实际上枚举思想是最接近人的思维方式，在更多的时候是用来帮助我们去「理解问题」，而不是「解决问题」。

常见应用：

• 选择排序
• 顺序查找法
• ...

3、迭代

迭代法（iterative method）是指无法使用公式一次求解，而需要使用迭代，例如用循环取重复执行程序代码的某些部分来得到答案，本质思想是递推。

递推思想跟枚举思想一样，都是接近人类思维方式的思想，甚至在实际生活具有比枚举思想更多的应用场景。人脑在遇到未知的问题时，大多数人第一直觉都会从积累的「先验知识」出发，试图从「已知」推导「未知」，从而解决问题，说服自己。

事实上，迭代就是一种递推的算法思想。递推思想的核心就是从已知条件出发，逐步推算出问题的解。实现方式很像是初高中时我们的数学考卷上一连串的「因为」「所以」。那个时候还是用三个点来表示的。

而对于计算机而言，复杂的推导其实很难实现。计算机擅长的是执行高密度重复性高的工作，对于随机性高变化多端的问题反而不好计算。相比之下，人脑在对不同维度的问题进行推导时具有更高的自由度。

比方说，人脑可以很容易的从「太阳从东边升起」推出「太阳从西边落下」，然后大致推出「现在的时间」。但是对于计算机而言并没有那么容易，你可能需要设置一系列的限制条件，才能避免计算机推出「太阳/月亮/星星」从「南/北/东边」「落下/飞走/掉落」的可能性。

这个例子的用意是在说明，计算机在运用递推思想时，大多都是重复性的推理。比方说，从「今天是1号」推出「明天是2号」。这种推理的结构十分类似，往往可以通过继而往复的推理就可以得到最终的解。

递推思想用图解来表示可以参见下图。每一次推导的结果可以作为下一次推导的开始。

常见应用：

• 冒泡排序
• 矩阵相加、相乘、转置
• 链表
• ...

4、递归

「递」的理解可以是逐次、逐步。在递归中可理解为逐次回归迭代，直到跳出回归。

递归算法实际上是把问题转化成规模更小的同类子问题，先解决子问题，再通过相同的求解过程逐步解决更高层次的问题，最后获得问题的最终解。递归算法要求子问题跟父问题的结构相同。

用一句话来形容递归算法的实现，就是在函数内部调用（函数）自身的算法。所以在实现的过程中，最重要的是确定递归过程终止的条件，也就是迭代过程跳出的条件判断。否则，程序会在自我调用中无限循环，最终导致内存溢出而崩溃。

递归思想其实就是一个套娃过程。一般官方都是严禁套娃行为的。所以在使用时一定要明确「套娃」举动的停止条件，及时止损。

常见应用：

• 回溯算法
• 阶乘
• 斐波那契数列
• 堆栈
• 汉诺塔
• 二叉树遍历
• 图的深度优先遍历
• 图的广度优先遍历
• ...

5、分治

分治，分而治之。分治算法的核心步骤就是两步，一是分，二是治。在实际的运用中，分治算法主要包括两个维度的处理，一是自顶向下，将主要问题逐层级划分为子问题；二是自底向上，将子问题的解逐层递增融入主问题的求解中。

分治算法很像是一种向下管理的思想，从最高级层层划分，将子任务划分给不同的子模块，进而可以进行大问题的拆分，对系统问题的粒度进行细化，寻求最底层的最基本的解。这样的思路在很多领域都有运用，比如几何数学中的正交坐标、单位坐标、基的概念等，都是通过将复杂问题依照相同的概念，分割成多个子问题，直到这些子问题足够简单到可以解决，最后再将各个子问题的解合并，从而得到原问题的最终解。

分治算法还引申出了一系列的问题，为什么分，怎么分，怎么治，治后如何。

• 为什么要分？这个很好解释，由于主要问题的规模过大，无法直接求解，所以需要对主要问题进行粒度划分。
• 那怎么分？遵循计算机最擅长的高密度重复性运算，划分出来的子问题需要相互独立并且与原问题结构特征相同，这样能够保证解决子问题后，主问题也就能够顺势而解。
• 怎么治？这就涉及到最基本子问题的求解，我们约定最小的子问题是能够轻易得到解决的，这样的子问题划分才具有意义，所以在治的环节就是需要对最基本子问题的简易求解。
• 治后如何？子问题的求解是为了主问题而服务的。当最基本的子问题得到解后，需要层层向上递增，逐步获得更高层次问题的解，直到获得原问题的最终解。

如下图所示，通过层层粒度上的划分，将原问题划分为最小的子问题，然后再向上依次得到更高粒度的解。从上而下，再从下而上。先分解，再求解，再合并。

常见应用：

• 递归算法
• 归并排序
• 快速排序
• 二分查找法
• 插值查找法
• ...

6、动态规划

我们知道分治思想最重要的一点是分解出的子问题是相互独立且结构特征相同的，这一点并不是所有问题都能满足，许多问题划分的子问题往往都是相互重叠且互相影响的，那么就很难使用分治算法进行有效而又干净的子问题划分。

于是乎，动态规划来了。动态规划同样需要将问题划分为多个子问题，但是子问题之间往往不是互相独立的。

动态规划的主要做法是：如果一个问题答案与子问题相关的话，就能将大问题拆解成各个小问题，其中与分治法最大不同的地方是可以让每一个子问题的答案被存储起来，以供下次求解时直接取用。这样的做法不但能减少再次计算的时间，还可以将这些解组合成大问题的解答，故而使用动态规划可以解决重复计算的问题。

动态规划是在目前看来非常不接近人类思维方式一种算法，主要原因是在于人脑在演算的过程中很难对每一次决策的结果进行记忆。动态规划在实际的操作中，往往需要额外的空间对每个阶段的状态数据进行保存，以便下次决策的使用。

动态规划主要就是用来解决多阶段决策的问题，但是实际问题中往往很难有统一的处理方法，必须结合问题的特点来进行算法的设计，这也是这种算法很难真正掌握的原因。

最优化原理：

当前子问题的解可看作是前多个阶段问题的完整总结。因此这就需要在子问题求解的过程中进行多阶段的决策，同时当前阶段之前的决策都能够构成一种最优的子结构。这就是所谓的最优化原理。

一个最优化策略具有这样的性质：不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。同时，这样的最优策略是针对已作出决策的总结，对后来的决策没有直接影响，只能借用目前最优策略的状态数据。这也被称之为无后效性。

动态规划的求解思路如下图解：动态规划的开始需要将问题按照一定顺序划分为各个阶段，然后确定每个阶段的状态，如图中节点的 F0 等。然后重点是根据决策的方法来确定状态转移方程。也就是需要根据当前阶段的状态确定下一阶段的状态。在这个过程中，下一状态的确定往往需要参考之前的状态。因此需要在每一次状态转移的过程中将当前的状态变量进行记录，方便之后的查找。

示例：根据动态规划法的思想，修改斐波那契数列的递归算法。

output = [None] * 1000  # 斐波那契数列的暂存区

def fibonacci(n):
    result = output[n]
    if result is None:
        if n == 0:
            result = 0
        elif n == 1:
            result = 1
        else:
            result = fibonacci(n-1) + fibonacci(n-2)
        output[n] = result
    return result

if __name__ == "__main__":
for i in range(10):
    print(fibonacci(i))

7、贪心

人活在世上，不可能每一个选择都那么恰到好处，很多问题根本没有准确解，甚至于无解。所以在某些场景下，傻傻地去追求问题的最精确解是没有意义的。

有人说，那还有最优解呢。难道最优解都不要了吗？没错，许多问题虽然找不到最精确的解，但是的确会存在一个或者一些最优解。但是一定要去追求这些最优解吗？我看不一定。

算法的存在不是单纯地为了对问题求解，更多的是提供一种「策略」。何谓「策略」，解决问题的一种方式，一个角度，一条路。所以，贪心思想是有价值的。

从贪心二字可得知，这个算法的目的就是为了「贪图更多」。但是这种贪心是「目光短浅」的，这就导致贪心算法无法从长远出发，只看重眼前的利益。

具体点说，贪心算法在执行的过程中，每一次都会选择当前最大的收益，但是总收益却不一定最大。所以这样傻白甜的思路带来的好处就是选择简单，不需要纠结，不需要考虑未来。

贪心算法的实现过程就是从问题的一个初始解出发，每一次都作出「当前最优」的选择，直至遇到局部极值点。

• 缺点：贪心所带来的局限性很明显，就是无法保证最后的解是最优的，很容易陷入局部最优的情况。
• 优点：但是它每一次做选择的速度很快，同时判断条件简单，能够比较快速地给出一种差不多的解决方案。

下图表示的是对多条直线的交点进行求解。很显然，图中的直线是不存在统一交点的，但是可以通过算法求得统一交点的最优解。若是采用贪心算法，那么在进行迭代时，每一次都会选择离此时位置最近的直线进行更新。这样一来，在经过多次迭代后，交点的位置就会在某一片区域无限轮回跳转。而这片区域也就是能得出的大致的最优解区域。

常见应用：

• 最小生成树
• 图的最短路径法
• ...

8、回溯

回溯算法也可称作试探算法，是不是让你回忆起了在女神面前的小心翼翼。简单来说，回溯的过程就是在搜索过程中寻找问题的解，当发现不满足求解问题时，就回溯（即不再递归到下一层，而是返回到上一层，以节省时间），尝试别的路径，避免无效搜索，是一种走不通就退回再走的方法。

这样看起来，回溯算法很像是一种进行中的枚举算法，在行进的过程中对所有可能性进行枚举并判断。常用的应用场景就在对树结构、图结构以及棋盘落子的遍历上。

回溯思想在许多大规模的问题的求解上都能得到有效的运用。回溯能够将复杂问题进行分步调整，从而在中间的过程中可对所有可能运用枚举思想进行遍历。这样往往能够清晰地看到问题解决的层次，从而可以帮助更好地理解问题的最终解结构。

假设目的是从 O0 到达 O4，需要对所有节点进行回溯遍历路径。那么回溯算法的过程则需要在前进的每一步对所有可能的路径进行试探。

比方说，O0 节点前进的路径有三条，分别是上中下条的 O1。回溯过程的开始，先走上面的 O1，然后能够到达上面 O2，但是这时是一条死路。那么就需要从 O2 退回到 O1，而此时 O1 的唯一选择也走不通，所以还需要从 O1 退回到 O0。然后继续试探中间的 O1。

回溯算法的过程就是不断进行这样的试探、判断、退回并重新试探，直至找到一条完整的前进路径。只不过在这个过程中，可以通过「剪枝」等限制条件降低试探搜索的空间，从而避免重复无效的试探。比方说上下的 O2 节点，在经过 O0-O1-O2 的试探之后，就已经验证了该节点不可行性，下次就无须从 O1 开始重复对 O2 的试探。

常见应用：

• 八皇后问题
• ...

三、顺序表及其算法

1、线性表与顺序表

在程序中，经常需要将一组（通常是同为某个类型的）数据元素作为整体管理和使用，用变量记录它们，传进传出函数等。一组数据中包含的元素个数可能发生变化（可以增加或删除元素）。

对于这种需求，最简单的解决方案便是将这样一组元素看成一个序列，用元素在序列里的位置和顺序，表示实际应用中的某种有意义的信息，或者表示数据之间的某种关系。

这样的一组序列元素的组织形式，我们可以将其抽象为线性表。一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。

线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更复杂的数据结构的实现基础。

根据线性表的内存存储的方式，基本可分为两种实现模型：

• 静态数据结构（static data structure）

• 它使用连续分配的内存空间（contiguous allocation）来存储有序表中的数据。静态数据结构是在编译时就会给相关的变量分配好内存空间。例如，顺序表就是一种典型的静态数据结构。
• 缺点：由于在建立静态数据结构的初期就必须声明最大可能要占用的固定内存空间，因此容易造成内存的浪费。
• 优点：设计时相当简单，而且读取与修改表中任意一个元素的时间都是固定的（一次操作即可）；缺点是删除或加入数据时，需要移动大量的数据。

• 动态数据结构（dinamic data structure）

• 动态数据结构又称为“链表”（linked list），它使用不连续的内存空间存储具有线性表特征的数据。
• 优点：数据的插入或删除都相当方便，不需要移动大量数据。另外，动态数据结构的内存分配是在程序执行时才进行的，所以不需要事先声明，这样能充分节省内存。
• 缺点：在设计数据结构时较为麻烦，另外在查找数据时，也无法像静态数据一样随机读取，必须按顺序找到该数据才行。

2、顺序表的形式

图 a：基本顺序表

图a表示的是顺序表的基本形式，数据元素本身连续存储，每个元素所占的存储单元大小固定相同，元素的下标是其逻辑地址，而元素存储的物理地址（实际内存地址）可以通过存储区的起始地址 Loc(e0) 加上逻辑地址（第 i 个元素）与存储单元大小（c）的乘积计算而得，即：

Loc(ei) = Loc(e^0) + c*i

故，访问指定元素时无需从头遍历，通过计算便可获得对应地址，其时间复杂度为 O(1)。

图 b：元素外围顺序表

如果元素的大小不统一，则须采用图b的元素外置的形式，将实际数据元素另行存储，而顺序表中各单元位置保存对应元素的地址信息（即链接）。由于每个链接所需的存储量相同，通过上述公式，可以计算出元素链接的存储位置，而后顺着链接找到实际存储的数据元素。注意，图 b 中的 c 不再是数据元素的大小，而是存储一个链接地址所需的存储量，这个量通常很小。

图b这样的顺序表也被称为对实际数据的索引，这是最简单的索引结构。

3、顺序表的结构与实现

顺序表的结构：

一个顺序表的完整信息包括两部分：

• 一部分是表中的元素集合，即真实的数据区。
• 一部分是为实现正确操作而需记录的信息（表头信息），即有关表的整体情况的信息，这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。

顺序表的两种基本实现方式：

图a：一体式结构。

存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。

一体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。

图b：分离式结构（动态顺序表）。

表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。

1. 元素存储区替换

一体式结构由于顺序表信息区与数据区连续存储在一起，所以若想更换数据区，则只能整体搬迁，即整个顺序表对象（指存储顺序表的结构信息的区域）改变了。

分离式结构若想更换数据区，只需将表信息区中的数据区链接地址更新即可，而该顺序表对象不变。

2. 元素存储区扩充

采用分离式结构的顺序表，若想将数据区更换为存储空间更大的区域，则可以在不改变表对象的前提下对其数据存储区进行扩充，所有使用这个表的地方都不必修改。只要程序的运行环境（计算机系统）还有空闲存储，这种表结构就不会因为满了而导致操作无法进行。人们把采用这种技术实现的顺序表称为动态顺序表，因为其容量可以在使用中动态变化。

3. 扩充的两种策略

线性增长：

• 每次扩充增加固定数目的存储位置，如每次扩充增加 10 个元素位置。
• 特点：节省空间，但是扩充操作频繁，操作次数多。

倍数增长：

• 每次扩充容量加倍，如每次扩充增加一倍存储空间。
• 特点：减少了扩充操作的执行次数，但可能会浪费空间资源（以空间换时间，推荐的方式）。

4、顺序表的操作

1. 增加元素

如图所示，为顺序表增加新元素“111”的三种方式：

a）尾端加入元素，时间复杂度为 O(1)。

b）非保序的加入元素（不常见），时间复杂度为 O(1)。

c）保序的元素加入，（最坏）时间复杂度为 O(n)。

2. 删除元素

a）删除表尾元素，时间复杂度为 O(1)。

b）非保序的元素删除（不常见），时间复杂度为 O(1)。

c）保序的元素删除，时间复杂度为 O(n)。

5、Python 中的顺序表

Python 中的 list 和 tuple 两种类型采用了顺序表的实现技术，具有前面讨论的顺序表的所有性质。

Tuple 是不可变类型，即不变的顺序表，因此不支持改变其内部状态的任何操作，而其他方面，则与 list 的性质类似。

1. list 的基本实现技术

Python 标准类型 list 就是一种元素个数可变的线性表，可以加入和删除元素，并在各种操作中维持已有元素的顺序（即保序），而且还具有以下行为特征：

1）基于下标访问

• 基于下标（位置）的高效元素访问和更新，时间复杂度是 O(1)。
• 为满足该特征，采用了顺序表技术，表中元素保存在一块连续的存储区中。

2）允许不断加入元素，且对象标识不变

• 为满足该特征，就必须能更换元素存储区，并且为保证更换存储区时 list 对象的标识 id 不变，只能采用分离式结构的实现技术。

3）允许元素类型不一致

• 为满足该特征，采用了元素外置的形式，因为存储的地址链接所占用的大小一致。 

在 Python 的官方实现中，list 就是一种采用分离式技术实现的动态顺序表。这就是为什么用 list.append(x)（或 list.insert(len(list), x)，即尾部插入）比在指定位置插入元素效率高的原因。

List 实现采用了如下的策略：在建立空表（或者很小的表）时，系统分配一块能容纳 8 个元素的存储区。在执行插入操作（insert 或 append）时，如果元素存储区满就换一块 4 倍大的存储区。但如果此时的表已经很大（目前的阀值为 50000），则改变策略，采用加一倍的方法。引入这种改变策略的方式，是为了避免出现过多空闲的存储位置。

四、链表及其算法

1、链表

1. 为什么需要链表

顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。

链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

2. 链表的定义

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。

3. 链表与顺序表的对比

链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大，但对存储空间的使用要相对灵活。

链表与顺序表的各种操作复杂度如下所示：

注意虽然表面看起来复杂度都是 O(n)，但是链表和顺序表在插入和删除时进行的是完全不同的操作：

• 链表的主要耗时操作是遍历查找，删除和插入操作本身的复杂度是 O(1)。
• 顺序表查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作，只能通过拷贝和覆盖的方法进行。

2、单向链表

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

• 元素域 elem 用来存放具体的数据。
• 链接域 next 用来存放下一个节点的位置（python 中的 id 标识）。
• 变量 p 指向链表的头节点（首节点）的位置，从 p 出发能找到表中的任意节点。

 自定义单链表的操作：

• is_empty()：链表是否为空。
• length()：链表长度。
• travel()：遍历整个链表。
• add(item)：链表头部添加元素。
• append(item)：链表尾部添加元素。
• insert(pos, item)：指定位置添加元素。
• remove(item)：删除元素。
• search(item)：元素是否存在。
• reverse()：反转链表。

头部增加节点：

指定位置添加节点： 

删除节点：

实现： 

class Node:
    """单链表的节点"""
    def __init__(self, item):
        # item 存放数据元素
        self.item = item
        # next是下一个节点的标识
        # 直接指向下一个节点对象即可
        self.next = None


class SingleLinkList:
    """单链表"""
    def __init__(self, node=None):
        # head只是一个变量，指向头节点
        self.head = node

    def is_empty(self):
        """判断链表是否为空"""
        return self.head == None

    def length(self):
        """链表长度"""
        # cur代表当前所在节点，先初始化指向头节点
        cur = self.head
        count = 0
        #尾节点指向None，当未到达尾节点时
        while cur != None:
            count += 1
            # 将cur后移一个节点
            cur = cur.next
        return count

    def travel(self):
        """遍历链表"""
        # cur初始化指向头节点
        cur = self.head
        while cur != None:
            print(cur.item, end=" ")
            cur = cur.next
        print()

    def append(self, item):
        """尾部添加节点，即尾插法"""
        node = Node(item)
        # 先判断链表是否为空，若是空链表，则将head指向新节点
        if self.is_empty():
            self.head = node
        # 若不为空，则找到尾部，将尾部节点的next指向新节点
        else:
            cur = self.head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def add(self, item):
        """头部添加节点，即头插法"""
        # 先创建一个保存item值的节点
        node = Node(item)
        # 该节点先指向头节点
        node.next = self.head
        # 头节点再指向该节点
        self.head = node

    def insert(self, pos, item):
        """指定位置添加节点"""
        # 若指定位置为第一个元素之前，则执行头插法
        if pos <= 0:
            self.add(item)
        # 若指定位置超过链表尾部，则执行尾插法
        elif pos > (self.length()-1):
            self.append(item)
        # 找到指定位置
        else:
            node = Node(item)
            # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
            pre = self.head
            for i in range(pos-1):
                pre = pre.next
            # 先将新节点的next指向插入指定位置本身的节点
            node.next = pre.next
            # 将插入指定位置的前一个节点的next指向新节点
            pre.next = node

    def search(self, item):
        """查看节点是否存在，返回布尔值"""
        cur = self.head
        while cur != None:
            if cur.item == item:
                return True
            cur = cur.next
        return False

    def remove(self, item):
        """删除节点"""
        cur = self.head
        pre = None
        while cur != None:
            # 找到了指定元素
            if cur.item == item:
                # 如果头节点就是被删除的节点
                if not pre:
                    # 将头指针指向头结点的后一个节点
                    self.head = cur.next
                else:
                    # 将删除位置前一个节点的next指向删除位置的后一个节点
                    pre.next = cur.next
                break
            else:
                # 继续按链表后移节点
                pre = cur
                cur = cur.next

    def reverse(self):
        if self.head is None:
            print("链表为空，无需反转")
            return
        pre = None
        while self.head != None:
            tmp = pre
            pre = self.head
            self.head = self.head.next
            pre.next = tmp
        self.head = pre
        print("反转结果：", end="")
        self.travel()


if __name__ == "__main__":
    ll = SingleLinkList()
    print(ll.is_empty())  # True
    ll.append(1)
    ll.append(2)
    ll.append(4)
    print(ll.is_empty())  # False
    ll.travel()  # 1 2 4
    ll.add(5)
    ll.travel()  # 5 1 2 4

    ll.insert(-1, -1)
    ll.travel()  # -1 5 1 2 4
    ll.insert(9, 10)
    ll.travel()  # -1 5 1 2 4 10
    ll.insert(2, 11)
    ll.travel()  # -1 5 11 1 2 4 10

    print(ll.search(11))  # True
    print(ll.search(100))  # False
    ll.remove(-1)
    ll.remove(1)
    ll.travel()  # 5 11 2 4 10
    ll.reverse()  # 反转结果：10 4 2 11 5

3、双向链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：

• 一个指向前一个节点，当此节点为第一个节点时，指向空值；
• 而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

指定位置插入节点： 

删除元素： 

实现： 

from test import SingleLinkList


class Node:
    "双向链表节点"
    def __init__(self, item):
        self.item = item
        self.prev = None
        self.next = None


class DoubleLinkList(SingleLinkList):
    "双向链表"

    """以下方法继承自SingleLinkList"""
    # def __init__(self, node=None):
        # # head只是一个变量，指向头节点
        # self.head = node

    # def is_empty(self):
        # "判断链表是否为空"
        # return self.head == None

    # def length(self):
        # "链表长度"
        # # cur代表当前所在节点，先初始化指向头节点
        # cur = self.head
        # count = 0
        # #尾节点指向None，当未到达尾节点时
        # while cur != None:
            # count += 1
            # # 将cur后移一个节点
            # cur = cur.next
        # return count

    # def travel(self):
        # "遍历链表"
        # # cur初始化指向头节点
        # cur = self.head
        # while cur != None:
            # print(cur.item, end=" ")
            # cur = cur.next
        # print()

    # def search(self, item):
        # "查看节点是否存在，返回布尔值"
        # cur = self.head
        # while cur != None:
            # if cur.item == item:
                # return True
            # cur = cur.next
        # return False

    def append(self, item):
        "尾部添加节点，即尾插法"
        node = Node(item)
        # 先判断链表是否为空，若是空链表，则将head指向新节点
        if self.is_empty():
            self.head = node
        # 若不为空，则找到尾部，将尾部节点的next指向新节点
        else:
            cur = self.head
            while cur.next != None:
                cur = cur.next
            cur.next = node
            node.prev = cur

    def add(self, item):
        "头部添加节点，即头插法"
        # 先创建一个保存item值的节点
        node = Node(item)
        # 如果是空链表，将head指向node
        if self.is_empty():
            self.head = node
        else:
            # 将node的next指向头节点
            node.next = self.head
            # 将头节点的prev指向node
            self.head.prev = node
            # 将头节点指向node
            self.head = node

    def insert(self, pos, item):
        "指定位置添加节点"
        # 若指定位置为第一个元素之前，则执行头插法
        if pos <= 0:
            self.add(item)
        # 若指定位置超过链表尾部，则执行尾插法
        elif pos > (self.length()-1):
            self.append(item)
        # 找到指定位置
        else:
            node = Node(item)
            cur = self.head
            # 移动到指定位置的前一个位置
            for i in range(pos-1):
                cur = cur.next
            # 将node的prev指向cur
            node.prev = cur
            # 将node的next指向指定位置
            node.next = cur.next
            # 将指定位置的prev指向node
            cur.next.prev = node
            # 将cur的next指向node
            cur.next = node

    def remove(self, item):
        "删除节点"
        if self.is_empty():
            return
        else:
            cur = self.head
            # 如果头节点就是被删除的节点
            if cur.item == item:
                # 如果链表只有这一个节点
                if cur.next == None:
                    self.head = None
                else:
                    # 将第二个节点的prev指向None
                    cur.next.prev = None
                    # 将head指向第二个节点
                    self.head = cur.next
                return
            while cur != None:
                # 找到了指定元素
                if cur.item == item:
                    # 将cur的前一个节点的next指向cur的下一个节点
                    cur.prev.next = cur.next
                    # 将cur的下一个节点的next指向cur的前一个节点
                    cur.next.prev = cur.prev
                    break
                else:
                    # 继续按链表后移节点
                    cur = cur.next


# 测试
if __name__ == "__main__":
    dl = DoubleLinkList()
    dl.add(1)
    dl.add(2)
    dl.append(3)
    dl.insert(2, 4)
    dl.insert(4, 5)
    dl.insert(0, 6)
    print("length: ", dl.length())
    dl.travel()
    print(dl.search(3))
    print(dl.search(13))
    dl.remove(6)
    dl.travel()

4、单向循环链表

单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。

操作：

• is_empty()：判断链表是否为空
• length()：返回链表的长度
• travel()：遍历
• add(item)：在头部添加一个节点
• append(item)：在尾部添加一个节点
• insert(pos, item)：在指定位置pos添加节点
• remove(item)：删除一个节点
• search(item)：查找节点是否存在

实现：

class Node:
    """单链表的节点"""
    def __init__(self, item):
        # item 存放数据元素
        self.item = item
        # next是下一个节点的标识
        # 直接指向下一个节点对象即可
        self.next = None


class SingleCycLinkList:
    """单向循环链表"""
    def __init__(self, node=None):
        # head只是一个变量，指向头节点
        self.head = node

    def is_empty(self):
        """判断链表是否为空"""
        return self.head == None

    def length(self):
        """链表长度"""
        if self.is_empty():
            return 0
        # cur代表当前所在节点，先初始化指向头节点
        cur = self.head
        count = 1
        #尾节点指向头节点，当未到达尾节点时
        while cur.next != self.head:
            count += 1
            # 将cur后移一个节点
            cur = cur.next
        return count

    def travel(self):
        """遍历链表"""
        if self.is_empty():
            return
        # cur初始化指向头节点
        cur = self.head
        while cur.next != self.head:
            print(cur.item, end=" ")
            cur = cur.next
        print(cur.item, end="\n")

    def append(self, item):
        """尾部添加节点，即尾插法"""
        node = Node(item)
        # 先判断链表是否为空，若是空链表，则将head指向新节点
        if self.is_empty():
            self.head = node
            node.next = node
        # 若不为空，则找到尾部，将尾部节点的next指向新节点
        else:
            cur = self.head
            print(1)
            while cur.next != self.head:
                cur = cur.next
            # 将尾节点指向node
            cur.next = node
            # 将node指向头节点
            node.next = self.head

    def add(self, item):
        """头部添加节点，即头插法"""
        # 先创建一个保存item值的节点
        node = Node(item)
        if self.is_empty():
            self.head = node
            node.next = node
        else:
            # 该节点先指向头节点
            node.next = self.head
            # 移动到链表尾部，将尾部节点的next指向node
            cur = self.head
            while cur.next != self.head:
                cur = cur.next
            cur.next = node
            # 头节点再指向该节点
            self.head = node


    def insert(self, pos, item):
        """指定位置添加节点"""
        # 若指定位置为第一个元素之前，则执行头插法
        if pos <= 0:
            self.add(item)
        # 若指定位置超过链表尾部，则执行尾插法
        elif pos > (self.length()-1):
            self.append(item)
        # 找到指定位置
        else:
            node = Node(item)
            # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
            pre = self.head
            for i in range(pos-1):
                pre = pre.next
            # 先将新节点的next指向插入指定位置本身的节点
            node.next = pre.next
            # 将插入指定位置的前一个节点的next指向新节点
            pre.next = node

    def search(self, item):
        """查看节点是否存在，返回布尔值"""
        if self.is_empty():
            return False
        cur = self.head
        while cur.next != self.head:
            if cur.item == item:
                return True
            cur = cur.next
            # cur指向尾节点
        if cur.item == item:
            return True
        return False

    def remove(self, item):
        """删除节点"""
        # 若链表为空，则直接返回
        if self.is_empty():
            return
        cur = self.head
        pre = None
        # 若头节点就是要被删除的节点
        if cur.item == item:
            # 如果链表不止一个节点
            if cur.next != self.head:
                # 先找到尾部节点，将尾部节点的next指向第二个节点
                while cur.next != self.head:
                    cur = cur.next
                cur.next = self.head.next
                self.head = self.head.next
            # 如果链表只有一个节点
            else:
                self.head = None
        # 若头节点不是要被删除的节点
        else:
            pre = self.head
            while cur.next != self.head:
                # 找到了要删除的节点
                if cur.item == item:
                    # 删除
                    pre.next = cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next
            # cur 指向尾节点
            if cur.item == item:
                # 尾部删除
                pre.next = cur.next


if __name__ == "__main__":
    ll = SingleCycLinkList()
    ll.add(1)
    ll.add(2)
    ll.append(3)
    ll.append(7)
    ll.insert(2, 4)
    ll.insert(6, 5)
    ll.insert(-1, 6)
    print("length: ", ll.length())  # 7
    ll.travel()  # 6 2 1 4 3 7 5
    print(ll.search(3))  # True
    print(ll.search(13))  # False
    ll.remove(6)
    ll.travel()  # 2 1 4 3 7 5

五、堆栈与队列算法

1、堆栈（Stack）

1. 堆栈简介

堆栈（stack）也叫“栈”，是一种后进先出（LIFO, Last In First Out）的线性表，它的特点在于只允许在堆栈的一端（top，栈顶）进行插入数据（push）和弹出数据（pop）的运算。

栈没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。

栈与线性表的区别：

• 栈（和队列）：描述的是数据的操作方式。
• 线性表：描述的是数据的存储方式。

2. 栈结构的实现

栈可以用顺序表实现，也可以用链表实现。

• 以顺序表来实现栈的好处是设计的算法相当简单，但是，如果栈本身的大小是变动的，而顺序表大小只能事先规划和声明好，那么顺序表规划太大了会浪费空间，规划太小了则又不够用。
• 以链表来实现栈的好处是随时可以动态改变链表长度，能有效利用内存资源，不过缺点是设计的算法较为复杂。

代码实现 1：用列表实现栈

• Stack()：创建一个新的空栈。
• push(item)：添加一个新的元素 item 到栈顶。
• pop()：弹出栈顶元素。
• peek()：返回栈顶元素。
• is_empty()：判断栈是否为空。
• size()：返回栈的元素个数。

class Stack:
    "栈"

    def __init__(self):
        self.__list = []

    def push(self, item):
        "添加一个新的元素item到栈顶"
        self.__list.append(item)  # 时间复杂度为O(1)
        # self.__list.insert(0, item)  # 时间复杂度为O(n)

    def pop(self):
        "弹出栈顶元素"
        return self.__list.pop()  # 接收列表pop方法的返回值
        # self.__list.pop(0)  # 时间复杂度为O(n)

    def peek(self):
        "返回栈顶元素"
        if self.__list:
            return self.__list[-1]
        else:
            return

    def is_empty(self):
        "判断栈是否为空"
        return self.__list == []
        # return not self.__head

    def size(self):
        "返回栈的元素个数"
        return len(self.__list)


if __name__ == "__main__":
    s = Stack()
    print(s.is_empty())  # True
    s.push(1)
    print(s.is_empty())  # False
    s.push(2)
    s.push(3)
    print(s.peek())  # 3
    s.push(4)
    s.push("hello")
    print(s.pop())  # hello
    print(s.pop())  # 4
    print(s.size())  # 3

代码实现 2：用链表实现栈

栈的操作：

• Stack()：创建一个新的空栈。
• push(item)：添加一个新的元素 item 到栈顶。
• pop()：弹出栈顶元素。
• is_empty()：判断栈是否为空。

class Node:
    "堆栈的链表节点类"

    def __init__(self, data):
        self.data = data  # 本节点存储的数据
        self.next = None  # 指向下一个节点

class Stack:
    "堆栈类"

    # 初始化栈顶节点变量
    def __init__(self):
        self.top = None

    # 判断堆栈是否为空
    def is_empty(self):
        if not self.top:
            return True
        else:
            return False

    # 将指定数据压栈
    def push(self, data):
        new_add_node = Node(data)
        new_add_node.next = self.top
        self.top = new_add_node

    # 弹栈
    def pop(self):
        if self.is_empty():
            print("===当前堆栈已为空===")
            return
        else:
            cur = self.top.data  # 记录栈顶数据
            self.top = self.top.next  # 将栈顶节点指向后一个节点
            return cur

# 主程序
s = Stack()
while 1:
    i = int(input("压栈请输入【1】，弹栈请输入【0】，停止操作则输入【-1】："))
    if i == -1:
        break
    elif i == 1:
        value = input("请输入要压栈的元素值：")
        s.push(value)
    elif i == 0:
        print("弹栈元素为 %s" % s.pop())

print("="*40)
while not s.is_empty():  # 陆续打印弹栈元素
    print("弹栈顺序为：%s" % s.pop())
print("="*40)

执行结果：

压栈请输入【1】，弹栈请输入【0】，停止操作则输入【-1】：1
请输入要压栈的元素值：7
压栈请输入【1】，弹栈请输入【0】，停止操作则输入【-1】：1
请输入要压栈的元素值：8
压栈请输入【1】，弹栈请输入【0】，停止操作则输入【-1】：1
请输入要压栈的元素值：9
压栈请输入【1】，弹栈请输入【0】，停止操作则输入【-1】：1
请输入要压栈的元素值：10
压栈请输入【1】，弹栈请输入【0】，停止操作则输入【-1】：0
弹栈元素为 10
压栈请输入【1】，弹栈请输入【0】，停止操作则输入【-1】：0
弹栈元素为 9
压栈请输入【1】，弹栈请输入【0】，停止操作则输入【-1】：-1
========================================
弹栈顺序为：8
弹栈顺序为：7
========================================

2、队列（Queue）

1. 队列简介

队列是一种先进先出（FIFO, First In First Out）的线性表，只允许在一端进行插入数据（enqueue），在另一端进行删除数据（dequeue）。

在队列中，允许插入的一端为队尾，允许删除的一端为队头，队列不允许在中间部位进行操作。

假设队列是 q =（a1，a2，……，an），那么 a1 就是队头元素，而 an 是队尾元素。这样我们就可以删除时，总是从 a1 开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

2. 队列结构的实现

同栈一样，队列也可以用顺序表或者链表实现。

1）单向队列

代码实现 1：用列表实现队列

• Queue()：创建一个空的队列。
• enqueue(item)：往队列中添加一个 item 元素。
• dequeue()：从队列头部删除一个元素。
• is_empty()：判断一个队列是否为空。
• size()：返回队列的大小。

class Queue:
    "队列"

    def __init__(self):
        self.__list = []

    def enqueue(self, item):
        "往队列中添加一个item元素"
        # 根据具体的使用频率，决定添加/删除元素的方式
        self.__list.append(item)  # O(1)
        # self.__list.insert(0, item)  # O(n)

    def dequeue(self):
        "从队列头部删除一个元素"
        return self.__list.pop(0)  # O(n)
        # return self.__list.pop()  # O(1)

    def is_empty(self):
        "判断一个队列是否为空"
        return self.__list == []
        # return not self.__list

    def size(self):
        "返回队列的大小"
        return len(self.__list)


if __name__ == "__main__":
    q = Queue()
    print(q.is_empty())  # True
    q.enqueue("hello")
    print(q.is_empty())  # False
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    print(q.dequeue())  # hello
    print(q.dequeue())  # 1
    print(q.size())  # 2

代码实现 2：用链表实现队列

• Queue()：创建一个空的队列。
• enqueue(item)：往队列中添加一个 item 元素。
• dequeue()：从队列头部删除一个元素。
• is_empty()：判断一个队列是否为空。

class Node:
    "队列的链表节点类"

    def __init__(self, data):
        self.data = data  # 本节点存储的数据
        self.next = None  # 指向下一个节点

class Queue:
    "队列类"

    # 初始化队列头部和尾部节点变量
    def __init__(self):
        self.head = None
        self.end = None

    # 判断队列是否为空
    def is_empty(self):
        if not self.head:
            return True
        else:
            return False

    # 往队列尾部添加元素
    def enqueue(self, data):
        new_node = Node(data)
        # 表明添加的是第一个元素
        if not self.end:
            self.head = new_node
        # 否则将新节点连接到队列末尾
        else:
            self.end.next = new_node
        # 将新的队列末尾变量指向新节点
        self.end = new_node

    # 删除队列头部元素
    def dequeue(self):
        if self.is_empty():
            print("===当前队列已为空===")
            return
        else:
            cur = self.head.data  # 记录队列头部数据
            self.head = self.head.next  # 将头部节点指向后一个节点
            return cur

# 主程序
q = Queue()
while 1:
    i = int(input("添加元素请输入【1】，删除元素请输入【0】，停止操作则输入【-1】："))
    if i == -1:
        break
    elif i == 1:
        value = input("请输入要添加的元素值：")
        q.enqueue(value)
    elif i == 0:
        print("删除元素：%s" % q.dequeue())

print("="*40)
while not q.is_empty():
    print("元素删除顺序为：%s" % q.dequeue())
print("="*40)

执行结果：

添加元素请输入【1】，删除元素请输入【0】，停止操作则输入【-1】：1
请输入要添加的元素值：5
添加元素请输入【1】，删除元素请输入【0】，停止操作则输入【-1】：1
请输入要添加的元素值：6
添加元素请输入【1】，删除元素请输入【0】，停止操作则输入【-1】：1
请输入要添加的元素值：7
添加元素请输入【1】，删除元素请输入【0】，停止操作则输入【-1】：1
请输入要添加的元素值：8
添加元素请输入【1】，删除元素请输入【0】，停止操作则输入【-1】：0
删除元素：5
添加元素请输入【1】，删除元素请输入【0】，停止操作则输入【-1】：0
删除元素：6
添加元素请输入【1】，删除元素请输入【0】，停止操作则输入【-1】：-1
========================================
元素删除顺序为：7
元素删除顺序为：8
========================================

2）双向列表

双向队列（deque，全名 double-ended queue）又称双端链表，是一种具有队列和栈的性质的数据结构。

双向队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双向队列可以在队列任意一端入队和出队。

通常在一般的应用上，双向队列可以区分为两种：

1. 数据只能从一端加入，但可从两端取出。
2. 数据可从两端加入，但只能从一端取出。

代码实现 1：用列表实现双端列表

• Deque()：创建一个空的双向队列。
• add_front(item)：从队头加入一个 item 元素。
• add_rear(item)：从队尾加入一个 item 元素。
• remove_front()：从队头删除一个 item 元素。
• remove_rear()：从队尾删除一个 item 元素。
• is_empty()：判断双向队列是否为空。
• size()：返回队列的大小。

class Deque:
    "双端队列"

    def __init__(self):
        self.__list = []

    def add_front(self, item):
        "往队列头部添加一个item元素"
        self.__list.insert(0, item)

    def add_rear(self, item):
        "往队列尾部添加一个item元素"
        self.__list.append(item)

    def remove_front(self):
        "从队列头部删除一个元素"
        return self.__list.pop(0)

    def remove_rear(self):
        "从队列尾部删除一个元素"
        return self.__list.pop()

    def is_empty(self):
        "判断一个队列是否为空"
        return self.__list == []
        # return not self.__list

    def size(self):
        "返回队列的大小"
        return len(self.__list)


if __name__ == "__main__":
    d = Deque()
    print(d.is_empty())  # True
    d.add_front(1)
    d.add_front(2)
    d.add_rear(3)
    d.add_rear(4)
    print(d.is_empty())  # False
    print(d.size())  # 4
    print(d.remove_front())  # 2
    print(d.remove_rear())  # 4
    print(d.size())  # 2

代码实现 2：用链表实现双向队列 

• Deque()：创建一个空的双向队列。
• enqueue(item)：从队头加入一个 item 元素。
• dequeue(action)：根据 action 从队头或队尾删除一个元素。
• is_empty()：判断双向队列是否为空。

class Node:
    "队列的链表节点类"

    def __init__(self, data):
        self.data = data  # 本节点存储的数据
        self.next = None  # 指向下一个节点

class Deque:
    "双向队列类"

    # 初始化队列头部和尾部节点变量
    def __init__(self):
        self.head = None
        self.end = None

    # 判断队列是否为空
    def is_empty(self):
        if not self.head:
            return True
        else:
            return False

    # 往队列尾部添加元素
    def enqueue(self, data):
        new_node = Node(data)
        # 表明添加的是第一个元素
        if not self.end:
            self.head = new_node
        # 否则将新节点连接到队列末尾
        else:
            self.end.next = new_node
        # 将新的队列末尾变量指向新节点
        self.end = new_node

    # 可从队列两端删除元素
    def dequeue(self, action):
        if self.is_empty():
            print("===当前队列已为空===")
            return
        # 从队列头部删除元素
        if action == 1:
            value = self.head.data  # 记录队列头部数据
            self.head = self.head.next  # 将头部节点指向后一个节点
            return value
        # 从队列尾部删除元素
        elif action == 2:
            value = self.end.data  # 记录队末数据
            # 若队列只有一个元素
            if not self.head.next:
                self.head = None
                self.end = None
            # 否则遍历找到倒数第二个节点
            else:
                cur = self.head
                while cur.next.next:
                    cur = cur.next
                self.end = cur
                self.end.next = None
            return value

# 主程序
q = Deque()
print("用链表来实现双向队列")
print("="*40)
while 1:
    i = int(input("添加元素请输入【1】，删除元素请输入【0】，停止操作则输入【-1】："))
    if i == -1:
        break
    elif i == 1:
        value = input("请输入要添加的元素值：")
        q.enqueue(value)
    elif i == 0:
        print("从队头删除元素：%s" % q.dequeue(1))
        print("从队尾删除元素：%s" % q.dequeue(2))

3）优先队列

优先队列（Priority Queue）是一种不必遵守队列特性（先进先出）的有序线性表，其中的每一个元素都被赋予了一个优先级（Priority），加入元素时可任意加入，但有最高优先级者（Highest Priority Out First，HPOF）则最先输出。

像一般医院中的急诊室，当然以最严重的病患优先诊治，跟进入医院挂号的顺序无关。又例如在计算机中 CPU 的作业调度，优先级调度（Priority Scheduling，PS）就是一种按进程优先级”调度算法“（Scheduling Algorithm）进行的调度，这种调度就会使用到优先队列，好比优先级高的用户，就比一般用户拥有较高的权力。

注意，当各个元素按输入先后次序为优先级时，就是一般的队列；若是以输入先后次序的倒序作为优先级，此优先队列即为一个堆栈。

六、排序算法

1、排序算法简介

排序算法（英语：Sorting algorithm）是一种能将一串数据依照特定顺序进行排列的一种算法。

1. 排序算法的稳定性

稳定性：稳定排序算法会让原本有相等键值的纪录维持其相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录 R 和 S，且在原本的列表中 R 出现在 S 之前，在排序过的列表中 R 也将会是在 S 之前。

当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。

(4, 1) (3, 1) (3, 7) (5, 6)

在这个状况下，有可能产生两种不同的结果，一个是让相等键值的纪录维持相对的次序，而另外一个则没有：

(3, 1) (3, 7) (4, 1) (5, 6)  （维持次序）
(3, 7) (3, 1) (4, 1) (5, 6)  （次序被改变）

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。

不稳定排序算法可以被特别地实现为稳定，做这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较（比如上面的比较中加入第二个标准：第二个键值的大小），就会被决定使用在原先数据次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。

2. 常见算法效率比较

性能从优到劣： 

2、冒泡排序 

冒泡排序（英语：Bubble Sort）是一种简单的排序算法，它通过不断地交换“大数”的位置达到排序的目的。因为不断出现“大数”类似于水泡不断出现，因此被形象地称为冒泡排序算法。

它重复地遍历要排序的数列，一次比较两个元素，如果他们的大小顺序有误则把它们交换过来。遍历数列的工作是重复地进行直到没有元素再需要交换，也就是说该数列已经排序完成。

冒泡排序算法的运作如下：

• 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对元素需要比较。

1. 时间复杂度

• 最优时间复杂度：O(n)（表示第一次遍历发现没有任何可以交换的元素，则排序结束）
• 最坏时间复杂度：O(n2)
• 稳定性：稳定

2. 交换过程图示（第一次遍历）

那么我们需要进行n-1次冒泡过程，每次对应的比较次数如下图所示： 

3. 代码实现

Python 版：

def bubble_sort(alist):
    "冒泡排序"
    n = len(alist)
    for j in range(n-1):  # 控制轮数（图示中的Pass）
        count = 0  # 记录每轮中的比较次数
        for i in range(n-1-j):  # 每轮遍历中的元素比较次数，逐渐减少（图示中的Comparisons）；也可以使用 for i in range(n-1, 0, -1); for j in range(i):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
                count += 1
        # 优化时间复杂度，若该轮没有交换元素，即代表列表已是有序，则无需再进行下一轮比较
        # 即可直接退出
        if count == 0:
            return


# j: 0     i: range(n-1-0) = n-1
# j: 1     i: range(n-1-1) = n-2
# j: 2     i: range(n-1-2) = n-3
# ...
# j: n-2   i: range(n-1-(n-2)) = 1


if __name__ == "__main__":
    li = [1, 21, 4, 2, 56, 2, 34, 67]
    bubble_sort(li)
    print(li)  # [1, 2, 2, 4, 21, 34, 56, 67]

Java 版：

public static void main(String[] args) {
        int[] input = {12, 34, 65, 23, 54, 12, 34, 54};
        bubbleSort(input);
        System.out.println(Arrays.toString(input));
    }

    public static void bubbleSort(int[] arr) {
        int length = arr.length;
        for (int i=0; i<length-1; i++) {
            int changeCount = 0;
            for (int j=0; j<(length-1-i); j++) {
                if (arr[j]>arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    changeCount ++;
                }
            }
            if (changeCount==0) {
                return;
            }
        }
    }

3、选择排序

选择排序（Selection sort）的算法算是枚举法的应用，就是反复从未排序的数列中取出最小（大）的元素，加入到另一个数列中，最后的结果即为已排序的数列。它的具体工作原理如下：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n 个元素的数列进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

1. 时间复杂度

• 最优时间复杂度：O(n2)
• 最坏时间复杂度：O(n2)
• 稳定性：不稳定（考虑升序每次选择最大的情况）

Python版的选择排序：

理论上选择排序的时间复杂度为 O(n2)，但在 Python 中较为特殊，因为在 Python 列表中寻找最小的那个数不需要逐个比较，使用 min() 就可以一步到位地得到最小的数，所以使用 Python 版的选择排序，时间复杂度是 O(n)。因此理论上 Python 版本的排序算法中选择排序算法是最快的。

2. 排序过程图示

3. 代码实现

Python 常规版：

def selected_sort(alist):
    n = len(alist)
    # 需要进行n-1次选择操作
    for i in range(n-1):
        # 记录最小位置
        min_index = i
        # 从i+1位置到末尾，选择出最小的元素
        for j in range(i+1, n):
            if alist[j] < alist[min_index]:
                min_index = j
        # 如果选择出的元素不在正确位置，进行交换
        if min_index != i:
            alist[i], alist[min_index] = alist[min_index], alist[i]


alist = [54, 226, 93, 17, 77, 31, 44, 55, 20]
selected_sort(alist)
print(alist)

python 内置的 min()：

import random
import timeit

def random_list(n):
    return [random.randint(0, 100) for i in range(n)]

def selection_sort(i_list):
    if len(i_list) <= 1:
        return i_list
    # 一个长度为n的数列需要排序n-1轮
    for i in range(0, len(i_list)-1):
        if i_list[i] != min(i_list[i:]):
            # 使用min()找到列表剩余元素中的最小值
            min_index = i_list.index(min(i_list[i:]), i)
            i_list[i], i_list[min_index] = i_list[min_index], i_list[i]
        # print("第%s轮的排序结果：%s" % (i+1, i_list))
    return i_list

if __name__ == "__main__":
    i_list = random_list(20)
    print(i_list)
    print(selection_sort(i_list))
    print(timeit.timeit("selection_sort(i_list)", "from __main__ import selection_sort, i_list", number=100))

Java 版：

public static void main(String[] args) {
        int[] input = {12, 34, 65, 23, 54, 12, 34, 54};
        selectSort(input);
        System.out.println(Arrays.toString(input));
    }

    public static void selectSort(int[] arr) {
        int length = arr.length;
        for (int i=0; i<length-1; i++) {
            int tmpMin = arr[i];
            for (int j=i+1; j<length; j++) {
                if (arr[j]<tmpMin) {
                    tmpMin = arr[j];
                    arr[j] = arr[i];
                    arr[i] = tmpMin;
                }
            }
        }
    }

4、插入排序

插入排序（Insertion Sort）可能是最好理解的排序了。插入排序方法与打扑克取牌的排序很相似，在打扑克时，每取一张新牌，都会与手上已有的牌进行比较，将新牌插入到比自己小的牌后面。等取完所有的牌后，手上已有的牌就是各有序的序列。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

当原始序列的元素大部分已排好序的情况下，插入排序会非常有效率，因为它不需要执行太多的数据搬移操作。

1. 时间复杂度

• 最优时间复杂度：O(n)（升序排序时，序列已经处于升序状态）
• 最坏时间复杂度：O(n2)
• 稳定性：稳定

2. 排序过程图示

3. 代码实现 

Python 版：

def insertion_sort(data):
    for i in range(1, len(data)):
        tmp = data[i]  # 暂存数据
        count = i
        while i >= 1 and tmp < data[i-1]:  # 遍历与前一个元素比较
            data[i] = data[i-1]  # 把所有元素往后移一位
            i -= 1
        data[i] = tmp  # 若当前元素大于等于前一个元素，则当前位置放入暂存数据
        print("第%d次排序结果：%s" % (count, data))
    return data


data = [12, 11, 23, 4, 1, 5, 12, 31, 4]
insertion_sort(data)

执行结果：

第1次排序结果：[11, 12, 23, 4, 1, 5, 12, 31, 4]
第2次排序结果：[11, 12, 23, 4, 1, 5, 12, 31, 4]
第3次排序结果：[4, 11, 12, 23, 1, 5, 12, 31, 4]
第4次排序结果：[1, 4, 11, 12, 23, 5, 12, 31, 4]
第5次排序结果：[1, 4, 5, 11, 12, 23, 12, 31, 4]
第6次排序结果：[1, 4, 5, 11, 12, 12, 23, 31, 4]
第7次排序结果：[1, 4, 5, 11, 12, 12, 23, 31, 4]
第8次排序结果：[1, 4, 4, 5, 11, 12, 12, 23, 31]

Java 版：

public static void main(String[] args) {
        int[] input = {12, 34, 65, 23, 54, 12, 34, 54, 17};
        insertSort(input);
        System.out.println(Arrays.toString(input));
    }

    public static void insertSort(int[] arr) {
        for (int i=1; i<arr.length; i++) {
            int tmp = arr[i];
            for (int j=i; j>0; j--) {
                if (tmp<arr[j-1]) {
                    arr[j]=arr[j-1];
                } else {
                    arr[j] = tmp;
                    break;
                }
            }
        }
    }

5、希尔排序

希尔排序（Shell Sort）是插入排序算法的一种更高效的改进版本。该方法因 DL.Shell 于 1959 年提出而得名。

希尔排序的基本思想是：将数组列在一个表中，并对每一列进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行，最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。

1. 时间复杂度

• 最优时间复杂度：根据步长序列的不同而不同
• 最坏时间复杂度：O(n2)
• 稳定性：不稳定

2. 希尔排序过程

例如，假设有这样一组数 [13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10]，如果我们以步长为 5 开始进行排序，我们可以通过将这列表放在有 5 列的表中来更好地描述算法，这样他们就应该看起来是这样（竖着的元素是步长组成）：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45]。这时 10 已经移至正确位置了，然后再以 3 为步长进行排序：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以 1 步长进行排序（此时就是简单的插入排序了）。

3. 示例分析

4. 代码实现 

# 希尔排序
def shell_sort(alist):
    count = 1  # 打印排序次数
    n = len(alist)
    gap = n // 2  # 步长需通过数学计算，质数最好。为了算法方便，习惯选2
    # gap变化到0前，子序列插入算法执行的次数
    while gap > 0:
        # 子序列的插入算法，与普通插入算法区别在于gap步长
        for i in range(gap, n):
            tmp = alist[i]
            while i >= gap and tmp < alist[i-gap]:  # 每组子序列中，当前元素与前gap个元素比较
                alist[i] = alist[i-gap]
                i -= gap
            alist[i] = tmp
        print("gap=%d, 第%d次排序的结果：%s" % (gap, count, alist))
        # 每轮排序对半缩短gap
        gap //= 2
        count += 1


alist = [63, 92, 27, 36, 45, 71, 58, 7]
shell_sort(alist)

执行结果：

gap=4, 第1次排序的结果：[45, 71, 27, 7, 63, 92, 58, 36]
gap=2, 第2次排序的结果：[27, 7, 45, 36, 58, 71, 63, 92]
gap=1, 第3次排序的结果：[7, 27, 36, 45, 58, 63, 71, 92]

6、快速排序

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），是目前公认最佳的排序法。它通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

步骤为：

1. 从数列中挑出一个元素，称为“基准”(pivot)。
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

1. 时间复杂度

• 最优时间复杂度：O(nlogn)
• 最坏时间复杂度：O(n2)
• 稳定性：不稳定

2. 排序过程图示

3. 代码实现

Python 版：

def quick_sort(alist, start, end):
    # 递归的退出条件
    if start >= end:
        return
    # 设定起始元素为要寻找位置的基准元素
    mid_value = alist[start]
    # low为从左往右的游标
    low = start
    # high为从右往左的游标
    high = end
    # 当low与high未重合
    while low < high:
        # 当low与high未重合时，若high指向的元素不比基准元素小，则high向左移动一位
        while low < high and alist[high] >= mid_value:
            high -= 1
        # 若high指向的元素比基准元素小，则退出循环，交换元素位置
        alist[low] = alist[high]
        # 当low与high未重合时，若low指向的元素比基准元素小，则low向右移动一位
        while low < high and alist[low] < mid_value:
            low += 1
        # 若low指向的元素比基准元素大，则推出循环，交换元素位置
        alist[high] = alist[low]
    # 当low与high重合，退出循环，此时所指位置为基准元素的正确位置
    # 将基准元素放到该位置
    alist[low] = mid_value
    # 对基准元素左边的子序列进行递归快速排序
    quick_sort(alist, start, low-1)
    # 对基准元素右边的子序列进行递归快速排序
    quick_sort(alist, low+1, end)


alist = [54, 226, 93, 17, 77, 31, 44, 55, 20]
quick_sort(alist, 0, len(alist)-1)
print(alist)

Java 版：

import java.util.Arrays;

public class Demo {

    public static void main(String[] args) {
        int[] arr = new int[]{21,13,4,16,7,39,4,10};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));  // [4, 4, 7, 10, 13, 16, 21, 39]
    }

    // 快排
    public static void quickSort(int[] arr, int start, int end) {
        if (start>=end) {
            return;
        }
        int standard = arr[start];
        int left = start;
        int right = end;
        while (left<right) {
            while (left < right && arr[right] >= standard) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] < standard) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = standard;
        quickSort(arr, start, left-1);
        quickSort(arr, left+1, end);
    }
}

时间复杂度 O(nlogn) 分析：

• 在最好的情况下，每次运算一次分区，我们会把一个数列分为两个几近相等的片段。这个意思就是每次递归调用处理一半大小的数列。因此，在到达大小为一的数列前，我们只要作 logn 次嵌套的调用，这个意思就是调用树的深度是 O(logn)。
• 同时，在同一层次结构的左右两个递归调用中，不会处理到原来数列的相同部分。因此，程序调用的每一层次结构总共全部仅需要 O(n) 的时间（每次调用会有某些共同的额外耗费，但是因为在每一层次结构仅仅只有 O(n) 个调用，这些被归纳在 O(n) 系数中）。

7、归并排序

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。

将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

1. 时间复杂度

• 最优时间复杂度：O(nlogn)
• 最坏时间复杂度：O(nlogn)
• 稳定性：稳定

2. 归并排序的分析

3.  代码实现

版本一：

def merge_sort(alist):
    """归并排序"""
    n = len(alist)
    if n <= 1:
        return alist
    mid = n // 2
    # left 采用归并排序后形成的有序的新的列表
    left_li = merge_sort(alist[:mid])
    # right 采用归并排序后形成的有序的新的列表
    right_li = merge_sort(alist[mid:])

    # 将两个有序的子序列合并为一个新的整体
    # merge(left, right)
    left_pointer, right_pointer = 0, 0
    result = []

    while left_pointer < len(left_li) and right_pointer < len(right_li):
        if left_li[left_pointer] <=  right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1

    result += left_li[left_pointer:]
    result += right_li[right_pointer:]
    return result


if __name__ == "__main__":
    li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(li)
    sorted_li = merge_sort(li)
    print(li)
    print(sorted_li)

版本二：

import random
import timeit

def random_list(n):
    return [random.randint(0, 100) for i in range(n)]

def merge_sort(i_list):
    if len(i_list) <= 1:
        return i_list
    mid = len(i_list) // 2
    left, right = i_list[:mid], i_list[mid:]
    # 将左右子数列再拆分成左右子子子……数列
    return merge_list(merge_sort(left), merge_sort(right))

# 将左右两个有序数列进行合并
def merge_list(left, right):
    result_list = []
    while left and right:
        if left[0] >= right[0]:
            result_list.append(right.pop(0))
        else:
            result_list.append(left.pop(0))
    result_list.extend(left)
    result_list.extend(right)
    return result_list

if __name__ == "__main__":
    i_list = random_list(20)
    print(i_list)
    print(merge_sort(i_list))
    print(timeit.timeit("merge_sort(i_list)", "from __main__ import merge_sort, i_list", number=100))

七、查找算法

1、查找算法简介

查找算法也叫搜索算法，常用于判断某个数是否在数列中，或者某个数在数列中的位置。影响查找时间长短的主要因素有算法、数据存储的方式及结构。

查找和排序算法一样，如果是以查找过程中被查找的表格或数据是否变动来分类，则可以分为静态查找（Static Search）和动态查找（Dynamic Search）。

• 静态查找是指数据在查找过程中，该查找数据不会有添加、删除或更新等操作，例如符号表查找就属于一种静态查找。
• 动态查找则是指所查找的数据，在查找过程中会经常性地添加、删除或更新。例如在网络上查找数据就是一种动态查找。

查找的几种常见方法：顺序查找、二分法查找、二叉树查找、哈希查找等。

2、顺序查找

顺序查找是最简单、最直接的查找算法。顾名思义，顺序查找就是将数列从头到尾按照顺序查找一遍，是适用于小数据量的查找方法。

此方法优点是数据在查找前不需要进行任何的处理与排序；缺点是查找速度较慢。

时间复杂度：

• 最优时间复杂度：O(1)
• 最坏时间复杂度：O(n)

# 顺序查找
def sequential_search(i_list, target):
    for i in range(len(i_list)):
        if i_list[i] == target:
            return i
    return -1

if __name__ == "__main__":
    li = [1, 22, 44, 55, 66]
    print(sequential_search(li, 0))  # -1
    print(sequential_search(li, 1))  # 0
    print(sequential_search(li, 66))  # 4
    print(sequential_search(li, 67))  # -1

3、二分查找法

二分查找又称折半查找，实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素。

• 其优点是比较次数少，查找速度快，平均性能好；
• 其缺点是要求待查表为有序表，且插入删除困难。

因此，二分查找方法适用于不经常变动而查找频繁的有序列表。

算法步骤：

1. 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功。
2. 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
3. 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

1. 时间复杂度

• 最优时间复杂度：O(1)
• 最坏时间复杂度：O(logn)

2. 图解二分查找过程

3.代码实现

返回值：如果查找成功返回目标的索引值；否则返回 -1。

方式一：递归实现

def binary_search(li, start_index, end_index, element):
    if end_index >= start_index:
        mid_index = (start_index + end_index) // 2
        if element == li[mid_index]:
            return mid_index
        elif element > li[mid_index]:
            return binary_search(li, mid_index+1, end_index, element)
        else:
            return binary_search(li, start_index, mid_index-1, element)
    # 未找到该元素
    return -1


if __name__ == "__main__":
    li = list(range(100))
    print(binary_search(li, 0, len(li)-1, 0))  # 0
    print(binary_search(li, 0, len(li)-1, 99))  # 99
    print(binary_search(li, 0, len(li)-1, 100))  # -1

方式二：非递归实现

# 非递归实现
def binary_search(li, element):
    start_index = 0
    end_index = len(li) - 1
    while end_index >= start_index:
        mid_index = (start_index + end_index) // 2
        if element == li[mid_index]:
            return mid_index
        elif element > li[mid_index]:
            start_index = mid_index + 1
        else:
            end_index = mid_index - 1
    return -1


if __name__ == "__main__":
    li = list(range(100))
    print(binary_search(li, 0))  # 0
    print(binary_search(li, 99))  # 99
    print(binary_search(li, 100))  # -1

4、斐波那契查找

斐波那契数列（Fibonacci）又称黄金分割数列，指的是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, ......。

在数学上，斐波那契被递归方法如下定义：F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2）。该数列越往后，相邻的两个数的比值越趋向于黄金比例值（0.618）。斐波那契查找就是在二分法查找的基础上根据斐波那契数列进行分割的。

斐波那契查找作为二分法查找的变种，与二分法的效率不相上下。根据数据在数列中的分布状态，二分法和斐波那契法很难说哪个更快一点（比如被查找数正好在数列靠前位置，斐波那契查找效率还不如二分法查找）。

1. 原理

斐波那契查找与二分法查找几乎一样，只是在选取比较点（参照点）的位置有所区别。二分法选的是将数列中间的那个元素作为比较点（参照点），而斐波那契查找则选取了数列中间略为靠后的位置作为比较点，也就是黄金分割点。

既然叫做斐波那契查找，首先得列出一个斐波那契数列，如 [1, 2, 3, 5, 8, 13, 21] 这个斐波那契数列只是提供了被查找数列中参照点的位置，基本上就是下标。

以 i_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 为例，共有 len(i_list)=10 个元素。选择一个比 len(i_list) 稍大的斐波那契数，也就是 13（因为斐波那契数列中没有10），比 13 小一号的斐波那契数是 8，那么首次选取的参照点就是 i_list[8]。如果被查找数比 i_list[8] 小，就看一下比 8 小一号的斐波那契数 5，第二次选取的参照点就是 i_list[5]。以此类推，就是把斐波那契数当做被查找数列的位置参数来使用。

2. 代码实现

# 斐波那契数列
def fibonacci(n):
    f_list = [1, 1]
    while n > 1:
        f_list.append(f_list[-1] + f_list[-2])
        n -= 1
    return f_list[-1]

## 斐波那契查找
def fibonacci_search(i_list, target):

    i_len = len(i_list)
    start_index = 0
    end_index = i_len - 1

    k = 1
    # 斐波那契数列中的最后一个元素要比i_list长度稍微大一点
    while fibonacci(k) < i_len :
        k += 1

    while start_index < end_index:
        # 参照点的位置
        mid_index = start_index + fibonacci(k-1)
        if target == li[mid_index]:
            return mid_index
        elif target > li[mid_index]:
            start_index = mid_index + 1
            k -= 2
        else:
            end_index = mid_index - 1
            k -= 1
    # 当剩余相邻的两个元素比较时
    if target == li[start_index]:
        return start_index
    elif target == li[end_index]:
        return end_index
    else:
        return -1

if __name__ == "__main__":
    li = [4, 12, 24, 45, 56, 63, 78]
    print(fibonacci_search(li, 1))  # -1
    print(fibonacci_search(li, 4))  # 0
    print(fibonacci_search(li, 78))  # 6

5、插值查找

在被查找数列中选取比较点（参照点）时，二分法采用的是中点，斐波那契法采用的是黄金分割点。二分查找法是最直观的，斐波那契查找法可能是最“美观”的，但都不是最科学的。

那么，如何选取最科学的那个比较点（参照点）呢？通常情况下被查找数列都不是等差的，也不知道数列的差值分布状态，没法确定到底选择哪个点是“最优解”。插值算法则给出了一个在大多数情况下的理论上最科学的比较点（参照点）。

插值查找法也是二分查找法的进阶算法，虽然当数列中的元素分布得比较广的情况下插值查找的效果并不太好。

1. 原理

以英文词典为例，如果是要找以“a”开头的单词，一般都不会从中间位置开始翻（二分查找法），也不会从黄金分割点（页数*0.618）的位置开始找（斐波那契查找法），直觉上就应该从字典的前面开始查找。但数学没有直觉，它会告诉我们最佳取值点 mid_index = left_index + (target - i_list[left_index]) * (right_index-left_index) // (i_list[right_index]-i_list[left_index])，不管是找哪个字母开头的单词，还是在任意数列中寻找任意数，这个点在大多数情况下就是最优的比较点（至于为什么这个点是最优的比较点，请自行查找答案）。

对于等差数列，插值查找可能是最快的算法；而对于等比数列，效率远不如二分查找和斐波那契查找。

2. 代码实现

def insert_search(i_list, target):

    i_len = len(i_list)
    left = 0
    right = i_len - 1

    while right - left > 1:
        mid = left + (target - i_list[left]) * (right-left) // (i_list[right]-i_list[left])
        if mid == left:
            # 当i_list[right]和i_list[left]相差太大时，有可能导致mid一直都等于left，从而陷入死循环
            mid += 1
        if target < i_list[mid]:
            right = mid
        elif target > i_list[mid]:
            left = mid
        else:
            return mid
    if target == i_list[left]:
        return left
    elif target == i_list[right]:
        return right
    else:
        return -1

6、分块查找

分块查找合以上几种查找方式有所不同：顺序查找的数列是可以无序的，二分法查找和斐波那契查找的数列的数列必须是有序的。分块查找介于两者之间，需要块有序，元素可以无序。

分块查找可以看成是顺序查找的进阶算法。虽然在分块时会耗费点时间，但是在后期的查找会快很多。一般情况下分块查找比顺序查找要快。

1. 原理

分块查找首先按照一定的取值范围将数列分成数块（至少分成两块，否则就和顺序查找没区别了）。块内的元素是可以无序的，但块必须是有序的，意思是处于后面位置的块中的最小元素都要比前面位置块中的最大元素大。

首先将被查找数与块的分界数相比较（也可以与每个块中最大的元素比较），确定被查找数属于哪个块，然后再在对应块内逐个对比，也就是顺序查找了。

2. 代码实现

# 存储每个块的最大值以及数列中对应元素的个数
index_list = [[25, 0], [50, 0], [75, 0], [100, 0]]
i_list = [1, 3, 66, 12, 99, 43, 54, 78, 33, 41, 98]

# 制造分块数列
def divide_block():
    global index_list, i_list
    # 分块后的list
    sort_list = []
    for key in index_list:
        # 小于key[0]的元素单独成块
        sub_list = [i for i in i_list if i < key[0]]
        key[1] = len(sub_list)
        sort_list += sub_list
        # 过滤掉已经加入到sub_list的元素
        i_list = list(set(i_list)-set(sub_list))
    i_list = sort_list
    # 返回分块情况
    return index_list

# 找到目标值的块并在块中进行顺序查找
def block_search(i_list, target, index_list):
    print("i_list : %s" % i_list)
    print("index_list : %s" % index_list)
    # 起始索引
    left = 0
    # 终止索引
    right = 0
    # 首先找到目标值所在的块
    for index_info in index_list:
        right += index_info[1]
        if target < index_info[0]:
            break
        else:
            left += index_info[1]
    # 在块中顺序查找
    for i in range(left, right):
        if target == i_list[i]:
            return "%s is in the list, index is: %s" % (target, i)
    return "%s is not in the list" % target


if __name__ == "__main__":
    print(i_list)
    divide_block()
    print(block_search(i_list, 3, index_list))
    print(block_search(i_list, 99, index_list))
    print(block_search(i_list, 59, index_list))

八、矩阵及其算法

1、矩阵介绍

矩阵（matrix）是数字或字符的矩形网格（如 excel 表格），并具有加、减、乘等运算规则。

从数学的角度来看，对于 m x n 矩阵的形式，可以用计算机中的二维数组来表示。基本上，许多矩阵的运算与应用都可以使用计算机中的二维数组解决。

我们用 (行数, 列数) 来描述矩阵的维度。

2、矩阵相加

矩阵的相加运算较为简单，前提是相加的两个矩阵对应的行数与列数必须相等，而相加后矩阵的行数与列数也是相同的。

示例代码： 

A = [[1,2,3], [1,2,3], [1,2,3]]
B = [[1,2,3], [1,2,3], [1,2,3]]
N = 3
# 用于存放相加结果的矩阵
C = [[None]*N for i in range(N)]

for i in range(N):
    for j in range(N):
        C[i][j] = A[i][j] + B[i][j]  # 矩阵C = 矩阵A + 矩阵B
print("矩阵A和矩阵B的相加结果：")
for i in range(N):
    for j in range(N):
        print(C[i][j], end="\t")
    print()

执行结果：

矩阵A和矩阵B的相加结果：
2       4       6
2       4       6
2       4       6

3、矩阵相乘

并不是所有的矩阵都能进行乘法运算的。 并且，对输出矩阵的维度也存在要求。

矩阵一的列数必须等于矩阵二的行数，如 M×N 矩阵和 N×K 矩阵相乘的结果是 M×K 矩阵（新矩阵取矩阵一的行和矩阵二的列）。

矩阵乘法依赖于点积与行列元素的各种组合。 以下图为例，矩阵 C 中的每个元素都是矩阵 A 的行与矩阵 B 的列的点积。

操作 a1·b1 表示我们取矩阵 A 中第 1 行 (1,7) 和矩阵 B 中第 1 列 (3,5) 的点积： 

即： 

矩阵的乘法运算非常有用，但背后并没有太深奥的数学规律，之所以数学家发明了这种运算，完全是因为它简化了以前乏味的计算。这是一个人为的产物，但却非常有效。 

# 矩阵相乘函数
def matrix_multiply(matrix1, matrix2):
        # 初始化所需的维度
    m = len(matrix1)  # matrix1的行数
    n = len(matrix1[0])  # matrix1的列数 即matrix2的行数
    p = len(matrix2[0])  # matrix2的列数

    # 初始化结果矩阵 = matrix1的行数 x matrix2的列数
    result_matrix = [[None]*p for i in range(m)]

    for row_no in range(m):
        for col_no in range(p):
            tmp = 0
            for k in range(n):
                tmp = tmp + matrix1[row_no][k] * matrix2[k][col_no]
            result_matrix[row_no][col_no] = tmp
    return result_matrix


A = [[1,2,3], [4,5,6], [7,8,9]]
B = [[1,2], [3,4], [5,6]]

result_matrix = matrix_multiply(A, B)

print("矩阵相乘结果：")
for i in range(len(result_matrix)):
    for j in range(len(result_matrix[0])):
        print(result_matrix[i][j], end="\t")
    print()

执行结果：

矩阵相乘结果：
22      28
49      64
76      100

4、矩阵转置

转置矩阵（A^T）就是把原矩阵的行坐标元素与列坐标元素相互调换。假设 A^T 为 A 的转置矩阵，则有 A^T[j, i] = A[i, j]。

转置矩阵有两个步骤：

1. 矩阵旋转 90°
2. 反转每行元素的顺序（例如 [a b c] 变为 [c b a]）

例如，将矩阵 M 转置为 T：

示例代码：

# 转置矩阵函数
def matrix_t(matrix):
    result_matrix = [[None]*len(matrix) for i in range(len(matrix[0]))]
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            result_matrix[j][i] = matrix[i][j]
    return result_matrix


A = [[1,2], [3,4], [5,6]]

result_matrix = matrix_t(A)
print("矩阵转置结果：")
for i in result_matrix:
    for j in i:
        print(j, end="\t")
    print()

九、哈希算法

1、常见的哈希算法

1. 哈希算法简介

哈希算法又称为散列法，任何通过哈希查找的数据都不需要经过事先的排序，也就是说这种查找可以直接且快速地找到键值（Key，访问数据）所存放的地址。

通常判断一个查找算法的好坏主要由其比较次数及查找所需时间来判断，一般的查找技巧主要是通过各种不同的比较方法来查找所要的数据，反观哈希算法则是直接通过数学函数来获取对应的存放地址，因此可以快速地找到所要的数据。

哈希算法还具有保密性高的特点，因为不事先知道哈希函数就无法查找到数据。信息技术上有许多哈希法的应用，特别是在数据压缩与加解密方面。

常见的哈希算法有除留余数法、平方取中法、折叠法、数字分析法以及链地址法。哈希算法并没有一定的规则可循，可能是其中的某一种方法，也可能同时使用好几种方法。

1）原理

1. 哈希算法使用哈希函数（散列函数）来计算一个键值（访问数据）所对应的地址（哈希值），进而建立哈希表（也叫散列表，是通过键值直接访问数据的一种数据结构）。
2. 之后每次通过键值和哈希函数，就可以直接获得访问数据的地址，实现 O(1) 的数据访问效率。

哈希算法的查找速度与数据多少无关，在没有碰撞和溢出的情况下，一次读取即可完成。

2）设计原则

选择哈希函数时，要特别注意不宜过于复杂，设计原则上至少必须符合计算速度快与碰撞频率尽量低的两个特点。

2. 常见的哈希算法

1）除留余数法

最简单的哈希函数是将数据值（key）除以某一个常数后，取余数来当索引（哈希值）。可以用以下式子来表示：

h(key) = key mod B

一般而言，B（即常数）最好是质数。

例如，在一个有 13 个位置的数组中，只使用到 7 个地址，值分别是 12、65、70、99、33、67、48。我们可以把数据内的值除以 13，并以其余数来当数组的下标（作为索引）。在这个例子中，我们所使用的 B 即为 13，则 h(12) = 12、h(65) = 0、...，其所建立出来的哈希表为：

2）平方取中法

平方取中法和除留余数法相当类似，就是先计算数据的平方，之后再取中间的某段数字作为索引。

如下例所示，我们用平方取中法，并将数据存放在 100 个地址空间中，其操作步骤如下：

将 12、65、70、99、33、67、51 平方后如下：

144、4225、4900、9801、1089、4489、2601

再取百位数和十位数作为索引，分别为：

14、22、90、80、08、48、60

上述这7个数字的数列就对应于原先的 7 个数 12、65、70、99、33、67、51 存放在 100 个地址空间的索引值，即：

f(14) = 12
f(22) = 65
f(90) = 70
f(80) = 99
f(08) = 33
f(40) = 67
f(60) = 51

若实际空间介于 0~9（10 个空间），但取百位数和十位数的值介于 0~99（共 100 个空间），则必须将平方取中法第一次所求得的索引值再压缩 1/10 才可以将 100 个可能产生的索引值对应到 10 个空间，即将每一个索引值除以 10 取整数（下例我们以 DIV 运算符作为取整数的除法），我们可以得到下列的对应关系：

f(14 DIV 10) = 12         f(1) = 12
f(22 DIV 10) = 65         f(2) = 65
f(90 DIV 10) = 70         f(9) = 70
f(80 DIV 10) = 99   ——>   f(8) = 99
f(08 DIV 10) = 33         f(0) = 33
f(40 DIV 10) = 67         f(4) = 67
f(60 DIV 10) = 51         f(6) = 51

3）折叠法

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

例如，有一个数据，转换成数字后为 2365479125443，若以每 4 个数为一个部分则可拆为 2365、4791、2544、3。将这 4 组数字加起来后（9703）即为索引值。

在折叠法中有两种做法，如上例直接将每一部分相加所得的值作为其 Bucket Address，被称为“移动折叠法”。

哈希算法的设计原则之一就是降低碰撞，如果希望降低碰撞的机会，就可以将上述每一部分数字中的奇数或偶数翻转，再相加取得其 Bucket Address，这种改进做法被称为“边界折叠法”（folding at the boundaries）。

• 情况一：将偶数反转

　　　2365(第一组数据为奇数，故不反转) + 4791(奇数) + 4452(偶数，故反转) + 3(奇数) = 11611（Bucket Address）

• 情况二：将奇数反转

　　　5631(第一组数据为奇数，故反转) + 1974(奇数) + 2544(偶数，故不反转) + 3(奇数) = 10153（Bucket Address）

4）数字分析法

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

例如，下面这个电话号码表时相当有规则性的，除了区号全部是 080 外，中间三个数字的变化也不大：

080-772-2234
080-772-4525
080-774-2604
080-772-4651
080-774-2285
080-772-2101
080-774-2699
080-772-2694

假设地址空间的大小为 999，那么我们必须从下列数字提取适当的数字，即数字不要太集中，分布范围较为平均（或称随机度高），最后决定提取最后三个数字作为键值，故可得哈希表：

2、碰撞与溢出问题的处理

在哈希法中，当标识符要放入某个桶（Bucket，哈希表中存储数据的位置）时，若该桶已经满了，就会发生溢出（Overflow）；另一方面哈希法的理想情况是所有数据经过哈希函数运算后都得到不同的值，但现实情况是即使所有关键字段的值都不相同，还是可能得到相同的地址，于是就发生了碰撞（Collsion）问题。因此，如何在碰撞发生后处理溢出的问题就显得相当重要。

常见的处理算法有线性探测法、平方探测法、再哈希法、链地址法等。

1. 线性探测法

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

线性探测法通常把哈希的位置视为环形结构，如此一来若后面的位置已被填满而前面还有位置时，可以将数据放到前面。

Python 线性探测算法：

def create_table(num, index):
    """
    :param num: 需要存放的数据
    :param index: 哈希表
    :return: None
    """
    # 哈希函数：数据 % 哈希表最大元素（索引）
    tmp = num % INDEXBOX
    while True:
        # 如果数据对应的位置是空的，则直接存入数据
        if index[tmp] == -1:
            index[tmp] = num
            break
        # 否则往后找位置存放
        else:
            # 递增取余是为了将哈希表视为环形结构，后面的位置都被填满时再从头位置往后遍历
            tmp = (tmp+1) % INDEXBOX

以除留余数法的哈希函数取得索引值，再以线性探测法来存储数据。

import random


INDEXBOX = 10  # 哈希表最大元素（索引）
MAXNUM = 7  # 最大数据个数


# 线性探测算法
def create_table(num, index):
    """
    :param num: 需要存放的数据
    :param index: 哈希表
    :return: None
    """
    # 哈希函数：数据 % 哈希表最大元素
    tmp = num % INDEXBOX
    while True:
        # 如果数据对应的位置是空的，则直接存入数据
        if index[tmp] == -1:
            index[tmp] = num
            break
        # 否则往后找位置存放
        else:
            # % 递增取余是为了将哈希表视为环形结构，后面的位置都被填满时再从头位置往后遍历
            tmp = (tmp+1) % INDEXBOX


# 主程序
index = [-1] * INDEXBOX  # 初始化哈希表
data = [random.randint(1, 20) for num in range(MAXNUM)]  # 原始数组值
print("  原始数组值：\n%s" % data)

# 使用哈希算法存入数据
print("哈希表内容：")
for i in range(MAXNUM):
    create_table(data[i], index)
    print("  %d => %s" % (data[i], index))

print("  完成哈希表：\n%s" % index)

执行结果：

原始数组值：
  [13, 17, 19, 10, 14, 20, 18]
哈希表内容：
  13 => [-1, -1, -1, 13, -1, -1, -1, -1, -1, -1]
  17 => [-1, -1, -1, 13, -1, -1, -1, 17, -1, -1]
  19 => [-1, -1, -1, 13, -1, -1, -1, 17, -1, 19]
  10 => [10, -1, -1, 13, -1, -1, -1, 17, -1, 19]
  14 => [10, -1, -1, 13, 14, -1, -1, 17, -1, 19]
  20 => [10, 20, -1, 13, 14, -1, -1, 17, -1, 19]
  18 => [10, 20, -1, 13, 14, -1, -1, 17, 18, 19]
完成哈希表：
  [10, 20, -1, 13, 14, -1, -1, 17, 18, 19]

2. 平方探测法

线性探测法有一个缺点，就是相类似的键值经常会聚集在一起，因此可以考虑以平方探测法来加以改进。

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

例如数据值 key，哈希函数 h，其查找算法如下：

第一次查找：h(key)
第二次查找：(h(key)+1^2) % B
第三次查找：(h(key)-1^2) % B
第四次查找：(h(key)+2^2) % B
第五次查找：(h(key)-2^2) % B
...
...
第 n 次查找：(h(key)±((B-1)/2)^2) % B，其中，B 必须为 4j + 3 型的质数，且 1 ≤ i ≤ (B-1)/2

3. 再哈希法

再哈希法就是一开始就先设置一系列的哈希函数，如果使用第一种哈希函数出现溢出时就改用第二种，如果第二种也出现溢出则改用第三种，一直到没有发生溢出为止。例如，h1 为 key%11、h2 为 key*key、h3 为 key*key%11、h4....。

示例：使用再哈希法处理下列数据碰撞的问题。

681、467、633、511、100、164、472、438、445、366、118

其中哈希函数为（此处的 m=13）：

h1(key) = key MOD m
h2(key) = (key+2) MOD m
h3(key) = (key+4) MOD m

使用第一种哈希函数 f(key) = key MOD 13，所得的哈希地址如下：

681 -> 5
467 -> 12
633 -> 9
511 -> 4
100 -> 9
164 -> 8
472 -> 4
438 -> 9
445 -> 3
366 -> 2
118 -> 1

其中 100、472、438 都发生碰撞，再使用第二种哈希函数 h2(key) = (key+2) MOD 13，进行数据的地址安排：

100 -> h2(100+2) = 102 mod 13 = 11
472 -> h2(472+2) = 474 mod 13 = 6
438 -> h2(438+2) = 440 mod 13 = 11

438 仍发生碰撞问题，故接着使用第三种哈希函数 h3(key+4) = (key+4) MOD 13，重新进行438 的地址安排：

438 -> h3(438+4) = 442 mod 13 = 0

经过三次再哈希后，数据的地址安排如下：

4. 链地址法

链地址法是目前比较常用的冲突解决方法，一般可以通过数组和链表的结合达到冲突数据缓存的目的。 

左侧数组的每个成员包括一个指针，指向一个链表的头。每发生一个冲突的数据，就将该数据作为链表的节点链接到链表尾部。这样一来，就可以保证冲突的数据能够区分并顺利访问。

考虑到链表过长造成的问题，还可以使用红黑树替换链表进行冲突数据的处理操作，来提高散列表的查询稳定性。 

3、哈希表的动态扩容

1. 重哈希和装载因子

• 装载因子：即关键字个数和哈希表长度之比，用于度量所有关键字填充后哈希表的饱和度。
• 哈希表的装载因子 = 填入表中的元素个数 / 哈希表的长度。
• 重哈希：当装载因子达到指定的阈值时，哈希表进行扩容的过程。

2. 动态扩容过程 

总结：

• 每次插入时迁移一个数据，这样不像集中一次性迁移数据那样耗时，不会形成明显的阻塞。
• 由于迁移过程中，有新旧两个哈希表，查找数据时，先在新的哈希表中进行查找，如果没有，再去旧的哈希表中进行查找。

十、树形结构与算法

1、树的概念

树（Tree）是由多个节点（Node）的集合组成，每个节点又有多个与其关联的子节点（Child Node）。子节点就是直接处于节点之下的节点，而父节点（Parent Node）则位于节点直接关联的上方。树的根（Root）指的是一个没有父节点的单独的节点。

所有的树都呈现了一些共有的性质：

1. 只有一个根节点；
2. 除了根节点，所有节点都有且仅有一个父节点；
3. 无环。将任意一个节点作为起始节点，都不存在任何回到该起始节点的路径（正是前两个性质保证了无环的成立）。

树形结构是一种日常生活应用相当广泛的非线性结构。树状算法在程序中的建立与应用大多使用链表来处理，因为链表的指针用来处理树相当方便，只需改变指针即可。当然，也可以使用数组这样的连续内存来表示二叉树，两者各有利弊。

图示：

树的术语：

• 根（Root）：树中最顶端的节点，根没有父节点。
• 子节点（Child）：节点所拥有子树的根节点称为该节点的子节点。
• 父节点（Parent）：如果节点拥有子节点，则该节点为子节点的父节点。
• 兄弟节点（Sibling）：与节点拥有相同父节点的节点。
• 后代节点（Descendant）：节点向下路径上可达的节点。
• 叶节点（Leaf）：没有子节点的节点。
• 内节点（Internal Node）：至少有一个子节点的节点。
• 度（Degree）：节点拥有子树的数量。
• 边（Edge）：两个节点中间的链接。
• 路径（Path）：从节点到子孙节点过程中的边和节点所组成的序列。
• 层级（Level）：根为 Level 0 层，根的子节点为 Level 1 层，以此类推。
• 高度（Height）/ 深度（Depth）：树中层的数量。比如只有 Level 0、Level 1、Level 2，则高度为 3。

树的种类：

• 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树。
• 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树。

• 二叉树：每个节点最多含有两个子树的树称为二叉树。
• 霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树。
• B 树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。

树的存储与表示：

由于对节点的个数无法掌握，常见树的存储表示都转换成二叉树进行处理，即子节点个数最多为 2。

• 顺序存储：将数据结构存储在固定的数组中，虽然在遍历速度上有一定的优势，但因需要事先声明的所占空间大，是非主流二叉树。
• 链式存储：使用链表来表示二叉树的好处是对于节点的增加与删除相当容易；缺点是很难找到父节点，除非在每一节点多增加一个父字段。

1）顺序存储

2）链式存储 

常见的一些树的应用场景：

1. xml，html 等，那么编写这些东西的解析器的时候，不可避免用到树。
2. 路由协议就是使用了树的算法。
3. Mysql 数据库索引。
4. 文件系统的目录结构。
5. 很多经典的 AI 算法其实都是树搜索，如机器学习中的决策树（decision tree）就是树结构。

2、二叉树与基本实现

1. 二叉树的基本概念

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

2. 二叉树的性质（特性）

• 性质1：在二叉树的第 i 层上至多有 2i-1 个节点（i>0）
• 性质2：深度为 k 的二叉树至多有 2k-1 个节点（k>0）
• 性质3：对于任意一棵二叉树，如果其叶节点数为 N0，而度数为 2 的节点总数为 N2，则 N0 = N2+1
• 性质4：具有 n 个节点的完全二叉树的深度必为 log2(n+1)
• 性质5：对完全二叉树，若从上至下、从左至右编号，则编号为 i 的节点，其左子节点编号必为 2i，其右子节点编号必为 2i＋1；其父节点的编号必为 i/2（i=1 时为根，除外）

3. 完全二叉树和满二叉树

• 完全二叉树：除了最后一层，其它层的节点数都达到了最大值，且叶节点从左往右紧密排列。
• 满二叉树：除了最后一层，其它层的节点都有两个子节点。

4. 代码实现：用队列实现普通二叉树

class Node:
    """树的节点类"""
    def __init__(self, item):
        self.item = item
        self.lchild = None
        self.rchild = None


class BinaryTree:
    """二叉树类"""

    def __init__(self, root=None):
        """初始化根节点"""
        self.root = root

    def add(self, item):
        """为树添加节点"""
        node = Node(item)
        # 如果树是空的，则为根节点赋值
        if self.root is None:
            self.root = node
        else:
            queue = []
            queue.append(self.root)
            # 对已有节点进行层次遍历
            while queue:
                # 弹出队列的第一个元素（先进先出）
                cur_node = queue.pop(0)
                if cur_node.lchild is None:
                    cur_node.lchild = node
                    return
                elif cur_node.rchild is None:
                    cur_node.rchild = node
                    return
                # 如果左右子树都不为空，加入队列继续判断
                else:
                    queue.append(cur_node.lchild)
                    queue.append(cur_node.rchild)

3、二叉查找树

1. 普通二叉树的问题

如果要访问二叉树中的某一个节点，通常需要逐个遍历二叉树中的节点来定位，它不像数组那样能对指定的元素进行直接的访问。

所以普通二叉树的查找效率是线性的 O(n)，在最坏的情况下需要查找树中所有的节点。也就是说，随着二叉树节点数量增加时，查找任一节点的步骤数量也将相应地增加。

那么，如果一个二叉树的查找时间是线性的，那相比数组来说到底哪里有优势呢？毕竟数组的查找时间是常量 O(1)。的确是这样，通常来说普通的二叉树确实不能提供比数组更好的查找性能。然而，如果我们按照一定的规则来组织排列二叉树中的元素时，就可以很大程度地改善查找效率。

2. 二叉查找树的定义

二叉查找树（BST：Binary Search Tree）是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。它不仅支持快速查找一个数据，还支持快速插入、删除一个数据。它是怎么做到这些的呢？

这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其值要大于其左子树中每个节点的值，且要小于其右子树所有节点的值。

二叉查找树有以下性质：

• 可以是空集合，若不是空集合，则节点上一定要有数据值；
• 每一个节点的值需大于其左子树（left subtree）下的所有节点的值；
• 每一个节点的值需小于其右子树（left subtree）下的所有节点的值；
• 树的每个节点值都不相同。

二叉查找树改善了二叉树节点查找的效率，是一种很好的排序应用模式，因为在建立二叉树的同时，数据就经过初步的比较判断，并按照二叉树的建立规则来存放数据，非常高效。因此，二叉查找树也叫作二叉排序树。

• 数组的搜索比较方便，可以直接用下标，但删除或者插入某些元素就比较麻烦；链表与之相反，删除和插入元素很快，但查找很慢。  
• 相对数组和链表而言，二叉排序树是一种比较有用的折衷方案，既有链表的好处，也有数组的好处，在处理大批量的动态的数据时较为有效。

3. 二叉查找树的时间复杂度分析

不管操作是插入、删除还是查找，二叉查找树的时间复杂度其实都跟树的高度成正比，也就是 O(height)。

• 所以对于一棵完全二叉查找树，它的时间复杂度为 O(logn)。
• 如果退化成下图左边这种类型，它的时间复杂度为 O(n)。

1）创建二叉查找树

例 1：用数组实现二叉查找树。

使用有序的一维数组来表示二叉树，首先可将此二叉树假想成一棵满二叉树，而且第 k 层具有 2k-1 个节点，按序存放在一维数组中。

首先来看看使用一维数组建立二叉查找树的表示方法以及数组索引值的设置：

（PS：索引从 1 开始是为了计算更方便）

由此可以看出此一维数组中的索引值有以下关系：

• 左子节点的索引值是父节点索引值乘 2。
• 右子节点的索引值是父节点索引值乘 2 加 1。

代码实现：

# 把数组的数据值放入二叉查找树数组
def bstree(bts_list, data):
    for i in range(1, len(data)):
        # 根节点索引值设置为1而不是0，是为了能够直接计算子节点的索引值
        index = 1
        # 默认空节点的数据值为0
        # 从根节点开始遍历，直到找到空节点把数据放入
        while bts_list[index] != 0:
            # 如果数据值大于当前节点值，则往右子树比较
            if data[i] > bts_list[index]:
                index = index * 2 + 1
            # 如果数据值小于当前节点值，则往左子树比较
            else:
                index *= 2
        # 找到空节点，放入数据值
        bts_list[index] = data[i]


# 原始数据（第一个元素为无效数据，有效数据实际从索引值1开始）
data = [0, 6, 3, 5, 4, 7, 8, 9, 2]
# 初始化二叉树数组
bts_list = [0] * 16

print("原始数组内容：\n%s" % data)
bstree(bts_list, data)
print("二叉树数组内容：\n%s" % bts_list[1:])

执行结果：

原始数组内容：
[0, 6, 3, 5, 4, 7, 8, 9, 2]
二叉树数组内容：
[6, 3, 7, 2, 5, 0, 8, 0, 0, 4, 0, 0, 0, 0, 9]

 例 2：用链表实现二叉查找树。

class Node:
    """树的节点类"""
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


class BSTree:
    """二叉查找树类"""

    def __init__(self, root=None):
        """初始化根节点"""
        self.root = root

    def add(self, data):
        """添加节点数据"""
        if self.root is None:
            self.root = Node(data)
            return
        cur_node = self.root
        while cur_node is not None:
            # backup 作用：记录 cur_node 的父节点
            backup = cur_node
            # 若新加的值小于当前节点的值，则往左子树遍历
            if cur_node.data > data:
                cur_node = cur_node.left
            # 若新加的值大于当前节点的值，则往右子树遍历
            else:
                cur_node = cur_node.right
        # 当cur_node为空节点时，将新加的值与父节点backup的值比较
        if  backup.data > data:
            backup.left = Node(data)
        else:
            backup.right = Node(data)

    def travel_data(self):
        """打印节点值"""
        print("根节点值：")
        print(self.root.data)
        print("各左节点值：")
        left_node = self.root.left
        while left_node is not None:
            print(left_node.data)
            left_node = left_node.left
        print("各右节点值：")
        right_node = self.root.right
        while right_node is not None:
            print(right_node.data)
            right_node = right_node.right


# 初始化原始数据
data = [5, 6, 24, 8, 12, 3, 17, 1, 9]
bst = BSTree()
for i in data:
    bst.add(i)
bst.travel_data()

执行结果：

根节点值：
5
各左节点值：
3
1
各右节点值：
6
24

2）查找节点

二叉查找树在建立的过程中，是根据左子树 < 树根 < 右子树的原则建立的，因此只需从树根出发比较节点值，如果比树根大就往右，否则往左而下，直到相等就找到了要查找的值，如果比到 None，无法再前进就代表查找不到此值。

通过 BST 查找节点，理想情况下我们需要检查的节点数可以减半。如下图中的 BST 树，包含了 15 个节点。从根节点开始执行查找算法，第一次比较决定我们是移向左子树还是右子树。对于任意一种情况，一旦执行这一步，我们需要访问的节点数就减少了一半，从 15 降到了 7。同样，下一步访问的节点也减少了一半，从 7 降到了 3，以此类推。

根据这一特点，查找算法的时间复杂度应该是 O(logn)。

实际上，对于 BST 查找算法来说，其十分依赖于树中节点的拓扑结构，也就是节点间的布局关系。下图描绘了一个节点插入顺序为 20, 50, 90, 150, 175, 200 的 BST 树。这些节点是按照递升顺序被插入的，结果就是这棵树没有广度（Breadth）可言。也就是说，它的拓扑结构其实就是将节点排布在一条线上，而不是以扇形结构散开，所以查找时间也为 O(n)。

当 BST 树中的节点以扇形结构散开时，对它的插入、删除和查找操作最优的情况下可以达到线性的运行时间 O(logn)。因为当在 BST 中查找一个节点时，每一步比较操作后都会将节点的数量减少一半。尽管如此，如果拓扑结构像上图中的样子时，运行时间就会退减到线性时间 O(n)。因为每一步比较操作后还是需要逐个比较其余的节点。也就是说，在这种情况下，在 BST 中查找节点与在链表中查找就基本类似了。

因此，BST 算法查找时间依赖于树的拓扑结构。最佳情况是 O(log­n)，最坏情况是 O(n)。

代码实现：

建立一个二叉查找树，并输入要查找的值。如果找到该值，则显示查找的次数。

class Node:
    """树的节点类"""
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


class BSTree:
    """二叉查找树"""

    def __init__(self, root=None):
        """初始化根节点"""
        self.root = root

    def add(self, data):
        """添加节点数据"""
        if self.root is None:
            self.root = Node(data)
            return
        cur_node = self.root
        while cur_node is not None:
            # backup 作用：记录 cur_node 的父节点
            backup = cur_node
            # 若新加的值小于当前节点的值，则往左子树遍历
            if cur_node.data > data:
                cur_node = cur_node.left
            # 若新加的值大于当前节点的值，则往右子树遍历
            else:
                cur_node = cur_node.right
        # 当cur_node为空节点时，将新加的值与父节点backup的值比较
        if  backup.data > data:
            backup.left = Node(data)
        else:
            backup.right = Node(data)

    def search(self, data):
        """查找节点"""
        # 记录遍历节点的次数
        search_time = 1
        cur_node = self.root
        while True:
            if cur_node is None:
                return None
            if cur_node.data == data:
                print("共查找了【%d】次" % search_time)
                return cur_node.data
            elif cur_node.data > data:
                cur_node = cur_node.left
            else:
                cur_node = cur_node.right
            search_time += 1


# 初始化原始数据
data = [7, 1, 4, 2, 8, 13, 12, 11, 15, 9, 5]
print("原始数据：%s" % data)
bst = BSTree()
for i in data:
    bst.add(i)
search_data = bst.search(8)
if search_data:
    print("您要找的值【%d】找到了" % search_data)

执行结果：

原始数据：
[7, 1, 4, 2, 8, 13, 12, 11, 15, 9, 5]
共查找了【2】次
您要找的值【8】找到了

3）插入节点

二叉树节点插入的情况和查找相似，重点是插入后仍要保持二叉查找树的特性。BST 的插入算法的复杂度与查找算法的复杂度是一样的：最佳情况是 O(log­n)，最坏情况是 O(n)，因为它们对节点的查找定位策略是相同的。

代码实现：

如果插入的节点已经在二叉树中，就没有插入的必要了。如果插入的值不在二叉树中，就出现查找失败的情况，表示找到了要插入的位置。

class Node:
    """树的节点类"""
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


class BSTree:
    """二叉查找树"""

    def __init__(self, root=None):
        """初始化根节点"""
        self.root = root

    def add(self, data):
        """添加节点数据"""
        if self.root is None:
            self.root = Node(data)
            return
        cur_node = self.root
        while cur_node is not None:
            # backup 作用：记录 cur_node 的父节点
            backup = cur_node
            # 若新加的值小于当前节点的值，则往左子树遍历
            if cur_node.data > data:
                cur_node = cur_node.left
            # 若新加的值大于当前节点的值，则往右子树遍历
            else:
                cur_node = cur_node.right
        # 当cur_node为空节点时，将新加的值与父节点backup的值比较
        if  backup.data > data:
            backup.left = Node(data)
        else:
            backup.right = Node(data)

    def search(self, data):
        """查找节点"""
        # 记录遍历节点的次数
        search_time = 1
        cur_node = self.root
        while True:
            if cur_node is None:
                return None
            if cur_node.data == data:
                print("共查找了【%d】次" % search_time)
                return cur_node.data
            elif cur_node.data > data:
                cur_node = cur_node.left
            else:
                cur_node = cur_node.right
            search_time += 1

    def inorder(self, node):
        """中序遍历"""
        if node is not None:
            self.inorder(node.left)
            print("%d" % node.data, end=" ")
            self.inorder(node.right)


# 初始化原始数据
data = [7, 1, 4, 2, 8, 13, 12, 11, 15, 9, 5]
print("原始数据：%s" % data)

# 初始化二叉查找树
bst = BSTree()
for i in data:
    bst.add(i)

# 需要添加的数据值
new_data = 21
# 先使用查找算法校验插入的数据是否已存在
search_data = bst.search(new_data)
if search_data:
    print("您要找的值【%d】找到了，无需再插入！" % search_data)
# 若不存在，则进行添加并使用中序遍历打印所有节点值
else:
    bst.add(new_data)
    bst.inorder(bst.root)

执行结果：

原始数据：[7, 1, 4, 2, 8, 13, 12, 11, 15, 9, 5]
1 2 4 5 7 8 9 11 12 13 15 21

4）删除节点

从 BST 中删除节点比插入节点难度更大。因为删除一个非叶子节点，就必须选择其他节点来填补因删除节点所造成的树的断裂。如果不选择节点来填补这个断裂，那么就违背了 BST 的性质要求。

删除节点算法的第一步是定位要被删除的节点，这可以使用前面介绍的查找算法，因此运行时间为 O(log­n)。接着应该选择合适的节点来代替删除节点的位置，它共有三种情况需要考虑：

• 情况 1：如果被删除的节点没有右孩子，那么就选择它的左孩子来代替原来的节点。二叉查找树的性质保证了被删除节点的左子树必然符合二叉查找树的性质，因此左子树的值都小于被删除节点的父节点的值。（如果被删除的节点没有左孩子，同理。）
• 情况 2：如果被删除节点的右孩子没有左孩子，那么这个右孩子被用来替换被删除节点。因为被删除节点的右孩子都大于被删除节点左子树的所有节点，同时也大于被删除节点的父节点。因此，用右孩子来替换被删除节点，符合二叉查找树的性质。
• 情况 3：如果被删除节点的右孩子有左孩子，就需要用被删除节点右孩子的左子树中的最下面的节点来替换它，就是说，我们用被删除节点的右子树中最小值的节点来替换。我们知道，在 BST 中，最小值的节点总是在最左边，最大值的节点总是在最右边。所以替换被删除节点右子树中最小的一个节点，就保证了该节点一定大于被删除节点左子树的所有节点；同时，也保证它替代了被删除节点的位置后，它的右子树的所有节点值都大于它。因此这种选择策略符合二叉查找树的性质。

和查找、插入算法类似，删除算法的运行时间也与 BST 的拓扑结构有关，最佳情况是 O(log­n)，而最坏情况是 O(n)。 

5）重复数据的处理

前面我们讲的二叉查找树的操作，针对的都是不存在键值相同的情况。那如果存储的两个对象键值相同，这种情况该怎么处理呢？有两种解决方法。

1. 第一种方法比较容易：二叉查找树中每一个节点不单只存储一个数据，为此我们通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。
2. 第二种方法比较不好理解，不过更加优雅：每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。 

当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。 

对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。

6）遍历节点

二叉树的遍历（Binary Tree Traversal）是树的一种重要的运算。最简单的说法就是“访问树中所有的节点各一次”，并且在遍历后，将树中的数据转化为线性关系。

二叉树有四种常用的遍历方式：

• 层序遍历：从根节点开始，从上到下、从左到右地依次遍历每个节点（常用队列实现）：

1. 根节点入队列。
2. 根节点出队，同时将根节点的左子树和右子树入队。
3. 结点出队，同时将该节点的左子树和右子树入队。
4. 重复步骤 3 直到队列为空。

• 前序遍历（Perorder traversal）：“中左右”的遍历顺序，也就是先从根节点遍历，再往左方移动，当无法继续时，继续向右方移动，接着再重复此步骤：

1. 遍历（或访问）树根。
2. 遍历左子树。
3. 遍历右子树。

• 中序遍历（Inorder traversal）：“左中右”的遍历顺序，也就是从树的左侧逐步向下方移动，直到无法移动，再访问此节点，并向右移动一节点。如果无法再往右移动时，可以返回父节点，并重复左、中、右的步骤：

1. 遍历左子树。
2. 遍历（或访问）树根。
3. 遍历右子树。

• 后序遍历（Postorder traversal）：“左右中”的遍历顺序，就是先遍历左子树，再遍历右子树，最后遍历（或访问）根根，反复执行此步骤：

1. 遍历左子树。
2. 遍历右子树。
3. 遍历树根。

示例：普通二叉树的遍历。

代码实现：二叉查找树的遍历。

二叉查找树意味着二叉树中的数据是排好序的，顺序为左节点 < 根节点 < 右节点，这表明二叉查找树的中序遍历结果是有序的。

class Node:
    """树的节点类"""
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


class BSTree:
    """二叉查找树"""

    def __init__(self, root=None):
        """初始化根节点"""
        self.root = root

    def add(self, data):
        """添加节点数据"""
        if self.root is None:
            self.root = Node(data)
            return
        cur_node = self.root
        while cur_node is not None:
            # backup 作用：记录 cur_node 的父节点
            backup = cur_node
            # 若新加的值小于当前节点的值，则往左子树遍历
            if cur_node.data > data:
                cur_node = cur_node.left
            # 若新加的值大于当前节点的值，则往右子树遍历
            else:
                cur_node = cur_node.right
        # 当cur_node为空节点时，将新加的值与父节点backup的值比较
        if  backup.data > data:
            backup.left = Node(data)
        else:
            backup.right = Node(data)

    def breadth_order(self):
        """队列实现层序遍历"""
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.data, end=" ")
            if cur_node.left is not None:
                queue.append(cur_node.left)
            if cur_node.right is not None:
                queue.append(cur_node.right)

    def preorder(self, node):
        """递归实现前序遍历"""
        if node is None:
            return
        print(node.data, end=" ")
        self.preorder(node.left)
        self.preorder(node.right)

    def inorder(self, node):
        """递归实现中序遍历"""
        if node is None:
            return
        self.inorder(node.left)
        print(node.data, end=" ")
        self.inorder(node.right)

    def postorder(self, node):
        """递归实现后序遍历"""
        if node is None:
            return
        self.postorder(node.left)
        self.postorder(node.right)
        print(node.data, end=" ")


# 初始化原始数据
data = [7, 1, 4, 2, 8, 13, 12, 11, 15, 9, 5]
print("原始数据：%s" % data)
# 创建二叉查找树
bst = BSTree()
for i in data:
    bst.add(i)

print("层序遍历：", end="")
bst.breadth_order()
print()
print("先序遍历：", end="")
bst.preorder(bst.root)
print()
print("中序遍历：", end="")
bst.inorder(bst.root)
print()
print("后序遍历：", end="")
bst.postorder(bst.root)

运行结果：

原始数据：[7, 1, 4, 2, 8, 13, 12, 11, 15, 9, 5]
层序遍历：7 1 8 4 13 2 5 12 15 11 9
先序遍历：7 1 4 2 5 8 13 12 11 9 15
中序遍历：1 2 4 5 7 8 9 11 12 13 15
后序遍历：2 5 4 1 9 11 12 15 13 8 7

思考：（先中后序）哪两种遍历方式能够唯一的确定一颗树？

• 先序：a b c d e f g h
• 中序：b d c e a f h g
• 后序：d e c b h g f a

答：先序与中序、中序与后续。

4、堆及堆排序

1. 堆简介

堆（Heap）是一种特殊的二叉树——堆积树（Heap Tree）的数组对象。堆的具体实现一般不通过指针域，而是通过构建一个一维数组与二叉树的父子节点进行对应，因此堆总是一个完全二叉树。

对于任意一个父节点的序号 n 来说（这里的 n 从 0 开始算），它的子节点的序号一定是 2n+1 和 2n+2；若 n 从 1 算，则它的子节点的序号是 2n 和 2n+1。因此可以直接用数组来表示一个堆。

堆具有以下性质：

• 堆是一个完全二叉树。
• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
• 若根节点最大，则堆叫做“最大堆”或“大根堆”；若根节点最小，则堆叫做“最小堆”或“小根堆”。

如下图所示，第 1 个和第 2 个是大顶堆，第 3 个是小顶堆，第 4 个不是堆。从图中可以看出来，对于同一组数据，我们可以构建多种不同形态的堆。

2. 堆化

在使用堆排序前，必须先了解如何将二叉树转换成堆积树。往堆中插入或者删除一个元素后，我们需要继续满足堆的两个特性，即需要进行调整，让其重新满足堆的特性，这个过程叫做堆化（heapify）。

堆化实际上有两种，从下往上和从上往下。

1）堆中插入元素

如下图所示，往最大堆中插入一个新元素 22。

我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，我们就互换两个节点。一直重复这个过程，直到父子节点之间满足刚说的那种大小关系，这就是从下往上的堆化方法。

2）删除堆顶元素

假设我们构造的是大顶堆，堆顶元素就是最大的元素。当我们删除堆顶元素之后，就需要把第二大的元素放到堆顶，那第二大元素肯定会出现在左右子节点中。然后我们再迭代地删除第二大节点，以此类推，直到叶子节点被删除。

不过这种方法有点问题，就是最后堆化出来的堆并不满足完全二叉树的特性。

实际上，我们稍微改变一下思路，就可以解决这个问题。我们把最后一个节点放到堆顶，然后利用同样的父子节点对比方法（左子树优先）。对于不满足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。这就是从上往下的堆化方法。 

3. 堆排序

1）建堆

进行排序前，首先要进行建堆，即把数组原地建成一个堆。所谓“原地”就是不借助另一个数组，就在原数组上操作。建堆的过程，有两种思路。

第一种是借助我们前面讲的，在堆中插入一个元素的思路。尽管数组中包含 n 个数据，但是我们可以假设，起初堆中只包含一个数据，就是下标为 1 的数据。然后，我们调用前面讲的插入操作，将下标从 2 到 n 的数据依次插入到堆中。这样我们就将包含 n 个数据的数组，组织成了堆。

第二种实现思路跟第一种截然相反，也是下文图解和代码实现的思路。第一种建堆思路的处理过程是按数组顺序从前往后处理数据，并且每个数据插入堆中时，都是从下往上堆化。而第二种实现思路，是从后往前处理数组数据，且每个数据是从上往下堆化的。

2）堆排序 

建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。

这个过程有点类似上面讲的“删除堆顶元素”的操作，当堆顶元素移除之后，我们把下标为 n 的元素放到堆顶，然后再通过堆化的方法，将剩下的 n-1 个元素重新构建成堆。堆化完成之后，我们再取堆顶的元素，放到下标是 n-1 的位置，一直重复这个过程，直到最后堆中只剩下标为 1 的一个元素，排序工作就完成了。

代码实现堆排序：

# 堆排序
def heap_sort(data):
    # 对原始数据建堆
    for i in range(len(data)//2, 0, -1):
        add_heap(data, i, len(data)-1)  # i表示最后一个带有子节点的节点索引
    print("原始数据建堆结果：%s" % data)

    # 堆排序
    for i in range(len(data)-2, 0, -1):
        # 头尾节点交换：每次将最大值放到数组末尾
        data[1], data[i+1] = data[i+1], data[1]
        # 对剩下的节点进行重新建堆
        add_heap(data, 1, i)  # i表示堆顶节点索引
        print("处理过程为：%s" % data)

# 建堆
def add_heap(data, i, size):
    # data：需要排序的数组
    # i：需要堆化的节点索引位（从上往下堆化）
    # size：需要建堆的数组长度

    # 记录当前树根的值
    tmp = data[i]
    # j 为子节点的索引（左子树优先）
    j = i * 2
    # 遍历比较后代节点
    while j <= size:
        # 除了最后一个节点，前面的节点都要与右边节点进行比较
        if j < size:
            # 比较当前的左右节点，谁大取谁
            if data[j] < data[j+1]:
                j += 1
        # 如果树根值较大，结束比较过程
        if tmp >= data[j]:
            break
        # 若树根较小，则将子节点的值赋给树根，并从当前节点的左子节点开始继续比较
        else:
            data[j//2] = data[j]
            j = 2*j
    # 将临时存储的树根的值赋给最后遍历到的子节点
    data[j//2] = tmp


if __name__ == "__main__":
    data = [0, 5, 6, 4, 8, 3, 2, 7, 1]
    print("原始数组为：%s" % data)
    # 进行堆排序
    heap_sort(data)
    print("排序结果为：%s" % data)

执行结果：

原始数组为：[0, 5, 6, 4, 8, 3, 2, 7, 1]
原始数据建堆结果：[0, 8, 6, 7, 5, 3, 2, 4, 1]
处理过程为：[0, 7, 6, 4, 5, 3, 2, 1, 8]
处理过程为：[0, 6, 5, 4, 1, 3, 2, 7, 8]
处理过程为：[0, 5, 3, 4, 1, 2, 6, 7, 8]
处理过程为：[0, 4, 3, 2, 1, 5, 6, 7, 8]
处理过程为：[0, 3, 1, 2, 4, 5, 6, 7, 8]
处理过程为：[0, 2, 1, 3, 4, 5, 6, 7, 8]
处理过程为：[0, 1, 2, 3, 4, 5, 6, 7, 8]
排序结果为：[0, 1, 2, 3, 4, 5, 6, 7, 8]

4. 堆排序的性能分析

堆排序是选择排序的改进版。

选择排序的原理不难理解，每次从未排序部份找出最小值，插入已排序部份的后端，其时间主要花费于在整个未排序部份寻找最小值。如果能让搜寻最小值的方式加快，那么选择排序的效率也就可以加快。

而堆排序法其实在重建堆的过程中，就是一个选择的行为，（最小堆）每次将最小值选至树根，而选择的路径并不是所有的元素，而是由树根至树叶的路径，因而可以加快选择的过程，所以称之为改良的选择排序法。

• 建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以堆排序整体的时间复杂度是 O(nlogn)。
• 整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。
• 堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。

在实际开发中，为什么快速排序要比堆排序性能好？

• 堆排序数据访问的方式没有快速排序友好。对于快速排序来说，数据是顺序访问的；而对于堆排序来说，数据是跳着访问的。
• 对于同样的数据，在排序过程中，堆排序的数据交换次数要多于快速排序。

5. 堆的应用

1）优先级队列

优先队列的概念和堆的特性十分契合，往优先队列中插入一个元素就相当于往堆中插入一个元素；从优先队列中取出优先级最高的元素，就相当于取出堆顶元素。

问题：

假设我们有 100 个小文件，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。

方案：

整体思路有点像归并排序中的合并函数。我们从这 100 个文件中，各取第一个字符串，放入数组中，然后比较大小，把最小的那个字符串放入合并后的大文件中，并从数组中删除。时间复杂度为 O(100n)。

优化：

1. 每次将从小文件中取出来的字符串放入到大小为 100 的小顶堆中，那堆顶的元素，也就是优先级队列队首的元素，即最小的字符串。
2. 之后将这个字符串放入到大文件中，并将其从堆中删除。
3. 然后再从对应小文件中取出下一个字符串，放入到堆中。
4. 循环这个过程，就可以将 100 个小文件中的数据依次放入到大文件中。时间复杂度为 O(log100n)。

2）高性能定时器

问题：

假设我们有一个定时器，定时器中维护了很多定时任务，每个任务都设定了一个要触发执行的时间点。定时器每过一个很小的单位时间（比如 1 秒），就扫描一遍任务，看是否有任务到达设定的执行时间。如果到达了，就拿出来执行。

但是，这样每过 1 秒就扫描一遍任务列表的做法比较低效，主要原因有两点：第一，任务的约定执行时间离当前时间可能还有很久，这样前面很多次扫描其实都是徒劳的；第二，每次都要扫描整个任务列表，如果任务列表很大的话，势必会比较耗时。

方案：

我们按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（也就是小顶堆的堆顶）存储的是最先执行的任务。这样，定时器就不需要每隔 1 秒就扫描一遍任务列表了，每次拿队首任务的执行时间点，与当前时间点相减，直接得到下一个任务的执行时间间隔。

3）求 Top K

问题：

求 Top K 的问题可以分为两类：

• 一类是针对静态数据集合，也就是说数据集合事先确定，不会再变。
• 另一类是针对动态数据集合，也就是说数据集合事先并不确定，有数据会动态地加入到集合中。

方案：

• 针对静态数据：如何在一个包含 n 个数据的数组中，查找前 K 大数据呢？我们可以维护一个大小为 K 的最小堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。遍历数组需要 O(n) 的时间复杂度，一次堆化操作需要 O(logK) 的时间复杂度，所以最坏情况下，n 个元素都入堆一次，时间复杂度就是 O(nlogK)。
• 针对动态数据：每当有数据要插入时先与堆顶元素比较，若大于堆顶元素则删除堆顶元素并且将这个数据插入堆中；如果小于堆顶元素小则不做处理。这样无论何时需要查询当前 K 大元素，都能立即返回。

4）求动态数据集合中的 n% 分位数

以求 50% 分位数，即中位数为例，假设当前总数据的个数是 n，方案如下：

1. 维护一个大顶堆存储前半部分数据，一个小顶堆存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。
2. 偶数情况下 n/2 个存大顶堆，n/2 存小顶堆；奇数情况下 n/2+1 个存大顶堆，n/2 个存小顶堆。
3. 如果新加入数据小于等于大顶堆堆顶元素，那么将其加入大顶堆；否则加入小顶堆。
4. 数据加入后可能出现两边数据与约定数量不符的情况，此时可以将数据互相移动，将数量满足约定。

若是求 n% 分位数，则在大顶堆中保存 n * 99% 个数据，小顶堆中保存 n * 1% 个数据。

5、平衡二叉树（AVL）

1. 二叉查找树存在的问题

二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，最佳时间复杂度是 O(log­n)。

不过，由于二叉排序树本身为有序，当插入一个有序程度十分高的序列时，生成的二叉排序树会持续在某个方向的字数上插入数据，导致最终的二叉排序树会退化为链表，从而使得二叉树的查询和插入效率恶化。时间复杂度会退化到 O(n)。

因此一般的二叉查找树不适用于数据经常变动（加入或删除）的情况。而是比较适合不会变动的数据，例如编程语言中的“保留字”等。

为了能够尽量降低查找所需要的时间，快速找到所要的键值，或者很快地知道当前的树中没有我们要的键值，必须让树的高度越小越好。要解决这个时间复杂度退化的问题，我们需要设计一种平衡二叉查找树。

2. 平衡二叉树的概念

平衡二叉树（Balanced Binary Tree）又称 AVL 树（由 Adelse-Velskil 和 Landis 两个人发明），本身也是一棵二叉查找树，其产生是为了解决二叉排序树在插入时发生线性排列的现象。

平衡二叉树的严格定义是这样的：

1. 满足二叉查找树的性质，左子树所有值小于父节点，右子树所有值大于等于父节点。
2. 作为一棵平衡二叉树，它需要满足任意一个节点的左右子树的高度相差不能大于 1。

在平衡二叉树中，每次在插入数据和删除数据后，必要时就会对二叉树做一些高度的调整（左旋和右旋），来让二叉查找树的高度随时维持平衡，将查找、插入、删除操作的时间复杂度保证在 O(log­n) 范围内。通常只有从那些插入点到根节点的路径上的节点的平衡性可能被改变，因为只有这些节点的子树可能变化。

平衡二叉树适用于动态数据，这就完成了哈希表不便完成的工作——动态性。所以：

• 如果输入集合确定，所需要的就是查询，则可以考虑使用哈希表。
• 如果输入集合不确定，则考虑使用平衡二叉树/红黑树，保证达到最大效率。

平衡二叉树主要优点集中在快速查找，频繁旋转会使插入和删除牺牲掉 O(log­n) 左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

3. 平衡二叉树的高度调整方式

高度调整的关键是找出“不平衡点”，主要的四种调整方式有 LL（左旋）、RR（右旋）、LR（先左旋再右旋）、RL（先右旋再左旋）。这里介绍下简单的单旋转操作，左旋和右旋。LR 和 RL 本质上只是 LL 和 RR 的组合。

调整思路：在插入一个结点后应该沿搜索路径将路径上的节点平衡因子进行修改，当平衡因子大于 1 时，就需要进行平衡化处理。从发生不平衡的节点起，沿刚才回溯的路径取直接下两层的节点，如果这三个节点在一条直线上，则采用单旋转进行平衡化，如果这三个节点位于一条折线上，则采用双旋转进行平衡化。

（平衡因子 = 左子树高度 - 右子树高度）

左旋的操作可以用一句话简单表示：将当前节点 S 的左孩子旋转为当前结点父节点 E 的右孩子，同时将父节点 E 旋转为当前节点 S 的左孩子。可用动画表示：

右旋的操作同样可以用一句话简单表示：将当前节点 S 的左孩子 E 的右孩子旋转为当前节点 S 的左孩子，同时将当前节点 S 旋转为左孩子 E 的右孩子。可用动画表示：

6、红黑树

平衡二叉树（AVL）为了追求高度平衡，需要通过平衡处理使得左右子树的高度差必须小于等于 1。高度平衡带来的好处是能够提供更高的搜索效率，其最坏的查找时间复杂度都是 O(logn)。但是由于需要维持这份高度平衡，所付出的代价就是当对树种结点进行插入和删除时，需要经过多次旋转实现复衡。这导致 AVL 的插入和删除效率并不高。

为了解决这样的问题，能不能找一种结构能够兼顾搜索和插入、删除的效率呢？这时候红黑树便申请出战了。

红黑树具有五个特性：

1. 每个节点要么是红的，要么是黑的。
2. 根节点是黑的。
3. 每个叶子节点（叶子节点即树尾端 NIL 指针或 NULL 节点）都是黑的。
4. 如果一个节点是红的，那么它的两个子节点都是黑的。
5. 对于任意节点而言，其到叶子节点树尾端 NIL 指针的每条路径都包含相同数目的黑节点。

红黑树通过将节点进行红黑着色，使得原本高度平衡的树结构被稍微打乱，平衡程度降低。红黑树不追求完全平衡，只要求达到部分平衡。这是一种折中的方案，大大提高了节点删除和插入的效率。C++ 中的 STL 就常用到红黑树作为底层的数据结构。

红黑树 VS 平衡二叉树：

7、B 树和 B+ 树

数据库索引大量使用到了 B 树和 B+ 树，索引一般需要解决下面两个问题：

1. 根据某个值查找数据，比如 select * from user where id=1234；
2. 根据区间值来查找某些数据，比如 select * from user where id > 1234 and id < 2345。

尝试用数据结构解决这个问题：

• 散列表的查询性能很好，时间复杂度是 O(1)。但是，散列表不能支持按照区间快速查找数据。
• 平衡二叉查找树尽管查询的性能也很高，时间复杂度是 O(logn)，而且对树进行中序遍历时我们还可以得到一个从小到大有序的数据序列，但这仍然不足以支持按照区间快速查找数据。
• 跳表是在链表之上加上多层索引构成的。它支持快速地插入、查找、删除数据，对应的时间复杂度是 O(logn)。并且跳表也支持按照区间快速地查找数据。

这样看来，跳表是可以解决这个问题。实际上，数据库索引所用到的数据结构跟跳表非常相似，叫作 B+ 树。不过，它是通过二叉查找树演化过来的，而非跳表。

1. B+ 树

1）B+ 树的思想

为了让二叉查找树支持按照区间来查找数据，我们可以对它进行这样的改造：树中的节点并不存储数据本身，而是只是作为索引。除此之外，我们把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。经过改造之后的二叉树，就像图中这样，看起来是不是很像跳表呢？

但是，当我们要为几千万、上亿的数据构建索引时，即使将索引存储在内存中，内存访问的速度非常快，查询的效率非常高，但同时，占用的内存也会非常大，所以借助时间换空间的思路，把索引存储在硬盘中，而非内存中。

我们知道，硬盘是一个非常慢速的存储设备。通常内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的。这种将索引存储在硬盘中的方案，尽管减少了内存消耗，但是在数据查找的过程中，需要读取磁盘中的索引，因此数据查询效率就相应降低很多。

综上，索引查找的效率取决于磁盘 I/O 的次数；而磁盘 I/O 的次数取决于树的高度；那如何降低树的高度呢？如果我们把索引构建成 m 叉树，高度是不是比二叉树要小呢？

不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 I/O 操作。所以，我们在选择 m 大小的时候，要尽量让每个节点的大小等于一个页的大小。这样，读取一个节点只需要一次磁盘 I/O 操作。

2）B+ 树的性质

• m 叉树只存储索引，并不真正存储数据，这个有点儿类似跳表。
• 通过链表将叶子节点串联在一起，这样可以方便按区间查找。
• 一般情况，根节点会被存储在内存中，其他节点存储在磁盘中。
• 根节点中子节点的个数不能超过 m。
• 除根节点外每个节点中子节点的个数不能超过 m，也不能小于 m/2（向上取整，包括 m/2）。
• 除叶子节点外，每个节点的关键字个数 = 子节点个数 - 1。

2. B 树

1）定义

B-tree 全称 Balance-tree（平衡多路查找树），平衡的意思是左边和右边分布均匀。多路的意思是相对于二叉树而言的，二叉树就是二路查找树，查找时只有两条路，而 B-tree 有多条路，即父节点有多个子节点。

而 B 树实际上是低级版的 B+ 树，或者说 B+ 树是 B 树的改进版。B 树跟 B+ 树的不同点主要集中在这几个地方：

• B+ 树中的节点不存储数据，只存储索引；而 B 树中的节点存储数据。
• B 树中的叶子节点并不需要链表来串联。
• 也就是说，B 树只是一个每个节点的子节点个数不能小于 m/2 的 m 叉树。

2）m 阶 B 树的性质

• 阶数表示了一个节点最多有多少个子节点，一般用字母 m 表示阶数；
• 根节点中子节点的个数不能超过 m；
• 除根节点外每个节点中子节点的个数不能超过 m，也不能小于 m/2（向上取整，包括 m/2）；
• 除叶子节点外，每个节点的关键字个数 = 子节点个数 - 1。

十一、图形结构及其算法

1、图简介

“图”和“图形”在数据结构的描述中指同一个概念。在图论中，图的定义有特定的含义。

图在实际的应用场景中经常出现，比如交通中的线路图等。图还被应用在数据结构中的最短路径搜索、拓扑排序等。

例如，如何计算网络上两个节点之间最短距离的问题，就变成图的数据结构要处理的问题，采用 Dijkstra 这种图形算法就能快速寻找出两个节点之间的最短距离，如果没有 Dijkstra 算法，现代网络的运行效率必将大大降低。

1. 图的定义

图（Graph）是由“顶点”和“边”所组成的集合，顶点（vertex）通常用圆圈来表示，边（edge）就是这些圆圈之间的连线，还可以根据顶点之间的关系为边设置不同的权重，默认权重相同（皆为 1）。

此外，根据边的方向性，还可将图分为有向图和无向图。

和树比起来，图是一种更加复杂的非线性表结构。树描述的是节点与节点之间“层次”的关系，而图却是讨论两个顶点之间“连通与否”的关系。

2. 图的相关概念及应用示例

微信：

• 比如在微信中可以把每个用户看作一个顶点。
• 如果两个用户之间互加好友，那就在两者之间建立一条边。
• 所以，整个微信的好友关系就可以用一张图来表示。其中，每个用户有多少个好友，对应到图中，就叫作顶点的度（degree），就是跟顶点相连接的边的条数。

微博：

• 微博的社交关系跟微信有点不一样，或者说更加复杂一点。微博允许单向关注，也就是说，用户 A 关注了用户 B，但用户 B 可以不关注用户 A。
• 因此，可以把图结构稍微改造一下，引入边的“方向”的概念：

• 如果用户 A 关注了用户 B，就在图中画一条从 A 到 B 的带箭头的边，来表示边的方向。
• 如果用户 A 和用户 B 互相关注了，那就画一条从 A 指向 B 的边，再画一条从 B 指向 A 的边。

• 我们把这种边有方向的图叫作“有向图”(Digraph)。以此类推，把边没有方向的图叫作“无向图”(Graph)。

• 无向图中有“度”这个概念，表示一个顶点有多少条边；而在有向图中，把度分为入度（In-degree）和出度（Out-degree）。

• 顶点的入度：表示有多少条边指向这个顶点。
• 顶点的出度：表示有多少条边是以这个顶点为起点指向其他顶点。

• 对应到微博的例子，入度就表示有多少粉丝，出度就表示关注了多少人。

QQ：

• QQ 中的社交关系要更复杂一点。QQ 不仅记录了用户之间的好友关系，还记录了两个用户之间的亲密度。如果两个用户经常往来，那亲密度就比较高；如果不经常往来，亲密度就比较低。
• 为此，要用到另一种图——带权图（weighted graph）。在带权图中，每条边都有一个权重（weight），可以通过这个权重来表示 QQ 好友间的亲密度。

2、图的数据表示法

图结构用抽象的图线来表示十分简单，顶点和边之间的关系非常清晰明了。但是在具体的代码实现中，为了将各个顶点和边的关系存储下来，却不是一件易事。

1. 邻接矩阵

图最直观的一种存储方法就是邻接矩阵（Adjacency Matrix），邻接矩阵的底层依赖一个二维数组。

对于一个图 G = (V, E)，V 代表顶点的集合，E 代表边的集合。假设该图有 n 个顶点， n >= 1，则可以将 n 个顶点使用一个 n X n 的二维矩阵来表示。其中若 A(i, j) = 1，则表示图中有一条边 (Vi, Vj) 存在；反之，若 A(i, j) = 0，则不存在 (Vi, Vj)。

• 对无向图而言，如果顶点 i 与顶点 j 之间有边，就将 A[i][j] 和 A[j][i] 标记为 1；
• 对有向图而言，如果顶点 i 到顶点 j 之间有一条箭头从顶点 i 指向顶点 j 的边，那就将 A[i][j] 标记为 1。
• 对带权图而言，数组中就存储相应的权重。

相关特性说明：

1. 对无向图而言，邻接矩阵一定是对称的，而且对角线一定为 0；有向图则不一定如此。
2. 对无向图而言，顶点 i 的度就是第 i 行所有元素的和；而在有向图中，顶点 i 的出度就是第 i 行所有元素的和，而入度是第 j 列所有元素的和。
3. 用邻接矩阵表示图共需要 n2 个单位空间，由于无向图的邻接矩阵一定具有对称关系的，扣除对角线全部为零之外，仅需存储上三角形或下三角形的数据即可，因此仅需 n(n-1)/2 的单位空间。

邻接矩阵的优缺点：

优点：

1. 邻接矩阵的存储方式简单直观，因为基于数组，所以在获取两个顶点的关系时，就非常高效。
2. 要在图中加入新边时，这个表示法的插入和删除操作相当简易。
3. 用邻接矩阵存储图的另外一个好处是计算方便，借着矩阵的运算有许多特别的应用。

缺点：

用邻接矩阵来表示一个图，虽然简单、直观，但是比较浪费存储空间。如果要计算所有顶点的度，其时间复杂度为 O(n2)。

1. 无向图的二维数组中，如果将其用对角线划分为上下两部分，只需要利用上面或者下面这样一半的空间就足够了，另外一半白白浪费掉了。
2. 如果存储的是稀疏图（Sparse Matrix），也就是说，顶点很多但每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间了。比如微信有好几亿的用户，对应到图上就是好几亿个顶点，但是每个用户的好友并不会很多，一般也就三五百个而已。如果用邻接矩阵来存储，那绝大部分的存储空间都被浪费了。

代码实现邻接矩阵：

# 无向图的邻接矩阵算法
def adjacency_matrix(arr):
    # 首先获取最大顶点值，即 n*n的n
    max_n = 1
    for e in arr:
        if e[0] > max_n:
            max_n = e[0]
        if e[1] > max_n:
            max_n = e[1]
    # 矩阵中的行和列的索引默认从1开始，所以长度要+1
    n = max_n + 1
    # 初始化结果矩阵（n*n）
    result_arr = [[0]*n for row in range(n)]

    # 读取图的每条边的数据，获取起始和终止顶点
    for i in range(len(arr)):
        tmp_i = arr[i][0]  # 起始顶点
        tmp_j = arr[i][1]  # 终止顶点
        result_arr[tmp_i][tmp_j] = 1  # 有边的点填入1

    # 输出结果
    print("邻接矩阵：")
    for i in range(1, n):
        for j in range(1, n):
            print("%s " % result_arr[i][j], end=" ")
        print()
    return result_arr


# 无向图
graph_data = [[1,2], [2,1], [1,5], [5,1], [2,3], [3,2], [2,4], [4,2], [3,4], [4,3]]
adjacency_matrix(graph_data)

# 有向图
digraph_data = [[1,2], [2,1], [2,3], [2,4], [4,3], [4,1]]
adjacency_matrix(digraph_data)

执行结果：

邻接矩阵：
0  1  0  0  1
1  0  1  1  0
0  1  0  1  0
0  1  1  0  0
1  0  0  0  0
邻接矩阵：
0  1  0  0
1  0  1  1
0  0  0  0
1  0  1  0

2. 邻接表

针对邻接矩阵较为浪费内存空间的问题，可以考虑更有效的另一种图的存储方法——邻接表（Adjacency List）。邻接表有点像散列表，每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。

下图中画的是一个有向图的邻接表存储方式，每个顶点对应的链表里面，存储的是指向的顶点。对无向图而言也是类似的，只是每个顶点的链表中存储的，是跟这个顶点有边相连的顶点。

邻接表的优缺点：

这其实就是时间、空间复杂度互换的设计思想：邻接矩阵存储起来比较浪费空间，但是使用起来比较节省时间；相反，邻接表存储起来比较节省空间，但是使用起来就较为耗时。

优点：

1. 邻接矩阵如果要计算所有顶点的度，其时间复杂度为 O(n2)；而邻接表计算所有顶点的度，邻接表的时间复杂度为 O(n+e)，n 为链表个数，e 为每个链表中的元素个数。

缺点：

1. 比起邻接矩阵的存储方式，在邻接表中查询两个顶点之间的关系就没那么高效了。如上图示例，如果要确定，是否存在一条从顶点 2 到顶点 4 的边，那就要遍历顶点 2 对应的那条链表，看链表中是否存在顶点 4。
2. 有新边加入图中或从图中删除边时，就要修改相关的链表链接，较为麻烦和耗时。

邻接表的优化方案：

• 在基于链表法解决冲突的散列表中，如果链过长，为了提高查找效率，可以将链表换成其他更加高效的数据结构，比如平衡二叉查找树等。而因为邻接表长得很像散列表，所以也可以将邻接表同散列表一样进行“改进升级”。

• 例如可以将邻接表中的链表改成平衡二叉查找树，来提高查询效率。实际开发中，可以选择用红黑树。这样，就可以更加快速地查找两个顶点之间是否存在边了。
• 这里的二叉查找树还可以换成其他动态数据结构，比如跳表、散列表等。

• 除此之外，还可以将链表改成有序动态数组，可以通过二分查找的方法来快速定位两个顶点之间否是存在边。

代码实现邻接表：

# 链表的节点类
class Node:

    def __init__(self, data=None):
        self.data = data
        self.next = None

# 链表类
class LinkList:

    def __init__(self, data=None):
        self.root = Node(data)

    def add(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            cur = self.root
            while cur.next is not None:
                cur = cur.next
            cur.next = Node(data)

    def travel(self):
        cur = self.root
        while cur is not None:
            print(cur.data, end=" ")
            cur = cur.next

# 邻接表算法
def adjacency_list(arr):
    # 邻接表结果
    result_arr = []
    # 遍历图的每个数据，获取起始顶点和终止顶点
    for e in arr:
        # 遍历现有链表，如果该起始顶点的链表已存在，则新增节点
        for cur_link in result_arr:
            if cur_link.root.data == e[0]:
                cur_link.add(e[1])
                break
        # 如果不存在，则新增链表
        else:
            ll = LinkList(e[0])
            ll.add(e[1])
            result_arr.append(ll)

    # 打印结果
    print("邻接表：")
    for link in result_arr:
        link.travel()
        print()
    return result_arr

graph_data = [[1,2], [2,1], [2,3], [3,2], [2,4], [4,2], [3,4], [4,3], [2,5], [5,3], [3,5], [5,3], [4,5], [5,4]]
adjacency_list(graph_data)

执行结果：

邻接表：
1 2
2 1 3 4 5
3 2 4 5
4 2 3 5
5 3 3 4

3. 逆邻接表

逆邻接表与邻接表结构类似，只不过图的顶点链接的是指向该顶点的相邻顶点。也就是说，邻接表是顺着图中的箭头寻找相邻顶点，而逆邻接表是逆着图中的箭头寻找相邻顶点。

邻接表和逆邻接表的共同使用下，就能够把一个完整的有向图结构进行表示。可以发现，邻接表和逆邻接表实际上有一部分数据是重合的，因此可以将两个表合二为一，从而得到了所谓的十字链表。

4. 十字链表

十字链表是有向图的邻接表改进形式，似乎很简单，只需要通过相同的顶点分别链向以该顶点为终点和起点的相邻顶点即可。

但这并不是最优的表示方式。虽然这样的方式共用了中间的顶点存储空间，但是邻接表和逆邻接表的链表节点中重复出现的顶点并没有得到重复利用，反而是进行了再次存储。

因此，上图的表示方式还可以进行进一步优化，如下图所示： 

十字链表优化后，可通过扩展的顶点结构和边结构来进行正逆邻接表的存储（下图中的弧头可看作终止顶点，弧尾可看作是起始顶点）：

• data：用于存储该顶点中的数据；
• firstin 指针：用于连接从别的顶点指进来的顶点；
• firstout 指针：用于连接从该顶点指出去的顶点。

边结构通过存储两个顶点来确定一条边，同时通过分别代表这两个顶点的指针来与相邻顶点进行链接：

• tailvex：用于存储作为弧尾的顶点的编号；
• headvex：用于存储作为弧头的顶点的编号；
• headlink 指针：用于链接下一个存储作为弧头的顶点的节点；
• taillink 指针：用于链接下一个存储作为弧尾的顶点的节点。

以上图为例子，对于顶点 A 而言，其作为起点能够到达顶点 E。因此在邻接表中顶点 A 要通过边 AE（即边 04）指向顶点 E，顶点 A 的 firstout 指针需要指向边 04 的 tailvex。同时，从 B 出发能够到达 A，所以在逆邻接表中顶点 A 要通过边 AB（即边 10）指向 B，顶点 A 的 firstin 指针需要指向边 10 的弧头，即 headlink 指针。依次类推。

十字链表采用了一种看起来比较繁乱的方式对边的方向性进行了表示，能够在尽可能降低存储空间的情况下增加指针保留顶点之间的方向性。但具体的操作可能一时间不好弄懂。

5. 应用示例

如何存储微博社交网络中的好友关系？

数据结构是为算法服务的，所以具体选择哪种存储方法，与期望支持的操作有关系。针对微博用户关系，假设需要支持下面这样几个操作：

• 判断用户 A 是否关注了用户 B；
• 判断用户 A 是否是用户 B 的粉丝；
• 用户 A 关注用户 B；
• 用户 A 取消关注用户 B；
• 根据用户名称的首字母排序，分页获取用户的粉丝列表；
• 根据用户名称的首字母排序，分页获取用户的关注列表。

1）邻接表

关于如何存储一个图，主要的存储方法有：邻接矩阵和邻接表。而因为社交网络是一张稀疏图，使用邻接矩阵存储比较浪费存储空间。所以，这里采用邻接表来存储。

2）邻接表 + 逆邻接表

不过，用一个邻接表来存储这种有向图是不够的。比如去查找某个用户关注了哪些用户非常容易，但是如果要想知道某个用户都被哪些用户关注了，也就是用户的粉丝列表，是非常困难的。

基于此，需要一个逆邻接表。邻接表中存储了用户的关注关系，逆邻接表中存储的是用户的被关注关系。

对应到下图，邻接表中，每个顶点的链表中，存储的就是这个顶点指向的顶点；逆邻接表中，每个顶点的链表中，存储的是指向这个顶点的顶点。

如果要查找某个用户关注了哪些用户，可以在邻接表中查找；如果要查找某个用户被哪些用户关注了，从逆邻接表中查找。

3）改进邻接表中的链表 —> 跳表

但基础的邻接表不适合快速判断两个用户之间是否是关注与被关注的关系，所以选择改进版本，将邻接表中的链表改为支持快速查找的动态数据结构。比如：红黑树、跳表、有序动态数组、散列表等。

因为需要按照用户名称的首字母排序，且需要分页来获取用户的粉丝列表或者关注列表，因此这里选择跳表。

跳表的插入、删除、查找都非常高效，时间复杂度是 O(logn)，空间复杂度上稍高，是 O(n)。

最重要的一点，跳表中存储的数据本来就是有序的了，分页获取粉丝列表或关注列表，就非常高效。

4）哈希算法

如果对于小规模的数据，比如社交网络中只有几万、几十万个用户，可以将整个社交关系存储在内存中，上面的解决思路是没有问题的。但是如果像微博那样有上亿的用户，数据规模太大，就无法全部存储在内存中了。

可以通过哈希算法等数据分片方式，将邻接表存储在不同的机器上。如下图所示：机器 1 上存储顶点 1、2、3 的邻接表，在机器 2 上，存储顶点 4、5 的邻接表。逆邻接表的处理方式也一样。

当要查询顶点与顶点关系的时候，就利用同样的哈希算法，先定位顶点所在的机器，然后在相应的机器上查找。

5）外部存储 —> 数据库

除此之外，还有另外一种解决思路，就是利用外部存储（比如硬盘），因为外部存储的存储空间要比内存会宽裕很多。

数据库是经常用来持久化存储关系数据的，用下面这张表来存储这样一个图。为了高效地支持前面定义的操作，可以在表上建立多个索引，比如第一列、第二列，给这两列都建立索引。

3、图的遍历

树的遍历目的是访问每一个节点仅一次，而图的遍历指的是从图中的任一顶点出发，对图中的所有顶点访问一次且仅访问一次。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。

图的遍历可以划分为两种搜索策略：

• 深度优先遍历/搜索（DFS，Depth First Search）
• 广度优先遍历/搜索（BFS，Breadth First Search）

1. 深度优先遍历

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

这种图的遍历方法结合了递归和堆栈的技巧，由于此方法会造成无限循环，因此必须加入一个变量，判断该点是否已经遍历完毕。

图解深度优先遍历步骤：

1. 以顶点 1 为起点，将相邻的顶点 2 和顶点 5 压入堆栈：[5, 2]
2. 弹出顶点 2，将与顶点 2 相邻且未访问过的顶点 3 和顶点 4 压入堆栈：[5, 4, 3]
3. 弹出顶点 3，将与顶点 3 相邻且未访问过的顶点 4 和顶点 5 压入堆栈：[5, 4, 5, 4]
4. 弹出顶点 4，将与顶点 4 相邻且未访问过的顶点 5 压入堆栈：[5, 4, 5, 5]　
5. 弹出顶点 5，将与顶点 5 相邻且未访问过的顶点压入堆栈。此时与顶点 5 相邻的顶点都访问过了，所以无需再压栈：[5, 4, 5]
6. 将堆栈内的值弹出并判断是否已经遍历过了，直到堆栈内无节点可遍历为止。

故该图的深度优先遍历顺序为：顶点 1、2、3、4、5。

代码实现深度优先遍历：

# 链表的节点类
class Node:

    def __init__(self, data=None):
        self.data = data
        self.next = None

# 链表类
class LinkList:

    def __init__(self, data=None):
        self.root = Node(data)

    def add(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            cur = self.root
            while cur.next is not None:
                cur = cur.next
            cur.next = Node(data)

    def travel(self):
        cur = self.root
        while cur is not None:
            print(cur.data, end=" ")
            cur = cur.next

# 邻接表算法
def adjacency_list(arr):
    # 邻接表结果
    result_arr = []
    # 遍历图的每个数据，获取起始顶点和终止顶点
    for e in arr:
        # 遍历现有链表，如果该起始顶点的链表已存在，则新增节点
        for cur_link in result_arr:
            if cur_link.root.data == e[0]:
                cur_link.add(e[1])
                break
        # 如果不存在，则新增链表
        else:
            ll = LinkList(e[0])
            ll.add(e[1])
            result_arr.append(ll)

    # 打印结果
    print("邻接表：")
    for link in result_arr:
        link.travel()
        print()
    print()
    return result_arr


# 深度遍历算法
def dfs(run_list, arr, current):
    # run_list 记录每个顶点是否被访问过
    # arr 表示邻接表
    # current 表示当前所在顶点，1 表示已访问
    run_list[current] = 1
    print(arr[current].root.data, end=" ")  # 打印顶点
    cur = arr[current].root.next
    while cur is not None:  # 遍历访问相邻顶点
        # 如果顶点未被访问过，就递归调用dfs（效果等同压栈）
        if run_list[cur.data-1] == 0:
            dfs(run_list, arr, cur.data-1)
        cur = cur.next


# 原始图数据
graph_data = [[1,2], [1,5], [2,1], [2,3], [2,4], [3,2], [3,4], [3,5], [4,2], [4,3], [4,5], [5,1], [5,3], [5,4]]

# 记录每个顶点是否访问过，0 表示未访问过
run = [0] * len(graph_data)

# 使用邻接表存储原始图数据
arr = adjacency_list(graph_data)

print("深度优先遍历结果：")
# 进行深度优先遍历
dfs(run, arr, 0)

执行结果：

邻接表：
1 2 5
2 1 3 4
3 2 4 5
4 2 3 5
5 1 3 4

深度优先遍历结果：
1 2 3 4 5

2. 广度优先遍历

广度优先遍历利用队列和递归技巧，从图的某一顶点开始遍历，被访问过的顶点就做上已访问的记号，接着遍历此顶点所有相邻且未访问过的顶点中的任一顶点，并做上已访问的记号，再以该点为新的起点继续进行深度优先遍历。

图解广度优先遍历步骤：

1. 以顶点 1 为起点，将相邻的顶点 2 和顶点 5 加入队列：[2, 5]
2. 取出顶点 2，将与顶点 2 相邻且未访问过的顶点 3 和顶点 4 加入队列：[5, 3, 4]
3. 取出顶点 5，将与顶点 5 相邻且未访问过的顶点 3 和顶点 4 加入队列：[3, 4, 3, 4]
4. 取出顶点 3，将与顶点 3 相邻且未访问过的顶点 4 加入队列：[4, 3, 3, 4]　
5. 取出顶点 4，将与顶点 4 相邻且未访问过的顶点加入队列。此时与顶点 4 相邻的顶点都访问过了，所以再加入队列：[3, 4, 2, 4]
6. 将队列内的值取出并判断是否已经遍历过了，直到队列内无节点可遍历为止。

故该图的广度优先遍历顺序为：顶点 1、2、5、3、4。

代码实现广度优先遍历：

# 链表的节点类
class Node:

    def __init__(self, data=None):
        self.data = data
        self.next = None

# 链表类
class LinkList:

    def __init__(self, data=None):
        self.root = Node(data)

    def add(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            cur = self.root
            while cur.next is not None:
                cur = cur.next
            cur.next = Node(data)

    def travel(self):
        cur = self.root
        while cur is not None:
            print(cur.data, end=" ")
            cur = cur.next

# 邻接表算法
def adjacency_list(arr):
    # 邻接表结果
    result_arr = []
    # 遍历图的每个数据，获取起始顶点和终止顶点
    for e in arr:
        # 遍历现有链表，如果该起始顶点的链表已存在，则新增节点
        for cur_link in result_arr:
            if cur_link.root.data == e[0]:
                cur_link.add(e[1])
                break
        # 如果不存在，则新增链表
        else:
            ll = LinkList(e[0])
            ll.add(e[1])
            result_arr.append(ll)

    # 打印结果
    print("邻接表：")
    for link in result_arr:
        link.travel()
        print()
    print()
    return result_arr

# 队列类
class Queue:

    def __init__(self):
        self.queue = []

    def enqueue(self, data):
        self.queue.append(data)

    def dequeue(self):
        return self.queue.pop(0)

    def is_empty(self):
        return len(self.queue) == 0


# 广度遍历算法
def bfs(queue, run_list, arr, current):
    # queue 队列
    # run_list 记录每个顶点是否被访问过
    # arr 表示邻接表

    run_list[current] = 1  # current 表示当前所在顶点，1 表示已访问
    queue.enqueue(arr[current].root.data)  # 将第一个顶点加入队列
    print(arr[current].root.data, end=" ")  # 打印第一个顶点的值
    # 判断当前队列是否为空
    while not queue.is_empty():
        # 取出队列中的顶点
        cur = queue.dequeue()
        cur_node = arr[cur-1].root
        # 遍历访问相邻顶点
        while cur_node is not None:
            # 如果顶点未被访问过
            if run_list[cur_node.data-1] == 0:
                queue.enqueue(cur_node.data)
                run_list[cur_node.data-1] = 1  # 记录已遍历过
                print(cur_node.data, end=" ")  # 打印顶点
            cur_node = cur_node.next


# 原始图数据
graph_data = [[1,2], [1,5], [2,1], [2,3], [2,4], [3,2], [3,4], [3,5], [4,2], [4,3], [4,5], [5,1], [5,3], [5,4]]

# 记录每个顶点是否访问过，0 表示未访问过
run = [0] * len(graph_data)

# 使用邻接表存储原始图数据
arr = adjacency_list(graph_data)

print("广度优先遍历结果：")
# 进行广度优先遍历
bfs(Queue(), run, arr, 0)

执行结果：

邻接表：
1 2 5
2 1 3 4
3 2 4 5
4 2 3 5
5 1 3 4

广度优先遍历结果：
1 2 5 3 4

4、最小成本生成树

1. 基本概念

1）无向连通图

无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。如下图的无向图就是一个连通图，因为此图中任意两顶点之间都是连通的。

V2 和 V4 通过 V1 中转连通。

2）最小生成树

首先对于一张图，我们有一个定理：n 个顶点用 n-1 条边连接，形成的图形只可能是树。我们可以这样理解：树中的每一个节点都有唯一的父节点，也就是至少有 n 条边，但是根节点要除外，所以就是 n-1 条边。

那么，对于一张 n 个顶点的带权的无向连通图，它的生成树（spanning tree）就是用其中的 n-1 条边来连接这 n 个顶点，而最小成本生成树（MST，Minimun Cost Spanning Tree）就是 n-1 条边的边权之和最小的一种方案。简单的理解，就是用让这张图只剩下 n-1 条边，同时这 n-1 条边的边权总和最小。

最小生成树在生活中的应用十分广泛，比如：要连通 n 个城市需要 n-1 条边线路，那么怎么样建设才能使工程造价最小呢？可以把线路的造价看成权值，来求这几个城市的连通图的最小生成树。求最小造价的过程也就转化成求最小生成树的过程，则最小生成树表示使其造价最小的生成树。

3）常用算法

求最小生成树的过程，我们可以理解为建一棵树。要使边权总和最小，我们不难想到可以用贪心的思想：让最小生成树里的每一条边都尽可能小。那么我们有两种思路，分别对应着两种算法： Kruskal 算法（ 克鲁斯卡尔算法）和 Prim 算法（普里姆算法）。Kruskal 算法涉及大量对边的操作，因此适用于稀疏图；普通的 prim 算法则适用于稠密图。

2. Kruskal 算法（ 克鲁斯卡尔算法）

我们不难想到一种贪心的策略：每一条边的边权都是小的，那这些边连接起来的边权总和一定也是小的。因此，我们可以先挑选最小的，再挑选次小的、第三小的......直到我们挑了 n-1 条边。为此，我们可以将这些边按照边权排序，然后开始挑选边。为什么是挑选边呢？不是越小的边越好吗，为什么还要挑？

边权小固然好，但是不要忘记我们有一个大前提：我们要建的是树，它里面不能存在环。也就是说，假如我们看到一条边连着的两个顶点在我们建的树里已经连通了，那这条边还需要再加进来吗？很显然不用。

图解用 K 氏法得到最小生成树：

我们将上图的边排序后从小到大依次为： 

要建的最小生成树一开始如下所示：

我们的操作就是往这棵树里加边，其操作过程如下所示： 

直到目前为止，一切都很顺利。轮到我们的第五条边（2 3 6）了。我们发现，2 和 3 已经连通，通过 1 作为中转，这时候我们就不能将（2 3 6）这条边加入到我们的树中了。同理，下一条⑥号边也要跳过，因为 4 和 5 已经连通了。接下来，我们加入（3 4 9）这条边，如图所示： 

至此，我们建的树里每个节点都已经连接了，刚好用了 5 条边，也就是我们说的 n-1 条边，算法结束。

代码实现 K 氏法：

算法的难点在于如何判断两点是否已经连通。我们可以用深搜或广搜来解决，但显然效率极低。因此，我们需要借助一种强大的数据结构：并查集。并查集的最强大的功能就是可以快速地判断两个元素是否在同一集合内（祖先是否相同），所以我们可以借助它来判断两点是否连通。

下面将使用一个二维数组存储成本表并用 K 氏法对其排序，最后求出最小成本树。

# 成本表数组
data = [[1,2,1], [1,3,2], [2,3,6], [2,4,11], [3,4,9], [3,5,13], [4,6,3], [4,5,7], [5,6,4]]
# 图的顶点数
VERTS = 6


# 声明边的类
class Edge:
    def __init__(self):
        self.start = 0  # 起始顶点
        self.to = 0  # 终止顶点
        self.find = 0  # 该边是否已加入图
        self.val = 0  # 权值/成本
        self.next = None  # 链接下一条边


# 建立图的链表（用链表将顶点升序连接）
def graph_link(data):
    head = None
    for i in range(len(data)):
        for j in range(1, VERTS+1):
            # 如果遍历到的成本表数据的起始顶点等于顶点记录表v的索引位（顶点值）
            if data[i][0] == j:
                new_node = Edge()
                new_node.start = data[i][0]
                new_node.to = data[i][1]
                new_node.val = data[i][2]
                new_node.find = 0
                if head is None:
                    head = new_node
                else:
                    cur = head
                    while cur.next is not None:
                        cur = cur.next
                    cur.next = new_node
    return head


# 根据传入的图链表，搜索成本最小的边
def find_min_cost(head):
    min_val = 100  # 初始化一个最小成本
    cur = head
    tmp_min_edge = cur
    while cur is not None:
        # 如果找到更小成本的边，且改变未被搜索过
        # 就把改变设为当前最小成本
        if cur.val < min_val and cur.find == 0:
            min_val = cur.val
            tmp_min_edge = cur
        cur = cur.next
    tmp_min_edge.find = 1  # 将tmp_min_edge 设为已找到的边
    return tmp_min_edge


# 自定义并查集类，用来判断两点是否已连通。
# 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。
class UnionFind:

    # 在构造函数中，初始化一个数组parent，parent[i]表示的含义为，索引为i的节点，它的直接父节点为parent[i]。
    # 初始化时各个节点都不相连，因此初始化parent[i]=i，让自己成为自己的父节点，从而实现各节点不互连。
    def __init__(self, n):
        self.parent = list(range(n))

    # 由于parent[i]仅表示自己的直接父节点，查询两个节点是否相交需要比较它们的根节点是否相同
    def get_root(self, i):
        while i != self.parent[i]:  # 循环找到根节点
            i = self.parent[i]
        return i

    # 通过来比较根节点是否相同来判断两节点是否连通
    def is_connected(self, i, j):
        return self.get_root(i) == self.get_root(j)

    # 当要连通两个节点时，我们要将其中一个节点的根节点的parent，设置为另一个节点的根节点。
    # 注意，连通两个节点并非仅仅让两节点自身相连，实际上是让它们所属的集合实现合并。
    def union(self, i, j):
        i_root = self.get_root(i)
        j_root = self.get_root(j)
        self.parent[i_root] = j_root


# 最小成本树生成函数
def min_tree(head):
    cur = head
    u = UnionFind(VERTS+1)
    # 遍历图链表中的所有边
    while cur is not None:
        # 每次从图链表中找出最小成本的边
        min_edge = find_min_cost(head)
        # 如果起始和终止顶点已连通，则跳过该边；否则就设为连通
        if not u.is_connected(min_edge.start, min_edge.to):
            u.union(min_edge.start, min_edge.to)
            print("起始顶点 [%d] —> 终止顶点 [%d] —> 成本 [%d]" \
                % (min_edge.start, min_edge.to, min_edge.val))
        cur = cur.next


print("*"*50)
print("建立最小成本树：")
print("*"*50)
min_tree(graph_link(data))

执行结果：

**************************************************
建立最小成本树：
**************************************************
起始顶点 [1] —> 终止顶点 [2] —> 成本 [1]
起始顶点 [1] —> 终止顶点 [3] —> 成本 [2]
起始顶点 [4] —> 终止顶点 [6] —> 成本 [3]
起始顶点 [5] —> 终止顶点 [6] —> 成本 [4]
起始顶点 [3] —> 终止顶点 [4] —> 成本 [9]

3. Prim 算法（普里姆算法）

除了通过加入边来建树，我们还有没有其它的方法了呢？Kurskal 中，我们加入边，是在我们固定了节点的情况下完成的。也就是，我们这时候不在乎这些节点，我们只在乎连接它们的边。那我们可以不可以在乎一下这些节点呢？这时候，我们建树的过程就不是添加边了，而是添加点。

1）Prim 算法的基本思路

将图中的所有的顶点分为两类：树顶点（已经被选入生成树的顶点）和非树顶点（还未被选入生成树的顶点）。

首先选择任意一个顶点加入生成树，接下来要找出一条边添加到生成树，这需要枚举每一个树顶点到每一个非树顶点所有的边，然后找到最短边加入到生成树。依次重复操作 n-1 次，直到将所有顶点都加入生成树中。

2）图解 Prim 算法

• 我们选择一个起点，然后在与起点相连且未被选的顶点中选择一个权值最小的顶点，将该顶点与其相连边添加入生成树。假设起点是 1 顶点，与 1 顶点相连且未被选的顶点是 {2,3,4}，分别对应的权值是 {6,1,5}，可见当前最小的权值 1，权值最小的顶点就是 3 顶点，所以将 3 顶点和 1-3 的边添加入生成树。
• 接着我们在与已选顶点相连且未被选的顶点中选择一个权值最小的顶点，将该顶点与其相连边添加入生成树。当前已选顶点是 1、3 顶点，与已选顶点相连且未被选的顶点有 {2,3,4,5}，而当前最小的权值 4，权值最小的顶点就是 6 顶点，所以将 6 顶点和 3-6 的边添加入生成树。
• 接着我们依照上一次的步骤继续在与已选顶点相连且未被选的顶点中选择一个权值最小的顶点，将该顶点与其相连边添加入生成树。最终图 e 就是我们通过 Prim 算法得到的最小生成树了。

5、图的最短路径

最短路径的概念：从有向图中某一顶点（起始顶点）到达另一顶点（终止顶点）的路径中，其权值之和最小的路径。简单来说就是找出两个顶点间可通行的花费最少的方式，如下图所示。

由于交通运输工具和通信工具的便利和普及，两地之间发生货物或者进行信息传递时，最短路径（The Shortest Path）的问题随时都可能因需求而产生。

最小成本生成树（MST）计算的是连通网络中每一个顶点所需的最少花费，但是连通树中任意两顶点的路径不一定是一条花费最少的路径，这也是研究最短路径问题的主要理由。一般讨论的方向有两种：一种是 Dijkstra（迪杰斯特拉）算法，另一种是 Floyd（弗洛伊德）算法。

1. Dijkstra 算法（迪杰斯特拉算法）

一个顶点到多个顶点的最短路径通常使用 Dijkstra 算法求得，其核心是通过已知最短路径寻找未知最短路径，本质是贪心思想。

Dijkstra 是单源最短路算法，不能处理带负边权的情况，用邻接矩阵或邻接表存图。

解决思路：首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的。所谓松弛就是遍历一遍看看通过刚刚找到的距离最短的点作为中转站到其他顶点会不会更近，如果更近了就更新距离。这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。

1. 声明一个数组 dis 来保存起始点到各个顶点的最短距离，和一个保存已经找到了最短路径的顶点的集合 S。
2. 初始时，源点 s 的路径权重被赋为 0（dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s, m），则把 dis[m] 设为 w（s, m）,同时把所有其他（s 不能直接到达的）顶点的路径长度设为无穷大。因此初始时，集合 S 只有顶点 s。
3. 从 dis 数组选择最小值，则该值就是源点 s 到该值对应的顶点的最短路径，并且把该点加入到 S 中，此时完成一个顶点。
4. 我们需要看看新加入的顶点是否可以到达其他顶点，并且进行松弛，即看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在 dis 中的值。
5. 从 dis 中找出最小值，重复上述动作，直到 S 中包含了图的所有顶点。

图解 Dijkstra 算法：

以下图为示例，求从顶点 v1 到其他各个顶点的最短路径。

1）首先将v1 顶点进行标识，并作为当前顶点。以此声明一个 dis 数组和集合 S。如下图所示：

集合 S：初始化为 {v1}。

dis 数组：源点 v1 的路径权重被赋为 0，v1 不能到达的 v2 和 v4 顶点则赋为 ∞，其余能达到的顶点则按权重赋值。

2）求 v1 顶点到其余各个顶点的最短路程。如下图所示：

先找一个离v1 顶点最近的顶点。通过数组 dis 可知当前离 v1 顶点最近是 v3 顶点。当选择了 v3 顶点后，dis[2]（下标从0开始）的值（即加入了集合 s 的顶点在 dis 中对应的值）就已经从“估计值”变为了“确定值”，即 v1 顶点到  v3 顶点的最短路程就是当前 dis[2] 值。并将 v3 加入到 S 中。

为什么 v1 顶点到 v3 顶点的最短路径即 0 -> 10 呢？因为目前离  v1 顶点最近的是 v3 顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 v1 顶点到 v3 顶点的路程进一步缩短了。因为 v1 顶点到其它顶点的路程肯定没有 v1 到 v3 顶点短。

3）将顶点 v3 进行标识，并作为当前顶点

下面我们根据这个新入的顶点 v3 的出度，发现以 v3 为弧尾的有：< v3,v4 >，那么我们看看路径：v1–v3–v4 的长度是否比 v1–v4 短。其实这个已经是很明显的了，因为 dis[3] 代表的就是 v1–v4 的长度为无穷大，而 v1–v3–v4 的长度为：10+50=60，所以更新 dis[3] 的值,得到如下结果：

dis[3] 更新为 60 的这个过程有个专业术语叫做“松弛”。即 v1 顶点到 v4 顶点的路程即 dis[3]，通过 <v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过“边”来松弛 v1 顶点到其余各个顶点的路程。 

4）将顶点 v5 进行标识，并作为当前顶点

我们又从除了 dis[2] 和 dis[0] 外的其他值中寻找最小值，发现 dis[4] 的值最小，通过之前解释的原理，可以知道 v1到 v5 的最短距离就是 dis[4] 的值，然后，我们把 v5 加入到集合 S 中，然后，考虑 v5 的出度是否会影响我们的数组 dis 的值，v5有两条出度：< v5,v4> 和 < v5,v6>，然后我们发现 v1–v5–v4 的长度为：50，而 dis[3] 的值为 60，所以我们要更新 dis[3] 的值。另外，v1-v5-v6 的长度为：90，而 dis[5] 为 100，所以我们也需要更新 dis[5] 的值。更新后的 dis 数组如下图：

5）将顶点 v4 进行标识，并作为当前顶点

继续从 dis 中选择未确定的顶点的值中选择一个最小的值，发现 dis[3] 的值是最小的，于是把 v4 加入到集合 S 中，此时集合 S = {v1,v3,v5,v4}。然后，考虑 v4 的出度是否会影响我们的数组 dis 的值，v4 有一条出度：< v4,v6>，我们发现：v1–v5–v4–v6 的长度为：60，而 dis[5] 的值为 90，所以我们要更新 dis[5] 的值，更新后的 dis 数组如下图：

6）同理，分别确定了 v6 和 v2 的最短路径，最后 dis 的数组的值如下：  

从图中，我们可以发现 v1-v2 的值为 ∞，代表没有路径从 v1 到达 v2。 

最后，我们得到 v1 顶点到其他各顶点的最短距离为：

起点  终点    最短路径         长度
v1    v2     无               ∞    
      v3     {v1,v3}         10
      v4     {v1,v5,v4}      50
      v5     {v1,v5}         30
      v6     {v1,v5,v4,v6}   60

代码实现：

# 图数组的长度
SIZE = 7
# 顶点个数
VERT_NUMS = 6
# 设置无穷大
INFINITE = 99999


# 带权图的邻接矩阵算法
def adjacency_matrix(arr):
    # 矩阵中的行和列的索引默认从1开始，所以长度要+1
    n = SIZE
    # 初始化结果矩阵（n*n），INFINITE 是为了方便后续 Dijkstra 算法的使用
    result_arr = [[INFINITE]*n for row in range(n)]

    # 读取图的每条边的数据，获取起始和终止顶点
    for i in range(len(arr)):
        tmp_i = arr[i][0]  # 起始顶点
        tmp_j = arr[i][1]  # 终止顶点
        result_arr[tmp_i][tmp_j] = arr[i][2]  # 填入权值

    # 输出结果
    print("邻接矩阵：")
    for i in range(1, n):
        for j in range(1, n):
            print("%s " % result_arr[i][j], end=" ")
        print()
    return result_arr


# Dijkstra：单顶点对全部顶点的最短距离
def short_cost_path(matrix, start_vertex, vertex_nums):
    # matrix 邻接矩阵
    # start_vertex 起始顶点
    # vertex_nums 总顶点数

    # 记录当前最短距离的顶点
    shortest_vertex = 1  # 默认从顶点1开始，因此最近的是自己
    s = [0] * SIZE  # 集合S：记录该顶点是否被选取
    # 路径成本数组
    dis = [INFINITE] * SIZE
    # 初始化起始顶点的dis
    for i in range(1, SIZE):
        dis[i] = matrix[start_vertex][i]
    s[start_vertex] = 1   # 将起始顶点加入集合s
    dis[start_vertex] = 0

    # 遍历剩下的全部顶点
    for i in range(1, vertex_nums):
        shortest_distance = INFINITE
        for j in range(1, vertex_nums+1):
            # 遍历dis，找出最小距离的下一顶点
            if s[j] == 0 and shortest_distance > dis[j]:
                shortest_distance = dis[j]
                shortest_vertex = j
        # 将最小距离的下一顶点加入集合s
        s[shortest_vertex] = 1
        # 松弛：开始计算当前顶点到各出度顶点的最短距离
        for j in range(vertex_nums+1):
            # s[j] == 0 表示未在集合s中的出度顶点
            # dis[shortest_vertex]：起始点到当前顶点的暂时最短距离
            # matrix[shortest_vertex][j]：当前顶点到出度顶点的距离
            # dis[j]：起始点到出度顶点的距离
            if s[j] == 0 and dis[shortest_vertex] + matrix[shortest_vertex][j] < dis[j]:
                dis[j] = dis[shortest_vertex] + matrix[shortest_vertex][j]

    return dis


path_cost = [[1,3,10], [1,5,30], [1,6,100], [2,3,5], [3,4,50], [4,6,10], [5,4,20], [5,6,60]]
matrix = adjacency_matrix(path_cost)
print()
# 搜索顶点1到其他顶点的最短路径
dis = short_cost_path(matrix, 1, VERT_NUMS)
print("*"*50)
print("顶点1到各顶点的最短距离为：")
print("*"*50)
for i in range(1, SIZE):
    print("顶点 1 到顶点 %d 的最短距离=%d"%(i, dis[i]))

执行结果：

邻接矩阵：
99999  99999  10  99999  30  100
99999  99999  5  99999  99999  99999
99999  99999  99999  50  99999  99999
99999  99999  99999  99999  99999  10
99999  99999  99999  20  99999  60
99999  99999  99999  99999  99999  99999

**************************************************
顶点1到各顶点的最短距离为：
**************************************************
顶点 1 到顶点 1 的最短距离=0
顶点 1 到顶点 2 的最短距离=99999
顶点 1 到顶点 3 的最短距离=10
顶点 1 到顶点 4 的最短距离=50
顶点 1 到顶点 5 的最短距离=30
顶点 1 到顶点 6 的最短距离=60

2. Floyd 算法（弗洛伊德算法）

Dijkstra 算法只能求出某一点其他顶点的最短距离，如果要求出图中任意两点甚至所有顶点间的最短距离（也被称为“多源最短路径问题”），那么就需要使用 Floyd 算法。

求图中所有顶点间的最短路径，有以下两种解法：

1. 以图中的每个顶点作为起始点，调用 Dijkstra 算法，时间复杂度为 O(n3)。
2. Floyd 算法更简洁，时间复杂度仍为 O(n3)，空间复杂度为 O(n2)。

Floyd 算法是一个经典的动态规划算法，三个 for 循环便可以解决一个复杂的问题，其算法实现相比 Dijkstra 等算法是非常优雅的，可读性高，理解起来较为容易。从它的三层循环可以看出其时间复杂度为 O(n3)，除了在第二层 for 中加点判断可以略微提高效率，几乎没有其他办法再减少它的复杂度。

比较两种算法，不难得出以下的结论：

• 对于稀疏图，采用 n 次 Dijkstra 比较出色；对于稠密图，使用 Floyd 算法效果更佳。
• Floyd 算法可以处理带负边的图。

图解 Floyd 算法：

1. Floyd 算法首先初始化一个矩阵 S，记录着顶点间的最小路径。例如 S[0][3] = 10，说明顶点 0 到 3 的最短路径为 10。
2. 然后通过 3 重循环，k 为中转点，v 为起点，w 为终点，循环比较 S[v][w] 和 S[v][k] + S[k][w] 最小值，如果 S[v][k] + S[k][w] 为更小值，则把 S[v][k] + S[k][w] 覆盖保存在 S[v][w] 中。

如下图所示：

1. 矩阵 S 中，顶点 S[i][j] 的距离为顶点 i 到顶点 j 的权值；如果 i 和 j 不相邻，则 a[i][j] = ∞。
2. 以 A 为中转点，找出 S[i][j] 从 i 到 j，经由顶点 A 的最短路径，并更新矩阵。如原 S 矩阵中，S[B][G] 的值为 INF，即不存在 B->G 的最小路径，但是通过 A 为中转点，S[B][A] + S[A][G] = 12 + 14 = 26 小于 S[B][G] = INF， 所以 S[B][A] + D[A][G] 为 B -> G 的最小值，因此覆盖 S[B][G] 为 26。
3. 以 B 为中转点，找出 S[i][j] 从 i 到 j，经由顶点 B 的最短路径，并更新矩阵。如 S[A][C] 的值为 INF， 但是通过 B 作为中转点，S[A][B] + S[B][C] = 12 + 10 = 22 小于 S[A][C] = INF，所以 S[A][B] + S[B][C] 为 A->C 的最小路径，覆盖 S[A][C] 的值为 22。
4. 以此类推，当遍历完所有顶点，矩阵 S 中记录的便是各顶点间的最短路径。

代码实现：

# 顶点个数
VERT_NUMS = 7
# 图数组的长度
SIZE = 8
# 设置无穷大
INFINITE = 99999


# 带权图的邻接矩阵算法
def adjacency_matrix(arr):
    # 矩阵中的行和列的索引默认从1开始，所以长度要+1
    n = SIZE
    # 初始化结果矩阵（n*n），INFINITE 是为了方便后续算法的使用
    result_arr = [[INFINITE]*n for row in range(n)]

    for i in range(n):
        for j in range(n):
            if i == j:
                result_arr[i][j] = 0  # 对角线设为0

    # 读取图的每条边的数据，获取起始和终止顶点
    for i in range(len(arr)):
        tmp_i = arr[i][0]  # 起始顶点
        tmp_j = arr[i][1]  # 终止顶点
        result_arr[tmp_i][tmp_j] = arr[i][2]  # 填入权值

    # 输出结果
    print("邻接矩阵：")
    for i in range(1, n):
        for j in range(1, n):
            print("%s " % result_arr[i][j], end="\t")
        print()
    return result_arr


# 任意两点间的最短距离
def short_cost_path(matrix, vertex_nums):
    # matrix 邻接矩阵
    # vertex_nums 总顶点数

    # 初始化结果矩阵：即复制传入的初始化的邻接矩阵
    dis = matrix[:]

    # 使用Floyd 算法找出所有顶点间的最短距离
    for k in range(1, vertex_nums+1):
            for i in range(1, vertex_nums+1):
                    for j in range(1, vertex_nums+1):
                        if dis[i][k] + dis[k][j] < dis[i][j]:
                            dis[i][j] = dis[i][k] + dis[k][j]
    return dis


path_cost = [[1,2,12], [2,1,12], [1,6,16], [6,1,16], [1,7,14], [7,1,14], [2,3,10], [2,6,7], \
    [3,2,10], [3,6,6], [3,4,3], [3,5,5], [4,3,3], [4,5,4], [5,3,5], [5,4,4], [5,6,2], [5,7,8], \
    [6,2,7], [6,3,6],[6,5,2], [6,7,9], [7,6,9], [7,5,8]]

matrix = adjacency_matrix(path_cost)
print()
# 搜索各顶点间的最短路径
dis = short_cost_path(matrix, VERT_NUMS)
print("*"*70)
print("顶点间的最短距离：")
print("*"*70)
print("    顶点1    顶点2    顶点3    顶点4    顶点5    顶点6    顶点7")
for i in range(1, SIZE):
    print("顶点%d"%i, end="\t")
    for j in range(1, SIZE):
        print("%d"%dis[i][j], end="\t")
    print()

执行结果：

邻接矩阵：
0       12      99999   99999   99999   16      14
12      0       10      99999   99999   7       99999
99999   10      0       3       5       6       99999
99999   99999   3       0       4       99999   99999
99999   99999   5       4       0       2       8
16      7       6       99999   2       0       9
14      99999   99999   99999   8       9       0

**********************************************************************
顶点间的最短距离：
**********************************************************************
        顶点1   顶点2   顶点3   顶点4   顶点5   顶点6   顶点7
顶点1   0       12      22      22      18      16      14
顶点2   12      0       10      13      9       7       16
顶点3   22      10      0       3       5       6       13
顶点4   22      13      3       0       4       6       12
顶点5   18      9       5       4       0       2       8
顶点6   16      7       6       6       2       0       9
顶点7   14      16      13      12      8       9       0