基本線性數據結構的Python實現

本篇主要實現四種數據結構，分別是數組、堆棧、隊列、鏈表。我不知道我為什麼要用Python來干C乾的事情，總之Python就是可以干。

數組

數組的設計

數組設計之初是在形式上依賴內存分配而成的，所以必須在使用前預先請求空間。這使得數組有以下特性：

1. 請求空間以後大小固定，不能再改變（數據溢出問題）；
2. 在內存中有空間連續性的表現，中間不會存在其他程序需要調用的數據，為此數組的專用內存空間；
3. 在舊式編程語言中（如有中階語言之稱的C），程序不會對數組的操作做下界判斷，也就有潛在的越界操作的風險（比如會把數據寫在運行中程序需要調用的核心部分的內存上）。

因為簡單數組強烈倚賴電腦硬體之內存，所以不適用於現代的程序設計。欲使用可變大小、硬體無關性的數據類型，Java等程序設計語言均提供了更高級的數據結構：ArrayList、Vector等動態數組。

Python的數組

從嚴格意義上來說:Python里沒有嚴格意義上的數組。

typedef struct { PyObject_VAR_HEAD /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */ PyObject **ob_item; /* ob_item contains space for allocated elements. The number * currently in use is ob_size. * Invariants: * 0 <= ob_size <= allocated * len(list) == ob_size * ob_item == NULL implies ob_size == allocated == 0 * list.sort() temporarily sets allocated to -1 to detect mutations. * * Items must normally not be NULL, except during construction when * the list is not yet visible outside the function that builds it. */ Py_ssize_t allocated;} PyListObject;

取自CPython-Github

還有一篇文章講List實現,感興趣的朋友可以去看看。中文版。

當然，在Python里它就是數組。

堆棧

什麼是堆棧

堆棧（英語：stack），也可直接稱棧，在計算機科學中，是一種特殊的串列形式的數據結構，它的特殊之處在於只能允許在鏈接串列或陣列的一端（稱為堆疊頂端指標，英語：top）進行加入資料（英語：push）和輸出資料（英語：pop）的運算。另外堆疊也可以用一維陣列或連結串列的形式來完成。堆疊的另外一個相對的操作方式稱為佇列。

由於堆疊數據結構只允許在一端進行操作，因而按照後進先出（LIFO, Last In First Out）的原理運作。

特點

• 先入後出，後入先出。
• 除頭尾節點之外，每個元素有一個前驅，一個後繼。

操作

從原理可知，對堆棧(棧)可以進行的操作有:

• top():獲取堆棧頂端對象
• push():向棧里添加一個對象
• pop():從棧里推出一個對象

實現

class my_stack(object): def __init__(self, value): self.value = value # 前驅 self.before = None # 後繼 self.behind = None def __str__(self): return str(self.value)def top(stack): if isinstance(stack, my_stack): if stack.behind is not None: return top(stack.behind) else: return stackdef push(stack, ele): push_ele = my_stack(ele) if isinstance(stack, my_stack): stack_top = top(stack) push_ele.before = stack_top push_ele.before.behind = push_ele else: raise Exception(不要亂扔東西進來好么)def pop(stack): if isinstance(stack, my_stack): stack_top = top(stack) if stack_top.before is not None: stack_top.before.behind = None stack_top.behind = None return stack_top else: print(已經是棧頂了)

隊列

什麼是隊列

和堆棧類似，唯一的區別是隊列只能在隊頭進行出隊操作，所以隊列是是先進先出（FIFO, First-In-First-Out）的線性表

特點

• 先入先出,後入後出
• 除尾節點外,每個節點有一個後繼
• （可選）除頭節點外,每個節點有一個前驅

操作

• push（）:入隊
• pop（）：出隊

實現

普通隊列

class MyQueue(): def __init__(self, value=None): self.value = value # 前驅 # self.before = None # 後繼 self.behind = None def __str__(self): if self.value is not None: return str(self.value) else: return Nonedef create_queue(): """僅有隊頭""" return MyQueue()def last(queue): if isinstance(queue, MyQueue): if queue.behind is not None: return last(queue.behind) else: return queuedef push(queue, ele): if isinstance(queue, MyQueue): last_queue = last(queue) new_queue = MyQueue(ele) last_queue.behind = new_queuedef pop(queue): if queue.behind is not None: get_queue = queue.behind queue.behind = queue.behind.behind return get_queue else: print(隊列里已經沒有元素了)def print_queue(queue): print(queue) if queue.behind is not None: print_queue(queue.behind)

鏈表

什麼是鏈表

鏈表（Linked list）是一種常見的基礎數據結構，是一種線性表，但是並不會按線性的順序存儲數據，而是在每一個節點裡存到下一個節點的指針(Pointer)。由於不必須按順序存儲，鏈表在插入的時候可以達到O(1)的複雜度，比另一種線性表順序錶快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而順序表相應的時間複雜度分別是O(logn)和O(1)。

特點

使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由於增加了結點的指針域，空間開銷比較大。

操作

• init():初始化
• insert(): 插入
• trave(): 遍歷
• delete(): 刪除
• find(): 查找

實現

此處僅實現雙向列表

class LinkedList(): def __init__(self, value=None): self.value = value # 前驅 self.before = None # 後繼 self.behind = None def __str__(self): if self.value is not None: return str(self.value) else: return Nonedef init(): return LinkedList(HEAD)def delete(linked_list): if isinstance(linked_list, LinkedList): if linked_list.behind is not None: delete(linked_list.behind) linked_list.behind = None linked_list.before = None linked_list.value = Nonedef insert(linked_list, index, node): node = LinkedList(node) if isinstance(linked_list, LinkedList): i = 0 while linked_list.behind is not None: if i == index: break i += 1 linked_list = linked_list.behind if linked_list.behind is not None: node.behind = linked_list.behind linked_list.behind.before = node node.before, linked_list.behind = linked_list, nodedef remove(linked_list, index): if isinstance(linked_list, LinkedList): i = 0 while linked_list.behind is not None: if i == index: break i += 1 linked_list = linked_list.behind if linked_list.behind is not None: linked_list.behind.before = linked_list.before if linked_list.before is not None: linked_list.before.behind = linked_list.behind linked_list.behind = None linked_list.before = None linked_list.value = Nonedef trave(linked_list): if isinstance(linked_list, LinkedList): print(linked_list) if linked_list.behind is not None: trave(linked_list.behind)def find(linked_list, index): if isinstance(linked_list, LinkedList): i = 0 while linked_list.behind is not None: if i == index: return linked_list i += 1 linked_list = linked_list.behind else: if i < index: raise Exception(404) return linked_list

以上所有源代碼均在Github共享，歡迎提出issue或PR，希望與大家共同進步!

參考資料

• Wiki百科: 數據結構、數組、隊列、鏈表

轉載請註明出處：https://zhuanlan.zhihu.com/p/22109324

推薦閱讀：