网站LOGO
公爵书房 | 技术分享
页面加载中
2月24日
网站LOGO 公爵书房 | 技术分享
以指键之轻,承载知识之重
菜单
  • 公爵书房 | 技术分享
    以指键之轻,承载知识之重
    用户的头像
    首次访问
    上次留言
    累计留言
    我的等级
    我的角色
    打赏二维码
    打赏博主
    Python数据结构(二)·单链表
    点击复制本页信息
    微信扫一扫
    文章二维码
    文章图片 文章标题
    创建时间
  • 一 言
    确认删除此评论么? 确认
  • 本弹窗介绍内容来自,本网站不对其中内容负责。

    Python数据结构(二)·单链表

    公爵 · 原创 ·
    笔记 · python单链表
    共 6320 字 · 约 2 分钟 · 98
    本文最后更新于2023年09月02日,已经过了175天没有更新,若内容或图片失效,请留言反馈
    单链表是一种链式的数据结构,链表中的数据用结点表示,保持了数据之间的逻辑关系,但存储空间不一定是按照顺序存储。

    链表的基本元素有:

    • 节点:包括数据域和指针域,数据域存放数据,指针域存放指向下一个元素的指针
    • head:头结点
    • tail:尾结点
    • None:链表最后一个结点的指针域为None

    Python中没有显式的指针,但是有引用啊,所以我们可以通过定义节点类和引用来实现链表!

    链表分为单链表和单循环链表,双向链表和双向循环链表,本篇先讲一下单链表:

    2.1 定义节点类

    节点类中包括节点数据和下一个节点地址,即引用

    python 代码:
    # 节点类
    class Node(object):
    
        # 单个节点 初始化 输入一个值data,将值变为一个节点
        def __init__(self, data):
            self.data = data
            self.next = None
    
        # 打印对象中具体的属性值
        def __str__(self):
            # 测试基本功能,输出data
            return self.data
    # 输出data
    print(Node('data'))

    这里的__str__可以不用写,这里是在进行测试,在后面的具体实现部分可以不用这个,str函数可以方便我们打印对象中具体的属性值,也是很nice了!具体使用如上

    2.2 获取链表的长度

    python 代码:
    # 获取链表的长度
    def length(self):
        cur = self.head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    2.3 头插元素

    python 代码:
    # 头部添加元素
    def add_fist(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node

    2.4 尾插元素

    python 代码:
    # 尾部添加元素
    def add_last(self, data):
        node = Node(data)
        # 如果链表为空,需要特殊处理
        if self.is_empty():
            self.head = node
        else:
            cur = self.head
            while cur.next is not None:
                cur = cur.next
            # 退出循环的时候,curl指向尾结点
            cur.next = node

    2.5 指定位置插元素

    python 代码:
    # 在指定位置添加元素
    def insert_node(self, index, data):
        node = Node(data)
        if index < 0 or index > self.length():
            return False
        elif index == 0:
            self.add_fist()
        elif index == self.length():
            self.add_last()
        else:
            cur = self.head
            count = 0
            while count < (index - 1):
                count += 1
                cur = cur.next
            # 退出循环的时候,cur指向index的前一个位置
            node.next = cur.next
            cur.next = node

    2.6 删除节点

    python 代码:
    # 删除指定节点
    def remove_node(self, data):
        cur = self.head  # 指针指向的结点
        pre = None  # 指针指向结点的前一个
        if self.head == data:
            self.head.next = self.head
        else:
            while cur.data is not data:
                # 不是要找的元素,移动游标
                pre = cur
                cur = cur.next
            pre.next = cur.next

    2.7 查找节点

    python 代码:
    # 查找节点
    def search_node(self, data):
        cur = self.head
        while cur is not None:
            if cur.data == data:
                return True
            else:
                cur = cur.next
        return False

    2.8 打印链表

    python 代码:
    # 遍历 打印链表
    def traverse_to_print_node(self):
        # cur = self.head
        # while cur is not None:
        #     print(cur.data, end = " ")
        #     cur = cur.next
        print_list = []
        cur = self.head
        while cur is not None:
            print_list.append(str(cur.data))
            cur = cur.next
        print('->'.join(print_list))

    2.9 测试代码

    python 代码:
    # 测试
    if __name__ == '__main__':
        list = SingleLinkedList()
        list.add_fist(2)
        list.add_fist(1)
        list.add_last(4)
        list.insert_node(2, 3)
        list.traverse_to_print_node()
        print(list.is_empty())
        print(list.length())
        list.remove_node(4)
        print(list.search_node(3))
        list.traverse_to_print_node()

    结果图:

    结果图结果图

    2.10 完整代码

    python 代码:
    #!usr/bin/env python
    # encoding:utf-8
    
    # 节点类
    class Node(object):
    
        # 单个节点 初始化 输入一个值data,将值变为一个节点
        def __init__(self, data):
            self.data = data
            self.next = None
    
        # 打印对象中具体的属性值
        def __str__(self):
            # 测试基本功能,输出data
            return self.data
    
    
    class SingleLinkedList(object):
    
        # 创建一个单链表
        def __init__(self):
            self.head = None
    
        # 判断链表是否为空
        def is_empty(self):
            return self.head is None
    
        # 获取链表的长度
        def length(self):
            cur = self.head
            count = 0
            while cur is not None:
                count += 1
                cur = cur.next
            return count
    
        # 头部添加元素
        def add_fist(self, data):
            node = Node(data)
            node.next = self.head
            self.head = node
    
        # 尾部添加元素
        def add_last(self, data):
            node = Node(data)
            # 如果链表为空,需要特殊处理
            if self.is_empty():
                self.head = node
            else:
                cur = self.head
                while cur.next is not None:
                    cur = cur.next
                # 退出循环的时候,curl指向尾结点
                cur.next = node
    
        # 在指定位置添加元素
        def insert_node(self, index, data):
            node = Node(data)
            if index < 0 or index > self.length():
                return False
            elif index == 0:
                self.add_fist()
            elif index == self.length():
                self.add_last()
            else:
                cur = self.head
                count = 0
                while count < (index - 1):
                    count += 1
                    cur = cur.next
                # 退出循环的时候,cur指向index的前一个位置
                node.next = cur.next
                cur.next = node
    
        # 删除指定节点
        def remove_node(self, data):
            cur = self.head  # 指针指向的结点
            pre = None  # 指针指向结点的前一个
            if self.head == data:
                self.head.next = self.head
            else:
                while cur.data is not data:
                    # 不是要找的元素,移动游标
                    pre = cur
                    cur = cur.next
                pre.next = cur.next
    
        # 查找节点
        def search_node(self, data):
            cur = self.head
            while cur is not None:
                if cur.data == data:
                    return True
                else:
                    cur = cur.next
            return False
    
        # 遍历 打印链表
        def traverse_to_print_node(self):
            # cur = self.head
            # while cur is not None:
            #     print(cur.data, end = " ")
            #     cur = cur.next
            print_list = []
            cur = self.head
            while cur is not None:
                print_list.append(str(cur.data))
                cur = cur.next
            print('->'.join(print_list))
    
    # 测试
    if __name__ == '__main__':
        list = SingleLinkedList()
        list.add_fist(2)
        list.add_fist(1)
        list.add_last(4)
        list.insert_node(2, 3)
        list.traverse_to_print_node()
        print(list.is_empty())
        print(list.length())
        list.remove_node(4)
        print(list.search_node(3))
        list.traverse_to_print_node()
    声明:本文由 公爵(博主)原创,依据 CC-BY-NC-SA 4.0 许可协议 授权,转载请注明出处。

    还没有人喜爱这篇文章呢

    发一条! 发一条!
    博客logo 公爵书房 | 技术分享 以指键之轻,承载知识之重 51统计 百度统计
    MOEICP 萌ICP备20226257号 ICP 赣ICP备2022001242号-1 ICP 闽公网安备35020502000606号 又拍云 本站由又拍云提供CDN加速/云存储服务

    🕛

    本站已运行 2 年 35 天 19 小时 20 分

    🌳

    自豪地使用 Typecho 建站,并搭配 MyLife 主题
    公爵书房 | 技术分享. © 2022 ~ 2024.
    网站logo

    公爵书房 | 技术分享 以指键之轻,承载知识之重
     
     
     
     
    壁纸