Fortran递归树实现中的分段错误

Question

我需要在Fortran中为一个项目实现一个树结构,所以我在网上阅读了各种指南,解释了如何做到这一点.但是,我不断收到错误或奇怪的结果.

假设我想构建一个二叉树,每个节点存储一个整数值.我还希望能够将新值插入树中并打印树的节点.所以我写了一个类型"树",它包含一个整数,两个指向子子树的指针和一个我设置为.true的布尔值.如果没有子子树:

module class_tree
implicit none

type tree
    logical :: isleaf
    integer :: value
    type (tree), pointer :: left,right
end type tree

interface new
    module procedure newleaf
end interface

interface insert
    module procedure inserttree
end interface

interface print
    module procedure printtree
end interface

contains

subroutine newleaf(t,n)
    implicit none
    type (tree), intent (OUT) :: t
    integer, intent (IN) :: n

    t % isleaf = .true.
    t % value = n
    nullify (t % left)
    nullify (t % right)
end subroutine newleaf

recursive subroutine inserttree(t,n)
    implicit none
    type (tree), intent (INOUT) :: t
    integer, intent (IN) :: n
    type (tree), target :: tleft,tright

    if (t % isleaf) then
        call newleaf(tleft,n)
        call newleaf(tright,n)

        t % isleaf = .false.
        t % left => tleft
        t % right => tright
    else
        call inserttree(t % left,n)
    endif
end subroutine inserttree

recursive subroutine printtree(t)
    implicit none
    type (tree), intent (IN) :: t

    if (t % isleaf) then
        write(*,*) t % value
    else
        write(*,*) t % value
        call printtree(t % left)
        call printtree(t % right)
    endif
end subroutine printtree
end module class_tree

除非尝试插入叶子,否则插入总是在左子树中完成.在这种情况下,插入到两个子树中以确保节点始终具有0或2个子节点.打印在前缀遍历中完成.

现在,如果我尝试运行以下程序:

program main
use class_tree
implicit none
type (tree) :: t

call new(t,0)
call insert(t,1)
call insert(t,2)
call print(t)
end program main

我得到了所需的输出0 1 2 2 1.但是如果我在"call insert(t,2)"之后添加"call insert(t,3)"并再次运行,输出为0 1 2 0然后我得到一个段错误.

我试着看看插入或打印过程中是否发生了故障,所以我尝试运行:

program main
use class_tree
implicit none
type (tree) :: t

call new(t,0)
call insert(t,1)
call insert(t,2)
write(*,*) 'A'
call insert(t,3)
write(*,*) 'B'
call print(t)
end program main

这使得segfault消失但我得到一个非常奇怪的输出AB 0 1 2673568 6 1566250180.

当在网上搜索类似的错误时,我得到了类似的结果,它说它可能是由于太多的递归调用.但是,对insert(t,3)的调用应该只包含3个递归调用...我还尝试使用带有-g -Wall -pedantic -fbounds-check的gfortran进行编译并使用调试器运行.似乎故障发生在打印子程序中的"if(t%isleaf)"行,但我不知道如何理解它.

编辑:

在评论之后,我-g -fbacktrace -fcheck=all -Wall在gfortran中编译并尝试检查内存的状态.我对此很新,所以我不确定我是否正确使用了我的调试器(gdb).

在三次插入之后和调用之前print,似乎一切都进展顺利:例如,当我输入p t % left % left % right % valuegdb时,我得到了预期的输出(即3).如果我只是键入p t,输出是(.FALSE.,0,x,y),其中x和y是十六进制数字(内存地址,我猜).但是,如果我尝试p t % left,我得到的东西就像指针的"描述":

PTR TO -> (Type tree
logical(kind=4) :: isleaf
integer(kind=4) :: value

由于每个指针指向包含两个指针的树,因此它会重复很多次.我本来期望输出类似于输出p t,但我不知道这是否正常.

我也试图检查内存:例如,如果我型x/4uw t % left,我得到4个字,第2个话似乎对应于isleaf和value,最后2到内存地址.通过遵循这样的内存地址,我设法访问所有节点,我没有发现任何错误.

段错误发生在打印例程中.如果我p t在故障后输入,它说我无法访问0x0地址.这是否意味着当我尝试打印时,我的树会以某种方式被修改？

Answer 1

您遇到问题的原因是,超出范围的变量不再有效.这与Python之类的语言形成对比,其中现有指针的数量是相关的(refcount).

在您的特定情况下,这意味着,在调用newleaf(left, n)和newleaf(right, n)设置的值left和right,RESP,但这些变量得到OUF的范围,因此无效.

更好的方法是在需要时分配每个叶子(第一个叶子除外,因为它已经分配,​​并且在程序结束之前不会超出范围).

recursive subroutine inserttree(t,n)
  implicit none
  type (tree), intent (INOUT) :: t
  integer, intent (IN) :: n

  if (t % isleaf) then
    allocate(t%left)
    allocate(t%right)
    call newleaf(t%left,n)
    call newleaf(t%right,n)

    t % isleaf = .false.
  else
    call inserttree(t % left,n)
  endif
end subroutine inserttree