第11回：ポインタとリスト構造1（12/10） - ax

木村拓馬
FORTRAN プログラミング
–第 11・12 回 ポインタとリスト構造–
木村拓馬
2014 年 12 月 16 日 21:43
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
1/25
木村拓馬
ポインタ
.
ポインタ
.
Fortran90 で新しく導入された機能
.
.
.
データポインタ： 他の変数を指す変数
（手続ポインタ： 他の手続（関数・サブルーチン）を指す手続）
ここではデータポインタのみ扱う .
データポインタ
.
他の変数と結合する（指す）と，その変数の別名のように使える
配列や構造体，それらの一部も指せる
.
1
構造体と組み合わせてリスト構造を作ったり（次回）
2.4.6 ポインタ [1] データポインタ (data pointer) は，POINTER 属性をもつデータ要素とする。手続ポインタ (procedure pointer) は，POINTER 属性をもつ
手続要素とする。ポインタ (pointer) は，データポインタ 又は 手続ポインタのいずれかとする。ポインタは，ポインタ代入（7.4.2 参照）によって 指示先 (target)
と結合されて 指示状態 (pointer associated) になる。データポインタは，割付け（6.3.1 参照）によって指示先と結合されて指示状態になってもよい。ポインタ
は，NULLIFY 文の実行の結果として，空状態のポインタとのポインタ代入の結果として，暗黙的初期値指定によって，又は 明示的初期値指定によって 空状態
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
2/25
木村拓馬
.
ポインタの使い方
.
ポインタの宣言
.
. 型，POINTER :: ポインタ変数名または配列名，…
.
例） integer, pointer :: p
.
例） integer, pointer :: p(:) ⇐ 大きさは無指定で宣言する．
TARGET 属性を指定した変数の宣言
.
. 型，TARGET :: 変数名
.
例） integer, target :: a
.
例） integer, target :: a(3) ⇐ 大きさを指定してもよい．
.
ポインタと TARGET 属性をもつ変数との結合
.
. ポインタ変数名 => TARGET 属性をもつ変数名（またはポインタ変数名）
.
.例） p => a
ポインタは宣言しただけではどこも指してない
ポインタが指せるのは，
同じデータ型で，
TARGET 属性をもつ変数，ポインタ
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
3/25
木村拓馬
.
ポインタの宣言，結合 (ex11.1.f90) ..
.
1
2
3
4
5
6
7
8
9
10
11
12
13
14.
Download
program pointer1
implicit none
!ポインタの宣言
integer, pointer :: p
!TARGET 属性を指定した変数の宣言
integer, target :: a
!ポインタと TARGET 属性をもつ変数との結合
p => a
!ポインタは結合した変数の別名として使える
p = 10
write(*,*) a
p = p + 10
write(*,*) a
end program pointer1
.
実行すると（p の値を変えると a の値が変わる）
.
10
. 20
ポインタは他の変数と結合する（指す）と，その変数の別名のようにして代入文や式に
書くことができる．
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
4/25
木村拓馬
.
例：結合しなおすことができる (ex11.2.f90) ..
.
1
2
3
4
5
6
7
8
9
10
11
12.
Download
program pointer2
implicit none
integer, pointer :: p1, p2
integer, target :: a1, a2
p1 => a1; p2 => a2
p1 = 10; p2 = 20
write(*,*) a1,a2,p1,p2
p2 => a1
p1 = p1+1; p2 = p2+2
write(*,*) a1,a2,p1,p2
end program pointer2
⇓
.
実行すると（a1,a2,p1,p2 の値が変わる）
.
10 20 10 20
. 13 20 13 13
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
5/25
木村拓馬
ポインタは配列を扱うこともできる．ただし，
配列へのポインタであることを明示的に宣言すること（p(:)）．
大きさは無指定で宣言すること（(:)）．
.
例：配列を指すポインタ (ex11.3.f90) .. Download
.
1
2
3
4
5
6
7
8
9
10.
program pointer3
implicit none
integer, pointer :: p(:)
integer, target :: a(3)
p => a
p(1) = 1
p(2) = 2
p(3) = 3
write(*,*) a
end program pointer3
.
実行すると
.
.1 2 3
ポインタ配列の大きさは，結合した配列の大きさ.
ポインタ配列の各要素は，結合した配列の各要素を指す．
2
データポインタが配列であるときは，次元数は宣言されるが，寸法はそのポインタが指示先と結合した時に決まる。[1]
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
6/25
木村拓馬
ポインタは構造体を扱うこともできる．
.
例：構造体を指すポインタ (ex11.4.f90) .. Download
.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19.
program pointer4
implicit none
type :: record
character(8) :: id, fname, lname
integer :: score(3)
end type record
character(8), pointer :: p1,p2,p3
integer, pointer :: p4(:)
type(record), pointer :: p
type(record), target :: a
p => a
p1 => a%ID
p2 => a%fname
p3 => a%lname
p4 => a%score
a=record(’1W129999’,’Kimura’,’Takuma’,(/90,100,0/))
write(*,*) p%id, ’,’, p%fname, ’,’, p%lname, ’,’, p%score
write(*,*) p1,
’,’, p2,
’,’, p3,
’,’, p4
end program pointer4
.
実行すると
.
1W129999,Kimura
. 1W129999,Kimura
,Takuma
,Takuma
, 90 100 0
, 90 100 0
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
7/25
木村拓馬
ポインタはポインタと結合できる．
.
例：ポインタを指すポインタ (ex11.5.f90) .. Download
.
1
program pointer5
2
implicit none
3
integer, pointer :: p1, p2
4
integer, target :: a
5
p1 => a
6
p2 => p1
7
p2 = 10
8
write(*,*) a
9. end program pointer5
.
実行すると（p2 の値を変えると a の値が変わる）
.
. 10
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
8/25
木村拓馬
ALLOCATE 文にポインタを入れると，適当な無名の領域と結合する．
このとき，値は不定（g95 ではゼロ）.
ポインタを宣言するときは， ALLOCATABLE 属性の指定は必要ない．
DEALLOCATE 文でポインタが指す領域を解放．
ポインタは空の状態になり，参照できなくなる．
.
例：結合しなおすことができる (ex11.6.f90) .. Download
.
1
program pointer6
2
integer, pointer :: p, q(:)
3
allocate(p, q(10))
4
write(*,*) p, ’/’, q
5
p=1
6
q=2
7
write(*,*) p, ’/’, q
8
deallocate(p,q)
9
!
write(*,*) p !実行するとここでセグメントエラー
10. end program pointer6
.
実行すると（ALLOCATE すれば普通の変数として使用できる）
.
0 / 0 0 0 0 0 0 0 0 0 0
.1 / 2 2 2 2 2 2 2 2 2 2
3
空状態のポインタは，指示先と結合していない（16.4.2 参照）。結合していないポインタは，引用も確定もしてはならない。[1]
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
9/25
木村拓馬
.
ポインタの結合状態を解除するには
.
. NULLIFY(ポインタ変数名)
ポインタの結合状態を調べるには
.
. ASSOCIATE(ポインタ [, 変数名])
.
.
例：結合状態を調べる／結合状態を解除 (ex11.7.f90) ..
.
1
2
3
4
5
6
7
8
9
10
11
12.
4
Download
program pointer7
implicit none
integer, pointer :: p1,p2
integer, target :: a
write(*,*) associated(p1)
p1 => a
write(*,*) associated(p1)
p2 => a
write(*,*) associated(p1,a), associated(p2,a)
nullify(p1)
write(*,*) associated(p1,a), associated(p2,a)
end program pointer7
.
実行すると
.
F
T
T T
.F T
NULLIFY 文（6.3.2 参照）は，指示先との結合を解除してポインタを空状態にする。ポインタが不定の結合状態をもたない限り，そのポインタが結合されてい
るか否かは，組込み関数 ASSOCIATED（13.7.13 参照）によって知ることができる。[1]
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
10/25
.
演習 11.1（pr11.1.f90）
.
データを値の大きい順に並べ替えるプログラムを作成しよう．
木村拓馬
データは，通し番号（3 文字の文字列）と整数値が n 組．
出力は，並べ替えられた通し番号と整数値．
構造体を利用すること（副プログラムやモジュールは使わなくてもよい）．
派生型のポインタを ALLOCATE してデータを入力・並び替えすること
（副プログラムやモジュールは使わなくてもよい）．
.
.
データの例
出力の例
.
.
ID, VALUE
d01, 41
d04, 94
d02,
6
d03, 42
d03, 42
d01, 41
d04, 94
d05, 20
d05, 20
6
. d02,
.
.
.
選択ソート
.
1) データ x1 , x2 , · · · , xn の中での最大値を探し， x1 と入れ替える．
2) データ
x2 , x3 , · · · , xn の中での最大値を探し， x2 と入れ替える
.
.
..
n) データ xn−1 , xn の大きい方を xn−1 と入れ替える．
5 ポインタを使う必要は全く無いが，リストの並び替え（次回）の練習のため．
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
11/25
木村拓馬
リスト構造
.
リスト構造
.
データ部とポインタ部からなる構造体を鎖状にポインタで連結するデータ構造
.
単方向リスト
双方向リスト
循環リスト
単方向リスト
双方向リスト
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
12/25
木村拓馬
リスト構造
.
リスト構造
.
データ部とポインタ部からなる構造体を鎖状にポインタで連結するデータ構造
.
単方向リスト
双方向リスト
循環リスト
循環リスト（単方向）
循環リスト（双方向）
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
13/25
木村拓馬
.
リスト構造と配列の違い
.
リスト構造
利点 ポインタを繋ぎなおすだけでデータを挿入・削除できる．
欠点 データの参照に時間がかかる．
（ポインタをたどり順番に捜査，ランダムアクセスが出来ない)
配列
利点 データの参照が早い．ランダムアクセスができる．
.
欠点 データの挿入・削除の際，データを格納しなおす手間がかかる．
単方向リストにおけるデータの削除と挿入
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
14/25
木村拓馬
自己参照構造体
リスト構造の，
「データ部とポインタ部からなる構造体」の例．
.
type record
integer :: dat
type(record), pointer :: next
end type record
.
例のように，
「自分自身と同じ型（構造体）のポインタを構成要素にもつ構造体」を
「自己参照構造体」という．
6 派生型は，ポインタとして定義された成分を一つ以上もってもよい。その成分が同じ派生型の実体へのポインタであってもよい。この“ 再帰的 ”なデータ定
ポインタ部が構造体を全て指せるので，リストをつくるとき利用される，
義によって，リスト，木 及び グラフのような動的データ構造を構築することができる [1]
6 派生型は，ポインタとして定義された成分を一つ以上もってもよい。その成分が同じ派生型の実体へのポインタであってもよい。この“ 再帰的 ”なデータ定
義によって，リスト，木 及び グラフのような動的データ構造を構築することができる [1]
0
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
15/25
木村拓馬
.
リスト構造のつくりかた１
.
1. 構造体に next という自分自身を構成要素にもつポインタを追加し，
リストの先頭を表すポインタ (root) を設定．
. 1 番目のデータを入力．
2 番目のデータの記憶領域を確保（allocate）．
1 番目のデータの next と 2 番目のデータを結合（=>）．
2 番目のデータの next はどことも結合していないものとする（nullify）．
3. 2 番目のデータを入力．
2
3 番目のデータの記憶領域を確保（allocate）．
2 番目のデータの next と 3 番目のデータを結合（=>）．
3 番目のデータの next はどことも結合していないものとする（nullify）．
.
. 以下同様．
4
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
16/25
木村拓馬
.
リスト構造のつくりかた２（先頭にダミーノードを置くと，先頭の削除・挿入に便利かも）
.
1. 構造体に next という自分自身を構成要素にもつポインタを追加し，
リストの先頭を指すだけのポインタ (root) を設定．
. 1 番目のデータの記憶領域を確保し，root%next と結合（allocate(root%next)）
1 番目のデータの next はどことも結合していないものとする（nullify）．
1 番目のデータを入力．
3. 2 番目のデータの記憶領域を確保し，1 番目のデータの next と結合
2
2 番目のデータの next はどことも結合していないものとする．
2 番目のデータを入力．
.
. 以下同様．
4
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
17/25
木村拓馬
（例）ex12.1.f90
.. Download
root はリストの最初を表
す，work は作業ポインタ
リストの最初を表すポイン
タを設定．
データを入力
構造体の記憶領域を確保し
next と結合．
新しい構造体の next はど
ことも結合していないもの
とする
.
リスト構造を作る例（ex12.1.f90）前半
.
! 例: リスト構造. 単方向リスト
program pointer_list
implicit none
type record
integer :: dat
type(record), pointer :: next
end type record
type(record), pointer :: root, work
integer :: newdata
!ポインタ root%next は最初のデータを指す
allocate(root, root%next)
nullify(root%next%next)
!リストを作る
work => root%next
write(*,*)’ 数値 (integer) を read，非負値ならばリストに追加，負値ならば exit’
do while(.true.)
read(*,*) newdata
if(newdata >= 0) then
work%dat=newdata
allocate(work%next)
work=>work%next
nullify(work%next)
else
write(*,*)’ 負値なので exit’
exit
end if
. end do
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
18/25
木村拓馬
.
リスト構造を作る例（ex12.1.f90）後半
.
作業ポインタをリストの最
初と結合．
作業ポインタのデータ部を
write し，作業ポインタを
next と結合．
allocate したら deallocate
しないと警告が出る．
!リストを表示
write(*,*)’ リストを表示’
work => root%next
do while(associated(work%next))
write(*,fmt=’(i5,",")’,advance=’no’) work%dat
work=>work%next
end do
write(*,*)
!リストを解放
work => root
do while(associated(work%next))
root => work
work=>work%next
deallocate(root)
end do
deallocate(work)
end
. program pointer_list
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
19/25
木村拓馬
.
例：削除と挿入 (ex12.2.f90 の一部) ..
.
Download
!リストを挿入
work => root
write(*,*) ’ リストを挿入\n 何番目に挿入？(’,1,’-’,n,’)-->’
read(*,*) m
allocate(temp)
do i=1,m-1
work=>work%next
end do
temp%next=>work%next
work%next=>temp
write(*,*) ’ データ（integer）を入力-->’
read(*,*) temp%dat
n=n+1
.
⇒
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
⇒
20/25
木村拓馬
.
例：削除と挿入 (ex12.2.f90 の一部) ..
.
⇓
Download
!リストを削除
work => root
write(*,*) ’ リストを削除’
write(*,*) ’ 何番目を削除?(’,1,’-’,n,’)-->’
read(*,*) m
do i=1,m-1
work=>work%next
end do
temp=>work%next
work%next=>work%next%next
deallocate(temp)
n=n-1
.
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
⇓
21/25
木村拓馬
.
演習 12.1（pr12.1.f90）
.
p.18-21 の例を書き換えて，入力したデータを値の大きい順に並べ替えるプログラムを
作成しよう．
入力するデータは，通し番号（3 文字の文字列）と整数値が n 組．
出力は，並べ替えられた通し番号と整数値．
.
構造体とポインタを利用すること（自己参照構造体によるリスト構造）．
.
.
データの例
出力の例
.
.
ID, VALUE
d01, 41
d04, 94
d02,
6
d03, 42
d03, 42
d01, 41
d04, 94
d05, 20
d05, 20
6
. d02,
.
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
22/25
木村拓馬
参考文献
[1] JIS X 3001-1:2009 (プログラム言語 Fortran – 第 1 部:基底言語)
「“ 再帰的 ”な型の定義」（自己参照構造体），線形リストの例が少し
附属書 C に，
だけ掲載されています．
[2] 戸川隼人: 「ザ・Fortran90/95」, サイエンス社 (1999)
[3] Les Hancock, Morris Krieger, Saba Zamir (倉骨彰, 三浦明美訳): C 言語入門
THE C Primer, アスキー出版局（1984）
FORTRAN で自己参照構造体・リスト構造を扱っている書籍が手元に無かったので，
C 言語の入門書にある内容を移植しました．
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
23/25
木村拓馬
Appendix
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
24/25
木村拓馬
.
演習 11.2（pr11.2.f90）
.
売上表を出力するプログラムを以下の仕様に従って作成してみよう．
売上データは店舗 ID（101 からの通し番号とする），店舗名（20 文字），売上金額の
三項目とし，構造体を用いること．
売上データはファイルから読み込むようにすること．なお，ファイルの 1 行目には総
店舗数が書かれているものとする．
出力は「店舗 ID 順」，
「売上金額の多い順」の 2 種類の並び替えを画面に表示すること．
今回は副プログラムやモジュールを使用しないこと．
.
.
pr11.2data.txt
出力の例
.
.
ID
3
| 101 | aaa
101
aaa
1000
| 102 | bbb
102
bbb
2000
| 103 | ccc
103
ccc
3000
.
KINGAKU
| 103 | ccc
| 102 | bbb
. | 101 | aaa
.
.
選択ソート
.
|
|
|
1000 |
2000 |
3000 |
|
|
|
3000 |
2000 |
1000 |
1) データ x1 , x2 , · · · , xn の中での最大値を探し， x1 と入れ替える．
FORTRAN プログラミング,–第 11・12 回 ポインタとリスト構造– ( 2014 年 12 月 16 日 21:43 )
25/25