サーチのアルゴリズムを学ぶ

PHP版リンクトリスト

　要素を表す部分をPHPで書けば図2-1のような感じになります。なお、紹介するソースコードは、こちら（http://www.thinkit.co.jp/images/article/159/1/15911.zip）からダウンロードできます（15911.zip/0.96 KB）。

　PHPのclassを使っていますが、ここでは要素をリンクする（つなぐ）ために使っています。オブジェクト指向のためというよりはCの「構造体」の替わりです。この要素を表すLinkは図2-2のようなイメージです。この要素を「作る」ためにはclassのインスタンスを作ります。PHPではnewを使います。

　要素をつなげるためには「ポインタ」を操作します。そのための関数insert()を作りましょう（図2-3）。この関数で少しだけ注意しなければならないことは、引数の$anchorに「&」がついていることです。理由はおわかりでしょう。$anchorの値を書き換える必要があるからです。

　リスト構造をたどって要素を見つけるためにはsearch()関数を作ります（図2-4）。

　配列版の線形探索とあまり変わりませんね。配列版では要素のインデックスを増やしながら順に見て行くだけですが、リストの場合はポインタを順にたどっていきます。

テストする

　このプログラムをテストしますが、配列を初期化するようにはリスト構造のデータを準備することができません。要素ひとつひとつをリストに「つなげる」作業が必要です。データを探す前に、まずリスト構造そのものを作る必要があります。このことも含めて図2-5のようなテストプログラムを作ります。

　このテストプログラムにはデータのための配列があります。その中身はプログラミング言語の名前です（プログラミング言語とは呼ばないものも含まれていますが）。これらは筆者が多少なりとも勉強したプログラミング言語を、ほぼ勉強した順序に並べたものです。また、本来は大文字で書くべきものもありますが、簡単にするために小文字にしてあります。

　これをもとにリスト構造を作ります。次の部分がリストに追加する作業をしています。

insert( $anchor, $langs[$n], "$n" );

　リストの個々の要素にはプログラミング言語名と番号（連番）が入ります。

　登録したものを検索するだけですが、実行すれば図2-6のような結果が出力されます。

　ただ順番に検索して表示するだけでは面白くありませんから、検索するまえにデータをシャッフルしています。そのため、実行するたびに表示順序は変わりますのでご注意ください。みなさんが実行した場合、この結果とは違う出力になると思います。

　続いて、このプログラムの性能を考えましょう。