本文实例讲述了Python实现的单向循环链表功能。分享给大家供大家参考，具体如下：
概述：
单向循环链表是指在单链表的基础上，表的最后一个元素指向链表头结点，不再是为空。
由图可知，单向循环链表的判断条件不再是表为空了，而变成了是否到表头。
操作
is_empty() 判断链表是否为空
length() 返回链表的长度
travel() 遍历
add(item) 在头部添加一个节点
append(item) 在尾部添加一个节点
insert(pos, item) 在指定位置pos添加节点
remove(item) 删除一个节点
search(item) 查找节点是否存在
具体代码：
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
class Node(object): """节点""" def __init__(self, item): self.item = item self.next = Noneclass SinCycLinkedlist(object): """单向循环链表""" def __init__(self): self._head = None def is_empty(self): """判断链表是否为空""" return self._head == None def length(self): """返回链表的长度""" # 如果链表为空，返回长度0 if self.is_empty(): return 0 count = 1 cur = self._head while cur.next != self._head: count += 1 cur = cur.next return count def travel(self): """遍历链表""" if self.is_empty(): return cur = self._head print cur.item, while cur.next != self._head: cur = cur.next print cur.item, print "" def add(self, item): """头部添加节点""" node = Node(item) if self.is_empty(): self._head = node node.next = self._head else: #添加的节点指向_head node.next = self._head # 移到链表尾部，将尾部节点的next指向node cur = self._head while cur.next != self._head: cur = cur.next cur.next = node #_head指向添加node的 self._head = node def append(self, item): """尾部添加节点""" node = Node(item) if self.is_empty(): self._head = node node.next = self._head else: # 移到链表尾部 cur = self._head while cur.next != self._head: cur = cur.next # 将尾节点指向node cur.next = node # 将node指向头节点_head node.next = self._head def insert(self, pos, item): """在指定位置添加节点""" if pos <= 0: self.add(item) elif pos > (self.length()-1): self.append(item) else: node = Node(item) cur = self._head count = 0 # 移动到指定位置的前一个位置 while count < (pos-1): count += 1 cur = cur.next node.next = cur.next cur.next = node def remove(self, item): """删除一个节点""" # 若链表为空，则直接返回 if self.is_empty(): return # 将cur指向头节点 cur = self._head pre = None # 若头节点的元素就是要查找的元素item if cur.item == item: # 如果链表不止一个节点 if cur.next != self._head: # 先找到尾节点，将尾节点的next指向第二个节点 while cur.next != self._head: cur = cur.next # cur指向了尾节点 cur.next = self._head.next self._head = self._head.next else: # 链表只有一个节点 self._head = None else: pre = self._head # 第一个节点不是要删除的 while cur.next != self._head: # 找到了要删除的元素 if cur.item == item: # 删除 pre.next = cur.next return else: pre = cur cur = cur.next # cur 指向尾节点 if cur.item == item: # 尾部删除 pre.next = cur.next def search(self, item): """查找节点是否存在""" if self.is_empty(): return False cur = self._head if cur.item == item: return True while cur.next != self._head: cur = cur.next if cur.item == item: return True return Falseif __name__ == "__main__": ll = SinCycLinkedlist() ll.add(1) ll.add(2) ll.append(3) ll.insert(2, 4) ll.insert(4, 5) ll.insert(0, 6) print "length:",ll.length() ll.travel() print ll.search(3) print ll.search(7) ll.remove(1) print "length:",ll.length() ll.travel() |
运行结果：
希望本文所述对大家Python程序设计有所帮助。
原文链接：https://www.cnblogs.com/Erick-L/p/7209208.html
