プログラミング応用演習 第 4 回再帰的構造体
プログラミングを 余談 : 教えることの難しさ 丁寧に説明しないと分かってもらえない 説明すると 小難しくなる学生が目指すべきところプログラム例を説明されて理解できる違うやり方でも良いので自力で解決できる おっけー 動けば良い という意識でプログラミング 正しく動くことのチェックは必要 解答例と自分のやり方との比較が勉強になる
今日のお題 再帰的構造体 malloc と free
( 連結 ) リスト構造 吉田先生の データ構造とアルゴリズム でやりましたね? こんなデータ構造を作りたい : 21 33 39 ここで使われているを どう表現するか? これ ( ここではデータとポインタの組 ) をセル (cell) と呼ぶ struct cell { int data; ; struct cell *next; // データ // 次のセルへのポインタ 構造体の定義の中に同じ構造体へのポインタがある こうして循環する構造体を再帰的構造体という
再帰的構造体でポインタを使う理由 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; ここで定義しようとしている構造体へのポインタをメンバとする ( 再帰的構造体 ) このとき typedef と構造体の宣言を同時にする場合でも 構造体の名前を省略できない 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 39 x 33 stack r??
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 する といったメモリ管理を行うプログラムを書くこともある