module NumLink                          
  implicit none
  integer, parameter :: N=10    
  ! 聲明制作鏈表的類型
  type :: link
    integer :: num                      ! 儲存數據組
    type(link), pointer :: next         ! 指向下一個環結的指針
  end type link

  type(link), target  :: linking(N) ! 儲存hashing后的數據
  type(link), pointer :: proc      ! 暫時使用的指針

  integer :: Source(N) = (/ 21,53,71,19,61,81,3,17,44,93 /)

contains
  subroutine InitLink()
    integer i
	do i=1,N
	  linking(i)%num = 0
	  nullify(linking(i)%next)
	end do
  end subroutine

! hash函數
  integer function hash(KEY)
    integer KEY
    hash = KEY/10+1
	return
  end function
!
! 把數字經過散列處理后放入鏈表的子程序
!
  subroutine Insert(KEY, INFO)
    integer :: KEY, INFO ! 所要插入的數字及在Source中的位置
    integer :: L         ! hashing 后的結果

    L=hash(KEY)        
    proc=>linking(L) ! 把proc指向類型linking中hash(L)的位置

    ! 移動到鏈表中的最后一個位置
    do while( proc%num /= 0 )
      proc=>proc%next
    end do

    proc%num = INFO
    !配置內存空間給proc%next
    allocate(proc%next)
	proc=>proc%next
    proc%num = 0
	nullify(proc%next)
  end subroutine Insert 
!
! 在鏈表中查找數據的子程序
!
  subroutine Hash_Search( KEY )
    integer :: KEY  ! 要查找的值
    integer :: L    ! 計算hashing后的值

    L=hash(KEY)
    proc=>linking(L)        ! 把proc指向類型linking中hash(L)的位置

    ! 在這一個鏈表中一直向下順序查找到找到為止
    do while( .true. )
	  if ( proc%num==0 ) then
	    write(*,*) "Not found."
		return
	  end if
	  if ( Source(proc%num)==KEY ) then
	    write(*,"('Source(',I2,' )=',I3)") proc%num, KEY
		return
	  end if
	  if ( associated(proc%next) ) proc=>proc%next
    end do
    return
  end subroutine Hash_Search
!
! 輸出鏈表中數據的子程序
!
  subroutine OutputLink()
    integer :: i 
    do i=1,N
      proc=>linking(i)
      write(*,"(1X,I2,':')", advance="NO") i
      do while( associated(proc%next) )
        write(*,"('->',I2)", advance="NO" ) Source(proc%num)
        proc=>proc%next
      end do
      write(*,*)
    end do
  end subroutine OutputLink

end module NumLink
!       
!    哈稀查找法范例
!                  
program HASHING_SEARCH_DEMO
use NumLink
implicit none
  integer :: KEY  ! 記錄所要找的值
  integer :: I    ! 循環記數器

  call InitLink()
  write(*,"('Source=>',10I3)") Source
  do I=1,N
    call Insert( Source(I), I )
  end do
  write(*,*) 'Link List=>'
  call OutputLink()
! 讀入要找的值
  write(*,*) 'Input KEY:'
  read (*,*) KEY
! 調用順序查找的子程序
  call Hash_Search(KEY)
  stop
end program HASHING_SEARCH_DEMO