数据结构与算法Day3链表(3)

1187-吴同学

发表文章数:41

首页 » 数据结构 » 正文

链表

单向循环链表

单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点
数据结构与算法Day3链表(3)

节点实现

比单向列表多一个self.pre的链接

class Node():
    def __init__(self,item):
        self.elem=item
        self.next=None

单向循环链表的操作

操作 表示
is_empty() 链表是否为空
length() 链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos, item) 指定位置添加元素
remove(item) 删除节点
search(item) 查找节点是否存在

代码示例:

note:

/quad

单向链表 单向循环链表
头节点 指向下一个 头节点为唯一节点时指向自身
尾结点 指向None 指向头节点
遍历循环判断 cur!=None
cur.next!=None
cur.next!=self.__head(尾结点不指向None,退出循环时指向尾结点)
(PS:不能用cur==self.head,因为第一次指向头节点的时候就满足这种情况)
判断为否的情况 当前节点为None
下一节点为空
1. 头节点为唯一节点
2. 空链表报错
3.尾结点

调用内部方法是self.方法名(),括号不要漏,如self.is_empty()

链表是否为空和指定位置添加元素
都不涉及单向循环列表的特殊节点的变动——头节点和尾结点。

class SinCycLinkedlist():
    def __init__(self,node=None):
        self.__head=node
        if node:
            node.next=node  #循环需要指向自己
      
    def is_empty(self):
        """判断链表是否为空"""
        return self._head is None  #None一般用is来判断
      
    def insert(self,pos, item):
        """指定位置添加元素
        :params 从0开始
        """
        if pos<=0:
            self.add(item)  #self不要落
        elif pos>(self.length()-1): #注意这里不包含等号
            self.append(item)
        else:
            node=Node(item)
            pre=self.__head  #pre相当于上述的cur,作为指针
            count=0
            while count<pos-1:
                pre=pre.next
                count+=1
            node.next=pre.next
            pre.next=node

链表长度、遍历整个链表和尾部添加元素

    def length(self):
        """链表长度"""
        if self.is_empty:
            return 0
        else:
            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 None
        cur=self.__head
        while cur.next!=self.__head: 
            print(cur.elem,'/t')
            cur=cur.next
        #退出时指向cur指向尾结点,但未打印
        print(cur.elem)  

    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  #self.__head也可用cur.next代替
            cur.next=node      

链表头部添加元素和删除节点**
循环链表涉及尾部和头部之间操作时,需要循环获取尾结点。

    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指向尾结点
            node.next=self.__head
            cur.next=node
            self.__head=node
      
    def remove(self,item) :
        """删除节点"""
        if self.is_empty:
            return
        pre=None
        cur=self.__head
        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   #rear.next=cur.next
                else:
                    pre.next=cur.next
                return  ##不能用break,因为跳出while,会进入后面的if
            pre=cur
            cur=cur.next
        if cur.elem==tiem:
            if cur==self.__head:#链表只有一个节点且为要删除的对象
                self.__head=None
            else:
                pre.next=cur.next  

查找节点是否存在

    def search(self,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
        if cur.elem==item:
            return True
                
        return False   

双向循环链表

后续再补充

未经允许不得转载:作者:1187-吴同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《数据结构与算法Day3链表(3)》 发布于2020-11-28

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录