C言語入門

1
C言語入門
第9週
プログラミング言語Ⅰ(実習を含む。),
計算機言語Ⅰ・計算機言語演習Ⅰ,
情報処理言語Ⅰ(実習を含む。)
2
関数
3
第4週資料pp.33-41,48-49.
関数
• 関数の定義の書式:
関数の宣言
戻り値の型関数名(引数の宣言, ...);
.h ファイルへ書き出す
関数の定義
戻り値の型関数名(引数の宣言, ...)
{
// 関数に行わせる処理
// ...
return 戻り値; // 戻り値の型がvoidの場合は不要
}
.c ファイルへ書き出す
関数の利用
変数名 = 関数名(引数, ...);
適宜呼び出す
4
第4週資料pp.42-44.
関数の引数(値渡し、参照渡し)
• 変数のスコープ(有効範囲)
scopetest.c
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int gl = 100;
void sub(int lo)
関数の引数は呼び出し元とは別の変数になっていた
{
{
int lo = 400;
printf("%-4s : %3d: gl=%d, lo=%d\n", __func__, __LINE__, ++gl, ++lo);
}
printf("%-4s : %3d: gl=%d, lo=%d\n", __func__, __LINE__, ++gl, ++lo);
}
int main()
mintty + bash + GNU C
{
$ gcc scopetest.c && ./a
int lo = 200;
sub(300);
sub : 14: gl=101, lo=401
printf("%-4s : %3d: gl=%d, lo=%d\n", __func__, __LINE__, ++gl, ++lo);
return EXIT_SUCCESS;
}
sub :
main :
16: gl=102, lo=301
23: gl=103, lo=201
5
第4週資料pp.42-44. 教科書p.171.
関数の引数(値渡し、参照渡し)
• 値渡し: 呼出し元の値のコピーを渡す
call_by_value.c
8
9
10
11
12
13
14
15
16
17
18
19
20
void sub(int lo)
{
lo = 200;
}
引数で受け取った変数を変更しても
呼び出し元には反映されない
int main()
{
int lo = 100;
sub(lo);
printf("lo=%d\n", lo);
return EXIT_SUCCESS;
}
mintty + bash + GNU C
$ g++ call_by_value.c && ./a
lo=100
6
第4週資料pp.42-44. 教科書p.171.
関数の引数(値渡し、参照渡し)
• 参照渡し: 呼出し元の値の格納場所を渡す
call_by_pointer.c
8
9
10
11
12
13
14
15
16
17
18
19
20
void sub(int *lo)
{
*lo = 200;
}
引数で受け取った変数を変更すると
呼び出し元にも反映される
int main()
{
int lo = 100;
sub(&lo);
printf("lo=%d\n", lo);
scanf で見たことがある書き方！
&: アドレス演算子
これは正確には
ポインタ渡しと言う
変数loのアドレスを
渡している
return EXIT_SUCCESS;
}
mintty + bash + GNU C
$ g++ call_by_pointer.c && ./a
lo=200
7
参考
関数の引数(値渡し、参照渡し)
• C++における参照渡し
call_by_reference.cpp
4
5
6
7
8
9
10
11
12
13
14
15
16
void sub(int &lo)
{
lo = 200;
}
引数で受け取った変数を変更すると
呼び出し元にも反映される
int main()
{
int lo = 100;
sub(lo);
printf("lo=%d\n", lo);
C++の参照渡しでは
アドレス演算子「&」が不要
C++では
本物の参照渡しが
可能になった
値が変化することが
分かり難いという
デメリットもある
return EXIT_SUCCESS;
}
mintty + bash + GNU C++
$ g++ call_by_reference.cpp && ./a
lo=200
8
教科書pp.207-272.
ポインタ変数
pointer: 指し示す者
• メモリ上のアドレスを指し示すための変数
• char * 型: char 型の変数へのポインタ
• int * 型: int 型の変数へのポインタ
• 要はアドレスを格納するための変数
• ポインタ型のサイズはアドレス空間のビット数
• 32ビットアドレス空間なら4バイト
• 64ビットアドレス空間なら8バイト
• sizeof(char *)もsizeof(int *)も同じ
教科書 pp.52-56.
第2週資料 p.45.
メモリの構成
• 1byte単位でアドレスが振られている
• つまり各アドレスには1byteの値を格納出来る
32bitのOSは32bitのアドレス空間
最大232 Bytes=4GiB
64bitのOSは64bitのアドレス空間
最大264 Bytes=16EiB
0x00000000
0x00
0x0000000000000000
0x00
0x00000001
0x00
0x0000000000000001
0x00
0x00000002
0x00
0x0000000000000002
0x00
0x00000003
0x00
0x0000000000000003
0x00
:
:
:
:
0xffffffff
0x00
アドレス
格納値
:
:
0xffffffffffffffff
ポインタ変数には
これらの値が入る
アドレス
:
:
0x00
格納値
10
教科書pp.207-272.
ポインタ変数
宣言時に*を付けると
ポインタ変数になる
• 例: 16bit short型little endianの場合
:
:
&a
:
:
0x～00
0x34
0x～01
0x12
0x～02
0x??
&aは
0x～03
変数aの
0x～04
メモリ上の
先頭アドレス
0x～05
0x??
0x～06
0x??
0x～07
0x??
0x～08
0x??
:
:
0x??
a
0x??
:
:
short a = 0x1234;
short *p = &a;
0x1234
0x～00
a
0x1234
0x～00
*p
0x～00
pは変数*pの
アドレスを指し示す
要はリンク
みたいなもの
p
p に &a を入れておくと
*p は a への
参照として機能する
C言語ではこれを
ポインタと言う
*pはアドレスpに
置かれた変数(ここではa)
への参照
実際に存在している変
数はpで中にはアドレス
が格納されている
11
教科書pp.207-272.
ポインタ変数
• 変数が配置されたアドレスを扱うための変数
pointertest1.c
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
int a = 1;
int *p;
p = &a;
*p = 2;
printf("a=%d\n", a);
return EXIT_SUCCESS;
}
変数の宣言で
変数名の前にポインタ宣言子「*」を付けると
ポインタ変数になる。
この場合、
int 型の変数 *p を宣言した結果、
実際には int 型変数へのポインタである
int * 型変数 p が宣言されると
理解しておくとスッキリする。
mintty + bash + GNU C
$ gcc pointertest1.c && ./a
a=2
12
教科書pp.207-272.
ポインタ変数
• 変数が配置されたアドレスを扱うための変数
pointertest1.c
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
int a = 1;
int *p;
p = &a;
*p = 2;
アドレス演算子「&」を用いて
int 型変数 a のアドレス &a を
int 型の変数へのポインタ p に代入する
printf("a=%d\n", a);
1
return EXIT_SUCCESS;
}
0x～
a
mintty + bash + GNU C
$ gcc pointertest1.c && ./a
a=2
&a
0x～
p
13
教科書pp.207-272.
ポインタ変数
• 変数が配置されたアドレスを扱うための変数
pointertest1.c
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
int a = 1;
int *p;
p = &a;
*p = 2;
printf("a=%d\n", a);
return EXIT_SUCCESS;
}
mintty + bash + GNU C
int 型の変数へのポインタ p の前に
間接演算子「*」を付けると
ポインタ変数 p が指し示すアドレスを
int 型の変数としてアクセス出来る。
今 p に変数 a のアドレス &a が
入っているので、
*p に対するあらゆる操作は
変数 a に対する操作と同義となる。
実際 *p を書き変えることで a が
書き変えられていることが確認出来る。
$ gcc pointertest1.c && ./a
a=2
2
0x～
*p
a
0x～
p
14
教科書pp.207-272., [1] pp.250,268-269.
ポインタ変数の宣言と代入
• 「*」と「=」の使い方は要注意
• 同じ「*」だが宣言時とそれ以外で意味が異なる
宣言時
それ以外
*p
pをポインタとして宣言
pが指すアドレスの格納値
*p=x
pにxを代入
*pにxを代入
ポインタ変数pが指すアドレス
(言い換えると、ある型の変数*p)に
値xを代入する
ポインタ変数pを宣言
(言い換えると、ある型の変数*pを宣言)し
宣言した変数pに
アドレスxを代入する
*は間接演算子
indirection operator
または間接参照演算子
dereference operator
*はポインタ宣言子
pointer declarator
要注意
15
教科書pp.207-272.
ポインタ変数の宣言と代入
• 「*」と「=」の使い方は要注意
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pointertest2.cpp
mintty + bash + GNU C
int a = 1;
int *p1, b;
int *p2 = &a;
p1 = &a;
$ gcc pointertest2.c && ./a
sizeof(p1)=8
sizeof(b)=4
&a=0x000000000022aabc
p1=0x000000000022aabc
p2=0x000000000022aabc
a=1
*p1=1
*p2=1
printf("sizeof(p1)=%d\n", sizeof(p1));
printf("sizeof(b)=%d\n", sizeof(b));
printf("&a=%#0*p\n", sizeof(&a)*2+2, &a);
printf("p1=%#0*p\n", sizeof(p1)*2+2, p1);
printf("p2=%#0*p\n", sizeof(p2)*2+2, p2);
printf("a=%d\n",
a);
printf("*p1=%d\n", *p1);
printf("*p2=%d\n", *p2);
要注意
16
教科書pp.207-272.
ポインタ変数の宣言と代入
宣言時は「*」が間接演算子ではなく
ポインタ宣言子として働いている
宣言時に初期化すると
*p2 ではなく p2mintty
に &a+ bash
が代入される点が紛らわしい
+ GNU C
要注意
• 「*」と「=」の使い方は要注意
pointertest2.cpp
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int a = 1;
int *p1, b;
int *p2 = &a;
p1 = &a;
$ gcc pointertest2.c && ./a
sizeof(p1)=8
p1 に &a を代入している
sizeof(b)=4
&a=0x000000000022aabc
printf("sizeof(p1)=%d\n", sizeof(p1));
printf("sizeof(b)=%d\n", sizeof(b));
p1=0x000000000022aabc
p2=0x000000000022aabc
printf("&a=%#0*p\n", sizeof(&a)*2+2, &a);
a=1
printf("p1=%#0*p\n", sizeof(p1)*2+2, p1);
printf("p2=%#0*p\n", sizeof(p2)*2+2, p2);
*p1=1
*p2=1
printf("a=%d\n",
a);
printf("*p1=%d\n", *p1);
printf("*p2=%d\n", *p2);
宣言時以外は*は関節演算子として働く
ポインタの前に*が付くと、指し示す
アドレスに格納されている値を操作する
要注意
17
教科書pp.207-272.
ポインタ変数の宣言と代入
• 「*」と「=」の使い方は要注意
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pointertest2.cpp
mintty + bash + GNU C
int a = 1;
int *p1, b;
int *p2 = &a;
p1 = &a;
$ gcc pointertest2.c && ./a
sizeof(p1)=8
sizeof(b)=4
&a=0x000000000022aabc
p1=0x000000000022aabc
p2=0x000000000022aabc
a=1
*p1=1
*p2=1
printf("sizeof(p1)=%d\n", sizeof(p1));
「int
*」型の宣言ではなく、
printf("sizeof(b)=%d\n", sizeof(b));
「int」型の宣言である点も紛らわしい。
printf("&a=%#0*p\n",
sizeof(&a)*2+2, &a);
p1
はポインタ変数だが
sizeof(p1)*2+2, p1);
bprintf("p1=%#0*p\n",
は通常のint型変数
printf("p2=%#0*p\n", sizeof(p2)*2+2, p2);
複数の変数を宣言する場合
printf("a=%d\n",
a);
printf("*p1=%d\n", *p1);
変数名の前に
printf("*p2=%d\n", *p2);
ポインタ宣言子「*」を付けた変数だけが
ポインタ変数になる
要注意
要注意
18
第3週資料pp.24-33.
ポインタの表示
• %p
• void *;ポインタとして印字(処理系依存)
例
mintty + bash + GNU C
printf("&a=%#0*p\n", sizeof(&a)*2+2, &a);
$ gcc hoge.c && ./a
&a=0x000000000022aabc
%*pによる最小フィールド幅指定
1バイト=16進数2桁
先頭の0xで更に2桁
#:
0:
*:
p:
16進表示が0でない場合、先頭を0xにする
フィールド幅いっぱいに左側から0を詰める
最小フィールド幅を引数で指定
void *;ポインタとして印字
19
教科書pp.207-272.
1次元配列とポインタ
配列は1要素のバイト数×要素数
ポインタはアドレス空間のビット数/8
• 機能としてはほぼ同じ
• ポインタはアドレスを変更可能(少し柔軟)
配列
int p[N];
ポインタ
int *p;
sizeof(p)
○
○
変数pの割り当てバイト数
&p
△
○
変数pのアドレス(配列はpと同じ)
p
○
○
アドレスp(p[0]のアドレス)
*p
○
○
アドレスpの格納値
p[x]
○
○
アドレスpを先頭にしてx個目の要素の格納値
*(p+x)
○
○
アドレスpを先頭にしてx個目の要素(p[x])の格納値
&p[x]
○
○
アドレスpを先頭にしてx個目の要素(p[x])のアドレス
p+x
○
○
アドレスpを先頭にしてx個目の要素(p[x])のアドレス
p+=x
×
○
アドレスpを先頭にしてx個目の要素(p[x])のアドレス
20
教科書pp.207-272.
ポインタ変数とアドレス演算
• 例: 16bit short型little endianの場合
:
:
pa
pa+1
pa+2
pa+3
:
:
0x～00
0x34
0x～01
0x12
0x～02
0x??
0x～03
0x??
0x～04
0x??
0x～05
0x??
0x～06
0x??
0x～07
0x??
0x～08
0x??
:
:
:
:
*pa
*(pa+1)
*(pa+2)
short a = 0x1234;
short *pa = &a;
±1するとsizeof(*pa)単位で
アドレスが増減する
つまり short 型配列の
0要素目、1要素目、...
という意味になる
*(pa+3)
要注意
21
教科書pp.207-272.
ポインタ変数とアドレス演算
• 例: 32bit int型little endianの場合
:
:
pa
pa+1
:
:
0x～00
0x78
0x～01
0x56
0x～02
0x34
0x～03
0x12
0x～04
0x??
0x～05
0x??
0x～06
0x??
0x～07
0x??
0x～08
0x??
:
:
:
:
int a = 0x12345678;
int *pa = &a;
*pa
*(pa+1)
±1するとsizeof(*pa)単位で
アドレスが増減する
つまり int 型配列の
0要素目、1要素目、...
という意味になる
要注意
22
教科書pp.207-272.
ポインタ変数の配列的利用法
• 例: 16bit short型little endianの場合
:
:
&pa[0]
&pa[1]
&pa[2]
&pa[3]
:
:
0x～00
0x34
0x～01
0x12
0x～02
0x??
0x～03
0x??
0x～04
0x??
0x～05
0x??
0x～06
0x??
0x～07
0x??
0x～08
0x??
:
:
:
:
pa[0]
pa[1]
pa[2]
pa[3]
short a = 0x1234;
short *pa = &a;
配列同様[x]で先頭x個目の
要素にアクセス出来る
要素の頭に&を付けると
アドレスが得られる
23
教科書pp.207-272.
ポインタ変数の配列的利用法
• 例: 32bit int型little endianの場合
:
:
&pa[0]
&pa[1]
:
:
0x～00
0x78
0x～01
0x56
0x～02
0x34
0x～03
0x12
0x～04
0x??
0x～05
0x??
0x～06
0x??
0x～07
0x??
0x～08
0x??
:
:
:
:
int a = 0x12345678;
int *pa = &a;
pa[0]
配列同様[x]で先頭x個目の
要素にアクセス出来る
要素の頭に&を付けると
アドレスが得られる
pa[1]
24
教科書pp.207-272.
1次元配列とポインタ
pointertest3.c
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int x;
int a[] = {0,1,2,3,4,5,6,7,8,9};
int *p = a;
fprintf(stderr, "x = ? ");
scanf("%d", &x);
printf("sizeof(a) = %p\n", sizeof(a));
printf("sizeof(p) = %p\n", sizeof(p));
printf("&a = %p\n", &a);
printf("&p = %p\n", &p);
printf("a = %p\n", a);
printf("p = %p\n", p);
printf("*a = %d\n", *a);
printf("*p = %d\n", *p);
printf("a[x] = %d\n", a[x]);
printf("p[x] = %d\n", p[x]);
printf("*(a+x) = %d\n", *(a+x));
printf("*(p+x) = %d\n", *(p+x));
printf("&a[x] = %p\n", &a[x]);
printf("&p[x] = %p\n", &p[x]);
printf("a+x = %p\n", a+x);
printf("p+x = %p\n", p+x);
cygwin64 + mintty + bash + GNU C
$ gcc pointertest3.c && ./a
x = ? 1
sizeof(a) = 0x28
sizeof(p) = 0x8
&a = 0x22aaa0
&p = 0x22aa98
a = 0x22aaa0
p = 0x22aaa0
*a = 0
*p = 0
pに1を足しているのに
a[x] = 1
結果が4増えていることが
p[x] = 1
確認出来る
*(a+x) = 1
*(p+x) = 1
&a[x] = 0x22aaa4
&p[x] = 0x22aaa4
a+x = 0x22aaa4
p+x = 0x22aaa4
p+=x = 0x22aaa4
//printf("a+=x = %p\n", a+=x); // Address of array variable can not be modified.
printf("p+=x = %p\n", p+=x);
25
教科書pp.207-272.
1次元配列とポインタ
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pointertest3.c
cygwin64 + mintty + bash + GNU C
int x;
int a[] = {0,1,2,3,4,5,6,7,8,9};
int *p = a;
$ gcc pointertest3.c && ./a
x = ? 1
sizeof(a) = 0x28
sizeof(p) = 0x8
&a = 0x22aaa0
&p = 0x22aa98
a = 0x22aaa0
p = 0x22aaa0
<以下略>
fprintf(stderr, "x = ? ");
scanf("%d", &x);
printf("sizeof(a) = %p\n", sizeof(a));
printf("sizeof(p) = %p\n", sizeof(p));
printf("&a = %p\n", &a);
printf("&p = %p\n", &p);
printf("a = %p\n", a);
printf("p = %p\n", p);
配列変数aはメモリに配置されたアドレス
配列変数aのアドレス&aはつまりaと同じ
ポインタ変数pは
メモリ上のどこかに確保されており
&pはそのアドレス
pはそのアドレス&pに格納されたアドレス
この例では&a
*pはそのアドレスpに格納されたデータ
26
教科書pp.207-272.
1次元配列とポインタ
• 例: 32bitOSで8bit char型little endianの場合
&a
=a
=p
&p
:
:
:
:
0x～00
0x00
0x～01
0x01
0x～02
0x02
0x～03
0x03
0x～04
0x00
0x～05
0x~~
0x～06
0x~~
0x～07
0x~~
0x～08
0x??
:
:
:
:
char a[] = {0,1,2,3};
char *p = &a;
a
これ全体が配列aであり
aはその先頭アドレス
配列変数aはメモリに配置されたアドレス
配列変数aのアドレス&aはつまりaと同じ
p
ポインタ変数pは
メモリ上のどこかに確保されており
&pはそのアドレス
pはそのアドレス&pに格納されたアドレス
この例では&a
*pはそのアドレスpに格納されたデータ
27
教科書pp.207-272.
1次元配列とポインタ
• 例: 32bitOSで8bit char型little endianの場合
&a
=a
=p
&p
:
:
:
:
0x～00
0x00
0x～01
0x01
0x～02
0x02
0x～03
0x03
0x～04
0x00
0x～05
0x~~
0x～06
0x~~
0x～07
0x~~
0x～08
0x??
:
:
:
:
char a[] = {0,1,2,3};
char *p = &a;
a
p
sizeof(a) は
aの1要素辺りのバイト数×要素数
つまりsizeof(char)*N
sizeof(p) は
OSのアドレス空間のビット数/8
つまりsizeof(char *)
28
教科書pp.207-272.
ポインタ変数
6
7
8
9
10
11
12
13
14
15
16
17
18
pointertest4.c
Cygwin64+mintty+bash+GNU C
int i, *p, a[] = {0,1,2,3,4,5,6,7,8,9};
$ gcc pointertest4.c && ./a
&a[0]=0x000000000022aa90
p = ? 0x000000000022aa98
*p=0x12345678
a[0]=0000000000
a[1]=0x00000001
a[2]=0x12345678
a[3]=0x00000003
a[4]=0x00000004
a[5]=0x00000005
a[6]=0x00000006
a[7]=0x00000007
a[8]=0x00000008
a[9]=0x00000009
printf("&a[0]=%#0*p\n", sizeof(&a[0])*2+2, &a[0]);
printf("p = ? ");
scanf("%p", &p);
printf("*p=");
scanf("%i", p);
for (i = 0; i < sizeof(a) / sizeof(*a); i++) {
printf("a[%d]=%#0*x\n", i, sizeof(*a)*2+2, a[i]);
}
結果がどうなるかは別として
アドレス演算子を使って
変数のアドレスを入れなくても
適当な値を入れても動く。
29
教科書pp.207-272.
ポインタ変数
6
7
8
9
10
11
12
13
14
15
16
17
18
pointertest4.c
Cygwin64+mintty+bash+GNU C
int i, *p, a[] = {0,1,2,3,4,5,6,7,8,9};
$ gcc pointertest4.c && ./a
&a[0]=0x000000000022aa90
p=0x000000000022aa92
*p=0x12345678
a[0]=0x56780000
a[1]=0x00001234
a[2]=0x00000002
a[3]=0x00000003
a[4]=0x00000004
a[5]=0x00000005
a[6]=0x00000006
a[7]=0x00000007
a[8]=0x00000008
a[9]=0x00000009
printf("&a[0]=%#0*p\n", sizeof(&a[0])*2+2, &a[0]);
printf("p=");
scanf("%p", &p);
printf("*p=");
scanf("%i", p);
for (i = 0; i < sizeof(a) / sizeof(*a); i++) {
printf("a[%d]=%#0*x\n", i, sizeof(*a)*2+2, a[i]);
}
結果が正しいかどうかは別として
配列の途中のアドレスを
ポインタに入れることも出来る
30
動的配列
多くの問題では
配列のサイズを事前に
(コンパイルの段階では)
決められない。
＝
実行時、プログラムに
与えるデータや
パラメータによって
配列のサイズは決まる。
プログラムの実行時に
配列のサイズを適宜に決める事が必要
malloc, calloc, realloc, free 関数
31
malloc 関数
• void *malloc(site_t size);
• 動的にメモリを確保する
• 引数:
• size: 確保するメモリのバイト数
• 戻り値
• 確保したメモリへのポインタを返す
• 確保したメモリの内容は初期化されない
• エラーの場合は NULL を返す
JM: malloc (3)
32
calloc 関数
• void *calloc(site_t nobj,
site_t size);
• 動的にメモリを確保する
• 引数:
• nobj: メモリを確保する要素数
• size: 1要素辺りのバイト数
• 戻り値
• 確保したメモリへのポインタを返す
• 確保したメモリの内容は0で初期化される
• エラーの場合は NULL を返す
JM: malloc (3)
33
realloc 関数
• void *realloc(void *p,
site_t size);
• 動的に確保したメモリのサイズを変更する
• 引数:
• p: サイズを変更するメモリへのポインタ
• size: 変更後のバイト数
• 戻り値
• 確保したメモリへのポインタを返す
• サイズ変更前後で小さい方のサイズまでは
前の内容が維持される
• 増加した部分のメモリの内容は初期化されない
• エラーの場合は NULL を返す
• 元のブロックは維持される
JM: malloc (3)
34
free 関数
• void free(void *p);
• 動的に確保したメモリを解放する
• 引数:
• p: 解放するメモリへのポインタ
JM: malloc (3)
35
関数の作成
演習
36
演習: is_leap_year～.c の関数化
• 第4週資料 p.41. の演習をしましょう
37
演習: is_odd.c
• print_evenodd.c を参考に以下の関数を作り
なさい
• int is_odd(int i);
• 奇数かどうか判定する
• 引数
• i:
判定する整数
• 戻り値
2014-06-20追加
• 奇数なら1、奇数でなければ0を返す
• is_odd_test.c と共にコンパイルして動作を
確認すること
Cygwin64+mintty+bash+GNU C
$ gcc is_odd_test.c is_odd.c && ./a
i = ? 1
odd number
38
演習: is_even.c
• print_evenodd.c を参考に以下の関数を作り
なさい
• int is_even(int i);
• 偶数かどうか判定する
• 引数
• i:
判定する整数
• 戻り値
2014-06-20追加
• 偶数なら1、偶数でなければ0を返す
• is_even_test.c と共にコンパイルして動作を
確認すること
Cygwin64+mintty+bash+GNU C
$ gcc is_even_test.c is_even.c && ./a
i = ? 2
even number
39
演習: is_prime.c
• print_isprime.c を参考に以下の関数を作り
なさい
• int is_prime(int i);
• 素数かどうか判定する
• 引数
• i:
判定する整数
• 戻り値
2014-06-20追加
• 素数なら1、素数でなければ0を返す
• is_prime_test.c と共にコンパイルして動作
を確認すること
Cygwin64+mintty+bash+GNU C
$ gcc is_prime_test.c is_prime.c && ./a
i = ? 7
prime number
40
演習: swapi.c
• 以下の関数を作りなさい
• void swapi(int *a, int *b);
• 引数で与えた変数の値を交換する
• 引数
• a, b: 値を交換する変数へのポインタ
2014-06-20追加
• swapi_test.c と共にコンパイルして動作を
Cygwin64+mintty+bash+GNU C
確認すること
ヒント
第6週資料pp.43-44.
本資料 p.6. を参考にせよ
$
a
b
a
b
gcc swapi_test.c swapi.c && ./a
= ? 1
= ? 2
= 2
= 1
41
演習: ヘッダファイルの作成
• ここまでに作った is_odd, is_even,
is_prime, swapi 関数のプロトタイプ宣言
を myfunc.h というファイルにまとめよ。
• 第4週資料p.38.のis_leap_year_func.h
を参考にせよ。
• include ガードの識別子は MYFUNC_H と
せよ。
誤:3週資料
正:4週資料
42
エラトステネスのふるい
• N以下の整数について既知の素数とその倍
数をふるい落とすことで素数を判定するアル
ゴリズム
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99 100
43
エラトステネスのふるい
• 𝑁以下の素数の探索
1. 2以上𝑁以下の整数を探索リストに入れる
2. 検索リストの先頭の数𝑥
(これは素数)が𝑥 ≤ 𝑁なら
2
3
4
5
ステップ3
11 12 13 14 15
そうでなければステップ4へ
21 22 23 24 25
3. 𝑥を素数リストに移し
31 32 33 34 35
𝑥の倍数を探索リストから
41 42 43 44 45
ふるい落とした後
51 52 53 54 55
ステップ2に戻る
61 62 63 64 65
4. 探索リストに残った数を
71 72 73 74 75
素数リストに移動
6
7
8
9
10
16
17
18
19
20
26
27
28
29
30
36
37
38
39
40
46
47
48
49
50
56
57
58
59
60
66
67
68
69
70
76
77
78
79
80
90
81
82
83
84
85
86
87
88
89
91
92
93
94
95
96
97
98
99 100
44
エラトステネスのふるい
探索リスト先頭の数は素数
• 𝑁以下の素数の探索
先頭の2を素数と判定し
2の倍数を探索リストから削除する
1. 2以上𝑁以下の整数を探索リストに入れる
2. 検索リストの先頭の数𝑥
(これは素数)が𝑥 ≤ 𝑁なら
2
3
4
5
6
7
8
ステップ3
11 12 13 14 15 16 17 18
そうでなければステップ4へ
21 22 23 24 25 26 27 28
3. 𝑥を素数リストに移し
31 32 33 34 35 36 37 38
𝑥の倍数を探索リストから
41 42 43 44 45 46 47 48
ふるい落とした後
51 52 53 54 55 56 57 58
ステップ2に戻る
61 62 63 64 65 66 67 68
4. 探索リストに残った数を
71 72 73 74 75 76 77 78
素数リストに移動
9
10
19
20
29
30
39
40
49
50
59
60
69
70
79
80
90
81
82
83
84
85
86
87
88
89
91
92
93
94
95
96
97
98
99 100
45
エラトステネスのふるい
探索リスト先頭の数は素数
• 𝑁以下の素数の探索
先頭の3を素数と判定し
3の倍数を探索リストから削除する
1. 2以上𝑁以下の整数を探索リストに入れる
2. 検索リストの先頭の数𝑥
(これは素数)が𝑥 ≤ 𝑁なら
2
3
4
5
6
7
8
ステップ3
11 12 13 14 15 16 17 18
そうでなければステップ4へ
21 22 23 24 25 26 27 28
3. 𝑥を素数リストに移し
31 32 33 34 35 36 37 38
𝑥の倍数を探索リストから
41 42 43 44 45 46 47 48
ふるい落とした後
51 52 53 54 55 56 57 58
ステップ2に戻る
61 62 63 64 65 66 67 68
4. 探索リストに残った数を
71 72 73 74 75 76 77 78
素数リストに移動
9
10
19
20
29
30
39
40
49
50
59
60
69
70
79
80
90
81
82
83
84
85
86
87
88
89
91
92
93
94
95
96
97
98
99 100
46
エラトステネスのふるい
探索リスト先頭の数は素数
• 𝑁以下の素数の探索
先頭の5を素数と判定し
5の倍数を探索リストから削除する
1. 2以上𝑁以下の整数を探索リストに入れる
2. 検索リストの先頭の数𝑥
(これは素数)が𝑥 ≤ 𝑁なら
2
3
4
5
6
7
8
ステップ3
11 12 13 14 15 16 17 18
そうでなければステップ4へ
21 22 23 24 25 26 27 28
3. 𝑥を素数リストに移し
31 32 33 34 35 36 37 38
𝑥の倍数を探索リストから
41 42 43 44 45 46 47 48
ふるい落とした後
51 52 53 54 55 56 57 58
ステップ2に戻る
61 62 63 64 65 66 67 68
4. 探索リストに残った数を
71 72 73 74 75 76 77 78
素数リストに移動
9
10
19
20
29
30
39
40
49
50
59
60
69
70
79
80
90
81
82
83
84
85
86
87
88
89
91
92
93
94
95
96
97
98
99 100
47
エラトステネスのふるい
探索リスト先頭の数は素数
• 𝑁以下の素数の探索
先頭の7を素数と判定し
7の倍数を探索リストから削除する
1. 2以上𝑁以下の整数を探索リストに入れる
2. 検索リストの先頭の数𝑥
(これは素数)が𝑥 ≤ 𝑁なら
2
3
4
5
6
7
8
ステップ3
11 12 13 14 15 16 17 18
そうでなければステップ4へ
21 22 23 24 25 26 27 28
3. 𝑥を素数リストに移し
31 32 33 34 35 36 37 38
𝑥の倍数を探索リストから
41 42 43 44 45 46 47 48
ふるい落とした後
51 52 53 54 55 56 57 58
ステップ2に戻る
61 62 63 64 65 66 67 68
4. 探索リストに残った数を
71 72 73 74 75 76 77 78
素数リストに移動
9
10
19
20
29
30
39
40
49
50
59
60
69
70
79
80
90
81
82
83
84
85
86
87
88
89
91
92
93
94
95
96
97
98
99 100
48
エラトステネスのふるい
先頭の11は≤ 100でないので
• 𝑁以下の素数の探索
探索リストに残った数を素数と判定
1. 2以上𝑁以下の数を探索リストに入れる
2. 検索リストの先頭の数𝑥
(これは素数)が𝑥 ≤ 𝑁なら
2
3
4
5
6
7
8
ステップ3
11 12 13 14 15 16 17 18
そうでなければステップ4へ
21 22 23 24 25 26 27 28
3. 𝑥を素数リストに移し
31 32 33 34 35 36 37 38
𝑥の倍数を探索リストから
41 42 43 44 45 46 47 48
ふるい落とした後
51 52 53 54 55 56 57 58
ステップ2に戻る
61 62 63 64 65 66 67 68
4. 探索リストに残った数を
71 72 73 74 75 76 77 78
素数リストに移動
9
10
19
20
29
30
39
40
49
50
59
60
69
70
79
80
90
81
82
83
84
85
86
87
88
89
91
92
93
94
95
96
97
98
99 100
49
エラトステネスのふるい
通常の配列による探索リスト
• メモリ上のイメージ
探索リストの初期化
添字
n-1
0
2
1
3
2
4
3
5
4
6
5
7
6
8
:
:
98
100
#define N 100
int i, j = 2, n = N;
// n は探索リストの件数
int slist[N-2];
for (i = 0; i < n; i++) {
slist[i] = j++;
}
訂正2014-06-20
誤:slist[N-1]
正:slist[N-2]
訂正2014-06-20
誤:n = N
正:n = N - 2
50
エラトステネスのふるい
通常の配列による探索リスト
• 値の削除
添字
n-1
添字
0
2
0
2
1
3
1
3
2
4
2
5
3
5
3
6
4
6
4
7
5
7
5
8
6
8
:
:
:
:
97
100
98
100
98
100
4を削除
n-1
普通の配列だと
値を削除して
詰める処理に
時間がかかる
51
エラトステネスのふるい
通常の配列による探索リスト
• 探索リストの消費メモリ
• 2以上N以下の数を配列に保存すると
Nが32bitで表現可能な整数と仮定して
初期状態で(N-1)*4バイト必要
普通の配列だと
値を削除して
詰める処理に
時間がかかる
探索リストの初期化
探索リストから値xの削除
#define N 100
for (i = 0; i < n; i++) {
if (slist[i] == x) {
for (j = 0; i + j + 1 < n; j++) {
slist[i + j] = slist[i + j + 1];
// ↑ 探索リストから x を削除し
// ↑ 以降の値を１つずつずらして詰める
}
n--; // 探索リストの件数をxを削除した分減らす
break;
}
}
int i, j = 2, n = N-2;
// n は探索リストの件数
int slist[N-2];
for (i = 0; i < n; i++) {
slist[i] = j++;
}
訂正あり
p.49.参照
52
エラトステネスのふるい
通常の配列による探索リスト
• 探索リストの消費メモリ
• 2以上N以下の数を配列に保存すると
Nが32bitで表現可能な整数と仮定して
初期状態で(N-1)*4バイト必要
探索リストで値xの判定
for (i = 0; i < n; i++) {
if (slist[i] == x) {
// x が探索リストにある場合の処理
break;
}
}
53
エラトステネスのふるい
通常の配列による探索リスト
• 値の削除を工夫
添字
添字
n-1
0
2
0
2
1
3
1
3
2
4
2
-1
3
5
3
5
4
6
4
6
5
7
5
7
6
8
6
8
:
:
:
:
98
100
98
100
4を削除
n-1
使ってない値を
マイナスにして
検索時に
無視すると
削除は速くなるが
値の検索でごみ
になった-1も
処理しなければ
いけなくなる
マイナス値も
扱う場合は
使えない方法
54
エラトステネスのふるい
通常の配列による探索リスト
• 探索リストの消費メモリ
• 2以上N以下の数を配列に保存すると
Nが32bitで表現可能な整数と仮定して
初期状態で(N-1)*4バイト必要
削除は速いが
検索時にゴミも
検索するので
検索が遅くなる
探索リストの初期化
探索リストから値xの削除
#define N 100
for (i = 0; i < n; i++) {
if (slist[i] == x) {
slist[i] = -1;
// ↑ 探索リストから x を削除
break;
}
}
訂正2014-06-20
誤:slist[i+j]
正:slist[i]
int i, j = 2, n = N-2;
// n は探索リストの件数
int slist[N-2];
for (i = 0; i < n; i++) {
slist[i] = j++;
}
訂正あり
p.49.参照
55
エラトステネスのふるい
通常の配列による探索リスト
• 探索リストの消費メモリ
• 2以上N以下の数を配列に保存すると
Nが32bitで表現可能な整数と仮定して
初期状態で(N-1)*4バイト必要
探索リストで値xの判定
for (i = 0; i < n; i++) {
if (slist[i] == x) {
// x が探索リストにある場合の処理
break;
}
}
56
エラトステネスのふるい
1方向リストによる探索リスト
• メモリ上のイメージ
探索リストの初期化
添字
N-1
訂正2014-06-20
誤:slist[N][2]
正:slist[N-1][2]
#define N 100
[0][0]
2
[0][1]
1
[1][0]
3
[1][1]
2
[2][0]
4
[2][1]
3
[3][0]
5
:
:
[98][1]
99
[99][0]
?
[99][1]
-1
int i, j = 2;
int slist[N-1][2];
for (i = 0; i
slist[i][0]
slist[i][1]
}
slist[i][1] =
訂正2014-06-20
誤:i<N-1でしたが
正:i<N-2の誤りでした
< N - 2; i++) {
= j++;
= i+1; // 次の値の格納位置
-1; // 終端記号
2つの値をペアとして扱い
1つ目を次の値の格納場所の添え字
2つ目を格納値
として利用している
マイナスの値を次の値がない目印
つまり終端記号として用いている
訂正2014-06-20
誤:slist[i][0]
正:slist[i][1]
1つ目の値を
ポインターっぽく
使っている
57
エラトステネスのふるい
1方向リストによる探索リスト
• 値の削除
添字
N-1
[0][0]
2
[0][1]
1
[1][0]
3
[1][1]
2
[2][0]
5
[2][1]
4
[3][0]
5
:
:
[98][1]
99
[99][0]
?
[99][1]
-1
2
3
4
5
100
?
×
4を削除
2
3
5
5
100
?
×
58
エラトステネスのふるい
1方向リストによる探索リスト
• 探索リストの消費メモリ
• 2以上N以下の数を配列に保存すると
Nが32bitで表現可能な整数と仮定して
初期状態で(N)*4*2バイト必要
探索リストの初期化
探索リストから値xの削除
メモリが通常の配列の
倍必要
#define N 100
int i, j = 2;
int slist[N-1][2];
for (i = 0; i
slist[i][0]
slist[i][1]
}
slist[i][0] =
使わなくなった
メモリは
無駄になるが
削除が高速
< N - 2; i++) {
= j++;
= i+1; // 次の値の格納位置
-1; // 終端記号
訂正あり
p.56.参照
for (i = 0; 0 <= slist[i][1]; i=slist[i][1]) {
if (slist[i][0] == x) {
j = slist[i][1];
slist[i][0] = slist[j][0];
slist[i][1] = slist[j][1];
// ↑ 探索リストの x が格納されている要素を
// ↑ 次の要素で上書き
break;
}
}
59
エラトステネスのふるい
1方向リストによる探索リスト
• 探索リストの消費メモリ
• 2以上N以下の数を配列に保存すると
Nが32bitで表現可能な整数と仮定して
初期状態で(N)*4*2バイト必要
探索リストで値xの判定
for (i = 0; 0 <= slist[i][1]; i=slist[i][1]) {
if (slist[i][0] == x) {
// x が探索リストにある場合の処理
break;
}
}
60
エラトステネスのふるい
フラグ配列による探索リスト(int版)
• メモリ上のイメージ
探索リストの初期化
添字
N
0
0
#define N 100
1
0
int slist[N+1] = {0};
2
0
3
0
4
0
5
0
6
0
:
:
100
0
添え字をxとして考え
格納値がゼロなら有効
格納値が非ゼロなら無効
と考える
61
エラトステネスのふるい
フラグ配列による探索リスト(int版)
• 値の削除
添字
添字
N
0
0
0
0
1
0
1
0
2
0
2
0
3
0
4を削除
3
0
4
0
4
1
5
0
5
0
6
0
6
0
:
:
:
:
100
0
100
0
N
使ってない値を
非ゼロ
削除は速い
検索はごみも
検索するので
あまり速くない
62
エラトステネスのふるい
フラグ配列による探索リスト(int版)
• 探索リストの消費メモリ
• 2以上N以下の数を配列に保存すると
Nが32bitで表現可能な整数と仮定して
こんなに必要？
初期状態で(N+1)*4バイト必要
探索リストの初期化
探索リストから値xの削除
#define N 100
slist[x] = 1;
int slist[N] = {0};
探索リストで値xの判定
if (!slist[x]) {
// x が 0 の時の処理
// x が探索リストにある場合の処理
}
検索しなくて良いので
削除は高速
63
エラトステネスのふるい
フラグ配列による探索リスト(char版)
• 探索リストの消費メモリ
• 2以上N以下の数を配列に保存すると
初期状態で(N+1)バイト必要
char で十分
必要メモリが
1/4になった
もっと減
らせるのでは？
探索リストの初期化
探索リストから値xの削除
#define N 100
slist[x] = 1;
char slist[N] = {0};
探索リストで値xの判定
if (!slist[x]) {
// x が 0 の時の処理
// x が探索リストにある場合の処理
}
検索しなくて良いので
削除は高速
64
エラトステネスのふるい
フラグ配列による探索リスト(1bit版)
• 探索リストの消費メモリ
• 2以上N以下の数を配列に保存すると
初期状態で(N+8)/8バイト必要
探索リストの初期化
探索リストから値xの削除
#define N 100
slist[x/8] |= 1<<(x%8);
char slist[(N+8)/8] = {0};
探索リストで値xの判定
訂正2014-06-20
誤:slist[x/7]
正:slist[x/8]
if (!(slist[x/8] & (1<<(x%8)))) {
// x が 0 の時の処理
// x が探索リストにある場合の処理
}
bit毎のOR演算による
bitマスクを用いて
狙ったビットをONにする
bit毎のAND演算による
bitマスクを用いて
狙ったビットのON/OFFを調べる
1bitでも十分
charの場合から
更に1/8になった
検索しなくて良いので
削除は高速
65
演習: print_prime_lt～.c
• エラストテネスのふるいによりN未満の素数を小さい順に全て表示せよ
• print_prime_lt.c を元に以下のファイル名で作成せよ
• print_prime_lt_a1.c
• 通常の配列版(削除した値を詰めた場合)
• print_prime_lt_a2.c
• 通常の配列版(削除値を-1にした場合)
• print_prime_lt_b.c
• 一方向リスト版
• print_prime_lt_c1.c
• フラグ配列int版
• print_prime_lt_c2.c
• フラグ配列char版
• print_prime_lt_c3.c
• フラグ配列1bit版
66
演習: print_prime_lt～.c
• 前頁で作成したプログラムについて速度を比
較してみましょう
• Cygwin の場合 time コマンドを用いると実
行実感が計測出来ます。例えば ./a の実
行時間を計測するには以下のようにします。
mintty+bash+GNU C
$ time ./a
67
参考文献
• [1] B.W.カーニハン/D.M.リッチー著石田晴久
訳、プログラミング言語C 第2版 ANSI 規格準
拠、共立出版(1989)

Download Report