アルゴリズムとデータ構造 補足資料11-1 「mallocとfree」 横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

メモリの「物理的」な構成 Random Access Memory (RAM) 「アドレス」と「中身」 有限個のセル（資源） CPUは、メモリに対して次の操作を行う アドレスを指定して、その内容を読み出す(load) アドレスを指定して、その内容を書き込む(store) CPUの演算と比べれば、読み書きには「それなりに」時間がかかる e.g. メモリバスの周波数は、CPUの内部周波数の1/10程度 アドレスの指定は「任意」 どのアドレスを指定しても、読み書きが可能 Random Access Memory と呼ばれる 2次記憶と比べれば、「そこそこ速く」読み書きが可能 c.f. Sequential Access Device （ディスクやテープ；ディスクはアドレス指定が可能だが、「極めて遅い」） メモリの中身の種類 データ アドレス プログラム（命令）

printf(“a:%x = %d\n”, &a, a); return 0; } アドレス（32bit） 中身（1記憶単位は8bit） … 0x 40ea 0800 1101 0000 0x 40ea 0801 0000 0111 0x 40ea 0802 0100 1011 0x 40ea 0803 1011 1111 0x 40ea 0804 0000 0000 0x 40ea 0805 0x 40ea 0806 0x 40ea 0807 0001 0100 0x 40ea 0808 0100 0001 0x 40ea 0809 1011 0111 0x 40ea 080a 0x 40ea 080b 0x 40ea 080c 0100 1100 0x 40ea 080d 0110 1111 0x 40ea 080e 1010 0111 0x 40ea 080f 0101 0000 0x 40ea 0810 int main(void) { int a; a = 20; printf(“a:%x = %d\n”, &a, a); return 0; } &a a 実行すると、以下の結果が出た。 a: 40ea0804 = 20 この場合のaは？ 　→int型（32bitの箱）の変数aは、 　　中身が20 （2進数では10100） 00000000 00000000 00000000 00010100 a int 型（32bit） aは、物理的にどこに存在する？ 　→ 記憶（メモリ）の中 　　 （ＯＳに割り当ててもらう； 毎回変わる） aは、具体的にどこ？ 　→ 今回は0x 40ea 0804番地からの4バイト分 　→ &a == 0x 40ea 0804 （aのアドレス）

アドレス（32bit）, 4アドレス飛び この場合のaは？ →int型（32bitの箱）の変数aは、 中身が20 （16進数では14） &a 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 0x d007 4bbf 0x 40ea 0804 0x 0000 0014 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 0000 0000 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x ef5c 2100 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 0x 40ea 082c 0x 1101 0000 0x 40ea 0830 0x 0100 1100 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 この場合のaは？ 　→int型（32bitの箱）の変数aは、 　　中身が20 （16進数では14） &a a 00000000 00000000 00000000 00010100 a int 型（32bit） 変数aのアドレスは、 　　0x 40ea0804番地

printf(“a:%0x = [%d, %0x]\n”, p, a.key, a.next); return 0; } アドレス（32bit）, 4アドレス飛び 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 0x d007 4bbf 0x 40ea 0804 0x 0000 0014 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 0000 0000 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x ef5c 2100 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 0x 40ea 082c 0x 1101 0000 0x 40ea 0830 0x 0100 1100 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 struct list { int key; struct list *next; }; int main(void) { struct list a, *p; a.key = 20; a.next = NULL; p = &a; printf(“a:%0x = [%d, %0x]\n”, p, a.key, a.next); return 0; } 変数によるプログラム： プログラム中では、 変数の枠は動かない

printf(“a:%0x = [%d, %0x]\n”, p, a.key, a.next); return 0; } &a a アドレス（32bit）, 4アドレス飛び 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 0x d007 4bbf 0x 40ea 0804 0x 0000 0014 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 0000 0000 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x ef5c 2100 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 0x 40ea 082c 0x 1101 0000 0x 40ea 0830 0x 0100 1100 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 struct list { int key; struct list *next; }; int main(void) { struct list a, *p; a.key = 20; a.next = NULL; p = &a; printf(“a:%0x = [%d, %0x]\n”, p, a.key, a.next); return 0; } &a a a.key a.next p 変数によるプログラム： プログラム中では、 変数の枠は動かない

printf(“a:%0x = [%d, %0x]\n”, p, a.key, a.next); return 0; } &a a アドレス（32bit）, 4アドレス飛び 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 20 0x 40ea 0804 0x 0000 0014 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 0000 0000 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x ef5c 2100 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 0x 40ea 082c 0x 1101 0000 0x 40ea 0830 0x 0100 1100 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 struct list { int key; struct list *next; }; int main(void) { struct list a, *p; a.key = 20; a.next = NULL; p = &a; printf(“a:%0x = [%d, %0x]\n”, p, a.key, a.next); return 0; } &a a a.key a.next p

printf(“a:%0x = [%d, %0x]\n”, p, a.key, a.next); return 0; } &a a アドレス（32bit）, 4アドレス飛び 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 20 0x 40ea 0804 0x 0000 0000 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x ef5c 2100 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 0x 40ea 082c 0x 1101 0000 0x 40ea 0830 0x 0100 1100 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 struct list { int key; struct list *next; }; int main(void) { struct list a, *p; a.key = 20; a.next = NULL; p = &a; printf(“a:%0x = [%d, %0x]\n”, p, a.key, a.next); return 0; } &a a a.key a.next p

printf(“a:%0x = [%d, %0x]\n”, p, a.key, a.next); return 0; } &a a アドレス（32bit）, 4アドレス飛び 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 20 0x 40ea 0804 0x 0000 0000 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x ef5c 2100 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 0x 40ea 082c 0x 1101 0000 0x 40ea 0830 0x 0100 1100 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 struct list { int key; struct list *next; }; int main(void) { struct list a, *p; a.key = 20; a.next = NULL; p = &a; printf(“a:%0x = [%d, %0x]\n”, p, a.key, a.next); return 0; } &a a a.key a.next p

printf(“a:%0x = [%d, %x]\n”, p, a.key, a.next); return 0; } &a a アドレス（32bit）, 4アドレス飛び 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 20 0x 40ea 0804 0x 0000 0000 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x ef5c 2100 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 0x 40ea 082c 0x 1101 0000 0x 40ea 0830 0x 0100 1100 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 struct list { int key; struct list *next; }; int main(void) { struct list a, *p; a.key = 20; a.next = NULL; p = &a; printf(“a:%0x = [%d, %x]\n”, p, a.key, a.next); return 0; } &a a a.key a.next p a: 40ea0800 = [20, 0] と表示

p = (struct list *)malloc(sizeof(struct list)); p->key = 21; アドレス（32bit）, 4アドレス飛び 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 0x 0000 0014 0x 40ea 0804 0x 0000 0000 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x ef5c 2100 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 0x 40ea 082c 0x 1101 0000 0x 40ea 0830 0x 0100 1100 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 struct list { int key; struct list *next; }; int main(void) { struct list *p; p = (struct list *)malloc(sizeof(struct list)); p->key = 21; p->next = NULL; printf(“p->%x = [%d, %x]\n”, p, p->key, p->next); return 0; } 動的領域割当によるプログラム： プログラム中で、 領域を確保する （枠が増える・減る）

p = (struct list *)malloc(sizeof(struct list)); p->key = 21; アドレス（32bit）, 4アドレス飛び 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 0x 0000 0014 0x 40ea 0804 0x 0000 0000 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x ef5c 2100 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 0x 40ea 082c 0x 1101 0000 0x 40ea 0830 0x 0100 1100 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 struct list { int key; struct list *next; }; int main(void) { struct list *p; p = (struct list *)malloc(sizeof(struct list)); p->key = 21; p->next = NULL; printf(“p->%x = [%d, %x]\n”, p, p->key, p->next); return 0; } p pは変数 動的領域割当によるプログラム： プログラム中で、 領域を確保する （枠が増える・減る）

p = (struct list *)malloc(sizeof(struct list)); p->key = 21; アドレス（32bit）, 4アドレス飛び 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 0x 0000 0014 0x 40ea 0804 0x 0000 0000 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x 40ea 082c 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 0x 1101 0000 0x 40ea 0830 0x 0100 1100 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 struct list { int key; struct list *next; }; int main(void) { struct list *p; p = (struct list *)malloc(sizeof(struct list)); p->key = 21; p->next = NULL; printf(“p->%x = [%d, %x]\n”, p, p->key, p->next); return 0; } アドレスを 代入 p key next 領域を 割当てる 動的領域割当によるプログラム： プログラム中で、 領域を確保する （枠が増える・減る）

p = (struct list *)malloc(sizeof(struct list)); p->key = 21; アドレス（32bit）, 4アドレス飛び 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 0x 0000 0014 0x 40ea 0804 0x 0000 0000 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x 40ea 082c 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 0x 1101 0000 0x 40ea 0830 0x 0100 1100 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 struct list { int key; struct list *next; }; int main(void) { struct list *p; p = (struct list *)malloc(sizeof(struct list)); p->key = 21; p->next = NULL; printf(“p->%x = [%d, %x]\n”, p, p->key, p->next); return 0; } アドレスを 代入 p key next 領域を 割当てる 動的領域割当によるプログラム： プログラム中で、 領域を確保する （枠が増える・減る）

p = (struct list *)malloc(sizeof(struct list)); p->key = 21; アドレス（32bit）, 4アドレス飛び 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 0x 0000 0014 0x 40ea 0804 0x 0000 0000 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x 40ea 082c 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 21 0x 40ea 0830 0x 0100 1100 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 struct list { int key; struct list *next; }; int main(void) { struct list *p; p = (struct list *)malloc(sizeof(struct list)); p->key = 21; p->next = NULL; printf(“p->%x = [%d, %x]\n”, p, p->key, p->next); return 0; } p key next 参照先に 代入 動的領域割当によるプログラム： プログラム中で、 領域を確保する （枠が増える・減る）

p = (struct list *)malloc(sizeof(struct list)); p->key = 21; アドレス（32bit）, 4アドレス飛び 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 0x 0000 0014 0x 40ea 0804 0x 0000 0000 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x 40ea 082c 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 21 0x 40ea 0830 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 struct list { int key; struct list *next; }; int main(void) { struct list *p; p = (struct list *)malloc(sizeof(struct list)); p->key = 21; p->next = NULL; printf(“p->%x = [%d, %x]\n”, p, p->key, p->next); return 0; } p key next 参照先に 代入 動的領域割当によるプログラム： プログラム中で、 領域を確保する （枠が増える・減る）

p = (struct list *)malloc(sizeof(struct list)); p->key = 21; アドレス（32bit）, 4アドレス飛び 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 0x 0000 0014 0x 40ea 0804 0x 0000 0000 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x 40ea 082c 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 21 0x 40ea 0830 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 struct list { int key; struct list *next; }; int main(void) { struct list *p; p = (struct list *)malloc(sizeof(struct list)); p->key = 21; p->next = NULL; printf(“p->%x = [%d, %x]\n”, p, p->key, p->next); return 0; } p key next 参照先に 代入 p-> 40ea082c = [21, 0] と表示

p = (struct list *)malloc(sizeof(struct list)); p->key = 21; int key; struct list *next; }; int main(void) { struct list *p; p = (struct list *)malloc(sizeof(struct list)); p->key = 21; p->next = NULL; printf(“p->%x = [%d, %x]\n”, p, p->key, p->next); return 0; } p key 21 next NULL p-> 40ea082c = [21, 0] と表示

p = (struct list *)malloc(sizeof(struct list)); １．メモリに割当てる p = (struct list *)malloc(sizeof(struct list)); ２．その量は、”struct list”型1個分 ３．mallocの戻り値は、割当てたメモリの先頭アドレス ４．そのアドレス（参照先）の中身は “struct list”型として、「キャスト」（型変換） ５．“struct list”型へのポインタとして、アドレスを代入 この書き方は、憶えましょう。 　　　　　　　　結果は 　　　　　　　←これ p key 21 next NULL 要するに、 新しく「箱」ができる。 この箱に名前（変数名）はない。 だから、ポインタ変数pで指し示しておく必要がある。

free(p); この使い方も憶えましょう。 結果は ←これ malloc関数で割り当てられた この名前のない「箱」の領域は、 開放する（使わなかったことにする）ことができる。 この使い方も憶えましょう。 　　　　　　　　結果は 　　　　　　　←これ p 赤い箱は解放された。 つまり、このメモリは、別のプログラムや別の機会に使われる。 でも、ポインタ変数pにアドレスだけは残っている。 うっかりpの参照先に代入しようとすると、OSが怒る。（Segmentation Fault）

p = (struct list *)malloc(sizeof(struct list)); p->key = 21; アドレス（32bit）, 4アドレス飛び 中身（1記憶単位=8bitを4領域まとめて32bitで表示） … 0x 40ea 0800 20 0x 40ea 0804 0x 0000 0000 0x 40ea 0808 0x 41b7 41b0 0x 40ea 080c 0x 4c6f a750 0x 40ea 0810 0x 40ea 0814 0x 40ea 0818 0x 40ea 081c 0x 40ea 082c 0x 40ea 0820 0x 0100 0001 0x 40ea 0824 0x 1011 0111 0x 40ea 0828 21 0x 40ea 0830 0x 40ea 0834 0x 0110 1111 0x 40ea 0838 0x 1010 0111 0x 40ea 083c 0x 0101 0000 struct list { int key; struct list *next; }; int main(void) { struct list a, *p; a.key = 20; a.next = NULL; p = (struct list *)malloc(sizeof(struct list)); p->key = 21; p->next = NULL; printf(“a:%0x = [%d, %0x]\n”, &a, a.key, a.next); printf(“p->%x = [%d, %x]\n”, p, p->key, p->next); free(p); return 0; } a a.key a.next p key next

p = (struct list *)malloc(sizeof(struct list)); p->key = 21; int key; struct list *next; }; int main(void) { struct list a, *p; a.key = 20; a.next = NULL; p = (struct list *)malloc(sizeof(struct list)); p->key = 21; p->next = NULL; printf(“a:%0x = [%d, %0x]\n”, &a, a.key, a.next); printf(“p->%x = [%d, %x]\n”, p, p->key, p->next); free(p); return 0; } a 20 a.key a.next NULL p key 21 next NULL

水色の箱（変数） と 赤い箱（確保された領域） の違い 変数： a 20 ・ NULL ・変数領域 mallocによって確保された領域： 　・ 　・変数領域 mallocによって確保された領域： 　・動的割当領域 a a.key 20 a.next NULL p key 21 next NULL

水色の箱（変数） と 赤い箱（確保された領域） の違い 変数： a 20 ・ブロック内で「宣言」されると、 そのブロックの中でずっと有効 　・ブロック内で「宣言」されると、 　そのブロックの中でずっと有効 　　（スコープ） 　・ 　・変数領域 mallocによって確保された領域： 　・プログラムの実行中に「割当て」。 　または、「解放」。 　（必要時に割り当てて、 　　不要になったら解放する。） 　・動的割当領域 a a.key 20 a.next NULL p key 21 next NULL

水色の箱（変数） と 赤い箱（確保された領域） の違い 変数： a 20 ・ブロック内で「宣言」されると、 そのブロックの中でずっと有効 　・ブロック内で「宣言」されると、 　そのブロックの中でずっと有効 　　（スコープ） 　・名前（変数名）がある。 　・変数領域 mallocによって確保された領域： 　・プログラムの実行中に「割当て」。 　または、「解放」。 　（必要時に割り当てて、 　　不要になったら解放する。） 　・名前はない。 　だから、アドレスを記録しなくては 　ならない。 　・動的割当領域 a a.key 20 a.next NULL p key 21 next NULL

使わないのにずっと確保される「静的領域」は資源の無駄。もったいない(MOTTAINAI) 水色の箱（変数） と 赤い箱（確保された領域） の違い 変数： 　・ブロック内で「宣言」されると、 　そのブロックの中でずっと有効 　　（スコープ） 　・名前（変数名）がある。 　・変数領域 mallocによって確保された領域： 　・プログラムの実行中に「割当て」。 　または、「解放」。 　（必要時に割り当てて、 　　不要になったら解放する。） 　・名前はない。 　だから、アドレスを記録しなくては 　ならない。 　・動的割当領域 a 20 a.key NULL a.next p key 21 next NULL メモリ（記憶領域）は有限な資源。 使わないのにずっと確保される「静的領域」は資源の無駄。もったいない(MOTTAINAI) 必要なときだけ、必要な量を確保し、使い終わったら解放して、他のプログラムに使ってもらおう