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

往期链接

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 -> (回到头节点)