Python 實現靜態鏈表案例詳解

 更新時間:2021年09月10日 10:20:14   作者:Yake1965  
這篇文章主要介紹了Python 實現靜態鏈表案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下

靜態鏈表和動態鏈表區別

靜態鏈表和動態鏈表的共同點是,數據之間"一對一"的邏輯關系都是依靠指針(靜態鏈表中稱"游標")來維持。

靜態鏈表

使用靜態鏈表存儲數據,需要預先申請足夠大的一整塊內存空間,也就是說,靜態鏈表存儲數據元素的個數從其創建的那一刻就已經確定,后期無法更改。

不僅如此,靜態鏈表是在固定大小的存儲空間內隨機存儲各個數據元素,這就造成了靜態鏈表中需要使用另一條鏈表(通常稱為"備用鏈表")來記錄空間存儲空間的位置,以便后期分配給新添加元素使用。

這意味著,如果你選擇使用靜態鏈表存儲數據,你需要通過操控兩條鏈表,一條是存儲數據,另一條是記錄空閑空間的位置。

動態鏈表

使用動態鏈表存儲數據,不需要預先申請內存空間,而是在需要的時候才向內存申請。也就是說,動態鏈表存儲數據元素的個數是不限的,想存多少就存多少。

同時,使用動態鏈表的整個過程,你也只需操控一條存儲數據的鏈表。當表中添加或刪除數據元素時,你只需要通過 malloc 或 free 函數來申請或釋放空間即可,實現起來比較簡單。

python 實現的靜態鏈表

靜態鏈表的設計思維非常巧妙,通過索引、游標完成單向鏈表結構,相對于順序結構的列表而言,節省了數據移位、內存碎片的開支。

python 實現的靜態鏈表代碼,靜態鏈表采用的 list 結構存儲。

class Node:
    def __init__(self, next, val=None):
        self.val = val  # 值
        self.next = next  # 游標。最后一個元素的游標必須是 0


class SLinkList:
    # 分配線性表長度、定義線性表
    def __init__(self, size=7):
        self.size = size
        self.link = [Node((i + 1) % self.size) for i in range(self.size)]

    # 線性表清空
    def clearSLL(self):
        self.__init__()

    # 線性表是否為空
    def isEmpty(self):
        return False if self.link[self.size - 1].next else True

        # 查找空位置

    def findEmpty(self):
        ind = self.size
        for i in range(1, self.size - 1):
            if self.link[i].val is None:
                ind = i
                break
        return ind

    # 指定位置插入元素
    def insert(self, ind, ele):
        sua = -1
        # 前一個元素
        pre = self.size - 1
        # 插入元素的位置(第一個空位置)
        insertLoc = self.link[0].next
        # 條件判斷
        if ind < 1 or ind >= pre or insertLoc >= self.size:
            return 0
        # 第一個元素的索引
        for i in range(1, self.size - 1):
            index = self.link[pre].next
            if i == ind:
                self.link[pre].next = insertLoc
                # 元素插入
                self.link[insertLoc].val = ele
                self.link[insertLoc].next = index
                # 首位元素
                self.link[0].next = self.findEmpty()
                sua = 1
                break
            if self.link[index].val is None:
                break
            pre = index
        return sua

    # 查找線性表某位置的元素
    def getByIndex(self, ind):
        if ind < 1 or ind >= self.size - 1:
            return -1

        index = self.link[self.size - 1].next
        if index == 0:
            return -1
        for i in range(1, ind):
            index = self.link[index].next

        return self.link[index].val

        # 查找線性表的元素所在位置
    def locateElement(self, ele):
        index = self.link[self.size - 1].next
        ind = -1
        if index == 0:
            return ind
        for i in range(1, self.size - 1):
            if self.link[index].val == ele:
                ind = i
                break
            if self.link[index].val is None:
                break
            index = self.link[index].next
        return ind

        # 刪除線性表指定位置的元素
    def deleteElement(self, ind):
        sua = -1
        # 前一個索引
        pre = self.size - 1
        for i in range(1, self.size - 1):
            index = self.link[pre].next
            # 當前位置是個空位置
            if self.link[index].val is None:
                break
            # 已經遍歷到第i個位置
            if i == ind:
                self.link[pre].next = self.link[index].next
                self.link[index].val = None
                # 刪除元素的游標指向備用鏈表
                self.link[index].next = self.link[0].next
                # 首位元素
                self.link[0].next = index
                sua = 1
                break
            pre = index
        return sua

        # 按照線性表排序線性表遍歷
    def travelLink(self):
        print("*" * 50)
        index = self.link[self.size - 1].next
        while self.link[index].val:
            print(
                f"value = {self.link[index].val} next = {self.link[index].next}"
            )
            index = self.link[index].next
        print("*" * 50)

    # 按照索引遍歷
    def traversingByIndex(self):
        print("*" * 50)
        for i in range(self.size):
            print(
                f"index = {i}, value = {self.link[i].val} next = {self.link[i].next}"
            )
        print("*" * 50)


if __name__ == '__main__':
    ll = SLinkList()
    ll.traversingByIndex()
    print(ll.isEmpty())
    print(ll.insert(1, 'A'))
    ll.travelLink()
    print(ll.insert(2, 'B'))
    ll.travelLink()
    print(ll.insert(1, 'C'))
    print(ll.insert(4, 'D'))
    ll.travelLink()
    ll.traversingByIndex()
    print(ll.deleteElement(3))
    ll.traversingByIndex()
    ll.travelLink()
    print(ll.isEmpty())
    print(ll.getByIndex(2))
    print(ll.locateElement('BcA'))
    print(ll.clearSLL())

到此這篇關于Python 實現靜態鏈表案例詳解的文章就介紹到這了,更多相關Python 實現靜態鏈表內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持腳本之家!

相關文章

  • python 分離文件名和路徑以及分離文件名和后綴的方法

    python 分離文件名和路徑以及分離文件名和后綴的方法

    今天小編就為大家分享一篇python 分離文件名和路徑以及分離文件名和后綴的方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-10-10
  • Python獲取指定網段正在使用的IP

    Python獲取指定網段正在使用的IP

    這篇文章主要介紹了Python獲取指定網段正在使用的IP的示例代碼,幫助大家更好的利用python進行測試,感興趣的朋友可以了解下
    2020-12-12
  • python中yield的用法詳解

    python中yield的用法詳解

    這篇文章主要介紹了python中yield的用法詳解,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-01-01
  • opencv 圖像禮帽和圖像黑帽的實現

    opencv 圖像禮帽和圖像黑帽的實現

    這篇文章主要介紹了opencv 圖像禮帽和圖像黑帽的實現,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-07-07
  • Python檢測字符串中是否包含某字符集合中的字符

    Python檢測字符串中是否包含某字符集合中的字符

    這篇文章主要介紹了Python檢測字符串中是否包含某字符集合中的字符,需要的朋友可以參考下
    2015-05-05
  • Django框架模板介紹

    Django框架模板介紹

    今天小編就為大家分享一篇關于Django框架模板介紹,小編覺得內容挺不錯的,現在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2019-01-01
  • python3學習之Splash的安裝與實例教程

    python3學習之Splash的安裝與實例教程

    splash 是一個python語言編寫的用于配合scrapy解析js的庫,下面這篇文章主要給大家介紹了關于python3學習之Splash的安裝與使用的一些相關資料,文中通過示例代碼介紹的非常詳細,需要的朋友可以參考下
    2018-07-07
  • Django實現微信小程序的登錄驗證功能并維護登錄態

    Django實現微信小程序的登錄驗證功能并維護登錄態

    這篇文章主要介紹了Django實現小程序的登錄驗證功能并維護登錄態,本文通過實例代碼給大家介紹的非常詳細,具有一定的參考借鑒價值,需要的朋友可以參考下
    2019-07-07
  • python程序需要編譯嗎

    python程序需要編譯嗎

    在本篇文章里小編給大家整理了關于python程序編譯相關的知識點內容,有興趣的朋友們參考學習下。
    2020-06-06
  • python實現得到當前登錄用戶信息的方法

    python實現得到當前登錄用戶信息的方法

    這篇文章主要介紹了python實現得到當前登錄用戶信息的方法,結合實例形式分析了Python在Linux平臺以及Windows平臺使用相關模塊獲取用戶信息的相關操作技巧,需要的朋友可以參考下
    2019-06-06

最新評論

精品国内自产拍在线观看