ダイクストラ法の実装

データ構造とアルゴリズム
第10回 mallocとfree
静岡大学工学部
安藤 和敏
2011.06.17
目次
1. 変数とメモリ (復習)
2. 配列の宣言とメモリ
3. メモリの動的割り当て(malloc)と開放
(free)
4. プログラム例:malloc1.c (int型配列)
5. プログラム例:malloc2.c (struct
COMPLEX型)
6. 実習
目次
1. 変数とメモリ (復習)
2. 配列の宣言とメモリ
3. メモリの動的割り当て(malloc)と開放
(free)
4. プログラム例:malloc1.c (int型配列)
5. プログラム例:malloc2.c (struct
COMPLEX型)
6. 実習
コンピュータのメモリのイメージ
アドレス
内容
0
1
2
3
4
5
6
7
175
.
.
.
安藤
浜松
2004
.
.
.
変数とメモリ
int x;
と宣言することに
よって、xという名前
が付けられた4バイ
ト分のメモリ領域が
確保される。
確保されるバイト数
はその変数の型に
依存する。p.18の表
2.3を見よ。
アドレス
0
1
2
3
4
5:x:
6
7
内容
175
安藤
浜松
2004
.
.以降は、この確保されたメモ
と言う名前
.リ領域の内容をx.
.
. で参照できるようになる。
ポインタとメモリ(教科書p.143-144)
int x;
int *p=&x;
アドレス
内容
0
1:p:
2
3
4
5
6
7:x:
175
7
安藤
浜松
2004
ポインタ変数 pの
内容=7
xの宣言によっ
て確保されたメ
モリ領域
ポインタとメモリの関係の図示
int x;
int *p=&x;
アドレス
p:
x:
内容
前ページのよ
うな状況を図
示するために、
このような矢
線を用いて表
現する。
目次
1. 変数とメモリ (復習)
2. 配列の宣言とメモリ
3. メモリの動的割り当て(malloc)と開放
(free)
4. プログラム例:malloc1.c (int型配列)
5. プログラム例:malloc2.c (struct
COMPLEX型)
6. 実習
配列の宣言とメモリ
int array[100];
配列を、例えばこのよう
に宣言すると、メモリ上
に,array[0], array[1],
…, array[99] という名
前の付いた連続したメ
モリ領域がプログラムを
実行した直後に確保さ
れる.この記憶場所に
は,int型のデータが記
憶される.
array[0]:
array[1]:
array[2]:
・
・
・
・
・
・
array[99]:
したがって、この宣言によって、
100×4=400バイトのメモリがプ
ログラムによって確保される。
実際に使わないメモリ領域をを
無駄に確保するかも知れないし、
配列の宣言とメモリ(問題点)
int array[100];
ちょうど100個の整数の
データを格納することが
事前に分かっていれば
問題ない。
しかし、実行した後でな
いと何個のデータを格
納しなければならない
か分からないということ
が、良くある。
array[0]:
array[1]:
array[2]:
・
・
・
・
・
・
array[99]:
メモリ領域の過不足が生じる
可能性がある。
特に携帯電話のように十分大きなメモ
リ領域が搭載されていないデバイス上
で動くプログラムにおいては、メモリを
効率的に使用しなければならない。
目次
1. 変数とメモリ (復習)
2. 配列の宣言とメモリ
3. メモリの動的割り当て(malloc)と開放
(free)
4. プログラム例:malloc1.c (int型配列)
5. プログラム例:malloc2.c (struct
COMPLEX型)
6. 実習
メモリの動的割り当て
• 前ページで述べた問題はメモリの動的割り当てとい
う仕組みによって解決できる。
• すなわち、データの個数がプログラムの実行前に分
かっていなくても、プログラムの実行中にメモリを適切
に確保できる。
• C言語では、このメモリの動的割り当てを実現する
ために、mallocとfreeという関数が用意されている。
• これらの関数は、ヘッダファイル stdlib.h の中で定
義されている。
malloc (エムアロック、マロック)
void *malloc (int size);
確保に成功すれば、確
保したメモリの先頭の
アドレス(番地)を返
す。失敗した場合は
NULLを返す。
確保するメモ
リのバイト数
void * は任意の型を持つ変数へのポインタという意味。実
際に使うときには、キャスト演算子(p.22)によって、適当な
ポインタに変換する必要がある。
malloc の例(int 型のメモリ領域)
int *p;
p = (int *)malloc(sizeof(int));
番地
0
1 :p:
2
3
4
5
6
7
メモリの内容
ポインタ変数 pの
ためのメモリ領域
が確保される。
malloc の例(int 型のメモリ領域)
int *p;
p = (int
(int *)malloc(sizeof(int));
*)malloc(sizeof(int))
番地
0
1:p:
2
3
4
5
6
7
メモリの内容
そのアドレスは、適切
な型に変換(キャスト)
されなければならない。
mallocによって確
保されたメモリ領域。
sizeof(int)バイ
ト=4バイト。malloc
はこのメモリのアドレ
スを返す。
malloc の例(int 型のメモリ領域)
int *p;
p = (int *)malloc(sizeof(int));
番地
0
1:p:
2
3
4
5
6
7
メモリの内容
ポインタ変数 p に
mallocによって確
保されたメモリのアド
レス(5)が代入され
る。
これ以降は、ここの
内容は p を介して
参照できる。例えば、
*p=100とか。
free
関数 free の呼び出しによって、動的に確保されたメモリ領
域を開放することができる。
int free (void* p);
開放したいメモリ領域の
先頭アドレス
目次
1. 変数とメモリ (復習)
2. 配列の宣言とメモリ
3. メモリの動的割り当て(malloc)と開放
(free)
4. プログラム例:malloc1.c (int型配列)
5. プログラム例:malloc2.c (struct
COMPLEX型)
6. 実習
プログラム例 (malloc1.c)
/* プログラム 10.5 配列の動的な割り当て */
#include <stdio.h>
#include <stdlib.h>
配列の要素数をプログラム
の実行後に決めることがで
main(){
きる。
int i,n,*array;
printf("N= "); scanf("%d",&n);
if ((array=(int *)malloc(n*sizeof(int)))
==NULL) {
fprintf(stderr,"malloc failed.\n");
exit(1);
}
mallocによる配列の宣言とメモリ
int *array;
array=(int *)malloc(n*sizeof(int));
とすれば、配列 array
の要素数をプログラム
の実行中に決めること
ができる.だから、必要
十分なメモリの確保が
可能になる。
mallocによって確保されたメ
モリ領域(n×4バイト)
array:
array[0]:
array[1]:
array[2]:
・
・
・
array[n-1]:
・
・
・
プログラム例 (malloc1.c) (続き)
for(i=0;i<n;i++) {
array[i]=i;
printf("%d ", array[i]);
}
putchar('\n');
free(array);
}
配列の要素数をプログラム
の実行後に決めることがで
きる。
目次
1. 変数とメモリ (復習)
2. 配列の宣言とメモリ
3. メモリの動的割り当て(malloc)と開放
(free)
4. プログラム例:malloc1.c (int型配列)
5. プログラム例:malloc2.c (struct
COMPLEX型)
6. 実習
プログラム例 (malloc2.c)
#include <stdio.h>
#include <stdlib.h>
#define PrintComplex(x) ...(省略)
struct COMPLEX {double real; double img;} ;
main(){
struct COMPLEX *a;
a = (struct COMPLEX *)
malloc(sizeof(struct COMPLEX));
a->real = 10;
a->img =3;
PrintComplex(*a); putchar('\n');
free(a);
}
malloc の例(struct COMPLEX型の
メモリ領域)
struct COMPLEX *a;
a = (struct COMPLEX *)
malloc(sizeof(struct COMPLEX));
メモリの内容
a:
ポインタ変数 a
のためのメモリ領
域が確保される。
malloc の例(struct COMPLEX型の
メモリ領域) そのアドレスは、適
切な型に変換(キャ
スト)されなければ
ならない。
struct COMPLEX *a;
a = (struct COMPLEX *)
COMPLEX));
malloc(sizeof(struct COMPLEX))
メモリの内容
a:
(real)
(img)
mallocによって確
保されたメモリ領域。
sizeof(struct
COMPLEX)バイト
=16バイト。malloc
はこのメモリのアドレ
スを返す。
malloc の例(struct COMPLEX型の
メモリ領域)
struct COMPLEX *a;
a = (struct COMPLEX *)
malloc(sizeof(struct COMPLEX));
メモリの内容
a:
(real)
(img)
ポインタ変数 a に
mallocによって確
保されたメモリのアド
レスが代入される。
それ以降は、ここの
内容はポインタ a を
介して参照できる。
a->real,
a->img で。
プログラム例 (malloc2.c)
#include <stdio.h>
#include <stdlib.h>
#define PrintComplex(x) ...(省略)
struct COMPLEX {double real; double img;} ;
main(){
struct COMPLEX *a;
a = (struct COMPLEX *)
malloc(sizeof(struct COMPLEX));
a->real = 10;
a->img =3;
PrintComplex(*a); putchar('\n');
free(a);
}
目次
1. 変数とメモリ (復習)
2. 配列の宣言とメモリ
3. メモリの動的割り当て(malloc)と開放
(free)
4. プログラム例:malloc1.c (int型配列)
5. プログラム例:malloc2.c (struct
COMPLEX型)
6. 実習