2005年度 データ構造とアルゴリズム 第３回 「C言語の復習：再帰的データ構造」 西尾 信彦 nishio@cs.ritsumei.ac.jp 立命館大学情報理工学部 情報システム学科

配列で何でもできる！わけではない？ 配列に身長データを格納する 2つ配列があるのは面倒なのでひとつにしよう 学生番号順に格納した 身長順にしたい 身長順の添字をデータとする別の配列を用意 2つ配列があるのは面倒なのでひとつにしよう 2次元配列か構造体(どちらでもいいがここでは構造体にする) ひとつの要素に2つのデータ(身長と順番) ひとつにする意味が希薄 データの増減時に大変面倒、全書換えが起きる 自分の次に背の高いデータの添字を格納して解決！

構造体を定義しよう 配列と似ている、違うのは異なった型のデータを集めているところ このため定義が面倒、長くなる char line[100]; 黄色が型定義 毎回書くのは面倒 型に名前をつけよう struct student {…} taro; と一度定義したら後はstruct student型として使える。{…}が省略できる struct { int data; char name[100]; int *pointer; } taro;

構造体の例： 実行結果： #include <stdio.h> #include <string.h> int main(){ struct student{ /* 構造体の定義 */ char name[40]; int height; }A_san = {"Ritsumei Taro", 172}, B_san; /* 変数A_sanは宣言と同時に初期化 */ strcpy(B_san.name, "Kinugasa Hanako"); /* B_sanのnameに値を代入 */ B_san.height = 155; /* B_sanのheightに値を代入 */ struct student *pointer; /* 構造体へのポインタを定義 */ pointer = &B_san; /* struct student型のB_sanのアドレスを代入 */ /* 構造体変数A_sanのメンバを表示 */ printf("A_san: Name=\"%s\" Height=%d\n", A_san.name, A_san.height); /* 構造体へのポインタを使って構造体のメンバへアクセス */ printf("B_san: Name=\"%s\" Height=%d\n", pointer->name, pointer->height); } 実行結果： A_san: Name=“Ritsumei Taro" Height=172 B_san: Name=“Kinugasa Hanako" Height=155

自分の隣りのデータを指し示す それがリストの本質 構造体のメンバは 添字で指していたものをポインタで指そう 自分のデータと 自分の次のデータのある場所へのポインタ まだ構造体型が定義できる前 にそれを参照している 自分で自分を参照(再帰的参照) ポインタというデータはサイズが 変らないので許されている struct student { int data; struct student *next; } table[100];

静的な構造体によるリストの例(教科書p.21)： #include <stdio.h> int main(){ struct _elem{ /* 構造体の定義 */ int height; struct _elem *next; }a[5]; struct _elem *p; /* 構造体へのポインタの定義 */ /* 構造体の配列のメンバheightにデータを代入 */ a[0].height = 174; a[1].height = 158; a[2].height = 166; a[3].height = 170; a[4].height = 162; /* 各構造体を繋ぐ */ a[1].next = &a[4]; a[4].next = &a[2]; a[2].next = &a[3]; a[3].next = &a[0]; a[0].next = NULL; for(p = &a[1]; p != NULL; p = p->next){ printf("%d\n", p->height); } 実行結果 158 162 166 170 174

動的メモリ管理 いままでは、プログラムが動く前にすべての変数が定義されていた。 静的変数という プログラムが動いた結果、必要な変数がわかるような場合は、プログラム実行中に変数を作りたい これを動的というが、変数としての名前がついてない。データを格納するメモリ領域を確保するだけ 名前がないのでプログラム中ではポインタを用いて アクセスする。

何がどれだけ欲しいのか？ どれだけというのはメモリのサイズ(バイト数)のこと malloc関数にメモリ領域を確保してもらえる sizeof演算子を使おう sizeof(struct student)という演算をするとstruct Student型のデータを格納するのに必要なバイト数が整数として計算される malloc関数にメモリ領域を確保してもらえる struct student型のデータを100個格納する領域は malloc(sizeof(struct student) * 100) のように確保する

動的メモリ確保の例： 実行結果： Dynamic Storage Allocation! #include <stdio.h> #include <stdlib.h> #include <string.h> int main(){ char *str; str = (char *)malloc(sizeof(char) * 128); /* 文字列のために動的にメモリを確保 */ if(str == NULL){ /* エラー処理 */ printf("メモリが確保できません\n"); exit(1); } strcpy(str, "Dynamic Storage Allocation!\n"); /* 文字列をコピー */ printf("%s\n", str); /* 文字列の表示 */ free(str); /* 動的に確保した領域を解放する */ 実行結果： Dynamic Storage Allocation!

3 a: p: q: 図に示すデータ構造をC言語のプログラムソースで書き、qを使って変数aの中身を表示しなさい。

a l g o r i t h m \0 *str メモリ空間上のある場所に、上図のように文字列が格納されており，ポインタ変数strは矢印のアドレスを指す。この時，*(str+4)は何を指すか。それを確認するプログラムソースを書きなさい。