提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  系统

当前栏目

Meta佛萨奇系统开发2.0讲解丨Meta魔豹联盟模式系统开发方案功能

系统模式开发 功能 方案 讲解 2.0 Meta
2023-06-13 09:17:38 时间

单链表反转

唯一就是有一处笔误。 3.4.4 两个链表操作/链表反转 书中代码是：

def rev(self):
    p = None
    while self._head is not None:
        q = self._head
        self._head = q.next # 摘下原来的原结点
        q._next = p 
        p = q               # 将刚摘下的结点加入 p 引用的结点序列
    self._head = p          # 反转后的结点序列已经做好，重置表头链接

其中倒数第三行的 ._next 应该改为 .next，因为结点类 LNode 中类属性是.next。

        q.next = p

如果把其中的 p 变量更名为 tmp_list_head，把 q 改为 sliced_node可能更能理解。

完整的程序，包括测试如下：

# coding:utf8

class LinkedListUnderflow(ValueError):
    pass

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

class LList(object):
    def __init__(self):
        self._head = None
    
    def is_empty(self):
        return self._head is None

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

    def pop(self):
        if self._head is None:
            raise LinkedListUnderflow("in pop")
        e = self._head.elem
        self._head = self._head.next
        return e

    def append(self, elem):
        if self._head is None:
            self._head = LNode(elem)
            return
        p = self._head
        while p.next is not None:
            p = p.next
        p.next = LNode(elem)

    def pop_last(self):
        if self._head is None:
            raise LinkedListUnderflow
        p = self._head
        if p.next is None:
            e = p.elem
            self._head = None
            return e
        while p.next.next is not None:
            p = p.next
        e = p.next.elem
        p.next = None
        return e

    def rev(self):
        tmp_list_head = None
        while self._head is not None:
            sliced_node = self._head
            self._head = self._head.next
            sliced_node.next = tmp_list_head
            tmp_list_head = sliced_node 
        self._head = tmp_list_head

    def elements(self):
        p = self._head
        while p is not None:
            yield p.elem
            p = p.next

    
def main():
    lst = LList()
    for i in range(10):
        lst.append(i)
    print "original linked list:"
    for i in lst.elements():
        print i
    
    print '-' * 25
    print "reserved linked list:"

    lst.rev()
    for i in lst.elements():
        print i 

if __name__ == '__main__':
    main()

相关文章