C言語入門

1
C言語入門
第14週
プログラミング言語Ⅰ(実習を含む。),
計算機言語Ⅰ・計算機言語演習Ⅰ,
情報処理言語Ⅰ(実習を含む。)
2
復習
3
確認問題: ポインタのポインタ
• *p, *pp, **pp はいくらか？
hoge.c
6
7
8
9
10
11
12
13
14
15
int
a = 'h'; // = 0x68 = 104
int *p = &a;
int **pp = &p;
printf("&a = %p\n",
printf("&p = %p\n",
printf("&pp = %p\n",
printf("sizeof(a) =
printf("sizeof(p) =
printf("sizeof(pp) =
&a);
&p);
&pp);
%d\n", sizeof(a));
%d\n", sizeof(p));
%d\n", sizeof(pp));
&p
0x22aab8 = &pp
&a
0x22aac0 = &p
p
'h'
mintty + bash + GNU C
$ gcc hoge.c && ./a
&a = 0x22aacc
&p = 0x22aac0
&pp = 0x22aab8
sizeof(a) = 4
sizeof(p) = 8
sizeof(pp) = 8
pp
0x22aacc = &a
a
4
確認問題: ポインタのポインタ
• pp + 1, *(pp + 1), pp[1] はいくらか？
hoge.c
6
7
8
9
10
11
12
13
14
15
int
a = 'h'; // = 0x68 = 104
int *p = &a;
int **pp = &p;
printf("&a = %p\n",
printf("&p = %p\n",
printf("&pp = %p\n",
printf("sizeof(a) =
printf("sizeof(p) =
printf("sizeof(pp) =
&a);
&p);
&pp);
%d\n", sizeof(a));
%d\n", sizeof(p));
%d\n", sizeof(pp));
&p
0x22aab8 = &pp
&a
0x22aac0 = &p
p
'h'
mintty + bash + GNU C
$ gcc hoge.c && ./a
&a = 0x22aacc
&p = 0x22aac0
&pp = 0x22aab8
sizeof(a) = 4
sizeof(p) = 8
sizeof(pp) = 8
pp
0x22aacc = &a
a
5
確認問題: 配列と文字列
• sizeof(s), strlen(s), sizeof(p), strlen(p), p[3] は
いくらか？
6
7
8
9
10
hoge.c
mintty + bash + GNU C
char s[] = "hello";
char *p = s;
p++;
$ gcc hoge.c && ./a
sizeof(&s[0]) = 8
printf("sizeof(&s[0]) = %d\n", sizeof(&s[0]));
'e'
'l'
'l'
'o'
'\0'
s[0]
s[1]
s[2]
s[3]
s[4]
s[5]
0x68
0x65
0x6c
0x6c
0x6f
0x00
s[0]
s[1]
s[2]
s[3]
s[4]
s[5]
=
'h'
6
探索
7
総当たり探索
• 先頭から1つ探索する方法
• データがn個ある時
• 最悪n個全て調べる必要がある
• 見つかる場合の平均探索回数n/2回の確率
• 簡単だけど速くない
541
...
2
5
7
11
...
541
s[0]
s[1]
s[2]
s[3]
...
s[99]
8
総当たり探索
• 簡単だけど遅い
asearchi.c
4
5
6
7
8
9
10
11
12
13
14
15
16
int *asearchi(int key, int *data, int n)
{
int i;
for (i = 0; i < n; i++) {
#ifdef DEBUG
printf("[%d] = %d\n", i, data[i]);
#endif
if (key == data[i]) {
return &data[i];
}
}
return NULL;
}
asearchi_test.c
26
27
28
29
30
31
p = asearchi(key, data, sizeof(data)/sizeof(int));
if (p) {
printf("data[%d] = %d\n", p - data, *p);
} else {
printf("not found.\n");
}
asearchi_test.c
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int data[] =
2,
3,
31, 37,
73, 79,
127, 131,
179, 181,
233, 239,
283, 293,
353, 359,
419, 421,
467, 479,
};
int key;
int *p;
{
5,
41,
83,
137,
191,
241,
307,
367,
431,
487,
7,
43,
89,
139,
193,
251,
311,
373,
433,
491,
11,
47,
97,
149,
197,
257,
313,
379,
439,
499,
13,
53,
101,
151,
199,
263,
317,
383,
443,
503,
17,
59,
103,
157,
211,
269,
331,
389,
449,
509,
19,
61,
107,
163,
223,
271,
337,
397,
457,
521,
23,
67,
109,
167,
227,
277,
347,
401,
461,
523,
mintty + bash + GNU C
$ gcc asearchi_test.c asearchi.c -DDEBUG && ./a
13key = ?
[0] = 2
[1] = 3
[2] = 5
[3] = 7
[4] = 11
[5] = 13
data[5] = 13
29,
71,
113,
173,
229,
281,
349,
409,
463,
541,
9
演習: asearchi.c
• int型のデータを総当たり探索する関数 asearchi を作
成せよ
• asearchi_test.c と共にコンパイルして動作を確認せ
よ
• 引数
• int key : 検索したい値へのポインタ
• int *data : 検索対象のデータ集合へのポインタ
• int n
: データの要素数
• 戻り値
• 見つけたデータへのポインタを返す
• 見つからなかった場合はNULLを返す
mintty + bash + GNU C
$ gcc asearchi_test.c asearchi.c && ./a
key = ? 31
data[10] = 31
10
教科書 pp.198-202.
2分探索
• 昇順ソート済みのデータから探す
• 探す領域を半分に探す範囲を絞り込む
• データがn個ある時
• 最悪 𝑛個調べれば良い
• 速いけど事前にソートが必要
13
2
3
5
7
11
13
17
19
23
s[0]
s[1]
s[2]
s[3]
s[4]
s[5]
s[6]
s[7]
s[8]
11
教科書 pp.198-202.
2分探索
13
• 全体を2つに分けて
• 中央の値と比較して行く
2
3
5
7
11
13
17
19
23
s[0]
s[1]
s[2]
s[3]
s[4]
s[5]
s[6]
s[7]
s[8]
2
3
5
7
11
13
17
19
23
s[0]
s[1]
s[2]
s[3]
s[4]
s[5]
s[6]
s[7]
s[8]
2
3
5
7
13
17
19
23
s[0]
s[1]
s[2]
s[3]
s[5]
s[6]
s[7]
s[8]
探索成功
11
s[4]
12
教科書 pp.198-202.
2分探索
18
• 全体を2つに分けて
• 中央の値と比較して行く
2
3
5
7
11
13
17
19
23
s[0]
s[1]
s[2]
s[3]
s[4]
s[5]
s[6]
s[7]
s[8]
2
3
5
7
11
13
17
19
23
s[0]
s[1]
s[2]
s[3]
s[4]
s[5]
s[6]
s[7]
s[8]
2
3
5
7
11
13
17
s[0]
s[1]
s[2]
s[3]
s[4]
s[5]
s[6]
探索失敗
19
s[7]
23
s[8]
13
教科書 pp.198-202.
2分探索
• 標準ライブラリ関数ライクな実装例
bsearchi.c
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int *bsearchi(int key, int *data, int n)
{
int cmp;
if (n <= 0) return NULL;
#ifdef DEBUG
printf("%d: [%d] = %d\n", n, n/2, data[n/2]);
#endif
if (key < data[n/2]) {
return bsearchi(key, data, n/2);
} else if (data[n/2] < key) {
return bsearchi(key, &data[n/2+1], n - n/2 - 1);
} else {
return &data[n/2];
}
}
bsearchi_test.c
26
27
28
29
30
31
p = bsearchi(key, data, sizeof(data)/sizeof(int));
if (p) {
printf("data[%d] = %d\n", p - data, *p);
} else {
printf("not found.\n");
}
bsearchi_test.c
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int data[] =
2,
3,
31, 37,
73, 79,
127, 131,
179, 181,
233, 239,
283, 293,
353, 359,
419, 421,
467, 479,
};
int key;
int *p;
{
5,
41,
83,
137,
191,
241,
307,
367,
431,
487,
7,
43,
89,
139,
193,
251,
311,
373,
433,
491,
11,
47,
97,
149,
197,
257,
313,
379,
439,
499,
13,
53,
101,
151,
199,
263,
317,
383,
443,
503,
17,
59,
103,
157,
211,
269,
331,
389,
449,
509,
19,
61,
107,
163,
223,
271,
337,
397,
457,
521,
23,
67,
109,
167,
227,
277,
347,
401,
461,
523,
29,
71,
113,
173,
229,
281,
349,
409,
463,
541,
mintty + bash + GNU C
$ gcc bsearchi_test.c bsearchi.c -DDEBUG && ./a
key = ? 17
100: [50] = 233
50: [25] = 101
25: [12] = 41
12: [6] = 17
data[6] = 17
14
演習: bsearchi.c
• 昇順ソート済みのint型のデータを2分探索する関数
bsearchi を作成せよ
• bsearchi_test.c と共にコンパイルして動作を確認せ
よ
• 引数
• int key : 検索したい値へのポインタ
• int *data : 検索対象のデータ集合へのポインタ
• int n
: データの要素数
• 戻り値
• 見つけたデータへのポインタを返す
• 見つからなかった場合はNULLを返す
mintty + bash + GNU C
$ gcc bsearchi_test.c bsearchi.c && ./a
key = ? 31
data[10] = 31
15
教科書 pp.198-202.
標準ライブラリの2分探索関数
• 標準ライブラリ関数
•
void *bsearch(const void *key, const void *base,
size_t n, size_t size,
int (*cmp)(const void *keyval, const void *datum));
• 引数
•
•
•
•
•
key
base
n
size
cmp
:
:
:
:
:
検索したい値へのポインタ
検索対象のデータ集合へのポインタ
データの要素数
データの1要素当りのバイト数
データ比較用の関数へのポインタ
• 戻り値
• マッチした項目へのポインタを返す
• マッチした項目がない場合NULLを返す
16
教科書 pp.198-202.
標準ライブラリの2分探索関数
• 比較関数さえ用意すれば簡単に検索出来る
bsearch_test.c
29
30
31
32
33
34
p = bsearch(&key, data, sizeof(data)/sizeof(int), sizeof(int), (int (*)(const void*, const void*))cmp);
if (p) {
printf("data[%d] = %d\n", p - data, *p);
} else {
printf("not found.d\n");
}
bsearch_test.c
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
{
int data[] = {
2,
3,
5,
31, 37, 41,
73, 79, 83,
127, 131, 137,
179, 181, 191,
233, 239, 241,
283, 293, 307,
353, 359, 367,
419, 421, 431,
467, 479, 487,
};
int key;
int *p;
7,
43,
89,
139,
193,
251,
311,
373,
433,
491,
bsearch_test.c
11,
47,
97,
149,
197,
257,
313,
379,
439,
499,
13,
53,
101,
151,
199,
263,
317,
383,
443,
503,
17,
59,
103,
157,
211,
269,
331,
389,
449,
509,
19,
61,
107,
163,
223,
271,
337,
397,
457,
521,
23,
67,
109,
167,
227,
277,
347,
401,
461,
523,
29,
71,
113,
173,
229,
281,
349,
409,
463,
541,
4
5
6
7
int cmp(const int *keyval, const int *datum)
{
return *keyval - *datum;
}
mintty + bash + GNU C
$ gcc bsearch_test.c && ./a
key = ? 113
data[29] = 113
17
関数へのポインタ
• ポインタ変数に * が付いたら何になるか？
関数の定義
int cmp(int *a, int *b)
{
return *a - *b;
}
関数のプロトタイプ宣言
int cmp(int *a, int *b);
関数へのポインタ変数の宣言
int (*fnc)(int *a, int *b);
関数へのポインタに代入と呼び出し
fnc = cmp;
(*fnc)(&x, &y);
cmp が
戻り値が int 型
引数が (int *a, int *b) の
関数という意味になる
fnc がポインタ変数で
*fnc が
戻り値が int 型
引数が (int *a, int *b) の
関数という意味になる
*fnc とすれば
関数へのポインタが関数になる
演算子の優先順位は
高*>()低なので*fncに()が必要
18
関数へのポインタ
• 関数関連の宣言では引数名は省略可能
• 関数のプロトタイプ宣言
• 関数へのポインタ変数の宣言
関数のプロトタイプ宣言
関数のプロトタイプ宣言
int cmp(int *a, int *b);
int cmp(int * , int * );
関数へのポインタ変数の宣言
関数へのポインタ変数の宣言
int (*fnc)(int *a, int *b);
int (*fnc)(int * , int * );
19
関数へのポインタ
• 汎用型の場合キャストが必要
• 例: qsort や bsearch へ渡す比較関数
関数のプロトタイプ宣言
int cmp(int *a, int *b);
関数へのポインタ変数の宣言
int (*fnc)(void *a, void *b);
関数へのポインタに代入と呼び出し
fnc = (int (*)(void *, void *)) cmp;
(*fnc)(&x, &y);
20
void 型と void 型へのポインタ
• void(=空洞)つまり大きさがない
• 関数に引数や戻り値がないことを意味する
• ポインタの指し示す先の大きさが不明(特定の型
に縛られない)であることを意味する
変数の宣言
void a; // void 型の変数はないのでコンパイルエラー
void *p; // p が void 型へのポインタ
0x～0
0x～0
0x～1
0x～1
0x～2
0x～3
p=
0x～0
0x～2
0x～3
大きさが0バイトのデータ
つまり void a; には意味がないが
大きさが不明のデータでも先頭アドレス
つまり void *p; には意味がある
21
void 型と void 型へのポインタ
• void * 型は使用時に大きさを決めて使う
• 適当な型へのポインタとしてキャストする
void 型ポインタの例
int a;
void *p = &a;
// p に a のアドレスが入る
*((int *)p) = 1; // p は void* なので *p は void だが
// p を int* にキャストすると *p が int になる
0x～0
0x～0
0x～1
0x～1
0x～2
0x～3
p=
0x～0
0x～2
0x～3
*p は void なので意味がない
*((int*)p) は int なので意味がある
22
商と剰余
23
整数除算の商と剰余
•
•
•
知っているようで知らない商と剰余の定義
整数𝑚, 𝑛, 𝑞, 𝑟 (𝑛 ≠ 0)について𝑚 ÷ 𝑛とした時、𝑞が商、 𝑟が剰余
剰余の一般形: 𝑚 = 𝑞𝑛 + 𝑟 ただし 𝑟 < 𝑛
例:
•
/ 3 = 1 余り 2、 2 余り -1
/ 3 = -1 余り -2、 -2 余り 1
/ -3 = -1 余り 2、 -2 余り 1
/ -3 = 1 余り -2、 2 余り 1
追加の制約がないと
一意に決まらない
5
-5
5
-5
/ 3 = 1 余り
/ 3 = -2 余り
/ -3 = -1 余り
/ -3 = 2 余り
一意に決まるが
𝑚, 𝑛の符号により
𝑞, 𝑟の絶対値が変わる
最小非負剰余: 𝑚 = 𝑞𝑛 + 𝑟 ただし 0 ≤ 𝑟 < 𝑛
例:
•
5
-5
5
-5
2
1
2
1
𝑛
絶対値最小剰余: 𝑚 = 𝑞𝑛 + 𝑟 ただし − 2 ≤ 𝑟 <
例:
5
-5
5
-5
/ 3 = 2 余り -1
/ 3 = -2 余り 1
/ -3 = -2 余り 1
/ -3 = 2 余り 1
𝑛
2
一意に決まるが
𝑚, 𝑛が共に正の場合
感覚に合わない
24
負の数の除算と剰余算
• C89では実装依存だった
• 「/に対する切捨ての方向および%に対する結果の符号は,負の被演算子に
対しては機種依存する」([1]p.50)
• 例：以下のいずれも有り得る
• 5 / 3
• -5 / 3
• 5 / -3
• -5 / -3
= 1 余り 2
= -1 余り -2、-2 余り 1
= -1 余り 2、-2 余り -1
= 1 余り -2、 2 余り 1
• C99以降は以下のように定義された
• a/bはゼロに向かった切捨て
• (a/b)*b + a%b は a と等しい
• 例: 必ず以下のようになる
• 5 / 3
• -5 / 3
• 5 / -3
• -5 / -3
= 1 余り 2
= -1 余り -2
= -1 余り 2
= 1 余り -2
実装依存なので
安心して使えない
絶対値最小の商
𝑚 = 𝑞𝑛 + 𝑟
ただし 𝑟 < 𝑛 かつ 𝑞𝑛 ≤ 𝑚
きちんと定義されたので
安心して使えるようになった
a,bが共に正の時と
商と剰余の絶対値も一致して
使い易い
25
除算と剰余算: C89
K&R 第2版 p.50
整数の割り算では小数部分は切り捨てられる。式
x % y
はxをyで割った余りで、xがｙでちょうど割り切れる
なら0となる。
/に対する切捨ての方向および%に対する結果の
符号は、負の被演算子に対しては機種依存する。
26
除算と剰余算: C99
ISO/IEC 9899:1999 Programming languages C (C99) + TC1 + TC2 + TC3
Committee Draft - September 7, 2007 p.82.
6.5.5 Multipliative operators
5
The result of the / operator is the quotient from the division of the
first operand by the second; the result of the % operator is the
remainder. In both operations, if the value of the second operand is
zero, the behavior is undefined.
6
When integers are divided, the result of the / operator is the
algebraic quotient with any fractional part discarded.90) If the
quotient a/b is representable, the expression (a/b)*b + a%b shall equal
a.
90) This is often call "truncated toward zero".
6.5.5 乗算演算子
5
/ 演算子の結果は1つ目のオペランド(演算対象)を2つ目のオペランドで除算した商であり; %
演算子の結果は剰余である。両方の演算子は、もし2つ目のオペランドがゼロなら、動作は未
定義である。
6
整数が除算される場合、/ 演算子の結果は小数部が破棄された代数的な商になる。90) もし
商a/bが表現可能なら、式 (a/b)*b + a%b は a と等しくなくてはならない。
90) これはしばしば「ゼロに向かった切捨て」と呼ぶ。
27
除算と剰余算: C11
ISO/IEC 9899:2011 Programming languages C (C11)
Committee Draft - April 12, 2011 p.92.
6.5.5 Multipliative operators
6
When integers are divided, the result of the / operator is
the algebraic quotient with any fractional part
discarded.105) If the quotient a/b is representable, the
expression (a/b)*b + a%b shall equal a ; otherwise, the
behavior of both a/b and a%b is undefined.
105) This is often call "truncated toward zero".
6.5.5 乗算演算子
6
整数が除算される場合、/ 演算子の結果は小数部が破棄された代数的な商に
なる。105) もし商 a/b が表現可能なら、式 (a/b)*b + a%b は a と等しく
なくてはならない; そうでないなら、a/b および a%b の両方の動作は未定義
である。
105) これはしばしば「ゼロに向かった切捨て」と呼ぶ。
28
C言語の仕様書
ここに書いてあることが
C言語のすべて
書いてないことは
実装依存
OpenStandards
ISO/IEC JTC1/SC22 - Programming languages and, operating systems
WG14 - C
http://www.open-std.org/JTC1/SC22/WG14/
WG14 N1256
ISO/IEC 9899:1999 Programming languages C (C99) + TC1 + TC2 +
TC3
Committee Draft - September 7, 2007
http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf
WG14 N1570
ISO/IEC 9899:2011 Programming languages C (C11)
Committee Draft - April 12, 2011
http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1570.pdf
注: Committee Draft (委員会草案) なので最終版ではない
正式版の仕様書は有料: ISO/IEC 9899:2011
29
ユークリッドの互除法
Euclidean algorithm
• 最大公約数(GCD: Greatest Common Divisor)
を求めるアルゴリズム
Wikipedia / ユークリッドの互除法
30
ユークリッドの互除法
Euclidean algorithm
整数𝑚, 𝑛, 𝑞, 𝑟について𝑚を𝑛で割った商を𝑞余りを𝑟をとし以下のように定義する
𝑚 = 𝑞𝑛 + 𝑟 ただし 𝑟 < 𝑛 かつ 𝑞𝑛 ≤ 𝑚
• 𝑖, 𝑗, 𝑘, 𝑙を適当な整数とすれば
• 𝑑1 を𝑛, 𝑟の任意の公約数とすると、𝑛 = 𝑖𝑑1 , 𝑟 = 𝑗𝑑1と書けるから
𝑚
= 𝑞𝑛 + 𝑟
= 𝑞𝑖𝑑1 + 𝑗𝑑1
= 𝑞𝑖 + 𝑗 𝑑1
𝑑2 を𝑚, 𝑛の任意の公約数とすると、𝑚 = 𝑘𝑑2 , 𝑛 = 𝑙𝑑2 と書けるから
𝑚 = 𝑞𝑛 + 𝑟
•
•
•
•
𝑛, 𝑟の公約数と𝑚, 𝑛の公約数は等しい集合である
𝑚, 𝑛の最大公約数は等しい
31
ユークリッドの互除法
Euclidean algorithm
• ここで𝑚 ÷ 𝑛の余り𝑟は 𝑟 < 𝑛 であるから、
以下の手順を行うと𝑟 = 0に収束する
1. 𝑚 ÷ 𝑛の余り𝑟を求める
2. 𝑛, 𝑟を新たな𝑚, 𝑛とする
3. 𝑚が𝑛で割り切れるまで手順1,2を繰り返す
• つまり上記手順1.で𝑟 = 0になった時の 𝑛 が
最初に与えた𝑚, 𝑛の最大公約数である
n = 0 の時 m % n が
0 割りになるので具合が悪い
32
ユークリッドの互除法
Euclidean algorithm
• ここで𝑚 ÷ 𝑛の余り𝑟は 𝑟 < 𝑛 であるから、
以下の手順を行うと𝑟 = 0に収束する
1. 𝑛が0になるまで以下の手順2,3を繰り返す
2. 𝑚 ÷ 𝑛の余り𝑟を求める
3. 𝑛, 𝑟を新たな𝑚, 𝑛とする
• つまり上記手順1.で𝑛 = 0になった時の 𝑚 が
最初に与えた𝑚, 𝑛の最大公約数である
n = 0 の時 m % n が
0 割りにならないように工夫
33
ユークリッドの互除法
Euclidean algorithm
• 𝑚 ÷ 𝑛の余り𝑟を求める
• r = m % n;
• 𝑛, 𝑟を新たな𝑚, 𝑛とする
n = 0 の時 m % n すると
0 割りになるので具合が悪いため
厳密には前判定ループで n == 0 で
ループを辞める方が都合が良い
• m = n;
• n = r;
• 𝑚が𝑛で割り切れるまで繰り返す
• r != 0 の間ループさせる
• 無限ループで r == 0 の時 break や return させる
•
𝑛
• n < 0 ? -n : n;
• abs(n);
• n * sign(n);
34
ユークリッドの互除法
Euclidean algorithm
• 実装は色々出来る
若干まずいやり方
n = 0 だと m % n が
0 割りで不具合を生じる
gcd.c
gcd.c
for (;;) {
r = m % n;
if (r == 0) return n < 0 ? -n : n;
m = n;
n = r;
}
while (1) {
r = m % n;
if (r == 0) break;
m = n;
n = r;
};
return n < 0 ? -n : n;
gcd.c
gcd.c
gcd.c
while (r = m % n) {
m = n;
n = r;
};
return n < 0 ? -n : n;
r = 1;
while (r) {
r = m % n;
m = n;
n = r;
};
return m < 0 ? -m : m;
do {
r = m % n;
m = n;
n = r;
} while (r);
return m < 0 ? -m : m;
35
ユークリッドの互除法
Euclidean algorithm
• 実装は色々出来る
gcd.c
while (n) {
r = m % n;
m = n;
n = r;
};
return m < 0 ? -m : m;
C99未満の仕様だと
m,nが共に正でない場合
おかしな結果が出るかもしれない
点に注意
演習:
m = 0 のときはどうなるだろう？
何らかの例外処理が必要でないか
検討しなさい
36
演習: gcd.c
• 整数m,nの最大公約数を計算する関数 gcd
を作成せよ
• gcd_test.c と共にコンパイルする事で動
作を確認せよ
mintty + bash + GNU C
• 引数
• int m,n : 任意の整数
$ gcc gcd_test.c gcd.c && ./a
m = ? 48
n = ? 15
gcd(48, 15) = 3
• 戻り値
• m,n の最大公約数をint型で返す
37
参考文献
• [1] B.W.カーニハン/D.M.リッチー著石田晴久
訳、プログラミング言語C 第2版 ANSI 規格準
拠、共立出版(1989)

Download Report