基礎資料結構

基礎資料結構

• 基礎資料結構
  • 堆疊（stack）
  • 佇列 (queue)
  • 雙端佇列 ( deque )
  • 順序表 與 記憶體
    • 簡單了解一下記憶體
    • 順序表
    • 順序表的弊端：順序表的結構需要預先知道資料大小來申請連續的存盤空間，而在進行擴充時又需要進行資料的搬遷，
  • 鏈表 （Linked list）
  • 二叉樹

堆疊（stack）

  堆疊（stack）又名堆疊，它是一種運算受限的線性表，其限制是僅允許在表的一端進行插入和洗掉運算，
這一端被稱為堆疊頂，相對地，把另一端稱為堆疊底，向一個堆疊插入新元素又稱作進堆疊、入堆疊或壓堆疊，
它是把新元素放到堆疊頂元素的上面，使之成為新的堆疊頂元素；從一個堆疊洗掉元素又稱作出堆疊或退堆疊，
它是把堆疊頂元素洗掉掉，使其相鄰的元素成為新的堆疊頂元素，

堆疊作為一種資料結構，是一種只能在一端進行插入和洗掉操作的特殊線性表，它按照先進后出的原則存盤資料，
先進入的資料被壓入堆疊底，最后的資料在堆疊頂，需要讀資料的時候從堆疊頂開始彈出資料（最后一個資料被第一個讀出來），
堆疊具有記憶作用，對堆疊的插入與洗掉操作中，不需要改變堆疊底指標，

- 特性：先進后出的資料結構

# 應用：每個 web 瀏覽器都有一個回傳按鈕，當你瀏覽網頁時，這些網頁被放置在一個堆疊中（實際是網頁的網址），
你現在查看的網頁在頂部，你第一個查看的網頁在底部，如果按‘回傳’按鈕，將按相反的順序瀏覽剛才的頁面，

# 使用python代碼實作一個堆疊
- Stack() 創建一個空的新堆疊， 它不需要引數，并回傳一個空堆疊，
- push(item)將一個新項添加到堆疊的頂部，它需要 item 做引數并不回傳任何內容，
- pop() 從堆疊中洗掉頂部項，它不需要引數并回傳 item ，堆疊被修改，
- peek() 從堆疊回傳頂部項，但不會洗掉它，不需要引數， 不修改堆疊，
- isEmpty() 測驗堆疊是否為空，不需要引數，并回傳布林值，
- size() 回傳堆疊中的 item 數量，不需要引數，并回傳一個整數，

class Stack():
    def __init__(self):
        self.items = []
    def push(self,item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return len(self.items) - 1
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)
    
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print('堆疊頂元素下標：',stack.peek())
print(stack.isEmpty())
print('元素個數：',stack.size())
print(stack.pop())
print(stack.pop())
print(stack.pop())

佇列 (queue)

- 佇列：先進先出
- 應用場景：
    - 我們的計算機實驗室有 30 臺計算機與一臺列印機聯網，當學生想要列印時，
他們的列印任務與正在等待的所有其他列印任務“一致”，第一個進入的任務是先完成，
如果你是最后一個，你必須等待你前面的所有其他任務列印，

# 使用python代碼實作一個佇列
- Queue() 創建一個空的新佇列， 它不需要引數，并回傳一個空佇列，
- enqueue(item) 將新項添加到隊尾， 它需要 item 作為引數，并不回傳任何內容，
- dequeue() 從隊首移除項，它不需要引數并回傳 item， 佇列被修改，
- isEmpty() 查看佇列是否為空，它不需要引數，并回傳布林值，
- size() 回傳佇列中的項數，它不需要引數，并回傳一個整數，

class Queue():
    def __init__(self):
        self.items = []
    def enqueue(self,item):
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)

q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())    

# 面試題
- 燙手的山芋
    - 燙手山芋游戲介紹：6個孩子圍城一個圈，排列順序孩子們自己指定，第一個孩子手里有一個燙手的山芋，
需要在計時器計時1秒后將山芋傳遞給下一個孩子，依次類推，規則是，在計時器每計時7秒時，手里有山芋的孩子退出游戲，
該游戲直到剩下一個孩子時結束，最后剩下的孩子獲勝，請使用佇列實作該游戲策略，排在第幾個位置最侄訓獲勝，
# 解題思路
    - 讓手里有山芋的孩子永遠排在佇列的頭部
class Queue():
    def __init__(self):
        self.items = []
    def enqueue(self,item):
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)
    
kids = ['A','B','C','D','E','F']
queue = Queue()
for kid in kids:
    queue.enqueue(kid) #A對頭F隊尾
while queue.size() > 1:
    for i in range(6): #每回圈一次，山芋傳遞一次，手里有山芋的孩子永遠在對頭位置
        kid = queue.dequeue()
        queue.enqueue(kid)
    queue.dequeue()
print('獲勝的選手是：',queue.dequeue())
for a in range(len(kids)):
    if kids[a] == kid:   
        print('排在第：%d會獲勝'%a)  
# 執行結果
獲勝的選手是： E
排在第：4會獲勝

# 面試題 使用兩個佇列實作一個堆疊
class Queue():
    def __init__(self):
        self.items = []
    def enqueue(self,item):
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def size(self):
        return len(self.items)
    
alist = [1,2,3,4,5]
q1 = Queue()
for i in alist:
    q1.enqueue(i)
q2 = Queue()
while q1.size() > 0:
    #將q1中的n-1個值取出放入到q2中
    while q1.size() > 1:
        item = q1.dequeue()
        q2.enqueue(item)
    print(q1.dequeue())

    q1,q2 = q2,q1    

雙端佇列 ( deque )

同佇列相比，有兩個頭部和尾部，可以在雙端進行資料的插入和洗掉，提供了單資料結構中堆疊和佇列的特性.

# 用python代碼實作一個雙端佇列
- Deque() 創建一個空的新 deque，它不需要引數，并回傳空的 deque，
- addFront(item) 將一個新項添加到 deque 的首部，它需要 item 引數 并不回傳任何內容，
- addRear(item) 將一個新項添加到 deque 的尾部，它需要 item 引數并不回傳任何內容，
- removeFront() 從 deque 中洗掉首項，它不需要引數并回傳 item，deque 被修改，
- removeRear() 從 deque 中洗掉尾項，它不需要引數并回傳 item，deque 被修改，
- isEmpty() 測驗 deque 是否為空，它不需要引數，并回傳布林值，
- size() 回傳 deque 中的項數，它不需要引數，并回傳一個整數，

class Deque():
    def __init__(self):
        self.items = []
    def addFront(self,item):
        self.items.insert(0,item)
    def addRear(self,item):
        self.items.append(item)
    def removeFront(self):
        return self.items.pop()
    def removeRear(self):
        return self.items.pop(0)
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)
    
q = Deque()
q.addFront(1)
q.addFront(2)
q.addFront(3)

print(q.removeRear())
print(q.removeRear())
print(q.removeRear())

- 雙端佇列應用案例：回文檢查
    - 回文是一個字串，讀取首尾相同的字符，例如，radar toot madam，
class Deque():
    def __init__(self):
        self.items = []
    def addFront(self,item):
        self.items.insert(0,item)
    def addRear(self,item):
        self.items.append(item)
    def removeFront(self):
        return self.items.pop()
    def removeRear(self):
        return self.items.pop(0)
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)
    
def isHuiWen(s):
    ex = True
    q = Deque()
    for ch in s:
        q.addFront(ch)
    while q.size() > 1:
        if q.removeFront() != q.removeRear():
            ex = False
            break
    return ex
print(isHuiWen('上海自來水來自海上'))
# 執行結果
True

順序表 與 記憶體

• 簡單了解一下記憶體

- 記憶體在計算機的作用
    - 用來存盤和運算二進制的資料
- 問題：計算機如何計算1+2？
    - 將1和2的二進制型別的資料加載到計算機的記憶體中，然后使用暫存器進行數值的預算，
- 變數的概念
    - 變數可以理解為某一塊記憶體(實際是參考的某一塊記憶體的地址)
    - 記憶體空間是有兩個默認的屬性：
        - 記憶體空間的大小
            - bit（位）：一個bit大小的記憶體空間只能存放一位二進制的數
            - byte（位元組）：8bit
            - kb：1024byte
        - 記憶體空間的地址
            - 使用一個十六進制的數值表示
            - 作用：讓cup尋址
                       
- 理解a=10的記憶體圖（參考，指向）
    - 參考：變數==》記憶體空間的地址
    - a = 10：a變數/參考/記憶體空間的地址
    - 指向：如果變數或者參考表示的是某一塊記憶體空間地址的話，則該變數或者該參考指向了該塊記憶體

• 順序表

- 集合中存盤的元素是有順序的，順序表的結構可以分為兩種形式：單資料型別(np.array陣列)和多資料型別(串列,元組)，

- python中的串列和元組就屬于多資料型別的順序表

- 單資料型別順序表的記憶體圖 (記憶體連續開辟,每個記憶體空間大小一致)

- 多資料型別順序表的記憶體圖（記憶體非連續開辟）

• 順序表的弊端：順序表的結構需要預先知道資料大小來申請連續的存盤空間，而在進行擴充時又需要進行資料的搬遷，

鏈表 （Linked list）

- 鏈表（Linked list）是一種常見的基礎資料結構，是一種線性表，但是不像順序表一樣連續存盤資料，
而是每一個結點（資料存盤單元）里存放下一個結點的資訊（即地址）

- 相對于順序表，鏈表結構可以充分利用計算機記憶體空間，實作靈活的記憶體動態管理且進行擴充時不需要進行資料搬遷，

- 使用python實作單向鏈表

. is_empty()：鏈表是否為空

. length()：鏈表長度

. travel()：遍歷整個鏈表

. add(item)：鏈表頭部添加元素

. append(item)：鏈表尾部添加元素

. insert(pos, item)：指定位置添加元素

. remove(item)：洗掉節點

. search(item)：查找節點是否存在

# 代碼
class Node():
    def __init__(self,item):
        self.item = item
        self.next = None
        
class Link():
    def __init__(self):
        #構造出一個空鏈表
        #_head存盤的只能是慷訓者第一個節點的地址
        self._head = None
    #向鏈表的頭部插入一個節點
    def add(self,item):
        #創建一個新的節點
        node = Node(item)
        node.next = self._head
        self._head = node
        
    def travel(self):
        #_head在鏈表創建好之后一定是不可變
        cur = self._head
        while cur:
            print(cur.item)
            cur = cur.next
            
    def isEmpty(self):
        return self._head == None
    
    def size(self):
        cur = self._head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count
    
    def append(self,item):
        node = Node(item)
        #特殊情況
        if self._head == None:
            self._head = node
            return
        
        cur = self._head
        pre = None#pre指向的是cur前一個節點
        while cur:
            pre = cur
            cur = cur.next
        pre.next = node
    
    def search(self,item):
        find = False
        
        cur = self._head
        while cur:
            if cur.item == item:
                find = True
                break
            cur = cur.next
        
        return find
    
    def insert(self,pos,item):
        node = Node(item)
        pre = None
        cur = self._head
        for i in range(pos):
            pre = cur
            cur = cur.next
        pre.next = node
        node.next = cur
        
    def remove(self,item):
        cur = self._head
        pre = None
        #洗掉的是第一個節點
        if cur.item == item:
            self._head = cur.next
            return
        while cur:  
            pre = cur
            cur = cur.next
            if cur.next == None:
                return
            if cur.item == item:
                pre.next = cur.next
                return      

- 如何實作將單鏈表倒置

# 單鏈表（插入，洗掉，遍歷）
class Node():
   def __init__(self,item):
       self.item = item
       self.next = None
class Link():
   def __init__(self):
       self._head = None
   def append(self,item):
       node = Node(item)
       if self._head == None:
           self._head = node
           return
       cur = self._head
       pre = None
       
       while cur:
           pre = cur
           cur = cur.next
       pre.next = node
   def travel(self):
       cur = self._head
       while cur:
           print(cur.item)
           cur = cur.next
   def remove(self,item):
       cur = self._head
       pre = None
       #洗掉的是第一個節點
       if cur.item == item:
           self._head = cur.next
           return
       while cur:
           pre = cur
           cur = cur.next
           if item == cur.item:
               pre.next = cur.next
               return
   
   def reverse(self):
       cur = self._head
       pre = None
       next_node = cur.next
       
       while cur:
           cur.next = pre
           pre = cur
           cur = next_node
           if cur:
               next_node = cur.next
       self._head = pre
   
# 雙向鏈表就是連續開辟三個記憶體空間,分別存放 資料 上個節點記憶體地址 下個節點記憶體地址   

二叉樹

• 二叉樹
  • 根節點
  • 葉子節點：
    • 左葉子節點
    • 右葉子節點
  • 樹的層級/樹的高度
• 二叉樹的遍歷
  • 廣度優先遍歷
    • 一層一層對節點進行遍歷
  • 深度優先遍歷
    • 前序：根左右
    • 中序：左根右
    • 后序：左右根

# 使用python代碼實作二叉樹
class Node():
    def __init__(self,item):
        self.item = item
        self.left = None
        self.right = None    
class Tree():
    def __init__(self):
        self.root = None
    def addNode(self,item):
        node = Node(item)
        #如果插入第一個節點的情況
        if self.root == None:
            self.root = node
            return
        cur = self.root
        q = [cur] #串列元素是我們進行遍歷判斷的節點
        while q:
            nd = q.pop(0)
            if nd.left == None:
                nd.left = node
                return
            else:
                q.append(nd.left)
            if nd.right == None:
                nd.right = node
                return
            else:
                q.append(nd.right)
    def travel(self):  #廣度優先遍歷
        cur = self.root
        q = [cur]
        while q:
            nd = q.pop(0)
            print(nd.item)
            if nd.left:
                q.append(nd.left)
            if nd.right:
                q.append(nd.right)
                
    def forwoar(self,root): #深度優先 前序:根左右
        if root == None:
            return
        print(root.item)
        self.forwoar(root.left)
        self.forwoar(root.right)
    def middle(self,root):  #深度優先 前序:左根右
        if root == None:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)
    def back(self,root):   #深度優先 前序:左右根
        if root == None:
            return
        self.back(root.left)
        self.back(root.right)
        print(root.item)

標籤：Python

上一篇：LeetCode 10. 正則運算式匹配 | Python

下一篇：pyqt5，pycharm，Process finished with exit code -1073741819 (0xC0000005)