鏈表（四）

荒廢了一段時間，這段時間實驗室事情多，就沒怎么看數(shù)據(jù)結(jié)構(gòu)（悲痛）。

什么是單向循環(huán)鏈表？

顧名思義，單向循環(huán)鏈表，就是在單向鏈表的基礎(chǔ)上做一些改動，實現(xiàn)鏈表循環(huán)，即將原本尾節(jié)點的next指向None，現(xiàn)指向鏈表的頭節(jié)點，這樣一來就實現(xiàn)了所謂的單項循環(huán)鏈表。
單向循環(huán)鏈表

了解了大致的概念之后，我們需要用代碼實現(xiàn)這個單向循環(huán)鏈表，單向循環(huán)鏈表的代碼也是在單向鏈表的代碼基礎(chǔ)上進(jìn)行更改。
節(jié)點的構(gòu)造是沒有區(qū)別的，可以直接用單向鏈表的代碼。
那關(guān)于首節(jié)點，我們是不是需要一些改動啊，比如讓它指向自己。

class Node():
    '''節(jié)點'''
    def __init__(self,elem):
        self.elem = elem
        self.next = None

class SingleLinkList(object):
    '''單向循環(huán)鏈表'''
    def __init__(self,node=None):
        #內(nèi)部私有函數(shù)，鏈表頭的初始化，可以直接建立空鏈表
        self.__head = node
        if node:
            node.next = node#self.__head指向node，如果node存在那還需要建立一個回環(huán)，讓  note.next指向自己本身
  • 那么關(guān)于探空的功能呢?是不是也無需更改？答案是無需更改 
    def is_empty(self):
        """判斷鏈表是否為空"""
        return self.__head == None

  • 實現(xiàn)求長度的功能：

    單向鏈表結(jié)束的條件：cur == None或者cur == self.__head
    能否用在我們的單項循環(huán)鏈表呢，答案是不可以，因為單向鏈表的判斷語句不僅在尾結(jié)點上復(fù)合，且在頭節(jié)點也符合，故不可用。
    單向循環(huán)鏈表的結(jié)束條件：cur.next == seif.__head
    但是我們的count初始值為1，如果按照這個初值走，最后會少算一個節(jié)點，故初始值改為1。

    def length(self):
        """返回鏈表的長度"""
        #cur游標(biāo)，用來移動遍歷節(jié)點
        #count，用來記錄節(jié)點數(shù)量
        count = 1
        cur = self.__head
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count

考慮一下，若鏈表為空鏈表怎么處理呢，若鏈表只有一個節(jié)點呢？

  def length(self):
        """返回鏈表的長度"""
        #cur游標(biāo)，用來移動遍歷節(jié)點
        #count，用來記錄節(jié)點數(shù)量
        count = 1
        if self.is_empty():
            return 0
        cur = self.__head
        while cur.next != self.__head:#滿足僅有一個節(jié)點的選項
            count += 1
            cur = cur.next
        return count
  • 如何實現(xiàn)遍歷功能：
    如果我們使用單向鏈表的原代碼，會發(fā)現(xiàn)忽略了打印尾結(jié)點，所以最后要加一個打印。
    考慮特殊情況，若這個單向循環(huán)鏈表為空鏈表呢？我們可以預(yù)先做個判斷，若為空則直接返回，不進(jìn)行任何操作。
    若只含有一個節(jié)點呢？直接看代碼吧。
    def travel(self):
        """遍歷鏈表"""
        cur = self.__head
        if self.is_empty():
            return 
        while cur != self.__head:
            print(cur.elem,end=' ')
            cur = cur.next
        print(cur.next,end=' ')

通過代碼分析，若只含有一個節(jié)點，程序不會執(zhí)行while循環(huán)，而是直接打印這個節(jié)點。

  • 實現(xiàn)頭插法（add）:

  1. 方法一
    這個主要是自己要理解

  2. 方法二

    這個方法比較容易理解，首先就是移動游標(biāo)找到尾結(jié)點，當(dāng)終止while循環(huán)的時候，游標(biāo)cur所指向的位置恰好是尾結(jié)點，然后將添加的新節(jié)點node的node.next指向原首節(jié)點也就是self.__head，然后讓self.__head指向node，最后將尾結(jié)點的next，指向我們新添加的這個頭節(jié)點，即cur.next指向node或者也可以指向self.__head，因為此時self.head就指向node。
    考慮一下特殊情況，當(dāng)鏈表為空鏈表時，那么self.__head指向的便是None，cur就在None的位置了，但是None怎么可能會有next呢？顯然程序無法滿足空鏈表的頭插需求；現(xiàn)在考慮一下只有一個節(jié)點的鏈表是否符合要求呢？顯然符合要求；下面是代碼實現(xiàn)。

  def add(self, item):
        """頭部添加節(jié)點"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            node.next = self.__head
            self.__head = node
            cur.next = node
  • 實現(xiàn)尾插法：

  1. 方法一
    這個應(yīng)該不難理解

  2. 方法二
    這個也不難理解

    那我們直接上代碼吧：

    def append(self, item):
        """尾部添加節(jié)點"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node
            node.next = self.__head

驗證一下，若單向循環(huán)鏈表只有一個節(jié)點怎么辦?是不是程序依舊可以實現(xiàn)啊。

  • 實現(xiàn)隨機(jī)插入的（insert）方法：

    我們直接先碼一下，單向鏈表的代碼，看看怎么更改

    因為隨機(jī)插入涉及的頭插和尾插都是調(diào)用，所以我們這里就不在更改，因為已經(jīng)可以實現(xiàn)；唯一需要更改的就是else語句，也就是涉及到中間插入的問題，但是單向循環(huán)鏈表的中間插入和單向鏈表的中間插入并沒有什么區(qū)別啊，所以更無需更改。所以整體同單向鏈表一致，無需再做任何更改。

  • 實現(xiàn)查找某個元素的功能：
    單向鏈表

    我們直接從這個單向鏈表中更改：
    while語句的條件存在問題，要改成while cur.next ！= self.head
    這樣一來if條件判斷到最后一個元素的時候，就會終止循環(huán)了，而不再進(jìn)行判斷，其次還需要考慮的問題是特殊情況，比如空鏈表或者僅有一個節(jié)點的情況(直接上代碼，按照代碼進(jìn)行分析)。

    def search(self, item):
        """查找節(jié)點是否存在"""
        if self.is_empty():
            return False
        cur = self.__head
        while cur.next != self.__head:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        if cur.elem == item:
            return True
        return False

我們考慮一下，單個節(jié)點，代碼也完全可以實現(xiàn)預(yù)期目標(biāo)。

  • 實現(xiàn)刪除節(jié)點的功能：

    觀察代碼，不能拿發(fā)現(xiàn)這個刪除首節(jié)點的情況是最復(fù)雜的，因為涉及要遍歷到尾節(jié)點，然后改變尾節(jié)點的指向。如果是刪除中間節(jié)點的話，首尾節(jié)點無需更改，直接更改中間節(jié)點的指向即可。但同時當(dāng)cur指向尾節(jié)點的時候，會忽略尾節(jié)點的判斷，所以最后要重新判斷一下尾節(jié)點的問題。接下來就是考慮首屆點刪除的問題了。
    還要考慮特殊情況：
  1. 判斷是否為空鏈表，若為空直接返回。
  2. 如果僅有一個節(jié)點，那么程序直接跳出while循環(huán)，執(zhí)行pre.next但pre指向的是None沒有next ,需要讓head直接指向None。
    總程序如下：
   def remove(self, item):
        """刪除一個節(jié)點"""
        if self.is_empty():
            return
        cur = self.__head
        pre = None
        while cur.next != self.__head:
            if cur.elem == item:
                #先判斷是否為頭節(jié)點，然后再去處理頭節(jié)點
                if cur == self.__head:#頭節(jié)點的情況下
                    rear = self.__head
                    self.__head = cur.next
                    while rear.next != self.__head:
                        rear = rear.next
                    self.__head = cur.next
                    rear.next = self.__head
                else:#在中間刪除
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next
        if cur.elem == item:#退出循環(huán)cur指向尾節(jié)點，在尾部刪除
            if cur == self.__head:#鏈表只有一個節(jié)點
                self.__head = None
        else:
            pre.next = cur.next

總體代碼：

class Node():
   '''節(jié)點'''
   def __init__(self,elem):
       self.elem = elem
       self.next = None

class SingleCycleLinkList(object):
   '''單向循環(huán)鏈表'''
   def __init__(self,node=None):
       #內(nèi)部私有函數(shù)，鏈表頭的初始化，可以直接建立空鏈表
       self.__head = node
       if node:
           node.next = node#self.__head指向node，如果node存在那還需要建立一個回環(huán)，讓  note.next指向自己本身

   def is_empty(self):
       """判斷鏈表是否為空"""
       return self.__head == None

   def length(self):
       """返回鏈表的長度"""
       #cur游標(biāo)，用來移動遍歷節(jié)點
       #count，用來記錄節(jié)點數(shù)量
       count = 1
       if self.is_empty():
           return 0
       cur = self.__head
       while cur.next != self.__head:#滿足僅有一個節(jié)點的選項
           count += 1
           cur = cur.next
       return count

   def travel(self):
       """遍歷鏈表"""
       cur = self.__head
       if self.is_empty():
           return
       while cur != self.__head:
           print(cur.elem,end=' ')
           cur = cur.next
       print(cur.next,end=' ')

   def add(self, item):
       """頭部添加節(jié)點"""
       node = Node(item)
       if self.is_empty():
           self.__head = node
           node.next = node
       else:
           cur = self.__head
           while cur.next != self.__head:
               cur = cur.next
           node.next = self.__head
           self.__head = node
           cur.next = node

   def append(self, item):
       """尾部添加節(jié)點"""
       node = Node(item)
       if self.is_empty():
           self.__head = node
           node.next = self.__head
       else:
           cur = self.__head
           while cur.next != self.__head:
               cur = cur.next
           cur.next = node
           node.next = self.__head

   def insert(self, pos, item):
       """在指定位置添加節(jié)點"""
       pre = self.__head
       count = 0
       if pos <= 0:
           self.add(item)
       elif pos >= (self.length()-1):
           self.append(item)
       else:
           while count < (pos-1):
               count += 1
               pre = pre.next
           node = Node(item)
           node.next = pre.next
           pre.next = node

   def remove(self, item):
       """刪除一個節(jié)點"""
       if self.is_empty():
           return
       cur = self.__head
       pre = None
       while cur.next != self.__head:
           if cur.elem == item:
               #先判斷是否為頭節(jié)點，然后再去處理頭節(jié)點
               if cur == self.__head:#頭節(jié)點的情況下
                   rear = self.__head
                   self.__head = cur.next
                   while rear.next != self.__head:
                       rear = rear.next
                   self.__head = cur.next
                   rear.next = self.__head
               else:#在中間刪除
                   pre.next = cur.next
               break
           else:
               pre = cur
               cur = cur.next
       if cur.elem == item:#退出循環(huán)cur指向尾節(jié)點，在尾部刪除
           if cur == self.__head:#鏈表只有一個節(jié)點
               self.__head = None
       else:
           pre.next = cur.next


   def search(self, item):
       """查找節(jié)點是否存在"""
       if self.is_empty():
           return False
       cur = self.__head
       while cur.next != self.__head:
           if cur.elem == item:
               return True
           else:
               cur = cur.next
       if cur.elem == item:
           return True
       return False



if __name__ == '__main__':
   li = SingleCycleLinkList()
   print(li.is_empty())
   print(li.length())

   li.append(1)
   li.append(2)
   print(li.is_empty())
   print(li.length())

   li.append(3)
   li.append(4)
   li.add(10)
   li.add(20)
   li.insert(2,30)
   li.insert(10,1000)
   li.insert(0,999)
   li.travel()
   print()
   print(li.search(20))
   print(li.search(123))
   li.travel()
   li.remove(999)
   li.travel()
   li.remove(1000)
   li.travel()
   li.remove(30)
   li.travel()

測試結(jié)果：

D:\anaconda\python.exe D:/bilibili大學(xué)/簡書代碼/singe_cycle_link_list.py
True
0
False
2
<__main__.Node object at 0x000001C2CEDBB390> 
True
False
<__main__.Node object at 0x000001C2CEDBB390> <__main__.Node object at 0x000001C2CEDBB438> <__main__.Node object at 0x000001C2CEDBB438> <__main__.Node object at 0x000001C2CEDBB438> 
Process finished with exit code 0
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 有頭鏈表（注意：頭結(jié)點有的地方是全局變量） 初學(xué)者學(xué)自于大話數(shù)據(jù)結(jié)構(gòu)，不足及錯誤的地方請讀者提出來，謝謝。 可加 ...
    lxr_閱讀 983評論 0贊 2
  • 搞懂單鏈表常見面試題 Hello 繼上次的 搞懂基本排序算法，這個一星期，我總結(jié)了，我所學(xué)習(xí)和思考的單鏈表基礎(chǔ)知識...
    醒著的碼者閱讀 4,742評論 1贊 45
  • 摘自《維基百科》?鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲...
    ChinaChong閱讀 1,827評論 0贊 52
  • 芃芃棫樸，薪之槱之。濟(jì)濟(jì)辟王，左右趣之。 濟(jì)濟(jì)辟王，左右奉璋。奉璋峩峩，髦士攸宜。 淠彼涇舟，烝徒楫之。周王于邁，...
    尊敬的王二閱讀 890評論 9贊 14
  • 有人把沖動比作魔鬼，其實不然，一瞬間的沖動也許會幻成最美的風(fēng)景。 小時候總是在想，這個世界太美好太大太繁華，美...
    段小段姑娘閱讀 323評論 0贊 0

友情鏈接更多精彩內(nèi)容