tags: 資訊科技

資料結構與演算法(使用Python、ZeroJudge)

零、學習資料結構與演算法的目的

1. 資料結構討論「資料儲存的方式」

• 如陣列、鏈結串列

2. 演算法討論「解決問題的想法」

• 如排序方法、找質數的方法

:mega: 所選用的資料結構和演算法將影響程式的複雜度與效率

3.參考網站

• 演算法與資料結構
• Algorithms and Data Structures

一、資料結構

1. 堆疊

• LIFO(last in first out)
• 串列模擬堆疊(Stack)常用的方法

  串列方法(函式)	意義
  len(sk)	回傳串列個數
  sk.append(x)	將 x 附加到串列後面
  sk.pop()	回傳最後一個元素並刪除

• 模擬程式

EX_1_1：執行下列堆疊程式，印出一堆堆疊操作後的堆疊內容。

sk = []  # 以list模擬
sk.append(5)
sk.append(3)
sk.pop()
sk.append(7)
sk.pop()
sk.append(4)

while ~ : # 堆疊不空
    ~    # 印出堆疊最上面的元素
    ~    # pop掉這個元素

2. 佇列

• FIFO(first in first out)
• 串列模擬佇列(Queue)常用的方法

  串列方法(函式)	意義
  len(q)	回傳串列個數
  q.append(x)	將 x 附加到串列後面
  q.pop(i)	回傳索引值i的元素，並將其刪除； 如果沒有i，則傳回最後一個元素並刪除

• 模擬程式

EX_1_2：執行下列佇列程式，印出一堆佇列操作後的佇列內容。

q = []
q.append(5)
q.append(3)
q.pop(0)
q.append(7)
q.pop(0)
q.append(4)

while ~ : # 佇列不空
    ~    # 印出佇列前面的元素
    ~    # pop掉這個元素

3. 樹

• 模擬具有樹枝狀性質的資料，由節點與邊組成，例如家族族譜、電腦資料夾結構。
  

• 二元樹

• 二元樹的走訪(Tree Traversal)(課本p4-7)

  • 前序走訪(preOrder):先走訪樹根，然後左子樹，最後右子樹。
  • 中序走訪(inOrder):先走訪左子樹，然後樹根，最後右子樹。
  • 後序走訪(postOrder):先走訪左子樹，然後右子樹，最後樹根。
    
    

EX_1_3：下圖的前序、中序、後序走訪分別為？

• 二元搜尋樹(課本p4-12)
  • 模擬程式

EX_1_4：建立二元搜尋樹
依讀入順序 30, 15, 50, 35, 10, 25, 40, 20, 45 建立一個二元搜尋樹(binary search tree)。

• 樹的應用
  • 遊戲樹(game tree)(課本p4-20)
  • 霍夫曼編碼(Huffman Coding)(課本p4-24)

EX_1_5：若一篇文章每個字母出現的次數為：a:8，b:7，c:3，d:4，e:5。
建立Huffman Tree(次數小的結點放左邊)，並求每個字母的Huffman Code。
a->11
b->
c->
d->
e->00

4. 圖

• 圖形是「頂點」(vertex)和邊(edge)所組成
• 圖常用的表示法
  • 相鄰矩陣表示法(Adjacency Matrix)(課本p5-10)
  • 相鄰串列表示法(Adjacency Lists)
• 圖的搜尋(課本p5-12)
  • 深度優先搜尋(Depth First Search,DFS)：以堆疊(Stack)、遞迴來實作。(類似樹的前序走訪)
    • 模擬程式1
    • 模擬程式2
    • Animation of Graph DFS
  • 廣度優先搜尋(Breadth First Search,BFS)：以佇列(Queue)來實作。
    • 模擬程式1
    • 模擬程式2
    • Animation of Graph BFS

EX_1_6：下圖的DFS與BFS走訪順序為(子節點以字母序走訪)？

DFS： 將走訪順序標示在字母「上」。
　　　線條以「黑色箭頭」代表往下探尋，以「白色箭頭」代表回溯上一個點。
BFS： 將階層編號(紅色)標示在字母「下」。

• 圖的應用1-最小生成樹(minimum spanning tree)(課本p5-23)
  • Kruskal演算法為一個使用貪婪法 (greedy method) 的演算法，一開始為一空樹，每次在不讓圖中含有任何迴路(cycle)下尋找圖中最小權重的邊加入樹中，直到所有點皆在樹中即完成。
  • Prim演算法與Dijkstra演算法類似，屢次找出不在樹上，離樹最近的點。

EX_1_7：畫出下圖的最小生成樹，其權重總和為？28

• 圖的應用2-最短路徑(一個頂點到多頂點Dijkstra)(課本p6-20)

EX_1_8：畫出下圖的相鄰陣列，以Dijkstra演算法，求A到各點的最短路徑(以Excel表格表示)？0 8 6 4 3 1 5

二、演算法

1. 演算法效能

• 運算能力

  • 費式數列-遞迴 vs. 陣列
  • 搜尋-循序 vs. 二分搜尋

• 時間複雜度

  • 常見的六種時間複雜度與演算法

• 大O記號(Big-O notation)

  • 令f(n) 與g(n) 是由非負整數對應至實數的函數，若存在正實數常數c 和正整數常數n₀，使n≧n₀時，f(n) ≦ cg(n) 成立，則我們說 f(n)=O(g(n))。
  • 若f(n)=3n²+2，g(n)=n² (n₀=2, c=4)。f(n)=O(n²)
    
    

2.求質數演算法效能比較

EX_2_1：d237: 質數合
以『埃拉托斯特尼篩法』讓本題的速度更快。

n = 2000000
prime = [True]*(n+1)                # 產生n+1個True的list 

for i in range(2, int(n**0.5)+1) :  # 檢查到<=√n即可
    if ~ :                          # 如果i是質數  
        for j in range(~, n+1, ~) : # 如果i是質數，則篩掉它的倍數。(從i^2開始，每次+i)
            prime[~] = ~            # i的倍數不為質數

lst = [x for x in range(2, n+1) if prime[x]]
print(sum(lst))

3. 排序(sort)

• 思考排序的演算法(1) (2)
• 模擬程式
• Bubble Sort
• Sorting Algorithms Animations

EX_2_2：練習 bubble sort

a=[6,4,9,8,3]
for ~ :                # 5 個數字排序只需 4 個循環
    for ~ :            # 每次兩兩比較，每次比較索引值「0、1」「1、2」「2、3」「3、4」 的數字
        if a[~]>a[~] : # 如果左邊比右邊大
            ~          # a[j]和a[j+1]交換

Q：for 內圈寫完後(將最大值移至最右的位子)，複製貼上5次，程式碼會正確嗎？

4. 二分搜尋(binary search)

• 模擬程式

5. 分而治之(Divid and Conquer)

• 合併排序(Merge Sort)1、合併排序2