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。但是如果我添加「呼叫插入（T，3）」後，「呼叫插入（ t，2）「並再次運行，輸出爲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 

它使段錯誤消失，但我得到一個非常奇怪的輸出AB 0 1 2673568 6 1566250180.

當在網上搜索類似的錯誤時，我得到了類似here的結果，它說這可能是由於遞歸調用太多。然而，插入（t，3）的調用應該只包含3次遞歸調用......我也嘗試使用gfortran進行編譯，使用-g -Wall -pedantic -fbounds-check並使用調試器運行。看來故障發生在打印子程序中的「if（t％isleaf）」行，但我不知道如何理解這一點。

編輯：

繼意見，我與-g -fbacktrace -fcheck=all -Wall在gfortran編譯並試圖檢查存儲器的狀態。我很新，所以我不確定我是否正確使用我的調試器（gdb）。

在三次插入之後，在呼叫print之前，看起來一切都很順利：例如，當我在gdb中鍵入p t % left % left % right % value時，我得到期望的輸出（即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