首页 > 编程语言 >Python数据结构day3

Python数据结构day3

时间：2024-11-25 19:00:20浏览次数：6  
标签：node head Python self day3 链表 数据结构 data def

一、双向链表

1.1 作用

双向链表也叫双面链表。

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

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

1.2 节点和链表类的定义

#定义节点类的类型
class Node:
    #显性定义出构造函数
    def __init__(self,data):
        self.data = data #普通节点的数据域
        self.next = None #保存下一个节点的链接域
        self.prior = None #保存前一个节点饿链接域

#定义双向链表的类的类型
class DoubleLink:
    #定义构造函数
    def __init__(self,node = None):
        self.head = node #头结点的head初始化为None
        self.size = 0 #链表的初始长度为0

1.3 双向链表的相关操作（功能函数的封装）

1】判空

函数功能：判断双向链表是否为空。思路：判断头结点的数据域是否为0，或者判断头结点的链接域是否为None

函数返回值：空则返True 非空返回False

函数名：符合命名规则

参数列表：双向链表

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

2】头插

函数功能：往双向链表中增加一个节点，并且是头插的方式。思路：如上图

函数返回值：可以是无，也可以bool类型

函数名：符合命名规则

参数列表：双向链表、要插入的元素

注意事项：判断双向链表是否为空。

插入成功，链表长度自增。

#头插
def add_head(self,data):
    #创建出一个新的节点
    node = Node(data)
    #判断链表是否为空 分为空和非空情况
    if self.is_empty():
        self.head = node
    else:
        node.next = self.head
        self.head.prior = node #node.next.prior = node
        self.head = node
    #插入成功 链表长度自增
    self.size += 1

3】遍历

函数功能：依次打印出链表节点中的数据。（同思路）

函数返回值：无

函数名：符合命名规则

参数列表：双向链表

注意事项：判断双向链表是否为空

#遍历
def show(self):
    #判空
    if self.is_empty():
        print("链表为空 遍历失败")
    else:
        q = self.head
        while q:
            print("%d "%(q.data),end = " ")
            q = q.next
        print()

4】任意位置插入

函数功能：在双向链表的任意位置插入数据

函数返回值：可以是无 也可以是bool

函数名：符合命名规则

参数列表：双向链表self、要插入的位置、要插入的数据

注意事项：

1、是否是第一个位置、最后一个位置、其他位置

#任意位置插入
def add_index(self,idex,data):
    #判断插入的位置是否合理
    if idex<1 or idex>self.size+1:
        print("插入失败")
    else:
        #判断插入的位置是否是第一个位置
        if idex == 1:
            self.add_head(data)
        else:
            #创建新的节点
            node = Node(data)
            #找到要插入位置的前一个节点
            q = self.head
            i=1
            while i<idex-1:
                q = q.next
                i+=1
            # 判断插入的位置是否是最后一个节点
            if q.next == 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

5】任意位置删除

函数功能：删除双向链表指定的位置

函数返回值：可以是无 可以是bool

函数名：符合命名规范

参数列表：双向链表self、删除的位置

注意事项：

1.判空

2.判断删除的位置是否是第一个、最后一个、其他位置

#任意位置删除
def del_idex(self,idex):
    #判空  判断位置是否合理：
    if self.is_empty() or idex<1 or idex>self.size:
        print("删除失败")
    else:
        #判断删除的是否是第一个节点
        if idex == 1:
            self.head = self.head.next
            self.head.prior = None
        else:
            #判断删除的是否是最后一节节点
            q = self.head
            i = 1
            while i<idex:
                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

6】查找节点是否存在

函数功能：按值查找，返回真假（存在或者不存在）

函数返回值：bool

函数名：符合命名规则

参数列表：要查找的数据

#查找节点是否存在 按值
def find_node(self,data):
    #判空
    if self.is_empty():
        print("查询失败")
    else:
        p = self.head
        while p:
            if p.data == data:
                return True
            p=p.next
        return False

全部代码：

#定义节点类的类型
class Node:
    #显性定义出构造函数
    def __init__(self,data):
        self.data = data #普通节点的数据域
        self.next = None #保存下一个节点的链接域
        self.prior = None #保存前一个节点饿链接域

#定义双向链表的类的类型
class DoubleLink:
    #定义构造函数
    def __init__(self,node = None):
        self.head = node #头结点的head初始化为None
        self.size = 0 #链表的初始长度为0

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

    #头插
    def add_head(self,data):
        #创建出一个新的节点
        node = Node(data)
        #判断链表是否为空 分为空和非空情况
        if self.is_empty():
            self.head = node
        else:
            node.next = self.head
            self.head.prior = node #node.next.prior = node
            self.head = node
        #插入成功 链表长度自增
        self.size += 1

    #遍历
    def show(self):
        #判空
        if self.is_empty():
            print("链表为空 遍历失败")
        else:
            q = self.head
            while q:
                print("%d "%(q.data),end = " ")
                q = q.next
            print()

    #任意位置插入
    def add_index(self,idex,data):
        #判断插入的位置是否合理
        if idex<1 or idex>self.size+1:
            print("插入失败")
        else:
            #判断插入的位置是否是第一个位置
            if idex == 1:
                self.add_head(data)
            else:
                #创建新的节点
                node = Node(data)
                #找到要插入位置的前一个节点
                q = self.head
                i=1
                while i<idex-1:
                    q = q.next
                    i+=1
                # 判断插入的位置是否是最后一个节点
                if q.next == 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_idex(self,idex):
        #判空  判断位置是否合理：
        if self.is_empty() or idex<1 or idex>self.size:
            print("删除失败")
        else:
            #判断删除的是否是第一个节点
            if idex == 1:
                self.head = self.head.next
                self.head.prior = None
            else:
                #判断删除的是否是最后一节节点
                q = self.head
                i = 1
                while i<idex:
                    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,data):
        #判空
        if self.is_empty():
            print("查询失败")
        else:
            p = self.head
            while p:
                if p.data == data:
                    return True
                p=p.next
            return False


#测试
if __name__ == "__main__":
    #创建一个双向链表
    doubleLink = DoubleLink()

    #头插
    doubleLink.add_head(10)
    doubleLink.add_head(20)
    doubleLink.add_head(30)
    doubleLink.add_head(40)
    doubleLink.add_head(50)

    #遍历
    doubleLink.show()

    #任意位置插入
    doubleLink.add_index(1,33)
    doubleLink.show()
    doubleLink.add_index(3, 999)
    doubleLink.show()
    doubleLink.add_index(8, 1111)
    doubleLink.show()

    #任意位置删除
    doubleLink.del_idex(1)
    doubleLink.show()
    doubleLink.del_idex(4)
    doubleLink.show()
    doubleLink.del_idex(6)
    doubleLink.show()

    if(doubleLink.find_node(40)):
        print("存在")

二、循环链表

2.1 概念

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

分类：单向循环链表、双向循环链表

2.2 单向循环链表的类格式

单向循环链表也就是单向链表的最后一个节点的next域不再为None,而是第一个节点

2.3 操作

1】创建

#封装节点的类
class Node:
    def __init__(self,data):
        self.data = data
        self.next = None

#封装单向循环链表类
class LinkList:
    def __init__(self,node = None):
        self.size = 0
        self.head = node

2】判空

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

3】尾插

#尾插
def add_tail(self,data):
    #创建一个新的节点
    node = Node(data)
    #判空
    if self.is_empty():
        self.head = node
        node.next = node
    else:
        #找到最后一个节点
        q = self.head
        while q.next != self.head:
            q = q.next

        q.next = node
        node.next = self.head
    #链表长度自增
    self.size += 1

4】遍历

#遍历
def show(self):
    #判空
    if self.is_empty():
        print("失败")
    else:
        #两种： 长度遍历   位置遍历（循环结束 多打印一次）
        q = self.head
        while q.next != self.head:
            print("%d"%(q.data),end=" ")
            q = q.next
        print("%d"%(q.data),end=" ")
        print()

5】尾删

#尾删
 def del_tail(self):
     #判空
     if self.is_empty():
         print("删除失败")
     else:
         #判断长度是否为1  是否只有一个节点
         if self.size == 1:
             self.head = None
         else:
             q = self.head
             i=1
             while i<self.size-1:
                 q = q.next
                 i+=1
             q.next = self.head
         #删除成功 链表长度自减
         self.size -=1

全部代码

#封装节点的类
class Node:
    def __init__(self,data):
        self.data = data
        self.next = None

#封装单向循环链表类
class LinkList:
    def __init__(self,node = None):
        self.size = 0
        self.head = node

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

    #尾插
    def add_tail(self,data):
        #创建一个新的节点
        node = Node(data)
        #判空
        if self.is_empty():
            self.head = node
            node.next = node
        else:
            #找到最后一个节点
            q = self.head
            while q.next != self.head:
                q = q.next

            q.next = node
            node.next = self.head
        #链表长度自增
        self.size += 1

    #遍历
    def show(self):
        #判空
        if self.is_empty():
            print("失败")
        else:
            #两种： 长度遍历   位置遍历（循环结束 多打印一次）
            q = self.head
            while q.next != self.head:
                print("%d"%(q.data),end=" ")
                q = q.next
            print("%d"%(q.data),end=" ")
            print()
   #尾删
    def del_tail(self):
        #判空
        if self.is_empty():
            print("删除失败")
        else:
            #判断长度是否为1  是否只有一个节点
            if self.size == 1:
                self.head = None
            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__":
    #创建一个单向循环链表
    linkList = LinkList()

    #尾插
    linkList.add_tail(1)
    linkList.add_tail(2)
    linkList.add_tail(3)
    linkList.add_tail(4)
    linkList.add_tail(5)
    #显示
    linkList.show()

    #尾删
    linkList.del_tail()
    linkList.show()
    linkList.del_tail()
    linkList.show()
    linkList.del_tail()
    linkList.show()
    linkList.del_tail()
    linkList.show()
    linkList.del_tail()
    linkList.show()

三、栈

3.1 概念

栈的概念：操作受限的线性表，对数据的插入和删除操作只能在同一端操作

栈的特点：先进后出（FILO ---->First In Last Out） 、后进先出（LIFO ---->Last In First Out）

栈顶：能够被操作的一端称为栈顶

栈底：不能被操作的一端，称为栈底

种类：顺序栈、链式栈

基本操作：创建栈、判空、入栈、出栈、获取栈顶元素、求栈的大小、遍历栈

3.2 顺序栈

3.2.1 概念

顺序存储的栈 叫顺序栈

3.2.2 顺序栈的组成

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

3.3 栈的操作

  • 创建一个空栈
  • 添加数据
  • 遍历栈
  • 弹出栈顶元素（删除）
  • 返回栈顶元素
  • 判空
  • 栈的大小
#封装一个栈的类
class Stack:
    def __init__(self):
        self.data = [] #使用列表来完成顺序栈

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

    #增加数据
    def push(self,value):
        self.data.insert(0,value)

    #遍历
    def show(self):
        for i in self.data:
            print(i, end=" ")
        print()

    #弹出元素 删除
    def pop(self):
        #self.data.remove(self.data[0])
        #self.data.pop(0)
        del self.data[0]

    #获取栈顶元素
    def first_value(self):
        return self.data[0]

    #返回栈的大小
    def size(self):
        return len(self.data)




#测试
if __name__ == "__main__":
    #创建一个栈
    stack = Stack()

    #增加元素
    stack.push("hello")
    stack.push("world")
    stack.push("hello")
    stack.push("meimei")
    #遍历
    stack.show()

    #删除
    stack.pop()
    # 遍历
    stack.show()

    num = stack.first_value()
    print(num)

    size = stack.size()
    print(size)

标签：node,head,Python,self,day3,链表,数据结构,data,def
From： https://blog.csdn.net/m0_67609958/article/details/144035104

相关文章

  • python实现LBP方法提取图像纹理特征 (附完整源码)
    python实现LBP方法提取图像纹理特征局部二值模式（LBP）是一种用于纹理特征提取的有效方法。下面是一个使用Python实现LBP方法提取图像纹理特征的完整示例代码。我们将使用OpenCV库来处理图像，并使用NumPy来进行数组操作。首先，确保你已经安装了OpenCV库。如果没有安装，可......
  • python实现加密认证通信系统 (附完整源码)
    python实现加密认证通信系统安装依赖完整源码代码解释：运行代码注意事项实现一个简单的加密认证通信系统可以通过使用对称加密（如AES）和消息认证码（如HMAC）来完成。以下是一个使用Python的cryptography库实现的示例，展示了如何建立一个简单的加密认证通信系统......
  • Day39--自定义异常及小结
    Day39--自定义异常及小结自定义异常使用Java内置的异常类可以描述在编程时出现的大部分异常情况。除此之外，用户还可以自定义异常。用户自定义异常类，只需继承Exception类即可。在程序中使用自定义异常类，大体可分为以下几个步骤：创建自定义异常类。在方法中通过throw关键字抛......
  • python 生成图表
    在Python中生成图表，通常会使用matplotlib库，它是Python中最常用的绘图库之一。以下是如何使用matplotlib来生成一些基本图表的示例：安装Matplotlib如果您还没有安装matplotlib，可以使用以下命令安装：pipinstallmatplotlib基本图表1.折线图（LinePlot）importmatplotlib.pyplo......
  • python计算非线性相关的一些笔记
    在Scipy中，相关系数的范围是介于-1到1之间。其中，1表示完全正相关，-1表示完全负相关，0表示无相关关系。因此，相关性最高是1，最低是-1。在计算非线性相关时，样本量的大小对于结果的准确性有重要影响。根据搜索结果，虽然没有一个固定的“最佳”样本量，但是有一些指导性的建议：样本量与p......
  • python如何读取excel的图表
    在Python中读取Excel文件中的图表，你可以使用openpyxl库来处理.xlsx文件。openpyxl是一个用来读写Excel2010xlsx/xlsm/xltx/xltm文件的Python库。以下是使用openpyxl读取Excel文件中图表的基本步骤：安装openpyxl：如果你还没有安装openpyxl，可以通过pip安装：pipinstallopenpyx......
  • python怎么调用js中的函数
    Python调用JS文件中的函数方法如下：1、安装PyExecJS第三方库2、导入库：importexecjs3、调用JS文件中的方法Passwd = execjs.compile(open(r"web.js").read().decode("utf-8")).call('loginHandle'，'steam')语句解析，open后跟所执行的js文件位置，call后第一个单引号引......
  • 利用Python爬取12306网站车次信息
    整体思路：首先利用https://kyfw.12306.cn/otn/resources/js/framework/station_name.js?station_version=1.9053这个网站解析目前国内所有车站代码以及对应的城市名称利用Python对该url进行处理defget_respose(url):try:r=requests.get(url)r.r......
  • Python 类初始化方法中初始化日志后，导致日志被重复打印
    Python类初始化方法中初始化日志后，导致日志被重复打印这个问题通常是由于添加处理器到同一个日志记录器上或使用了全局的日志记录器，从而导致重复的日志记录。以下是一些常见原因以及解决方法：问题原因日志处理器未被正确检查或清理：每次实例化类时，如果给日志记录器添加了新......
  • Python知识点精汇：字典篇精汇！
    目录一、字典是什么二、字典长什么样三、字典的基本操作（1）新增元素（2）删除元素（3）清空元素（4）获取全部键值四、其他（1）字典的遍历（2）定义嵌套字典（3）字典的合并（4）返回指定的键的值，找不到键时返回预设值（5）返回指定的键的值，找不到键时，将该键更新到字典中一、字典是什么字如其名......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99