摘要：什么是數(shù)據(jù)結構數(shù)據(jù)的組織結構方式一組數(shù)據(jù)如何存儲，基本數(shù)據(jù)類型，，的封裝算法與數(shù)據(jù)結構的區(qū)別數(shù)據(jù)結構只是靜態(tài)的描述了數(shù)據(jù)元素之間的關系。高效的程序需要在數(shù)據(jù)結構的基礎上設計和選擇算法。

什么是數(shù)據(jù)結構和算法：兵法，計算的方法。
算法是獨立存在的一種解決問題的方法和思想。

算法的特征：

輸入：算法具有0個或多個輸入

輸出：算法至少有1個或多個輸出

有窮性：算法在有限的步驟之后會自動結束而不會無限循環(huán)，并且每一個步驟可以在可接受的時間內(nèi)完成

確定性：算法中的每一步都有確定的含義，不會出現(xiàn)二義性

可行性：算法的每一步都是可行的，也就是說每一步都能執(zhí)行有限的次數(shù)完成

時間復雜度和大O表示法

算法的優(yōu)劣： 實現(xiàn)算法程序的執(zhí)行時間可以反應出算法的效率

時間復雜度：步驟的執(zhí)行速度(基本執(zhí)行數(shù)量總和) + 程序運行環(huán)境（包括硬件和操作系統(tǒng)）

假設存在函數(shù)g，使得算法A處理規(guī)模為n的問題示例所用時間為T(n)=O(g(n))，則稱O(g(n))為算法A的漸近時間復雜度，簡稱時間復雜度，記為T(n)
T: time
三個1000次for循環(huán):
T = 1000 * 1000 * 1000 * 2 -> T(n) = n ^ 3 * 2 -> g(n) = n ^ 3, T(n) = k * g(n) -> T(n) = O(g(n))

“大O記法”：對于單調(diào)的整數(shù)函數(shù)f，如果存在一個整數(shù)函數(shù)g和實常數(shù)c>0，使得對于充分大的n總有f(n) <= c*g(n)，就說函數(shù)g是f的一個漸近函數(shù)（忽略常數(shù)），記為f(n)=O(g(n))。
也就是說，在趨向無窮的極限意義下，函數(shù)f的增長速度受到函數(shù)g的約束，亦即函數(shù)f與函數(shù)g的特征相似。

最壞時間復雜度

算法完成工作最少需要多少基本操作，即最優(yōu)時間復雜度

算法完成工作最多需要多少基本操作，即最壞時間復雜度

算法完成工作平均需要多少基本操作，即平均時間復雜度

最優(yōu)時間復雜度，其價值不大。
最壞時間復雜度，提供了一種保證，（只要關注，最壞時間復雜度）
平均時間復雜度，是對算法的一個全面評價。

時間復雜度的幾條基本計算規(guī)則

基本步驟，即只有常數(shù)項，認為其時間復雜度為O(1)

順序結構，時間復雜度按加法進行計算

循環(huán)結構，時間復雜度按乘法進行計算

分支結構，時間復雜度取最大值（if 或者 else 哪個步數(shù)最多）

判斷一個算法的效率時，往往只需要關注操作數(shù)量的最高次項，其它次要項和常數(shù)項可以忽略

在沒有特殊說明時，所分析的算法的時間復雜度都是指最壞時間復雜度

計算方式：

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


# T(1000) = 1000 * 1000 * (1 + 1)
# T(n) = n * n * (1 + max(1, 0))
#  = n ^ 2 * 2
#  = O(n ^ 2)

常見時間復雜度與大小關系

Note: 經(jīng)常將log2n（以2為底的對數(shù)）簡寫成logn

所消耗的時間從小到大:
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(n^n)

Note：函數(shù)是步驟和執(zhí)行結構的綜合

Python內(nèi)置類型性能

timeit模塊作用：測試一小段Python代碼代碼的執(zhí)行速度

class timeit.Timer(stmt="pass", setup="pass", timer=)
Timer是測量小段代碼執(zhí)行速度的類。
stmt參數(shù)是要測試的代碼語句（statment）；
setup參數(shù)是運行代碼時需要的設置；
timer參數(shù)是一個定時器函數(shù)，與平臺有關。

#coding=utf-8

from timeit import Timer


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

def test2():
    li = []
    for i in range(10000):
        li += [i]

def test3():
    li = [i for i in range(10000)]

def test4():
    li = list(range(10000))

timer1 = Timer("test1()", "from __main__ import test1")
print("append: ",timer1.timeit(1000)) # 測算次數(shù), 返回值測算時間

timer2 = Timer("test2()", "from __main__ import test2")
print("+: ",timer1.timeit(1000))

timer3 = Timer("test3()", "from __main__ import test3")
print("[]: ",timer1.timeit(1000))

timer4 = Timer("test4()", "from __main__ import test4")
print("list: ",timer1.timeit(1000))

list內(nèi)置操作的時間復雜度:

n: 列表長度
k: 范圍

主要：

index[] -> O(1)
append -> O(1)
pop(i) -> O(n)
insert(i, item) -> O(n)
contains(in) -> O(n)

dict內(nèi)置操作的時間復雜度:

數(shù)據(jù)結構引入

算法關注在解決問題的步驟和思想上面。

什么是數(shù)據(jù)結構：數(shù)據(jù)的組織結構方式,（一組數(shù)據(jù)如何存儲），基本數(shù)據(jù)類型（int， float，char）的封裝

算法與數(shù)據(jù)結構的區(qū)別：
數(shù)據(jù)結構只是靜態(tài)的描述了數(shù)據(jù)元素之間的關系。
高效的程序需要在數(shù)據(jù)結構的基礎上設計和選擇算法。

程序 = 數(shù)據(jù)結構 + 算法

總結：算法是為了解決實際問題而設計的，數(shù)據(jù)結構是算法需要處理的問題載體

最常用的數(shù)據(jù)運算有五種:

插入

刪除

修改

查找

排序

內(nèi)存

32位機器：一個int, 占四個字節(jié)。

變量表示起始地址位置

內(nèi)存的基本信息：

單位：字節(jié)， 1byte == 8bit

連續(xù)的存儲空間

一個字節(jié)表示一個地址單元

類型本質

任何變量，函數(shù)原則上都是一塊塊大小各異的內(nèi)存，而類型則是和系統(tǒng)對這塊內(nèi)存含義的約定（固定內(nèi)存塊大小的別名）

決定在內(nèi)存中占多少個單元

基本順序表與元素外圍順序表

順序表的基本布局：

數(shù)據(jù)元素本身連續(xù)存儲，每個元素所占的存儲單元大小固定相同，元素的下標是其邏輯地址，而元素存儲的物理地址（實際內(nèi)存地址）可以通過存儲區(qū)的起始地址Loc (e0)加上邏輯地址（第i個元素）與存儲單元大?。╟）的乘積計算而得

所以，訪問指定元素時無需從頭遍歷，通過計算便可獲得對應地址，其時間復雜度為O(1)

下標：地址單元的偏移量，才會規(guī)定為從0開始。

順序表的元素外置基本布局：

元素外置在內(nèi)存中存儲地址，地址字節(jié)是相同的（可以使用順序表），而非變化的字節(jié)。

順序表的一體式結構與分離式結構

順序表 = 數(shù)據(jù)區(qū)(元素集合) + 表頭信息(容量 + 元素個數(shù))

容量: 在最初始的時候，就要預估當前規(guī)模，一次性向操作系統(tǒng)申請內(nèi)存地址 （最大存儲多少）
元素個數(shù)：當前存儲多少

順序表的基本實現(xiàn)方式（表頭和數(shù)據(jù)區(qū)如何組合在一起）：

一體式結構：
優(yōu)點: 一次性申請， 整體性強，易于管理。
缺點：元素存儲區(qū)就固定。當數(shù)據(jù)存儲不下的時候，需要整體替換重新向操作系統(tǒng)申請

分離式結構：
優(yōu)點：元素存儲區(qū)不固定。
缺點：分二次申請，不易管理

最大區(qū)別：分離式其實位置（表頭）的地址不變，而一體式，需要整體替換（表頭和數(shù)據(jù)區(qū)）都需要重新申請。

順序表數(shù)據(jù)區(qū)替換與擴充

重新擴充的兩種策略：

每次擴充增加固定數(shù)目的存儲位置，如每次擴充增加10個元素位置，這種策略可稱為線性增長。
特點：節(jié)省空間，但是擴充操作頻繁，操作次數(shù)多。

每次擴充容量加倍，如每次擴充增加一倍存儲空間。
特點：減少了擴充操作的執(zhí)行次數(shù)，但可能會浪費空間資源。以空間換時間，推薦的方式。

順序表的操作

添加元素:

尾端加入元素，時間復雜度為O(1)
保序的元素加入，時間復雜度為O(n)

刪除元素:

刪除表尾元素，時間復雜度為O(1)
保序的元素刪除，時間復雜度為O(n)

Python中的list和tuple兩種類型采用了順序表的實現(xiàn)技術.
list就是一種采用分離式技術實現(xiàn)的動態(tài)順序表

list實現(xiàn)采用了如下的策略：在建立空表（或者很小的表）時，系統(tǒng)分配一塊能容納8個元素的存儲區(qū)；在執(zhí)行插入操作（insert或append）時，如果元素存儲區(qū)滿就換一塊4倍大的存儲區(qū)。但如果此時的表已經(jīng)很大（目前的閥值為50000），則改變策略，采用加一倍的方法。引入這種改變策略的方式，是為了避免出現(xiàn)過多空閑的存儲位置。

為什么需要鏈表

順序表缺點：

需要預先知道數(shù)據(jù)大小來申請存儲空間

進行擴充時需要進行數(shù)據(jù)的搬遷

靈活性低

手拉手的方式（線串）去存儲，而非通過元素外置的方式去存儲，元素外置需要預先知道數(shù)據(jù)大小。

線性表：
一維空間的一條線去組織數(shù)據(jù)，呈線性狀態(tài)。

順序表：將元素順序地存放在一塊連續(xù)的存儲區(qū)里，元素間的順序關系由它們的存儲順序自然表示。

鏈表：將元素存放在通過鏈接構造起來的一系列存儲塊中。

原本的數(shù)據(jù)區(qū)，不單單僅僅存儲數(shù)據(jù)，而會增加一個下一個的單元地址

單鏈表的ADT模型

頭節(jié)點：開始存儲的變量
尾節(jié)點：往后就是空指針

變量p指向鏈表的頭節(jié)點（首節(jié)點）的位置，從p出發(fā)能找到表中的任意節(jié)點。

單鏈表的操作:

is_empty() 鏈表是否為空
length() 鏈表長度
travel() 遍歷整個鏈表
add(item) 鏈表頭部添加元素
append(item) 鏈表尾部添加元素
insert(pos, item) 指定位置添加元素
remove(item) 刪除節(jié)點
search(item) 查找節(jié)點是否存在

Python中變量標識的本質: 存儲地址，引用指向到一個實際數(shù)據(jù)

單鏈表的實現(xiàn)

# coding=utf-8
# single_link_list

class Node(object):
    """節(jié)點"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None

# node = Node(100) # 保存  elem, next

class SingleLinkList(object):
    """單鏈表"""
    def __init__(self, node=None):
        self.__head = node # 頭節(jié)點
    def is_empty(self):
        """鏈表是否為空"""
        return self.__head == None

    def length(self):
        """鏈表長度"""
        # 游標, 指針
        # cur游標，用來移動遍歷節(jié)點
        cur = self.__head
        # count記錄數(shù)量
        count = 0
        while cur != None: # cur.next == None
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍歷整個鏈表"""
        cur = self.__head
        while cur != None:
            print(cur.elem, end=" ")
            cur = cur.next

    def add(self, item):
        """鏈表頭部添加元素，頭插法"""
        node = Node(item)
        node.next = self.__head # 保證鏈表中的所有關系不打斷
        self.__head = node

    def append(self, item):
        """鏈表尾部添加元素，尾插法"""
        # item 數(shù)據(jù)元素
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:     
            cur = self.__head
            while cur.next != None: # 從頭往后走，然后最后掛載一個新的游標
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        """指定位置添加元素
            :param pos 從0開始
        """
        if pos < 0:
            self.add(item)
        elif pos > self.length() - 1:
            self.append(item)
        else:
            # pre用來指向指定位置pos的前一個位置pos-1，初始從頭節(jié)點開始移動到指定位置
            pre = self.__head # pre, prior
            count = 0
            while count < pos - 1:
                count += 1
                pre = pre.next
            # 當循環(huán)退出后，pre指向pos-1的位置
            node = Node(item)
            # 先將新節(jié)點node的next指向插入位置的節(jié)點
            node.next = pre.next
            # 將插入位置的前一個節(jié)點的next指向新節(jié)點
            pre.next = node
    def remove(self, item):
        """刪除節(jié)點"""
        # pre 與 cur 二個游標，需要隔開移動
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 如果第一個就是刪除的節(jié)點
                if cur == self.__head:
                # 判斷子節(jié)點是否是頭節(jié)點
                    self.__head = cur.next # 將頭指針指向頭節(jié)點的后一個節(jié)點
                else:
                    # 將刪除位置前一個節(jié)點的next指向刪除位置的后一個節(jié)點
                    pre.next = cur.next
                break
            else:
                # 繼續(xù)按鏈表后移節(jié)點
                pre = cur
                cur = cur.next
    def search(self, item):
        """查找節(jié)點是否存在"""
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

if __name__ == "__main__":
    sll = SingleLinkList()
    print("is_empty", sll.is_empty())
    print("length", sll.length())
    sll.append(100)
    print("is_empty", sll.is_empty())
    print("length", sll.length())

    sll.append(22)
    sll.add(7)
    sll.append(20)
    sll.insert(2, 777)

    sll.travel()
    sll.remove(7)
    sll.travel()

insert示意圖:

remove示意圖：

后繼結點：當前節(jié)點的下一個節(jié)點

單鏈表與順序表的對比

鏈表失去了順序表隨機讀取的優(yōu)點，同時鏈表由于增加了節(jié)點的指針域，空間開銷比較大，但對存儲空間的使用要相對靈活。

鏈表與順序表的各種操作復雜度：

鏈表不能一次性找到位置，都需要通過循環(huán)來找到該位置；而順序表則直接找到位置。

數(shù)據(jù)包含：數(shù)據(jù)區(qū) + 前驅結點 + 后繼結點

# coding=utf-8
# double_link_list

class Node(object):
    """節(jié)點"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None
        self.prev = None

class DoubleLinkList(object):
    """雙鏈表"""
    def __init__(self, node=None):
        self.__head = node
    def is_empty(self):
        return self.__head is None

    def length(self):
        count = 0
        cur = self.__head
        while cur != None:
            count += 1
            cur = cur.next
        return count
    def travel(self):
        cur = self.__head
        while cur != None:
            print(cur.elem, end=" ")
            cur = cur.next
        print("")
    def add(self, item):
        node = Node(item)
        node.next = self.__head
        self.__head = node
        node.next.prev = node

    def append(self, item):
        node = Node(item)
        cur = self.__head

        if self.is_empty():
            self.__head = node
        else:    
            while cur.next != None:
                cur = cur.next
            cur.next = node
            node.prev = cur 

    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            cur = self.__head
            count = 0
            while count < pos:
                count += 1
                cur = cur.next
            # 當循環(huán)退出的時候，cur指針指向的就是pos的位置
            node = Node(item)
            # 將node的prev指向cur
            node.next = cur
            #  將node的next指向cur的下一個節(jié)點
            node.prev = cur.prev # 當前節(jié)點的上一個，指向到插入節(jié)點的前指針
            # 將cur的下一個節(jié)點的prev指向node
            cur.prev.next = node
            # 將cur的next指向node
            cur.prev = node

    def remove(self, item):
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                if cur == self.__head:
                    self.__head = cur.next
                    if cur.next: # 判斷雙鏈表是否之后一個節(jié)點
                        cur.next.prve = None
                else:
                    # 將cur的前一個節(jié)點的next指向cur的后一個節(jié)點
                    cur.prev.next = cur.next
                    if cur.next:
                        # 將cur的后一個節(jié)點的prev指向cur的前一個節(jié)點
                        cur.next.prev = cur.prev
                break
            else:
                cur = cur.next

    def search(self, item):
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

if __name__ == "__main__":
    dll = DoubleLinkList()

    print("is_empty", dll.is_empty())
    print("length", dll.length())
    dll.append(100)
    print("is_empty", dll.is_empty())
    print("length", dll.length())

    dll.append(22)
    dll.add(7)
    dll.append(20)
    dll.insert(2, 777)

    dll.travel()
    dll.remove(7)
    dll.travel()

# coding=utf-8
# single_cycle_link_list

class Node(object):
    """節(jié)點"""
    def __init__(self, node):
        self.elem = node
        self.next = None

class SingleCycleLinkList(object):
    """單鏈表"""
    def __init__(self, node=None):
        self.__head = node # 頭節(jié)點
        if node:
            node.next = node

    def is_empty(self):
        """鏈表是否為空"""
        return self.__head == None

    def length(self):
        """鏈表長度"""
        if self.is_empty():
            return 0
        cur = self.__head
        # count記錄數(shù)量
        count = 1 # count從1開始
        while cur.next != self.__head: # cur.next == None
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍歷整個鏈表"""
        if self.is_empty():
            return
        cur = self.__head
        while cur.next != self.__head:
            cur = cur.next
            print(cur.elem, end=" ")
        # print(cur.elem, "-------")
        # print("")

    def add(self, item):
        """鏈表頭部添加元素，頭插法"""
        node = Node(item)
        if self.is_empty():
            # 如果為空，指向節(jié)點，然后節(jié)點的指針指向自己
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            # 指針先移動到尾端
            while cur.next != self.__head:
                cur = cur.next
            # 退出循環(huán)，cur指向尾節(jié)點
            # 改變指針指向
            node.next = self.__head
            self.__head = node
            # cur.next = node
            cur.next = node

    def append(self, item):
        """鏈表尾部添加元素，尾插法"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            node.next = self.__head
            cur.next = node

    def insert(self, pos, item):
        """指定位置添加元素
            :param pos 從0開始
        """
        if pos < 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            pre = self.__head
            count = 0
            while count < (pos - 1):
                count += 1
                pre = pre.next
            node = Node(item)
            node.next = pre.next
            pre.next = node

    def remove(self, item):
        """刪除節(jié)點"""
        """
            1. 頭節(jié)點
            2. 尾節(jié)點
            3. 中間節(jié)點
            4. 只存在一個節(jié)點
            5. 空鏈表
            6. 首節(jié)點就是刪除的節(jié)點
        """
        if self.is_empty():
            return
        cur = self.__head
        pre = None
        while cur.next != self.__head:
            if cur.elem == item:
                if cur == self.__head:
                    # 頭節(jié)點的情況
                    # 找到尾節(jié)點
                    rear = self.__head
                    # 為了順利把尾節(jié)點的指針指向到頭節(jié)點，先把指針便利到尾部
                    while rear.next != self.__head:
                        rear = rear.next
                    self.__head = cur.next
                    rear.next = self.__head
                else:
                    # 中間節(jié)點
                    pre.next = cur.next
                return
            else:
                # 兩個游標順次往鏈表后邊移動
                pre = cur
                cur = cur.next
        # 尾部情況
        # 退出循環(huán)，cur指向尾節(jié)點
        if cur.elem == item:
            if self.__head == cur:
                # 只有一個節(jié)點
                self.__head = None
            else:
                pre.next = cur.next

    def search(self, item):
        """查找節(jié)點是否存在"""
        if self.is_empty():
            return False
        cur = self.__head
        while cur.next != self.__head:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        # 退出循環(huán)，cur指向尾節(jié)點        
        if cur.elem == item:
            return True
        return False

if __name__ == "__main__":
    scll = SingleCycleLinkList()
    print("is_empty", scll.is_empty())
    print("length", scll.length())

    scll.append(100)
    print("is_empty", scll.is_empty())
    print("length", scll.length())

    scll.append(22)
    scll.add(7)
    scll.append(20)
    scll.insert(2, 777)

    scll.travel()
    scll.remove(7)
    scll.travel()

線性表：順序表（連續(xù)存放），鏈表（離散存放）。存儲線性的數(shù)據(jù)。 --> 解決數(shù)據(jù)怎么存放的問題

棧與隊列基礎

棧：容器，可以利用線性表的特性，來實現(xiàn)數(shù)據(jù)的操作。

由于棧數(shù)據(jù)結構只允許在一端進行操作，因而按照后進先出（LIFO, Last In First Out）的原理運作。

棧的實現(xiàn)

在python的list是順序表，借助list來實現(xiàn)棧.

棧頂：棧的頭部
棧低：棧的底部

#coding=utf-8


class Stack(object):
    """棧"""
    def __init__(self):
        self.__list = []

    def push(self, item):
        """添加一個新的元素item到棧頂"""
        self.__list.append(item)
        # 確定是尾部還是頭部插入數(shù)據(jù)
        # 選擇在尾部添加，而非頭部插入，順序表對于尾部操作的時間復雜度是O(1)
        # self.__list.insert(0, item)
    def pop(self):
        """彈出棧頂元素"""
        return self.__list.pop()
        # self.__list.pop(0)

    def size(self):
        """返回棧的元素個數(shù)"""
        return len(self.__list)

    def is_empty(self):
        """判斷棧是否為空"""
        # "", 0, {}, [], ()
        return self.__list == []

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

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

    stack.push(11)
    stack.push(1000)
    print(stack.size(), "stack.size()")
    print(stack.pop(), "stack.pop()")

隊列（queue）是只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。
隊列不允許在中間部位進行操作。

可以在tree中使用.

隊列

隊列頭：取的那一端，叫做隊頭
隊列尾：添加隊一端，叫做隊尾

隊列

#coding=utf-8


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

    def enqueue(self, item):
        """往隊列中添加一個item元素"""
        self.__list.append(item) # 尾部插入
        # self.__list.insert(0, item) # 頭部插入

    def dequeue(self):
        """從隊列頭部刪除一個元素"""
        return self.__list.pop(0) # 尾部刪除
        # return self.__list.pop() # 頭部刪除

    def is_empty(self):
        """判斷一個隊列是否為空"""
        return not self.__list

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

if __name__ == "__main__":

    queue = Queue()
    queue.enqueue(10)
    queue.enqueue(13)

    print(queue.size())
    print(queue.dequeue())

雙端隊列

兩端都可以出隊列，也都可以入隊列。

#coding=utf-8

class Dqueue(object):
    """雙端隊列"""
    def __init__(self):
        self.__list = []

    def add_front(self, item):
        """添加一個新的元素item到棧頂"""
        self.__list.insert(0, item) # 頭部添加

    def add_rear(self, item):
        self.__list.append(item) # 尾部添加

    def pop_fornt(self):
        return self.__list.pop(0)
    
    def pop_rear(self):
        return self.__list.pop()

    def size(self):
        """返回棧的元素個數(shù)"""
        return len(self.__list)

    def is_empty(self):
        """判斷棧是否為空"""
        # "", 0, {}, [], ()
        return self.__list == []

if __name__ == "__main__":
    dq = Dqueue()

    dq.add_front(11)
    dq.add_front(100)
    dq.add_rear(1000)
    print(dq.size(), "dq.size()")
    print(dq.pop_fornt(), "dq.pop_fornt()")

排序算法：是一種能將一串數(shù)據(jù)依照特定順序進行排列的一種算法。

排序算法的穩(wěn)定性

穩(wěn)定排序算法會讓原本有相等鍵值的記錄維持相對次序。也就是如果一個排序算法是穩(wěn)定的，當有兩個相等鍵值的紀錄R和S，且在原本的列表中R出現(xiàn)在S之前，在排序過的列表中R也將會是在S之前。（特指排序條件相等的兩個元素，排序后的順序是否和排序前一致。有時候需要按照多個條件排序）

如果排序算法是穩(wěn)定的，可以先按照第一個條件排序后再按照其它條件排序，則結果就是想要的。若果是不穩(wěn)定的排序，需要額外的步驟保證結果的正確性。

冒泡排序

比較相鄰的元素。如果第一個比第二個大（升序），就交換它們兩個。

對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。

針對所有的元素重復以上的步驟，除了最后一個。

持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

#condig-utf8

def bubble_sort(alist):
    """冒泡排序"""
    n = len(alist)

    # 走多少次
    # 從頭走到尾

    for j in range(n - 1):# 走多少次
        count = 0
        for i in range(0, n - 1 - j): # 從頭走到尾
            if alist[i] > alist[i+1]:
                # 位置調(diào)換
                alist[i], alist[i+1] = alist[i+1], alist[i]
                count += 1
        if 0 == count: # 常量 ，變量
            return

    # i 0 ~ n-2  range(0, n-1) j=0
    # i 1 ~ n-3  range(0, n-1-1) j=1
    # i 2 ~ n-4  range(0, n-1-1-1) j=2
    # j=n i range(0, n-1-j)

if __name__ == "__main__":
    li = [54, 26, 93, 17, 77, 34]
    bubble_sort(li)
    print(li)

時間復雜度：

最優(yōu)時間復雜度：O(n) （表示遍歷一次發(fā)現(xiàn)沒有任何可以交換的元素，排序結束。）

最壞時間復雜度：O(n^2)

穩(wěn)定性：穩(wěn)定

選擇排序

從未排序的列表中選擇一個最小的排到前面去

# alist = [12, 34, 3453, 456, 4, 45, 2, 5, 100]
#           0   1   2    3    4   5  6  7  8

# min = 0
# min = 6
# alist[0], alist[6] = alist[6], alist[0]



# alist = [2,     34, 3453, 456, 4, 45, 12, 5, 100]
#           0      1    2    3   4  5    6  7   8

# min = 1
# min = 4
# alist[1], alist[4] = alist[4], alist[1]

# 從未排序的列表中選擇一個最小的排到前面去


# 選擇排序，看未排序的后邊部分

# 插入排序，把未排序的序列放在，已經(jīng)排序的序列那一個位置中。

# 比較的位置
# j = 0
# min = 0 + 1

# j = 1
# min = 1 + 1

alist = [12, 34, 3453, 456, 4, 45, 2, 5, 100]

def select_sort(alist):
  """選擇排序"""
  n = len(alist)

  for j in range(0, n-1): # 產(chǎn)生n-2, 這邊需要寫n-1, 及 (0 ~ n-2)
    min_index = j
    for i in range(j+1, n): # 需要到 (n-1) 的位置  時間復雜度：1-n, 2-n, 3-n
    # 分為左右兩邊，完成的序列 和 未完成的序列
      if alist[min_index] > alist[i]:
        min_index = i
    alist[j], alist[min_index] = alist[min_index], alist[j]


print(alist)
select_sort(alist)
print(alist)

時間復雜度：

最優(yōu)時間復雜度：O(n^2)

最壞時間復雜度：O(n^2)

穩(wěn)定性：不穩(wěn)定（考慮升序每次選擇最大的情況）

相同數(shù)據(jù)中，排列之后的位置一樣，具有穩(wěn)定性。

插入排序

#coding=utf-8

li = [54, 26, 93, 17, 77, 34]

# 后續(xù)的無需序列，與前面的有序序列中的最后一個元素比較

def insert_sort(alist):
    n = len(alist)
    # 從右邊的無序序列中取出多少個元素執(zhí)行這個的過程
    for j in range(0, n):
        i = j
        # 執(zhí)行從右邊的無序序列中取出第一個元素，即i位置的元素，然后將其插入到前面正確的位置中
        while i > 0: 
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
                i -= 1
            else:
                break

print(li)
insert_sort(li)
print(li)

時間復雜度：

最優(yōu)時間復雜度：O(n) （升序排列，序列已經(jīng)處于升序狀態(tài)）

最壞時間復雜度：O(n^2)

穩(wěn)定性：穩(wěn)定

希爾排序

插入排序的改進版本

#coding=utf-8
alist = [12, 34, 3453, 456, 4, 45, 2, 5, 100]

def shell_sort(alist):
    """希爾排序"""
    n = len(alist) # n = 9
    gap = n // 2 # n = 4

    # i = 1
    # i = gap
    # gap變化到0之前，插入算法執(zhí)行到次數(shù)
    while gap > 0: # 可以等于0
        # 希爾算法 與普通的 插入算法的區(qū)別就是 gap 步長
        for j in range(gap, n): # 一次性循環(huán)全部處理完成
            # 控制子序列中的所有元素
            # j = [gap, gap+1, gap+2, gap+3, ... , n-1]
            i = j
            while i > 0: # 控制子序列中的比較和交換的算法
                if alist[i] < alist[i-gap]:
                    alist[i], alist[i-gap] = alist[i-gap], alist[i]
                    i -= gap
                else:
                    break
        gap //= 2 # 縮短gap步長


print(alist)
shell_sort(alist)
print(alist)

時間復雜度：

最優(yōu)時間復雜度：根據(jù)步長序列的不同而不同

最壞時間復雜度：O(n^2)

穩(wěn)定性：不穩(wěn)定

快速排序

一個數(shù)字，在序列的那個位置。按照當前的數(shù)字，每次分開兩部分。

步驟：

從數(shù)列中挑出一個元素，稱為"基準"（pivot），

重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)結束之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。

遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。

核心代碼:
取第一個位置保存中間值(middle_value), 第一個位置是空位置，就該high的位置來判斷了，當合適就換位置，并且移動對方的指針（low），當不合適移動當前指針(high)。

middle_value = 10

low = 0
high = len(list)

if alist[high] < middle_value:
    alist[low] = alist[high]
    low += 1
elif alist[high] > middle_value:
    high -= 1
    
if alist[low] < middle_value:
    alist[high] = alist[low]
    hight -= 1
elif alist[low] > middle_value:
    low += 1
    
if low == high:    
    alist[low] = middle_value            

#conding=utf-8

def quick_sort(alist, first, last):
    """快速排序"""
    if first >= last:
        return

    # mid_value = alist[0] # 中間值
    mid_value = alist[first] # 中間值
    # n = len(alist)
    # 左右游標
    # low = 0
    low = first
    # high = n-1
    high = last

    while low < high:
        # high 游標 左移動
        while low < high and alist[high] >= mid_value:
            high -= 1
        alist[low] = alist[high]
        # low += 1

        # low 游標 右移動
        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] = alist[low]
        # high -= 1

        # 等于的情況放到其中一邊去處理
        # 為了保證二個指針不錯過，注釋 【low += 1】和 【high -= 1】

    # 退出循環(huán)的時候，low == high
    alist[low] = mid_value # 中間值賦值到該位置

    # 遞歸
    # 對low左邊的列表執(zhí)行快速排序
    quick_sort(alist, first, low-1)
    # 對low右邊的列表執(zhí)行快速排序
    quick_sort(alist, low+1, last)

if __name__ == "__main__":
    li = [54, 26, 93, 17, 77, 34]
    print(li)
    quick_sort(li, 0, len(li)-1)
    print(li)

時間復雜度：

最優(yōu)時間復雜度：O(nlogn): 2*2*2... = n, n個元素對2取對數(shù)。 log2(n)以2為底的對數(shù)

最壞時間復雜度：O(n^2)

穩(wěn)定性：不穩(wěn)定

時間復雜度不好從代碼中分析，通過畫圖中理解每次循環(huán)中操作。橫向和縱向來區(qū)分判斷。

歸并排序

先把序列從頭開始往下拆，直到只有一個元素。緊接著開始，二個部分合并到一起，然后再次合并，直到完成序列合并。

需要使用到遞歸。

#coding=utf-8

def merge_sort(alist):
  """歸并排序"""

  """
    分裂
  """
  n = len(alist)
  if n <= 1:
    return alist
  mid = n // 2
  # left, right 采用歸并排序后形成的有序的新的列表
  left_li = merge_sort(alist[:mid]) # 傳新的列表
  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:] # 加上剩下數(shù)據(jù)
  result += right_li[right_pointer:]
  return result

alist = [1, 23, 34, 6,2, 12, 12, 1, 2]
print(alist)
new_alist = merge_sort(alist) # 返回新的列表
print(new_alist)

時間復雜度：

最優(yōu)時間復雜度：O(nlogn), 2*2*2... = n, n個元素對2取對數(shù)。 log2(n)以2為底的對數(shù)

最壞時間復雜度：O(nlogn)

穩(wěn)定性：穩(wěn)定

搜索：在一個項目集合中找到特定項目的算法過程。
搜索結果：通常的答案是真或假,因為該項目是否存在。

常見搜索方法：順序查找，二分法查找，二叉樹查找，哈希查找

二分查找

二分查找，需要定位到索引，也就是說，只能作用到順序表上，而且是排序過后的，有序順序表中。

非遞歸實現(xiàn)
需要關注：頭和尾的下標，來計算二分位置的下標。（原因在原有的列表上去找）
指明查找的范圍，需要二個指針來控制前后移動

def binary_search_2(alist, item):
  """二分查找"""
  n = len(alist)
  first = 0
  last = n - 1
  while first <= last: # 中間最小之后一個值，需要包含等于
    mid = (first + last) // 2
    if alist[mid] == item:
      return True
    elif item < alist[mid]:
      last = mid - 1
    else:
      first = mid + 1
  return False

遞歸實現(xiàn)

def binary_search(alist, item):
  """二分查找"""
  n = len(alist)
  if n > 0:
    mid = n//2 # 新的列表

    if alist[mid] == item:
      return True
    elif item < alist[mid]:
      return binary_search(alist[:mid], item)
    else:
      return binary_search(alist[mid+1:], item)
  return False

時間復雜度：

最優(yōu)時間復雜度：O(1)

最壞時間復雜度：O(logn)

用來模擬具有樹狀結構性質的數(shù)據(jù)集合，它是由n(n>=1)個有限節(jié)點組成一個具有層次關系的集合。

二叉樹是二維空間上的表現(xiàn)，圖是三維空間上的表現(xiàn)。

特點：

每個節(jié)點有零個或多個子節(jié)點（每個節(jié)點都會有數(shù)據(jù)區(qū)和鏈接區(qū)）

沒有父節(jié)點的節(jié)點稱為根節(jié)點

每一個非根節(jié)點有且只有一個父節(jié)點

除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹(每個節(jié)點只有一個父級)

樹的術語

節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度（有幾個下級，幾個下級子節(jié)點）

樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度；

葉節(jié)點或終端節(jié)點：度為零的節(jié)點；

父親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點；

孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點；

兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點；

節(jié)點的層次：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推；

樹的高度或深度：樹中節(jié)點的最大層次；

堂兄弟節(jié)點：父節(jié)點在同一層的節(jié)點互為堂兄弟；

節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點；

子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。

森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

樹的種類

無序樹：樹中任意節(jié)點的子節(jié)點之間沒有順序關系，這種樹稱為無序樹，也稱為自由樹；

有序樹：樹中任意節(jié)點的子節(jié)點之間有順序關系（樹的節(jié)點直接有某種特殊的意義在），這種樹稱為有序樹；

二叉樹：每個節(jié)點最多含有兩個子樹的樹稱為二叉樹（節(jié)點的度最高到2）

完全二叉樹：對于一顆二叉樹，假設其深度為d(d>1)。除了第d層外，其它各層的節(jié)點數(shù)目均已達最大值，且第d層所有節(jié)點從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹，其中滿二叉樹的定義是所有葉節(jié)點都在最底層的完全二叉樹

平衡二叉樹（AVL樹）：當且僅當任何節(jié)點的兩棵子樹的高度差不大于1的二叉樹

排序二叉樹（二叉查找樹（英語：Binary Search Tree），也稱二叉搜索樹、有序二叉樹）

霍夫曼樹（用于信息編碼）：帶權路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹

B樹：一種對讀寫操作進行優(yōu)化的自平衡的二叉查找樹，能夠保持數(shù)據(jù)有序，擁有多余兩個子樹

樹的存儲與表示

雖然樹是二維的，但是可以用一維的順序表存儲起來。

順序存儲：將數(shù)據(jù)結構存儲在固定的數(shù)組中，然在遍歷速度上有一定的優(yōu)勢，但因所占空間比較大，是非主流二叉樹。二叉樹通常以鏈式存儲。(把連續(xù)的空間和樹上的節(jié)點做對應關系。按照節(jié)點的層次來存儲數(shù)據(jù))

鏈式存儲：缺陷，指針域指針個數(shù)不定

由于對節(jié)點的個數(shù)無法掌握，常見樹的存儲表示都轉換成二叉樹進行處理，子節(jié)點個數(shù)最多為2

最常用的樹的存儲，是鏈式存儲，多存儲后記鏈接區(qū)。

常見應用場景

xml，html等，那么編寫這些東西的解析器的時候，不可避免用到樹

路由協(xié)議就是使用了樹的算法

mysql數(shù)據(jù)庫索引

文件系統(tǒng)的目錄結構

所以很多經(jīng)典的AI算法其實都是樹搜索，此外機器學習中的decision tree也是樹結構

二叉樹介紹

每個節(jié)點最多有兩個子樹的樹結構。(最大的度只能是2)
通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）

二叉樹的數(shù)學上的一些性質(特性)

在二叉樹的第i層上至多有2^(i-1)個結點（i>0）

深度為k的二叉樹至多有2^k - 1個結點（k>0）

對于任意一棵二叉樹，如果其葉結點數(shù)為N0（度數(shù)為0），而度數(shù)為2的結點總數(shù)為N2，則N0=N2+1;

具有n個結點的完全二叉樹的深度必為 log2(n+1)(和特性2在數(shù)學上是相反的)

對完全二叉樹，若從上至下、從左至右編號，則編號為i 的結點，其左孩子編號必為2i，其右孩子編號必為2i＋1；其雙親的編號必為i/2（i＝1 時為根,除外）

二叉樹的實現(xiàn)

添加的方式：二叉樹的廣度優(yōu)先遍歷（廣度層次遍歷），通過隊列，取出頭的元素，判斷是否有左子節(jié)點與右子節(jié)點，如果都有往隊列中添加，如果沒有，掛載到節(jié)點上。

深度遍歷：

先序遍歷（從最小的三個節(jié)點二叉樹的先根節(jié)點遍歷，左子節(jié)點，右子節(jié)點的遍歷）-> 根，左，右

中序遍歷（把根放到中間，就是左子節(jié)點，根，右子節(jié)點的順序遍歷）-> 左，根，右

后序遍歷（把根放到最后一個上面，左子節(jié)點，右子節(jié)點的順序遍歷）-> 左，右，根

無論把根放到那個位置上，子節(jié)點都是先左邊后右邊

#coding=utf-8

class Node(object):
    """節(jié)點類"""
    def __init__(self, item):
        self.elem = item
        self.lchild = None
        self.rchild = None

class Tree(object):
    """二叉樹"""
    def __init__(self):
        self.root = None        

    # 插入 （廣度優(yōu)先遍歷）
    def add (self, item):
        node = Node(item)
        if self.root is None:
            self.root = node
            return
        queue = [self.root]

        while queue: # 不為空列表
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)
            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)
    def breadth_travel(self):
        """廣度遍歷"""
        """層次遍歷"""
        if self.root is None:
            return
        queue = [self.root]

        while queue:
            cur_node = queue.pop(0)
            print(cur_node.elem, end=" ")
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)
    def preorder(self, node): # 中序，先序，后序，根節(jié)點都在變化，為了調(diào)用自身，而且是調(diào)用不同的子樹，所以根節(jié)點作為參數(shù)傳入
        """先序遍歷"""
        if node is None:
            return
        print(node.elem, end=" ") # 根
        self.preorder(node.lchild) # 左邊
        self.preorder(node.rchild) # 右邊

    def inorder(self, node):
        """中序遍歷"""
        if node is None:
            return
        self.inorder(node.lchild)
        print(node.elem, end=" ")
        self.inorder(node.rchild)
    
    def postorder(self, node):
        """后序遍歷"""
        if node is None:
            return
        self.postorder(node.lchild)
        self.postorder(node.rchild)
        print(node.elem, end=" ")

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.breadth_travel()
    print(" ")
    tree.preorder(tree.root)
    print(" ")
    tree.inorder(tree.root)
    print(" ")
    tree.postorder(tree.root)
    print(" ")

層次遍歷： 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

給出遍歷結果，然后確定一顆二叉樹。給其中二個種遍歷結果，就可以寫出二叉樹（先序和中序，或者，中序和后序），一定需要一個中序，不然，左右子樹無法分開。