使用邻接表构造图时 Fortran 中的分段错误

Question

我正在使用邻接表方法创建图形。每个节点都表示为一个指向与其相连的其他节点的节点。以下是我的代码

 program main
 use graphs
 implicit none
 type(node),pointer :: start
 type(node), dimension(:), pointer :: grp
 integer :: n, ios=0, a,b, i

 open(1, file='test6.txt', status='OLD', action='READ')
 read(1,*,iostat=ios) n
 allocate(start)
 allocate(grp(n))
 do, i=1,n
   grp(i)%val=i
 enddo

 do while(ios==0)
  read(1,*, iostat=ios)a,b
  if(ios.NE.0)then
     exit
  endif
  start => grp(a)
  call add(start, b)
  start => grp(b)
  call add(start, a)
 end do
end program main

模块图如下

module graphs
 type node
  integer :: val
  type(node), pointer :: next
 end type node

contains

subroutine add(strt, nxn)
 implicit none
 type(node), pointer :: strt, new_node, lst
 integer :: nxn
 allocate(new_node)
 allocate(lst) 
 lst => strt
 new_node%val = nxn
 new_node%next => NULL()
 do while(associated(lst%next))
   lst => lst%next
 enddo
 lst%next => new_node
end subroutine add
end module graphs

文件test6.txt如下

我收到以下错误

Program received signal SIGSEGV: Segmentation fault - invalid memory
reference

Backtrace for this error:
#0  0x7f786df6bef7 in ???
#1  0x7f786df6b12d in ???
#2  0x7f786dbbc4af in ???
#3  0x401db0 in __graphs_MOD_add
at /home/nav/MS project/new/grph.f90:18
#4  0x400f48 in ???
#5  0x400f85 in ???
#6  0x7f786dba782f in ???
#7  0x400a18 in ???
#8  0xffffffffffffffff in ???
Segmentation fault (core dumped)

以上程序运行对小图很平滑，但对大图不起作用。我无法理解我做错了什么？我正在使用 gfortran 编译器。

Answer 1

在您的代码中没有任何地方将起始 %next 指针设置为空。所以当你来到

do while(associated(lst%next))

lst%next指向的地址未定义。不许问是否关联，因为结果associated() will return 也是undefined。另请参阅此经典资源以获取更多解释 http://www.cs.rpi.edu/~szymansk/OOF90/bugs.html#5

最好的办法是对指针组件进行默认初始化

 type node
  integer :: val
  type(node), pointer :: next =>  null()
 end type node

养成总是将指针组件设置为空的习惯。

使用邻接表构造图时 Fortran 中的分段错误

Segmentation fault in Fortran while constructing graph using adjacency lists

fortran

fortran90