Code:
class Node(object):
"""結點"""
def __init__(self, elem):
self.elem = elem
self.next = None
class SingleCycleLinklist(object):
"""單連結清單"""
def __init__(self, node = None):
self.__head = node
if node != None:
node.next = node
def is_empty(self):
"""判斷單連結清單是否為空"""
return self.__head is None
def length(self):
"""單連結清單長度"""
if self.is_empty():
return 0
cur = self.__head # 設定遊标cur
count = 1 # 設定計數器
while cur.next != self.__head:
count += 1
cur = cur.next
return count
def travel(self):
"""周遊單連結清單"""
if self.is_empty():
print("空表")
return
cur = self.__head # 設定遊标cur
while cur.next != self.__head:
print(cur.elem, end=" ")
cur = cur.next
print(cur.elem)
print("連結清單斷沒有?",'No!' if cur.next is self.__head else 'yes!')
def add(self, elem):
"""在表頭增加一個元素"""
if self.is_empty():
self.__head = node
node.next = node
node = Node(elem)
cur = self.__head
while cur.next != self.__head:
cur = cur.next
cur.next = node
node.next = self.__head
self.__head = node
def append(self, elem):
"""在表尾增加元素"""
node = Node(elem)
if self.is_empty():
self.__head = node
node.next = node
else:
cur = self.__head # 設定遊标
while cur.next != self.__head:
cur = cur.next
cur.next = node
node.next = self.__head
def insert(self, pos, elem):
"""在指定處增加元素
:param pos 從0開始
"""
if pos <= 0:
self.add(elem)
elif pos >= (self.length()-1):
self.append(elem)
else:
node = Node(elem)
i = 0
cur = self.__head
while i < (pos-1):
cur = cur.next
i += 1
node.next = cur.next
cur.next = node
def remove(self, elem):
"""删除某一進制素"""
if self.is_empty():
print("SingleLinklist is none!")
return False
cur = self.__head
pre = None
mark = False
while cur.next != self.__head:
if cur.elem != elem:
pre = cur
cur = cur.next
else:
mark = True
if cur == self.__head:
# 頭節點要特殊處理
self.__head = self.__head.next
cur = self.__head
else:
pre.next = cur.next
cur = cur.next
if cur.elem == elem:
pre.next = cur.next
print(mark) # 顯示是否删除成功
def search(self, elem):
"""查找某一進制素"""
if self.is_empty():
return False
cur = self.__head
count = 0
while cur.next != self.__head:
if cur.elem == elem:
return count
cur = cur.next
count += 1
if cur.elem == elem:
return count
return False
if __name__ == "__main__":
li = SingleCycleLinklist()
print("添加與周遊測試:")
print(li.is_empty())
li.remove(666)
li.append(1)
print(li.is_empty())
li.append(2)
li.append(3)
li.append(4)
li.append(5)
li.append(6)
li.travel()
print(li.length())
print()
li.add(0)
li.append(8)
li.travel()
li.insert(3, 666)
li.travel()
li.insert(13, 666)
li.insert(-3, 1000)
li.travel()
print("-" * 10)
print("查找測試:")
print(li.search(1000))
print(li.search(7))
print(li.search(8))
print("-" * 10)
print("删除測試")
li.insert(3, 666)
li.insert(3, 666)
li.insert(3, 666)
li.travel()
li.remove(666)
li.remove(666)
li.travel()
li.remove(6)
li.travel()
li.remove(1000)
li.remove(8)
li.travel()
li.append(6)
li.travel()
li.append(6)
li.travel()
OUTPUT