| 目次| 1234567891011121314
| 資料| 予定| 課題| 宿題|

データ構造

データ構造とアルゴリズムとは

データ構造とは,データを表現・保存する方法や形式のことです.アルゴリズ ムとは,データを操作する一連の作業のことです.

比較的大きなアプリケーションを作ろうとしたとき,最初に操作対象のデータ 形式が決まらないと,頭の中にコーディングのインスピレーションが湧いてこ ないことがあります.データ構造がいくつも用意できるのに,実際にそれをど うやって実現するのかわからないために,コーディングに不安を覚えながら作 業を進めることもあります.

コンピュータサイエンスの教育課程を履修なさったり,データ構造とアルゴリ ズムについて書籍から知識を得ていた方などは,こんなことを思ったことがあ るのではないでしょうか.

「データ構造とアルゴリズムか.切っても切れないな. 両方分からないとダメなんだ.データ構造とアルゴリズムとは,うまく言ったもんだ」
ここでは,データ構造としてスタック,連結リスト,二分木を取り上げます.

スタック

図1: スタックの仕組み
スタック
スタックは,一つのデータを入力,または出力するデータ構造です(図1). 出力されるデータは,最後に入力されたデータです.データを上に積んでいき, 必要なとき,一番上に積まれているデータから取り出していく構造になってい ます.スタックでは,上にデータを積む操作を「プッシュ(push)」,上から データを取り出す操作を「ポップ(pop)」といいます. スタックはこの入出 力の関係から LIFO(Last-In First-Out; 最後に入力したものが最初に出力さ れる) と呼ばれます.

スタックは主に再帰処理を行う場合のデータの保存や,文字列の解析に利 用されます.たとえば,以下のようにスタックを用意して

    import java.util.*;
    ...

    Stack stack = new Stack();

    stack.push("Huyu");
    stack.push("Nabe");
    stack.push("Nihonn-shu");

    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
実行すると

  Nihonn-shu
  Nabe
  Huyu
と表示されます.最後のプッシュされたものから順にポップされている様 子が分かります.

スタックは何かのデータを格納して利用するというよりは,ある目的を達 成するための仕組みの一つとして利用されることが多いといわれます.コンパ イラのソースコード解析など,スタックを利用しています.

連結リスト

図2: 連結リストの仕組み
連結リスト
連結リストは,「データ」と「次のデータへのアクセス方法」を持ったデー タ構造です(図2).データを追加したいときは,同じデータ構造を持ったデー タを作成して,それを「次のデータへのアクセス方法」が指し示すようにしま す.このようにすると,最初のデータにアクセスして,次のデータを持ってき て,データにアクセスして,次のデータを持ってきて,データにアクセスして… を繰り替えすことになります.連結リストでは,基本的に「次のデータへのア クセス方法」が,自分より先に連結された同じリストのどれかを指すことはあ りません.閉ループは作らずに,一本の線としてのデータ構造を持ちます(注: データの最後が先頭を指し示すようにすることもあります.).

このような構造を持っている連結リストは,どこまで増えるか分からない データを格納するのに適しています.データ構造が単純であることから,また, この構造が非常に有用であることから,他のデータ構造を作成するのに連結リ ストを用いていることもあります.

 連結リストのデータ構造を持ったクラスを作成します.

class LinkedList {
    private Object data = null;
    private LinkedList next = null;

    public void setData(Object obj) {
        data = obj;
    }

    public Object getData() {
        return(data);
    }

    public void setNext(LinkedList list) {
        next = list;
    }

    public LinkedList getNext() {
        return(next);
    }
}

    ...


    // それぞれデータを作成
    LinkedList Number1 = new LinkedList();
    LinkedList Number2 = new LinkedList();
    LinkedList Number3 = new LinkedList();

    Number1.setData("Midorikawa");
    Number2.setData("Koshino Kanbai");
    Number3.setData("Secchuu Bai");

    // データを連結
    Number1.setNext(Number2);
    Number2.setNext(Number3);
    Number3.setNext(null);


    // データにアクセスして出力
    System.out.println(Number1.getData());
    System.out.println(Number1.getNext().getData());
    System.out.println(Number1.getNext().getNext().getData());
実行すると

    Midorikawa
    Koshino Kanbai
    Secchuu Bai
のようになります. 順順に次のデータにアクセスしてデータを出力していることがわかります.

もしかすると,あなたはこのクラスは間違っていると思うかもしれません. 作成した連結リストのクラス LinkedList の中で LinkedList を生成していま す.LinkedList の中では LinkedList が生成されて,その LinkedList の中 では inkedList が生成されて,その LinkedList の中でも LinkedList が… という堂々巡りが起ってしまうのではないか,と思うかもしれません.連結リ ストのような仕組みはとても便利であるため,コンパイラはこの記述を我々が 思うところのように動作するように設計・実装されています.これは,実際に 生成される LinkedList フィールドは,実体ではなく参照なので,堂々巡りに は陥らない,ということです.

二分木

図3: 二分木の仕組み
二分木
二分木は,「データ」と二つの「次のデータへのアクセス方法」を持った データ構造です(図3).二分木では,基本的に「次のデータへのアクセス方 法」が,自分より先に連結された同じ木のどれかを指すことはありません.閉 ループは作らずに,一本の木としてのデータ構造を持ちます(注:「次のデー タへのアクセス方法」が示すデータが,自分より上にあるデータであった場合, 一般にそれは木構造ではなくグラフと呼ばれます.).

図4: 探索二分木の仕組み
探索二分木
二分木は主に検索とデータ保持の両方の目的を効率よく果たすために利用 されます.検索に利用される代表的な二分木に二分探索木があります(図4). 二分探索木は,二つの「次のデータへのアクセス方法」に,それぞれ決まった 条件を付けたデータ構造です.たとえば,保持しているデータよりも小さいデー タは「次のデータへのアクセス方法A」の方に連結し,保持しているデータよ りも大きいデータは「次のデータへのアクセス方法B」の方に連結する,といっ たものです.このように規則を決めておけば,目的のデータを探索するには, そのノードのデータだけを判定して探索すればよいことになり,探索にかかる 計算が少なくなります.

図5: バランスの崩れた二分木
バランスの崩れた二分木
二分探索木のような二分木を利用してデータの保持および探索などを行う 場合,木の左右のバランスがとれていることが重要になります.もし,バラン スが崩れて片方に長い二分木を作ってしまうと,連結リストと同じ構造になっ てしまい,二分木の利点はなくなってしまいます(図5).このように,バラ ンスを失っている二分木を不均衡二分木,これに反してバランスを保っている 二分木を均衡二分木と呼びます(図6).データの追加や削除を行ってもバラ ンスの崩れない二分探索木などの研究も行われています.バランスを保とうと する二分木では,データの追加や削除に用いられるアルゴリズムが難しくなり ます.

図6: 均等二分木と不均等二分木
均等二分木と不均等二分木
二分木のような構造を持っていて,かつ「次のデータへのアクセス方法」 を複数持っている構造を一般に多方向木と呼びます.身近なところで,多方向 木はファイルシステムとして利用されています.最上階のルートディレクトリ / の次には bin, dev, etc, usr, Program Files といったディレクトリが連 結されています.usr ディレクトリの下には X11R6, home, local ディレクト リが結合されている,という構造です./usr/local/bin/vi のようにパスを指 定して目的のファイルにアクセスしています.このような構造にすることで, データを目的別に違う名前の仕切りの中に格納しているようなイメージを持ち, ファイルを分類しやすくなります.このデータ構造は非常に便利であるため, 多くの OS でファイルシステムの構造として採用されています.もちろん,多 方向木の構造をとらないファイルシステムを持つものもあります.

再帰計算

再帰 (recursion) とは,「メソッドが自分自身を呼び出す」というプログラ ミングテクニックである.自分を呼ぶ出すなんてできるわけはないと思われる かも知れないが,再帰は,もっとも興味深くかつ便利な計算技法の一つである. 再帰を使うと便利な状況はいくつもある.例えば,三角数の計算,階乗の計算, ある種の数列の計算,ある種のサーチ(再帰によるバイナリ・サーチ),アナ グラム(文字の並べ替え),「ハノイの塔」などのある種のパズルの解決,な どである.ここではもっとも単純な三角数の計算を例にして説明を行う.

三角数の計算

古代ギリシャのピタゴラス派の数学者たちは,次のような数列を神秘的だと 考えたという.
  1, 3, 6, 10, 15, 21, … …
  
この数列の n 番目の項は,前の項に n を足した数になっている.例えば,3 番目の項は,2 番目の項の 3 に 3 を足した数 6 になっている.この数列を 構成する数は,下に示すように三角形に並べることができるので,三角数 (triangle numbers) と呼ばれている.
                □
           □    □□
       □   □□   □□□       … …
    □  □□  □□□  □□□□  
 □  □□ □□□ □□□□ □□□□□
  #1=1  #2=3   #3=6  #4=10    #5=15      … …
  
ここで,この数列の n 番目の項の値を見つけるプログラムを書くとしよう. 下の図を見ればわかるように,各項の値は図の各桁の四角形の数を単純に足せ ば求まる.例えば,4 番目の項の値は,4 + 3 + 2 + 1 = 10 となる.
  ■
  ■□
  ■□■
  ■□■□
  ↑↑↑↑
  |||1 この桁
  ||2 この桁
  |3 この桁
  4 この桁
  
次に示す TriangleNum クラスの中の triangle メソッドでは,上図のような テクニックを用いて三角数を求めている.ディクリメンタル演算子で n を 1 ずつ減らしながら,桁の数を変数 total に足し込んでいる.
public class TriangleNum {
   public static int triangle(int n) {
      int total = 0;

      while (n > 0) {        // n が 1 になるまで
         total = total + n;  // n(桁数)を total に足し込む
         n--;                // n の値を 1 だけ減らす
      }
      return total;
   }
   public static void main(String[] args) {
      int num = KeyboardInput.askInt("Enter a number: ");
      System.out.println("The answer: " + triangle(num));
   }
}
あるいは,n 項目の値は 1 から n までの数の総和に等しいことに着目すれ ば,次に示す TriangleNum2 クラスの中の triangle メソッドのように計算す ることも可能である.
public class TriangleNum2 {
   public static int triangle(int n) {
      return (n * (n + 1) / 2);  // 1 から n までの総和を求める
   }

   public static void main(String[] args) {
      int num = KeyboardInput.askInt("Enter a number: ");
      System.out.println("The answer: " + triangle(num));
   }
}

n項木目の値を再帰を使って求める

TriangleNum クラスの中の triangle メソッドのようにループを使う方法はわ かり易いが,ここでは少し違った角度から問題を捉えてみよう.違った角度か らの捉え方というのは,n 項目の値を全部の桁の和として考える捉え方ではな く,たった 2 つのものの和だと考える捉え方である.その 2 つというのは, である.つまり下図のように n 項目の値を 2 つに分割して考えるのである.
■
■□
■□□
■□□□
↑|____|
|  |
|  6 その他の桁の総和 −
|                      |→ 合計 10
4 最初の桁 −−−−−−−
この考え方では,「その他の桁の総和」が求まれば(それに n を足せば良い のだから)解は求まる.それをメソッド triangle として書くと以下のような イメージになる.
  public static int triangle(int n) {
     return (n + sumRemainingColumns(n));  // 不完全なバージョン
  }
  
しかし,最初に triangle メソッドを書くのが難しいのと同様に sumRemainingColumns メソッドを書くのも難しいわけであり,これでは解に全 く近付いていないように思えるかも知れない.だが,ここで上の図をよく見直 すとわかるのは,項 n の場合の「残りの桁(その他の桁)」の総和が項 n - 1 の場合の「すべての桁」の総和に等しいということである.従って,項 n のすべての桁の和を求めるメソッド sumAllColumns があれば,そのメソッド を n - 1 という引数で呼び出せば,項 n の場合の「残りの桁(その他の桁)」 の総和が求まることになる.
  public static int triangle(int n) {
     return (n + sumAllColumns(n - 1));  // 不完全なバージョン
  }
  
ところで,メソッド sumAllColumns が行うことは メソッド triangle が行う ことと等価である.従って,ここでわざわざ別のメソッドを定義する必要はな く,メソッド triangle を呼び出せば良い.そのイメージは下のようになるは ずである.
  public static int triangle(int n) {
     return (n + triangle(n - 1));  // 不完全なバージョン
  }
  
このように,メソッドが自分自身を呼び出すのは不可能に思えるかも知れない. しかし,メソッドの呼び出しとは「制御(コンピュータの次の瞬間の実行)を そのメソッドの先頭に移す」ことなので,制御の移動はメソッドの中からでも 外からでも行うことができる.従って,メソッドが自分自身を呼び出すことは 可能なのである.

他人任せ

上記の最後のコードのような方法は,「無限の責任転嫁」のようにも思える. n 番目の人は自分が求める値は n - 1 番目の値 + n なので,n - 1 番目の人 に n - 1 番目の値を求めるようにお願いし,n - 1 番目の人は … … という ように.こうやって一番肝心な仕事は他人まかせにしているとも言える.この 責任転嫁はどこかで止まらなければならないはずである.もしどこかで自力で 求めた解がわかってこの責任転嫁の鎖が切れれば,その解を一つ前の人に教え て,その人はその解に自分の数を足してさらにその前の人に解を教えて,とい うようにどんどん前に遡って(これをバックトラック(backtrack) という), 最終的には元の n 番目の項の値がわかるはずである.逆に言えば,自力で求 めた地点すなわち他人まかせの終点がなければ,この無限の責任転嫁の鎖は永 久に切れないことになる.

他人任せの終点

この無限の責任転嫁を防ぐためには,n = 1 の場合,つまり 1 番目の三角 形を見つけてくれと頼まれた人が自力で「答えは 1 である」と答えられねば ならない.というのも,n は 1 より小さくなり得ないので,1 番目の人は他 人に値を見つけてもらうことは叶わないからである.従って,無限の責任転嫁 は n = 1 で終る.このことをメソッド triangle の条件文(if 文)として加 えると以下のようになる.
  public static int triangle(int n) {
     if (n == 1)
        return 1;
     else
        return (n + triangle(n - 1));
  }
  
再帰メソッドがもはや再帰的な呼び出しをせずに,その場で素直にリターン する条件のことを基底条件 (base condition) と呼ぶ.この例では n == 1 が 基底条件である.いかなる場合でも,再帰メソッドに無限再帰を起こさせない ためには,この基底条件が必要不可欠となる.
以上をまとめて,実際に動作するプログラムとしたのが以下のものである.
public class TriangleNum3 {

    public static int triangle(int n) {
      if (n == 1)
         return 1;
      else
         return (n + triangle(n - 1));
   }

   public static void main(String[] args) {
      int num = KeyboardInput.askInt("Enter a number: ");
      System.out.println("The answer: " + triangle(num));
   }
}

再帰の仕組み

再帰で実際にどのような処理が行われているのかがわかるように,引数と戻り 値を出力するようにプログラムを書き換えたのが以下のものである.
public class TriangleNum4 {
   public static int triangle(int n) {
      System.out.println("Entering: n =" + n );
      if (n == 1) {
         System.out.println("Returning: 1");
         return 1;
      }
      else {
         int temp = n + triangle(n - 1);
         System.out.println("Returning: " + temp);
         return (temp);
      }
   }

   public static void main(String[] args) {
      int num = KeyboardInput.askInt("Enter a number: ");
      System.out.println("The answer: " + triangle(num));
   }
}
これを例えば n = 5 として実行すると,以下のように表示される.
  Entering: n = 5
  Entering: n = 4
  Entering: n = 3
  Entering: n = 2
  Entering: n = 1
  Returning: 1
  Returning: 3
  Returning: 6
  Returning: 10
  Returning: 15
  The answer: 15
  
見ればわかるように,メソッド triangle が自分自身を呼び出すたびに,n の 値が 5 から 1 ずつ減っていき,メソッドが徐々に自分自身に沈み込んでいく. そのような沈み込みは n = 1 のときに終了し,不死鳥のごとく甦る(リター ンする).そしてリターンするたびに,自分に渡された引数の値に,自分が呼 び出した自分の分身からの戻り値を足して,それを自分の戻り値としてリター ンする.それは main メソッドへ戻り値が返されるまで続く.その様子を示し たのが下図である.
  n=3で呼び出す.
     ↓
┌───分身3───┐
│   n=3   │
│         │
│┌──分身2──┐│
││  n=2  ││
││       ││ 
││┌─分身3─┐││
│││ n=1 │││
│││     │││
│││ 1を返す│││
││└─────┘││
││       ││
││  2を足す ││
││  3を返す ││
│└───────┘│
│         │
│   3を足す  │
│   6を返す  │
└─────────┘
     ↓
    6を返す.
  

再帰の特徴

再帰メソッドに共通する特徴は, である.
メソッドを呼び出すには何らかのオーバーヘッド(制御をそのメソッドの先頭 に移すなど)が伴うので,ループよりも遅くなる可能性がある.特に再帰呼び 出しの回数が多い場合にはかなり非効率である.しかし再帰計算は,効率が良 いから使われるのではなく,ある種の問題の解き方を単純でわかり易いものに してくれるから利用されるのである.

[応用]数値計算

微分方程式や積分などを解析的に解くのではなく,計算機を利用して近似 的に解くことを数値計算と呼ぶ.数値計算のための様々な手法が開発されてお り,自然科学・工学はもとより,経済学やオペレーションズリサーチなどの様々 な分野で広く使われている.ここでは数値計算の理論的な詳細には触れずに, 簡単な数値計算の手法を学び,プログラミングしてみる.題材としては積分計 算(数値積分)を取り上げる.

積分計算と台形公式

a ≒ b のときの区間 [ a, b ] における関数 f(x) の定積分の近似式として,
  (b - a)(f(a) + f(b)) / 2 
  
という式が知られている.積分とは面積を求めることだと考えると,この式は, 区間 [ a, b ] における関数 f(x) の積分値を,4 点 (a, 0),(a,f(a)), (b,f(b)),(b, 0)が囲む台形の面積と捉えている.従って,この式を台形公 式と呼ぶ.
a ≒ b ではない場合の区間 [ a, b ] における関数 f(x) の 定積分を求める場合には,区間 [ a, b ] を微小区間に区切って上記の台形公 式を適用すれば良い.この際に区切る微小区間の数を「分割数」と呼ぶが,一 般に分割数が大きいほど数値積分の精度が上がる.
以下に示す IntegralTrapezoid クラスは,関数 f(x) = 4 / (1 + x * x) の区間 [ a, b ] における積分値を求めるプログラムである.関数 f(x) は func メソッドの中で,分割数 n は trapezoid メソッドの中で記述する.区 間の終端 a と b の値はキーボードから入力するようになっている.
public class IntegralTrapezoid {
   public static double func(double x) {
      return (4 / (1 + x * x));
   }

   public static double trapezoid(double a, double b) {
      int i, n = 32;
      double h, integral = 0.0;

      h = (b - a) / n;
      for (i = 0; i < n; i++) {
         double s = i * h + a;
         double t = (i + 1) * h + a;
         integral += (t - s) * (func(t) + func(s)) / 2;
      }
      return integral;
   }

   public static void main(String[] args) {
      double a = KeyboardInput.askDouble("開始点:");
      double b = KeyboardInput.askDouble("終了点:");

      System.out.println("積分値:" +  trapezoid(a, b));
   }
}

課題

1-3が必須.4はできればやってみて下さい.
  1. スタック・連結リストのプログラムを完成し,動作を確認しなさい. (ファイル名・プログラム名に注意する事.StackTest,LinklistTest等にしなさい)
  2. 階乗 (factorial) の計算を再帰を用いて行うプログラムを作成せよ. ここで n の階乗とは,n × (n - 1) × … … × 2 × 1 のことで ある.factorial(n) = n × factorial(n - 1) であり,0 の階乗は 1 と定義されている.
  3. [応用]上述の台形公式の代わりに,以下の中点公式を用いて関数 f(x) = 4 / (1 + x * x) の積分値を求めるプログラムを作成してみよ(下記表の"??"を埋める).そして 区間 [ 0, 1 ] における f(x) の積分値を求め,台形公式を用いた場 合と比較せよ.なお,この関数の区間 [ 0, t ] におる積分値は arctan t に等しい.従って区間 [ 0, 1 ] に おける関数 f(x) の 積分値はπ(= 3.141592653 …)に等しい.
    	(b - a)f((a + b) / 2)
    	
    なお,分割数 n を変化させた場合の [ 0, 1 ] における f(x) の積 分値は以下の表のようになるので,デバッグの参考とせよ.
    分割数 n 台形公式 中点公式 シンプソン公式
    1 3 3.2 3.133333
    2 3.1 3.162353 3.141569
    4 3.131176 3.146801 3.141593
    8 3.138988 3.142895 3.141593
    16 3.140942 3.141918 3.141593
    32 3.141430 3.141674 3.141593
    64 ?? ?? 3.14XXXX
    128 ?? ?? 3.14XXXX
  4. 整列アルゴリズムを考える
    来週は,ランダムな数字が入った配列を昇順に並べ替える方法(整列アル ゴリズム)を取り上げる.詳細なプログラムは次週以降に解説するが,今 までに説明したJava言語の機能を使って整列を実現する方法を考えな さ い.

    詳細なプログラムでなくてもかまわない.「繰り返す」「判断する」「x 番目の配列に変数yの内容を覚える」などの表現でよい


|
目次| 1234567891011121314
| 資料| 予定| 課題| 宿題|