Python 是一种面向对象解释型计算机程序设计语言, 由 Guido van Rossum 于 1989 年底发明, 第一个公开发行版发行于 1991 年 Python 语法简洁而清晰, 具有丰富和强大的类库它常被昵称为胶水语言, 它能够把用其他语言制作的各种模块 (尤其是 C/C++) 很轻松地联结在一起
这篇文章主要介绍了 Python 实现的单向循环链表功能, 简单描述了单向循环链表的概念原理并结合实例形式分析了 Python 定义与使用单向循环链表的相关操作技巧, 需要的朋友可以参考下
本文实例讲述了 Python 实现的单向循环链表功能分享给大家供大家参考, 具体如下:
概述:
单向循环链表是指在单链表的基础上, 表的最后一个元素指向链表头结点, 不再是为空
由图可知, 单向循环链表的判断条件不再是表为空了, 而变成了是否到表头
操作
is_empty() 判断链表是否为空
length() 返回链表的长度
travel() 遍历
add(item) 在头部添加一个节点
append(item) 在尾部添加一个节点
insert(pos, item) 在指定位置 pos 添加节点
remove(item) 删除一个节点
search(item) 查找节点是否存在
具体代码:
- class Node(object):
- """节点"""
- def __init__(self, item):
- self.item = item
- self.next = None
- class SinCycLinkedlist(object):
- """单向循环链表"""
- def __init__(self):
- self._head = None
- def is_empty(self):
- """判断链表是否为空"""
- return self._head == None
- def length(self):
- """返回链表的长度"""
- # 如果链表为空, 返回长度 0
- if self.is_empty():
- return 0
- count = 1
- cur = self._head
- while cur.next != self._head:
- count += 1
- cur = cur.next
- return count
- def travel(self):
- """遍历链表"""
- if self.is_empty():
- return
- cur = self._head
- print cur.item,
- while cur.next != self._head:
- cur = cur.next
- print cur.item,
- print ""def add(self, item):""" 头部添加节点 """
- node = Node(item)
- if self.is_empty():
- self._head = node
- node.next = self._head
- else:
- #添加的节点指向_head
- node.next = self._head
- # 移到链表尾部, 将尾部节点的 next 指向 node
- cur = self._head
- while cur.next != self._head:
- cur = cur.next
- cur.next = node
- #_head 指向添加 node 的
- self._head = node
- def append(self, item):
- """尾部添加节点"""
- node = Node(item)
- 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, item):
- """在指定位置添加节点"""
- if pos <= 0:
- self.add(item)
- elif pos > (self.length()-1):
- self.append(item)
- else:
- node = Node(item)
- cur = self._head
- count = 0
- # 移动到指定位置的前一个位置
- while count < (pos-1):
- count += 1
- cur = cur.next
- node.next = cur.next
- cur.next = node
- def remove(self, item):
- """删除一个节点"""
- # 若链表为空, 则直接返回
- if self.is_empty():
- return
- # 将 cur 指向头节点
- cur = self._head
- pre = None
- # 若头节点的元素就是要查找的元素 item
- if cur.item == item:
- # 如果链表不止一个节点
- if cur.next != self._head:
- # 先找到尾节点, 将尾节点的 next 指向第二个节点
- while cur.next != self._head:
- cur = cur.next
- # cur 指向了尾节点
- cur.next = self._head.next
- self._head = self._head.next
- else:
- # 链表只有一个节点
- self._head = None
- else:
- pre = self._head
- # 第一个节点不是要删除的
- while cur.next != self._head:
- # 找到了要删除的元素
- if cur.item == item:
- # 删除
- pre.next = cur.next
- return
- else:
- pre = cur
- cur = cur.next
- # cur 指向尾节点
- if cur.item == item:
- # 尾部删除
- pre.next = cur.next
- def search(self, item):
- """查找节点是否存在"""
- if self.is_empty():
- return False
- cur = self._head
- if cur.item == item:
- return True
- while cur.next != self._head:
- cur = cur.next
- if cur.item == item:
- return True
- return False
- if __name__ == "__main__":
- ll = SinCycLinkedlist()
- ll.add(1)
- ll.add(2)
- ll.append(3)
- ll.insert(2, 4)
- ll.insert(4, 5)
- ll.insert(0, 6)
- print "length:",ll.length()
- ll.travel()
- print ll.search(3)
- print ll.search(7)
- ll.remove(1)
- print "length:",ll.length()
- ll.travel()
运行结果:
来源: http://www.phperz.com/article/18/0216/360907.html