数据结构编程实践20讲(Python版)—02链表

本文目录

    • 02 链表 linked-list
      • S1 说明
      • S2 示例
        • 单向链表
        • 双向链表
        • 循环链表
      • S3 问题:反转单向链表
        • 求解思路
        • Python3程序
      • S4 问题: 双向链表实现历史浏览网页
        • 求解思路
        • Python3程序
      • S5 问题: 基于循环链表的玩家出牌顺序
        • 求解思路
        • Python3程序

往期链接

01数组

02 链表 linked-list

S1 说明

链表是一种常见的数据结构,用于存储一系列元素。与数组不同,链表的元素(称为节点)在内存中不必是连续存储的。

基本特征

  • 动态大小:链表的大小可以动态变化,不需要事先定义大小。
  • 插入和删除效率:在链表中插入和删除节点的时间复杂度为 O(1),这比数组更- 高效(数组在中间插入或删除元素时需要移动大量元素)。
  • 顺序存储:元素通过指针相互连接,而不是通过索引。

节点:链表的基本单元

通常包含两个部分:

  • 数据部分:存储实际的数据。
  • 指针部分:指向下一个节点(在单向链表中)或前一个节点(在双向链表中)。

链表的分类

  • 单向链表:每个节点只能指向下一个节点。
  • 双向链表:每个节点既可以指向下一个节点,也可以指向前一个节点。
  • 循环链表:最后一个节点指向第一个节点,形成一个环。

S2 示例

python中没有链表的数据结构,需要自己写函数定义。

单向链表
class Node:
    """链表节点类"""

    def __init__(self, data):
        self.data = data  # 节点存储的数据
        self.next = None  # 指向下一个节点的指针


class LinkedList:
    """单向链表类"""

    def __init__(self):
        self.head = None  # 链表头节点

    def append(self, data):
        """在链表末尾添加新节点"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def insert_at_position(self, data, position):
        """在指定位置插入新节点"""
        new_node = Node(data)
        if position == 0:
            new_node.next = self.head
            self.head = new_node
            return

        current = self.head
        for _ in range(position - 1):
            if current is None:
                raise IndexError("Position out of bounds")
            current = current.next

        new_node.next = current.next
        current.next = new_node

    def delete(self, key):
        """删除链表中指定值的节点"""
        current = self.head
        if current and current.data == key:
            self.head = current.next
            return

        prev = None
        while current and current.data != key:
            prev = current
            current = current.next

        if current is None:
            return  # 未找到要删除的节点

        prev.next = current.next

    def find(self, key):
        """查找链表中是否存在指定值"""
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

    def display(self):
        """遍历并打印链表中的所有节点"""
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")


# 使用示例
if __name__ == "__main__":
    ll = LinkedList()
    ll.append(1)
    ll.append(2)
    ll.append(3)

    print("链表内容:")
    ll.display()

    ll.insert_at_position(4, 1)  # 在位置 1 插入 4
    print("插入 4 后的链表内容:")
    ll.display()

    ll.delete(2)  # 删除值为 2 的节点
    print("删除节点 2 后的链表内容:")
    ll.display()

    exists = ll.find(3)  # 查找值为 3 的节点
    print("查找值 3 存在:", exists)

输出

链表内容:
1 -> 2 -> 3 -> None
插入 4 后的链表内容:
1 -> 4 -> 2 -> 3 -> None
删除节点 2 后的链表内容:
1 -> 4 -> 3 -> None
查找值 3 存在: True
双向链表
class Node:
    """双向链表节点类"""

    def __init__(self, data):
        self.data = data  # 节点存储的数据
        self.prev = None  # 指向前一个节点的指针
        self.next = None  # 指向下一个节点的指针


class DoublyLinkedList:
    """双向链表类"""

    def __init__(self):
        self.head = None  # 链表头节点

    def append(self, data):
        """在链表末尾添加新节点"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
        new_node.prev = current

    def insert_at_position(self, data, position):
        """在指定位置插入新节点"""
        new_node = Node(data)
        if position == 0:
            new_node.next = self.head
            if self.head:
                self.head.prev = new_node
            self.head = new_node
            return

        current = self.head
        for _ in range(position - 1):
            if current is None:
                raise IndexError("Position out of bounds")
            current = current.next

        new_node.next = current.next
        new_node.prev = current
        if current.next:
            current.next.prev = new_node
        current.next = new_node

    def delete(self, key):
        """删除链表中指定值的节点"""
        current = self.head
        if current and current.data == key:
            self.head = current.next
            if self.head:
                self.head.prev = None
            return

        while current and current.data != key:
            current = current.next

        if current is None:
            return  # 未找到要删除的节点

        if current.next:
            current.next.prev = current.prev
        if current.prev:
            current.prev.next = current.next

    def find(self, key):
        """查找链表中是否存在指定值"""
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

    def display(self):
        """遍历并打印链表中的所有节点"""
        current = self.head
        while current:
            print(current.data, end=" <=> ")
            current = current.next
        print("None")

    def reverse_display(self):
        """反向遍历并打印链表中的所有节点"""
        current = self.head
        while current and current.next:
            current = current.next
        while current:
            print(current.data, end=" <=> ")
            current = current.prev
        print("None")


# 使用示例
if __name__ == "__main__":
    dll = DoublyLinkedList()
    dll.append(1)
    dll.append(2)
    dll.append(3)

    print("链表内容:")
    dll.display()

    dll.insert_at_position(4, 1)  # 在位置 1 插入 4
    print("插入 4 后的链表内容:")
    dll.display()

    dll.delete(2)  # 删除值为 2 的节点
    print("删除节点 2 后的链表内容:")
    dll.display()

    exists = dll.find(3)  # 查找值为 3 的节点
    print("查找值 3 存在:", exists)

    print("反向显示链表内容:")
    dll.reverse_display()

输出

链表内容:
1 <=> 2 <=> 3 <=> None
插入 4 后的链表内容:
1 <=> 4 <=> 2 <=> 3 <=> None
删除节点 2 后的链表内容:
1 <=> 4 <=> 3 <=> None
查找值 3 存在: True
反向显示链表内容:
3 <=> 4 <=> 1 <=> None
循环链表
class Node:
    """循环链表节点类"""
    def __init__(self, data):
        self.data = data  # 节点存储的数据
        self.next = None  # 指向下一个节点的指针


class CircularLinkedList:
    """循环链表类"""
    def __init__(self):
        self.head = None  # 链表头节点

    def append(self, data):
        """在链表末尾添加新节点"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head  # 指向自己形成循环
            return
        current = self.head
        while current.next != self.head:
            current = current.next
        current.next = new_node
        new_node.next = self.head  # 新节点指向头节点

    def insert_at_position(self, data, position):
        """在指定位置插入新节点"""
        new_node = Node(data)
        if position == 0:  # 插入到头部
            if not self.head:
                self.head = new_node
                new_node.next = self.head
            else:
                current = self.head
                while current.next != self.head:
                    current = current.next
                current.next = new_node
                new_node.next = self.head
                self.head = new_node
            return

        current = self.head
        for _ in range(position - 1):
            current = current.next
            if current == self.head:
                raise IndexError("Position out of bounds")

        new_node.next = current.next
        current.next = new_node

    def delete(self, key):
        """删除链表中指定值的节点"""
        if not self.head:
            return  # 链表为空

        current = self.head
        if current.data == key:  # 删除头节点
            if current.next == self.head:  # 只有一个节点的情况
                self.head = None
                return
            else:
                while current.next != self.head:
                    current = current.next
                current.next = self.head.next
                self.head = self.head.next
                return

        while current.next != self.head and current.next.data != key:
            current = current.next

        if current.next == self.head:
            return  # 未找到要删除的节点

        current.next = current.next.next

    def find(self, key):
        """查找链表中是否存在指定值"""
        if not self.head:
            return False

        current = self.head
        while True:
            if current.data == key:
                return True
            current = current.next
            if current == self.head:
                break
        return False

    def display(self):
        """遍历并打印链表中的所有节点"""
        if not self.head:
            print("链表为空")
            return

        current = self.head
        print("链表内容:")
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print("头节点:", self.head.data)  # 显示头节点的值

# 使用示例
if __name__ == "__main__":
    cll = CircularLinkedList()
    cll.append(1)
    cll.append(2)
    cll.append(3)

    cll.display()

    cll.insert_at_position(4, 1)  # 在位置 1 插入 4
    print("插入 4 后的链表内容:")
    cll.display()

    cll.delete(2)  # 删除值为 2 的节点
    print("删除节点 2 后的链表内容:")
    cll.display()

    exists = cll.find(3)  # 查找值为 3 的节点
    print("查找值 3 存在:", exists)

输出

链表内容:
1 -> 2 -> 3 -> 头节点: 1
插入 4 后的链表内容:
链表内容:
1 -> 4 -> 2 -> 3 -> 头节点: 1
删除节点 2 后的链表内容:
链表内容:
1 -> 4 -> 3 -> 头节点: 1
查找值 3 存在: True

S3 问题:反转单向链表

求解思路
  • 初始化指针:使用三个指针:prev(前一个节点)、current(当前节点)、next_node(下一个节点)。
  • 遍历链表:在遍历的过程中,逐步改变当前节点的next指针,使其指向前一个节点。
  • 更新头节点:当遍历完成后,prev指针将指向新的头节点。
Python3程序
class Node:
    """链表节点类"""
    def __init__(self, data):
        self.data = data  # 节点存储的数据
        self.next = None  # 指向下一个节点的指针


class LinkedList:
    """单向链表类"""
    def __init__(self):
        self.head = None  # 链表头节点

    def append(self, data):
        """在链表末尾添加新节点"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def reverse(self):
        """反转链表"""
        prev = None
        current = self.head
        while current:
            next_node = current.next  # 保存下一个节点
            current.next = prev       # 反转指针
            prev = current            # 移动 prev 和 current 向前
            current = next_node
        self.head = prev  # 更新头节点

    def display(self):
        """遍历并打印链表中的所有节点"""
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")


# 使用示例
if __name__ == "__main__":
    ll = LinkedList()
    ll.append(1)
    ll.append(2)
    ll.append(3)
    ll.append(4)

    print("原链表内容:")
    ll.display()

    ll.reverse()

    print("反转后的链表内容:")
    ll.display()

输出

原链表内容:
1 -> 2 -> 3 -> 4 -> None
反转后的链表内容:
4 -> 3 -> 2 -> 1 -> None

S4 问题: 双向链表实现历史浏览网页

求解思路

定义管理浏览历史的类,包含头节点(打开的第一个网页)、尾节点(None)和当前节点(当前网页)。

  • visit(url):访问新网页,添加到链表中。
  • back():返回到上一个网页,更新当前节点。
  • forward():前进到下一个网页,更新当前节点。
Python3程序
class Node:
    """双向链表节点类"""
    def __init__(self, url):
        self.url = url  # 存储浏览的 URL
        self.prev = None  # 指向前一个节点的指针
        self.next = None  # 指向下一个节点的指针


class BrowsingHistory:
    """浏览历史管理类"""
    def __init__(self):
        self.head = None  # 链表头节点
        self.tail = None  # 链表尾节点
        self.current = None  # 当前浏览的节点

    def visit(self, url):
        """访问新网页"""
        new_node = Node(url)
        if not self.head:  # 如果链表为空
            self.head = new_node
            self.tail = new_node
            self.current = new_node
        else:
            # 将当前节点的下一个节点指向新节点
            self.current.next = new_node
            new_node.prev = self.current
            self.current = new_node  # 更新当前节点为新节点
            self.tail = new_node  # 更新尾节点

    def back(self):
        """后退到上一个网页"""
        if self.current and self.current.prev:
            self.current = self.current.prev
            return self.current.url
        return None  # 无法后退

    def forward(self):
        """前进到下一个网页"""
        if self.current and self.current.next:
            self.current = self.current.next
            return self.current.url
        return None  # 无法前进

    def display_history(self):
        """显示浏览历史"""
        current = self.head
        while current:
            print(current.url, end=" <-> ")
            current = current.next
        print("None")


# 使用示例
if __name__ == "__main__":
    history = BrowsingHistory()
    history.visit("https://www.baidu.com")
    history.visit("https://www.huawei.com")
    history.visit("https://www.apple.com")

    print("浏览历史:")
    history.display_history()

    print("后退到:", history.back())  # 返回到上一个网页
    print("后退到:", history.back())  # 再返回到上一个网页
    print("前进到:", history.forward())  # 前进到下一个网页
    print("当前网页:", history.current.url)  # 当前网页

输出

浏览历史:
https://www.baidu.com <-> https://www.huawei.com <-> https://www.apple.com <-> None
后退到: https://www.huawei.com
后退到: https://www.baidu.com
前进到: https://www.huawei.com
当前网页: https://www.huawei.com

S5 问题: 基于循环链表的玩家出牌顺序

求解思路
  • Node 类:表示循环链表中的每个节点,包含玩家名字和指向下一个节点的指针。
  • CircularLinkedList 类:管理循环链表的玩家顺序。
    • add_player(player_name):添加新玩家到循环链表。
    • display_players():遍历并打印当前所有玩家的名字,并标记头节点。
Python3程序
class Node:
    """循环链表节点类"""
    def __init__(self, player_name):
        self.player_name = player_name  # 存储玩家名字
        self.next = None  # 指向下一个节点的指针


class CircularLinkedList:
    """循环链表类"""
    def __init__(self):
        self.head = None  # 链表头节点

    def add_player(self, player_name):
        """添加新玩家到循环链表"""
        new_node = Node(player_name)
        if not self.head:  # 如果链表为空
            self.head = new_node
            new_node.next = self.head  # 指向自己形成循环
        else:
            current = self.head
            while current.next != self.head:  # 找到最后一个节点
                current = current.next
            current.next = new_node  # 将最后一个节点指向新节点
            new_node.next = self.head  # 新节点指向头节点

    def display_players(self):
        """显示当前所有玩家,包括头节点"""
        if not self.head:
            print("没有玩家在游戏中")
            return

        current = self.head
        players = []
        while True:
            if current == self.head:
                players.append(f"{current.player_name} (头节点)")  # 标记头节点
            else:
                players.append(current.player_name)
            current = current.next
            if current == self.head:  # 如果回到头节点
                break
        print("当前玩家:", " -> ".join(players) + " -> (回到头节点)")


# 使用示例
if __name__ == "__main__":
    game = CircularLinkedList()
    game.add_player("Alice")
    game.add_player("Bob")
    game.add_player("Charlie")

    print("当前玩家顺序:")
    game.display_players()

    # 添加更多玩家
    game.add_player("David")
    print("添加 David 后的玩家顺序:")
    game.display_players()

输出

当前玩家顺序:
当前玩家: Alice (头节点) -> Bob -> Charlie -> (回到头节点)
添加 David 后的玩家顺序:
当前玩家: Alice (头节点) -> Bob -> Charlie -> David -> (回到头节点)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/883702.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

华为GaussDB数据库(单机版)在ARM环境下的安装指南

一、软件版本 机器配置&#xff1a;8核16G&#xff0c;CPU: Huawei Kunpeng 920 2.9GHz操作系统&#xff1a;EulerOS 2.8 64bit with ARM数据库版本&#xff1a;GaussDB Kernel 505.1.0 build 44f4fa53 二、部署流程 2.1 新建用户 ① 以omm用户为例&#xff0c;添加一个omm用…

11. Map和Set

一、二叉搜索树 1. 概念 二叉搜索树又称二叉排序树&#xff0c;它或者是一棵空树&#xff0c;或者是具有以下性质的二叉树&#xff1a; 若它的左子树不为空&#xff0c;则左子树上所有节点的值都小于根节点的值若它的右子树不为空&#xff0c;则右子树上所有节点的值都大于根…

IvorySQL 3.4 来了

9 月 26 日&#xff0c;IvorySQL 3.4 发版。本文将带大家快速了解新版本特性。 IvorySQL 3.4 发版说明 IvorySQL 3.4 基于 PostgreSQL 16.4&#xff0c;修复了多个问题&#xff0c;并增强多项功能。 PostgreSQL 16.4 的变更 在未经授权时防止 pg_dump 执行&#xff0c;并引入一…

Qt-QTableWidget多元素控件(37)

目录 描述 QTableWidget 方法 QTableWidgetItem 信号 QTableWidgetItem 方法 使用 图形化界面操作 代码操作 描述 这是一个表格控件&#xff0c;表格中的每一个单元格&#xff0c;都是一个 QTableWidgetItem 对象 QTableWidget 方法 item(int row,int column)根据⾏数…

Snap AR眼镜Spectacles的技术揭秘:通往真正AR体验的道路

Snap公司自2010年成立以来&#xff0c;一直致力于探索增强现实&#xff08;AR&#xff09;技术的边界。经过多年的研发与迭代&#xff0c;Snap终于在最新一代Spectacles中实现了重大突破&#xff0c;为用户带来了前所未有的沉浸式AR体验。本文将深入探讨Spectacles的发展历程、…

【docker】debian中配置docker(2024年9月)

首先Follow了一下菜鸟教程&#xff0c;然后遇到了curl的问题。 curl存在的问题 参见这篇文章。其中用到了vim进行编辑&#xff0c;笔者的环境是windows10putty&#xff0c;vim的粘贴操作参考这篇文章。 修改之后的curl没有问题了&#xff0c;成功把脚本下载下来了。 但是在…

即插即用篇 | DenseNet卷土重来! YOLOv8 引入全新密集连接卷积网络 | ECCV 2024

本改进已同步到YOLO-Magic框架! 本文重新审视了密集连接卷积网络(DenseNets),并揭示了其在主流的ResNet风格架构中被低估的有效性。我们认为,由于未触及的训练方法和传统设计元素没有完全展现其能力,DenseNets的潜力被忽视了。我们的初步研究表明,通过连接实现的密集连接…

工作安排 - 华为OD统一考试(E卷)

2024华为OD机试(C卷+D卷)最新题库【超值优惠】Java/Python/C++合集 题目描述 小明每周上班都会拿到自己的工作清单,工作清单内包含n项工作,每项工作都有对应的耗时时长(单位h)和报酬,工作的总报酬为所有已完成工作的报酬之和。那么请你帮小明安排一下工作,保证小明在指定…

基于微信小程序的智能汽车充电站系设计与实现(源码+定制+文档)

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

Java线程池和原子性

文章目录 前言1 线程池1.1 线程池概述1.1.1 线程池存在的意义1.1.2 Executors默认线程池 1.2 线程状态介绍1.2.1 线程状态源码1.2.2 线程状态含义1.2.3 线程状态转换图 2 原子性2.1 volatile关键字2.2 synchronized解决2.3 原子性2.4 AtomicInteger类2.5 悲观锁和乐观锁 前言 …

代码随想录算法训练营第56天 | 1、冗余连接,2、冗余连接II

目录 1、冗余连接 2、冗余连接II 1、冗余连接 题目描述 有一个图&#xff0c;它是一棵树&#xff0c;他是拥有 n 个节点&#xff08;节点编号1到n&#xff09;和 n - 1 条边的连通无环无向图&#xff08;其实就是一个线形图&#xff09;&#xff0c;如图&#xff1a; 现在在…

JavaScript 学习

一、输出 为方便调试可以输出内容&#xff0c;但是用户是看不到的。要在开发者模式中看。 console . log ( "Hello" )&#xff1b; 二、外部文件引用 可以直接在html中写JS <head> <meta charset"utf-8"> <script> console.log("he…

RFID手持机——物联网时代的核心工具

一、行业背景 在当今物联网技术高速发展的时代&#xff0c;RFID技术作为核心的数据采集与识别手段&#xff0c;在物流、仓储、资产管理等众多领域发挥着至关重要的作用。以物流行业为例&#xff0c;利用RFID技术能够对货物进行全程精准跟踪&#xff0c;从入库、存储、搬运到出…

每日OJ题_牛客_NC40链表相加(二)_链表+高精度加法_C++_Java

目录 牛客_NC40链表相加&#xff08;二&#xff09;_链表高精度加法 题目解析 C代码 Java代码 牛客_NC40链表相加&#xff08;二&#xff09;_链表高精度加法 链表相加(二)_牛客题霸_牛客网 题目解析 模拟⾼精度加法的过程&#xff0c;只不过是在链表中模拟。 C代码 /*…

buuctf [ACTF2020 新生赛]Include

学习笔记。 开启靶机。 进入靶场&#xff1a; 我们跟进 tips瞅瞅&#xff1a; 额&#xff0c;纯小白&#xff0c;能想到的就是先F12看看&#xff0c;在CTRLu、以及抓包。 得&#xff0c;不会了&#xff0c;看wp呗&#xff0c;不会死磕没脑子0,0&#xff1f; 参考&#xff1a;…

JPA + Thymeleaf 增删改查

一、 什么是 Thymeleaf JPA&#xff08;Java Persistence API&#xff09;&#xff1a;是一种用于对象关系映射&#xff08;ORM&#xff09;的 Java 规范&#xff0c;它简化了数据库操作&#xff0c;使开发者可以以面向对象的方式处理数据存储。通过定义实体类和数据访问接口&a…

探索5 大 Node.js 功能

目录 单线程 Node.js 工作线程【Worker Threads】 Node.js 进程 进程缺点 工作线程 注意 集群进程模块【Cluster Process Module】 内部发生了什么&#xff1f; 为什么要使用集群 注意&#xff1a; 应用场景&#xff1a; 内置 HTTP/2 支持 这个 HTTP/2 是什么&…

vscode使用yarn 启动vue项目记录

第一次启动yarn项目&#xff0c;这个是公司的老项目&#xff0c;遇到了点问题&#xff0c;记录下首先是我一般使用的是npm命令&#xff0c;所以没有安装yarn vscode安装yarn vscode进入到该项目文件夹下&#xff0c;输入命令&#xff1a;npm install -g yarn 安装成功后&…

实时数字人DH_live使用案例

参看: https://github.com/kleinlee/DH_live ubuntu 测试 apt install ffmpeg 下载安装: git clone https://github.com/kleinlee/DH_live.git cd DH_liveconda create -n dh_live python=3.12 conda activate dh_live pip install -r requirements.txt pip install torch -…

小程序开发设计-小程序的宿主环境:组件⑦

上一篇文章导航&#xff1a; 小程序开发设计-小程序的宿主环境&#xff1a;宿主环境简介⑥-CSDN博客https://blog.csdn.net/qq_60872637/article/details/142425131?spm1001.2014.3001.5501 注&#xff1a;不同版本选项有所不同&#xff0c;并无大碍。 目录 上一篇文章导航…