I-14-9. データ構造

データ構造とは何か説明し、線形リスト、ツリー、スタック、キューといった一般的なデータ構造を紹介する。またメモリ管理とデータ構造の関係に触れ、Cプログラムによるデータ構造の実装例を紹介する。

【学習の要点】

* データ構造はアルゴリズムと深く関わる、プログラムの根幹をなすものである。

* 線形リスト、ツリー、スタック、キューといったデータ構造は、ポインタを用いることで実現できる。

図I-14-9. 各データ構造のイメージ図

【解説】

1) データ構造とは

データ構造とは、複数のデータの関連性を表現するモデルである。用いるアルゴリズムによって適切なデータ構造は異なり、その逆でデータ構造によって適切なアルゴリズムも異なる。プログラミングをする上でデータ構造は非常に重要な要素である。

2) 代表的なデータ構造

* 線形リスト

各ノードが次のノードへのポインタを持ち、データが直線状に並んだデータ構造。

* ツリー

各ノードがポインタを二つ以上持ち、それぞれのポインタが下位のノードを指す、データが木のように枝分かれするデータ構造。

* スタック

各ノードが積み重なっており、最後に追加されたデータが最初に取り出される、重ね餅のようなデータ構造。

* キュー

各ノードが積み重なっており、最初に追加されたデータが最初に読みだされる、パイプのようなデータ構造。

3) メモリ管理とデータ構造

各種のデータ構造に適したメモリ割り当てをすることにより、必要最小限のメモリで実装できる。データ構造がメモリ上でどう割り当てられているかを把握することが重要である。

4) データ構造の実装例

ここでは例として、線形リストの実装例を紹介する。

* 構造体のフィールドで、同じ構造体へのポインタを定義

struct linearelem {

char data[100]; // 実際のデータ

struct linearelem *next; // 次の構造体へのポインタを格納

};

* 構造体を3つと構造体へのポインタを宣言

struct linearelem first, second, third, *curr;

* ポインタでつないで線形リストを作成

first.next = &second;

second.next = &third;

* 最初の構造体を指し示す場合

curr = &first;

* 次の構造体を指し示す場合

curr = curr->next;

OSS Course Naviのコンテンツは IPA OSS モデルカリキュラムを基としています。