【数据结构】双向链表、单向循环链表、双向循环链表、栈、链栈

目录

一、双向链表

定义类和封装函数以及测试样例如下：

注意事项：

二、循环链表

单循环列表的类和函数封装如下：

注意事项： 

三、双向循环链表

结点类和双循环链表的定义部分

函数封装之判空和尾插

双循环链表遍历

双循环链表尾删

完整测试以及结果：

四、栈

顺序栈

顺序栈本质以及组成

顺序栈的操作

链栈

一、双向链表

对于单向链表而言。只能通过头节点或者第一个节点出发，单向的访问后继节点，每个节点只能记录其后继节点的信息（位置），不能向前遍历。

所以引入双向链表，双向链表可以保持单向链表特点的基础上，让每个节点，既能向后访问后继节点，也可以向前访问前驱节点。

相较于单向链表，我们更多的是在每个结点上加入了一个前驱链接域

定义类和封装函数以及测试样例如下：

class Node(object):
    def __init__(self,data):
        self.next = None
        self.prior = None
        self.data = data

class DoubleLinklist(object):
    def __init__(self):
        self.head = None
        self.size = 0

    def is_empty(self):
        return self.size == 0

    def add_head(self,value):
        node=Node(value)
        if self.is_empty():
            self.head = node
            self.size+=1
        else:
            node.next = self.head
            self.head.prior = node
            self.head = node
            self.size += 1

    def show_me(self):
        if self.is_empty():
            print('空表查看不了')
        else:
            q = self.head
            while q :
                print(q.data,end=' ')
                q = q.next

    def add_anywhere(self,location,value):
        if location < 1 or location > self.size+1:
            print('插入失败')
        else:
            node = Node(value)
            if location == 1:
                self.add_head(value)
            else:
                q = self.head
                i = 1
                while i< location-1:
                    q = q.next
                    i += 1
                if q.next is None:
                    q.next = node
                    node.prior = q
                else:
                    node.next = q.next
                    node.prior = q
                    q.next.prior = node
                    q.next = node
                self.size+=1

    def del_anywhere(self,location):
        if self.is_empty() or location < 1 or location > self.size:
            print('删除失败')
        else:
            if location == 1:
                self.head = self.head.next
                self.head.prior = None
            else:
                q=self.head
                i =1
                while i < location :
                    q = q.next
                    i += 1
                if  q.next :
                    q.prior.next = q.next
                    q.next.prior = q.prior
                else:
                    q.prior.next = None
            self.size -=1

    def find_node(self,value):
        if self.is_empty():
            print('查找失败')
        else:
            q = self.head
            while q:
                if q.data == value:
                    return True
                q = q.next
            return False






if __name__ == '__main__':
    new_l=DoubleLinklist()
    print('头插')
    new_l.add_head(50)
    new_l.add_head(40)
    new_l.add_head(30)
    new_l.add_head(20)
    new_l.add_head(10)
    new_l.show_me()
    print()

    print('任意位置插入')
    new_l.add_anywhere(1,666)
    new_l.add_anywhere(7,666)
    new_l.add_anywhere(3,666)
    new_l.show_me()
    print()

    print('任意位置删除')
    new_l.del_anywhere(8)
    new_l.del_anywhere(3)
    new_l.del_anywhere(1)
    new_l.show_me()
    print()

    print('找是否存在值30')
    print(new_l.find_node(30))
    print()

结果如下：

注意事项：

对链表的删除和插入操作我们均要考虑空表、末尾元素、单个元素情况；双循环链表的插入操作 :                       node.next = q.next
                    node.prior = q
                    q.next.prior = node
                    q.next = node

这四条语句除了第一条的位置不能变动以外（防止丢失结点），后面的操作前后顺序没有强制要求。

二、循环链表

循环链表：就是首尾相连的链表，通过任意一个节点，都能将整个链表遍历一遍

单循环列表的类和函数封装如下：


class Node(object):
    def __init__(self,data):
        self.data = data
        self.next = None

class CirculateLinkList(object):
    def __init__(self):
        self.head = None
        self.size = 0

    def is_empty(self):
        return self.size == 0

    def add_tail(self,value):
        node = Node(value)
        if self.is_empty():
            self.head = node
            node.next = node
        else:
            q = self.head
            i = 1
            while i < self.size:
                q = q.next
                i += 1
            q.next = node
            node.next = self.head
        self.size += 1

    def show_me(self):
        if self.is_empty():
            print('空表')
        elif self.size == 1 :
            print(self.head.data)
        else:
            q = self.head
            i = 1
            while i < self.size+1:  #q要定位到第一个结点才能遍历完
                print(q.data,end=' ')
                q=q.next
                i += 1

    def del_tail(self):
        if self.is_empty():
            print('删除失败')
        elif self.size == 1 :
            self.head = None
            self.size -=1
        else:
            q = self.head
            i = 1
            while i < self.size-1 :
                q = q.next
                i+=1
            q.next = self.head
            self.size -= 1

if __name__ == '__main__':
    new_l=CirculateLinkList()
    print('尾插')
    new_l.add_tail(30)
    new_l.add_tail(20)
    new_l.add_tail(10)
    new_l.show_me()
    print()

    print('尾删')
    new_l.del_tail()
    new_l.del_tail()
    new_l.show_me()
    print()

结果：

注意事项： 

基本注意事项不再赘述，这里有个格外要注意的点：


    def show_me(self):
        if self.is_empty():
            print('空表')
        elif self.size == 1 :
            print(self.head.data)
        else:
            q = self.head
            i = 1
            while i < self.size+1:  #q要定位到第一个结点才能遍历完
                print(q.data,end=' ')
                q=q.next
                i += 1

while循环要多循环一次，使得q指向第一个结点才能遍历完整

三、双向循环链表

双循环链表同样需要考虑几个点，如何创建，如何增删改查，由于是双向的，那么可以不用像单向的删除操作中一定要找到删除元素前一个位置，可以直接定位到要删除的位置，只需要把前驱后继都重新分配好即可。

结点类和双循环链表的定义部分

class Node(object):
    def __init__(self,data):
        self.data=data
        self.next=None
        self.prior=None

class DoubleCirculateLinkList(object):
    def __init__(self):
        self.head=None
        self.size=0

函数封装之判空和尾插

 注意：尾插部分要注意分空表和单元素情况

    def is_empty(self):
        return self.size == 0

    def add_tail(self,value):
        node=Node(value)
        if self.is_empty():
            self.head=node
            node.next=node
            node.prior=node
        elif self.size == 1:
            self.head.next=node
            self.head.prior=node
            node.next=self.head
            node.prior=self.head
        else:
            q=self.head
            while True:
                q=q.next
                if q.next==self.head:
                    break
            node.next=self.head
            node.prior=q
            q.next=node
            self.head.prior=node
        self.size+=1

这里的常规尾插我用到的遍历循环是while True：内部增加一个判断退出的条件来获得末尾结点q

情况全分析完毕整体判断外size+=1即可

双循环链表遍历

遍历涉及到打印，我们用一个变量q来记录，常规情况下要遍历到最后一个结点，但这还不够，要执行的下去循环内的打印语句才行，所以要留意。

 def show_me(self):
        if self.is_empty():
            print('空表')
        else:
            q=self.head
            while True:
                print(q.data,end=' ')
                q=q.next
                if q ==self.head:
                    break

双循环链表尾删

首先，空表无法删除，单元素删除直接head==None，常规情况可直接遍历到最后一个结点（由于是双向的链表所以不用找倒数第二个结点了），然后将该结点的前驱结点next指向head，head指向的结点的前驱再指向回来即可删除。

    def del_tail(self):
        if self.is_empty():
            print('空表')
        elif self.size == 1:
            self.head = None
        else:
            q=self.head
            while True:
                q=q.next
                if q.next==self.head:
                    break
            q.prior.next=self.head
            self.head.prior=q.prior
        self.size-=1

完整测试以及结果：

class Node(object):
    def __init__(self,data):
        self.data=data
        self.next=None
        self.prior=None

class DoubleCirculateLinkList(object):
    def __init__(self):
        self.head=None
        self.size=0

    def is_empty(self):
        return self.size == 0

    def add_tail(self,value):
        node=Node(value)
        if self.is_empty():
            self.head=node
            node.next=node
            node.prior=node
        elif self.size == 1:
            self.head.next=node
            self.head.prior=node
            node.next=self.head
            node.prior=self.head
        else:
            q=self.head
            while True:
                q=q.next
                if q.next==self.head:
                    break
            node.next=self.head
            node.prior=q
            q.next=node
            self.head.prior=node
        self.size+=1

    def show_me(self):
        if self.is_empty():
            print('空表')
        else:
            q=self.head
            while True:
                print(q.data,end=' ')
                q=q.next
                if q ==self.head:
                    break

    def del_tail(self):
        if self.is_empty():
            print('空表')
        elif self.size == 1:
            self.head = None
        else:
            q=self.head
            while True:
                q=q.next
                if q.next==self.head:
                    break
            q.prior.next=self.head
            self.head.prior=q.prior
        self.size-=1

if __name__ == '__main__':
    new_l=DoubleCirculateLinkList()
    print('尾插')
    new_l.add_tail(10)
    new_l.add_tail(20)
    new_l.add_tail(30)
    new_l.add_tail(40)
    new_l.add_tail(50)
    new_l.show_me()
    print()

    print('尾删')
    new_l.del_tail()
    new_l.del_tail()
    new_l.show_me()
    print()

四、栈

顺序栈

顺序存储的栈即是顺序栈

顺序栈本质以及组成

本质上：顺序栈是一个只允许在栈顶进行插入和删除操作的顺序表，遵循LIFO

需要使用一个容器存储一个栈，例如列表

顺序栈的操作

这里直接使用内置函数去对栈封装

class Stack(object):
    def __init__(self):
        self.data = []

    def is_empty(self):
        return self.data == []

    def push(self,value):
        self.data.insert(0,value)

    def pop(self):
        self.data.pop(0)

    def show(self):
        for i in self.data:
            print(i,end=' ')
        print()

    def get_top_value(self):
        return self.data[0]

    def get_size(self):
        return len(self.data)

链栈

既然顺序栈就是对栈顶元素增删的特殊的顺序表，那么链栈就是对栈顶元素增删的特殊的单向链表

这里我的pop不仅实现了删除，而且还增加了额外的返回值

代码如下：

class Node(object):
    def __init__(self,data):
        self.data=data
        self.next=None

class LinkStack(object):
    def __init__(self):
        self.size=0
        self.head=None

    def is_empty(self):
        return self.size==0

    def push(self,value):
        node=Node(value)
        node.next=self.head
        self.head=node
        self.size+=1

    def pop(self):
        if self.is_empty():
            print('空栈')
        else:
            q=self.head.data
            self.head=self.head.next
            self.size-=1
            return q

    def show(self):
        if self.is_empty():
            print('空栈')
        else:
            q=self.head
            while q:
                print(q.data,end=' ')
                q=q.next

    def get_top_value(self):
        if self.is_empty():
            return None
        else:
            return self.head.data

    def get_size(self):
        return self.size

未完待续（持续跟新中）🏆

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

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

相关文章

ModuleNotFoundError: No module named ‘_ssl‘ centos中的Python报错

ModuleNotFoundError: No module named ‘_ssl‘ centos中的Python报错

1、检查系统有没有openssl&#xff0c;有的话&#xff0c;就是python安装时没有指定openssl openssl version&#xff0c;有输出版本号就有&#xff0c;没有的话&#xff0c;需要手动安装 下载地址 参见https://www.openssl.org/&#xff0c;包括以下版本&#xff1a; https:/…
阅读更多...
C语言：树

C语言：树

在C语言中&#xff0c;树&#xff08;Tree&#xff09;是一种常见的数据结构&#xff0c;用于表示分层关系或层次结构的数据集合。树在计算机科学中广泛应用&#xff0c;包括但不限于文件系统、解析表达式、数据压缩、决策树等。 1. 基本概念 节点&#xff08;Node&#xff0…
阅读更多...
python写的服务，用docker制作镜像并且打包

python写的服务，用docker制作镜像并且打包

步骤1 简单写一个python服务脚本app.py&#xff0c;通过http访问一个端口&#xff0c;收到helloworld from flask import Flask, request app Flask(__name__) app.route(/, methods[GET]) # 确保包括GET方法 def hello_world(): return Hello, World! if __name__ __main…
阅读更多...
NSSCTF web刷题

NSSCTF web刷题

1 虽然找到了flag,但是我要怎么去改他的代码,让他直接输出flag呢? (好像是要得到他的json代码,这题不让看) 2 wllm应该就是他的密码,进入许可了 意思是服务器可以执行通过POST的请求方式传入参数为wllm的命令&#xff0c;那这就是典型的命令执行&#xff0c;当然&#xff0c…
阅读更多...
(0基础保姆教程)-JavaEE开课啦！--11课程(初识Spring MVC + Vue2.0 + Mybatis)-实验9

(0基础保姆教程)-JavaEE开课啦！--11课程(初识Spring MVC + Vue2.0 + Mybatis)-实验9

一、什么是Spring MVC&#xff1f; Spring MVC 是一个基于 Java 的 Web 框架&#xff0c;遵循 MVC 设计模式&#xff0c;用于构建企业级应用程序。它通过控制器(Controller)处理用户请求&#xff0c;模型(Model)处理业务逻辑&#xff0c;视图(View)展示数据&#xff0c;实现了请…
阅读更多...
FCBP 认证考试要点摘要

FCBP 认证考试要点摘要

理论知识 数据处理与分析&#xff1a;包括数据的收集、清洗、转换、存储等基础操作&#xff0c;以及数据分析方法&#xff0c;如描述性统计分析、相关性分析、数据挖掘算法等的理解和应用 。数据可视化&#xff1a;涉及图表类型的选择与应用&#xff0c;如柱状图、折线图、饼图…
阅读更多...
「Qt Widget中文示例指南」如何为窗口实现流程布局？（二）

「Qt Widget中文示例指南」如何为窗口实现流程布局？（二）

Qt 是目前最先进、最完整的跨平台C开发工具。它不仅完全实现了一次编写&#xff0c;所有平台无差别运行&#xff0c;更提供了几乎所有开发过程中需要用到的工具。如今&#xff0c;Qt已被运用于超过70个行业、数千家企业&#xff0c;支持数百万设备及应用。 本文将展示如何为不…
阅读更多...
智能产品综合开发 - 手势识别

智能产品综合开发 - 手势识别

1 实训选题目的 本次实训选择的题目是“基于树莓派的手势识别系统”&#xff0c;旨在为人们提供一种便捷的交互方式&#xff0c;使用户能够通过手势控制智能设备&#xff0c;摆脱传统的物理按键操作。通过本项目&#xff0c;我们希望能实现快速、灵活的手势识别&#xff0c;提升…
阅读更多...
Redis【1】- 如何阅读Redis 源码

Redis【1】- 如何阅读Redis 源码

1 Redis 的简介 Redis 实际上是简称&#xff0c;全称为 Remote Dictionary Server (远程字典服务器)&#xff0c;由 Salvatore Sanfilippo 写的高性能 key-value 存储系统&#xff0c;其完全开源免费&#xff0c;遵守 BSD 协议。Redis 与其他 key-value 缓存产品&#xff08;如…
阅读更多...
git的使用（简洁版）

git的使用（简洁版）

什么是 Git&#xff1f; Git 是一个分布式版本控制系统 (DVCS)&#xff0c;用于跟踪文件的更改并协调多人之间的工作。它由 Linus Torvalds 在 2005 年创建&#xff0c;最初是为了管理 Linux 内核的开发。Git 的主要目标是提供高效、易用的版本控制工具&#xff0c;使得开发者…
阅读更多...
用于高吞吐量和低延迟的 JVM 性能调优

用于高吞吐量和低延迟的 JVM 性能调优

Java 虚拟机 &#xff08;JVM&#xff09; 调优是调整默认参数以满足我们的应用程序需求的过程。这包括通过选择合适的垃圾回收器来使用优化版本的 getter 来调整堆的大小等简单调整。 了解 Java 虚拟机 &#xff08;JVM&#xff09; 什么是 JVM&#xff1f; Java 虚拟机 &…
阅读更多...
django authentication 登录注册

django authentication 登录注册

文章目录 前言一、django配置二、后端实现1.新建app2.编写view3.配置路由 三、前端编写1、index.html2、register.html3、 login.html 总结 前言 之前&#xff0c;写了django制作简易登录系统&#xff0c;这次利用django内置的authentication功能实现注册、登录 提示&#xff…
阅读更多...
Python+Pytest+Yaml+Allure数据参数化（DDT）数据驱动（一）

Python+Pytest+Yaml+Allure数据参数化（DDT）数据驱动（一）

我们在做数据之前要知道几个问题 1、在代码层面怎么来数据驱动 2、yaml文件是什么 3、怎么用yaml文件实现对应的数据驱动 我们用的是pytest框架所以相对来说是简单的&#xff0c;我们通过pytest框架来实现&#xff0c;而框架中要数据驱动用到我们装饰器就好啦pytest.mark.p…
阅读更多...
WaveForms™ SDK 参考手册(翻译笔记与总结)

WaveForms™ SDK 参考手册(翻译笔记与总结)

概述 WaveForms 提供了一个接口&#xff0c;允许用户与 Digilent Analog Design 硬件进行交互&#xff0c;例如 Analog DiscoveryTM、Analog Discovery 2TM、Analog Discovery ProTM、Digital DiscoveryTM、Discovery Power SupplyTM 和 Electronics ExplorerTM。虽然 WaveForm…
阅读更多...
Python基础学习-12匿名函数lambda和map、filter

Python基础学习-12匿名函数lambda和map、filter

目录 1、匿名函数&#xff1a; lambda 2、Lambda的参数类型 3、map、 filter 4、本节总结 1、匿名函数&#xff1a; lambda 1&#xff09;语法&#xff1a; lambda arg1, arg2, …, argN : expression using arg 2&#xff09; lambda是一个表达式&#xff0c;而不是一个语…
阅读更多...
pyqt5+yolo模型+多线程

pyqt5+yolo模型+多线程

界面开发 开发主窗口界面 from PyQt5 import QtWidgets from PyQt5 import QtCore,QtGui import sysclass MainWindow(QtWidgets.QMainWindow):def __init__(self):super().__init__()self.initUI()self.toolbar()# 创建菜单栏def initUI(self):menubar self.menuBar()file_m…
阅读更多...
交通流量预测：基于交通流量数据建立模型

交通流量预测：基于交通流量数据建立模型

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…
阅读更多...
[Java]微服务配置管理

[Java]微服务配置管理

介绍 代码拆分为微服务后, 每个服务都有自己的配置文件, 而这些配置文件中有很多重复的配置, 并且配置变化后需要重启服务, 才能生效, 这样就会影响开发体验和效率 配置管理服务可以帮助我们集中管理公共的配置, 并且nacos就可以实现配置管理服务 配置共享 我们可以把微服务共…
阅读更多...
【C++】入门【三】

【C++】入门【三】

本节目标 一、类的6个默认成员函数 二、 构造函数 三、析构函数 四、拷贝构造函数 五、赋值运算符重载 六、const成员函数 七、取地址及const取地址操作符重载 一、类的6个默认成员函数 如果类里一个成员都没有&#xff0c;简称空类空类中真的什么都没有吗&#xff1f;并不不是…
阅读更多...
D78【 python 接口自动化学习】- python基础之HTTP

D78【 python 接口自动化学习】- python基础之HTTP

day78 pycharm创建项目并进行接口请求 学习日期&#xff1a;20241124 学习目标&#xff1a;http定义及实战 -- pycharm创建项目并进行接口请求 学习笔记&#xff1a; 安装requests 安装方式&#xff1a;pip/pip3 install requests 官网教程&#xff1a;Requests: HTTP fo…
阅读更多...
最新文章

Copyright @ 2022~2023