python 与 数据结构 第三章 线性表 （中）

Question

3.3 链接表

基于链接技术实现的线性表称为链接表或者链表

3.2.3 单链表

• 一个单链表由一些具体的表节点构成
• 每个节点是一个对象，有自己的标识
• 节点之间通过节点链接建立起单向的顺序联系

定义一个简单的表结点类：

class LNode:
    def __init__(self, elem, next_=None):
        self.elem = elem
        self.next = next_

基本操作:

• 创建空表：O(1)
• 删除表：在 Python 里是 O(1)。当然存储管理也需要时间
• 判断空表：O(1)
• 加入元素（都需要加一个 T(分配) 的时间）
  • 首端加入元素：O(1)
  • 尾端加入元素：O(n)，因为需要找到表的最后结点
• 定位加入元素：O(n)，平均情况和最坏情况
• 删除元素：
  • 首端删除元素：O(1)；尾端删除：O(n)
  • 定位删除元素：O(n)，平均情况和最坏情况
• 其他删除通常需要扫描整个表或其一部分，O(n) 操作

class LinkedListUnderflow(ValueError):
	# 自定义一个 Exception
	pass

class LList(object):

    def __init__(self):
        self._head = None

    def is_empty(self):
        return not self._head

    def prepend(self, elem):
        self._head = LNode(elem, self._head)

    def pop(self):
        if not self._head:
            raise LinkedListUnderflow('in pop')
        e = self._head.elem
        self._head = self._head.next
        return e

后端操作

def append(self, elem):
    if not self._head:
        self._head = LNode(elem)
        return
    p = self._head
    while p.next:
        p = p.next
    p.next = LNode(elem)
    
def pop_last(self):
    if not self._head:  # 空表
        raise LinkedListUnderflow('in pop_last')
    p = self._head

    if not p.next:  # 表中只有一个元素
        e = p.elem
        self._head = None
        return e
    while p.next.next:
        p = p.next
    e = p.next.elem
    p.next = None
    return e

其他操作

def find(self, pred):
    p = self._head
    while p:
        if pred(p.elem):
            return p.elem
        p = p.next

def printall(self):
    p = self._head
    while p:
        print p.elem
        p = p.next

其他操作详见代码: LList.py

3.4 链表的变形

3.4.1 单链表简单变形

表对象增加一个表尾节点引用域。有了这个域，只需常量时间就能找到尾节点O(1)

def __init__(self):
    LList.__init__(self)
    self._rear = None

def prepend(self):
    if not self._head:
        self._head = LNode(elem, self._head)
        self._rear = self._head
    else:
        self._head = LNode(elem, self._head)

def append(self, elem):
    if not self._head:
        self._head = LNode(elem, self._head)
        self._rear = self._head
    else:
        self._rear.next = LNode(elem)
        self._rear = self._rear.next

def pop_last(self):
    if not self._head:
        raise LinkedListUnderflow('in pop last')
    p = self._head
    if not p.next:  # 表中只有一个元素
        e = p.elem
        self._head = None
        return e
    while p.next.next:
        p = p.next
    e = p.next.elem
    p.next = None
    self._rear = p

3.4.2 循环单链表

class LCList(object):

    def __init__(self):
        self._rear = None

    def is_empty(self):
        return self._rear

    def prepend(self, elem):  # 前端插入
        p = LNode(elem)
        if not self._rear:
            p.next = p
            self._rear = p
        else:
            p.next = self._rear.next
            self._rear.next = p

    def append(self, elem):  # 尾端插入
        self.prepend(elem)  # 因为是循环，所以尾端插入跟前端插入一样，只要保证最后 self._rear 节点指向它
        self._rear = self._rear.next

    def pop(self):  # 前端弹出
        if not self._rear:
            raise LinkedListUnderflow('in pop of LCList')
        p = self._rear.next
        if self._rear is p:  # 只有一个节点
            self._rear = None
        else:
            self._rear.next = p.next
        return p.elem

    def printall(self):
        if self.is_empty():
            return
        p = self._rear.next
        while p:
            print p.elem
            if p is self._rear:
                break
            p = p.next

3.4.3 双链表

如果希望两端插入和删除都能高效完成，就必须修改节点的基本设计，加入另一个方向的链接，每个结点都需要增加一个链接域，增加的空间开销和结点数成正比，是 O(n)

定义一个 DLNode 结点

class DLNode(object):

    def __init__(self, elem, prev=None, next_=None):
        self.elem = elem
        self.next = next_
        self.prev = prev

简单的操作

class DLList(LList1):

    def __init__(self):
        LList1.__init__(self)

    def prepend(self, elem):
        p = DLNode(elem, None, self._head)
        if not self._head:
            self._rear = p
        else:
            p.next.prev = p
        self._head = p

    def append(self, elem):
        p = DLNode(elem, self._rear, None)
        if not self._head:
            self._head = p
        else:
            p.prev.next = p
        self._rear = p

    def pop(self):
        if not self._head:
            raise LinkedListUnderflow('in pop of DLList')
        e = self._head.elem
        self._head = self._head.next
        if self._head:
            self._head.prev = None
        return e

    def pop_last(self):
        if not self._head:
            raise LinkedListUnderflow('in pop_last of DLList')
        e = self._rear.elem
        self._rear = self._rear.prev
        if self._rear:
            self._rear.next = None
        else:
            self._head = None
        return e

循环双链表待实现

链表反转

如何实现 python 中 list 类的 reverse

对于链表，可以修改结点的链接关系来改变表元素顺序

def rev(self):
    p = None
    while self._head:
        q = self._head