本章では、基本的なデータ構造を紹介するとともに、Ｃ言語で基本データ構造を実現する際の注意点について説明する。
２．１ 基本データ構造
基本的なデータ構造の概要を説明する。本章で説明したデータ構造は、以下の章において、抽象データ型の考えに基づいて課題を記述し解く際に用いられるものである。
○配列（array）
|
|
a[0]
|
a[1]
|
･ ･ ･
|
|
|
a[i]
|
･ ･ ･ |
| |
|
|
・ランダムアクセス可能
・要素の位置を指定してアクセス
○行列、２次元配列（matrix）
ｍ 0列 1列 j列
|
|
m[0][0] |
m[0][1] |
･ ･ ･ |
|
|
| m[0][j] |
･ ･ ･ |
m[1][0] |
m[1][1] |
･ ･ ･ |
m[1][j] |
|
|
| ･ ･ ･ |
･ ･ ･ |
･ ･ ･ |
･ ･ ･ |
･ ･ ･ |
|
|
| ･ ･ ･ |
m[i][0] |
m[i][1] |
･ ･ ･ |
m[i][j] |
|
|
| ･ ･ ･ |
･ ･ ･
|
･ ･ ･
|
･ ･ ･
|
･ ･ ･
|
|
|
･ ･ ･
|
|
・ランダムアクセス可能
・要素の位置（行と列）を指定してアクセス
○待ち行列、キュー（queue）
ＦＩＦＯ(First-In First-Out)：最初に入れたものが最初に出てくる
enqueue: 入れる dequeue: 出す
３ １
○スタック（stack）
ＬＩＦＯ(Last-In First-Out)：最後に入れたものが最初に出てくる
push: 入れる pop: 出す
３ ３
○線形リスト（linear list）
10番地 20番地
・セル：情報部、アドレス部（次のセルへのポインタ）
・先頭からのシーケンシャルアクセスのみ可能
○双方向リスト（doubly linked list）
・セル：情報部、前のセルへのポインタ、次のセルへのポインタ
・先頭からのシーケンシャルアクセスと逆方向のアクセス可能
○木（tree）
根(Root)
レベル０ ○ 節点(Node)
木の深さ
枝(Edge)
レベル１ ○ ●
木の高さ
レベル２ ● ● ● 葉(Leaf)
親節点（Parent Node）
枝で接続された上位の（レベルの小さい）節点
子節点（Child Node）
枝で接続された下位の（レベルの大きい）節点
兄弟節点（Sister Node）
親節点が同じ節点
・セル：情報部、子節点へのポインタ
・ｎ分木：節点から出る枝の数が高々ｎの木
・２分木：節点から出る枝の数が２つ以下の木
左側の子節点以下の木を左部分木、右側の子節点以下の木を右部分木と呼ぶ。
○
問 2.1.1 上記の各基本データ構造を利用している応用例にはどのようなものがあるか。
問 2.1.2 上記の各基本的データ構造を標準で提供しているプログラミング言語にはどのようなものがあるか。
問 2.1.3 スタック操作あるいはリスト操作を基本とする計算機について調べよ。
２．２ Ｃ言語による基本データ構造の実現
基本データ構造をＣ言語によって実現する際に必要な事柄について説明する。
○構造体
複数の変数をまとめて一つの変数として取り扱うための仕組みである。構造体をレコードと考えると、その要素である各変数は、フィールドとみなすことができる。
＜例＞ 氏名、年齢、身長、体重フィールドから構成されるレコード person_rec の定義
struct {
char name[20]; /* 名前フィールド */
int age, height, weight; /* 年齢、身長、体重フィールド */
} person_rec;
構造体の要素は、構造体変数名.要素変数名という形式で指定する。
＜例＞ 氏名、年齢を出力する
printf("Name: %s, Age: %d\n", person_rec.name, person_rec.age);
○アドレス
変数はメモリ上に割り当てられ、データはメモリに書き込まれる。その変数のメモリ上の位置がアドレスであり、&変数名という形式で指定する。ただし、配列に関しては、変数名そのものでアドレスを表す。
＜例＞ 整数 x と文字配列 s のアドレスを出力する
int x; char s[20];
printf("Address of x = %d\n", &x);
printf("Address of s = %d\n", s); （&s[0]も可）
○ポインタ変数
データそのものではなく、データのアドレスを記憶している変数である。
＜例＞ ポインタ p とデータ x, y の関係
100番地
200番地
ポインタの内容はデータのアドレスであり、ポインタの指すデータは、*ポインタ変数名により参照する。
＜例＞ データ x とデータ y をポインタ p により参照する
int x, y, *p; /* 整数型 x,y とポインタ p を宣言する */
p=100; /* p に 100番地（x）を指させる */
printf("x=%d\n", *p); /* p の指す x の値を出力する */
p=&y; /* p に y の番地を指させる */
printf("y=%d\n", *p); /* p の指す y の値を出力する */
○マトリックス
２次元の配列である。データ型 変数名[行数][列数] により、配列の大きさを宣言する。変数名[行] により各行を１次元の配列とみなすことができる。
＜例＞ 10 行 5 列の整数型のマトリックス
int m[10][5];
int *p; /* 整数型のポインタ変数 */
printf("m[1][1]=%d\n", m[1][1]);/* 1 行 1 列の要素を参照 */
p=m[1]; /* p に 1 行目のアドレスを代入
p=&m[1][0]; と等価 */
printf("m[1][1]=%d\n", p[1]); /* m[1][1] と等価な処理 */
○関数と返り値（return value）
関数は１つの関数値しか返すことができない。複数の値を返したい場合には、引数に変数のアドレスを指定し、関数中でそのアドレスに値を代入する。
＜例＞ x と y から x+y と x-y を計算して返す関数
void add_sub(int x, int y, int *addp, int *subp);
/* 利用する前に関数を宣言する */
void main(void)
{
int add, sub;
add_sub(100, 200, &add, &sub);
/* add と sub のアドレスを渡す */
printf("x+y=%d, x-y=%d\n", add, sub);
}
void add_sub(int x, int y, int *addp, int *subp)
{ /* アドレスをポインタ変数として宣言 */
*addp=x+y; /* 呼び出し側の add に値を代入 */
*subp=x-y; /* 呼び出し側の sub に値を代入 */
}
○typedef
Ｃ言語には整数型（int）、文字型（char）、実数型（float）などの型が定義されているが、これら既存の型を組み合わせて新しいユーザ定義のデータ型を宣言する。
＜例＞ 氏名、年齢、身長、体重フィールドからなる PersonRec 型を宣言する
typedef struct {
char name[20];
int age, height, weight;
} PersonRec, *Person;
○構造体へのポインタ
ポインタの指すデータが構造体である場合には、ポインタ変数名->要素変数名により各要素を参照する。
＜例＞ PersonRec 型の変数および PersonRec 型へのポインタ変数
PersonRec person_rec; /* PersonRec 型構造体変数の宣言 */
Person person; /* PersonRec 型へのポインタの宣言 */
person=&person_rec; /* person に person_rec を指させる
（person_rec のアドレスを代入） */
person_rec.age=20; /* person_rec.age に 20 を代入 */
person->age=20; /* ○->○ による等価な処理 */
*person.age=20; /* *○.○ による等価な処理 */
●リスト構造
情報部と次のセルへのポインタ部を持つリスト構造のセルを定義する。
typedef struct cell {
DATATYPE info; /* データ型 DATATYPE の情報部 */
struct cell *next; /* 次のセルへのポインタ */
} CellRec, *Cell;
＜例１＞ ２要素からなるリスト
CellRec cell_1, cell_2; /* ２つのリストセル */
cell_1.next=&cell_2; /* セルの接続 */
cell_2.next=NULL; /* セルの終端 */
cell_1 cell_2
＜例２＞ ポインタによる処理
Cell p=&cell_1, q=&cell_2; /* ポインタにセルを指させる */
p->next=q; /* セルの接続 */
q->next=NULL; /* セルの終端 */
●木構造
情報部と２つの子節点へのポインタを持つ２分木の木構造のセル（節点）を定義する。
typedef struct node {
DATATYPE info;
struct node *left; /* 左部分木へのポインタ */
struct node *right; /* 右部分木へのポインタ */
} NodeRec, *Node;
＜例１＞ ３要素からなる木
NodeRec parent, child_1, child_2;
parent.left=&child_1; /* セル（左部分木）の接続 */
parent.right=&child_2; /* セル（右部分木）の接続 */
child_1.left=child_1.right=NULL;/* セルの終端 */
child_2.left=child_2.right=NULL;
parent
child_1 child_2
＜例２＞ ポインタによる処理
Node p=&parent, l=&child_1, r=&child_2;
p->left=l; /* セル（左部分木）の接続 */
p->right=r; /* セル（右部分木）の接続 */
l->left=l->right=NULL; /* セルの終端 */
r->left=r->right=NULL;
問 2.2.1 キューおよびスタックに対応するデータ型として、どのような定義が可能かを考えよ。
問 2.2.2 双方向リストのセルに対応するデータ型を定義せよ。
問 2.2.3 ｎ分木の節点に対応するデータ型を定義せよ。
２．３ ＵＮＩＸにおけるＣ言語の利用方法
本講義はＵＮＩＸワークステーション上で行なうので、Ｃコンパイラの簡単な使用方法を説明する。
○１つのファイルの場合
＜例１＞ ソースファイル hello.c をコンパイルして a.out を生成し、実行する
% cc hello.c a.out が生成される
% a.out
＜例２＞ ソースファイル hello.c をコンパイルして hello を生成し、実行する
% cc -o hello hello.c hello が生成される
% hello
＜例３＞ 最適化を行う（-O オプション）
% cc -O -o hello hello.c
○複数のファイルの場合
＜例１＞ main.c, sub.c をコンパイルして main を生成する
% cat main.h
#define SUB "sub"
% cat main.c
#include "main.h"
void main(void)
{
printf("main\n");
sub(SUB);
}
% cat sub.c
void sub(char *msg)
{
printf("%s\n", msg);
}
% cc -o main main.c sub.c
＜例２＞ オブジェクトファイルを生成し、それを結合する
% cc -c main.c main.o が生成される
% cc -c sub.c sub.o が生成される
% cc -o main main.o sub.o
○Makefile の利用
Makefile という名前のファイルを以下のような内容で作成する。
ターゲットのリスト: 依存ファイルのリスト 依存ファイルからターゲットを生成するコマンド
|
このファイルを定義し、make コマンドを実行すると、ターゲットが依存ファイルより古くなっているかどうかを判定し、古くなっていれば自動的にコマンドを実行して、ターゲットを最新のものに更新する。
＜例＞ main.c, sub.c から main を生成するための Makefile。なお、main.h というヘッダファイルは main.c がインクルードしている。
OBJS=main.o sub.o
main: $(OBJS)
cc -o main $(OBJS)
main.o: main.h main.c main.c は省略可能
sub.o: 省略可能
実行の様子を以下に示す。
% make
`main' is up to date. main は最新の状態である
% rm *.o オブジェクトファイルを強制的に削除
% make
cc -c main.c
cc -c sub.c
cc -o main main.o sub.o