リスト構造

Fortranでリスト構造を作ることになってしまいました。
リストに要素を追加したり、途中のデータを削除することはできたのですが、途中にデータを挿入することができません。
まだfortranバリバリ現役で打っている方、ご教授お願いします。
以下は参考です。

type element
　　　integer::ele
　　　type(element),pointer::next1
end type element
type(element),pointer::root1,p1,tmp_p
allocate(root1)
nullify(root1%next1)
p1 => root1

do i=1,n
　　p1%ele = a(i) !配列Aをリストへ
　　allocate(p1%next1)
　　p1 => p1%next1
　　nullify(p1%next1)
enddo
p1 => root1

print_list1:do !表示
　　if(associated(p1%next1))then
write(*,*)p1%ele
　　　　　p1 => p1%next1
　　else
exit print_list1
endif
enddo print_list1
p1 => root1

free_list1:do !解放
if(associated(p1%next1))then
root1 => p1
p1 => p1%next1
deallocate(root1)
else
exit free_list1
endif
enddo free_list1

C------ちなみに削除は
delete_list:do
　　if(associated(p1%next1))then
if(p1%ele .eq. 0)then !例えば0の要素を削除
　　　tmp_p => p1%next1
　　　nullify(p1%next1)
deallocate(p1%next1)
p1 = tmp_p
else
p1 => p1%next1
endif
else
exit delete_list
endif
enddo delete_list
p1 => root1

No.1 ベストアンサー 回答者： chie65536 回答日時： 2006/04/13 16:40

単方向リストの場合「追加」は「末尾への挿入と考え、挿入の特殊ケース」としてコーディングすべきです。

・リストの先頭を指す変数root1を持つ。この変数がnullの場合はリストが空だとして扱う

・リストの項目のnext1メンバは「次はどれか」を指す。このメンバがnullの場合は、次は無し、つまり末尾として扱う

・先頭の削除の方法
　・root1がnullの場合、リストが空なので何もしない。
　・root1が指すリスト項目のnext1が指す値を一時変数tmp_pに代入して保存する
　・次に、root1が指すリスト項目を開放する
　・次に、tmp_pをroot1に代入する。もしこの時、tmp_pがnullであった場合はroot1もnullになるが、root1がnullの場合はリストが空であると扱うので問題なし

・途中または末尾を削除する方法
　・まず、削除したい項目の１つ手前を見付ける
　・削除したい項目のnext1メンバを、１つ手前の項目のnext1メンバに代入する。この時、削除したい項目のnext1メンバがnullだったら、１つ手前の項目のnext1メンバもnullになるが、これは末尾を削除して、１つ手前が末尾になると言う事なので問題なし
　・次に、削除したい項目を開放する

・先頭への挿入
　・リスト項目を確保し、eleメンバに値を代入
　・確保したリスト項目のnext1メンバにroot1の値を代入する。この時、root1がnullだったらnext1もnullになるが、それは空のリストに先頭かつ末尾の項目を追加する事なので問題なし
　・次に、たった今確保したリスト項目は先頭なので、root1がそれを指すようにroot1を更新する

・途中または末尾への挿入
　・リスト項目を確保し、eleメンバに値を代入
　・まず、挿入したい項目の１つ手前を見付ける。末尾に挿入する場合は末尾を見付けるに等しい
　・１つ手前のnext1メンバの値を、確保したリストのnext1メンバに代入する。１つ手前のnext1メンバがnullだったら確保したリストのnext1メンバもnullになるが、それは末尾に追加する場合なので問題なし
　・次に、１つ手前のnext1メンバが今確保した項目を指すように、１つ手前のnext1メンバを更新する

なお、挿入でも削除でも「１つ手前を見付ける」と言う処理が必要なので、リストが数万件にもなる場合は「next1が１つ次を指している」のと同様に「back1が１つ手前をさしている」と言うメンバを足すと、１つ手前を見付ける処理を高速化出来ます。但し、リストの挿入と削除でback1メンバとnext1メンバの両方を処理しないとならず、アルゴリズムが複雑になります。

この回答へのお礼

お礼が遅れて申しわけありません。
でもやっとできました!
参考を使って説明してくれたので分かり易かったです。
ありがとうございます。

お礼日時：2006/04/20 20:04