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

基本データ型

データ構造の説明をする前に，単体のデータ型をおさらいしておく．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;
}

文字列

C言語では文字列は，文字の配列として実現されている．C++やJavaなどのオブジェクト指向言語では，String型のような「オブジェクト」として実現されているため注意が必要である．

  char s[]="abcdef";

このように宣言された場合，s[0]に'a'，s[1]に'b'のように順に格納される．最後はs[5]の'f'ではなく，s[6]の'\0'(ヌル文字)が入っている点に注意すること．最後のヌル文字は文字列の終端を示すマークである．