Python 单向链接表反转与排序
2017-08-23 本文已影响0人
Tim_Lee
《数据结构与算法：Python 语言描述》（裘宗燕 著）讲解链表的过程清楚明了，反转的算法也很高效，没有使用回归。但是有两处笔误：
- 第95页，单链表反转，
._next应该改为.next。 - 第98页，单链表调整链接法排序，小循环有错误。
裘宗燕教授在“数据结构与算法（Python 语言）”教学材料中列明了新的示例代码，如果发现书中代码有问题，可以直接查看网页上的新代码。
1 单链表反转
唯一就是有一处笔误。
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()
2 单链表的排序
在上面的 LList 类中加入两种排序算法：
class LList(object):
#....
def sort1(self):
"""
方法1：搬动元素
单独提取一个扫描指针，这个扫描指针从头部后面一个位置开始，
扫描指针的值单独提出来，和扫描指针前的序列中的值依次对比，如果序列中的值大，序列的中的那个值就和指针的值进行交换，
最后需要把扫描指针的值再赋给扫描指针的那个元素。
如果前面序列中的值都比较过一遍以后，指针下移一位
"""
if self._head is None:
return
# 从头部的下一个开始
crt = self._head.next
# 大循环
while crt is not None:
# 比较序列的操作，
# 首先拿到序列指针p，且指向表头
p = self._head
# 另外，把扫描指针的值elem提取出来
x = crt.elem
# 如果序列中元素的值比扫描指针的值小，序列指针p向后移动一位，直到序列指针与 crt 扫描指针碰头
while p is not crt and p.elem <= x:
p = p.next
while p is not crt:
x, p.elem = p.elem, x
p = p.next
crt.elem = x
crt = crt.next
def sort(self):
"""
方法2：操作链接
从首结点的下一个开始进行大循环，一个扫描指针的基准点 last，用于扫描指针回归定位，以及扫描指针 crt
小循环就看crt指向的结点是否需要插入，
一旦需要插入，就把插入点前后的链接断开，都链接到新插入的 crt 指针的结点上。
"""
if self._head is None:
return
last = self._head
crt = last.next
while crt is not None:
p = self._head
q = None
while p is not crt and p.elem <= crt.elem:
q = p
p = p.next
if p is crt:
last = crt
else:
last = crt.next
crt.next = p
# 检查q是否为节点，如果不是节点就把首结点设为crt，如果是节点就把q的next连接到crt
if q = None:
self._head = crt
else:
q.next = crt
crt = last.next
