2005年度 データ構造とアルゴリズム 第３回 「C言語の復習：再帰的データ構造」 西尾 信彦 [email protected] 立命館大学情報理工学部 情報システム学科 配列で何でもできる！わけではない？ • 配列に身長データを格納する – 学生番号順に格納した – 身長順にしたい – 身長順の添字をデータとする別の配列を用意 • 2つ配列があるのは面倒なのでひとつにしよう – 2次元配列か構造体(どちらでもいいがここでは構造体にする) – ひとつの要素に2つのデータ(身長と順番) – ひとつにする意味が希薄 • データの増減時に大変面倒、全書換えが起きる • 自分の次に背の高いデータの添字を格納して解決！ 構造体を定義しよう • 配列と似ている、違うのは異なった型のデータ を集めているところ – – – – – – このため定義が面倒、長くなる char line[100]; struct { int data; 黄色が型定義 char name[100]; 毎回書くのは面倒 int *pointer; 型に名前をつけよう } taro; struct student {…} taro; と一度定義したら後は struct student型として使える。{…}が省略できる 構造体の例： #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 動的メモリ管理 • いままでは、プログラムが動く前にすべての変 数が定義されていた。 – 静的変数という • プログラムが動いた結果、必要な変数がわかる ような場合は、プログラム実行中に変数を作り たい – これを動的というが、変数としての名前がついてな い。データを格納するメモリ領域を確保するだけ – 名前がないのでプログラム中ではポインタを用いて アクセスする。 何がどれだけ欲しいのか？ • どれだけというのはメモリのサイズ(バイト数)のこ と – sizeof演算子を使おう – sizeof(struct student)という演算をするとstruct Student 型のデータを格納するのに必要なバイト数が整数とし て計算される • malloc関数にメモリ領域を確保してもらえる – struct student型のデータを100個格納する領域は – malloc(sizeof(struct student) * 100) – のように確保する 動的メモリ確保の例： #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! p: q: a: 3 図に示すデータ構造をC言語のプログラムソースで書 き、qを使って変数aの中身を表示しなさい。 a l g o r i t h m \0 *str メモリ空間上のある場所に、上図のように文字列が格納さ れており，ポインタ変数strは矢印のアドレスを指す。この時， *(str+4)は何を指すか。それを確認するプログラムソースを 書きなさい。
© Copyright 2024 ExpyDoc
