Javaによるアルゴリズムとデータ構造

演習3-2の解答

   |   0   1   2   3   4   5   6
---+------------------------------
   |   *
  0|   6   4   3   2   1   9   8
   |
   |       * 
  1|   6   4   3   2   1   9   8
   |
   |           * 
  2|   6   4   3   2   1   9   8

その値はa[2]に存在します。

　線形探索の過程が視覚的に分かるように、右に示すような表示を行うプログラムを作成せよ。
　着目要素の上に'*'を表示すること。

// 演習3-2
// 線形探索（探索過程の詳細を表示）

import java.util.Scanner;

class SeqSearchEx {

  //--- 配列aの先頭n個の要素からkeyと一致する要素を線形探索（番兵法）---//
  static int seqSearchEx(int[] a, int n, int key) {
    System.out.print("   |");
    for (int k = 0; k < n; k++)
      System.out.printf("%4d", k);
    System.out.println();

    System.out.print("---+");
    for (int k = 0; k < 4 * n + 2; k++)
      System.out.print("-");
    System.out.println();

    for (int i = 0; i < n; i++) {
      System.out.print("   |");
      System.out.printf(String.format("%%%ds*\n", (i * 4) + 3), "");
      System.out.printf("%3d|", i);
      for (int k = 0; k < n; k++)
        System.out.printf("%4d", a[k]);
      System.out.println("\n   |");
      if (a[i] == key)
        return i;      // 探索成功
    }
    return -1;          // 探索失敗
  }

  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);

    System.out.print("要素数：");
    int num = stdIn.nextInt();
    int[] x = new int[num];          // 長さnumの配列

    for (int i = 0; i < num; i++) {
      System.out.print("x[" + i + "]：");
      x[i] = stdIn.nextInt();
    }
    System.out.print("探す値：");      // キー値の読込み
    int ky = stdIn.nextInt();

    int idx = seqSearchEx(x, num, ky);    // 配列xから値がkyの要素を探索

    if (idx == -1)
      System.out.println("その値の要素は存在しません。");
    else
      System.out.println("その値は" + "x[" + idx + "]にあります。");
  }
}

戻る