C言語の基本｜データ構造の基本

C言語の基本｜データ構造の基本

データの持ち方が変われば、処理の流れも変わる。データ構造を理解して、アルゴリズムが動きやすい土台を作ろう。

アルゴリズムは、問題を解決するための手順です。しかし、手順だけを考えても、プログラムをうまく作れないことがあります。

アルゴリズムが扱うデータには、保存する場所や並べ方、取り出し方が必要だからです。

たとえば、複数の点数を小さい順に並べ替えるとします。このとき、点数が一列に並んでいれば、先頭から順番に比較できます。C言語では、このようなデータの並びを配列で表現できます。

また、最後に保存したデータから取り出したい場合と、最初に保存したデータから取り出したい場合では、適した管理方法が異なります。

そこで必要になるのがデータ構造です。

データ構造とは、データをどのような形で保存し、どのような規則で扱うかを表したものです。アルゴリズムが処理の手順を表すのに対して、データ構造は処理対象となるデータの持ち方を表します。

アルゴリズムとデータ構造を組み合わせて考えられるようになると、プログラムの処理手順を整理しやすくなります。

データ構造とは

データ構造は、複数のデータを効率よく管理するための入れ物と規則です。

単に値を保存するだけでなく、次のような点まで含めて考えます。

• いくつのデータを保存するのか
• どのような型のデータを保存するのか
• データをどの順番で並べるのか
• どこからデータを追加するのか
• どこからデータを取り出すのか
• データ同士をどのようにつなぐのか
• 目的のデータをどのように探すのか

1つの整数だけを扱うなら、int型の変数があれば十分です。

同じ種類の整数を複数扱うなら、配列が向いています。名前、年齢、身長のように異なる種類の情報を1つにまとめるなら、構造体が便利です。

保存するデータの内容や処理の目的に合わせて、適切な持ち方を選ぶことが大切です。

アルゴリズムとデータ構造の関係

アルゴリズムとデータ構造には、次のような違いがあります。

アルゴリズムが処理方法を表すのに対して、データ構造はデータの持ち方を表します。

たとえば、複数のデータから最大値を探すアルゴリズムを考えてみましょう。データが配列に保存されていれば、先頭から最後まで順番に調べられます。

一方、データが階層的に保存されている場合は、親から子へたどるような別の手順が必要になります。

同じ目的でも、使用するデータ構造によってアルゴリズムの組み立て方が変わります。

図1：データ構造がアルゴリズムを支える流れ

この図から分かること

最初にデータをどのような形で保存するかを決め、そのデータ構造に合ったアルゴリズムを組み立てます。

配列のようにデータが一列に並んでいれば、先頭から順番に比較、検索、集計できます。スタックのように取り出し順が決まっていれば、その規則に従ってデータを処理します。

データ構造は、アルゴリズムが正しく動くための土台です。入れ物の特徴に合った手順を選ぶことで、処理の流れを分かりやすく設計できます。

C言語で押さえておきたい基本的なデータの持ち方

C言語の学習を始めた段階では、変数、配列、構造体の役割を整理しておくと理解しやすくなります。

変数は、データを保存する最も基本的な単位です。1つの値を分かりやすく管理できます。

配列は、同じ型のデータを複数まとめて保存します。番号を使って各要素を指定できるため、forによる繰り返し処理と相性のよい持ち方です。

構造体は、異なる型のデータを1つのまとまりとして管理します。人物や商品など、複数の項目を持つデータを表現するときに役立ちます。

図2：変数・配列・構造体の違い

この図から分かること

変数は1つの値を保存します。現在の温度や1人分の点数など、単独のデータを扱う場合に適しています。

配列は、同じ型の値を複数並べて保存します。各要素を番号で指定できるため、複数のデータを順番に処理できます。

構造体は、名前、年齢、身長のような異なる種類の情報を1つにまとめます。どれもデータを保存するために使いますが、保存するデータの数や組み合わせ方が異なります。

変数は1つの値を管理する基本の入れ物

変数は、値を保存するための最も基本的な入れ物です。

変数を宣言するときは、保存する値の型と変数名を指定します。整数を保存する場合はint、小数を保存する場合はdoubleなどを使います。

変数は、次のような値を管理する場合に向いています。

• 現在の温度
• 1人分の点数
• 商品の価格
• 繰り返し回数
• 計算の途中結果

1つの変数には、その型に対応した1つの値を保存します。別の値を代入すると、それまで保存されていた値は新しい値に置き換わります。

1回分の温度を変数に保存して表示するプログラム

ファイル名：7_2_1.c

#include <stdio.h>

int main(void)
{
    int temperature = 24;  /* 1回分の温度を保存する */

    printf("現在の温度は%d度です。\n", temperature);
    printf("変数を使って1つの値を管理しています。\n");

    return 0;
}

実行結果の例

現在の温度は24度です。
変数を使って1つの値を管理しています。

変数を使ったプログラムの詳しい解説

このプログラムでは、temperatureという変数に現在の温度を保存しています。

int temperature = 24;では、整数を保存できる変数temperatureを宣言し、初期値として24を代入しています。

最初のprintfでは、変換指定子%dを使ってtemperatureの値を表示します。そのため、実行結果には24度と表示されます。

変数を使うと、数値の意味を変数名で表現できます。式の中に24を直接書くよりも、temperatureという名前を付けたほうが、その値が温度を表していることが分かりやすくなります。

配列は同じ型のデータをまとめて管理する

配列は、同じ型のデータを複数まとめて保存するための仕組みです。

たとえば、5回分の温度を別々の変数で管理すると、temperature1、temperature2のように複数の変数が必要になります。配列を使えば、すべての温度を1つの名前で管理できます。

配列の各データは要素と呼ばれます。それぞれの要素には、先頭を0とする番号が付いています。この番号が添字です。

5個の要素を持つ配列では、次の添字を使用します。

• 先頭の要素は添字0
• 2番目の要素は添字1
• 3番目の要素は添字2
• 4番目の要素は添字3
• 末尾の要素は添字4

添字を変化させれば、forを使って先頭から末尾まで順番に処理できます。

配列は、次のようなアルゴリズムでよく使われます。

• 複数の値の合計を求める
• 平均値を求める
• 最大値や最小値を探す
• 特定の値を検索する
• データを順番に並べ替える

5回分の温度を配列に保存して平均を求めるプログラム

ファイル名：7_2_2.c

#include <stdio.h>

int main(void)
{
    int temperatures[] = {24, 26, 23, 25, 27};
    int count = 5;
    int i;
    int total = 0;
    double average;

    for (i = 0; i < count; i++) {
        total += temperatures[i];
    }

    average = (double)total / count;

    printf("温度の合計は%d度です。\n", total);
    printf("温度の平均は%.1f度です。\n", average);
    printf("配列を使って複数の温度をまとめて処理しました。\n");

    return 0;
}

実行結果の例

温度の合計は125度です。
温度の平均は25.0度です。
配列を使って複数の温度をまとめて処理しました。

配列を使ったプログラムの詳しい解説

temperaturesは、5回分の温度を保存するint型の配列です。

forが始まる前に、totalを0で初期化しています。合計を求める処理では、以前の不要な値が残らないように、加算を始める前の値を0にします。

forでは、iを0から1ずつ増やします。iがcountより小さい間だけ処理するため、iは0、1、2、3、4と変化します。

それぞれの繰り返しで、temperatures[i]の値がtotalに加算されます。

forが終了すると、totalには5回分の温度を加算した125が保存されています。

平均を求めるときは、totalをdouble型にキャストしてからcountで割っています。整数同士で除算すると小数部分が失われるため、先にtotalをdouble型へ変換しています。

その結果、平均値は25.0になります。

配列とforを組み合わせると、要素の数が増えても同じ処理を繰り返して適用できます。複数のデータを集計、検索、並べ替えするときに便利です。

構造体は異なる型の情報を1つにまとめる

配列は、同じ型のデータをまとめる仕組みです。一方、構造体は異なる型のデータを1つのまとまりとして管理できます。

たとえば、学生1人分の情報を管理する場合、次のような項目が必要になります。

• 名前
• 年齢
• 身長
• 体重

名前は文字の並び、年齢は整数、身長や体重は小数として扱うことがあります。このように型が異なる情報は、1つの配列だけで自然にまとめることができません。

構造体を使うと、関連する複数の項目を1人分のデータとしてまとめられます。

構造体の大切な点は、異なる型を保存できることだけではありません。関連する情報を1つの単位として扱えることも大きな特徴です。

学生の名前と点数を別々に管理するよりも、1人分の学生情報としてまとめたほうが、データ同士の関係を理解しやすくなります。

配列や構造体から作れる代表的なデータ構造

C言語には、スタック、キュー、リスト、ハッシュ、木が完成した機能として最初から用意されているわけではありません。

これらは、配列、構造体、ポインタなどを組み合わせて作ります。

それぞれの違いを理解するときは、データをどのような規則で追加し、どこから取り出すのかに注目すると分かりやすくなります。

スタックは最後に入れたデータから取り出す

スタックは、最後に入れたデータを最初に取り出すデータ構造です。この規則をLIFOといいます。

LIFOはLast In, First Outの略で、後入れ先出しを表します。

本や皿を下から順番に積み重ねる場面を考えると分かりやすいでしょう。途中にあるものを取り出すのではなく、一番上にあるものから取り出します。

スタックでは、主に次の操作を行います。

最初に101、次に205、最後に318を追加した場合、取り出す順番は318、205、101になります。

配列を使って後入れ先出しを確認するプログラム

ファイル名：7_2_3.c

#include <stdio.h>

int main(void)
{
    int stack[3];
    int top = 0;  /* 次にデータを入れる位置 */

    /* pushでデータを順番に追加する */
    stack[top++] = 101;
    stack[top++] = 205;
    stack[top++] = 318;

    /* popで最後に追加したデータから取り出す */
    printf("取り出し1: %d\n", stack[--top]);
    printf("取り出し2: %d\n", stack[--top]);

    printf("スタックは最後に入れたデータから取り出します。\n");

    return 0;
}

実行結果の例

取り出し1: 318
取り出し2: 205
スタックは最後に入れたデータから取り出します。

スタックを使ったプログラムの詳しい解説

このプログラムでは、要素数3の配列stackを使って、スタックの基本的な動きを表現しています。

topは、次にデータを保存する配列の位置を表しています。最初は0なので、101はstack[0]に保存されます。その後、後置インクリメントによってtopが1になります。

同じように、205はstack[1]、318はstack[2]に保存されます。3つの値を追加した時点で、topは3です。

データを取り出すときは、前置デクリメントでtopを先に1つ減らします。

最初のstack[--top]では、topが3から2になります。そのため、stack[2]に保存されている318が取り出されます。

2回目はtopが2から1になり、stack[1]に保存されている205が取り出されます。

最後に追加した318が最初に取り出されるため、スタックの後入れ先出しを確認できます。

このプログラムはスタックの動きを確認するための簡単な例です。実際にスタックを作るときは、配列の大きさを超えて追加しないことや、空の状態から取り出さないことも確認する必要があります。

キューは最初に入れたデータから取り出す

キューは、最初に入れたデータを最初に取り出すデータ構造です。この規則をFIFOといいます。

FIFOはFirst In, First Outの略で、先入れ先出しを表します。

レジやATMの待ち行列を考えると分かりやすいでしょう。先に並んだ人から順番に案内され、後から来た人は列の後ろに並びます。

キューでは、主に次の操作を行います。

101、205、318の順番で追加した場合、取り出す順番も101、205、318になります。

配列で単純なキューを作ると、先頭の要素を取り出した後に、残りの要素を前へ移動させる方法があります。ただし、取り出すたびに要素を移動すると処理が増えます。

そこで、先頭位置と末尾位置を別々に管理する方法などが使われます。

図3：スタックとキューの取り出し順

この図から分かること

スタックとキューは、どちらも複数のデータを順番に管理しますが、取り出す位置が異なります。

スタックでは、最後に追加した318から取り出します。新しいデータを上に積み、上から取り出す構造です。

キューでは、最初に追加した101から取り出します。新しいデータを後ろに追加し、前から順番に取り出します。

どちらが優れているというものではありません。最後の操作から元に戻りたい場合はスタック、受け付けた順番に処理したい場合はキューというように、目的に合った規則を選びます。

リストはデータ同士のつながりを管理する

配列の要素は、メモリ上で連続して並びます。そのため、途中に新しい要素を追加したり、途中の要素を削除したりする場合は、ほかの要素を移動させることがあります。

リストは、データそのものと次のデータへのつながりを使って管理するデータ構造です。

それぞれの要素が次の要素を示すことで、データの並びを表現します。追加や削除の対象となる位置が分かっていれば、配列のように後ろの要素をまとめて移動せず、つながりを変更できます。

リストは、次のようなデータのイメージに近い構造です。

• 作業項目を並べるTo-Doリスト
• 曲の順番を管理する再生リスト
• 順番にたどるデータ
• 途中で追加や削除が行われるデータ

C言語では、構造体とポインタを組み合わせてリストを作れます。

ハッシュはキーを使って値を探す

ハッシュは、キーと値を対応させて管理するデータ構造です。

たとえば、次のような対応関係を管理できます。

• 名前から電話番号を探す
• 商品番号から商品情報を探す
• 単語から意味を探す
• 会員番号から会員情報を探す

ハッシュでは、キーからデータの保存位置を求めます。適切に作られていれば、多くのデータを先頭から順番に調べなくても、目的の値を効率よく探せます。

ただし、異なるキーから同じ保存位置が求められることもあります。その場合に、データをどのように保存して探すかという工夫が必要になります。

木は階層のあるデータを管理する

木は、データ同士の親子関係を表現するデータ構造です。ツリーとも呼ばれます。

1つの親データから複数の子データへ枝分かれすることで、階層的な構造を表します。

木は、次のようなデータを管理するときに向いています。

• フォルダとファイルの構成
• 会社の組織図
• 分類された商品カテゴリー
• 親子関係を持つデータ
• 選択肢が枝分かれする処理

配列はデータを一列に並べますが、木はデータを階層として管理します。そのため、親から子へ順番にたどるアルゴリズムが必要になります。

目的に合ったデータ構造を選ぶ

データ構造を選ぶときは、プログラムでどのような操作を多く行うかを考えます。

複数の値を順番に調べたい場合は配列が分かりやすい選択です。配列は添字で要素を指定できるため、forを使った繰り返し処理にも向いています。

直前の操作を元に戻すような処理では、最後に追加したデータから取り出すスタックが適しています。

依頼や処理を受け付けた順番に実行する場合は、最初に追加したデータから取り出すキューが自然です。

商品番号や名前などのキーから対応する情報を探す処理では、ハッシュが候補になります。フォルダや組織図のような階層を表現したい場合は、木が適しています。

データ構造を選ぶことは、単にデータを保存する箱を選ぶことではありません。その後にどのようなアルゴリズムを組み立てるかを決める、大切な設計作業です。