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

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

目录

  • 前言
  • 一、修改
  • 二、 转置
  • 三、整体代码
  • 四、单相循环链表
  • 五、顺序栈
  • 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()


四、单相循环链表

约瑟夫问题

设编号为12,……nn个人围坐一圈,约定编号为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 入栈

  1. 容错判断——判满——top+1==maxlen
  2. 入栈
  3. 移动栈针
    # 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

相关文章:

  • GIT日常记录
  • 六十天前端强化训练之第十五天React组件基础案例:创建函数式组件展示用户信息(第15-21天:前端框架(React))
  • ES怎么通过客户端操作和查询/curl操作指令
  • 地下停车场调频广播覆盖:破解地下车库无线广播收听孤岛,技术赋能地下停车场FM调频无线广播覆盖
  • 【python实战】-- 选择解压汇总mode进行数据汇总20250314更新
  • 61.Harmonyos NEXT 图片预览组件之数据模型设计与实现
  • API自动化测试实战:Postman + Newman/Pytest的深度解析
  • 注意力机制,层归一化,RBA。KAN-ODE,小波KAN
  • 如何使用Postman,通过Mock的方式测试我们的API
  • 【python】一文掌握 Conda 指令 (anaconda备忘清单)
  • 端口转发、隧道与Pivoting技术详解及区别解析
  • 数据类型及sizeof,进制转换
  • 蓝桥杯 排序题目【算法赛】
  • Unity光线追踪移动端降级适配技术指南
  • Mybatis 框架学习
  • C# Type类中Name、FullName、Namespace、AssemblyQualifiedName的区别
  • 了解一下HTTP的短连接和长连接
  • 从波士顿动力到Figure AI:探寻人工智能驱动的机器人智能化
  • UdpClient
  • 什么是 MyBatis?