プログラミング応用演習 第 4 回再帰的構造体
前回の出席確認演習 #include <stdio.h> int main() { FILE *fp; int c, linecount, length, maxlength; fp=fopen("/usr/share/dict/words","r"); if (fp == NULL) return 1; linecount=0; length=0; maxlength=0; while((c=fgetc(fp))!= EOF) { if (c == '\n') { linecount++; if (maxlength < length) maxlength=length; length=0; else { length++; printf("linecount: %d\n",linecount); printf("maxlength: %d\n",maxlength); return 0;
前回の出席確認演習 求めなければならない情報は何か? 最長の行の長さ 各行の長さ ファイルの終了まで 1byte ずつ読むことを繰り返すサンプルが与えられている この繰り返しの中で各行の長さをどのように求めるか?
各行の長さを求める 読んでいるファイルの内容 \n a b o u n d s \n a b o u t \n a b o v e \n 0 1 2 3 4 5 6 7 0 1 2 3 4 5 0 1 2 3 4 5 0 改行を読んだら 0 になる 1byte 読むごとに 1 ずつ増える 次の改行を読んだら 0 にする前に長さが分かる こう変化する値があれば良い 最初は 0 にしておく
最大の長さを求める 暫定の最大値を用意しておく これまでに読んだ中で最長のものの長さ 最初は小さな値 ( 例えば 0) にしておく 長さが一つ分かるごとに 暫定の最大値と比較し より長ければ暫定最大値を更新 全部読むと 暫定ではなく 最大値となる
前回の出席確認演習 ( 再掲 ) #include <stdio.h> int main() { FILE *fp; int c, linecount, length, maxlength; fp=fopen("/usr/share/dict/words","r"); if (fp == NULL) return 1; linecount=0; length=0; maxlength=0; while((c=fgetc(fp))!= EOF) { if (c == '\n') { linecount++; if (maxlength < length) maxlength=length; length=0; else { length++; 各行の長さ 改行でないときに 1 増やす printf("linecount: %d\n",linecount); printf("maxlength: %d\n",maxlength); 最大の長さ length の方が長ければ maxlength を更新する 改行であれば 0 にする return 0;
今日のお題 再帰的構造体 malloc と free
( 連結 ) リスト構造 吉田先生の データ構造とアルゴリズム でやりましたね? こんなデータ構造を作りたい : 21 33 39 ここで使われているを どう表現するか? これ ( ここではデータとポインタの組 ) をセル (cell) と呼ぶ struct cell { int data; ; struct cell *next; // データ // 次のセルへのポインタ 構造体の定義の中に同じ構造体へのポインタがある こうして循環する構造体を再帰的構造体という
再帰的構造体でポインタを使う理由 struct cell { ; int data; struct cell next; next をポインタではなく構造体そのものにすると コンパイルエラーになる この構造体のメモリイメージは? struct cell の記憶場所 int の記憶場所 パディング
再帰的構造体でポインタを使う理由 struct cell { ; int data; struct cell next; next をポインタではなく構造体そのものにすると コンパイルエラーになる この構造体のメモリイメージは? struct cell の記憶場所
再帰的構造体でポインタを使う理由 struct cell { ; int data; struct cell next; next をポインタではなく構造体そのものにすると コンパイルエラーになる この構造体のメモリイメージは? この構造体は大きさを決められない ( 無限大 ) 無限に続く ポインタ型の記憶領域のサイズは どれも同じ printf("%lu\n",sizeof(int*)); printf("%lu\n",sizeof(double*)); printf("%lu\n",sizeof(struct cell*));
リスト構造の終端 この斜線は何? 21 33 39 リストの最後なので 次は 無い 無いことを示す特別なポインタ値を入れておく 多くの場合 NULL を使う ちなみに 何もないことを Java では null と小文字で表記する C 言語では大文字で表記するので 間違えないように
プログラム例 #include <stdio.h> typedef struct _cell { int data; struct _cell *next; cell; void printlist(cell *p) { printf("( "); while( p!= NULL ) { printf("%d ",p->data); p = p->next; printf(")\n"); int main() { cell a,b,c; a.data=21; a.next=&b; b.data=33; b.next=&c; c.data=39; c.next=null; printlist(&a); return 0; a b c 21 33 39
ほかの再帰的構造の例 2 分木 これらの構造の単位を C 言語で表現してみよう 双方向リスト 双方向木
ほかの再帰的構造の例 2 分木 typedef struct _cell { int data; struct _cell *left; struct _cell *right; ; 双方向リスト typedef struct _cell { int data; struct _cell *left; struct _cell *right; ; 双方向木 typedef struct _cell { int data; struct _cell *parent; struct _cell *left; struct _cell *right; ;
動的メモリ割り付け 特に型を定めないポインタ long unsigned int の別名 void *malloc(size_t size); OS に size byte のメモリを要求する 成功すれば 先頭のポインタを返す 失敗すれば ( メモリが枯渇するなど ) NULL を返す 必要に応じて メモリを確保して使う : 動的メモリ割り付け 不要になったら 解放する (OS に通知する ): void free(void *ptr); 解放するメモリ領域の先頭のポインタを渡す
リスト構造を使ったスタック (1) #include <stdio.h> #include <stdlib.h> /* 連結リストの cell の定義 */ cell *push(int x, cell *stack) { cell *r = malloc(sizeof(cell)); if (r == NULL) { fprintf(stderr,"stack overflow\n"); exit(1); r->data = x; r->next = stack; return r; cell *pop(cell *stack) { cell *r; if (stack == NULL) { fprintf(stderr,"stack underflow\n"); exit(1); r = stack->next; free(stack); return r; push int top(cell *stack) { return stack->data; /* printlist の定義 */ int main() { cell *root = NULL; root = push(39,root); root = push(33,root); root = push(21,root); printlist(root); return 0; pop
push の様子 root x 39 stack r??
push の様子 root x 39 stack r 39
push の様子 root x 39 stack r 39
push の様子 ( 二つ目 ) root 39 x 33 stack r??
push の様子 ( 二つ目 ) root 39 x 33 stack r 33
push の様子 ( 二つ目 ) root 39 x 33 stack r 33
push の様子 ( 二つ目 ) root 39 x stack malloc で確保したメモリ領域は free するまで有効 33 x, stack, r の有効範囲は push 関数の中だけ r 33
ポインタのポインタ root ( こっちだけ ) どちらも cell* 型
ポインタのポインタ root cell のメンバ next の記憶領域を指す ポインタ値が入る記憶領域を指すポインタを考えることもできる これの型は cell**
リスト構造を使ったスタック (2) #include <stdio.h> #include <stdlib.h> /* 連結リストの cell の定義 */ /* printlist の定義 */ void push(int x, cell **stack) { cell *r = malloc(sizeof(cell)); if (r == NULL) { fprintf(stderr,"stack overflow\n"); exit(1); r->data = x; r->next = *stack; *stack = r; int pop(cell **stack) { int d; cell *r = *stack; if (*stack == NULL) { fprintf(stderr,"stack underflow\n"); exit(1); d = (*stack)->data; *stack = (*stack)->next; free(r); return d; int main() { cell *root = NULL; push(39,&root); push(33,&root); push(21,&root); printlist(root); return 0;
おまけ : 現実的なメモリ管理 malloc や free は OS にメモリ管理を依頼する OS の機能を呼び出す : システムコール OS はそれなりの作業をして返す 人間の感覚では瞬時とはいえ 多少の時間がかかる システムコールのオーバーヘッド 回数が多いときには無視できなくなる オーバーヘッドを減らすために malloc( や free) の回数を減らす : まとめて malloc して 少しずつ使う / まとめて free する といったメモリ管理を行うプログラムを書くこともある