プログラミング技法とデータ構造

基本データ型

データ構造の説明をする前に，単体のデータ型をおさらいしておく．C言語では，プログラムを実行する上で次のような型の変数を記憶することができた．

• int, long: 整数
• float, double: 小数(単精度と倍精度)
• char: 文字

単純なC言語のプログラムは，この基本データ型の変数だけを使えば書くことができた．しかし，大量のデータを扱うときや，効率よく計算を行うためのアルゴリズムを実行するためには，これら基本データ型を組み合わせた「データ構造」を構築する必要がある．例えば，前回の素数を求める「エラトステネスのふるい」を紹介したが，そのプログラムでは，素数かどうかのフラグを調べる数分用意しておく必要があった．このフラグは次に説明する「配列」というデータ構造をしていた．

#include <stdio.h>
#define MAX 1000

int main(void)
{
  int i, j;
  int table[MAX];

  for(i=2 ; i < MAX ; i++){  //初期化
    table[i] = 0;          //フラグを全部下ろす
  }
  for(i=2 ; i < MAX ; i++){
    if(table[i]!=0){       //フラグがなければ
      printf("%d\n", i);   //ならば，このiは素数である．
      for(j=2 ; i*j < MAX ; j++){ //倍数を除外，なにかの倍数にフラグを立てる
        table[i*j] = 1;
      }
    }
  }

  return 0;
}

配列とインデックス

基本データ型を組み合わせて，構築するデータ構造の中で，もっとも単純なものが「配列」(array)である．配列は，同じデータ型の要素を一列に並べたものである．例えばint型の配列例は次のようなイメージとなる．

配列table: 
000  001  002  ...  999

100
234
001
-32

配列全体を指す名前を「table」とすると，002に対応する要素はtable[2]として取り出すことができる．この「2」のような数字のことをインデックスと呼ぶ．

配列を使った基本的なプログラミング

配列を使った基本的なプログラムの例をいくつか示す．最初に，配列の中から最大値を求める問題である．

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX 10

int main(void)
{
  int i,max;
  int table[MAX];

  srand(time(NULL));
  for(i=0;i<MAX;i++){
    table[i] = rand() % 100; //0から99の乱数を生成
    printf("%d: %d\n",i,table[i]);
  }

  max = table[0];
  for( i=1; i<MAX; i++){
    if(table[i] > max){
      max = table[i];
    }
  }

  printf("MAX = %d\n", max); 

  return 0;
}

配列の順序を逆にするプログラム例である．

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX 10

int main(void)
{
  int i,tmp;
  int table[MAX];

  srand(time(NULL));
  for(i=0;i<MAX;i++){
    table[i] = rand() % 100; //0から99の乱数を生成
    printf("%d: %d\n",i,table[i]);
  }

  for( i=0; i<MAX/2; i++){
    tmp = table[i];
    table[i] = table[MAX-i-1];
    table[MAX-i-1] = tmp;
  }

  for(i=0;i<MAX;i++){
    printf("%d: %d\n",i,table[i]);
  }

  return 0;
}

配列の応用(スタックとキュー)

配列は，必要に応じてどの要素にも直接アクセスして読み書きすることができる．プログラム中では，エラトステネスのふるいの例のように必要に応じてアクセスをフラグを変更していた．

逆に，配列を使用してもデータの読み書きできる要素に一定のルールに従ってアクセスさせるようにプログラム内容を制限することで，機械的に分かりやすい機能を実現することもできる．ここではスタックとキュー(待ち行列)について説明する．

スタック(stack)は，配列の末尾だけにデータを追加削除できるように制限したものである．

キュー(queue)は，配列の末尾だけにデータを追加できるようにし，先頭だけからデータを取り出すことができるようにしたものである．

スタックとキューについては，別の回に改めて詳しく説明する．