"""以下为代码正文："""
# coding:utf-8
class Node(object):
"""定义节点类"""
def __init__(self, elem):
self.elem = elem
self.next = None
class SinglyLinkedList(object):
"""定义单向链表类"""
def __init__(self, node=None):
self.__head = node
def is_empty(self):
"""判断链表是否为空"""
return self.__head == None
def length(self):
"""计算链表长度"""
cursor = self.__head
count = 0
while cursor != None:
count += 1
cursor = cursor.next
return count
def travel(self):
"""Ergodic the whole list"""
cursor = self.__head
while cursor != None:
print(cursor.elem, end=" ")
cursor = cursor.next
print("")
def add(self, item):
"""Adds an element at the head"""
node = Node(item)
node.next = self.__head
self.__head = node
def append(self, item):
"""Adds an element at the end"""
node = Node(item)
if self.is_empty():
self.__head = node
else:
cursor = self.__head
while cursor.next != None:
cursor = cursor.next
cursor.next = node
def insert(self, pos, item):
"""Adds an element at the specified position"""
cursor = self.__head #The tutor defined a 'pre' instead of 'cursor'
node = Node(item)
count = 0
if pos <= 0:
self.add(item)
elif pos > self.length()-1:
self.append(item)
else:
while count < (pos-1):
count += 1
cursor = cursor.next
node.next = cursor.next
cursor.next = node
def remove(self, item):
"""Removes a node"""
node = Node(item)
cursor = self.__head
if self.search(item) and self.__head.elem == item:
self.__head = cursor.next
print("-----%d is removed!-----"%item)
elif self.search(item) and self.__head.elem != item:
while cursor.next != None:
if cursor.next.elem == item:
print("cursor.next.elem:%d"%item)
cursor.next = cursor.next.next
print("cursor: %s"%cursor.elem)
else:
cursor = cursor.next
print("======%d is removed!======="%item)
else:
print("%d doesn't exist."%item)
def search(self, item):
"""查找节点是否存在"""
cursor = self.__head
while cursor != None:
if cursor.elem == item:
return True
else:
cursor = cursor.next
return False
"""以下为功能测试："""
if __name__ == "__main__":
sll = SinglyLinkedList()
print(sll.is_empty())
print(sll.length())
sll.append(1)
print(sll.is_empty())
print(sll.length())
sll.append(2)
sll.append(3)
sll.append(4)
sll.append(5)
sll.add(9)
sll.append(6)
sll.append(7)
sll.append(8)
sll.insert(-5, 10)
sll.insert(6, 11)
sll.insert(7, 11)
sll.insert(8, 11)
sll.insert(100, 12)
print(sll.length())
print(sll.search(12))
sll.travel()
sll.remove(9)
sll.travel()
sll.remove(12)
sll.travel()
sll.remove(11)
sll.travel()
sll.remove(8)
sll.travel()
sll.remove(3)
sll.travel()
sll.remove(10)
sll.travel()
sll.remove(20)
sll.travel()
sll.remove(9)
sll.travel()
测试过程中，在remove操作时曾出现过如下异常：AttributeError: 'NoneType' object has no attribute 'elem'.
异常原因：未对链表头部进行专门处理，且游标定义不够准确，现已改正，见上文remove函数。
