數(shù)據(jù)結(jié)構(gòu)之鏈表變形

一、單鏈表的簡單變形

帶有尾部結(jié)點的單鏈表.png

為此，我們，需要設計一個新的鏈表結(jié)構(gòu)，但是從0開始是不可取的，往往帶來的結(jié)果是重復造輪子，所以，我們采用在python中常見的繼承方式來創(chuàng)建一個類，如所有類都繼承自object，所有異常類都繼承自基本的異常類一樣，往后創(chuàng)建的幾乎所有鏈表結(jié)構(gòu)都繼承自前面創(chuàng)建的List_Single類。如果需要加入或者改動基本類中的功能，只需要==新增==或者==重寫==即可。

1.1、初始化

class List_Single_Trans(List_Single):
    '''
    加入一個尾部結(jié)點
    '''
    def __init__(self):
        List_Single.__init__(self)#繼承基類中有的初始化
        self._rear = None#初始化尾結(jié)點引用域

1.2、方法重寫

1、prepend

這里還有一個問題，由于加入了新的引用域，當鏈表為空時，新插入的第一個結(jié)點也是最后一個結(jié)點，所以，prepend（前端插入）方法也需要重新定義：

1. 判斷鏈表是否為空
2. 如果鏈表不為空：

    def prepend(self,elem):
        '''
        前端插入方法
        '''
        if self._head is None:#鏈表為空
            self._head = LNode(elem,self._head)
            self._rear = self._head
        else:
            self._head = LNode(elem,self._head)

為了可視化，編者做了兩張圖

首端插入流程圖

原理圖

2、append

  def append(self,elem):
        '''
        后端插入結(jié)點
        :param elem:新結(jié)點的值
        :return:不返回
        '''
        if self._head is None:
            self._head = LNode(elem,self._head)
            self._rear = self._head
        else:
            #將新加入的結(jié)點連在現(xiàn)有的尾端結(jié)點后
            self._rear.next = LNode(elem)
            #將尾端結(jié)點指向新加入的結(jié)點
            self._rear = self._rear.next

3、pop_last

刪除最后一個結(jié)點，并且將尾結(jié)點中的元素值返回

1. 判斷是否為空表
2. 判斷首尾結(jié)點是否為一個【盡量保持用已有的類中定義的方法】
3. 找到上一個結(jié)點，為o
4. 保存最后一個結(jié)點中的值
5. 使上一結(jié)點變?yōu)樽詈笠粋€結(jié)點，尾端指針指向上一個元素
6. 返回值

    def pop_last(self):
        '''
        刪除最后一個結(jié)點，并且將尾結(jié)點中的元素值返回
        :return: 最后一個結(jié)點的元素值
        '''
        if self._head is None:
            raise LinkedListUnderflow('in pop_last')#程序在此結(jié)束，不需要else
        p = self._head
        if p.next is None:
            e = p.elem
            self._head = None
            return e#程序在此結(jié)束，不需要else
        while p.next.next is not None:#找到最后一個結(jié)點的前一個結(jié)點，
            # 例如如果最后一個結(jié)點為r，那么r.next = None
            # 則換到此處則為 p.next= r 即p.next為下一個結(jié)點，那么p即為最后一個結(jié)點的上一個結(jié)點
            p = p.next

        #存值
        e = p.next.elem
        #使p變?yōu)樽詈笠粋€結(jié)點，即使引用域置為None
        p.next = None
        #尾端指針指向最后一個結(jié)點的上一個結(jié)點，也就是p
        self._rear = p

        return e

4、使用示例

mlist1 = List_Single_Trans()
for i in range(10):
    mlist1.prepend(i)

for i in range(11,20):
    mlist1.append(i)

#繼承printall方法
mlist1.printall()#9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 11, 12, 13, 14, 15, 16, 17, 18, 19

for i in range(5):
    mlist1.pop_last()
    
mlist1.printall()#9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 11, 12, 13, 14

二、聯(lián)系方式

如果在本篇文章中有發(fā)現(xiàn)任何錯誤，或者您有更好的建議或思維方式，歡迎與我聯(lián)系！

聯(lián)系方式：psywency@foxmail.com

備用：wency03lk@outlook.com

三、下期預告

下一期是講循環(huán)列表哦！為了打?qū)嵒A，編者在前期并不會很快，基礎的學好了后期各種高能的時候才接得住哇！

今天給你們比兩個心??:blue_heart: