文章目录
单向循环链表操作,具体实施
#!/usr/bin/env python
#coding:utf8
#++++++++++++description++++++++++++#
"""
@author:ying
@contact:1074020480@qq.com
@site:
@software: PyCharm
@file: SingleCycle.py
@time: 2019/11/13 下午1:40
"""
#+++++++++++++++++++++++++++++++++++#
class SingleNode(object):
"""节点"""
def __init__(self, arg):
# arg存放数据元素
self.arg = arg
# next是下一个节点的标识
self.next = None
class SingleCycleList(object):
"""单项循环链表"""
def __init__(self, node=None):
self.__head = None # 空的单链表 self.__head = None
if node:
node.next = node # 非空的单链表 node.next = node
def is_empty(self):
"""判断链表是否为空"""
if self.__head == None:
return True
else:
return False
def length(self):
"""返回链表的长度"""
# 空链表
if self.is_empty():
return 0
# cur游标 指向首节点 用来遍历
cur = self.__head # None
count = 1
while 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.arg, end=' ')
cur = cur.next
# 退出循环的时候,cur指向尾结点,但是尾结点并没有打印
print(cur.arg)
def add(self, arg):
"""链表头部添加元素"""
# arg 你要具体插入的数据
node = SingleNode(arg)
# 空链表
if self.is_empty():
self.__head = node
node.next = self.__head
else:
cur = self.__head # None
while cur.next != self.__head:
cur = cur.next
# 添加的节点指向原先的头节点
node.next = self.__head
# __head指向node
self.__head = node
# 尾结点指向新的节点
cur.next = node
def append(self, arg):
"""链表尾部添加元素"""
node = SingleNode(arg)
# 空链表
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, arg):
"""指定位置添加元素"""
# 头部插入
if pos <= 0:
self.add(arg)
# 尾部插入
elif pos > self.length() - 1:
self.append(arg)
else:
# 指定位置插入
node = SingleNode(arg)
cur = self.__head
count = 0
while count < (pos - 1):
count += 1
cur = cur.next
node.next = cur.next
cur.next = node
def search(self, arg):
"""查找节点是否存在"""
if self.is_empty():
return False
cur = self.__head
while cur.next != self.__head:
if cur.arg == arg:
return True
else:
cur = cur.next
# 循环退出 cur指向尾节点
if cur.arg == arg:
return True
return False
def remove(self, arg):
"""删除节点"""
# 空链表
if self.is_empty():
return
cur = self.__head
pre = None
# 头节点的元素就是要删除的元素
if cur.arg == arg:
# 链表中的节点不止一个
if cur.next != self.__head:
while cur.next != self.__head:
cur = cur.next
# 循环结束 cur 指向尾结点
cur.next = self.__head.next
self.__head = cur.next
else:
self.__head = None
# 第一个节点不是要删除的
else:
while cur.next != self.__head:
if cur.arg == arg:
# 删除
pre.next = cur.next
return
else:
# 游标继续往下走
pre = cur
cur = cur.next
if cur.arg == arg:
pre.next = cur.next
sc = SingleCycleList()
sc.add(111)
sc.append(222222)
sc.insert(0, 3333)
print('add->append->Insert: ', end='')
sc.travel()
sc.remove(3333)
print('remove(3333) : ', end='')
sc.travel()
print('search(222222) : ', sc.search(222222))
print('is_empty : ', sc.is_empty())
print('length : ', sc.length())
----------------------结果--------------------------------
add->append->Insert: 3333 111 222222
remove(3333) : 111 222222
search(222222) : True
is_empty : False
length : 2
#!/usr/bin/env python
#coding:utf8
#++++++++++++description++++++++++++#
"""
@author:ying
@contact:1074020480@qq.com
@site:
@software: PyCharm
@file: SingleCycle.py
@time: 2019/11/13 下午1:40
"""
#+++++++++++++++++++++++++++++++++++#
class SingleNode(object):
"""节点"""
def __init__(self, arg):
# arg存放数据元素
self.arg = arg
# next是下一个节点的标识
self.next = None
class SingleCycleList(object):
"""单项循环链表"""
def __init__(self, node=None):
self.__head = None # 空的单链表 self.__head = None
if node:
node.next = node # 非空的单链表 node.next = node
def is_empty(self):
"""判断链表是否为空"""
if self.__head == None:
return True
else:
return False
def length(self):
"""返回链表的长度"""
# 空链表
if self.is_empty():
return 0
# cur游标 指向首节点 用来遍历
cur = self.__head # None
count = 1
while 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.arg, end=' ')
cur = cur.next
# 退出循环的时候,cur指向尾结点,但是尾结点并没有打印
print(cur.arg)
def add(self, arg):
"""链表头部添加元素"""
# arg 你要具体插入的数据
node = SingleNode(arg)
# 空链表
if self.is_empty():
self.__head = node
node.next = self.__head
else:
cur = self.__head # None
while cur.next != self.__head:
cur = cur.next
# 添加的节点指向原先的头节点
node.next = self.__head
# __head指向node
self.__head = node
# 尾结点指向新的节点
cur.next = node
def append(self, arg):
"""链表尾部添加元素"""
node = SingleNode(arg)
# 空链表
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, arg):
"""指定位置添加元素"""
# 头部插入
if pos <= 0:
self.add(arg)
# 尾部插入
elif pos > self.length() - 1:
self.append(arg)
else:
# 指定位置插入
node = SingleNode(arg)
cur = self.__head
count = 0
while count < (pos - 1):
count += 1
cur = cur.next
node.next = cur.next
cur.next = node
def search(self, arg):
"""查找节点是否存在"""
if self.is_empty():
return False
cur = self.__head
while cur.next != self.__head:
if cur.arg == arg:
return True
else:
cur = cur.next
# 循环退出 cur指向尾节点
if cur.arg == arg:
return True
return False
def remove(self, arg):
"""删除节点"""
# 空链表
if self.is_empty():
return
cur = self.__head
pre = None
# 头节点的元素就是要删除的元素
if cur.arg == arg:
# 链表中的节点不止一个
if cur.next != self.__head:
while cur.next != self.__head:
cur = cur.next
# 循环结束 cur 指向尾结点
cur.next = self.__head.next
self.__head = cur.next
else:
self.__head = None
# 第一个节点不是要删除的
else:
while cur.next != self.__head:
if cur.arg == arg:
# 删除
pre.next = cur.next
return
else:
# 游标继续往下走
pre = cur
cur = cur.next
if cur.arg == arg:
pre.next = cur.next
sc = SingleCycleList()
sc.add(111)
sc.append(222222)
sc.insert(0, 3333)
print('add->append->Insert: ', end='')
sc.travel()
sc.remove(3333)
print('remove(3333) : ', end='')
sc.travel()
print('search(222222) : ', sc.search(222222))
print('is_empty : ', sc.is_empty())
print('length : ', sc.length())
----------------------结果--------------------------------
add->append->Insert: 3333 111 222222
remove(3333) : 111 222222
search(222222) : True
is_empty : False
length : 2