当前位置：首页 > article >正文

链表与栈的实现及操作详解：从基础到应用

article 2025/3/15 7:18:51

前言
一、修改
二、转置
三、整体代码
四、单相循环链表
五、顺序栈
5.1 概念
5.2 接口实现
5.2.1 入栈
5.2.2 出栈
5.2.3 整体代码
六、小练习
总结

前言

书接上文

顺序表与单向链表的实现与应用详解-CSDN博客文章浏览阅读386次，点赞11次，收藏5次。本文深入解析顺序表和单向链表的设计原理与实现细节，通过Python代码演示了二者的插入、删除、查找等基础操作。顺序表基于数组实现，强调下标操作和元素移动策略；单向链表依托节点对象与指针操作，展现动态内存管理优势。文章对比两种结构在时间复杂度、空间效率及适用场景的差异，并给出完整可执行的代码示例，帮助读者理解线性结构的底层逻辑与应用场景选择。https://blog.csdn.net/qq_58364361/article/details/146223790?fromshare=blogdetail&sharetype=blogdetail&sharerId=146223790&sharerefer=PC&sharesource=qq_58364361&sharefrom=from_link

一、修改

修改指定位置数据

post类比下标，即从0开始。

    # 8.修改指定位置的数据 post 被修改的位置 data修改成的数据
    def change_data(self, position, data):
        pass

二、转置

头-1-2-3-4-5 ---> 头-5-4-3-2-1

hello

olleh

步骤：

头 1-2-3-4-5

头-1 2-3-4-5

头-2-1 3-4-5

头-3-2-1 4-5

思想：将链表拆成空的有头单向链表和一个无头单向链表

遍历无头单向链表，将每个结点头插进有头单向链表中

    def reverse(self):
        # 断开前，保存头节点的下一个节点的地址
        current = self.head.next
        # 断开链表
        self.head.next = None
        # 遍历无头单向链表，把无头单向链表的节点头插到有头空链表中
        while current:
            # 提前将current的下一个节点保存起来
            next_node = current.next
            # 先连后面，再连前面, 将无头表的节点插入头结点的下一个位置
            current.next = self.head.next
            self.head.next = current
            # 将current移动，指向下一个节点
            current = next_node

三、整体代码

class Node:
    """创建单链表节点"""

    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next = next_node


class LinkedList:
    def __init__(self):
        # 初始化一个头节点，它不包含实际数据，仅作为链表的起始标志
        self.head = Node()

    # 2.向单向链表的指定位置插入数据
    # post 插入的位置 data插入的数据
    def insert(self, position, data):
        if position < 0 or position > self.length():
            print("insert error")
            return
        # node新节点
        new_node = Node(data)
        # 移动伪指针到插入位置的前一个位置
        current = self.head
        for _ in range(position):
            current = current.next
        # 插入动作(先连后面，再连前面)
        new_node.next = current.next
        current.next = new_node

    # 3.遍历单向链表
    def show(self):
        current = self.head
        while current.next:
            current = current.next
            print(current.data, end=' ')
        print()

    # 4.求单向链表长度的函数
    def length(self):
        current = self.head
        length = 0
        while current.next:
            current = current.next
            length += 1
        return length

    # 5.删除单向链表中指定位置的数据 post 代表的是删除的位置
    def delete_position(self, position):
        if position < 0 or position >= self.length() or self.is_empty():
            print("delete_position error")
            return
        current = self.head
        for _ in range(position):
            current = current.next
        # 删除节点的前一个节点的指针域存放删除节点的下一个节点的地址
        current.next = current.next.next

    # 6.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
    def delete_data(self, data):
        if self.is_empty():
            print("del error")
            return
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
            else:
                current = current.next

    # 7.判断单向链表是否为空 1代表空 0代表非空
    def is_empty(self):
        return self.head.next is None

    # 8.修改指定位置的数据 post 被修改的位置 data修改成的数据
    def change_data(self, position, data):
        pass

    # 9.查找指定数据出现的位置 data被查找的数据 //search 查找
    def search_data(self, data):
        if self.is_empty():
            print("search_data failed")
            return
        current = self.head
        pos = 0
        while current.next:
            current = current.next
            if current.data == data:
                return pos
            pos += 1
        return -1

    # 10.转置链表
    def reverse(self):
        pass

    # 11.清空单向链表
    def clear(self):
        pass
    # endif


if __name__ == '__main__':
    link_list = LinkedList()
    link_list.insert(0, 999)
    link_list.insert(1, 888)
    link_list.insert(2, 777)
    link_list.show()
    link_list.insert(0, 1)
    link_list.insert(2, 666)
    link_list.show()
    print("search 999:", link_list.search_data(999))
    link_list.delete_position(0)
    link_list.show()
    link_list.insert(0, 666)
    link_list.insert(3, 666)
    link_list.show()
    link_list.delete_data(666)
    link_list.show()

四、单相循环链表

约瑟夫问题

设编号为1，2，……n的n个人围坐一圈，约定编号为k (1≤k≤n)的人从1开始报数，数到m的那个人出列。它的下一位继续从1开始报数，数到m的人出列，依次类推，最后剩下一个为猴王。

假设n=6总共6人，k=1从第一个人开始，m=5，每次从1数到5。

第一轮报数：从1号开始，数5个数，数完5个数，5号被杀死，第一轮报数后，剩余人数如下。

第二轮报数：

第三轮：

第四轮：

第五轮：

五、顺序栈

5.1 概念

1.什么是栈?

只能在一端进行插入和删除操作的线性表（又称为堆栈），进行插入和删除操作的一端称为栈顶（杯子顶部），另一端称为栈底（杯子底部）

案例：水杯

2. 栈特点：

先进后出FILO first in last out

top始终标记栈顶（始终代表的是栈内最后一个有效元素的下标）

逻辑结构：线性结构

物理结构：顺序存储

5.2 接口实现

class Stack:
    max_len = 32  # 保存栈的最大长度
    # 始终代表当前栈内最后一个有效元素的下标，称为栈顶指针
    top = -1
    data = [0] * max_len  # 顺序栈的存储空间
    # 1、判断是否为满, 满返回True,未满返回False
     def is_full(self):
        pass
    # 2. 入栈 
    def push(self, data: int):  # data代表入栈的数据
         pass
    # 3.判断栈是否为空
    def is_empty(self):
          pass 
    # 4.出栈 
    def pop(self):
        pass 
    # 5. 清空栈 
    def clear(self):
        pass 
    # 6.获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)
    def get_top(self):
        pass 
    # 7. 求栈的有限长度
    def get_length(self):
        pass

5.2.1 入栈

容错判断——判满——top+1==maxlen
入栈
移动栈针

    # 1、判断是否为满, 满返回True,未满返回False
    def is_full(self):
        return self.top + 1 == self.max_len

    # 2. 入栈
    def push(self, data: int):  # data代表入栈的数据
        if self.is_full():
            print("push error")
            return
        self.top += 1
        self.data[self.top] = data

5.2.2 出栈

数据出栈，返回出栈数据。

    # 3.判断栈是否为空
    def is_empty(self):
        return self.top == -1

    # 4.出栈
    def pop(self):
        if self.is_empty():
            print("pop error")
            return
        self.top -= 1
        return self.data[self.top + 1]

5.2.3 整体代码

class Stack:
    max_len = 32  # 保存栈的最大长度
    # 始终代表当前栈内最后一个有效元素的下标，称为栈顶指针
    top = -1
    data = [0] * max_len  # 顺序栈的存储空间

    # 1、判断是否为满, 满返回True,未满返回False
    def is_full(self):
        return self.top + 1 == self.max_len

    # 2. 入栈
    def push(self, data: int):  # data代表入栈的数据
        if self.is_full():
            print("push error")
            return
        self.top += 1
        self.data[self.top] = data

    # 3.判断栈是否为空
    def is_empty(self):
        return self.top == -1

    # 4.出栈
    def pop(self):
        if self.is_empty():
            print("pop error")
            return
        self.top -= 1
        return self.data[self.top + 1]

    # 5. 清空栈
    def clear(self):
        pass
        # 6.获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)

    def get_top(self):
        pass
        # 7. 求栈的有限长度

    def get_length(self):
        pass


if __name__ == '__main__':
    seq_stack = Stack()
    for i in range(6):
        seq_stack.push(i)
    # print("top_data=", seq_stack.get_top())
    # print("stack_len=", seq_stack.get_length())
    for _ in range(6):
        print(seq_stack.pop())

六、小练习

1.若进栈顺序为1 2 3 4 以下四种情况不可能出现的出栈序列是 ( )

A. 1 4 3 2 先1，再1出；再2、3、4，出4、3、2

B. 2 3 4 1

C. 3 1 4 2

D. 3 4 2 1

2.下列叙述正确的是 ( )

A. 线性表是线性结构

B. 栈与队列是非线性结构

C. 线性链表是非线性结构

D. 二叉树是线性结构

3.下列关于栈叙述正确的是( )

A. 在栈中只能插入数据

B. 在栈中只能删除数据

C. 栈是先进先出的线性表

D. 栈是先进后出的线性表

总结

本文系统讲解了链表与顺序栈的核心操作，结合代码实现与具体应用场景分析，帮助读者深入理解数据结构基础。首先，针对单链表的修改、转置、插入、删除等操作进行了代码级解析，重点探讨了链表转置的“无头链节点头插法”实现逻辑。其次，通过顺序栈的完整实现代码，剖析了栈的入栈、出栈、判空判满等关键操作细节，并结合栈的特性分析了典型题目答案（如栈的先进后出特性对应的选项验证）。最后，以约瑟夫问题为引，延伸至循环链表的应用场景，为数据结构实践提供思路。文中所有代码均经过逻辑验证，练习题答案结合原理分析确保准确性，全面覆盖链表与栈的核心知识点。

查看全文

http://www.kler.cn/a/585222.html