Python實現(xiàn)的數(shù)據(jù)結構與算法之鏈表詳解
本文實例講述了Python實現(xiàn)的數(shù)據(jù)結構與算法之鏈表。分享給大家供大家參考。具體分析如下:
一、概述
鏈表(linked list)是一組數(shù)據(jù)項的集合,其中每個數(shù)據(jù)項都是一個節(jié)點的一部分,每個節(jié)點還包含指向下一個節(jié)點的鏈接。
根據(jù)結構的不同,鏈表可以分為單向鏈表、單向循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表等。其中,單向鏈表和單向循環(huán)鏈表的結構如下圖所示:
二、ADT
這里只考慮單向循環(huán)鏈表ADT,其他類型的鏈表ADT大同小異。單向循環(huán)鏈表ADT(抽象數(shù)據(jù)類型)一般提供以下接口:
① SinCycLinkedlist() 創(chuàng)建單向循環(huán)鏈表
② add(item) 向鏈表中插入數(shù)據(jù)項
③ remove(item) 刪除鏈表中的數(shù)據(jù)項
④ search(item) 在鏈表中查找數(shù)據(jù)項是否存在
⑤ empty() 判斷鏈表是否為空
⑥ size() 返回鏈表中數(shù)據(jù)項的個數(shù)
單向循環(huán)鏈表操作的示意圖如下:
三、Python實現(xiàn)
Python的內建類型list底層是由C數(shù)組實現(xiàn)的,list在功能上更接近C++的vector(因為可以動態(tài)調整數(shù)組大小)。我們都知道,數(shù)組是連續(xù)列表,鏈表是鏈接列表,二者在概念和結構上完全不同,因此list不能用于實現(xiàn)鏈表。
在C/C++中,通常采用“指針+結構體”來實現(xiàn)鏈表;而在Python中,則可以采用“引用+類”來實現(xiàn)鏈表。在下面的代碼中,SinCycLinkedlist類代表單向循環(huán)鏈表,Node類代表鏈表中的一個節(jié)點:
#!/usr/bin/env python # -*- coding: utf-8 -*- class Node: def __init__(self, initdata): self.__data = initdata self.__next = None def getData(self): return self.__data def getNext(self): return self.__next def setData(self, newdata): self.__data = newdata def setNext(self, newnext): self.__next = newnext class SinCycLinkedlist: def __init__(self): self.head = Node(None) self.head.setNext(self.head) def add(self, item): temp = Node(item) temp.setNext(self.head.getNext()) self.head.setNext(temp) def remove(self, item): prev = self.head while prev.getNext() != self.head: cur = prev.getNext() if cur.getData() == item: prev.setNext(cur.getNext()) prev = prev.getNext() def search(self, item): cur = self.head.getNext() while cur != self.head: if cur.getData() == item: return True cur = cur.getNext() return False def empty(self): return self.head.getNext() == self.head def size(self): count = 0 cur = self.head.getNext() while cur != self.head: count += 1 cur = cur.getNext() return count if __name__ == '__main__': s = SinCycLinkedlist() print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size())) s.add(19) s.add(86) print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size())) print('86 is%s in s' % ('' if s.search(86) else ' not',)) print('4 is%s in s' % ('' if s.search(4) else ' not',)) print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size())) s.remove(19) print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))
運行結果:
$ python sincyclinkedlist.py s.empty() == True, s.size() == 0 s.empty() == False, s.size() == 2 86 is in s 4 is not in s s.empty() == False, s.size() == 2 s.empty() == False, s.size() == 1
希望本文所述對大家的Python程序設計有所幫助。
相關文章
macOS M1(AppleSilicon) 安裝TensorFlow環(huán)境
蘋果為M1芯片的Mac提供了TensorFlow的支持,本文主要介紹了如何給使用M1芯片的macOS安裝TensorFlow的環(huán)境,感興趣的可以了解一下2021-08-08python自定義函數(shù)實現(xiàn)最大值的輸出方法
今天小編就為大家分享一篇python自定義函數(shù)實現(xiàn)最大值的輸出方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2019-07-07基于pytorch的RNN實現(xiàn)字符級姓氏文本分類的示例代碼
當使用基于PyTorch的RNN實現(xiàn)字符級姓氏文本分類時,我們可以使用一個非常簡單的RNN模型來處理輸入的字符序列,并將其應用于姓氏分類任務,本文給大家舉了一個基本的示例代碼,需要的朋友可以參考下2023-12-12