文章目录

1、概念2、操作3、python实现操作

1、概念

单向循环链表是单链表的一个变型，链表最后的一个节点的next域不再为None，而是指向链表的头节点

2、操作

is_empty() 判断链表是否为空length() 返回链表的长度tracel() 遍历add(item) 在头部添加一个节点append(item) 在尾部添加一个节点insert(pos,item) 在指定位置pos添加节点remove(item) 删除一个节点search(item) 查找结点是否存在

3、python实现操作

# 定义节点 class Node(object): def __init__(self,elem): self.elem=elem self.next=None # 定义操作 class SingleCycleLink(object): def __init__(self,node=None): # 如果列表不为空，则节点的next应指向自己 self.__head=node if node: node.next=node def is_empty(self): # 判空 cur=self.__head return self.__head==None def length(self): # 求链表长度 if self.is_empty(): return 0 cur=self.__head # 这里为了计数，且由于停止条件不同，所以count=1 count=1 while cur.next != self.__head: count += 1 cur=cur.next return count def travel(self): # 遍历链表每个元素 if self.is_empty(): return 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(item) if self.is_empty(): self.__head=node node.next=node else: cur=self.__head while cur.next != self.__head: cur=cur.next # 退出循环，cur指向尾节点 # 先指定当前的next,再指定要指向当前节点的 node.next=self.__head self.__head=node cur.next=node # cur.next=self.__head 也可以 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 cur.next=node node.next=self.__head def insert(self,pos,item): # 在指定位置插入元素 node=Node(item) if pos < 0: self.add(item) elif pos > (self.length()-1): self.append(item) else: pre=self.__head count=0 while count < (pos-1): count += 1 pre=pre.next # 退出循环后，先将node的next移动到pre的下一个的位置，然后将pre的next指向node node.next=pre.next pre.next=node def remove(self,item): # 删除节点 if self.is_empty(): return 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 self.__head=cur.next rear.next=self.__head else: # 中间节点 pre.next=cur.next # 不能使用break，因为break表示跳出函数，但是这里函数还在执行 return else: pre=cur cur=cur.next # 退出循环时，cur指向尾节点，再判断一次尾节点 if cur.elem == item: if cur == self.__head: # 如果此时链表只有一个节点,则删除后链表为空 self.__head=None else: pre.next=cur.next def search(self,item): # 查找item是否在链表中 if self.is_empty(): return False cur=self.__head while cur.next != self.__head: if cur.elem == item: return True else: cur=cur.next # 退出循环时，cur指向尾节点，因此如果尾节点就是要找的节点，还需要判断一次 if cur.elem==item: return True return False

测试：

if __name__ == '__main__': sincyclink=SingleCycleLink() print('此时链表是否为空', sincyclink.is_empty()) print('此时链表长度为：', sincyclink.length()) sincyclink.append(1) print('此时链表是否为空', sincyclink.is_empty()) print('此时链表长度为：', sincyclink.length()) sincyclink.append(2) sincyclink.add(8) sincyclink.append(3) sincyclink.append(4) sincyclink.travel() sincyclink.insert(-1,9) sincyclink.travel() sincyclink.insert(-1,100) sincyclink.travel() sincyclink.insert(10,100) sincyclink.travel() sincyclink.remove(100) sincyclink.travel()

结果：

此时链表是否为空 True 此时链表长度为： 0 此时链表是否为空 False 此时链表长度为： 1 8 1 2 3 4 9 8 1 2 3 4 100 9 8 1 2 3 4 100 9 8 1 2 3 4 100 9 8 1 2 3 4 100