Python基礎_1.數據結構與演算法_簡單數據結構

我們先來看四種簡單但是重要的數據結構：棧(stack)、隊列(queue)、雙端隊列(deque)、 列表(list)。它們的區別在於元素如何加入集合中和從集合中移除。這些數據結構，也稱為線性數據結構。

一、 棧

1. 排序原則：後進先出(LIFO)

從圖中可以看出，第一個被加入棧中的元素[4]處於棧的底端，需要上面的元素[8.4]、[True]、[dog]先出去，[4]才能出去。

2. 實現抽象的棧數據結構

一個棧stack應該要有以下的函數實現其功能

1）Stack() 創建一個空的棧。不需要參數、並返回一個空的棧。

2）Push(item) 增添一個新的元素到棧的頂端。需要增添的新元素作為參數，無返回值。

3）Pop( ) 從棧的頂端移除一個元素。不需要參數，並返回被移除的元素。

4） Peek( ) 返回棧的頂端的元素，但不移除它。不需要參數。

5） is_empty( ) 查看棧是否為空。不需要參數，返回布爾值。

6）size( ) 返回棧中元素的數目。不需要參數，返回一個整數。

我們現在用Python來完善一個具備上述功能的Stack類：

class Stack: def __init__(self): self.items = [] # 使用Python里的List作為棧容器 def is_empty(self): return self.items == [] def push(self,item): self.items.append(item) # list.append(x) 添加元素到列表末端 Add an item to the end of the list def pop(self): return self.items.pop() # list.pop( ) 移除和返回列表中最後一個元素 Removes and returns the last item in the list def peek(self): return self.items[len(self.items)-1] def size(self): return len(self.items)

下面是對這個類的測試效果

3. 例子：十進位整數轉換為二進位至十六進位整數

我們首先來看十進位轉換為二進位的原理，如將10轉換為二進位則是1010,轉換過程為

10//2 = 5 rem（餘數）= 0

5//2 = 2 rem = 1

2//2 = 1 rem = 0

1//2 = 0 rem = 1

取反則為1010

這個過程和我們棧的結構相近，我們可用棧按照0101的順序儲存餘數，然後按後進先出取出，則為1010.

import stackdef base_converter(dec_number,base): digits="0123456789ABCDEF" # 用來查找替代的數值 rem_stack = stack.Stack() # 新建棧 while dec_number>0: rem = dec_number % base # 求余，如5%2=1 rem_stack.push(rem) # 儲存餘數 dec_number = dec_number // base # 除法向下取整，如5//2=2 new_string = "" while not rem_stack.is_empty(): # 按後進先出的順序取出棧中的元素,如取出的元素為15，則替代為十六進位中的F new_string = new_string +digits[rem_stack.pop()] return new_stringprint(base_converter(10,2))print(base_converter(25,16))

二、 隊列(Queue)

1. 排序原則：先進先出(FIFO)

從圖中可以看出，隊列就像是我們現實生活中的等車排隊一樣，第一個來排隊的人第一個上車。

2. 實現抽象的隊列數據結構

一個隊列Queue應該要有以下的函數實現其功能：

1） Queue( ) 創建一個空的隊列。不需要參數、並返回一個空的隊列。

2）enqueue(item) 增添一個新的元素到隊列後面。需要增添的新元素作為參數，無返回值。

3）dequeue( ) 移除隊列前面的元素。不需要參數，並返回被移除的元素。

4） is_empty( ) 查看隊列是否為空。不需要參數，返回布爾值。

5）size( ) 返回隊列中元素的數目。不需要參數，返回一個整數。

我們現在用Python來完善一個具備上述功能的Queue類：

class Queue: def __init__(self): self.items = [] def is_empty(self): return self.items == [] def enqueue(self,item): # list.insert(i, x) Insert an item at a given position. self.items.insert(0,item) # 添加元素到列表前端 def dequeue(self): return self.items.pop() def size(self): return len(self.items)

下面是對這個類的測試效果

3. 例子：擊鼓傳花

我們小時候想必都玩過一種叫做「擊鼓傳花」的遊戲：所有人圍成一個圈，鼓點開始的時候，花從其中一個人手裡傳到下一個人手裡，當鼓點停的時候，手裡有花的玩家會被淘汰，然後剩下的人繼續比賽。我們就使用隊列的結構來模擬這樣的遊戲。

遊戲：我們有六個人，每計數1次，隊列最前面的人排到隊列最後面，鼓點（計數7次）停止時，新隊列最前面的人被淘汰。一直到剩下一個人為止。

import queuedef hot_potato(name_list,num): sim_queue = queue.Queue() for name in name_list: sim_queue.enqueue(name) while sim_queue.size()>1: for i in range(num): sim_queue.enqueue(sim_queue.dequeue()) # 傳遞7次以後組成新的隊列 print(sim_queue.dequeue()) # 手裡有花的人被淘汰 return sim_queue.dequeue() #返回剩下的人print(hot_potato([Bill,David,Susan,Jane,Kent,Brad],7))

三、 雙端隊列(Deque)

1. 排序原則：兩端進出

從圖中可以看出，雙端隊列比隊列要靈活，可以從前面也可以從後面進行添加、刪除等操作。

2. 實現抽象的雙端隊列數據結構

一個隊列Deque應該要有以下的函數實現其功能：

1）Deque( ) 創建一個空的雙端隊列。不需要參數，並返回一個空的雙端隊列。

2）add_front(item) 增添一個新的元素到雙端隊列前面。需要增添的新元素作為參數，無返回值。

3）remove_front ( ) 移除雙端隊列前面的元素。不需要參數，並返回被移除的元素。

4）remove_rear ( ) 移除雙端隊列後面的元素。不需要參數，並返回被移除的元素。

5）is_empty( ) 查看雙端隊列是否為空。不需要參數，返回布爾值。

6）size( ) 返回雙端隊列中元素的數目。不需要參數，返回一個整數。

我們現在用Python來完善一個具備上述功能的Dueue類：

class Deque: def __init__(self): self.items = [] def is_empty(self): return self.items == [] def add_front(self,item): self.items.append(item) def add_rear(self,item): self.items.insert(0,item) def remove_front(self): return self.items.pop() def remove_rear(self): return self.items.pop(0) def size(self): return len(self.items)

下面是對這個類的測試效果

3. 例子：迴文（指順讀和倒讀都一樣的詞語）

有些英文單詞如radar,toot,madam無論順讀還是倒讀都一樣，正如一些漢語辭彙如「我為人人，人人為我」一樣。我們使用雙端隊列來實現迴文的檢測。

import dequedef pal_checker(a_string): char_deque = deque.Deque() for ch in a_string: char_deque.add_rear(ch) # 拆分字元串放入雙端隊列中 still_equal = True while char_deque.size()>1 and still_equal: first = char_deque.remove_front() # 去掉雙端隊列前面的一個元素 last = char_deque.remove_rear() # 去掉雙端隊列後面的一個元素 if first != last: # 判斷去掉的前後元素是否相同 still_equal = False return still_equalprint(pal_checker(helloworld))print(pal_checker(radar))print(pal_checker(少生孩子多種樹))print(pal_checker(我為人人，人人為我))

四、 無序列表——鏈表(Linked Lists)

1. 排序原則：無序，但是有相對位置

從圖中可以看出，無序列表具有相對位置，[54]是head，[31]是end, 但是在物理層它們的位置沒有順序的限制。無序列表和前三種數據結構最大的不同在於可以往無序列表中的任意位置添加和刪除元素。

2. 一個無序列表List應該要有以下的函數實現其功能：

1）List( ) 創建一個空的列表。不需要參數，並返回一個空的列表。

2）add(item) 增添一個新的元素到列表。需要增添的新元素作為參數，無返回值。

3）remove(item) 移除列表中的元素。需要參數。假設元素已經存在於列表中。

4）search (item) 查找列表中的元素。需要參數，並返回布爾值。

5）is_empty( ) 查看列表是否為空。不需要參數，返回布爾值。

6）size( ) 返回列表中元素的數目。不需要參數，返回一個整數。

7）append(item) 在列表末尾增加一個新的元素作為集合中的最後一個元素。需要參數，無返回值。假設元素未存在於列表中。

8）index(item) 返回列表中元素的位置。需要參數，返回一個索引號。假設元素已經存在於列表中。

9）insert(pos,item) 在列表中的指定位置插入。需要參數，無返回值。假設元素未存在於列表中。

10）pop( ) 移除列表中末尾的。不需要參數，返回被移除的元素。假設列表至少有一個元素。

11）pop(pos) 移除列表中指定位置的元素。需要參數，返回被移除的元素。假設列表中存在該元素。

我們現在用Python來完善一個具備上述功能的UnorderedList類, 在此之前，我們先實現一個Node（節點）類：

class Node: def __init__(self,init_data): self.data = init_data self.next = None def get_data(self): return self.data def get_next(self): return self.next def set_data(self, new_data): self.data = new_data def set_next(self, new_next): self.next = new_nexttemp = Node(93)print(temp.get_data())

Node類的原理如下圖所示

Node由兩部分組成，一部分是當前位置的元素data，另一部分是指向下一個位置元素的next（類似C語言中的指針）。

為何我們會先引入Node類？因為Node類是構成UnorderedList類的基本元素。正因為Node有指向下一個位置的部分，只要我們將next指向的位置改變，就可以修改列表中的任意元素。比如，原本93指向的下一個元素是4，我們只需要將93指向5，然後5指向4，這樣就可以在93和4之間添加一個新元素5。這就是鏈表結構的奇妙之處。

接下來我們用Python來完善UnorderedList類：

首先，我們的鏈表要有一個首元素，在鏈表內還沒有元素的時候，首元素為空。

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

其次，一個判斷是否空鏈表的函數，只需要檢查首元素。

def is_empty(self): return self.head == None

再次，一個為鏈表添加元素的函數。這裡用到我們的之前定義的Node類，正如我們之前所舉的例子：原本93指向的下一個元素是4，我們只需要將93指向5，然後5指向4，這樣就可以在93和4之間添加一個新元素5。

這裡我們只列出add函數，從首元素的位置為鏈表增添元素。若想要實現從指定位置插入元素，則可以按照相同的原理實現insert函數。

def add(self,item): temp = node.Node(item) temp.set_next(self.head) self.head = temp

然後，我們定義一個search函數實現查找功能。這裡的查找方式為最常見的順序查找法。

def search(self,item): current = self.head found = False while current != None and not found: if current.get_data() == item: found = True else: current = current.get_next() return found

最後我們定義一個remove函數實現刪除元素的功能。刪除分為兩部分，一部分是查找，另一部分是刪除。刪除類似於添加，如要刪除93,5,4中的5，則需要將93指向5改成93指向4。

def remove(self,item): current = self.head previous = None found = False while not found: if current.get_data() == item: found = True else: previous = current current = current.get_next() if previous == None: # 如果刪除的是首元素，則設置下一個元素為首元素 self.head = current.get_next() else: # 如果刪除的不是首元素，則前一個元素指向後一個元素（跳過了被刪除的當前元素） previous.set_next(current.get_next())

到目前為止，我們基本實現了簡單的鏈表結構。

五、 有序列表 (Ordered Lists)

1. 排序原則：數值按照從大到小或者從小到大的順序在列表中排列

從圖中可以看出，有序列表和無序列表相近，所不同的是列表中的元素按照一定的順序排列。

2. 實現一個簡單的Ordered List類

有序列表和無序列表的實現相近，但是在實現查找功能有微略不同。比如一個升序列表，查找5時，當查找到第一個大於5的元素時就停止了，因為後面的元素均大於5。因此，有序列表的好處在於其查找速度較快。

但是，有序列表添加元素的速度較慢。試想一下我們往一個有序列表[1,2,4,5]中添加3，則需要查找到4的位置，然後將2指向3,3指向4。與無序列表往首元素開始添加多了一個查找的過程。

class OrderedList: def __init__(self): self.head = None def search(self,item): current = self.head found = False stop = False while current != None and not found and not stop: if current.get_data() == item: found = True else: if current.get_data() > item: stop = True else: current = current.get_next() return found def add(self, item): current = self.head previous = None stop = False while current != None and not stop: if current.get_data()>item: stop = True else: previous = current current = current.get_next() temp = node.Node(item) if previous == None: temp.set_next(self.head) self.head = temp else: temp.set_next(current) previous.set_next(temp)

參考資料：Problem Solving with Algorithms and Data Structures