Fortran链表insert操作如何实现按序插入且仅传整数自动分配节点

核心修改说明 #

• 调整insert子例程接口：入参从节点指针改为整数，节点内存分配逻辑迁移到insert内部自动完成，完全符合要求的调用形式
• 重写insert插入逻辑：实现升序按值插入，插入完成后链表天然有序，无需额外排序步骤
• 精简主程序代码：删除手动分配节点的冗余代码，移除原代码中不存在的sort函数调用

修改后完整代码 #

program LinkedList
  implicit none

  type node
     integer :: value
     type(node),pointer :: next
  end type node

  type list
     type(node),pointer :: head
  end type list
  
  type(list) :: the_list

  ! 初始化链表头为空
  nullify(the_list%head)

  ! 按要求的形式调用insert
  call insert(the_list,1)
  call insert(the_list,5)
  call insert(the_list,3)
  ! 插入时已自动排序，直接打印即可
  call print(the_list)

contains
  
  subroutine insert(the_list, val)
    implicit none
    ! 入参修改为链表和待插入的整数值
    type(list),intent(inout) :: the_list
    integer, intent(in) :: val
    ! 本地变量
    type(node),pointer :: new_node, current, previous

    ! 内部自动分配新节点并赋值
    allocate(new_node)
    new_node%value = val
    nullify(new_node%next)

    ! 空链表直接插在头部
    if (.not. associated(the_list%head)) then
       the_list%head => new_node
       return
    end if

    ! 新节点值比头节点小，插在最前面
    if (val < the_list%head%value) then
       new_node%next => the_list%head
       the_list%head => new_node
       return
    end if

    ! 遍历找到合适的插入位置
    previous => the_list%head
    current => the_list%head%next
    do while (associated(current))
       if (val < current%value) exit
       previous => current
       current => current%next
    end do

    ! 插入节点
    previous%next => new_node
    new_node%next => current
    
  end subroutine insert
  
  
  integer function length(the_list)
    implicit none
    type(list),intent(in) :: the_list
    type(node),pointer :: current

    length = 0
    if (associated(the_list%head)) then
       current => the_list%head       
       do
          length = length+1
          if (.not. associated(current%next)) exit
          current => current%next
       end do
    end if
  end function length

  subroutine print(the_list)
    implicit none
    type(list),intent(in) :: the_list
    type(node),pointer :: current

    write(*,'("List: [ ")',advance="no")
    if (associated(the_list%head)) then
       current => the_list%head
       do while (associated(current))
          write(*,'(i0", ")',advance="no") current%value
          current => current%next
       end do
    end if
    write(*,'("]")')

  end subroutine print
  
end Program LinkedList

运行输出 #

执行后将输出有序链表结果：

List: [ 1, 3, 5, ]

内容的提问来源于stack exchange，提问作者Hannah Marques