スライド 1

アルゴリズムとデータ構造
補足資料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
（ディスクやテープ；ディスクはアドレス指定が可能だが、「極めて遅い」）
– メモリの中身の種類
• データ
• アドレス
• プログラム（命令）
アドレス（32bit）
中身（1記憶単位は8bit）
…
…
0x 40ea 0800
1101 0000
0x 40ea 0801
0000 0111
0x 40ea 0802
0100 1011
0x 40ea 0803
1011 1111
&a 0x 40ea 0804
a
0000 0000
0x 40ea 0805
0000 0000
0x 40ea 0806
0000 0000
0x 40ea 0807
0001 0100
int main(void)
{
int a;
a = 20;
printf(“a:%x = %d\n”, &a, a);
return 0;
}
実行すると、以下の結果が出た。
a: 40ea0804 = 20
0x 40ea 0808
この場合のaは？
→int型（32bitの箱）の変数aは、
0100 0001
中身が20 （2進数では10100）
0x 40ea 0809
1011 0111
0x 40ea 080a
0100 0001
0x 40ea 080b
1101 0000
0x 40ea 080c
0100 1100
0x 40ea 080d
0110 1111
0x 40ea 080e
1010 0111
0x 40ea 080f
0101 0000
0x 40ea 0810
1101 0000
…
…
a
00000000 00000000 00000000 00010100
int 型（32bit）
aは、物理的にどこに存在する？
→ 記憶（メモリ）の中
（ＯＳに割り当ててもらう；毎回変わる）
aは、具体的にどこ？
→ 今回は0x 40ea 0804番地からの4バイト分
→ &a == 0x 40ea 0804 （aのアドレス）
アドレス（32bit）,
4アドレス飛び
中身（1記憶単位=8bitを4領
域まとめて32bitで表示）
…
…
0x d007 4bbf
0x 40ea 0800
&a
0x 40ea 0804
a
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 0000 0000
0x 40ea 0818
0x 0000 0000
0x 40ea 081c
0x ef5c 2100
0x 40ea 0820
0x 0100 0001
0x 40ea 0824
0x 1011 0111
0x 40ea 0828
0x 0100 0001
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
00000000 00000000 00000000 00010100
int 型（32bit）
変数aのアドレスは、
0x 40ea0804番地
アドレス（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 0000 0000
0x 40ea 0818
0x 0000 0000
0x 40ea 081c
0x ef5c 2100
0x 40ea 0820
0x 0100 0001
0x 40ea 0824
0x 1011 0111
0x 40ea 0828
0x 0100 0001
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
アドレス（32bit）,
4アドレス飛び
中身（1記憶単位=8bitを4領
域まとめて32bitで表示）
…
…
a
0x 40ea 0800
0x 40ea 0804
a.key
0x d007 4bbf
a.next
0x 0000 0014
0x 40ea 0808
0x 41b7 41b0
0x 40ea 080c
0x 4c6f a750
p
0x 40ea 0810
0x 0000 0000
0x 40ea 0818
0x 0000 0000
0x 40ea 081c
0x ef5c 2100
0x 40ea 0820
0x 0100 0001
0x 40ea 0824
0x 1011 0111
0x 40ea 0828
0x 0100 0001
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
…
int main(void)
{
struct list a, *p;
0x 0000 0000
0x 40ea 0814
…
struct list {
int key;
struct list *next;
};
a.key = 20;
a.next = NULL;
p = &a;
printf(“a:%0x = [%d, %0x]\n”,
p, a.key, a.next);
return 0;
}
変数によるプログラム：
プログラム中では、
変数の枠は動かない
&a
アドレス（32bit）,
4アドレス飛び
中身（1記憶単位=8bitを4領
域まとめて32bitで表示）
…
…
a
0x 40ea 0800
a.key
a.next
0x 40ea 0804
20
0x 0000 0014
0x 40ea 0808
0x 41b7 41b0
0x 40ea 080c
0x 4c6f a750
p
0x 40ea 0810
0x 0000 0000
0x 40ea 0818
0x 0000 0000
0x 40ea 081c
0x ef5c 2100
0x 40ea 0820
0x 0100 0001
0x 40ea 0824
0x 1011 0111
0x 40ea 0828
0x 0100 0001
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
…
int main(void)
{
struct list a, *p;
0x 0000 0000
0x 40ea 0814
…
struct list {
int key;
struct list *next;
};
a.key = 20;
a.next = NULL;
p = &a;
printf(“a:%0x = [%d, %0x]\n”,
p, a.key, a.next);
return 0;
}
&a
アドレス（32bit）,
4アドレス飛び
中身（1記憶単位=8bitを4領
域まとめて32bitで表示）
…
…
a
0x 40ea 0800
a.key
a.next
0x 40ea 0804
20
0x 0000 0000
0x 40ea 0808
0x 41b7 41b0
0x 40ea 080c
0x 4c6f a750
p
0x 40ea 0810
0x 0000 0000
0x 40ea 0818
0x 0000 0000
0x 40ea 081c
0x ef5c 2100
0x 40ea 0820
0x 0100 0001
0x 40ea 0824
0x 1011 0111
0x 40ea 0828
0x 0100 0001
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
…
int main(void)
{
struct list a, *p;
0x 0000 0000
0x 40ea 0814
…
struct list {
int key;
struct list *next;
};
a.key = 20;
a.next = NULL;
p = &a;
printf(“a:%0x = [%d, %0x]\n”,
p, a.key, a.next);
return 0;
}
&a
アドレス（32bit）,
4アドレス飛び
中身（1記憶単位=8bitを4領
域まとめて32bitで表示）
…
…
a
0x 40ea 0800
a.key
a.next
0x 40ea 0804
20
0x 0000 0000
0x 40ea 0808
0x 41b7 41b0
0x 40ea 080c
0x 4c6f a750
p
0x 40ea 0810
0x 0000 0000
0x 40ea 0818
0x 0000 0000
0x 40ea 081c
0x ef5c 2100
0x 40ea 0820
0x 0100 0001
0x 40ea 0824
0x 1011 0111
0x 40ea 0828
0x 0100 0001
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
…
int main(void)
{
struct list a, *p;
0x 40ea 0800
0x 40ea 0814
…
struct list {
int key;
struct list *next;
};
a.key = 20;
a.next = NULL;
p = &a;
printf(“a:%0x = [%d, %0x]\n”,
p, a.key, a.next);
return 0;
}
&a
アドレス（32bit）,
4アドレス飛び
中身（1記憶単位=8bitを4領
域まとめて32bitで表示）
…
…
a
0x 40ea 0800
a.key
a.next
0x 40ea 0804
20
0x 0000 0000
0x 40ea 0808
0x 41b7 41b0
0x 40ea 080c
0x 4c6f a750
p
0x 40ea 0810
0x 0000 0000
0x 40ea 0818
0x 0000 0000
0x 40ea 081c
0x ef5c 2100
0x 40ea 0820
0x 0100 0001
0x 40ea 0824
0x 1011 0111
0x 40ea 0828
0x 0100 0001
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
…
int main(void)
{
struct list a, *p;
0x 40ea 0800
0x 40ea 0814
…
struct list {
int key;
struct list *next;
};
a.key = 20;
a.next = NULL;
p = &a;
printf(“a:%0x = [%d, %x]\n”,
p, a.key, a.next);
return 0;
}
a: 40ea0800 = [20, 0]
と表示
アドレス（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 0800
0x 40ea 0814
0x 0000 0000
0x 40ea 0818
0x 0000 0000
0x 40ea 081c
0x ef5c 2100
0x 40ea 0820
0x 0100 0001
0x 40ea 0824
0x 1011 0111
0x 40ea 0828
0x 0100 0001
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;
}
動的領域割当によるプログラム：
プログラム中で、
領域を確保する
（枠が増える・減る）
アドレス（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 0800
0x 40ea 0814
0x 0000 0000
0x 40ea 0818
0x 0000 0000
p
0x 40ea 081c
0x 40ea 0820
0x 40ea 0824
pは変数
p = (struct list *)malloc(sizeof(struct list));
p->key = 21;
p->next = NULL;
0x 0100 0001
printf(“p->%x = [%d, %x]\n”,
p, p->key, p->next);
0x 1011 0111
0x 0100 0001
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
…
int main(void)
{
struct list *p;
0x ef5c 2100
0x 40ea 0828
…
struct list {
int key;
struct list *next;
};
return 0;
}
動的領域割当によるプログラム：
プログラム中で、
領域を確保する
（枠が増える・減る）
アドレス（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 0800
0x 40ea 0814
0x 0000 0000
0x 40ea 0818
0x 40ea 081c
アドレスを
代入
p
0x 40ea 0824
0x 1011 0111
0x 40ea 0828
0x 0100 0001
0x 40ea 082c
key
0x 1101 0000
0x 40ea 0830
next
0x 0100 1100
0x 40ea 0838
…
0x 0110 1111
0x 1010 0111
0x 0101 0000
0x 40ea 083c
…
p = (struct list *)malloc(sizeof(struct list));
p->key = 21;
p->next = NULL;
0x 40ea 082c
0x 0100 0001
領域を
割当てる
int main(void)
{
struct list *p;
0x 0000 0000
0x 40ea 0820
0x 40ea 0834
struct list {
int key;
struct list *next;
};
printf(“p->%x = [%d, %x]\n”,
p, p->key, p->next);
return 0;
}
動的領域割当によるプログラム：
プログラム中で、
領域を確保する
（枠が増える・減る）
アドレス（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 0800
0x 40ea 0814
0x 0000 0000
0x 40ea 0818
0x 40ea 081c
アドレスを
代入
p
0x 40ea 0824
0x 1011 0111
0x 40ea 0828
0x 0100 0001
0x 40ea 082c
key
0x 1101 0000
0x 40ea 0830
next
0x 0100 1100
0x 40ea 0838
…
0x 0110 1111
0x 1010 0111
0x 0101 0000
0x 40ea 083c
…
p = (struct list *)malloc(sizeof(struct list));
p->key = 21;
p->next = NULL;
0x 40ea 082c
0x 0100 0001
領域を
割当てる
int main(void)
{
struct list *p;
0x 0000 0000
0x 40ea 0820
0x 40ea 0834
struct list {
int key;
struct list *next;
};
printf(“p->%x = [%d, %x]\n”,
p, p->key, p->next);
return 0;
}
動的領域割当によるプログラム：
プログラム中で、
領域を確保する
（枠が増える・減る）
アドレス（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 0800
0x 40ea 0814
0x 0000 0000
0x 40ea 0818
0x 0000 0000
0x 40ea 0820
0x 0100 0001
0x 40ea 0824
0x 1011 0111
0x 40ea 0828
0x 0100 0001
0x 40ea 082c
key
0x 40ea 0830
next
0x 40ea 0834
0x 40ea 0838
参照先に
代入
…
…
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;
21
0x 0100 1100
0x 0110 1111
0x 1010 0111
0x 0101 0000
0x 40ea 083c
int main(void)
{
struct list *p;
0x 40ea 082c
p
0x 40ea 081c
struct list {
int key;
struct list *next;
};
}
動的領域割当によるプログラム：
プログラム中で、
領域を確保する
（枠が増える・減る）
アドレス（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 0800
0x 40ea 0814
0x 0000 0000
0x 40ea 0818
0x 0000 0000
0x 40ea 0820
0x 0100 0001
0x 40ea 0824
0x 1011 0111
0x 40ea 0828
0x 0100 0001
0x 40ea 082c
key
0x 40ea 0830
next
0x 40ea 0834
0x 40ea 0838
参照先に
代入
…
…
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;
21
0x 0000 0000
0x 0110 1111
0x 1010 0111
0x 0101 0000
0x 40ea 083c
int main(void)
{
struct list *p;
0x 40ea 082c
p
0x 40ea 081c
struct list {
int key;
struct list *next;
};
}
動的領域割当によるプログラム：
プログラム中で、
領域を確保する
（枠が増える・減る）
アドレス（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 0800
0x 40ea 0814
0x 0000 0000
0x 40ea 0818
0x 0000 0000
0x 40ea 0820
0x 0100 0001
0x 40ea 0824
0x 1011 0111
0x 40ea 0828
0x 0100 0001
0x 40ea 082c
key
0x 40ea 0830
next
0x 40ea 0834
0x 40ea 0838
参照先に
代入
…
…
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;
21
0x 0000 0000
}
0x 0110 1111
0x 1010 0111
0x 0101 0000
0x 40ea 083c
int main(void)
{
struct list *p;
0x 40ea 082c
p
0x 40ea 081c
struct list {
int key;
struct list *next;
};
p-> 40ea082c = [21, 0]
と表示
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;
p
printf(“p->%x = [%d, %x]\n”,
p, p->key, p->next);
key
next
21
NULL
return 0;
}
p-> 40ea082c = [21, 0]
と表示
１．メモリに割当てる
p = (struct list *)malloc(sizeof(struct list));
２．その量は、”struct list”型1個分
３．mallocの戻り値は、割当てたメモリの先頭アドレス
４．そのアドレス（参照先）の中身は “struct list”型として、「キャスト」（型変換）
５．“struct list”型へのポインタとして、アドレスを代入
p
この書き方は、憶えましょう。
結果は
←これ
key
next
21
NULL
要するに、
新しく「箱」ができる。
この箱に名前（変数名）はない。
だから、ポインタ変数pで指し示しておく必要がある。
free(p);
malloc関数で割り当てられた
この名前のない「箱」の領域は、
開放する（使わなかったことにする）ことができる。
p
この使い方も憶えましょう。
結果は
←これ
赤い箱は解放された。
つまり、このメモリは、別のプログラムや別の機会に使われる。
でも、ポインタ変数pにアドレスだけは残っている。
うっかりpの参照先に代入しようとすると、OSが怒る。（Segmentation Fault）
アドレス（32bit）,
4アドレス飛び
中身（1記憶単位=8bitを4領
域まとめて32bitで表示）
…
…
a
0x 40ea 0800
a.key
a.next
0x 40ea 0804
20
0x 0000 0000
0x 40ea 0808
0x 41b7 41b0
0x 40ea 080c
0x 4c6f a750
0x 40ea 0810
0x 40ea 0800
0x 40ea 0814
0x 0000 0000
0x 40ea 0818
0x 0000 0000
0x 40ea 0820
0x 0100 0001
0x 40ea 0824
0x 1011 0111
0x 40ea 0828
0x 0100 0001
0x 40ea 082c
key
0x 40ea 0830
next
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;
0x 0000 0000
0x 0110 1111
0x 40ea 0838
0x 1010 0111
0x 40ea 083c
0x 0101 0000
…
a.key = 20;
a.next = NULL;
21
0x 40ea 0834
…
int main(void)
{
struct list a, *p;
0x 40ea 082c
p
0x 40ea 081c
struct list {
int key;
struct list *next;
};
}
a
a.key
a.next
20
NULL
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
p->key = 21;
p->next = NULL;
key
next
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;
21
NULL
}
a
a.key
a.next
水色の箱（変数）
と
赤い箱（確保された領域）
の違い
20
NULL
変数：
・
・
・変数領域
p
mallocによって確保された領域：
・
key
next
21
NULL
・
・動的割当領域
a
a.key
a.next
20
NULL
水色の箱（変数）
と
赤い箱（確保された領域）
の違い
変数：
・ブロック内で「宣言」されると、
そのブロックの中でずっと有効
（スコープ）
・
・変数領域
p
key
next
21
NULL
mallocによって確保された領域：
・プログラムの実行中に「割当て」。
または、「解放」。
（必要時に割り当てて、
不要になったら解放する。）
・
・動的割当領域
a
a.key
a.next
20
NULL
水色の箱（変数）
と
赤い箱（確保された領域）
の違い
変数：
・ブロック内で「宣言」されると、
そのブロックの中でずっと有効
（スコープ）
・名前（変数名）がある。
・変数領域
p
key
next
21
NULL
mallocによって確保された領域：
・プログラムの実行中に「割当て」。
または、「解放」。
（必要時に割り当てて、
不要になったら解放する。）
・名前はない。
だから、アドレスを記録しなくては
ならない。
・動的割当領域
a
a.key
a.next
20
NULL
水色の箱（変数）
と
赤い箱（確保された領域）
の違い
変数：
・ブロック内で「宣言」されると、
そのブロックの中でずっと有効
（スコープ）
・名前（変数名）がある。
・変数領域
p
key
next
21
NULL
mallocによって確保された領域：
・プログラムの実行中に「割当て」。
または、「解放」。
（必要時に割り当てて、
不要になったら解放する。）
・名前はない。
だから、アドレスを記録しなくては
ならない。
・動的割当領域
メモリ（記憶領域）は有限な資源。
使わないのにずっと確保される「静的領域」は資源の無駄。もったいない(MOTTAINAI)
必要なときだけ、必要な量を確保し、使い終わったら解放して、他のプログラムに使ってもらおう

Download Report