数据结构——单向循环链表

单向循环链表的结构

• 表元素域val用来存放具体的数据。
• 链接域next用来存放下一个节点的位置
• 变量head指向链表的头节点（首节点）的位置，从head出发能找到表中的任意节点。
• 链表尾节点next指向头结点, 形成循环

单向循环链表节点实现

class Node(object):"""单向循环链表节点类"""def __init__(self, val=None, next=None):self.val = valself.next = next

单向循环链表的实现

class SingleCycleLinklist(object):"""单向循环链表实现类"""def __init__(self, head=None, length=0):self.head = headself.length = length

图解说明

单向循环链表-链表是否为空（is_empty）

def is_empty(self):return self.length == 0

图解说明

单向循环链表-链表头部添加元素（add）

def add(self, value):"""头插入元素:param value::return:"""node = Node(value)if self.is_empty():self.head = nodenode.next = self.headelse:node.next = self.headcur = self.headwhile cur.next != self.head:cur = cur.nextcur.next = nodeself.head = nodeself.length += 1

图解说明

单向循环链表-链表尾部添加元素（append）

def append(self, value):"""尾部添加元素:return:"""node = Node(value)if self.is_empty():self.head = nodenode.next = self.headelse:cur = self.headwhile cur.next != self.head:cur = cur.nextcur.next = nodenode.next = self.headself.length += 1

图解说明

单向循环链表-链表查询指定元素（search）

def search(self, value):"""查询指定元素:param value::return:"""flag = Falsecur = self.headlens = self._length()indexs = 0while lens:if cur.val == value:flag = Truebreakcur = cur.nextlens -= 1indexs += 1indexs = indexs if flag else 0print(flag, indexs)return flag, indexs

图解说明

单向循环链表-链表指定位置插入元素（insert）

def insert(self, pos, value):"""指定位置插入元素:param pos::param value::return:"""cur = self.headif pos <= 0:self.add(value)elif pos > self.length:self.append(value)else:node = Node(value)count = pos - 1while count:cur = cur.nextcount -= 1node.next = cur.nextcur.next = nodeself.length += 1

图解说明

单向循环链表-链表删除指定元素（remove）

def remove(self, value):"""删除指定元素:param value::return:"""cur = self.headpre = Nonecounts = self.lengthwhile counts:if cur.val == value:if not pre:last_node = self.headwhile last_node.next != self.head:last_node = last_node.nextself.head = self.head.next  # 适配第一个元素为删除的元素, 将头结点指向原头节点的next, 建立新头节点last_node.next = self.head  # 指向头指针形成循环else:pre.next = cur.nextself.length -= 1return 0pre = curcur = cur.nextcounts -= 1return -1

图解说明

单向循环链表-链表遍历（traversal）

def traversal(self):"""遍历链表:return:"""cur_node = self.headif self.is_empty():returnelse:while cur_node.next != self.head:print(cur_node.val, end=" ")cur_node = cur_node.next# 最后一个元素print(cur_node.val)

图解说明

单向循环链表-完整代码及测试

# -*- coding:utf-8 -*-class Node(object):"""单向循环链表节点类"""def __init__(self, val=None, next=None):self.val = valself.next = nextclass SingleCycleLinklist(object):"""单向循环链表实现类"""def __init__(self, head=None, length=0):self.head = headself.length = lengthdef _length(self):return self.lengthdef is_empty(self):return self.length == 0def add(self, value):"""头插入元素:param value::return:"""node = Node(value)if self.is_empty():self.head = nodenode.next = self.headelse:node.next = self.headcur = self.headwhile cur.next != self.head:cur = cur.nextcur.next = nodeself.head = nodeself.length += 1def append(self, value):"""尾部添加元素:return:"""node = Node(value)if self.is_empty():self.head = nodenode.next = self.headelse:cur = self.headwhile cur.next != self.head:cur = cur.nextcur.next = nodenode.next = self.headself.length += 1def search(self, value):"""查询指定元素:param value::return:"""flag = Falsecur = self.headlens = self._length()indexs = 0while lens:if cur.val == value:flag = Truebreakcur = cur.nextlens -= 1indexs += 1indexs = indexs if flag else 0print(flag, indexs)return flag, indexsdef remove(self, value):"""删除指定元素:param value::return:"""cur = self.headpre = Nonecounts = self.lengthwhile counts:if cur.val == value:if not pre:last_node = self.headwhile last_node.next != self.head:last_node = last_node.nextself.head = self.head.next  # 适配第一个元素为删除的元素, 将头结点指向原头节点的next, 建立新头节点last_node.next = self.head  # 指向头指针形成循环else:pre.next = cur.nextself.length -= 1return 0pre = curcur = cur.nextcounts -= 1return -1def insert(self, pos, value):"""指定位置插入元素:param pos::param value::return:"""cur = self.headif pos <= 0:self.add(value)elif pos > self.length:self.append(value)else:node = Node(value)count = pos - 1while count:cur = cur.nextcount -= 1node.next = cur.nextcur.next = nodeself.length += 1def traversal(self):"""遍历链表:return:"""cur_node = self.headif self.is_empty():returnelse:while cur_node.next != self.head:print(cur_node.val, end=" ")cur_node = cur_node.next# 最后一个元素print(cur_node.val)def main():node = SingleCycleLinklist()node.add(1)node.add(2)node.append(3)node.insert(2, 666)node.insert(3, 888)node.traversal()print("cycle link list len: ", node._length())node.search(5)print('===================')res = node.remove(1)node.traversal()print("cycle link list len: ", node._length())print(res)if __name__ == '__main__':main()