」の値が抜け落ちたカードである。カードが1,000枚あっても、抜け落ちたカードを手作業で当てることができそうです。このアルゴリズムが思い付きましたでしょうか。速いアルゴリズムを考えるのは大変だと不安になったかもしれませんが大丈夫です。問題は先人によって優れたアルゴリズムが考案されているため、考えなくても調べるだけで解決することが多いです。2データ構造2.1リストデータの扱い方を工夫することでも処理が効率的になります。昇順に並んだデータ列を作りたい場合、配列で実現するとデータの追加や削除に時間がかかってしまいます(図2-1)。これを「リスト」と呼ばれるデータ構造にすると効率的になります。リストとは、「値」と「次の要素のアドレス」をセットにした図2-2のようなものです。2.2キューリストのほかにも様々なデータ構造があります。ここでは主なデータ構造をいくつか紹介します。窓口に並ぶ人々の行列のように、先に入れたデータから順番に取り出されるデータ構造を「キュー」といいます(図2-3)。図の下側にメインメモリ内の状態を示しています。「3」「5」のデータを入れた後、「3」「5」の順序でデータが取り出されていきます。キューを配列で実装する場合は図のように、「先頭」と「末尾」を指すポインタを用意し、末尾にデータを入れ、先頭から取り出す方法があります。ポインタが配列の末端に到達したときは、配列の先頭に戻します。キューはネットワーク通信やウインドウメッセージなど、寄せられてくるデータを非同期で処理したい場合によく使われます。2.3スタック積み上げた荷物のように、後に入れたデータを先に取り出すデータ構造を「スタック」といいます(図2-4)。スタック「3」「5」のデータを入れた後、「5」「3」の順序でデータが取り出されています。関数呼び出しの際に確保される「スタック領域」はこの構造です。以上で紹介した、リスト、キュー、スタックのデータ構造は、多くの言語では標準機能として用意されています。2.4ツリーリストは直線状に連なったデータ構造でしたが、枝分かれして階層構造になったものを「ツリー」といいます(図2-5)。ツリーツリーは計算式やXMLのような階層構造になっているもの全般で使われます。2.5グラフツリーは階層構造でしたが、ループを認めて網目状にしたものを「グラフ」といいます。グラフグラフは各地点間の距離や流量など、要素間の関係を扱うときによく使われます。グラフには様々なアルゴリズムが考案されています。ある地点から別の地点までの最短経路を求めたい場合は、用途によって「ワーシャル・フロイド法」「ダイクストラ法」「ベルマン・フォード法」などのアルゴリズムが使い分けられます。3プログラムで実装するアルゴリズムを調べて理解したり自分で考案したあとは、それをプログラムで実装しなければなりません。最後に、プログラムで実装する際のヒントを示しておきます。例題として、数字が書かれた100枚のカードが昇順に並んでいるときに「1234」と書かれたカードが存在するかを二分探索するプログラムを書いてみましょう。「1、5、12、30、...、2750、2987」のような中から1234を探すプログラムです。ここではC言語で書くことにします。100枚のカードはプログラム上では配列で表現できそうですので、とりあえず配列を宣言します(図3-1)。binary_search1.cアルゴリズムを一気にプログラムに書こうとすると、どこから手をつけたら良いのか判らなくなってしまいますので、行われる操作を「順番に」実装していくことが大切です。二分探索では、まず全データの中間のデータを見て、目的のデータが左右のどちら側にあり得るかを判断するのでした。これをプログラムに追記しましょう(図3-2)。binary_search2.cデータの中間の要素番号を指すmedianという変数を用意して、1234がそのどちら側にあるかをif文で判定しました。このとき仮に1234が左側にあった場合は「cards[0]~cards[median-1]」の中にあるといえます。1234が右側にあった場合は「cards[median+1]~cards[99]」の中にあるといえます。そこでこれを、minとmaxという変数を使って「cards[min]~cards[max]」の中にあると表現すれば、以後1234が存在しうる範囲に対して同様の操作を繰り返す部分が共通のプログラムで処理できそうです。試しに、今書いたプログラムをminとmaxを用いて書き直してみましょう(図3-3)。binary_search3.c最初はcards[0]~cards[99]の中から探すので、「min=0」、「max=99」とし、minとmaxの中間であるmedianは、両者の平均を取って「median=(min+max)/2」としています。仮にmedianより左側に1234があった場合、cards[min]~cards[median-1]の中にあることになるので、探索範囲を「max=median-1」に狭めています。medianより右側に1234があった場合は、cards[median+1]~cards[max]の中にあることになるので、探索範囲を「min=median+1」に狭めています。あとは新しく更新したminとmaxに対して、同様の操作を繰り返すだけです。minとmaxの間隔が無くなればデータ中に1234が存在しなかったことを意味するので、これをループの終了条件にします。完成したプログラムは図3-4の通りです。binary_search4.c7行目のコメントのところでcardsに適当に100枚のカードの値を設定すると、1234が存在するかどうかを判定してくれるでしょう。今回は、アルゴリズムと主なデータ構造について解説しました。次回は、プログラムが大規模になったときや多人数開発のときに役に立つ「オブジェクト指向」の考え方と機能について解説します。オブジェクト指向とクラス前へ目次ホームへ次へ©Kuina-chan1579923967jaf。