歡迎！

Data Structures and Algorithms in Python

Miriam Antona

Software Engineer

演算法與資料結構的重要性

資料結構 與 演算法 能幫助我們
- 解決 日常問題
- 使用 高效程式碼
這門課可用 任何程式語言 教學

演算法與資料結構

演算法：解決問題的一組指令
1. _設計_
2. 撰寫程式碼

資料結構： 在執行演算法時承載並操作資料
- 進階資料結構：linked lists、stacks、queues...

連結串列（Linked lists）

一個連結串列的視覺範例，內容為做麵包的步驟。

以連結相接的資料序列

連結串列－結構

連結串列中節點的表示法。

連結串列－結構

連結串列中節點的表示法，第一部分標示為「DATA」。

連結串列－結構

連結串列中節點的表示法，第一部分為「DATA」，第二部分為帶指標的「NEXT」。

連結串列－結構

兩個連結串列節點以連結相接的表示法。

連結串列－結構

多個連結串列節點以連結相接的表示法。

連結串列－結構

連結串列的最後一個節點指向 null 的表示法。

連結串列－結構

連結串列中第一個節點標示為「HEAD」的表示法。

連結串列－結構

連結串列中最後一個節點標示為「TAIL」的表示法。

資料不必存於連續記憶體區塊
資料可位於任何可用記憶體位址

單向連結串列

單向連結串列的表示法。

單一連結：單向連結串列

雙向連結串列

雙向連結串列的表示法。

兩端皆可連結：雙向連結串列

連結串列－實際用途

可實作其他資料結構：
- stacks
- queues
- graphs
可前後導覽以存取資訊
- 網頁瀏覽器
- 音樂播放清單

連結串列－Node 類別

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

連結串列－LinkedList 類別

class LinkedList:
  def __init__(self):
    self.head = None
    self.tail = None

連結串列－方法

insert_at_beginning()
remove_at_beginning()
insert_at_end()
remove_at_end()
insert_at()
remove_at()
search()
...

連結串列－insert_at_beginning

單向連結串列的表示法。

連結串列－insert_at_beginning

單向連結串列與一個新節點的表示法，

 def insert_at_beginning(self, data):
    new_node = Node(data)

    if self.head:

連結串列－insert_at_beginning

新節點已連上單向連結串列的表示法。

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head

連結串列－insert_at_beginning

新節點已連上，且該節點標示為「HEAD」的表示法。

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
      self.head = new_node

連結串列－insert_at_beginning

空的連結串列中新增節點的表示法。

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
      self.head = new_node
    else:

      self.tail = new_node      
      self.head = new_node

連結串列－insert_at_end

  def insert_at_end(self, data):
    new_node = Node(data)
    if self.head:  

      self.tail.next = new_node

      self.tail = new_node

    else:

      self.head = new_node
      self.tail = new_node

連結串列－search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

單向連結串列的表示法，標示「current_node」指向第一個節點。

連結串列－search

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

單向連結串列的表示法，標示「current_node」指向第二個節點。

連結串列－search

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

  return False

單向連結串列的表示法，標示「current_node」指向第三個節點。

連結串列－範例

空的連結串列中新增節點的表示法。

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")

連結串列－範例

在連結串列尾端加入新節點的表示法。

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll")

連結串列－範例

在連結串列開頭加入新節點的表示法。

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll") 
sushi_preparation.insert_at_beginning("assemble")

連結串列－範例

連結串列的表示法。

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

一起來練習吧！

Data Structures and Algorithms in Python