算法

一、算法复杂度

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

算法的提出

例：如果a+b+c=1000，且a^2+b^2=c^2（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",a,b,c)
end_time = time.time()
print("所用时间：",end_time-start_time)

C:\Users\...
a,b,c 0 500 500
a,b,c 200 375 425
a,b,c 375 200 425
a,b,c 500 0 500
所用时间： 107.89521360397339

Process finished with exit code 0

算法是独立存在的一种解决问题的方法和思想

算法的五大特征

1. 输入性：算法有零个或多个外部量作为算法的输入
2. 输出性：算法至少偶遇一个量作为输出
3. 确定性：算法中每条指令清晰，无歧义
4. 有穷性：算法中每条指令的执行次数有限，执行每条指令时间也有限
5. 可行性：算法原则上能够精确的运行，且用纸笔做有限次运算后即可完成

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",a,b,c)

end_time = time.time()
print("所用时间：",end_time-start_time)

C:\Users\...
a,b,c 0 500 500
a,b,c 200 375 425
a,b,c 375 200 425
a,b,c 500 0 500
所用时间： 0.7260236740112305

Process finished with exit code 0

1.时间复杂度

一个程序最终执行的次数来衡量算法的优劣

时间复杂度是一个函数，该函数计算的是执行基本操作的次数；

算法的主要部分：
算法最重要的是数量级和趋势；而计算算法基本操作数量的规模函数中常量因子可忽略不计

一个算法语句的执行次数是关于问题规模N的某个函数，记为f(N),[N称为问题的规模]

语句的总执行次数，记为T(N)；当N不断变化时，T(N)也在变化

O渐进法

算法语句的总执行次数的增长率和f(N)的增长率相同即：T(N)=O(f(N))
[Of(N)为时间复杂度的O的渐进表示法]

**T(N)[语句的总执行次数]**=**f(N)[忽略细节部分的总语句]**的增长率

即 =Of(N)
‘

T(n)=k*f(N)+c
f(N)=n*n
即：f(N)叫做T(N)的渐进函数

def test(n):

    count = 0

    for i in range(count,n):
        for j in range(count,n):
            count+=1
       #n*n次
    for k in range(0,2*n):
            count+=1
       #2*n次

    icount = 10
    while icount>0:
        count+=1
        icount-=1
     #递减10次

执行次数：n*n + 2*n +10 = f(n)

复杂度的计算

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

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

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

常见时间复杂度

注意：经常将log2n，简写成logn

时间复杂度关系

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O( 2n )<O(n!)<O(n*n)

2.空间复杂度

一个程序运行完所需要的内存大小

空间复杂度的分类

• 固定空间

指令空间（代码空间）、数据空间（常量、简单的变量）等所占的空间，属于静态空间

• 可变空间

指动态分配的空间，以及递归栈所需的空间等，与空间大小、算法有关

空间复杂度S(N) = O(f(n))

二、排序算法

排序算法：将一串数据依照特定顺序进行排列的一种算法

排序算分的稳定性：
如果一个排序算法是稳定的，那么两个相等键值的纪录R和S，在原本的列表中R出现在S之前，当在排序过后，列表中的R也将会在S之前。

稳定排序算法会让原本有相等键值的纪录维持相对次序

例：
（4,1）**（3,1）（3,7）**（5,6）

排序1：**（3,1）（3,7）**（4,1）（5,6） ——>（维持次序）稳定
排序2：**（3,7）（3,1）**（4,1）（5,6） ——>（次序改变）

1.冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它重复的遍历排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换起来。遍历数列的工作就是重复度的进行直到没有再需要交换，也就是说该序列已经排序完成。
冒泡排序算法的运作如下：

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

冒泡排序分析

def bubble_sort(alist):
    n=len(alist)
    for k in range(n-1):
        for i in range(n-1-k):
            if alist[i]>alist[i+1]:
                alist[i],alist[i+1]=alist[i+1],alist[i]




alist=[2,6,22,64,22,45,3]
bubble_sort(alist)
print(alist)

时间复杂度：

• 最优时间复杂度：O（n）
• 最坏时间复杂度：O（n^2）
• 稳定

2.选择排序

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

选择排序分析

[12,34,9,2,7,3,17,22,43,18]第一次
↑ ↑
[2, 34,9,12,7,3,17,22,43,18]第二次
↑ ↑
[2,3, 9,12,7,34,17,22,43,18]第三次
↑ ↑
[2,3,7, 12,9,34,17,22,43,18]第四次
↑ ↑
[2,3,7,9, 12,34,17,22,43,18] 无需比较
← ← ↑
[2,3,7,9,12, 34,17,22,43,18]第五次
↑ ↑
[2,3,7,9,12,17, 34,22,43,18]第六次
↑ ↑
[2,3,7,9,12,17,18, 34,22,43]第七次
↑ ↑
[2,3,7,9,12,17,18,22, 34,43]无需比较
↑ ↑
↓
[2,3,7,9,12,17,18,22,34,43]

def select_sort(alist):
    n=len(alist)
    for i in range(n-1):
        min_index=i;

        for j in range(i+1,n):
            if alist[min_index]>alist[j]:
                min_index=j;
        if min_index!=i:
            alist[i],alist[min_index] = alist[min_index],alist[i]

alist = [12,34,9,2,7,3,17,22,43,18]
select_sort(alist)
print(alist)

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

3.插入排序

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

插入排序分析

def inset_sort(alist):
    n=len(alist)
    for j in range(1,n):
        i=j
        while i>0:
            if alist[i]<alist[i-1]:
                alist[i],alist[i-1]=alist[i-1],alist[i]
            else:
                break
            i-=1

alist =[30,6,13,4,23,27,22,50,20,66,36,49]
inset_sort(alist)
print(alist)

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

4.快速排序

快速排序，又称为交换排序，通过一趟排序将要排序的数据分割为独立的两个部分。假设要排序的列表是A[0]······A[N-1]，首先任意选取一个数据（通常选用列表的第一个数）作为基准数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它的右边去，这个过程称为一趟快速排序。
步骤为：

1. 设置两个变量low、hight，排序开始的时候：low=0.height=N-1
2. 以第一个列表元素作为基准数据，赋值给mid，即mid=A[0]
3. 从hight开始向前搜索，即由后开始向前搜索（height—），找到第一个小于mid的值A[hight]，将A[hight]和A[low]交换
4. 从low开始向后搜索，即由前开始向后搜索low++，找到第一个大于mid的

快速排序分析

[34,38,49,2,48,21,25,7] #升序排序

选择基准数34：第一个元素34（比34小的放在左边，比34大的放在右边）
low==1
hight==n-1

low=1
34,(选pivot轴，通常是第一个元素)
[ 38,49,2,48,21,25,7]
↑ ↑

hight-1=-1
34, 7 拿7与34比，
[ 38,38,2,48,21,25, ]
34, ↑
[7,38,49,2,48,21,34,25]小于34，放在左边

low+1=2
34 38 拿38与34比
[7, 49,2,48,21,25]
34, ↑ ↑
[7,49,2,48,21,25,38]大于34，放在右边

hight-2=-2
34, 25 拿25与34比
[7, 49,2,48,21,34, 38]
34, ↑ ↑
[7,25,49,2,48,21,38]小于34，放在左边

low+2=3
34 49 拿34与49比
[7,25, 2,48,21,38]
↑ ↑
34
[7,25,2,48,21,38,49]大于34，放在右边

height-3=-3
34 21 拿21与34比
[7,25,2,48, 38,49]
↑ ↑
34,
[7,25,21,2,48,38,49]小于34，放在左边

low+3=4
34, 2 拿2与34比
[7,25,21, 48,38,49]
↑ ↑
[7,25,21,2 ,48,38,49]小于34，并且在左边，不变

hight-4=-4==low
34
[7,25,21,2,48,38,49]low 与height重合，
↑
low==heihgt
[7,25,21,2,34,48,38,49]把34放入其中
↑
此时①[7,25,21,2]<34<②[48,38,49]

①：
low=1
7
[ 25,21,2]

height-1=-1
7 2 拿2与7比
[ 25, 21 ]
↑ ↑
[ 2,25, 21 ]小于7，放在左边

low+1=2
7 25 拿25与7比
[2, 21]
7 ↑
[2, 21,25]大于7，放在右边

height-2=-2 重合
7
[2,21,25]
↑
[2,7,21,25]把7放入这个位置

[2,7]与[21,25]为有序序列，不需要排序

②：
low=1
48
[ 38,49]

height-1
48 38 拿38与48比
[ 49 ]
↑
[ 49 ]小于38，放在左边

low+1==height重合
[38,48,49]

①=[2,7,21,25]+②[38,48,49]
=[2,7,21,25,28,48,49]

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(lnogn)
最坏时间复杂度：O(n2)
不稳定

5.归并排序

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

归并排序分析

[29,10,14,37,3,43,15,23]
↓
[29,10,14,37][3,43,15,23]
↓
[29,10][14,37][3,43][15,23]
↓
[29][10][14][37][3][43][15][23]

————————-两两排序————————

[10,29] [14,37] [3][43] [15][23]
↑ ↑ ↑ ↑
left指针 right指针 left指针 right指针
比 ↓ 较 比 ↓ 较
[10,14,29,37] + [3,15,23,43]
↑ ↑
left指针 right指针
比 ↓ 较

   ` [3, 10, 14, 15, 23, 29, 37, 43]`

def merg_sort(alist):

    n=len(alist)
    mid =len(alist)
    #递归的出口
    if n<=1:
        return alist
    mid=n//2
    left_li=merg_sort(alist[0:mid])
    right_li=merg_sort(alist[mid:])

    #合并
    #排序结果列表
    result=[]
    left_pointer,right_pionter=0,0
    while left_pointer<len(left_li) and right_pionter<len(right_li):
        if left_li[left_pointer] < right_li[right_pionter]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pionter])
            right_pionter += 1


    #退出循环后，将不为空的列表剩余元素添加到result
    result+=left_li[left_pointer:]
    result+=right_li[right_pionter:]


    return result





if __name__=="__main__":
    alist=[29,10,14,37,3,43,15,23]
    print(alist)
    s=merg_sort(alist)
    print(s)

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

三、查找算法

1、顺序查找法

最基本的查找，从表中的第一个（或者最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或者第一个）记录，其关键字和给定值比较都不等时，则表示没有查到记录，查找不成功

def sequence_search(alsit,v):

    for i in range(len(alsit)):
        if alsit[i] ==v:
            return i

    return -1


if __name__ =="__main__":
    alist=[3,24,54,54,32,45]
    index=sequence_search(alist,32)
    if index !=-1:
        print("找到了，索引值为：",index)
    else:
        print("没有找到")

2、二分查找法

二分查找又称为折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
首先，假设列表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，知道满足条件的的记录、使查找成功，或直到子表不存在为止，此时查表不成功。

   start=0
    end=n-1

    while start<=end:
        mid=(start+end)//2

        #判断中间值与比较的值：
        if alist[mid]==v:
            return True
        elif alist[mid]>v: #从左边列表查找
            end=mid-1
        else:
            start=mid+1
    raise False



#使用递归方式实现

def binary_search(alist,v):
    n = len(alist)
    # 递归出口
    if n==0:
        return  False

    mid=n//2
    if alist[mid]==v:       #查找成功在中间
        return True
    elif alist[mid]<v:     #右边列表查找
        return binary_search(alist[mid+1:].v)
    else:                   #左边列表查找
        return binary_search(alist[0,mid],v)




if __name__ == "__main__":
    alist=[1,2,3,4,5,6,7,8,9]
    print(binary_search(alist,4))

数据结构

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

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

#保存一个班级的学生信息

#列表、元组、字典、集合set

#学生信息（sno、sname age、score）




#列表、元组
stu=[("1001","张三",23,98),
     ("1002","李四",21,92),
     ("1003","王五",24,89)]

#列表、字典
stus=[{"sno":1001,"sname":"张三","age":23,"score":98},
      {"sno":1002,"sname":"李四","age":21,"score":92},
      {"sno":1003,"sname":"王五","age":24,"score":89}]


#如果使用列表保存学生信息，必须遍历当前列表，拿学号进行判断
#时间复杂度O(n)
for stu in stus:
    pass





#字典
stus={"1001":{"sname":"张三","age":23,"score":98},
      "1002":{"sname":"李四","age":21,"score":92},
      "1003":{"sname":"王五","age":24,"score":89}}

#如果使用字典保存，根据key进行获取,时间复杂度0(1)
stu=stus["1002"]

顺序表

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

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

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

根据线性表的实际存储方式，分为两种实际存储模型：
顺序表，将元素顺序的存放在一块连续的存储器里，元素间的顺序关系由他们的存储顺序自然表示

链表，将元素存放在通过链接构造起来的一系列存储块中
python中的list和tuple两种类型采用了顺序表的实现技术，tuple是不可表类型，即不变的顺序表，因此不改变其内部状态的任何操作，而在其他方面，则与list的性质类似

顺序表的操作

增加元素

1. 尾端插入元素，时间复杂度为O(1)
2. 非保序的加入元素（不常见），时间复杂度为O(1)
3. 保序的时间的元素加入，时间复杂度O(n)

删除元素

1. 删除表尾元素，时间复杂度为O(1)
2. 非保序的元素删除（不常见），时间复杂度为O(1)
3. 保序的时间的元素删除，时间复杂度O(n)

python标准类型list就是一种元素个数可变的线性表，可以加入和删除元素，并在各种操作中维持已有元素的顺序（即保存）

timeit模块

timeit模块可以用来测试一小段python代码的执行速度

class timeit.Timer(stmt="pass",setup="pass",time=<timer function>)

Timer是测量小段代码的执行速度的类。其中stmt参数是要测试的代码语句(statment)；setup参数是运行代码是所需要的设置；timer参数是一个定时器函数，与平台有关

timeit.Timer.timeit(number=100000)

Timer类中测试语句执行的对象方法。number参数是测试代码时的测试次数，默认为1000000次。方法返回执行代码的平均耗时，一个float类型的秒数

from timeit import Timer

def append_test():
    li=[]
    for i in range(10000):
        li.append(i)


def insert_test():
    li=[]
    for i in range(10000):
        li.insert(0,i)


append_timer=Timer('append_test()','from __main__ import append_test')
print("append的time",append_timer.timeit(1000))


insert_timer=Timer('insert_test()','from __main__ import insert_test')
print("insert的time",insert_timer.timeit(1000))

C:\Users\...测试list列表中append和insert执行速度.py
append的time 0.5025127
insert的time 16.473333999999998

Process finished with exit code 0

链表

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

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

链表的定义

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

单向链表

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

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

class Node(object):

    def __init__(self,elem):

        self.elem=elem
        self.next=None


#构造单向链表类

class SingeLinkList:
    #初始化方法
    def __init__(self,node=None):
        #判断node是否为空
        if node!=None:
            headNode=Node(node)
            self.__head=headNode
        else:
            self.__head=node#__head为私有的，在外部不进行获取



    #在头部添加元素
    def add(self,item):
        #将传入的值构成节点
        node=Node(item)
        #将新节点的链接域next指向头节点
        node.next=self.__head
        #将列表的头__head指向新节点
        self.__head=node





    #在尾部追加元素
    def append(self,item):
        # 将传入的值构成节点
        node = Node(item)
        if self.is_empty():
            self.__head=node
        else:
            curNode = self.__head

            while curNode.next != None:
                curNode = curNode.next
            # 修改节点指向 最后一个节点的next指向node
            curNode.next = node



    #在指定位置添加元素
    def insert(self,pos,item):
        #如果传入的pos的是小于0的话，默认插入节点头部
        if pos<=0:
            self.add(item)
        #如果pos的值大于链表长度，直接将节点添加到尾部
        elif pos>(self.length()-1):
            self.append(item)
        else:
            # 构造节点
            node = Node(item)
            count = 0
            preNode = self.__head
            while count < (pos - 1):  # 找前一个节点
                count += 1
                preNode = preNode.next
            # 修改指向
            # 将前一个节点的next指向插入位置节点
            node.next = preNode.next
            # 将插入位置的前一个节点的next指向新节点
            preNode.next = node





    #删除节点
    def remove(self,item):
        curNode=self.__head
        preNode=None
        while curNode!=None:
            if curNode.elem==item:
                #判断是否是头节点
                if preNode==None:
                    self.__head=curNode.next
                else:

                    #删除
                    preNode.next=curNode.next
                break
            else:
                preNode=curNode
                curNode=curNode.next





    #查找节点是否存在
    def search(self,item):
        curNode=self.__head
        while curNode!=None:
            if curNode.elem==item:
                return True
            curNode=curNode.next
        return False







    #遍历链表
    def travel(self):
        curNode=self.__head
        while curNode!=None:
            print(curNode.elem,end='\t')
            curNode=curNode.next
        print("")





    #判断单向链表是否为空
    def is_empty(self):
        #判断head是否指向None,如果指向None则就是空链表
        """
        if self.__head==None:
            return True
        else:
            return False
        """
        return self.__head==None




    #计算单向链表的长度
    def length(self):
        count=0
        curNode=self.__head
        while curNode!=None:
            count+=1
            curNode=curNode.next
        return count



if __name__ =="__main__":

    singeLinkList = SingeLinkList()


    print("是否为空链表：",singeLinkList.is_empty())


    print("头部插入")
    singeLinkList.add(1)
    singeLinkList.add(2)
    singeLinkList.add(3)
    singeLinkList.travel()

    print("查找单链表中的元素：")
    print(singeLinkList.search(2))
    print(singeLinkList.search(3))

    print("尾部追加")
    singeLinkList.append(1)
    singeLinkList.append(2)
    singeLinkList.append(3)
    singeLinkList.travel()
    print("链表的长度：", singeLinkList.length())

    print("指定位置插入：")
    singeLinkList.insert(2,100)
    singeLinkList.insert(-1,100)
    singeLinkList.insert(10,200)
    singeLinkList.travel()

    print("删除节点：")
    singeLinkList.remove(100)
    singeLinkList.travel()
    singeLinkList.remove(200)
    singeLinkList.travel()
    singeLinkList.remove(100)
    singeLinkList.travel()

C:\User...链表.py
是否为空链表： True
头部插入
3    2    1    
查找单链表中的元素：
True
True
尾部追加
3    2    1    1    2    3    
链表的长度： 6
指定位置插入：
100    3    2    100    1    1    2    3    200    
删除节点：
3    2    100    1    1    2    3    200    
3    2    100    1    1    2    3    
3    2    1    1    2    3

链表与顺序表的对比

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

链表与顺序表的各种操作复杂度

注意：
虽然表面看起来复杂度都是O(n)，但是链表和顺序表在插入和删除的进行的是完全不同的操作。
链表的主要操作是遍历查找，删除和插入本身的复杂度就是O(1)。
顺序表查找很快，主要的操作时拷贝覆盖。因为除了目标元素尾部的特殊情况，顺序表进行插入和删除时需要对操作点之后的所有元素进行前后位移操作，只能通过拷贝和覆盖的方法进行

双向链表

一种更复杂的链表是“双向链表”或双面链表。每个节点有两个链表；一个指向前一个节点，当此节点为第一个时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值

···

指定位置插入

 #在指定位置添加元素
    def insert(self,pos,item):
        #如果传入的pos的是小于0的话，默认插入节点头部
        if pos<=0:
            self.add(item)
        #如果pos的值大于链表长度，直接将节点添加到尾部
        elif pos>(self.length()-1):
            self.append(item)
        else:
            # 构造节点
            node = Node(item)
            count = 0
            curNode = self.__head
            while count < (pos - 1):  # 找前一个节点
                count += 1
                curNode = curNode.next
            # 修改指向
            #将node节点的前驱指向当前节点
            node.prev=curNode
            #将node节点的后继指向当前节点的下一个节点
            node.next=curNode.next
            #将当前节点的下一个节点的前驱指向node节点
            curNode.next.prev=node
            #将当前节点的后继指向node节点
            curNode.next=node

删除节点

 #删除节点
    def remove(self,item):
        curNode=self.__head
        preNode=None
        while curNode!=None:
            if curNode.elem==item:
                #判断是否是头节点
                if curNode==self.__head:
                    self.__head=curNode.next
                    #判断当前节点是否只有一个节点，如果只有一个节点，则不需要移动
                    if curNode.next:
                        curNode.next.prev=None
                else:

                    #删除
                    curNode.prev.next=curNode.next
                    #判断是否为最后一个节点
                    if curNode.next:
                        curNode.next.prev = curNode.prev
                break
            else:
                curNode=curNode.next

#双向链表的节点

class Node:
    def __init__(self,elem):
        self.elem=elem
        self.next=None #后继
        self.prev=None #前驱



class DoubleLinkList:
    #初始化方法
    def __init__(self,node=None):
        #判断node是否为空
        if node!=None:
            headNode=Node(node)
            self.__head=headNode
        else:
            self.__head=node#__head为私有的，在外部不进行获取



    #在头部添加元素
    def add(self,item):

        # 将传入的值构成节点
        node = Node(item)

        #判断是否为空链表
        if self.is_empty():
            self.__head=node
        else:
            # 将新节点的链接域next指向头节点
            node.next = self.__head

            # 将__head的头节点的prev指向node
            self.__head.prev = node

            # 将链表的头__head指向新节点
            self.__head = node



    #在尾部追加元素
    def append(self,item):
        # 将传入的值构成节点
        node = Node(item)
        if self.is_empty():
            self.__head=node
        else:
            curNode = self.__head

            while curNode.next != None:
                curNode = curNode.next
            # 修改节点指向 最后一个节点的next指向noode
            curNode.next = node

            #将node节点的前驱指向当前节点
            node.prev=curNode



    #在指定位置添加元素
    def insert(self,pos,item):
        #如果传入的pos的是小于0的话，默认插入节点头部
        if pos<=0:
            self.add(item)
        #如果pos的值大于链表长度，直接将节点添加到尾部
        elif pos>(self.length()-1):
            self.append(item)
        else:
            # 构造节点
            node = Node(item)
            count = 0
            curNode = self.__head
            while count < (pos - 1):  # 找前一个节点
                count += 1
                curNode = curNode.next
            # 修改指向
            #将node节点的前驱指向当前节点
            node.prev=curNode
            #将node节点的后继指向当前节点的下一个节点
            node.next=curNode.next
            #将当前节点的下一个节点的前驱指向node节点
            curNode.next.prev=node
            #将当前节点的后继指向node节点
            curNode.next=node





    #删除节点
    def remove(self,item):
        curNode=self.__head
        preNode=None
        while curNode!=None:
            if curNode.elem==item:
                #判断是否是头节点
                if curNode==self.__head:
                    self.__head=curNode.next
                    #判断当前节点是否只有一个节点，如果只有一个节点，则不需要移动
                    if curNode.next:
                        curNode.next.prev=None
                else:

                    #删除
                    curNode.prev.next=curNode.next
                    #判断是否为最后一个节点
                    if curNode.next:
                        curNode.next.prev = curNode.prev
                break
            else:
                curNode=curNode.next




    #查找节点是否存在
    def search(self,item):
        curNode=self.__head
        while curNode!=None:
            if curNode.elem==item:
                return True
            curNode=curNode.next
        return False





    #遍历链表
    def travel(self):
        curNode=self.__head
        while curNode!=None:
            print(curNode.elem,end='\t')
            curNode=curNode.next
        print("")





    #判断链表是否为空
    def is_empty(self):
        #判断head是否指向None,如果指向None则就是空链表
        """
        if self.__head==None:
            return True
        else:
            return False
        """
        return self.__head==None




    #计算链表的长度
    def length(self):
        count=0
        curNode=self.__head
        while curNode!=None:
            count+=1
            curNode=curNode.next
        return count



if __name__ =="__main__":
    doubleLinkList=DoubleLinkList()
    doubleLinkList.add(1)
    doubleLinkList.add(2)
    doubleLinkList.add(3)
    doubleLinkList.travel()
    doubleLinkList.append(100)
    doubleLinkList.append(200)
    doubleLinkList.append(300)
    doubleLinkList.travel()
    doubleLinkList.insert(1,6)
    doubleLinkList.travel()
    doubleLinkList.remove(1)
    doubleLinkList.remove(100)
    doubleLinkList.travel()
    print(doubleLinkList.length())
    print(doubleLinkList.search(2))

C:\Users...\双向链表.py
3    2    1    
3    2    1    100    200    300    
3    6    2    1    100    200    300    
3    6    2    200    300    
5
True

Process finished with exit code 0

栈

栈（stack），又称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只允许在一个容器的一端进行加入数据和输出数据的运算，没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序
由于栈数据只允许一段进行操作，因而按照后进先出（LIFO，Last In First Out）的原理运作

栈结构的实现

实现步骤：

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

class Stack(object):

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

    # 压栈
    def push(self,item):
        self.__list.append(item)

    #弹出元素
    def pop(self):
        return self.__list.pop()

    #返回栈顶元素
    def peek(self):
        return self.__list[len(self.__list)]

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


    #计算栈的大小
    def size(self):
        return len(self.__list)



if __name__=='__main__':
    stack=Stack()

    print(stack.is_empty())

    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)

    print(stack.size())

    print(stack.pop())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())

C:\Users...\栈.py
True
4
4
3
2
1

Process finished with exit code 0

队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出的（First In Frist Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作。假设队列是q=（a1,a2,……,an）,那么a1就是队头元素，二an就是队尾元素。这样我们就可以在删除时，总是从a1开始，而插入时，总是在队列最后。

队列的操作：

     1. Queue()创建一个空列表
     1. enqueue（item）往队列中添加一个item元素
     1. dequeue（）从队列头部删除一个元素
     1. is_empty（）判断一个队列是否为空
     1. size()返回队列大小

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


    #进队
    def enqueue(self,item):
        # self.__list.append(item)
        self.__list.insert(0,item)


    #出队
    def dequeue(self):
        # return self.__list.pop(n)
        return self.__list.pop()


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

    #计算队列的大小
    def size(self):
        return len(self.__list)


if __name__=="__main__":
    queue=Queue()
    print(queue.is_empty())

    queue.enqueue(10)
    queue.enqueue(20)
    print(queue.size())
    print(queue.dequeue())
    print(queue.dequeue())
    print(queue.size())

C:\Users.../队列.py
True
2
10
20
0

Process finished with exit code 0

树与树的算法

树的概念

数是一种抽象的数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合，它是由n（n>=1）个有限节点组成的一个具有层次关系的集合。

它具有以下特点：

1. 每个节点有零个或多个子节点
2. 没有父节点的节点称为根节点
3. 每个非根节点有且只有一个父节点
4. 除根节点外，每个子节点可以分为多个不相交的子数

树的术语：

1. 节点的度：一个节点含有子树的个数称为该节点的度
2. 数的度：一颗数中，最大的节点的度称为数的度
3. 叶节点或终端节点：度为零的节点
4. 父节点：若一个节点含有子节点，则这个节点称为其他子节点的父节点
5. 子节点：一个节点含有子树的根节点称为该节点的子节点
6. 兄弟节点：具有相同父节点互称为兄弟节点
7. 节点的层次：从根开定义起，根为第一层，根的子节点为第二次，以此类推；
8. 树的高度或深度：树中节点的最大层次
9. 堂兄弟节点：父节点 在用一层的节点互为堂兄弟
10. 节点的祖先：从根节点到该节点所经分支的所有节点
11. 子孙：一某节点为根的子树中都称为该节点的子孙
12. 森林：由m（m>=0）棵互不相交的数的集合称为森林

树的种类

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

有序树：树任意节点的子节点之间有顺序关系，这种树称为有序树

二叉树：每个节点最多含有两个子树称为二叉树
完全二叉树：对于一棵二叉树，假设其深度为d(d>1)。d底层外，其他各层的节点数目均已达最大值，且第d层所有节点从左向右连续的紧密排列，这样的二叉数被称为完全二叉树，
满二叉树的定义是所有叶子节点都在最底层的完全二叉树
平衡二叉树（AVL数）：当且仅当任何节点的两棵子树的高度不大于1的二叉树
排序二叉树（二叉查找数Binary Search Tree），也称为二叉搜索数、有序二叉树

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

常见的一些数的应用场景

1. xml，html等
2. 路由协议
3. MySQL数据库索引
4. 文件系统的目录结构
5. 经典的AI算法，机器学习中的decision tree

二叉树

二叉树的基本概念

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

二叉树的性质（特性）

性质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层没有叶子节点，并且叶子节点都是从左到右依次排布。

（2）满二叉树——除了叶子节点每一个节点都有左右叶子且叶子节点都处在最底层的二叉树

二叉树的遍历

树的遍历是树的一种重要运算。所谓遍历是指对树中的所有节点的信息访问，即依次对树中每个节点访问一次且仅访问一次。我们把这种对所有节点的访问称为遍历。
树的两种重要的遍历模式是深度优先遍历，深度优先一般用递归，广度优先一般用队列；一般情况下能用过递归实现的算法大部分也能用堆栈来实现

广度优先遍历（层次遍历）

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

#广度优先遍历
    def travel(self):
        queue=[]
        #判断根节点是否存在
        if self.root is None:
            return
        else:
            queue.append(self.root)

        while queue:
            curNode=queue.pop(0)
            print(curNode.elem,end='\t')
            if curNode.lchild is not None:
                queue.append(curNode.lchild)
            if curNode.rchild is not None:
                queue.append(curNode.rchild)

深度优先遍历

对于一棵二叉树，深度优先搜索是沿着树的深度遍历树的节点，尽可能深的搜索数的的分支
深度遍历有三种重要的方法：

• 先序遍历（preorder）
• 中序遍历（inorder）
• 后序遍历（postorder）

先序遍历：在先序遍历中，我们先访问根节点，然后递归使用先序遍历访问左子树，再递归使用先序遍历访问右子树
根节点—>左子树—>右子树

中序遍历：在中序遍历中，我们递归使用中序遍历访问左子树，然后访问根节点，最后再递归使用中序遍历访问右子树
右子树—>根节点—>右子树

后序遍历：在后序遍历中，我们先递归使用后序遍历访问左子树和右子树，最后访问根访问根节点
左子树—>右子树—>根节点

层次遍历：0 1 2 3 4 5 6 7 8 9
先序遍历：0 1 3 7 8 4 9 2 5 6
中序遍历：7 3 8 1 9 4 0 5 2 6
后序遍历：7 8 3 9 4 1 5 6 2 0

遍历节点
先序：a b c d e f g h
中序：b d c e a f h g
后序：d e c b h g f a

#定义二叉树的节点
class Node:
    def __init__(self,elem):
        self.elem=elem
        self.lchild=None
        self.rchild=None

class Tree:
    def __init__(self):
        self.root=None


    #添加节点
    def add(self,elem):
        #创建节点
        node=Node(elem)

        if self.root==None:
            self.root=node
        else:
            queue = []
            queue.append(self.root)
            while queue:
                curNode = queue.pop(0)
                if curNode.lchild == None:
                    curNode.lchild = node
                    return
                else:
                    queue.append(curNode.lchild)


                if curNode.rchild == None:
                    curNode.rchild = node
                    return
                else:
                    queue.append(curNode.rchild)


    #广度优先遍历
    def travel(self):
        queue=[]
        #判断根节点是否存在
        if self.root is None:
            return
        else:
            queue.append(self.root)

        while queue:
            curNode=queue.pop(0)
            print(curNode.elem,end='\t')
            if curNode.lchild is not None:
                queue.append(curNode.lchild)
            if curNode.rchild is not None:
                queue.append(curNode.rchild)

        print()

    #深度优先遍历

    #先序遍历 根  左  右
    def preOrder(self,root):
        if root is None:
            return
        else:
            print(root.elem,end="\t")
            self.preOrder(root.lchild)
            self.preOrder(root.rchild)


    # 中序遍历 左  根  右
    def inOrder(self,root):
        if root is None:
            return
        else:
            self.inOrder(root.lchild)
            print(root.elem,end="\t")
            self.inOrder(root.rchild)


    # 后序遍历 左  右  根
    def lastOrder(self,root):
        if root is None:
            return
        else:
            self.lastOrder(root.lchild)
            self.lastOrder(root.rchild)
            print(root.elem,end="\t")



if __name__=='__main__':
    tree=Tree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.add(8)
    tree.add(9)


    tree.travel()
    tree.preOrder(tree.root)
    print()
    tree.inOrder(tree.root)
    print()
    tree.lastOrder(tree.root)

C:\Users\.../二叉树.py
0    1    2    3    4    5    6    7    8    9    
0    1    3    7    8    4    9    2    5    6    
7    3    8    1    9    4    0    5    2    6    
7    8    3    9    4    1    5    6    2    0    
Process finished with exit code 0