数据结构与算法（Python）简析

Bertha 。 2022-12-27 09:23 165阅读 0赞

# 1.数据结构与算法（Python） #

# 1.引⼊概念 #

> 引⼊  
> 先来看⼀道题:如果 a+b+c=1000，且 a2+b2=c^2（a,b,c为⾃然数），如何求出所有 a、b、c可能的组合?

## 1.第⼀次尝试 ##

import time
    start_time = time.time()
    # 注意是三重循环
    for a in range(0, 1001):
        for b in range(0, 1001):
    		for c in range(0, 1001):
    			if a**2 + b**2 == c**2 and a+b+c == 1000:
    				print("a, b, c: %d, %d, %d" % (a, b, c))
    end_time = time.time()
    print("elapsed: %f" % (end_time - start_time))
    print("complete!")

运⾏结果：a, b, c: 0, 500, 500a, b, c: 200, 375, 425a, b, c: 375, 200, 425a, b, c: 500, 0, 500elapsed: 214.583347complete!注意运⾏的时间:214.583347秒

## 2.算法的提出 ##

### 1.算法的概念 ###

算法是计算机处理信息的本质，因为计算机程序本质上是⼀个算法来告诉计算机确切的步骤来执⾏⼀个指定的任务。⼀般地，当算法在处理信息时，会从输⼊设备或数据的存储地址读取数据，把结果写⼊输出设备或某个存储地址供以后再调⽤。  
**算法是独⽴存在的⼀种解决问题的⽅法和思想。**  
对于算法⽽⾔，实现的语⾔并不重要，重要的是思想。算法可以有不同的语⾔描述实现版本（如C描述、C++描述、Python描述等），我们现在是在⽤Python语⾔进⾏描述实现。

### 2.算法的五⼤特性 ###

1.  输⼊:算法具有0个或多个输⼊
2.  输出:算法⾄少有1个或多个输出
3.  有穷性:算法在有限的步骤之后会⾃动结束⽽不会⽆限循环，并且每⼀个步骤可以在可接受的时间内完成
4.  确定性：算法中的每⼀步都有确定的含义，不会出现⼆义性
5.  可⾏性：算法的每⼀步都是可⾏的，也就是说每⼀步都能够执⾏有限的次数完成

## 3.第⼆次尝试 ##

import time
    start_time = time.time()
    # 注意是两重循环
    for a in range(0, 1001):
        for b in range(0, 1001-a):
            c = 1000 - a - b
            if a**2 + b**2 == c**2:
                print("a, b, c: %d, %d, %d" % (a, b, c))
    end_time = time.time()
    print("elapsed: %f" % (end_time - start_time))
    print("complete!")

> 运⾏结果：  
> a, b, c: 0, 500, 500  
> a, b, c: 200, 375, 425  
> a, b, c: 375, 200, 425  
> a, b, c: 500, 0, 500  
> elapsed: 0.182897  
> complete!  
> 注意运⾏的时间:0.182897秒

## 4.算法效率衡量 ##

### 1.执⾏时间反应算法效率 ###

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

单靠时间值绝对可信吗？  
假设我们将第⼆次尝试的算法程序运⾏在⼀台配置古⽼性能低下的计算机中，情况会如何？很可能运⾏的时间并不会⽐在我们的电脑中运⾏算法⼀的214.583347秒快多少。  
**单纯依靠运⾏的时间来⽐较算法的优劣并不⼀定是客观准确的！**

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

### 2.时间复杂度与"⼤O记法" ###

我们假定计算机执⾏算法每⼀个基本操作的时间是固定的⼀个时间单位，那么有多少个基本操作就代表会花费多少时间单位。显然对于不同的机器环境⽽⾔，确切的单位时间是不同的，但是对于算法进⾏多少个基本操作（即花费多少时间单位）在规模数量级上却是相同的，由此可以忽略机器环境的影响⽽客观的反应算法的时间效率。  
对于算法的时间效率，我们可以⽤"⼤O记法"来表示。

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

**如何理解"⼤O记法"**  
对于算法进⾏特别具体的细致分析虽然很好，但在实践中的实际价值有限。对于算法的时间性质和空间性质，最重要的是其数量级和趋势，这些是分析算法效率的主要部分。⽽计量算法基本操作数量的规模函数中那些常量因⼦可以忽略不计。例如，可以认为3n2和100n2属于同⼀个量级，如果两个算法处理同样规模实例的代价分别为这两个函数，就认为它们的效率"差不多"，都为n2级。

**最坏时间复杂度**

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

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

对于最优时间复杂度，其价值不⼤，因为它没有提供什么有⽤信息，其反映的只是最乐观最理想的情况，没有参考价值。  
对于最坏时间复杂度，提供了⼀种保证，表明算法在此种程度的基本操作中⼀定能完成⼯作。

对于平均时间复杂度，是对算法的⼀个全⾯评价，因此它完整全⾯的反映了这个算法的性质。但另⼀⽅⾯，这种衡量并没有保证，不是每个计算都能在这个基本操作内完成。⽽且，对于平均情况的计算，也会因为应⽤算法的实例分布可能并不均匀⽽难以计算。  
**因此，我们主要关注算法的最坏情况，亦即最坏时间复杂度。**

### 3.时间复杂度的⼏条基本计算规则 ###

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

### 4.空间复杂度 ###

类似于时间复杂度的讨论，⼀个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。  
**渐近空间复杂度也常常简称为空间复杂度。**  
空间复杂度(SpaceComplexity)是对⼀个算法在运⾏过程中临时占⽤存储空间⼤⼩的量度。  
**算法的时间复杂度和空间复杂度合称为算法的复杂度。**

## 5.算法分析 ##

1.  第⼀次尝试的算法核⼼部分

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

时间复杂度：

*  T(n) = O(n*n*n) = O(n3)

1.  第⼆次尝试的算法核⼼部分

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

时间复杂度：

*  T(n) = O(n*n*(1+1)) = O(n\*n) = O(n2)
 *  由此可⻅，我们尝试的第⼆种算法要⽐第⼀种算法的时间复杂度好多的。

## 6.常⻅时间复杂度 ##

常⻅时间复杂度!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/7ccfa0f94f7557a6e4a58c6c8ce1b2f4.png\#align=left&display=inline&height=379&margin=\[object Object\]&name=image.png&originHeight=379&originWidth=761&size=58233&status=done&style=none&width=761)  
注意，经常将log2n（以2为底的对数）简写成logn

### 常⻅时间复杂度之间的关系 ###

!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/491beb75d306347a93e4137edf49101d.png\#align=left&display=inline&height=565&margin=\[object Object\]&name=image.png&originHeight=565&originWidth=735&size=239597&status=done&style=none&width=735)

> 所消耗的时间从⼩到⼤  
> O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) <O(>  n n n^n nn)

练习：时间复杂度练习(参考算法的效率规则判断 )  
O(5)

> O(2n + 1)

> O(n²+ n + 1)

> O(3n³+1)

## 7.Python内置类型性能分析 ##

### 1.timeit模块 ###

timeit模块可以⽤来测试⼀⼩段Python代码的执⾏速度。  
class timeit.Timer(stmt=‘pass’, setup=‘pass’, timer=)

Timer是测量⼩段代码执⾏速度的类。  
stmt参数是要测试的代码语句（statment）；  
setup参数是运⾏代码时需要的设置；  
timer参数是⼀个定时器函数，与平台有关。  
timeit.Timer.timeit(number=1000000)  
Timer类中测试语句执⾏速度的对象⽅法。number参数是测试代码时的测试次数，默认为1000000次。⽅法返回执⾏代码的平均耗时，⼀个float类型的秒数。

list的操作测试

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))
    from timeit import Timer
    timer1 = Timer("t1()", "from __main__ import t1")
    print("concat ",timer1.timeit(number=1000), "seconds")
    timer2 = Timer("t2()", "from __main__ import t2")
    print("append ",timer2.timeit(number=1000), "seconds")
    timer3 = Timer("t3()", "from __main__ import t3")
    print("comprehension ",timer3.timeit(number=1000), "seconds")
    timer4 = Timer("t4()", "from __main__ import t4")
    print("list range ",timer4.timeit(number=1000), "seconds")
    # ('concat ', 1.7890608310699463, 'seconds')
    # ('append ', 0.13796091079711914, 'seconds')
    # ('comprehension ', 0.05671119689941406, 'seconds')
    # ('list range ', 0.014147043228149414, 'seconds')

pop操作测试

x = range(2000000)
    pop_zero = Timer("x.pop(0)","from __main__ import x")
    print("pop_zero ",pop_zero.timeit(number=1000), "seconds")
    x = range(2000000)
    pop_end = Timer("x.pop()","from __main__ import x")
    print("pop_end ",pop_end.timeit(number=1000), "seconds")
    # ('pop_zero ', 1.9101738929748535, 'seconds')
    # ('pop_end ', 0.00023603439331054688, 'seconds')

测试pop操作：从结果可以看出，pop最后⼀个元素的效率远远⾼于pop第⼀个元素

> 可以⾃⾏尝试下list的append(value)和insert(0,value),即⼀个后⾯插⼊和⼀个前⾯插⼊？？？

list内置操作的时间复杂度  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/ccce50ac68900329f34308306718ae07.png\#align=left&display=inline&height=700&margin=\[object Object\]&name=image.png&originHeight=700&originWidth=659&size=371480&status=done&style=none&width=659)  
dict内置操作的时间复杂度  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/817d7d55701be928e4031e2c78dc4bad.png\#align=left&display=inline&height=386&margin=\[object Object\]&name=image.png&originHeight=386&originWidth=746&size=181941&status=done&style=none&width=746)

## 8.数据结构 ##

> 我们如何⽤Python中的类型来保存⼀个班的学⽣信息？如果想要快速的通过学⽣姓名获取其信息呢？

实际上当我们在思考这个问题的时候，我们已经⽤到了数据结构。列表和字典都可以存储⼀个班的学⽣信息，但是想要在列表中获取⼀名同学的信息时，就要遍历这个列表，其时间复杂度为O(n)，⽽使⽤字典存储时，可将学⽣姓名作为字典的键，学⽣信息作为值，进⽽查询时不需要遍历便可快速获取到学⽣信息，其时间复杂度为O(1)。  
我们为了解决问题，需要将数据保存下来，然后根据数据的存储⽅式来设计算法实现进⾏处理，那么数据的存储⽅式不同就会导致需要不同的算法进⾏处理。我们希望算法解决问题的效率越快越好，于是我们就需要考虑数据究竟如何保存的问题，这就是数据结构。  
在上⾯的问题中我们可以选择Python中的列表或字典来存储学⽣信息。列表和字典就是Python内建帮我们封装好的两种数据结构。

### 1.概念 ###

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

Python给我们提供了很多现成的数据结构类型，这些系统⾃⼰定义好的，不需要我们⾃⼰去定义的数据结构叫做Python的内置数据结构，⽐如列表、元组、字典。⽽有些数据组织⽅式，Python系统⾥⾯没有直接定义，需要我们⾃⼰去定义实现这些数据的组织⽅式，这些数据组织⽅式称之为Python的扩展数据结构，⽐如栈，队列等。

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

*  数据结构只是静态的描述了数据元素之间的关系。
 *  ⾼效的程序需要在数据结构的基础上设计和选择算法。
 *  **程序 =数据结构 +算法**
 *  **总结：算法是为了解决实际问题⽽设计的，数据结构是算法需要处理的问题载体**

### 3.抽象数据类型(Abstract Data Type) ###

抽象数据类型(ADT)的含义是指⼀个数学模型以及定义在此数学模型上的⼀组操作。即把数据类型和数据类型上的运算捆在⼀起，进⾏封装。引⼊抽象数据类型的⽬的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引⽤隔开，使它们相互独⽴。  
最常⽤的数据运算有五种：

*  插⼊
 *  删除
 *  修改
 *  查找
 *  排序

# 2.顺序表 #

在程序中，经常需要将⼀组（通常是同为某个类型的）数据元素作为整体管理和使⽤，需要创建这种元素组，⽤变量记录它们，传进传出函数等。⼀组数据中包含的元素个数可能发⽣变化（可以增加或删除元素）。  
对于这种需求，最简单的解决⽅案便是将这样⼀组元素看成⼀个序列，⽤元素在序列⾥的位置和顺序，表示实际应⽤中的某种有意义的信息，或者表示数据之间的某种关系。

这样的⼀组序列元素的组织形式，我们可以将其抽象为线性表。⼀个线性表是某类元素的⼀个集合，还记录着元素之间的⼀种顺序关系。线性表是最基本的数据结构之⼀，在实际程序中应⽤⾮常⼴泛，它还经常被⽤作更复杂的数据结构的实现基础。

根据线性表的实际存储⽅式，分为两种实现模型：

*  顺序表，将元素顺序地存放在⼀块连续的存储区⾥，元素间的顺序关系由它们的存储顺序⾃然表示。
 *  链表，将元素存放在通过链接构造起来的⼀系列存储块中。

## 1.顺序表的形式 ##

### 1.顺序表的基本形式 ###

!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/c25663d1fd98d478341b43469b6df215.png\#align=left&display=inline&height=330&margin=\[object Object\]&name=image.png&originHeight=330&originWidth=735&size=96839&status=done&style=none&width=735)  
图a表示的是顺序表的基本形式，数据元素本身连续存储，每个元素所占的存储单元⼤⼩固定相同，元素的下标是其逻辑地址，⽽元素存储的物理地址（实际内存地址）可以通过存储区的起始地址Loc (e0)加上逻辑地址（第i个元素）与存储单元⼤⼩（c）的乘积计算⽽得，即：  
**Loc(ei) = Loc(e0) + c\*i**  
故，访问指定元素时⽆需从头遍历，通过计算便可获得对应地址，其时间复杂度为O(1)。  
如果元素的⼤⼩不统⼀，则须采⽤图b的元素外置的形式，将实际数据元素另⾏存储，⽽顺序表中各单元位置保存对应元素的地址信息（即链接）。由于每个链接所需的存储量相同，通过上述公式，可以计算出元素链接的存储位置，⽽后顺着链接找到实际存储的数据元素。注意，图b中的c不再是数据元素的⼤⼩，⽽是存储⼀个链接地址所需的存储量，这个量通常很⼩。

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

## 2.顺序表的结构与实现 ##

顺序表的结构  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/9da5234f0bf7722ed92e90b87e3d6530.png\#align=left&display=inline&height=393&margin=\[object Object\]&name=image.png&originHeight=393&originWidth=270&size=46652&status=done&style=none&width=270)  
⼀个顺序表的完整信息包括两部分，⼀部分是表中的元素集合，另⼀部分是为实现正确操作⽽需记录的信息，即有关表的整体情况的信息，这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。

顺序表的两种基本实现⽅式  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/0e0de40a18d2a2edc698444f062c74be.png\#align=left&display=inline&height=192&margin=\[object Object\]&name=image.png&originHeight=192&originWidth=752&size=55458&status=done&style=none&width=752)  
图a为⼀体式结构，存储表信息的单元与元素存储区以连续的⽅式安排在⼀块存储区⾥，两部分数据的整体形成⼀个完整的顺序表对象。  
⼀体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的⼀部分，顺序表创建后，元素存储区就固定了。  
图b为分离式结构，表对象⾥只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另⼀个独⽴的元素存储区⾥，通过链接与基本表对象关联。

### 3.元素存储区替换 ###

⼀体式结构由于顺序表信息区与数据区连续存储在⼀起，所以若想更换数据区，则只能整体搬迁，即整个顺序表对象（指存储顺序表的结构信息的区域）改变了。  
分离式结构若想更换数据区，只需将表信息区中的数据区链接地址更新即可，⽽该顺序表对象不变。

### 4.元素存储区扩充 ###

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

扩充的两种策略

*  每次扩充增加固定数⽬的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增⻓。
    
     *  特点：节省空间，但是扩充操作频繁，操作次数多。
 *  每次扩充容量加倍，如每次扩充增加⼀倍存储空间。
    
     *  特点：减少了扩充操作的执⾏次数，但可能会浪费空间资源。以空间换时间，推荐的⽅式。

## 3.顺序表的操作 ##

### 1.增加元素 ###

如图所示，为顺序表增加新元素111的三种⽅式  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/6733ca1dee07fe54060a00deb2d413cd.png\#align=left&display=inline&height=408&margin=\[object Object\]&name=image.png&originHeight=408&originWidth=808&size=173090&status=done&style=none&width=808)  
a.尾端加⼊元素，时间复杂度为O(1)  
b.⾮保序的加⼊元素（不常⻅），时间复杂度为O(1)  
c.保序的元素加⼊，时间复杂度为O(n)

### 2.删除元素 ###

!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/c354401887780328a7d76bf5a83d07cd.png\#align=left&display=inline&height=360&margin=\[object Object\]&name=image.png&originHeight=360&originWidth=700&size=131003&status=done&style=none&width=700)  
a.删除表尾元素，时间复杂度为O(1)  
b.⾮保序的元素删除（不常⻅），时间复杂度为O(1)  
c.保序的元素删除，时间复杂度为O(n)

## 4.Python中的顺序表 ##

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

tuple是不可变类型，即不变的顺序表，因此不⽀持改变其内部状态的任何操作，⽽其他⽅⾯，则与list的性质类似。

### 1.list的基本实现技术 ###

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

*  基于下标（位置）的⾼效元素访问和更新，时间复杂度应该是O(1)；为满⾜该特征，应该采⽤顺序表技术，表中元素保存在⼀块连续的存储区中。
 *  允许任意加⼊元素，⽽且在不断加⼊元素的过程中，表对象的标识（函数id得到的值）不变。

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

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

> 《数据结构与算法 Python语⾔描述》裘宗燕著

> 在Python的官⽅实现中，list实现采⽤了如下的策略：在建⽴空表（或者很⼩的表）时，系统分配⼀块能容纳8个元素的存储区；在执⾏插⼊操作（insert或append）时，如果元素存储区满就换⼀块4倍⼤的存储区。但如果此时的表已经很⼤（⽬前的阀值为50000），则改变策略，  
> 采⽤加⼀倍的⽅法。引⼊这种改变策略的⽅式，是为了避免出现过多空闲的存储位置。

在Python的官⽅实现中，list实现采⽤了如下的策略：

/* This over-allocates proportional to the list size, mak
    ing room
         * for additional growth.  The over-allocation is mild, b
    ut is
         * enough to give linear-time amortized behavior over a l
    ong
         * sequence of appends() in the presence of a poorly-perf
    orming
         * system realloc().
         * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 7
    2, 88, ...
    */
        new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
        /* check for integer overflow */
        if (new_allocated > PY_SIZE_MAX - newsize) { 
            PyErr_NoMemory();
            return -1;
        } else { 
            new_allocated += newsize;
    }

# 3.链表 #

### 1.为什么需要链表 ###

顺序表的构建需要预先知道数据⼤⼩来申请连续的存储空间，⽽在进⾏扩充时⼜需要进⾏数据的搬迁，所以使⽤起来并不是很灵活。链表结构可以充分利⽤计算机内存空间，实现灵活的内存动态管理。

### 2.链表的定义 ###

链表（Linked list）是⼀种常⻅的基础数据结构，是⼀种线性表，但是不像顺序表⼀样连续存储数据，⽽是在每⼀个节点（数据存储单元）⾥存放下⼀个节点的位置信息（即地址）。  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/92ebd70681a53afd14b03ca770917094.png\#align=left&display=inline&height=119&margin=\[object Object\]&name=image.png&originHeight=119&originWidth=670&size=33148&status=done&style=none&width=670)

## 1.单向链表 ##

单向链表也叫单链表，是链表中最简单的⼀种形式，它的每个节点包含两个域，⼀个信息域（元素域）和⼀个链接域。这个链接指向链表中的下⼀个节点，⽽最后⼀个节点的链接域则指向⼀个空值。  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/294e384c79a9110fdfb6132195a1c9eb.png\#align=left&display=inline&height=165&margin=\[object Object\]&name=image.png&originHeight=165&originWidth=656&size=40004&status=done&style=none&width=656)

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

**节点实现**

class SingleNode(object): 
        """单链表的结点"""
        def __init__(self,item):
            # item存放数据元素 
            self.item = item
            # next是下一个节点的标识
            self.next = None

**单链表的操作**

*  is\_empty()链表是否为空
 *  length()链表⻓度
 *  travel()遍历整个链表
 *  add(item)链表头部添加元素
 *  append(item)链表尾部添加元素
 *  insert(pos, item)指定位置添加元素
 *  remove(item)删除节点
 *  search(item)查找节点是否存在

**单链表的实现**

class SingleLinkList(object):
        """单链表"""
        def __init__(self):
            self.__head = None
    
        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 = self.__head
            while cur != None:
                print(cur.item)
                cur = cur.next
            print("")

**头部添加元素**  
**!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/30437710868d3f33b3740d2c6007f46b.png\#align=left&display=inline&height=144&margin=\[object Object\]&name=image.png&originHeight=144&originWidth=498&size=22279&status=done&style=none&width=498)**

def add(self, item):
            """头部添加元素"""
            # 先创建一个保存item值的节点
            node = SingleNode(item)
            # 将新节点的链接域next指向头节点，即_head指向的位置 
            node.next = self.__head
            # 将链表的头_head指向新节点
            self.__head = node

**尾部添加元素**

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

**指定位置添加元素**  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/be9f985ffa44459ac9371a4a2086420b.png\#align=left&display=inline&height=143&margin=\[object Object\]&name=image.png&originHeight=143&originWidth=570&size=24359&status=done&style=none&width=570)

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

**删除节点**

!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/769216bd10cbc56eab6e32862cdf06d6.png\#align=left&display=inline&height=123&margin=\[object Object\]&name=image.png&originHeight=123&originWidth=479&size=22492&status=done&style=none&width=479)

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 search(self,item):
            """链表查找节点是否存在，并返回True或者False"""
            cur = self.__head
            while cur != None:
                if cur.item == item:
                    return True
                cur = cur.next
            return False

测试

if __name__ == "__main__":
        ll = SingleLinkList()
        ll.add(1)
        ll.add(2)
        ll.append(3)
        ll.insert(2, 4)
        print("length:",ll.length())
        ll.travel()
        print(ll.search(3))
        print(ll.search(5))
        ll.remove(1)
        print("length:",ll.length())
        ll.travel()

### 链表与顺序表的对⽐ ###

链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空间开销⽐较⼤，但对存储空间的使⽤要相对灵活。  
链表与顺序表的各种操作复杂度如下所示：  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/f437aedfb40a465b178576861c98978d.png\#align=left&display=inline&height=206&margin=\[object Object\]&name=image.png&originHeight=206&originWidth=641&size=30523&status=done&style=none&width=641)  
注意虽然表⾯看起来复杂度都是 O(n)，但是链表和顺序表在插⼊和删除时进⾏的是完全不同的操作。链表的主要耗时操作是遍历查找，删除和插⼊操作本身的复杂度是O(1)。顺序表查找很快，主要耗时的操作是拷⻉覆盖。因为除了⽬标元素在尾部的特殊情况，顺序表进⾏插⼊和删除时需要对操作点之后的所有元素进⾏前后移位操作，只能通过拷⻉和覆盖的⽅法进⾏。

## 2.双向链表 ##

⼀种更复杂的链表是"双向链表"或"双⾯链表"。每个节点有两个链接：⼀个指向前⼀个节点，当此节点为第⼀个节点时，指向空值；⽽另⼀个指向下⼀个节点，当此节点为最后⼀个节点时，指向空值。  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/fb90ab2690a4d3e0b51bebaae3ed7f61.png\#align=left&display=inline&height=156&margin=\[object Object\]&name=image.png&originHeight=156&originWidth=625&size=25689&status=done&style=none&width=625)

### 1.操作 ###

*  is\_empty()链表是否为空
 *  length()链表⻓度
 *  travel()遍历链表
 *  add(item)链表头部添加
 *  append(item)链表尾部添加
 *  insert(pos, item)指定位置添加
 *  remove(item)删除节点
 *  search(item)查找节点是否存在

### 2.实现 ###

class Node(object):
        """双向链表节点"""
        def __init__(self, item):
            self.item = item
            self.next = None
            self.prev = None
    
    
    class DLinkList(object):
        """双向链表"""
        def __init__(self):
            self.__head = None
    
        def is_empty(self):
            """判断链表是否为空"""
            return self.__head == None
    
        def length(self):
            """返回链表的⻓度"""
            cur = self.__head
            count = 0
            while cur != None:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            """遍历链表"""
            cur = self.__head
            while cur != None:
                print(cur.item)
                cur = cur.next
            print("")
    
        def add(self, item):
            """头部插入元素"""
            node = Node(item)
            if self.is_empty():
                # 如果是空链表，将_head指向node
                self.__head = node
            else:
                # 将node的next指向_head的头节点 
                node.next = self.__head
                # 将_head的头节点的prev指向node
                self.__head.prev = node
                # 将_head 指向node 
                self.__head = node
    
        def append(self, item):
            """尾部插入元素"""
            node = Node(item)
            if self.is_empty():
                # 如果是空链表，将_head指向node
                self.__head = node
            else:
                # 移动到链表尾部
                cur = self.__head
                while cur.next != None:
                    cur = cur.next
                # 将尾节点cur的next指向node 
                cur.next = node
                # 将node的prev指向cur 
                node.prev = cur
        
        def search(self, item):
            """查找元素是否存在"""
            cur = self.__head
            while cur != None:
                if cur.item == item:
                    return True
                cur = cur.next
            return False

**指定位置插⼊节点**  
**!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/e3b732aee86f7da02150a651307b0a68.png\#align=left&display=inline&height=252&margin=\[object Object\]&name=image.png&originHeight=252&originWidth=471&size=58070&status=done&style=none&width=471)**

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
            count = 0
            # 移动到指定位置的前一个位置 
            while count < (pos-1):
                count += 1
                cur = cur.next
            # 将node的prev指向cur
            node.prev = cur
            # 将node的next指向cur的下一个节点 
            node.next = cur.next
            # 将cur的下一个节点的prev指向node 
            cur.next.prev = node
            # 将cur的next指向node
            cur.next = node

**删除元素**  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/ca0c78038ecfcc602ff9978b606df3d8.png\#align=left&display=inline&height=152&margin=\[object Object\]&name=image.png&originHeight=152&originWidth=542&size=30162&status=done&style=none&width=542)

def remove(self, item):
            """删除元素"""
            cur = self.__head
            while cur != None:
                # 找到了要删除的元素
                if cur.item == item:
                    # 先判断此结点是否是头节点
                    # 头节点
                    if cur == self.__head:
                        self.__head = cur.next
                        # 如果存在下一个结点，则设置下一个结点 
                        if cur.next:
                            # 判断链表是否只有一个结点 
                            cur.next.prev = None
                    else:
                        cur.prev.next = cur.next
                        # 如果存在下一个结点，则设置下一个结点 
                        if cur.next:
                            cur.next.prev = cur.prev
                    break
                else:
                    cur = cur.next

测试

if __name__ == "__main__":
        ll = DLinkList()
        ll.add(1)
        ll.add(2)
        ll.append(3)
        ll.insert(2, 4)
        ll.insert(4, 5)
        ll.insert(0, 6)
        print("length:",ll.length())
        ll.travel()
        print(ll.search(3))
        print(ll.search(4))
        ll.remove(1)
        print("length:",ll.length())
        ll.travel()

## 3.单向循环链表 ##

!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/dd5a2e3780214c64b5e99f9180f07c38.png\#align=left&display=inline&height=106&margin=\[object Object\]&name=image.png&originHeight=106&originWidth=445&size=24421&status=done&style=none&width=445)

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

### 1.操作 ###

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

### 2.实现 ###

class Node(object):
        """节点"""
    
        def __init__(self, item):
            self.item = item
            self.next = None
    
    
    class SinCycLinkedlist(object):
        """单向循环链表"""
    
        def __init__(self):
            self.__head = None
    
        def is_empty(self):
            """判断链表是否为空"""
            return self.__head == None
    
        def length(self):
            """返回链表的⻓度"""
            # 如果链表为空，返回⻓度0 
            if self.is_empty():
                return 0
            count = 1
            cur = self.__head
            while cur.next != self.__head:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            """遍历链表"""
            if self.is_empty():
                return
            cur = self.__head
            print(cur.item)
            while cur.next != self.__head:
                cur = cur.next
                print(cur.item)
            print("")
    
        def add(self, item):
            """头部添加节点"""
            node = Node(item)
            if self.is_empty():
                self.__head = node
                node.next = self.__head
            else:
                # 添加的节点指向_head 
                node.next = self.__head
                # 移到链表尾部，将尾部节点的next指向node 
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                cur.next = node
            # _head指向添加node的 
            self.__head = node
    
        def append(self, item):
            """尾部添加节点"""
            node = Node(item)
            if self.is_empty():
                self.__head = node
                node.next = self.__head
            else:
                # 移到链表尾部
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                # 将尾节点指向node 
                cur.next = node
                # 将node指向头节点_head 
                node.next = self.__head
    
        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
                count = 0
                # 移动到指定位置的前一个位置 
                while count < (pos - 1):
                    count += 1
                    cur = cur.next
                node.next = cur.next
                cur.next = node
    
        def remove(self, item):
            """删除一个节点"""
            # 若链表为空，则直接返回 
            if self.is_empty():
                return
            # 将cur指向头节点
            cur = self.__head
            pre = None
            while cur.next != self.__head:
                if cur.item == item:
                    # 先判断此结点是否是头节点 
                    if cur == self.__head:
                        # 头节点的情况
                        # 找尾节点
                        rear = self.__head
                        while rear.next != self.__head:
                            rear = rear.next
                        self.__head = cur.next
                        rear.next = self.__head
                    else:
                        # 中间节点
                        pre.next = cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next
                    # 退出循环，cur指向尾节点 if cur.item == item:
                    if cur == self.__head:
                        # 链表只有一个节点
                        self.__head = None
                    else:
                        # pre.next = cur.next
                        pre.next = self.__head
    
        def search(self, item):
            """查找节点是否存在"""
            if self.is_empty():
                return False
            cur = self.__head
            if cur.item == item:
                return True
            while cur.next != self.__head:
                cur = cur.next
                if cur.item == item:
                    return True
            return False
    
    
    if __name__ == "__main__":
        ll = SinCycLinkedlist()
        ll.add(1)
        ll.add(2)
        ll.append(3)
        ll.insert(2, 4)
        ll.insert(4, 5)
        ll.insert(0, 6)
        print("length:", ll.length())
        ll.travel()
        print(ll.search(3))
        print(ll.search(7))
        ll.remove(1)
        print("length:", ll.length())
        ll.travel()

# 4.栈 #

栈（stack），有些地⽅称为堆栈，是⼀种容器，可存⼊数据元素、访问元素、删除元素，它的特点在于只能允许在容器的⼀端（称为栈顶端指标，英语：top）进⾏加⼊数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存⼊的那个元素，确定了⼀种默认的访问顺序。  
由于栈数据结构只允许在⼀端进⾏操作，因⽽按照后进先出（LIFO, Last In First Out）的原理运作。  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/e3faf4b727b85ba7836920e167d7d216.png\#align=left&display=inline&height=407&margin=\[object Object\]&name=image.png&originHeight=407&originWidth=401&size=39347&status=done&style=none&width=401)

## 1.栈结构实现 ##

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

### 1.栈的操作 ###

*  Stack()创建⼀个新的空栈
 *  push(item)添加⼀个新的元素item到栈顶
 *  pop()弹出栈顶元素
 *  peek()返回栈顶元素
 *  is\_empty()判断栈是否为空
 *  size()返回栈的元素个数

class Stack(object):
        """栈"""
        def __init__(self):
            self.items = []
    
        def is_empty(self): 
            """判断是否为空"""
            return self.items == []
        
        def push(self, item):
            """加入元素"""
            self.items.append(item)
    
        def pop(self): 
            """弹出元素"""
            return self.items.pop()
    
        def peek(self):
            """返回栈顶元素"""
            return self.items[len(self.items) - 1]
    
        def size(self): 
            """返回栈的大小"""
            return len(self.items)
    if __name__ == "__main__":
        stack = Stack()
        stack.push("hello")
        stack.push("world")
        stack.push("itcast")
        print(stack.size())
        print(stack.peek())
        print(stack.pop())
        print(stack.pop())
        print(stack.pop())

# !\[image.png\](https://img-blog.csdnimg.cn/img\_convert/3ac738b4836bee6509f80332e5efc06b.png\#align=left&display=inline&height=370&margin=\[object Object\]&name=image.png&originHeight=370&originWidth=630&size=99191&status=done&style=none&width=630) #

# 5.队列 #

队列（queue）是只允许在⼀端进⾏插⼊操作，⽽在另⼀端进⾏删除操作的线性表。  
队列是⼀种先进先出的（First In First Out）的线性表，简称FIFO。允许插⼊的⼀端为队尾，允许删除的⼀端为队头。队列不允许在中间部位进⾏操作！

假设队列是q=（a1，a2，…，an），那么a1就是队头元素，⽽an是队尾元素。这样我们就可以删除时，总是从a1开始，⽽插⼊时，总是在队列最后。这也⽐较符合我们通常⽣活中的习惯，排在第⼀个的优先出列，最后来的当然排在队伍最后。  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/51791ed64fe6e1fabc92d927d124e239.png\#align=left&display=inline&height=418&margin=\[object Object\]&name=image.png&originHeight=418&originWidth=593&size=152533&status=done&style=none&width=593)

## 1.队列的实现 ##

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

### 1.操作 ###

*  Queue()创建⼀个空的队列
 *  enqueue(item)往队列中添加⼀个item元素
 *  dequeue()从队列头部删除⼀个元素
 *  is\_empty()判断⼀个队列是否为空
 *  size()返回队列的⼤⼩

class Queue(object):
        """队列"""
        def __init__(self):
            self.items = []
    
        def is_empty(self):
            return self.items == []
    
        def enqueue(self, item):
            """进队列"""
            self.items.insert(0, item)
    
        def dequeue(self):
            """出队列"""
            return self.items.pop()
    
        def size(self):
            """返回大小"""
            return len(self.items)
    
    if __name__ == "__main__":
        q = Queue()
        q.enqueue("hello")
        q.enqueue("world")
        q.enqueue("itcast")
        print(q.size())
        print(q.dequeue())
        print(q.dequeue())
        print(q.dequeue())

## 2.双端队列 ##

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

双端队列中的元素可以从两端弹出，其限定插⼊和删除操作在表的两端进⾏。双端队列可以在队列任意⼀端⼊队和出队。  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/f5c4c74c5ade3fbe665726d2e5e58ec4.png\#align=left&display=inline&height=160&margin=\[object Object\]&name=image.png&originHeight=160&originWidth=601&size=54280&status=done&style=none&width=601)  
操作

*  Deque()创建⼀个空的双端队列
 *  add\_front(item)从队头加⼊⼀个item元素
 *  add\_rear(item)从队尾加⼊⼀个item元素
 *  remove\_front()从队头删除⼀个item元素
 *  remove\_rear()从队尾删除⼀个item元素
 *  is\_empty()判断双端队列是否为空
 *  size()返回队列的⼤⼩

实现

class Deque(object): 
        """双端队列"""
        def __init__(self):
            self.items = []
    
        def is_empty(self): 
            """判断队列是否为空"""
            return self.items == [] 
        
        def add_front(self, item): 
            """在队头添加元素"""
            self.items.insert(0, item)
        
        def add_rear(self, item): 
            """在队尾添加元素"""
            self.items.append(item)
        
        def remove_front(self): 
            """从队头删除元素"""
            return self.items.pop(0)
        
        def remove_rear(self): 
            """从队尾删除元素"""
            return self.items.pop()
    
        def size(self): 
            """返回队列大小"""
            return len(self.items)
        
    if __name__ == "__main__":
        deque = Deque()
        deque.add_front(1)
        deque.add_front(2)
        deque.add_rear(3)
        deque.add_rear(4)
        print(deque.size())
        print(deque.remove_front())
        print(deque.remove_front())
        print(deque.remove_rear())
        print(deque.remove_rear())

# 6.排序与搜索 #

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

*  **排序算法的稳定性**

**稳定性**：稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果⼀个排序算法是稳定的，当有两个相等键值的纪录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)（次序被改变）

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。作这件事情的⼀个⽅式是⼈⼯扩充键值的⽐较，如此在其他⽅⾯相同键值的两个对象间之⽐较，（⽐如上⾯的⽐较中加⼊第⼆个标准：第⼆个键值的⼤⼩）就会被决定使⽤在原先数据次序中的条⽬，当作⼀个同分决赛。然⽽，要记住这种次序通常牵涉到额外的空间负担。

## 1.冒泡排序 ##

冒泡排序（英语：Bubble Sort）是⼀种简单的排序算法。它重复地遍历要排序的数列，⼀次⽐较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的⼯作是重复地进⾏直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越⼩的元素会经由交换慢慢"浮"到数列的顶端。

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

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

冒泡排序的分析

交换过程图示(第⼀次)：  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/8c907e24993aaf66d6266d3ff8256583.png\#align=left&display=inline&height=585&margin=\[object Object\]&name=image.png&originHeight=585&originWidth=631&size=214190&status=done&style=none&width=631)

那么我们需要进⾏n-1次冒泡过程，每次对应的⽐较次数如下图所示：  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/56a130a589509864805f5a9f8ba0e388.png\#align=left&display=inline&height=216&margin=\[object Object\]&name=image.png&originHeight=216&originWidth=659&size=30534&status=done&style=none&width=659)

def bubble_sort(alist):
        for j in range(len(alist) - 1, 0, -1):
            # j表示每次遍历需要比较的次数，是逐渐减小的
            for i in range(j):
                if alist[i] > alist[i + 1]:
                    alist[i], alist[i + 1] = alist[i + 1], alist[i]
    li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    bubble_sort(li)
    print(li)

**时间复杂度**

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

## 2.选择排序 ##

选择排序（Selection sort）是⼀种简单直观的排序算法。它的⼯作原理如下。⾸先在未排序序列中找到最⼩（⼤）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最⼩（⼤）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换⼀对元素，它们当中⾄少有⼀个将被移到其最终位置上，因此对n个元素的表进⾏排序总共进⾏⾄多n-1次交换。在所有的完全依靠交换去移动元素的排序⽅法中，选择排序属于⾮常好的⼀种。

选择排序分析  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/3b773b6d412e9941feed70c1793ae6a5.png\#align=left&display=inline&height=640&margin=\[object Object\]&name=image.png&originHeight=640&originWidth=635&size=203676&status=done&style=none&width=635)

def selection_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]
    
    selection_sort(alist)
    print(alist)

时间复杂度

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

## 3.插⼊排序 ##

插⼊排序（英语：Insertion Sort）是⼀种简单直观的排序算法。它的⼯作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插⼊。插⼊排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插⼊空间。  
插⼊排序分析  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/4ac6b336578b496e5375e939194a1511.png\#align=left&display=inline&height=250&margin=\[object Object\]&name=image.png&originHeight=250&originWidth=648&size=102243&status=done&style=none&width=648)

def insert_sort(alist):
        # 从第二个位置，即下标为1的元素开始向前插入
        for i in range(1, len(alist)):
        # 从第i个元素开始向前比较，如果小于前一个元素，交换位置
            for j in range(i, 0, -1):
                if alist[j] < alist[j - 1]:
                    alist[j], alist[j - 1] = alist[j - 1], alist[j]
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    insert_sort(alist)
    print(alist)

时间复杂度

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

## 4.快速排序 ##

快速排序（英语：Quicksort），⼜称划分交换排序（partition-exchangesort），通过⼀趟排序将要排序的数据分割成独⽴的两部分，其中⼀部分的所有数据都⽐另外⼀部分的所有数据都要⼩，然后再按此⽅法对这两部分数据分别进⾏快速排序，整个排序过程可以递归进⾏，以此达到整个数据变成有序序列。

步骤为：

1.  从数列中挑出⼀个元素，称为"基准"（pivot），
2.  重新排序数列，所有元素⽐基准值⼩的摆放在基准前⾯，所有元素⽐基准值⼤的摆在基准的后⾯（相同的数可以到任⼀边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3.  递归地（recursive）把⼩于基准值元素的⼦数列和⼤于基准值元素的⼦数列排序。

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

快速排序的分析  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/113964a1f03edee6b86e5e032c049921.png\#align=left&display=inline&height=714&margin=\[object Object\]&name=image.png&originHeight=714&originWidth=620&size=164878&status=done&style=none&width=620)

def quick_sort(alist, start, end):
        """快速排序"""
        # 递归的退出条件
        if start >= end:
            return
        # 设定起始元素为要寻找位置的基准元素
        mid = alist[start]
        # low为序列左边的由左向右移动的游标
        low = start
        # high为序列右边的由右向左移动的游标
        high = end
        while low < high:
        # 如果low与high未重合，high指向的元素不比基准元素小，则high向
            while low < high and alist[high] >= mid:
                high -= 1
                # 将high指向的元素放到low的位置上
            alist[low] = alist[high]
            # 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
            while low < high and alist[low] < mid:
                low += 1
                # 将low指向的元素放到high的位置上
            alist[high] = alist[low]
        # 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
        # 将基准元素放到该位置
        alist[low] = mid
        # 对基准元素左边的子序列进行快速排序
        quick_sort(alist, start, low-1)
        # 对基准元素右边的子序列进行快速排序
        quick_sort(alist, low+1, end)
    
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    quick_sort(alist, 0, len(alist) - 1)
    print(alist)

时间复杂度

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

从⼀开始快速排序平均需要花费O(n log n)时间的描述并不明显。但是不难观察到的是分区运算，数组的元素都会在每次循环中⾛访过⼀次，使⽤O(n)的时间。在使⽤结合（concatenation）的版本中，这项运算也是O(n)。在最好的情况，每次我们运⾏⼀次分区，我们会把⼀个数列分为两个⼏近相等的⽚段。这个意思就是每次递归调⽤处理⼀半⼤⼩的数列。因此，在到达⼤⼩为⼀的数列前，我们只要作log n次嵌套的调⽤。这个意思就是调⽤树的深度是O(log n)。但是在同⼀层次结构的两个程序调⽤中，不会处理到原来数列的相同部分；因此，程序调⽤的每⼀层次结构总共全部仅需要O(n)的时间（每个调⽤有某些共同的额外耗费，但是因为在每⼀层次结构仅仅只有O(n)个调⽤，这些被归纳在O(n)系数中）。结果是这个算法仅需使⽤O(n log n)时间。

## 6.希尔排序 ##

希尔排序(Shell Sort)是插⼊排序的⼀种。也称缩⼩增量排序，是直接插⼊排序算法的⼀种更⾼效的改进版本。希尔排序是⾮稳定排序算法。该⽅法因DL．Shell于1959年提出⽽得名。希尔排序是把记录按下标的⼀定增量分组，对每组使⽤直接插⼊排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减⾄1时，整个⽂件恰被分成⼀组，算法便终⽌。  
\*\*  
**希尔排序过程**

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

例如，假设有这样⼀组数\[ 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步⻓进⾏排序（此时就是简单的插⼊排序了）

希尔排序的分析  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/a88d1769b33c92a5babbe1f5702548d0.png\#align=left&display=inline&height=916&margin=\[object Object\]&name=image.png&originHeight=916&originWidth=972&size=645905&status=done&style=none&width=972)

希尔排序

def shell_sort(alist):
        n = len(alist)
        # 初始步⻓
        gap = n / 2
        while gap > 0:
            # 按步⻓进行插入排序
            for i in range(gap, n):
                j = i
                # 插入排序
                while j >= gap and alist[j - gap] > alist[j]:
                    alist[j - gap], alist[j] = alist[j], alist[j - gap]
                    j -= gap
            # 得到新的步⻓
            gap = gap / 2
    
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20, 11]
    shell_sort(alist)
    print(alist)

时间复杂度

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

## 7.归并排序 ##

归并排序是采⽤分治法的⼀个⾮常典型的应⽤。归并排序的思想就是先递归分解数组，再合并数组。  
将数组分解最⼩之后，然后合并两个有序数组，基本思路是⽐较两个数组的最前⾯的数，谁⼩就先取谁，取了后相应的指针就往后移⼀位。然后再⽐较，直⾄⼀个数组为空，最后把另⼀个数组的剩余部分复制过来即可。

归并排序的分析

def merge_sort(alist):
        if len(alist) <= 1:
            return alist
        # 二分分解
        num = int(len(alist) / 2)
        left = merge_sort(alist[:num])
        right = merge_sort(alist[num:])
        # 合并
        return merge(left, right)
    
    
    def merge(left, right):
        '''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组'''
        # left与right的下标指针
        l, r = 0, 0
        result = []
        while l<len(left) and r<len(right):
            if left[l] < right[r]:
                result.append(left[l])
                l += 1
            else:
                result.append(right[r])
                r += 1
        result += left[l:]
        result += right[r:]
        return result
    
    alist = [54,26,93,17,77,31,44,55,20]
    sorted_alist = merge_sort(alist)
    print(sorted_alist)

##  ##

时间复杂度

*  最优时间复杂度:O(nlogn)
 *  最坏时间复杂度:O(nlogn)
 *  稳定性:稳定

## 8.常⻅排序算法效率⽐较 ##

!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/58dda51f7dc6b666dab9e18d3ade29cf.png\#align=left&display=inline&height=372&margin=\[object Object\]&name=image.png&originHeight=372&originWidth=978&size=233175&status=done&style=none&width=978)

## 9.搜索 ##

搜索是在⼀个项⽬集合中找到⼀个特定项⽬的算法过程。搜索通常的答案是真的或假的，因为该项⽬是否存在。搜索的⼏种常⻅⽅法：顺序查找、⼆分法查找、⼆叉树查找、哈希查找

## 10.⼆分法查找 ##

⼆分查找⼜称折半查找，优点是⽐较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插⼊删除困难。因此，折半查找⽅法适⽤于不经常变动⽽查找频繁的有序列表。⾸先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字⽐较，如果两者相等，则查找成功；否则利⽤中间位置记录将表分成前、后两个⼦表，如果中间位置记录的关键字⼤于查找关键字，则进⼀步查找前⼀⼦表，否则进⼀步查找后⼀⼦表。重复以上过程，直到找到满⾜条件的记录，使查找成功，或直到⼦表不存在为⽌，此时查找不成功。  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/eef33a205760273fd3b02c21cab3ac35.png\#align=left&display=inline&height=546&margin=\[object Object\]&name=image.png&originHeight=546&originWidth=804&size=52310&status=done&style=none&width=804)  
⼆分法查找实现

（⾮递归实现）

def binary_search(alist, item):
        first = 0
        last = len(alist) - 1
        while first <= last:
            midpoint = (first + last) / 2
            if alist[midpoint] == item:
                return True
            elif item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
        return False
    
    testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42, ]
    print(binary_search(testlist, 3))
    print(binary_search(testlist, 13))

（递归实现）

def binary_search(alist, item):
        if len(alist) == 0:
            return False
        else:
            midpoint = len(alist)//2
            if alist[midpoint]==item:
              return True
            else:
              if item<alist[midpoint]:
                return binary_search(alist[:midpoint],item)
              else:
                return binary_search(alist[midpoint+1:],item)
    testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
    print(binary_search(testlist, 3))
    print(binary_search(testlist, 13))

时间复杂度

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

# 7.树与树算法 #

树与树算法

### 1.树的概念 ###

树（英语：tree）是⼀种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，⽤来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成⼀个具有层次关系的集合。把它叫做"树"是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。它具有以下的特点：

*  每个节点有零个或多个⼦节点；
 *  没有⽗节点的节点称为根节点；
 *  每⼀个⾮根节点有且只有⼀个⽗节点；
 *  除了根节点外，每个⼦节点可以分为多个不相交的⼦树；

!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/b6dd18e3d9b680f96a8af4098d220b1c.png\#align=left&display=inline&height=530&margin=\[object Object\]&name=image.png&originHeight=530&originWidth=944&size=349245&status=done&style=none&width=944)

!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/3d7c9419e4e27370e78c4dd764b65f5e.png\#align=left&display=inline&height=528&margin=\[object Object\]&name=image.png&originHeight=528&originWidth=938&size=125801&status=done&style=none&width=938)

### 2.树的术语 ###

*  节点的度：⼀个节点含有的⼦树的个数称为该节点的度；
 *  树的度：⼀棵树中，最⼤的节点的度称为树的度；
 *  叶节点或终端节点：度为零的节点；
 *  ⽗亲节点或⽗节点：若⼀个节点含有⼦节点，则这个节点称为其⼦节点的⽗节点；
 *  孩⼦节点或⼦节点：⼀个节点含有的⼦树的根节点称为该节点的⼦节点；
 *  兄弟节点：具有相同⽗节点的节点互称为兄弟节点；
 *  节点的层次：从根开始定义起，根为第1层，根的⼦节点为第2层，以此类推；
 *  树的⾼度或深度：树中节点的最⼤层次；
 *  堂兄弟节点：⽗节点在同⼀层的节点互为堂兄弟；
 *  节点的祖先：从根到该节点所经分⽀上的所有节点；
 *  ⼦孙：以某节点为根的⼦树中任⼀节点都称为该节点的⼦孙。
 *  森林：由m（m>=0）棵互不相交的树的集合称为森林；

### 3.树的种类 ###

*  ⽆序树：树中任意节点的⼦节点之间没有顺序关系，这种树称为⽆序树，也称为⾃由树；
 *  有序树：树中任意节点的⼦节点之间有顺序关系，这种树称为有序树；
    
     *  ⼆叉树：每个节点最多含有两个⼦树的树称为⼆叉树；
        
         *  完全⼆叉树：对于⼀颗⼆叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数⽬均已达最⼤值，且第d层所有节点从左向右连续地紧密排列，这样的⼆叉树被称为完全⼆叉树，其中满⼆叉树的定义是所有叶节点都在最底层的完全⼆叉树;
         *  平衡⼆叉树（AVL树）：当且仅当任何节点的两棵⼦树的⾼度差不⼤于1的⼆叉树；
         *  排序⼆叉树（⼆叉查找树（英语：Binary Search Tree），也称⼆叉搜索树、有序⼆叉树）；
     *  霍夫曼树（⽤于信息编码）：带权路径最短的⼆叉树称为哈夫曼树或最优⼆叉树；
     *  B树：⼀种对读写操作进⾏优化的⾃平衡的⼆叉查找树，能够保持数据有序，拥有多余两个⼦树。

### 4.树的存储与表示 ###

**顺序存储**：将数据结构存储在固定的数组中，然在遍历速度上有⼀定的优势，但因所占空间⽐较⼤，是⾮主流⼆叉树。⼆叉树通常以链式存储。  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/e33bba939a6970e89b167002f4020afa.png\#align=left&display=inline&height=680&margin=\[object Object\]&name=image.png&originHeight=680&originWidth=890&size=418868&status=done&style=none&width=890)  
**链式存储：**  
**!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/98bdb7f737c5987d0d15067670a04a78.png\#align=left&display=inline&height=538&margin=\[object Object\]&name=image.png&originHeight=538&originWidth=966&size=234829&status=done&style=none&width=966)**  
由于对节点的个数⽆法掌握，常⻅树的存储表示都转换成⼆叉树进⾏处理，⼦节点个数最多为2

### 5.常⻅的⼀些树的应⽤场景 ###

1.  xml，html等，那么编写这些东⻄的解析器的时候，不可避免⽤到树
2.  路由协议就是使⽤了树的算法
3.  mysql数据库索引
4.  ⽂件系统的⽬录结构
5.  所以很多经典的AI算法其实都是树搜索，此外机器学习中的decision tree也是树结构

!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/96b5182839f527ce1ad8c73886ab913a.png\#align=left&display=inline&height=598&margin=\[object Object\]&name=image.png&originHeight=598&originWidth=934&size=125879&status=done&style=none&width=934)

## 1.⼆叉树 ##

### 1.⼆叉树的基本概念 ###

⼆叉树是每个节点最多有两个⼦树的树结构。通常⼦树被称作"左⼦树"（leftsubtree）和"右⼦树"（right subtree）

### 2.⼆叉树的性质(特性) ###

*  性质1:在⼆叉树的第i层上⾄多有2^(i-1)个结点（i>0）
 *  性质2:深度为k的⼆叉树⾄多有2^k - 1个结点（k>0）
 *  性质3:对于任意⼀棵⼆叉树，如果其叶结点数为N0，⽽度数为2的结点总数为N2，则N0=N2+1;
 *  性质4:具有n个结点的完全⼆叉树的深度必为 log2(n+1)
 *  性质5:对完全⼆叉树，若从上⾄下、从左⾄右编号，则编号为i的结点，其左孩⼦编号必为2i，其右孩⼦编号必为2i＋1；其双亲的编号必为i/2（i＝1时为根,除外）

> (1)完全⼆叉树------若设⼆叉树的⾼度为h，除第 h层外，其它各层 (1～  
> h-1)的结点数都达到最⼤个数，第h层有叶⼦结点，并且叶⼦结点都是从左到右依次排布，这就是完全⼆叉树。  
> !\[image.png\](https://img-blog.csdnimg.cn/img\_convert/1874ac77f47672eaee9258b5d358bdb4.png\#align=left&display=inline&height=826&margin=\[object Object\]&name=image.png&originHeight=826&originWidth=996&size=343399&status=done&style=none&width=996)

(2)满⼆叉树------除了叶结点外每⼀个结点都有左右⼦叶且叶⼦结点都处在最底层的⼆叉树。  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/89b332996ef027e93888d18db02b8cc9.png\#align=left&display=inline&height=740&margin=\[object Object\]&name=image.png&originHeight=740&originWidth=766&size=406597&status=done&style=none&width=766)

### 3.⼆叉树的节点表示以及树的创建 ###

通过使⽤Node类中定义三个属性，分别为elem本身的值，还有lchild左孩⼦和rchild右孩⼦

class Node(object): 
        """节点类"""
        def __init__(self, elem=-1, lchild=None, rchild=None):
            self.elem = elem
            self.lchild = lchild
            self.rchild = rchild

树的创建,创建⼀个树的类，并给⼀个root根节点，⼀开始为空，随后添加节点

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

## 2.⼆叉树的遍历 ##

树的遍历是树的⼀种重要的运算。所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问⼀次且仅访问⼀次，我们把这种对所有的访问称为遍历（traversal）。那么树的两种重要的遍历模式是深度优先遍历和⼴度优先遍历,深度优先⼀般⽤递归，⼴度优先⼀般⽤队列。⼀般情况下能⽤递归实现的算法⼤部分也能⽤堆栈来实现。

### 1.深度优先遍历 ###

对于⼀颗⼆叉树，深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分⽀。那么深度遍历有重要的三种⽅法。这三种⽅式常被⽤于访问树的节点，它们之间的不同在于访问每个节点的次序不同。这三种遍历分别叫做先序遍历（preorder），中序遍历（inorder）和后序遍历（postorder）。我们来给出它们的详细定义，然后举例看看它们的应⽤。

*  先序遍历在先序遍历中，我们先访问根节点，然后递归使⽤先序遍历访问左⼦树，再递归使⽤先序遍历访问右⼦树根节点->左⼦树->右⼦树

def preorder(self, root): 
        """递归实现先序遍历"""
        if root == None:
            return
        print(root.elem)
        self.preorder(root.lchild)
        self.preorder(root.rchild)

*  中序遍历在中序遍历中，我们递归使⽤中序遍历访问左⼦树，然后访问根节点，最后再递归使⽤中序遍历访问右⼦树左⼦树->根节点->右⼦树

def inorder(self, root): 
        """递归实现中序遍历"""
        if root == None:
            return
        self.inorder(root.lchild)
        print(root.elem)
        self.inorder(root.rchild)

*  后序遍历在后序遍历中，我们先递归使⽤后序遍历访问左⼦树和右⼦树，最后访问根节点左⼦树->右⼦树->根节点

def postorder(self, root):
        """递归实现后续遍历"""
        if root == None:
            return
        self.postorder(root.lchild)
        self.postorder(root.rchild)
        print (root.elem)

!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/1f80a8ea2013b957284aab7d6827c78d.png\#align=left&display=inline&height=480&margin=\[object Object\]&name=image.png&originHeight=480&originWidth=928&size=118845&status=done&style=none&width=928)  
!\[image.png\](https://img-blog.csdnimg.cn/img\_convert/39a92cff8b47feeec3cf97658a24322a.png\#align=left&display=inline&height=792&margin=\[object Object\]&name=image.png&originHeight=792&originWidth=778&size=222382&status=done&style=none&width=778)  
思考：哪两种遍历⽅式能够唯⼀的确定⼀颗树？？？

### 2.⼴度优先遍历(层次遍历) ###

从树的root开始，从上到下从从左到右遍历整个树的节点

def breadth_travel(self): 
        """利用队列实现树的层次遍历"""
        if root == None:
            return
        queue = []
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print(node.elem)
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)