课时29 单项循环链表
原有的单链表为节点应该指向None，而此刻让它指向头节点，变成了单向循环链表。
?
?
class Node(object):
def __init__(self,item):
self.elem=item
self.next=None
class SingleLinkList(object):
def __init__(self,node=None):
"""单向循环链表"""
self.__head=node
if node: #如果有节点的话，应该让这个节点指向自己
node.next=node
def is_empty(self):
return self.__head==None
def length(self):
if self.is_empty():
return 0
else:
cur=self.__head
count=1
if cur.next!=self.__head:
count+=1
cur=cur.next
return count
def travel(self):
if self.is_empty():
return None
cur=self.__head
while cur.next!=self.__head:
print(cur.elem,end=" ")
cur=cur.next
#推出循环，cur指向尾节点，但尾节点的元素并没有并打印
print(cur.elem)?课时30单向链表插入元素
头插法，前面与单链表相同。
但是需要让尾节点的next区域指向插入的节点。
?
?需要考虑特殊情况，即只有一个节点的场合，和空链表的场合。
尾部插入，则需要让插入后的尾部的next区域指向头节点。
?课时31
查找节点依旧先要遍历。
class Node(object):
def __init__(self,item):
self.elem=item
self.next=None
class SingleLinkList(object):
def __init__(self,node=None):
"""单向循环链表"""
self.__head=node
if node: #如果有节点的话，应该让这个节点指向自己
node.next=node
def is_empty(self):
return self.__head==None
def length(self):
if self.is_empty():
return 0
else:
cur=self.__head
count=1
if cur.next!=self.__head:
count+=1
cur=cur.next
return count
def travel(self):
if self.is_empty():
return None
cur=self.__head
while cur.next!=self.__head:
print(cur.elem,end=" ")
cur=cur.next
#推出循环，cur指向尾节点，但尾节点的元素并没有并打印
print(cur.elem)
def add(self,item):
node=Node()
if self.is_empty():#链表为空的话，cur指向的是none，没有next区域，会报错，所以需要这一步
self.__head=node
node.next=node
else:
cur=self.__head
while cur.next!=self.__head:
cur=cur.next
#推出循环，cur指向尾节点
node.next=self.__head
self.__head=node
cur.next=self.__head #或者cur.next=node
def append(self,item):
node=Node(item)
if self.is_empty():
self.__head=node
node.next=node
else:
cur=self.__head
while cur.next!=self.__head:
cur=cur.next
node.next=self.__head
cur.next=node
def insert(self, pos, item): # pos为指定的位置
"""指定位置添加元素"""
""":param pos 从0开始"""
if pos <= 0:
self.add(item) # pos小于或等于零，那么就是在头部插入元素，即用头插法。
elif pos > self.lengh() - 1:
self.append(item) # 如果pos大于链表最后的下标，那么就是在尾部添加。
else:
pre = self.__head
count = 0
while count < (pos - 1):
count += 1
pre = pre.next
# 当退出循环后，pre指向pos-1位置
node = Node(item)
node.next = pre.next
pre.next = node
def search(self,item):
if self.is_empty():
return False
else:
cur=self.__head
while cur.next!=self.__head:
if cur.elem==item:
return True
else:
cur=cur.next
#推出循环，此时指向尾节点，此时需要判断该尾节点是否为查找元素
if cur.elem==item:
return True
def remove(self,item):
if self.is_empty():
return False
cur=self.__head
pre=None
while cur.next!=self.__head:
if cur.elem==item:
#先判断此节点是否为头节点
if cur==self.__head:
#头结点的时候，要找尾节点去指向头节点后的地方。
rear=self.__head
while rear.next!=self.__head:
rear=rear.next
rear.next=cur.next
self.__head=cur.next
else:
#中间节点
pre.next=cur.next
return
else:
pre=cur
cur=cur.next
#推出循坏，指标指向尾节点
if cur.elem==item:
if cur==self.__head:
self.__head==None
else:
pre.next=cur.next