时间戳

首页 > 解决方案 > 如何在 Julia 中实现 SingleLinkedList

julia - 如何在 Julia 中实现 SingleLinkedList

问题描述

我正在学习 TAD，但是我不太了解语法，这就是为什么创建单个列表对我来说太难了，但我了解它是如何工作的，例如 TAD，请有人可以告诉我如何实现这个TAD（链接列表），带有基本说明并对其进行描述

abstract type AbstractList{T} end
abstract type AbstractNode{T} end

mutable struct Nodo{T} <: AbstractNode{T}
    value ::T
    next ::Nodo{T}
    Nodo{T}() where T =(x=new();x;x.next=x)
    Nodo{T}(v,n) where T =new(v,n)
end

mutable struct LList{T} <: AbstractList{T}
    first ::Nodo{T}
    LList{T}() where T =new(Nodo{T}())
end

Lista=LList;

function Append(lista,value)
    current=Nodo(value,new(Nodo()))
    if Lista.size==0
        lista.head=current
    else
        MyNode=Lista.first;
        while MyNode.next!=nothing
            MyNode=MyNode.next;
        MyNode.next=current;
        end
    end
    Lista.size+=1
end

Append(Lista,2)

我正在尝试这个，但我不知道为什么它不起作用，我很困惑，因为我阅读了很多关于我使用的指令的帖子，但我根本不理解Nodo{T}() where T =(x=new();x;x.next=x)这个指令，我需要帮助。

标签： julia

解决方案

您的代码中有多种概念，因此为了帮助您，我将使用其中一个来向您展示如何实现您的链表。这是代码：

abstract type AbstractList{T} end
abstract type AbstractNode{T} end

mutable struct Nodo{T} <: AbstractNode{T}
    value::T
    next::Union{Nodo{T}, Nothing}
end

mutable struct LList{T} <: AbstractList{T}
    head::Union{Nodo{T}, Nothing}
    LList{T}() where T = new{T}(nothing)
end

function Base.push!(lista::LList, value)
    new_nodo = Nodo(value, nothing)
    if isnothing(lista.head)
        lista.head = new_nodo
    else    
        current_nodo = lista.head
        while !isnothing(current_nodo.next)
            current_nodo = current_nodo.next
        end
        current_nodo.next = new_nodo
    end
    return lista
end

这就是你可以使用它的方式：

julia> lista=LList{Int}()
LList{Int64}(nothing)

julia> push!(lista, 1)
LList{Int64}(Nodo{Int64}(1, nothing))

julia> push!(lista, 2)
LList{Int64}(Nodo{Int64}(1, Nodo{Int64}(2, nothing)))

julia> push!(lista, 3)
LList{Int64}(Nodo{Int64}(1, Nodo{Int64}(2, Nodo{Int64}(3, nothing))))

一些评论：

  • 我Union用来表明一个对象可以不包含引用（Nothing）或对下一个对象的某些引用（Nodo{T}）
  • 在LList{T}() where T = new{T}(nothing)我们只定义一个内部构造函数中，因为它不带参数，我使用new{T}它仅在内部构造函数中可用来创建一个LList{T}对象实例，其值设置为nothing（因为它还没有节点）
  • 我使用Base.push!它是因为这是将项目添加到集合中的函数的标准名称；Base.需要向标准函数添加方法；因此，后来我写信lista::LList以确保此方法特定于您的LList{T}类型
  • nothing正如您在代码中看到的那样，不需要“虚拟”节点（就像您的代码中存在的那样），因为您只需使用value跟踪列表的结尾

我希望从这一点开始，您将能够向您的LList对象添加其他方法。

推荐阅读