鏈表（二）

鏈表的構(gòu)造：
class Node():
    '''節(jié)點(diǎn)'''
    def __init__(self,elem):
        self.elem = elem
        self.next = None

class SingleLinkList(object):
    '''單鏈表'''
    def __init__(self,node=None):
        #內(nèi)部私有函數(shù)，鏈表頭的初始化，可以直接建立空鏈表
        self.__head = node

    def is_empty(self):
        """判斷鏈表是否為空"""
        pass

    def length(self):
        """返回鏈表的長(zhǎng)度"""
        pass

    def travel(self):
        """遍歷鏈表"""
        pass

    def add(self, item):
        """頭部添加節(jié)點(diǎn)"""
        pass

    def append(self, item):
        """尾部添加節(jié)點(diǎn)"""
        pass

    def insert(self, pos, item):
        """在指定位置添加節(jié)點(diǎn)"""
        pass

    def remove(self, item):
        """刪除一個(gè)節(jié)點(diǎn)"""
        pass

    def search(self, item):
        """查找節(jié)點(diǎn)是否存在"""
        pass


single_obj = SingleLinkList()
single_obj.travel()

這部分主要是考慮P節(jié)點(diǎn)指向的問(wèn)題，節(jié)點(diǎn)類(lèi)已經(jīng)有了；

關(guān)于這一點(diǎn)，也可以寫(xiě)成：

 def __init__(self,node):
        #內(nèi)部私有函數(shù)，鏈表頭的初始化，可以直接建立空鏈表
        self.__head = None
node = Node(100)
single_obj = SingleLinkList(node)

這樣也可以就是不太高級(jí)。


如圖，簡(jiǎn)寫(xiě)單鏈接表為sll，因?yàn)镾ingleListLink()傳入的值為空，故默認(rèn)node = None，即__head指向?yàn)榭?，也就是P指向?yàn)镹one。node = Node(100)，產(chǎn)生了節(jié)點(diǎn)類(lèi)，節(jié)點(diǎn)包括兩部分，一部分是elem，一部分是next。下一步就是讓__head指向100這個(gè)節(jié)點(diǎn)。

  • 我們先來(lái)看看如何實(shí)現(xiàn)第一個(gè)探空的功能，即判讀鏈表是否為空：

    這么寫(xiě)應(yīng)該不難理解，鏈表為空那么__head的指向就為空，利用一下羅即判讀，如self.__head ==None則返回True,代表鏈表為空，else鏈表不為空。

  • 實(shí)現(xiàn)第二個(gè)功能，判斷鏈表的長(zhǎng)度即length()：

    我們先模擬幾個(gè)節(jié)點(diǎn)，并建立游標(biāo)cur：
    之所以不采用cur.next == None，是考慮到第三個(gè)節(jié)點(diǎn)也就是300節(jié)點(diǎn)處的cur.next == None,這樣一來(lái)，記錄節(jié)點(diǎn)數(shù)目的時(shí)候就會(huì)少一個(gè)，cur = cur.next就可以移動(dòng)游標(biāo)了。 同時(shí)我們還要考慮特殊情況，當(dāng)這個(gè)鏈表為空鏈表的時(shí)候我們的程序能否實(shí)現(xiàn)要求，當(dāng)鏈表為空，即self.__head==None，cur == None，count = 0，符合我們的預(yù)期要求。

  • 實(shí)現(xiàn)第三個(gè)功能，遍歷鏈表（travel）:

    基本上和判斷鏈表長(zhǎng)度一樣，進(jìn)入循環(huán)打印出來(lái)即可，同樣不能采用cur.next == None，否則會(huì)丟掉最后一個(gè)節(jié)點(diǎn)。

  • 實(shí)現(xiàn)第四個(gè)功能，尾部添加節(jié)點(diǎn)，也就是append()功能：

    比如我們要在尾部添加400這個(gè)節(jié)點(diǎn)，就是要將300節(jié)點(diǎn)的next指向400節(jié)點(diǎn)。
    我們先建立一個(gè)node節(jié)點(diǎn)，移動(dòng)游標(biāo)cur，移動(dòng)到cur.next = None，然后將cur所在的節(jié)點(diǎn)的next指向我們先建立的node節(jié)點(diǎn)即可。這時(shí)我們還需要考慮特殊情況，即空鏈表的情況向下如何實(shí)現(xiàn)我們的操作：
    self.__head已經(jīng)指向None了怎么還能有next呢，那么我們就要針對(duì)性的改一下。

    我們這樣更改是不是可以；但利用之前探空的功能豈不是更好。
    這樣一來(lái)代碼讀起來(lái)會(huì)更流暢。
class Node():
    '''節(jié)點(diǎn)'''
    def __init__(self,elem):
        self.elem = elem
        self.next = None

class SingleLinkList(object):
    '''單鏈表'''
    def __init__(self,node=None):
        #內(nèi)部私有函數(shù)，鏈表頭的初始化，可以直接建立空鏈表
        self.__head = node

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

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

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

    def add(self, item):
        """頭部添加節(jié)點(diǎn)"""
        pass

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

    def insert(self, pos, item):
        """在指定位置添加節(jié)點(diǎn)"""
        pass

    def remove(self, item):
        """刪除一個(gè)節(jié)點(diǎn)"""
        pass

    def search(self, item):
        """查找節(jié)點(diǎn)是否存在"""
        pass


if __name__ == '__main__':
    li = SingleLinkList()
    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.travel()

測(cè)試結(jié)果：

True
0
False
2
1 2 3 4

  • 實(shí)現(xiàn)第五個(gè)功能，即像鏈表頭部添加元素（add）：

    假如400節(jié)點(diǎn)是我們即將插入的新元素，那么怎么更改指向才能實(shí)現(xiàn)呢？
    這樣的指向是不是我們想要的結(jié)果呢？這樣一來(lái)就很簡(jiǎn)單了。
    考慮一下特殊情況，如果一上來(lái)這個(gè)鏈表就是一個(gè)空鏈表呢？那么node.next = self.__head指向的就是None，因?yàn)閟elf.__head在空鏈表中指向None，self.__head 指向node是沒(méi)有問(wèn)題的，測(cè)試結(jié)果表明一切也OK。
  • 實(shí)現(xiàn)第六個(gè)功能，任意位置插入（insert）：
    比如insert(2,400)如圖所示：
    要想實(shí)現(xiàn)這個(gè)操作要如何更改程序呢？
    為了方便大家理解，我們把移動(dòng)到指定位置的前一個(gè)元素的游標(biāo)叫做pre不再是叫做cur我們要在第二個(gè)位置插入400，是不是就要在第一個(gè)位置上開(kāi)始改變指向呢？
    def insert(self, pos, item):
        """在指定位置添加節(jié)點(diǎn)"""
        pre = self.__head
        count = 0
        while count < (pos-1):
            count += 1
            pre = pre.next
        node = Node(item)
        node.next = pre.next
        pre.next = node

這么寫(xiě)是不是很OK，但是還需要考慮特殊情況，如果用戶輸入的pos =< 0怎么辦，我們只能默認(rèn)是0，故采用頭插法。如果大于等于鏈表的總長(zhǎng)度，那就是尾插法了。

    def insert(self, pos, item):
        """在指定位置添加節(jié)點(diǎn)"""
        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

這么一來(lái)就很清晰了，測(cè)試結(jié)果也不存在問(wèn)題。

  • 實(shí)現(xiàn)第七個(gè)功能，實(shí)現(xiàn)查找（research）功能：

    比如我們要查找這個(gè)400節(jié)點(diǎn)是否在鏈表內(nèi)，我們需要移動(dòng)游標(biāo)遍歷每一個(gè)節(jié)點(diǎn)，然后一個(gè)個(gè)的去比對(duì)，等于我們的item就返回真，不等于我們的item就返回假。
    但是還需要考慮特殊情況，也就是當(dāng)節(jié)點(diǎn)為空節(jié)點(diǎn)的時(shí)候如何處理呢？
    空節(jié)點(diǎn)代表cur = self.__head = None，就不用執(zhí)行while循環(huán)而是直接跳到return Flase，這樣一來(lái)也符合功能的需求，測(cè)試結(jié)果也不存在問(wèn)題。

  • 實(shí)現(xiàn)第八個(gè)功能，即實(shí)現(xiàn)刪除（remove）功能：

    比如我們需要?jiǎng)h除400這個(gè)節(jié)點(diǎn)元素，刪除的方法就是講400節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的next指向400節(jié)點(diǎn)的后一個(gè)300節(jié)點(diǎn)，這樣一來(lái)就有兩個(gè)實(shí)現(xiàn)方法。

    1. 建立兩個(gè)游標(biāo)，一個(gè)pre，一個(gè)cur，pre游標(biāo)指向400節(jié)點(diǎn)之前的20節(jié)點(diǎn)，cur游標(biāo)指向要?jiǎng)h除的400節(jié)點(diǎn)，pre.next = cur.next
    2. 建立一個(gè)游標(biāo)，實(shí)現(xiàn)同1相同的功能，pre游標(biāo)指向要?jiǎng)h除的400節(jié)點(diǎn)之前的20節(jié)點(diǎn)，pre.next = pre.next.next
      法二我可以理解，那么我就說(shuō)說(shuō)法一吧，如果我們要?jiǎng)h除的元素正好在中間：
      這樣是不是沒(méi)問(wèn)題
      考慮在兩頭和空鏈表的特殊情況如何處理：
      空鏈表
      意味著cur = self.__head = None，程序不執(zhí)行while循環(huán)，不執(zhí)行任何操作，這個(gè)是沒(méi)有問(wèn)題的。
      刪除開(kāi)頭的節(jié)點(diǎn)
      我們還要考慮一種特殊情況，就是這個(gè)鏈表只有一個(gè)節(jié)點(diǎn)怎么辦，也就是cur.next = None，刪除后正好self.__head = None，我們的程序可以實(shí)現(xiàn)這個(gè)特殊情況。
      刪除結(jié)尾的節(jié)點(diǎn)
      我們理解一下，如果刪除的是最后一個(gè)尾節(jié)點(diǎn)300，就是講指向400的pre游標(biāo)指向位于300節(jié)點(diǎn)的cur游標(biāo)所指向的None，恰好可以完美實(shí)現(xiàn)，那么我們的代碼就不存在問(wèn)題。
      測(cè)試一切正常

完整代碼如下：

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

class SingleLinkList(object):
    '''單鏈表'''
    def __init__(self,node=None):
        #內(nèi)部私有函數(shù)，鏈表頭的初始化，可以直接建立空鏈表
        self.__head = node

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

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

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

    def add(self, item):
        """頭部添加節(jié)點(diǎn)"""
        node = Node(item)
        node.next = self.__head
        self.__head = node

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

    def insert(self, pos, item):
        """在指定位置添加節(jié)點(diǎn)"""
        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):
        """刪除一個(gè)節(jié)點(diǎn)"""
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                #先判斷是否為頭節(jié)點(diǎn)，然后再去處理頭節(jié)點(diǎn)
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next


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



if __name__ == '__main__':
    li = SingleLinkList()
    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()
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

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

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