本文实例讲述了Python数据结构与算法之链表定义与用法。分享给大家供大家参考,具体如下:
本文将为大家讲解:
(1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计
(2)链表类插入和删除等成员函数实现时需要考虑的边界条件,
prepend(头部插入)、pop(头部删除)、append(尾部插入)、pop_last(尾部删除)
2.1 插入:
空链表
链表长度为1
插入到末尾
2.2 删除
空链表
链表长度为1
删除末尾元素
(3)从单链表到单链表的一众变体:
带尾节点的单链表
循环单链表
双链表
1. 链表节点的定义
1
2
3
4
|
class LNode: def __init__( self , elem, next_ = None ): self .elem = elem self . next = next_ |
2. 单链表的实现
重点理解插入、删除的实现及其需要考虑的边界条件:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class LinkedListUnderflow(ValueError): pass class LList: 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( 'in pop_last' ) 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 |
简单总结:
(0)能够访问 p.next.next 的前提是 p.next 不为空;
(1)尾部插入,如果链表不为空,需且仅需改变的是尾部节点的指针;
(2)尾部删除,如果链表长度不为空,需且仅需改变的是倒数第二个节点的指针。
单链表的简单变形:具有尾部节点的单链表
1
2
3
4
5
|
class LList1(LList): def __init__( self ): LList.__init__( self ) self ._rear = None ... |
我们仅需重写的是:头部的插入、尾部的插入、尾部的删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
def prepend( self , elem): if self ._head is None : self ._head = LNode(elem) self ._rear = self ._head else : self ._head = LNode(elem, self ._head) def append( self , elem): if self ._head is None : self ._head = LNode(elem) self ._rear = self ._head else : self ._rear. next = LNode(elem) self ._rear = self ._rear. next def pop_last( self ): if self ._head is None : raise LinkedListUnderflow( 'in pop_last' ) 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 self ._rear = p p. next = None return e |
单链表的变体:循环单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class LCList: def __init__( self ): self ._rear = None def prepend( self , elem): if self ._rear is None : self ._rear = LNode(elem) self ._rear. next = self ._rear else : self ._rear. next = LNode(elem, self ._rear. next ) def append( self , elem): self .prepend(elem) self_rear = self ._rear. next def pop( self ): if self ._rear is None : raise LinkedListUnderflow( 'in pop' ) p = self ._rear. next if p is None : self ._rear = None else : self ._rear. next = p. next return p.elem def printall( self ): if self ._rear is None : raise ... p = self ._rear. next while True : print (p.elem) if p is self ._rear: break p = p. next |
希望本文所述对大家Python程序设计有所帮助。
原文链接:http://blog.csdn.net/lanchunhui/article/details/51500342