VBでリスト構造を実現するには？

質問

DTDとHTMLのパーサを作ろうと思い、データを解析して配列に入れようとしていたのですが、配列じゃなくてリスト構造で実現しろというお達しをうけて非常に困っています。
そもそもVBでリスト構造って実現できるんでしょうか？実現できるのであればその方法を教えていただきたいと思っています。

回答No.7

ARC · ベストアンサー

>１：一度未使用リストに追加するという段階を踏むのはどうしてでしょうか？

Cでやるように、簡単にメモリの開放が行えないからです。
配列を使ったリスト構造ですので、リストから削除する操作を行った場合でも、削除された要素はまだ配列の中に含まれます。
その後、リストに再度、追加操作を行ったときには、出来れば先ほど削除した要素を再利用したいですよね。

未使用リストを使わない場合でしたら、配列のどの要素が今は使われていて、どの要素が既に開放されているのかを知るのが難しくなります。

配列に削除フラグを持たすっていうパターンも考えられますが、その場合は、最初の削除済み要素が見つかるまで、配列の始点から順々に、ずずーーっと探していかなくてはなりません。

それに対して、空き要素も同じくリスト構造にしておけば、削除済みフラグも要りませんし、空き要素の探索も、先の例のようにすごくシンプルに実装できます。

＞２：この配列の方法以外でもいいのですが、リスト構造の中に更にリスト構造を作る方法ってあるでしょうか？

リスト構造をクラスの形で作成します。
クラス名を「CDolbyList」とでもして、
Add
Remove
MoveNext
などもメソッドを実装してやります。

クラスの内部でデータを保持する構造体の方は
Type typHoge
　　sData　　as Valiant
　　lPrev　　as Long
　　lNext　　as Long
End Type

ってな感じですね。

あとは、 CDolbyListをNewして、別のCDolbyListにAddしてやればいいです。

もしくは、親リストと子リストを別々のクラスにして、
親リストの構造体の方を

Type typHoge
　　sData　　as C子リスト
　　lPrev　　as Long
　　lNext　　as Long
End Type
ってな感じで作ってやってもいいかもしれませんね。
(多分こっちの方がパフォーマンスは良くなる。)

お礼

PCが壊れて、しばらくネットに接続できない状態だったのですが、ようやく修理から戻ってきました。お返事遅れて申し訳ありません。

本当に丁寧なご回答どうもありがとうございました。
VBについてはほとんどなにもわからない私でも、わかりやすく説明していただいたおかげでなんとか目処がたつかな、という気になってきました。
がんばってVBを使ってみようと思います。

回答No.6

ARC

１：＞Hoge(2)のNextを見ます。EOF（つまり3）であれば
というのは「未使用リストのBOFを見る」という意味合いの処理でしょうか？

未使用リストのBOF(Before Of File)の次の要素がEOF(End Of File)かどうかを調べるっていうことです。
頭の直後が尻尾なら、胴体が空っぽ… (汗

IF Hoge(2).Next = 3 then
　　配列を拡張して、未使用リストにデータを追加してやります。
END IF

>というのは、追加されるもの自体が末尾になるのではなくて、末尾の一つ前の要素になるということ？

そういうことです。
実際のデータは、必ずBOF(頭)とEOF(尻尾)の間に存在します。
このような構造にしていると、様々なメリットが得られます。

まず、MoveNextとか、MovePreviousとかの処理を実装する際、一々その先頭/末尾かどうかのチェックをしなくてすみます。

それから、カレントレコードがEOFか否かを示すプロパティ*1を一つつけ加えるだけで、呼び出し元から以下のような感じでロジックが組めるようになります。

List.MoveFirst 'カレントレコードをHoge(0).Nextが示す場所に設定する。

Do Until List.EOF
　　処理を記述
　　List.MoveNext 'カレントレコードをカレントレコード.Nextが示す場所に設定する。
Loop

*1
Property Get EOF() As Boolean
　　EOF=(カレントレコード=1)
End Property

ってな感じです。
どうです？イメージがつかめましたか？

補足

回答、ありがとうございます！
ええと、カレントレコードがEOFになるまでループ、その間中はカレントレコードに対し処理を行い、カレントレコードを１進めるということですよね。
最初、Do～以降の処理が、MoveFirstメソッドの実装をしているものだと勘違いしてしまい、１０分ほど思いっきり悩んでしまいました（笑）

確かにそういう約束事（BOFとEOFの間に実際のデータがある）というのがあると処理がすごく綺麗になりますね。

ええと、もう二点ほどよろしいでしょうか。

１：一度未使用リストに追加するという段階を踏むのはどうしてでしょうか？
「ここがミソ」のはずなのに、全然わかってません・・・・・・（汗）

２：この配列の方法以外でもいいのですが、リスト構造の中に更にリスト構造を作る方法ってあるでしょうか？

HTMLのツリー構造をサーチする順番などを考えているうちに、リスト構造の中にリスト構造が作れればだいぶ楽になりそうだという風に思ったので・・・・・・。

回答No.5

ARC

ちゃい。
× 1:Hoge(3)のNextを見ます。EOFであれば、

○ 1:Hoge(2)のNextを見ます。EOF(つまり「3」)であれば、

でした～

回答No.4

ARC

続きです。
その２に関しては、むか～し、遊びで作ったことがありますので、そのときのやり方を紹介します。
双方向の線形リストの例です。

まず、最初に配列に4要素を追加します。

'リストの先頭(BOF)です。
Hoge(0).Prev=-2147483648#
Hoge(0).Next=1

'リストの末尾(EOF)です。
Hoge(1).Prev=0
Hoge(1).Next=2147483647

'未使用リストのBOF
Hoge(2).Prev=-2147483648#
Hoge(2).Next=3

'未使用リストのEOF
Hoge(3).Prev=2
Hoge(3).Next=2147483647

つまり、一つの配列の中に二つのリスト構造が同居しているわけです。（ここがミソ）

配列にデータを追加するときは、未使用リストから1要素減らし、それをリストに挿入します。
リストからデータを削除するときは、リストから一要素減らし、それを未使用リストに追加します。

追加処理（概要だけ）
1:Hoge(3)のNextを見ます。EOFであれば、配列を適当な数だけ拡張します。増えた分の要素は未使用リストに追加します。
2:未使用リストから一要素削除し、リストに挿入します。リストの末尾に追加するのでしたら、Hoge(1)と、Hoge(1).Prevの間に挟み込めばいいんですね。

削除処理とかは、適当にアレンジして作ってくださいね（横着

ちなみに削除しても空白リストの要素数が増えるだけでメモリ開放はされないので、必要であればガベージコレクションして、Redimして、メモリを開放してください。

補足

ご丁寧な回答、ありがとうございます。
その親切心に甘えさせていただいて頂くようで悪いのですが、二点ほど確認させていただいてよろしいでしょうか？

１：＞Hoge(2)のNextを見ます。EOF（つまり3）であれば
というのは「未使用リストのBOFを見る」という意味合いの処理でしょうか？

２：＞リストの末尾に追加するのでしたら、Hoge(1)と、Hoge(1).Prevの間に挟み込めばいいんですね。
というのは、追加されるもの自体が末尾になるのではなくて、末尾の一つ前の要素になるということ？

VBについては実はまったく素人なもので（笑）、馬鹿なことを聞いているようでしたら笑って聞き流してください。

回答No.3

ARC

その１。コレクションオブジェクトを使う。楽チンです。内部的にもリスト構造になっています。

その２。動的配列を使う。
VBではポインタは使えませんので、配列の添え字をポインタの代わりに使います。

Type typHoge
　　sData　　as String
　　lPrev　　as Long
　　lNext　　as Long
End Type
Dim Hoge() as typHoge

などとして、lPrev,lNextには配列の添え字を入れます。
配列を増やすときは、Redim Preserve ね。
クラスにしてAddやRemoveといった要素を追加してやります。

その３。非接続型のADOを使う。慣れればこっちの方が手っ取り早いかも。機能も豊富だし。
ただしちょっと複雑だし、プロジェクトによってはADO使っちゃダメってな場合も。

Dim rsHoge As New ADODB.Recordset()
Dim Fld As ADODB.Field
Dim sSQL As String
rsHoge.Fields.Append("DATA", ADODB.DataTypeEnum.adBSTR)
rsHoge.Open()

rsHoge.AddNew()
rsHoge.Fields("DATA").Value = "hoge"
rsHoge.Update()

rsHoge.AddNew()
rsHoge.Fields("Data").Value = "moga"
rsHoge.Update()

rsHoge.MoveFirst()
MsgBox(rsHoge.RecordCount & ", " & rsHoge.Fields("Data").Value)

回答No.2

imogasi

上役？がいう「リスト構造で実現しろ」は（１）一方向リストか（２）双方向リスト（木構造）なのか良く考える必要があります。
木構造について
http://www5c.biglobe.ne.jp/~ecb/c/14_08.html
ズバリを話題にしたものとして
http://pascal.cs.kobe-u.ac.jp/~shii/win/etc/VbList.html
http://www.alpha-net.ne.jp/users2/ei9711/vbkouza/kouza16.html
例題はＣ言語ですが、解説として
http://www.cs.shinshu-u.ac.jp/Lecture/SE2/2000/L5-2.html
など。

回答No.1

TAGOSAKU7

ぬぉ

参考URL：

http://pascal.cs.kobe-u.ac.jp/~shii/win/etc/VbList.html