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

学习日志016--python实现双向循环列表与链栈

article 2024/11/27 0:07:53

python中一些复合数据结构通过类的封装来实现的。双向循环链表与链栈也在其中。

双向循环链表

双向循环链表是一种特殊类型的链表，它结合了双向链表和循环链表的特点。在双向循环链表中，每个节点不仅包含数据，还持有指向前一个和后一个节点的指针，而且链表的最后一个节点指向第一个节点，形成一个闭环。

封装

就像上面介绍的一样，每一个结点（头结点除外）都有前驱，后继，以及数据域。由此创建结点类。

# 创建双向链表节点
# 双向链表结点有前驱有后继有数据域
class Node:
    def __init__(self,data):
        self.data = data
        self.prior = None
        self.next = None

头结点

不是必须的，但为了方便对链表的操作，我们还是会创建。和其他链表的头结点一样，包含链表长度和head的成员变量。

#创建头结点便于操作链表
class Double:
    # 头结点记录链表地址，链表长度
    def __init__(self,node = None):
        self.head = node
        self.size = 0

判空

同样由于链式存储的优点，我们只需要判空。

    # 判空
    def is_empty(self):
        return self.size == 0

双向链表的插入与删除，根据表内元素个数不同，需要分开编写代码

尾插法

#尾插 根据链表是否为空有不同的插入方法
    def insert_rear(self,value):
        node = Node(value)
        # 当表为空时
        if self.is_empty():
            # 当只有一个元素时，循环链表前驱和后继指向自己
            self.head = node
            node.next =  node
            node.prior = node
        else:
            # 变量指向最后一个结点，即head的前驱
            p = self.head.prior
            node.next = p.next
            node.prior = p
            p.next.prior = node
            p.next = node
        self.size += 1

尾删法

# 尾删
    def del_rear(self):
        if self.is_empty():
            print("删除失败")
        elif self.size == 1:
            self.head = None
        else:
            # 尾删直接将头结点的前驱指向前前结点，同时将现前结点的后继指向头结点
            q = self.head.prior.prior
            self.head.prior = q
            q.next = self.head
        self.size -= 1

遍历

双向循环列表可以使用前驱遍历和后继遍历两种方式

# 后继 
    def show(self):
        if self.size == 0:
            print("遍历失败")
            return
        else:
          
            p = self.head
            while p.next != self.head:
                print(f"{p.data}",end=" ")
                p = p.next
                
            print(f"{p.data}")


#前驱
    def r_show(self):
        if self.size == 0:
            print("遍历失败")
            return
        else:
           
            p = self.head
            while p.prior != self.head:
                print(f"{p.data}", end=" ")
                p = p.prior
                
            print(f"{p.data}")

全部代码

# 创建双向链表节点
# 双向链表结点有前驱有后继有数据域
class Node:
    def __init__(self,data):
        self.data = data
        self.prior = None
        self.next = None

#创建头结点便于操作链表
class Double:
    # 头结点记录链表地址，链表长度
    def __init__(self,node = None):
        self.head = node
        self.size = 0

    # 判空
    def is_empty(self):
        return self.size == 0

    #尾插 根据链表是否为空有不同的插入方法
    def insert_rear(self,value):
        node = Node(value)
        # 当表为空时
        if self.is_empty():
            # 当只有一个元素时，循环链表前驱和后继指向自己
            self.head = node
            node.next =  node
            node.prior = node
        else:
            # 变量指向最后一个结点，即head的前驱
            p = self.head.prior
            node.next = p.next
            node.prior = p
            p.next.prior = node
            p.next = node
        self.size += 1

    # 根据链表长度遍历输出
    def show(self):
        if self.size == 0:
            print("遍历失败")
            return
        else:
            i = 1
            p = self.head
            while p.next != self.head:
                print(f"{p.data}",end=" ")
                p = p.next
                i+=1
            print(f"{p.data}")

    def r_show(self):
        if self.size == 0:
            print("遍历失败")
            return
        else:
            i = 1
            p = self.head
            while p.prior != self.head:
                print(f"{p.data}", end=" ")
                p = p.prior
                i += 1
            print(f"{p.data}")
    # 尾删
    def del_rear(self):
        if self.is_empty():
            print("删除失败")
        elif self.size == 1:
            self.head = None
        else:
            # 尾删直接将头结点的前驱指向前前结点，同时将现前结点的后继指向头结点
            q = self.head.prior.prior
            self.head.prior = q
            q.next = self.head
        self.size -= 1

if __name__ =="__main__":

    d = Double()
    # 尾插法
    d.insert_rear(10)
    d.insert_rear(20)
    d.insert_rear(30)
    d.insert_rear(40)
    d.show()
    d.r_show()
        # 尾删法
    d.del_rear()
    d.show()
    d.del_rear()
    d.show()
    d.del_rear()
    d.show()
    d.del_rear()
    d.show()
10 20 30 40
10 40 30 20
10 20 30
10 20
10
遍历失败

链栈

链栈（Linked Stack）是一种基于链表实现的栈结构。在链栈中，每个元素都是一个节点，包含数据域和指向下一个节点的指针。链栈不需要像顺序栈那样预先分配固定大小的存储空间，它可以动态地分配和释放内存，因此更加灵活。

经过之前的练习，对于链式存储已经得心应手，简单完成栈的结点与头结点的封装

结点

和我们学习的线性表相同，链栈的结点也是由数据域与链接域组成。

# 创建链栈
# 创建链栈的结点，包含数据域data与链接域next
class Node:
    def __init__(self,data):
        self.data = data
        self.next = None

 头结点

栈没有像线性表一样，计算长度的实例变量。有一个指向栈顶元素的top

# 封装链栈 一个永远指向栈顶的头结点，不限于统计链栈长度 ，记录栈顶位置
class LinkStack:
    def __init__(self,top = None):
        self.top = top

判空

    # 判空
    def is_empty(self):
        return self.top is None

入栈

类似之前线性表的头插法 ，新结点指向栈顶，top指向新的结点

   # 入栈 每个新元素充当栈顶
    def push(self,value):
        node = Node(value)
#         根据是否栈空这里有不同的插入方法
        if self.is_empty():
            self.top = node
        else:
            node.next = self.top
            self.top = node

出栈

先入后出是栈的特性，最后入栈的元素后出来。出栈会返回该元素并删除。

     出栈 返回栈顶元素并删除
    def pop(self):
#         这里根据元素的多少有两种写法
        i = self.top
        if self.is_empty():
            print("栈空操作失败")
            return i
        else:
            if self.top.next is None:
                self.top = None
                return i.data
            else:
                self.top = self.top.next
                return i.data

返回栈顶元素

    def peek(self):
        #         这里根据元素的多少有两种写法
        i = self.top
        if self.is_empty():
            print("栈空操作失败")
            return i
        else:

            self.top = self.top.next
            return i

统计栈的大小

    def size(self):
        i = 0
        p = self.top
        while p:
            p = p.next
            i+=1
        return i

遍历栈的元素

  def show(self):
        if self.is_empty():
            print("栈空操作失败")
        else:
            p =self.top
            while p:
                print(f"{p.data}",end=" ")
                p = p.next
            print()

全部代码

# 创建链栈
# 创建链栈的结点，包含数据域data与链接域next
class Node:
    def __init__(self,data):
        self.data = data
        self.next = None

# 封装链栈 一个永远指向栈顶的头结点，不限于统计链栈长度 ，记录栈顶位置
class LinkStack:
    def __init__(self,top = None):
        self.top = top

    # 判空
    def is_empty(self):
        return self.top is None

    # 入栈 每个新元素充当栈顶
    def push(self,value):
        node = Node(value)
#         根据是否栈空这里有不同的插入方法
        if self.is_empty():
            self.top = node
        else:
            node.next = self.top
            self.top = node

#     出栈 返回栈顶元素并删除
    def pop(self):
#         这里根据元素的多少有两种写法
        i = self.top
        if self.is_empty():
            print("栈空操作失败")
            return i
        else:
            if self.top.next is None:
                self.top = None
                return i.data
            else:
                self.top = self.top.next
                return i.data

    def peek(self):
        #         这里根据元素的多少有两种写法
        i = self.top
        if self.is_empty():
            print("栈空操作失败")
            return i
        else:

            self.top = self.top.next
            return i

    def size(self):
        i = 0
        p = self.top
        while p:
            p = p.next
            i+=1
        return i

    def show(self):
        if self.is_empty():
            print("栈空操作失败")
        else:
            p =self.top
            while p:
                print(f"{p.data}",end=" ")
                p = p.next
            print()

if __name__ == "__main__":
    s = LinkStack()
    s.push(10)
    s.push(20)
    s.push(30)
    s.push(40)
    s.push(50)
    print(s.size())
    s.show()
    s.pop()
    s.show()
    s.peek()
    s.show()
    s.pop()
    s.show()
    s.pop()
    s.show()
    s.pop()
    s.show()
    s.pop()
    s.show()

D:\xn\hqyj\pythonProject\.venv\Scripts\python.exe C:\Users\31284\OneDrive\Desktop\PYTHON\数据结构\day03\03.py 
5
50 40 30 20 10 
40 30 20 10 
30 20 10 
20 10 
10 
栈空操作失败
栈空操作失败
栈空操作失败

进程已结束，退出代码为 0


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

相关文章：

  • 浅谈网络 | 传输层之套接字Socket
  • 自研芯片逾十年，亚马逊云科技Graviton系列芯片全面成熟
  • “软件定义汽车”时代 | 产线海量数据刷写解决方案
  • javaEE初阶——多线程（1）
  • Java基于Spring Boot框架的房屋租赁系统，附源码
  • springboot集成shiro和前后端分离配置
  • 软件测试丨Python语法与数据结构
  • C++【面试重要题目】 只出现一次的数字的集合.
  • git推送报错443
  • 从零开始：NetBox 4.1 Docker 部署和升级
  • 嵌入式的C/C++：深入理解 static、const 与 volatile 的用法与特点
  • 4.3 使用 JMeter 发起请求详解
  • 【人工智能】基于PyTorch的深度强化学习入门：从DQN到PPO的实现与解析
  • python VS c++
  • 室内定位论文速递（11.18-11.22）
  • Visual Studio下载安装教程（非常详细）从零基础入门到精通，看完这一篇就够了_visual studio安装教程
  • 鸿蒙征文｜鸿蒙心路旅程：从零到一的探索与成长——我的HarmonyOS
  • 如何定制谷歌浏览器的外观主题
  • 基于IPMI的服务器硬件监控指标解读
  • CSS笔记（一）炉石传说卡牌设计1
  • 周志华深度森林deep forest（deep-forest）最新可安装教程，仅需在pycharm中完成，超简单安装教程
  • android 音效可视化--Visualizer
  • 工欲善其事，必先利其器；爬虫路上，我用抓包
  • 003 STM32基础、架构以及资料介绍——常识
  • 【Vue3 for beginner】普通插槽、具名插槽、作用域插槽
  • TM1可视化解决方案：企业增效降本的智控大脑