筆記——Python數(shù)據(jù)結(jié)構(gòu)與算法

一、棧和隊(duì)列

1.1 棧的定義

棧、隊(duì)列、雙端隊(duì)列和列表都是有序的數(shù)據(jù)集合， 其元素的順序取決于添加順序或移除順序。一旦某個(gè)元素被添加進(jìn)來(lái)，它與前后元素的相對(duì)位置將保持不變。這樣的數(shù)據(jù)集合經(jīng)常被稱為線性數(shù)據(jù)結(jié)構(gòu)。

棧的添加操作和移除操作總發(fā)生在同一端。棧中的元素離底端越近，代表其在棧中的時(shí)間越長(zhǎng)，因此棧的底端具有非常重要的意義。最 新添加的元素將被最先移除。這種排序原則被稱作 LIFO（last-in first-out），即后進(jìn)先出。它提供了一種基于在集合中的時(shí)間來(lái)排序的方式。最近添加的元素靠近頂端，舊元素則靠近底端。

1.2 棧的實(shí)現(xiàn)

代碼實(shí)現(xiàn)：（注：定義棧頂位于列表末尾）

class Stack:
    def __init__(self):
        self.items = []
    # 判斷棧是否為空
    def isEmpty(self):
        return self.items == []
    # 入棧，使用列表中的append方法
    def push(self,item):
        self.items.append(item)
    # 出棧，使用列表中的pop方法
    def pop(self):
        return self.items.pop()
    # 返回棧頂元素
    def peek(self):
        return self.items(len(self.items)-1)
    # 返回棧的大小
    def size(self):
        return len(self.items)

## 棧的應(yīng)用
a = Stack()
a.isEmpty()
>> True
a.push(4)
a.size()
>> 2
a.pop()
>> 4

?

1.3 應(yīng)用案例一（括號(hào)匹配）

案例描述:從左到右讀取一個(gè)括號(hào)串，然后判斷其中的括號(hào)是否匹配。匹配括號(hào)是指每一個(gè)左括號(hào)都有與之對(duì)應(yīng)的一個(gè)右括號(hào)，并且括號(hào)有正確的嵌套關(guān)系。下面是正確匹配的括號(hào)串：（）（）（）；（（（）））

解決思路：為了解決這個(gè)問(wèn)題，需要注意到一個(gè)重要現(xiàn)象。當(dāng)從左到右處理括號(hào)時(shí)，最右邊的無(wú)匹配左括號(hào) 必須與接下來(lái)遇到的第一個(gè)右括號(hào)相匹配，如下圖所示。并且，在第一個(gè)位置的左括號(hào)可能要 等到處理至最后一個(gè)位置的右括號(hào)時(shí)才能完成匹配。相匹配的右括號(hào)與左括號(hào)出現(xiàn)的順序相反。這一規(guī)律暗示著能夠運(yùn)用棧來(lái)解決括號(hào)匹配問(wèn)題。

# 導(dǎo)入Stack類
from pythonds.basic import Stack
# 定義括號(hào)匹配函數(shù)
def parCherker(symbolString):
    # 實(shí)例化stack類
    s = Stack()
    # 設(shè)置balanced 為T(mén)rue 一個(gè)標(biāo)志位
    balanced = True
    # 初始化序號(hào)0
    index = 0
    # 當(dāng)index符合要求時(shí)，遍歷symbolString
    while index < len(symbolString) and balanced:
        # 獲取括號(hào)
        symbol = symbolString[index]
        # 如果是左括號(hào)壓入堆棧
        if symbol == '(':
            s.push(symbol)
        # 若是右括號(hào)則進(jìn)一步判斷
        else:
            # 如果堆棧為空，則設(shè)置標(biāo)志位為False，跳出循環(huán)
            if s.isEmpty():
                balanced = False
            # 否則返回棧頂括號(hào)，即遇到")"返回棧頂括號(hào)
            else:
                s.pop()
        index = index + 1
    # 所有括號(hào)匹配并且棧為空，返回TRUE
    if balanced and s.isEmpty():
        return True
    else:
        return False

1.3 應(yīng)用案例二（十進(jìn)制轉(zhuǎn)換）

案例描述：?利用棧將十進(jìn)制轉(zhuǎn)換為二進(jìn)制

解決思路：如下圖所示，每次將整數(shù)除以2然后取余，將所得余數(shù)壓入棧中，隨后出棧逆序輸出。

def divideBy2(decNumber):
    # 實(shí)例化堆棧
    remstack = Stack()
    # 判斷為整數(shù)
    while decNumber > 0:
        # 除2取余
        rem = decNumber %2
        # 將其壓入堆棧
        remstack.push(rem)
        # 取整數(shù)
        decNumber = decNumber //2
    # 初始化字符串
    binString = ''
    # 將堆棧的值逆序取出
    while not remstack.isEmpty():
        binString = binString + str(remstack.pop())

    return binString

二、隊(duì)列

2.1 隊(duì)列的定義

隊(duì)列是有序集合，添加操作發(fā)生在“尾部”，移除操作則發(fā)生在“頭部”（頭刪尾插）。新元素從尾部進(jìn)入隊(duì)列，然后一直向前移動(dòng)到頭部，直到成為下一個(gè)被移除的元素。最新添加的元素必須在隊(duì)列的尾部等待，在隊(duì)列中時(shí)間最長(zhǎng)的元素則排在最前面。這種排序原則被稱作 FIFO（first-in first-out），即先進(jìn)先出，也稱先到先得。隊(duì)列的存儲(chǔ)結(jié)構(gòu)有順序隊(duì)或鏈隊(duì)，主要以循環(huán)隊(duì)列更為常見(jiàn)。根據(jù)其隊(duì)列的存儲(chǔ)方式的區(qū)別其實(shí)現(xiàn)方式也有所差異。

2.2 隊(duì)列的常見(jiàn)應(yīng)用

• 脫機(jī)打印輸出:按申請(qǐng)的先后順序依次輸出。
• 多用戶系統(tǒng)中，多個(gè)用戶排成隊(duì)，分時(shí)地循環(huán)使用CPU和主存。
• 按用戶的優(yōu)先級(jí)排成多個(gè)隊(duì)，每個(gè)優(yōu)先級(jí)一個(gè)隊(duì)列
• 實(shí)時(shí)控制系統(tǒng)中，信號(hào)按接收的先后順序依次處理
• 網(wǎng)絡(luò)電文傳輸，按到達(dá)的時(shí)間先后順序依次進(jìn)行

2.3 隊(duì)列的實(shí)現(xiàn)

def Queue:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    # 在隊(duì)頭插入
    def enqueue(self,item):
        self.items.insert(0,item)
    # 在隊(duì)尾出棧
    def dequeue(self):
        return self.items.pop()
    # 計(jì)算隊(duì)列的大小
    def size(self):
        return len(self.items)

## 隊(duì)列的操作
q = Queue()
q.isEmpty()
>> True
q.enqueue('dog')
q.enqueue(4)
q.enqueue(True)
q.size()
>> 3
q.deque()
>> 'dog'

2.4 應(yīng)用案例一（擊鼓傳花）

案例描述：該程序接受一個(gè)名字列表和一個(gè)用于計(jì)數(shù)的常 量 num，并且返回最后一人的名字。 我們使用隊(duì)列來(lái)模擬一個(gè)環(huán)。假設(shè)握著土豆的孩子位于隊(duì)列的頭部。在模擬傳土豆的過(guò)程中，程序?qū)⑦@個(gè)孩子的名字移出隊(duì)列，然后立刻將其插入隊(duì)列的尾部。隨后，這個(gè)孩子會(huì)一直等待，直到再次到達(dá)隊(duì)列的頭部。在出列和入列 num 次之后，此時(shí)位于隊(duì)列頭部的孩子出局，新一輪游戲開(kāi)始。如此反復(fù)，直到隊(duì)列中只剩下一個(gè)名字（隊(duì)列的大小為 1）。

解決思路：隊(duì)列結(jié)構(gòu)是一個(gè)循環(huán)隊(duì)列的結(jié)構(gòu)，即出列后的元素再進(jìn)列

from pythonds.basic import Queue
# 傳入兩個(gè)參數(shù)，namelist和num
def hotPotato(namelist, num):
    # 定義一個(gè)空列表
    simqueue = Queue()
    # 遍歷namelist
    for name in namelist:
        # 將所有name傳入隊(duì)列中
        simqueue.enqueue(name)
    # 當(dāng)隊(duì)列中的元素大于1時(shí)，進(jìn)行擊鼓傳花的游戲
    while simqueue.size() >1:
        # 進(jìn)行num次循環(huán)
        for i in range(num):
            # 每次將頭部出隊(duì)列，在尾部加入隊(duì)列
            simqueue.enqueue(simqueue.dequeue())
        # 當(dāng)num次循環(huán)結(jié)束后，返回當(dāng)前頭部的隊(duì)列
        simqueue.dequeue()
    return simqueue.dequeue()

三、鏈表

3.1 鏈表的定義

? 在了解鏈表的定義之前，需要知道什么是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)其結(jié)點(diǎn)在存儲(chǔ)器中的位置是任意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。鏈表就相當(dāng)于無(wú)序列表。

? 為了實(shí)現(xiàn)無(wú)序列表，我們要構(gòu)建鏈表。無(wú)序列表需要維持元素之間的相對(duì)位置，但是并不需要在連續(xù)的內(nèi)存空間中維護(hù)這些位置信息。

? 需要注意的是，必須指明列表中第一個(gè)元素的位置。一旦知道第一個(gè)元素的位置，就能根據(jù) 其中的鏈接信息訪問(wèn)第二個(gè)元素，接著訪問(wèn)第三個(gè)元素，依此類推。指向鏈表第一個(gè)元素的引用被稱作頭。最后一個(gè)元素需要知道自己沒(méi)有下一個(gè)元素。

3.2 鏈表的構(gòu)建

??節(jié)點(diǎn)（node）是構(gòu)建鏈表的基本數(shù)據(jù)結(jié)構(gòu)。每一個(gè)節(jié)點(diǎn)對(duì)象都必須持有至少兩份信息。首先， 節(jié)點(diǎn)必須包含列表元素，我們稱之為節(jié)點(diǎn)的數(shù)據(jù)變量。其次，節(jié)點(diǎn)必須保存指向下一個(gè)節(jié)點(diǎn)的引用。

? 注意，Node 的構(gòu)造方法將 next 的初始值設(shè)為 None。由于這有時(shí)被稱為“將節(jié)點(diǎn)接地”，因此我們使用接地符號(hào)來(lái)代表指向 None 的引用。將 None 作為 next 的初始值是不錯(cuò)的做法。

## 節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)的構(gòu)建
class Node：
    # 初始化
    def __init__(self,initdata):
        self.data = initdata
        self.next = None
    # 查（每次需要設(shè)置兩個(gè)部分）
    def getData(self):
        return self.data
    def getNext(self):
        return self.next
    # 改（每次修改設(shè)置兩個(gè)部分）
    def setData(self,newdata):
        self.data = newdata
    def setNext(self,newnext):
        self.next = newnext

? 鏈表是基于節(jié)點(diǎn)集合來(lái)構(gòu)建的，每個(gè)節(jié)點(diǎn)都通過(guò)顯示的引用指向下一個(gè)節(jié)點(diǎn)。只要知道第一個(gè)節(jié)點(diǎn)的位置（包括第一個(gè)節(jié)點(diǎn)包含第一個(gè)元素），其后的每個(gè)元素都能通過(guò)下一個(gè)引用找到。因此每次查找某個(gè)元素時(shí)，都需要從第一個(gè)元素開(kāi)始尋找。

class UnorderedList:
    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head == None
    # 增
    def add(self，item):
        temp = Node(item)
        temp.setNext(self.head) # 將新節(jié)點(diǎn)的末尾與頭節(jié)點(diǎn)進(jìn)行連接
        self.head = temp # 將頭節(jié)點(diǎn)設(shè)置為新加入的節(jié)點(diǎn)
    # 計(jì)算長(zhǎng)度    
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count = count +1
            current = current.getNext()
        return count
    # 查
    def search(self,item);
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

    # 刪
    def remove(self,item):
        current = self.head # 頭節(jié)點(diǎn)設(shè)置為current
        previous = None # previous設(shè)置為None
        found = False
        while not found:
            if current.getData() == item:
                found = True # 檢查當(dāng)前節(jié)點(diǎn)中的元素是否為要移除的元素
            else:
                previous = current 
                current = current.getNext() # 進(jìn)行蠕動(dòng)
        if previous == None: # 要?jiǎng)h除的節(jié)點(diǎn)正好是頭節(jié)點(diǎn)
            self.head = current.getNext() 
        else: # 要?jiǎng)h除的節(jié)點(diǎn)位于鏈表的中間
            previous.setNext(current.getNext())

? 刪除過(guò)程中必須先將previous移動(dòng)到current的位置，然后再移動(dòng)current。這一過(guò)程類似為"蠕動(dòng)"，previous必須在current向前移動(dòng)之前指向當(dāng)前位置。

3.3 有序列表的構(gòu)建

? 在有序列表中，元素的相對(duì)位置取決于它們的基本特征。它們通常以升序或者降序排列，并 且我們假設(shè)元素之間能進(jìn)行有意義的比較。

class OrderedList:
    def __init__(self):
        self.head = None
    # 與無(wú)序列表相同
    def isEmpty(self):
        return self.head == None
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count = count +1
            current = current.getNext()
        return count

    # 查
    def search(self,item):
        current = self.head
        found = False 
        stop = False
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True 
            else:
                if current.getData() > item:
                    stop = True
                else:
                    current = current.getNext()
        return found

    # 增
    def add(self,item):
        current = self.head
        previous = None
        stop = False
        while current != None and stop:
            if current.getData() > item:
                stop = True
            else:
                previous = current
                current = current.getNext()
        temp = Node(item)
        if previous == None:
            temp.setNext(self.head)
            self.head = temp
        else:
            temp.setNext(current)
            previous.setNext(temp)

通過(guò)增加新的布爾型變量 stop，并將其初始化 為 False，可以將上述條件輕松整合到代碼中。當(dāng) stop 是 False 時(shí)，我們可以繼續(xù)搜索鏈表。如果遇到其值大于目標(biāo)元素的節(jié)點(diǎn)，則將 stop 設(shè)為 True.從而不需要遍歷完全部的鏈表。

四、搜索與排序

4.1 順序搜索

? 從列表中的第一個(gè)元素開(kāi)始，沿著默認(rèn)的順序逐個(gè)查看，直到找到目標(biāo)元素或者查完列表。如果查看列表后仍然沒(méi)有找到目標(biāo)元素，則說(shuō)明目標(biāo)元素不在列表中。

def sequentialSearch(alist,item):
    # 起始指針
    pos = 0
    # 設(shè)置一個(gè)found標(biāo)志位
    found = False
    # 如果指針為超過(guò)列表長(zhǎng)度并且還沒(méi)有找到元素
    while pos < len(alist) and not found :
        if alist[pos] == item:
            found = True
        else:
            pos = pos +1

    return found

時(shí)間復(fù)雜度為O(n)

4.2 二分搜索

? 二分搜索的首要條件是列表必須是有順序的，即從小到大排列或者從大到小排列。二分搜索相較于順序搜索，它的起始元素不是第一個(gè)元素，而是中間元素。其搜索邏輯如下：如果這個(gè)元素就是目標(biāo)元素，那么就立即停止搜索；如果不是，則利用列表的有序性，排除一半元素，再在剩余一半的元素繼續(xù)應(yīng)用二分搜索，直至找到目標(biāo)元素。

def binarySearch(alist,item):
    # 頭指針
    first = 0
    # 尾指針
    last = len(alist) - 1
    # 設(shè)置found標(biāo)志位
    found = False
    # 循環(huán)操作，條件：如果還有搜索空間，并且沒(méi)有找到
    while first <= last and not found:
        # 尋找中間二分點(diǎn)
        midpoint = (first + last)//2
        # 二分點(diǎn)對(duì)左右兩邊進(jìn)行判斷
        if alist(midpoint) == item:
            found = True
        else：
            # 如果目標(biāo)元素比中間元素小，修改尾指針至中間元素的前一個(gè)元素
            if item < alist[midpoint]:
                last = midpoint -1
            # 如果目標(biāo)元素比中間元素大，修改頭指針至中間元素的后一個(gè)元素
            else:
                first = midpoint +1
    return found

4.3 散列

4.3.1 散列表的定義

? 散列是元素的集合，其中一個(gè)元素以一種便于查找的方式存儲(chǔ)。散列表中的每個(gè)位置通常被稱為槽，其中可以存儲(chǔ)一個(gè)元素。散列表的基本思想就是記錄存儲(chǔ)位置與存儲(chǔ)關(guān)鍵字之間的對(duì)應(yīng)關(guān)系，這個(gè)對(duì)應(yīng)關(guān)系我們稱之為哈希函數(shù)。

? 通過(guò)構(gòu)建散列，我們可以得到一個(gè)時(shí)間復(fù)雜度為O(1)的數(shù)據(jù)結(jié)構(gòu)。槽用一個(gè)從0開(kāi)始的整數(shù)標(biāo)記，例如0號(hào)槽，1號(hào)槽等。初始情形下，散列表中沒(méi)有元素，每個(gè)槽都是空的?？梢杂昧斜韥?lái)實(shí)現(xiàn)散列表，并將每個(gè) 元素都初始化為 Python 中的特殊值 None。

4.3.2 散列函數(shù)的定義

? 散列函數(shù)將散列表中的元素與其所屬位置對(duì)應(yīng)起來(lái)。對(duì)散列表中的任一元素，散列函數(shù)返回 一個(gè)介于 0和m – 1之間的整數(shù)。這個(gè)散列函數(shù)可以通過(guò)自定義編碼的方式，將函數(shù)值和槽值對(duì)應(yīng)起來(lái)。常見(jiàn)的散列函數(shù)是取余函數(shù)，具體算法如下：將整數(shù)元素除以表的大小，將得到的余數(shù)作為散列值。

4.3.3 散列表的沖突

? 顯然，當(dāng)每個(gè)元素的散列值是不同的情況下，這個(gè)散列表是完美的，但是如果散列值是相同的情況下，例如77和44，在散列表大小為11的情況下，散列值均為0，此時(shí)散列函數(shù)會(huì)將兩個(gè)元素都放入同一個(gè)槽中，這種情況稱作沖突。處理沖突是散列計(jì)算的重點(diǎn)，因?yàn)槿绻麡?gòu)建想要一個(gè)完美的散列表的話，任何一種散列函數(shù)所耗費(fèi)的內(nèi)存，在預(yù)估元素很多的情況下是相當(dāng)大的。所以，我們需要解決好沖突問(wèn)題，這樣可以進(jìn)一步降低所需內(nèi)存。這里主要有兩種辦法。

? 一種方法是在散列表中找到另一個(gè)空槽，用于放置引起沖突的元素。簡(jiǎn)單的做法是從起初的 散列值開(kāi)始，順序遍歷散列表，直到找到一個(gè)空槽。注意，為了遍歷散列表，可能需要往回檢查第一個(gè)槽。這個(gè)過(guò)程被稱為開(kāi)放定址法，它嘗試在散列表中尋找下一個(gè)空槽或地址。由于是逐個(gè)訪問(wèn)槽，因此這個(gè)做法被稱作線性探測(cè)。

? 另一種處理沖突的方法是讓每個(gè)槽有一個(gè)指向元素集合（或鏈表）的引用。鏈接法允許散列 表中的同一個(gè)位置上存在多個(gè)元素。發(fā)生沖突時(shí)，元素仍然被插入其散列值對(duì)應(yīng)的槽中。不過(guò)， 隨著同一個(gè)位置上的元素越來(lái)越多，搜索變得越來(lái)越困難。圖 5-12 展示了采用鏈接法解決沖突后的結(jié)果。

?

4.3.4 利用散列表來(lái)實(shí)現(xiàn)字典

? 字典是最有用的python集合之一，字典能根據(jù)給定的一個(gè)key，快速找到其關(guān)聯(lián)的value，從而達(dá)到其高效搜索的實(shí)現(xiàn)方案。字典是存儲(chǔ)鍵–值對(duì)的數(shù)據(jù)類型。鍵用來(lái)查 找關(guān)聯(lián)的值，這個(gè)概念常常被稱作映射。映射抽象數(shù)據(jù)類型定義如下。它是將鍵和值關(guān)聯(lián)起來(lái)的無(wú)序集合，其中的鍵是不重復(fù)的，鍵和值之間是一一對(duì)應(yīng)的關(guān)系。

# 初始長(zhǎng)度為11的散列表的創(chuàng)建
class HashTable:
    def __init__(self):
        # 設(shè)置散列表的大小
        self.size = 11 
        # 設(shè)置兩個(gè)列表，一個(gè)存放鍵，一個(gè)存放值
        self.slots = [None]*self.size
        self.data = [None]*self.size 
    # 增，參數(shù)鍵值對(duì)
    def put(self,key,data):
        # 定義hashfunction為簡(jiǎn)單的取余函數(shù)，hashfunction返回的是散列值
        hashvalue = self.hashfunction(key,len(self.slots))
        # 如果散列表當(dāng)前位置為空，則直接添加
        if self.slots[hashvalue] == None:
            # slots存放鍵，在列表的散列值處存放鍵
            self.slots[hashvalue] = key
            # data存放值，在列表的散列值處存放值，這樣實(shí)現(xiàn)了鍵和值的一一對(duì)應(yīng)（通過(guò)散列值）
            self.data[hashvalue] = data
        # 如果散列表當(dāng)前位置不為空，有沖突
        else:
            # 如果鍵相同，值不同，則直接將原來(lái)的值修改，參考字典修改值的操作
            if self.slots[hashvalue] == key:
                self.data[hashvalue] = data
            # 如果鍵不同，但是散列值相同
            else:
                # 再散列操作，定義一個(gè)nextslot變量
                nextslot = self.rehash(hashvalue,len(self.slots))
                # 如果再散列后的槽中的值不是空，并且鍵不相同，繼續(xù)再散列操作
                while self.slots[nextslot] != None and self.slots[nextslot] != key:
                    nextslot = self.rehash(nextslot,len(self.slots))
                # 設(shè)置鍵值對(duì)
                if self.slots[nextslot] == None:
                    self.slots[nextslot] = key
                    self.data[nextslot] = data 
                else:
                    self.data[nextslot] = data


    # 取余哈希函數(shù)
    def hashfunction(self,key,size):
        return key%size 
    # 再哈希
    def rehash(self,oldhash,size):
        return (ordhash+1)%size

    # 查
    def get(self,key):
        # 獲取散列值
        startslot = self.hashfunction(key,len(self.slots))
        # 設(shè)置三個(gè)標(biāo)志位
        data = None
        stop = False
        found = False
        position = startslot
        # 如果當(dāng)前當(dāng)前散列值的槽不為空且沒(méi)有找到也沒(méi)有停止（因?yàn)橛袥_突的存在，所以有可能再散列）
        while self.slots[position] != None and not found and not stop:
            # 如果找到該鍵則跳出循環(huán)，返回data值
            if self.slots[position] == key:
                found = True
                data = self.data[position]
            # 如果鍵發(fā)生沖突，存在再散列操作
            else:
                # 再散列
                position = self.rehash(position,len(self.slots))
                if position == startslot:
                    stop = True
        return data

    def __getitem__(self,key):
        return self.get(key)

    def __setitem__(self,key,data):
        return self.put(key,data)

注：散列表的搜索效率是O(1)，它是以一種空間換時(shí)間的數(shù)據(jù)結(jié)構(gòu)。

4.4 冒泡排序

? 冒泡排序多次遍歷列表。它比較相鄰的元素，將不合順序的交換。每一輪遍歷都將下一個(gè)最 大值放到正確的位置上。本質(zhì)上，每個(gè)元素通過(guò)“冒泡”找到自己所屬的位置。

?

# 冒泡排序
def bubbleSort(alist):
    # 左閉右開(kāi)，逆序遞減
    for passnum in range(len(alist)-1,0,-1):
        # 第一輪比較n-1對(duì)，最大的元素一直往前挪，直到遍歷過(guò)程結(jié)束，逐輪遞減
        for i in range(passnum):
            # 如果前一個(gè)元素比后一個(gè)元素大，則要進(jìn)行轉(zhuǎn)移數(shù)值的操作
            if alist[i] > alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

?

4.5 選擇排序

? 選擇排序在冒泡排序的基礎(chǔ)上做了改進(jìn)遍歷列表時(shí)只進(jìn)行一次交換，選擇排序在每次遍歷時(shí)尋找最大值，并在遍歷完之后將它放到正確位置上。和冒泡排序一樣，每次遍歷完后，當(dāng)前最大的元素就位。

# 選擇排序
def selectionSort(alist):
    # 類似冒泡排序
    for fillslot in range(len(alist)-1,0,-1):
        # 初始化最大值標(biāo)志位
        positionofMax = 0
        # 左閉右開(kāi)，遍歷未排序的整個(gè)序列，尋找最大值
        for location in range(1,fillslot+1):
            if alist[location] > alist[positionofMax]:
                positionofMax = location
        # 將最大值就位
        temp = alist[fillslot]
        alist[fillslot] = alist[positionofMax]
        alist[positionofMax] = temp
        # 時(shí)間復(fù)雜度與冒泡排序一致，均為o(n^2)

4.6 插入排序

插入排序的時(shí)間復(fù)雜度也是 2 On ，但原理稍有不同。它在列表較低的一端維護(hù)一個(gè)有序的子列表，并逐個(gè)將每個(gè)新元素“插入”這個(gè)子列表。

# 插入排序
def insertionSort(alist):
    for index in range(1,len(alist)):
        # 獲取當(dāng)前指針和當(dāng)前的元素值
        currentvalue = alist[index]
        position = index
        # 如果當(dāng)前指針大于0并且前一個(gè)元素值大于當(dāng)前的元素值，那么需要調(diào)換操作
        while position > 0 and alist[position-1] > currentvalue:
            # 將前一個(gè)元素值與當(dāng)前元素值交換
            alist[position] = alist[position-1]
            # 并且將指針做減一操作，嘗試一直遍歷到列表頭
            position = position-1
        alist[position] = currentvalue

4.7 歸并排序

? 歸并排序是遞歸算法，每次將一個(gè)列表一分為二。如果列表為空或只有一個(gè)元素，那么從定義上來(lái)說(shuō)它就是有序的（基本情況）。如果列表不止一個(gè)元素，就將列表一分為二，并對(duì)兩部分都遞歸調(diào)用歸并。歸并是指將兩個(gè)較小的有序列表歸并為一 個(gè)有序列表的過(guò)程。

?

def merge(alist,low,mid,high):
    # 第一個(gè)有序列表的第一個(gè)元素
    i = low
    # 第二個(gè)有序列表的第一個(gè)元素
    j = mid+1
    ltmp = []
    # 只要左右兩個(gè)列表都有數(shù)
    while i<=mid and j<=high:
        # 比較兩個(gè)列表當(dāng)前指針的數(shù)的大小
        if alist[i] < alist[j]:
            # 先放入較小的那個(gè)
            ltmp.append(alist[i])
            # i+1
            i+=1
        else:
            ltmp.append(alist[j])
            j+=1
    # while執(zhí)行完，肯定有一部分是已經(jīng)遍歷完
    # 如果第一個(gè)有序列表有數(shù)
    while i<=mid:
        ltmp.append(alist[i])
        i +=1
    # 如果第二個(gè)有序列表有數(shù)
    while j<=high:
        ltmp.append(alist[j])
        j+=1
    # 將ltmp傳入alist
    alist[low:high+1]=ltmp
# 歸并操作，將列表越分越小，直至分為一個(gè)元素
def merge_sort(alist,low,high):
    if low < high: # 至少有兩個(gè)元素，遞歸；終止條件：只有一個(gè)元素
        # 設(shè)置中間元素
        mid = (low+high)//2
        # 歸并左邊
        merge_sort(alist,low,mid)
        # 歸并右邊
        merge_sort(alist,mid+1,high)
        # 排序
        merge(alist,low,mid,high)

4.8快速排序

? 快速排序也是交換排序的一種，其原理是：將未排序的元素根據(jù)一個(gè)作為基準(zhǔn)的“主元”分為兩個(gè)子序列，其中一個(gè)子序列的記錄均大于主元，而另一個(gè)子序列均小于主元，然后遞歸地對(duì)這兩個(gè)子序列用類似的方法進(jìn)行排序。本質(zhì)上，快速排序使用分治法，將問(wèn)題規(guī)模減小，然后再分別進(jìn)行處理。

def quickSort(alist):
    quickSoertHelper(alist,0,len(alist)-1)

def quickSoertHelper(alist,first,last):
    if first < last: # 至少兩個(gè)元素
        # 遞歸
        mid = partition(alist,first,last)
        quickSort(alist,first,mid-1)
        quickSort(alist,mid+1,last)


def partition(alist,left,right):
    # tmp作為主元
    tmp = alist[left]
    # 如果之間還有兩個(gè)元素
    while left < right:
         # 從右邊找比temp小的數(shù)
         while left < right and alist[right] >= tmp: 
               # 指針往左走一步
               right -= 1
         # 如果右邊的值比主元小，則要換位置
         alist[left] = alist[right]
         # 在左邊找比temp大的數(shù)
         while left < right and alist[left] <= tmp:
               left +=1
         alist[right]=alist[left]
    alist[left] = tmp
    # 返回此時(shí)的主元位置
    return left

五、樹(shù)

5.1 數(shù)的定義

? 數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，上面我們提到的像棧、隊(duì)列、線性表等均為線性結(jié)構(gòu)；而這個(gè)樹(shù)和圖屬于非線性結(jié)構(gòu)。

樹(shù)是n個(gè)節(jié)點(diǎn)的有限集。若n =0，稱為空樹(shù)；若n>0,則它滿足如下兩個(gè)條件：1、有且僅有一個(gè)特定的根稱為根節(jié)點(diǎn)；2、其余結(jié)點(diǎn)可分為m個(gè)互不相交的有限集$T1,T2,T3...$，其中每個(gè)集合本身又是一棵樹(shù)，并稱為根的子樹(shù)。因此可以看出來(lái)樹(shù)的定義本身就是一個(gè)遞歸的過(guò)程，

5.2 二叉樹(shù)的定義

二叉樹(shù)不是樹(shù)的特殊情況，而是兩個(gè)概念。

二叉樹(shù)結(jié)點(diǎn)的子樹(shù)要區(qū)分左子樹(shù)和右子樹(shù)，即使只有一棵子樹(shù)也要區(qū)分其是左子樹(shù)還是右子樹(shù)。

• 滿二叉樹(shù)
• 二叉樹(shù)分類
• 二叉樹(shù)的遍歷

5.3 使用列表進(jìn)行樹(shù)的創(chuàng)建

在“列表之列表”的樹(shù) 中，我們將根節(jié)點(diǎn)的值作為列表的第一個(gè)元素；第二個(gè)元素是代表左子樹(shù)的列表；第三個(gè)元素是代表右子樹(shù)的列表。

# 列表的列表進(jìn)行樹(shù)的定義
def BinaryTree(r):
    return [r,[],[]]
# 添加左子樹(shù)
def insertLeft(root,newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1,[newBranch,t,[]])
    else:
        root.insert(1,[newBranch,[],[]])
    return root
# 添加右子樹(shù)
def insertRight(root,newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2,[newBranch,[],t])
    else:
        root.insert(2,[newBranch,[],[]])
    return root
# 樹(shù)的訪問(wèn)函數(shù)
def getRootVal(root):
    return root[0]

def setRootVal(root,newVal):
    root[0] = newVal

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]

5.4 二叉樹(shù)的建立

? 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)：將二叉樹(shù)的節(jié)點(diǎn)定義為一個(gè)對(duì)象，節(jié)點(diǎn)之間采用類似鏈表的鏈接方式來(lái)鏈接

class BiTreeNode:
    def __init__(self,data):
        # 設(shè)置根節(jié)點(diǎn)
        self.key = data
        # 設(shè)置左右子樹(shù)
        self.leftchild = None
        self.rightchild = None

     # 添加左子樹(shù)
     def insertLeft(self,newNode):
        if self.LeftChild == None:
            self.LeftChild = BinaryTree(newNode)

        else:
            t = BinaryTree(newNode)
            t.left = self.LeftChild
            self.LeftChild = t
    # 添加右子樹(shù)
    def insertRight(self,newNode):
        if self.rightchild == None:
            self.rightchild = BinaryTree(newNode)

        else:
            t = BinaryTree(newNode)
            t.right = self.rightchild
            self.rightchild = t

# 實(shí)例一、構(gòu)建二叉樹(shù)，利用初始化類函數(shù)
a = BiTreeNode('A')
b = BiTreeNode('B')
c = BiTreeNode('C')
d = BiTreeNode('D')
e = BiTreeNode('E')
f = BiTreeNode('F')
g = BiTreeNode('G')

e.leftchild = a
e.rightchild = g
a.rightchild = c
c.leftchild = b
c.rightchild = d
g.rightchild = f
# 設(shè)置說(shuō)明根節(jié)點(diǎn)為e
root = e
# 打印根節(jié)點(diǎn)的左子樹(shù)的右子樹(shù)的值
print(root.leftchild.rightchild.key)
# 返回結(jié)果
>> C

上述實(shí)例一構(gòu)建的二叉樹(shù)模型如下圖所示

5.5 二叉樹(shù)的遍歷

? 二叉樹(shù)的遍歷是指從根節(jié)點(diǎn)出發(fā)，按照某種次序依次訪問(wèn)二叉樹(shù)中所有節(jié)點(diǎn)，使得每個(gè)節(jié)點(diǎn)被訪問(wèn)一次且被訪問(wèn)一次。遍歷方式分為以下三種：

1、前序遍歷（根左右）

在前序遍歷中，先訪問(wèn)根節(jié)點(diǎn)，然后遞歸地前序遍歷左子樹(shù)，最后遞歸地前序遍歷右子樹(shù)。

2、 中序遍歷（左根右）

先遞歸地中序遍歷左子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)，最后遞歸地中序遍歷右子樹(shù)。

注：可以理解為將樹(shù)從上往下拍扁，然后從左往右進(jìn)行依次遍歷

3、 后序遍歷（左右根）

先遞歸地后序遍歷右子樹(shù)，然后遞歸地后序遍歷左子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)。

# 前序遍歷
def pre_order(root):
    if root:
        print(root.key,end=',')
        pre_order(root.leftchild)
        pre_order(root.rightchild)
# 中序遍歷
def in_order(root):
    if root:
        in_order(root.leftchild)
        print(root.key,end=',')
        in_order(root.rightchild)
# 后序遍歷
def post_order(root):
    if root:
        post_order(root.leftchild)
        post_order(root.rightchild)
        print(root.key,end='')
## 遍歷充分利用了遞歸的思想

5.6 二叉搜索樹(shù)

二叉搜索樹(shù)具有如下特性：

1、若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值；

2、若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值；

3、它的左右子樹(shù)也都是二叉排序樹(shù)。

二叉搜索樹(shù)的操作：查詢、插入、刪除

5.6.1 查找

查找的偽代碼如下所示：

若二叉搜索樹(shù)為空，則查找不成功；
否則:
1、若給定值等于根節(jié)點(diǎn)，則查找成功；
2、若給定值小于根節(jié)點(diǎn)，則繼續(xù)在左子樹(shù)上查找；
3、若給定值大于根節(jié)點(diǎn)，則繼續(xù)在右子樹(shù)上進(jìn)行查找

5.6.2 刪除

刪除的偽代碼如下所示：

1、刪除的結(jié)點(diǎn)是葉子節(jié)點(diǎn)
直接刪除，然后修改其父節(jié)點(diǎn)的指針，置空即可。

2、 刪除的結(jié)點(diǎn)有左子樹(shù)和右子樹(shù)
將其右子樹(shù)的最小節(jié)點(diǎn)刪除，并替換當(dāng)前節(jié)點(diǎn)。

3、 刪除的結(jié)點(diǎn)只有左子樹(shù)或只有右子樹(shù)
將此節(jié)點(diǎn)的父親與孩子連接，然后刪除該節(jié)點(diǎn)。

5.6.3 代碼實(shí)現(xiàn)

class BinarySearchTree:

    def __init__(self,li=None):
        self.root = None
        self.size = 0
        self.parent = None
        if li:
            for val in li:
                self.insert_no_rec(val)
# 二叉搜索樹(shù)的插入操作（使用遞歸）
    def insert(self,node,val):
        # 如果節(jié)點(diǎn)為可空
        if not node:
            node = BiTreeNode(val)
        # 如果插入值小于節(jié)點(diǎn)，遍歷左子樹(shù)
        elif val < node.key:
            node.leftchild = self.insert(node.leftchild,val)
            node.leftchild.parent = node
        # 如果插入值大于節(jié)點(diǎn)，遍歷右子樹(shù)
        elif val > node.key:
            node.rightchild = self.insert(node.rightchild,val)
            node.rightchild.parent = node
        else:
            return node
# 插入操作（不使用遞歸）
    def insert_no_rec(self,key):
        p = self.root
        # 空樹(shù)
        if not p:
            self.root = BiTreeNode(key)
            return
        while True:
            # 如果插入節(jié)點(diǎn)比根節(jié)點(diǎn)小
            if key < p.key:
                # 如果左子樹(shù)存在
                if p.leftchild:
                    # 令p指針指向左子樹(shù)
                    p = p.leftchild
                # 如果左子樹(shù)不存在
                else:
                    # p的左子樹(shù)為該插入節(jié)點(diǎn)
                    p.leftchild =  BiTreeNode(key)
                    # 與父節(jié)點(diǎn)做鏈接
                    p.leftchild.parent = p
                    return

            elif key > p.key:
                if p.rightchild:
                    p = p.rightchild
                else:
                    p.rightchild = BiTreeNode(key)
                    p.rightchild.parent = p
                    return
            # 如果插入節(jié)點(diǎn)和根節(jié)點(diǎn)相同，則返回
            else:
                return

# 查詢操作
    def query(self,node,val):
        if not node:
            return None
        if node.data < val:
            return self.query(node.rchild,val)
        elif node.data > val:
            return self.query(node.leftchild,val)
        else:
            return node
    # 查詢操作非遞歸的方法
    def query_no_rec(self,val):
        p = self.root
        while p:
            if p.data < val:
                p = p.rightchild
            elif p.data > val:
                p = p.leftchild
            else:
                return p
        return None

# 刪除操作
    def delete(self,key):
        p = None
        q = self.root
        # 當(dāng)根節(jié)點(diǎn)不為空時(shí)，且添加的值不為根節(jié)點(diǎn)值時(shí)
        while q and q.key != key:
            # 將當(dāng)前根節(jié)點(diǎn)指針賦予p
            p = q
            # 如果刪除的值小于當(dāng)前根節(jié)點(diǎn)，則往左子樹(shù)搜索
            if key < q.key:
                # 將q指針指向q的左子樹(shù)
                q = q.leftchild
            # 反之，往右子樹(shù)搜索
            else:
                q = q.rightchild
            if not q:
                return
        # 上面已經(jīng)找到了要?jiǎng)h除的節(jié)點(diǎn)，用q引用。而p則是q的父節(jié)點(diǎn)或者None。情況一、刪除的節(jié)點(diǎn)沒(méi)有左子樹(shù)
        if not q.leftchild:
            # 如果刪除節(jié)點(diǎn)的父節(jié)點(diǎn)是空，則要?jiǎng)h除的是根節(jié)點(diǎn)，那么直接將其右節(jié)點(diǎn)設(shè)置為根節(jié)點(diǎn)
            if p is None:
                self.root = q.rightchild
            # 如果要?jiǎng)h除的節(jié)點(diǎn)是p的左子樹(shù)，那么直接將p的左子樹(shù)指向q的右子樹(shù)
            elif q is p.leftchild:
                p.leftchild = q.rightchild
            # 如果要?jiǎng)h除的節(jié)點(diǎn)是p的右子樹(shù)，那么直接將p的右子樹(shù)指向q的右子樹(shù)
            else:
                p.rightchild = q.rightchild
            return
        # 查找節(jié)點(diǎn)q的左子樹(shù)的最右節(jié)點(diǎn)，將q的右子樹(shù)鏈接為該節(jié)點(diǎn)的右子樹(shù)
        r = q.leftchild
        # 查找到最小的右子樹(shù)
        while r.rightchild:
            r  = r.rightchild
        r.rightchild = q.rightchild
        if p is None:
            self.root = q.leftchild
        elif p.leftchild is q:
            p.leftchild = q.leftchild
        else:
            p.rightchild = q.leftchild
# 三種遍歷
    def pre_order(self,root):
        if root:
            print(root.key, end=',')
            pre_order(root.leftchild)
            pre_order(root.rightchild)

    def in_order(self,root):
        if root:
            in_order(root.leftchild)
            print(root.key, end=',')
            in_order(root.rightchild)

    def post_order(self,root):
        if root:
            post_order(root.leftchild)
            post_order(root.rightchild)
            print(root.key, end='')

六、圖及其算法

6.1 圖的定義

對(duì)于上面的樹(shù)進(jìn)行比較，圖是更通用的結(jié)構(gòu)，事實(shí)上，樹(shù)可以看做一種特殊的圖。圖有多個(gè)前驅(qū)和多個(gè)后繼。圖可以理解為頂點(diǎn)和邊的集合。

6.2 鄰接矩陣

要實(shí)現(xiàn)圖，最簡(jiǎn)單的方式就是使用二維矩陣。在矩陣實(shí)現(xiàn)中，每一行和每一列都表示圖中的 一個(gè)頂點(diǎn)。第 v行和第 w列交叉的格子中的值表示從頂點(diǎn) v到頂點(diǎn) w的邊的權(quán)重。如果兩個(gè)頂點(diǎn)被一條邊連接起來(lái)，就稱它們是相鄰的。

第v行和第w列交叉的格子中的值表示從頂點(diǎn)v到頂點(diǎn)w的邊的權(quán)重，鄰接矩陣總共大致分為以下三類。

1、無(wú)向圖

對(duì)于n個(gè)頂點(diǎn)的無(wú)向圖，其鄰接矩陣是一個(gè)n×n的方陣。

2、有向圖

3、加權(quán)圖

6.3 圖的實(shí)現(xiàn)

class Vertext(): # 包含了頂點(diǎn)信息,以及頂點(diǎn)連接邊

    def __init__(self,key):#key表示是添加的頂點(diǎn)
        self.id = key
        self.connectedTo = {} # 初始化臨接列表

    def addNeighbor(self,nbr,weight=0):# 這個(gè)是賦值權(quán)重的函數(shù)
        self.connectedTo[nbr] = weight

    def __str__(self):
        return str(self.id)+ ' connectedTo: '+str([x.id for x in self.connectedTo])

    def getConnections(self): #得到這個(gè)頂點(diǎn)所連接的其他的所有的頂點(diǎn) (keys類型是class)
        return self.connectedTo.keys()

    def getId(self): # 返回自己的key
        return self.id

    def getWeight(self,nbr):#返回所連接ner頂點(diǎn)的權(quán)重是多少
        return self.connectedTo[nbr]

'''
Graph包含了所有的頂點(diǎn)
包含了一個(gè)主表(臨接列表)
'''
class Graph():# 圖 => 由頂點(diǎn)所構(gòu)成的圖

    '''
    存儲(chǔ)圖的方式是用鄰接表實(shí)現(xiàn)的.

    數(shù)據(jù)結(jié)構(gòu): {
                key:Vertext(){
                    self.id = key
                    self.connectedTo{
                        相鄰節(jié)點(diǎn)類實(shí)例 : 權(quán)重
                        ..
                        ..
                    }
                }
                ..
                ..
        }


    '''
    def __init__(self):
        self.vertList = {} # 鄰接列表
        self.numVertices = 0 # 頂點(diǎn)個(gè)數(shù)初始化

    def addVertex(self,key):# 添加頂點(diǎn)
        self.numVertices = self.numVertices + 1 # 頂點(diǎn)個(gè)數(shù)累加
        newVertex = Vertext(key) # 創(chuàng)建一個(gè)頂點(diǎn)的臨接矩陣
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self,n):# 通過(guò)key查找定點(diǎn)
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

    def __contains__(self,n):# transition:包含 => 返回所查詢頂點(diǎn)是否存在于圖中
        #print( 6 in g)
        return n in self.vertList

    def addEdge(self,f,t,cost=0): # 添加一條邊.
        if f not in self.vertList: # 如果沒(méi)有邊,就創(chuàng)建一條邊
            nv = self.addVertex(f)
        if t not in self.vertList:# 如果沒(méi)有邊,就創(chuàng)建一條邊
            nv = self.addVertex(t)

        if cost == 0:# cost == 0 代表是沒(méi)有傳入?yún)?shù),而使用的默認(rèn)參數(shù)0,即是是無(wú)向圖
            self.vertList[f].addNeighbor(self.vertList[t],cost) # cost是權(quán)重.無(wú)向圖為0
            self.vertList[t].addNeighbor(self.vertList[f],cost)
        else:#
            self.vertList[f].addNeighbor(self.vertList[t],cost) # cost是權(quán)重

    def getVertices(self):# 返回圖中所有的定點(diǎn)
        return self.vertList.keys()

    def __iter__(self): #return => 把頂點(diǎn)一個(gè)一個(gè)的迭代取出.
        return iter(self.vertList.values())


#
# -------------------------------------------------
# 以下是測(cè)試數(shù)據(jù).可刪除
# -------------------------------------------------
#
g = Graph()

# for i in range(6):
#     g.addVertex(i)
# print(g.vertList)

'''
# a = g.vertList[0]
# print(a.connectedTo)
'''




g.addEdge(0,5,2)
g.addEdge(1,2,4)
g.addEdge(2,3,9)
g.addEdge(3,4,7)
g.addEdge(3,5,3)
g.addEdge(4,0,1)
g.addEdge(5,4,8)
g.addEdge(5,2,1)

print(g.getVertices())
# vertList = { key :VertextObject}
# VertextObject =  ||key = key, connectedTo = {到達(dá)節(jié)點(diǎn):權(quán)重}||   => |||| 表示的是權(quán)重的意思

# print(g)
for v in g: # 循環(huán)類實(shí)例 => return ->  g = VertextObject的集合  v = VertextObject
    for w in v.getConnections(): # 獲得類實(shí)例的connectedTO
        # print(w)
        print("({},{}:{})".format(v.getId(),w.getId(),v.getWeight(w))) ## 為什么會(huì)是這樣 => 因?yàn)檫@個(gè)時(shí)候v就是class啊

6.4 圖的遍歷

圖常用的遍歷方式有兩種，分別是深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）

6.4.1 深度優(yōu)先搜索

? 深度優(yōu)先其思想就是從圖中某一個(gè)頂點(diǎn)出發(fā)，然后沿著邊一直搜索，一條道走到黑！直到走投無(wú)路為止，然后再回退（迷途知返），當(dāng)回退到能看到有尚未訪問(wèn)的頂點(diǎn)時(shí)，繼續(xù)向前搜索，一條道走到黑。直到迷途知返回到頂點(diǎn)，且所有頂點(diǎn)均被訪問(wèn)為止，算法搜索結(jié)束。

from pythonds.graphs import Graph
class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0

    def dfs(self):
        for aVertex in self:
            aVertex.setColor('white')
            aVertex.setPred(-1)
        for aVertex in self:
            if aVertex.getColor() == 'white':
                self.dfsvisit(aVertex)

    def dfsvisit(self,startVertex):
        startVertex.setColor('gray')
        self.time += 1
        startVertex.setDiscovery(self.time)
        for nextVertex in startVertex.getConnections():
            if nextVertex.getColor() == 'white':
                nextVertex.setPred(startVertex)
                self.dfsvisit(nextVertex)
        startVertex.setColor('black')
        self.time += 1
        startVertex.setFinish(self.time)

6.4.2 廣度優(yōu)先搜索

? 廣度優(yōu)先類似于樹(shù)的層次遍歷，從圖中的某個(gè)頂點(diǎn)出發(fā)，然后一次訪問(wèn)頂點(diǎn)未曾訪問(wèn)過(guò)的鄰接點(diǎn)，然后從這些鄰接點(diǎn)依次訪問(wèn)它們的鄰接點(diǎn)。直至所有點(diǎn)被訪問(wèn)到

def bfs(g,start):
    start.setDistance(0)
    start.srtPred(None)
    vertQueue = Queue()
    vertQueue.enqueue(start)
    while (vertQueue.size()>0):
        currentVert = vertQueue.dequeue()
        for nbr in currentVert.getConnections():
            if (nbr.getColor() == 'white'):
                nbr.setColor('gray')
                nbr.setDistance(currentVert.getDistance()+1)
                nbr.serPred(currentVert)
                vertQueue.enqueue(nbr)
         currentVert.setColor('black')

七、參考資料

1、《python數(shù)據(jù)結(jié)構(gòu)與算法》

2、清華大學(xué)博士講解Python數(shù)據(jù)結(jié)構(gòu)與算法（完整版）全套100節(jié)

數(shù)據(jù)結(jié)構(gòu)與算法文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-786523.html

到了這里，關(guān)于Python數(shù)據(jù)結(jié)構(gòu)與算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！