forked from JackKuo666/Data_Structure_with_Python
-
Notifications
You must be signed in to change notification settings - Fork 0
/
2.2单项循环链表.py
165 lines (148 loc) · 4.35 KB
/
2.2单项循环链表.py
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
# _*_ coding: UTF-8 _*_
# 单链表
class Node(object):
"""
单链表的节点
"""
def __init__(self,item):
# _item 存放数据元素
self.item = item
# _next 是下一个节点的标示
self.next = None
class SinCycLinkedlist(object):
"""单项循环链表"""
def __init__(self):
self._head = None
def is_empty(self):
"""判断链表是否为空"""
return self._head == None
def lengeth(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 False
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
cur.next = node
node.next = self._head
def insert(self, pos, item):
"""在指定位置添加节点"""
if pos <= 0:
self.add(item)
elif pos > (self.lengeth() - 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 False
if __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.lengeth())
ll.travel()
print(ll.search(3))
print(ll.search(7))
ll.remove(1)
print("length:",ll.lengeth())
ll.travel()