C言語 配列 sort,search,再帰 スクリプトの書き方

バイオインフォ道場、くまぞうです。

C言語で配列を使ってみましょう。配列は、複数の値を管理する入れ物のようなものです。他の言語でもよく使う機能ですが、C言語の場合は同じ型のデータを管理します。また、サイズや初期化に注意する必要があります。

配列の基本的な使い方

配列は、データを順番に管理します。この順番のことを「添字」や「インデックス」と呼びますが、配列を使う場合はこれらの番号を使ってデータ操作を行います。配列に名前を付けて生成し、先頭を0番のデータ、次のデータを１番のデータというようにデータを追加します。追加したデータは、番号を使って参照・編集を行います。

生成

配列を使うためには、必要な要素数と型を指定します。メモリ上に連続した領域か確保されます。

  int array[10];               # 必要に応じて初期化する
  int a[5] = {1, 2, 3, 4, 5};  # 初期化済み5個の配列
  int b[]  = {1, 2, 3, 4, 5};  # 初期化済み5個の配列（サイズは自動で確保される）
  char c[10];                  # char型配列。必要に応じて初期化する

参照

配列を参照する場合は、配列名[index番号]でアクセスします。０番が先頭です。最後は「要素数-1」です。

  for (i=0; i<SIZE; i++) {
    printf("%d", a[i]);  # int型の配列を参照する場合（i, SIZEの宣言は別途必要）
  }

編集

配列要素は書き換えることが出来ます。配列のインデックスを指定して、新しいデータを代入すると、指定したデータを更新出来ます。

  for (i=0; i<SIZE; i++) {
    a[i] = i*2;  # int型の配列にデータをセット、初期化など（i, SIZEの宣言は別途必要）
  }

プログラム

プログラム例

test_sort.c

#include <stdio.h>

#define SIZE_N 20

void main(void)
{
  int array[SIZE_N];

  int i, j;
  for (i=0; i<SIZE_N; i++) {
    array[i] = rand() % 10000;
  }
  
  int temp;
  for (i=1; i<SIZE_N; i++) {
    temp = array[i];
    for (j=i-1; j>=0 && array[j]>temp; j--) {
      array[j+1]=array[j];
    }
    array[j+1]=temp;
  }

  for (i=0; i<SIZE_N; i++) {
    printf("%6d\n", array[i]);
  }
}

test_search.c

#include <stdio.h>

#define SIZE_N 20

int my_search(const int array[], int key, int s_min, int s_max);

void main(void)
{
  int array[SIZE_N];
  int i;

  for (i=0; i<SIZE_N; i++) {
    array[i] = 2*i;
  }

  int key, res;
  printf("input number 0-38 ");
  scanf("%d", &key);

  res = my_search(array, key, 0, SIZE_N-1);
  res != -1 ? \
      printf("found:array[%d], %d\n", res, array[res]) : \
      printf("not found\n");

  for (i=0; i<SIZE_N; i++) {
    printf("%8d", array[i]);
  }
}

int my_search(const int array[], int key, int s_min, int s_max)
{
  int s_mid = (s_min+s_max)/2;

  int res;
  if (key == array[s_mid]) {
    return s_mid;
  }
  if (s_min > s_max) {
    return -1;
  }

  return (key<array[s_mid] ? \
          my_search(array, key, s_min, s_mid-1) : \
          my_search(array, key, s_mid+1, s_max));
}

プログラム実行

  $ gcc test_sort.c -o test_sort
  $ ./test_sort
  27
  59
  492
  ...
  8690
  9172
  9383

  $ gcc test_search.c -o test_search
  $ ./test_search
  input number 0-38 10
  found:array[5], 10
  0       2       4       6       8      10      12      ... 38  

プログラムについて

test_sort.cでは、配列に格納されたランダムな数値をソートしました。基本挿入法でソートしています。test_search.cでは、ソート済みの配列に対して、二分サーチを行いました。ソートで配列を破壊することがないように、constで修飾しています。また、再帰呼出しで検索を繰り返しています。