首页 > 其他分享 >【数据结构】双向链表、单向循环链表、双向循环链表、栈、链栈

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

时间：2024-11-25 21:30:33浏览次数：10  
标签：node head self next 链表 循环 双向 print def

目录

一、双向链表

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

注意事项：

二、循环链表

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

注意事项： 

三、双向循环链表

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

函数封装之判空和尾插

双循环链表遍历

双循环链表尾删

完整测试以及结果：

四、栈

顺序栈

顺序栈本质以及组成

顺序栈的操作

链栈

一、双向链表

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

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

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

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

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

未完待续（持续跟新中）

标签：node,head,self,next,链表,循环,双向,print,def
From： https://blog.csdn.net/bananapai/article/details/144035510

相关文章

  • LeetCode24 两两交换链表中的节点
    LeetCode24两两交换链表中的节点题目链接：LeetCode24描述给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。示例输入：head=[1,2,3,4]输出：[2,1,4,3]思路代码classSolution{publicListNodeswapPairs(ListNodehead){ListNodedummy=......
  • dom 元素应用 + for 循环应用
    文章目录元素获取应用getElementById与jquerydom元素的属性dom元素递归循环以及定向查找查找某DOM元素下符合特定条件的所有元素（以查找所有具有特定类名的元素为例）查找某DOM元素下的特定元素（以查找具有特定`id`的元素为例）for循环应用for中break,continue以及......
  • 挑战1000道前端面试题之判断对象是否存在循环引用（15）
    循环引用循环引用是指两个或多个对象之间相互引用，形成一个闭环。这种引用关系会导致垃圾回收机制无法正常工作，因为这些对象始终被认为是“可达”的，即使它们不再被其他部分的代码使用。具体实现functionisCyclic(obj){letseenObjects=newWeakSet();function......
  • 异步与资源调度 以浏览器事件循环为例
    初次发布于我的个人文档参考:chromiun官方文档w3c官方文档针对一个异步的程序应该如何对它进行资源的调度呢？本文以浏览器为典型范例进行简单介绍。1.查看浏览器的多进程图景打开任意一个浏览器这里以edge为例。然后打开Windows的任务管理器，你看到的可能是这样：事实上，在edg......
  • 206. 反转链表
    题目自己一开始的思路是对链表的每个节点的val进行更改，然后就没有然后了……没写出来然后看了卡哥的讲解感触最深的点是卡哥是让结点间的指向发生改变（换句话说，改变了节点的next），然后顺着这个思路卡哥给出了两个方法：双指针法和递归法。特别要给卡哥的视频讲解点个大大的赞，所有......
  • 数据结构第二章双链表的相关操作
    带头结点的双链表的实现以及一系列操作#include<stdio.h>#include<stdlib.h>//定义双链表节点结构体typedefstructDNode{intdata;structDNode*prior;structDNode*next;}DNode,*DLinkList;//初始化双链表voidInitList(DLinkList&L){......
  • LeetCode19 删除链表的倒数第 N 个结点
    LeetCode19删除链表的倒数第N个结点题目链接：LeetCode19描述给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。示例输入：head=[1,2,3,4,5],n=2输出：[1,2,3,5]思路定义fast指针和slow指针，初始值为虚拟头结点fast首先走n+1步fast和slow同时移动，直......
  • 【剑指Offer刷题系列】两个单链表相交的起始节点
    问题描述给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。图示两个链表在节点c1开始相交：题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须保持其原始结构。自定义评测：......
  • 自然语言处理中的循环神经网络：全面解析与代码实现
    目录引言循环神经网络基础工作原理变体RNN在NLP中的应用语言模型机器翻译文本分类语音识别优势与挑战优势挑战结论引言自然语言处理（NLP）是人工智能领域中的一个重要分支，它致力于使计算机能够理解、解释和生成人类语言。在NLP的众多技术中，循环神经网络（RNN）因其......
  • 用于自然语言处理的循环神经网络RNN
    前一篇：《人工智能模型学习到的知识是怎样的一种存在？》序言：在人工智能领域，卷积神经网络（CNN）备受瞩目，但神经网络的种类远不止于此。实际上，不同类型的神经网络各有其独特的应用场景。在接下来的几节中，我将带大家走近循环神经网络（RNN），深入了解其原理及其在处理人类自然语言中的改进与......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99