摘要:本篇主要實現四種數據結構,分別是數組堆棧隊列鏈表。后面的一些結構也將用來實現。由于堆疊數據結構只允許在一端進行操作,因而按照后進先出的原理運作。
本篇主要實現四種數據結構,分別是數組、堆棧、隊列、鏈表。我不知道我為什么要用Python來干C干的事情,總之Python就是可以干。
所有概念性內容可以在參考資料中找到出處
數組 數組的設計數組設計之初是在形式上依賴內存分配而成的,所以必須在使用前預先請求空間。這使得數組有以下特性:
請求空間以后大小固定,不能再改變(數據溢出問題);
在內存中有空間連續性的表現,中間不會存在其他程序需要調用的數據,為此數組的專用內存空間;
在舊式編程語言中(如有中階語言之稱的C),程序不會對數組的操作做下界判斷,也就有潛在的越界操作的風險(比如會把數據寫在運行中程序需要調用的核心部分的內存上)。
因為簡單數組強烈倚賴電腦硬件之內存,所以不適用于現代的程序設計。欲使用可變大小、硬件無關性的數據類型,Java等程序設計語言均提供了更高級的數據結構:ArrayList、Vector等動態數組。
Python的數組從嚴格意義上來說:Python里沒有嚴格意義上的數組。
List可以說是Python里的數組,下面這段代碼是CPython的實現List的結構體:
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里它就是數組。
后面的一些結構也將用List來實現。
堆棧(英語: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 stack def 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 "None" def create_queue(): """僅有隊頭""" return MyQueue() def last(queue): if isinstance(queue, MyQueue): if queue.behind is not None: return last(queue.behind) else: return queue def push(queue, ele): if isinstance(queue, MyQueue): last_queue = last(queue) new_queue = MyQueue(ele) last_queue.behind = new_queue def 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 "None" def 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 = None def 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, node def 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 = None def 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百科: 數據結構、數組、隊列、鏈表
EOF
轉載請注明出處:https://zhuanlan.zhihu.com/p/...
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/38135.html
摘要:線性表是最基本的數據結構之一,在實際程序中應用非常廣泛,它還經常被用作更復雜的數據結構的實現基礎。鏈表之單鏈表線性表的定義,它是一些元素的序列,維持著元素之間的一種線性關系。 線性表學習筆記,python語言描述-2019-1-14 線性表簡介 在程序中,經常需要將一組(通常是同為某個類型的)數據元素作為整體管理和使用,需要創建這種元素組,用變量記錄它們,傳進傳出函數等。一組數據中包含...
摘要:線性表的和采用了順序表的實現技術,具有順序表的所有性質。刪除鏈表應丟棄這個鏈表里的所有結點。在語言中,就是檢查相應變量的值是否為。也就是說,插入新元素的操作是通過修改鏈接,接入新結點,從而改變表結構的方式實現的。 1.線性表 Python的list和tuple采用了順序表的實現技術,具有順序表的所有性質。 2.鏈接表 單向鏈接表 的結點是一個二元組。 其表元素域elem保存著作為表元素...
摘要:文章首發于公眾號一件風衣在編程中,我們常使用一組有順序的數據來表示某個有意義的數據,這種一組元素的序列的抽象,就是線性表,簡稱表,是很多復雜數據結構的實現基礎,在中,和就可以看作是線性表的實現。 文章首發于公眾號一件風衣(ID:yijianfengyi) 在編程中,我們常使用一組有順序的數據來表示某個有意義的數據,這種一組元素的序列的抽象,就是線性表,簡稱表,是很多復雜數據結構的實現基...
馬上就要開始啦這次共組織15個組隊學習 涵蓋了AI領域從理論知識到動手實踐的內容 按照下面給出的最完備學習路線分類 難度系數分為低、中、高三檔 可以按照需要參加 - 學習路線 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...
閱讀 1764·2021-10-11 10:59
閱讀 2403·2021-09-30 09:53
閱讀 1765·2021-09-22 15:28
閱讀 2796·2019-08-29 15:29
閱讀 1559·2019-08-29 13:53
閱讀 3207·2019-08-29 12:34
閱讀 2850·2019-08-26 10:16
閱讀 2661·2019-08-23 15:16