プログラミング演習I

プログラミング演習II
2003年10月29日（第2,3回）
木村巌
今日やること
配列の復習
ポインタの復習
多倍長整数の配列での実現
足し算と繰り上がり
malloc()とfree()
キャスト（明示的な型変換）
配列
それぞれの型Tについて、T型の配列が存在
する（void型、「…を返す関数」型を除く）:
T var[16];
のように宣言する．Tは、整数、浮動小数点数、
文字、などが主な例．
例：int ary[16];
int型の配列．ary[0]からary[15]までの16個
のint型の値を保持できる
テキスト７章1節
配列の正体
T型の値を、指定された個数だけ保持でき
るメモリの先頭のアドレス（T型のポインタ）．
例：
int ary[16];
sizeof (ary); /* == sizeof (int) * 16 ==
64byte */
配列は0から始まる
配列は、0から始まる添え字を持つ
int ary[16]なら、ary[0]からary[15]まで．
ary[16]を読み書きしても（読み書きできて
しまう！）、結果は予測できない！！
配列の要素はすべて同じ型
int ary[16];
と宣言すると、ary[0]からary[15]はすべて
int型．
配列の初期化
int ary[3] = {1, 2, 3};
int ary[] = {1, 2, 3};
どちらも同じ意味．
後者のほうが間違いがない（コンパイラが
要素の数を数えてくれる）．
レポート課題１（フィボナッチ数）
フィボナッチ数f(n)は、次の漸化式で定義さ
れる：
f(0) = 1, f(1) = 1,
f(n) = f(n-1) + f(n-2), n >= 2.
f(n)を求めるプログラムをＣで書け．各項は
longで表すこと
何項目まで正しく求められるか？
多倍長整数の配列での実現
暫定的に、以下のようにする：
配列の長さを固定：DIMとする
基数を固定：BASEとする
longの配列、次元はDIM
とりあえず非負整数のみ
添え字の小さい方が小さい方の桁
多倍長整数の配列での実現（２）
つまり、
#define BASE 10
#define DIM 3
long a[DIM] = {1, 0, 0}; /* DIM = 3 */
なら、a = 1 + 0*101 + 0 * 102 = 1.
DIM桁のBASE進表記
繰り上がり
a = a_0 + a_1*10^1 + a_2 * 10^2,
b = b_0 + b_1*10^1 + b_2 * 10^2,
のとき、c=a+bをどのように計算するか考え
る
各c_i=a_i+b_iをi桁目にするのではない
BASEより大きくなったときに、次の桁へ繰
り上げる
プログラム例
（mpinteger-wo-malloc.c）
以上のようなアイディアで、フィボナッチ数
の計算を行うプログラムを作る．
ポインタ型
Cの型の一つ
任意の型Tに対して、「Tのポインタ型」が
定義できる
従って、「Tのポインタのポインタ」型等々も定
義できる
例：integer型のポインタ型変数a……int *a
例：char型のポインタ型変数s…char *s
テキスト9章
ポインタって何?
型Tのポインタ型の値は、型Tのモノ
（object）のアドレス（メモリ上の場所）
型Tのポインタ型の変数は、型Tのモノのア
ドレスを保持するのに必要なだけのメモリ
を占める
ポインタの作り方
型Tのモノから、それを指すポインタ値をつ
くるには、アドレス演算子&を使う
例：int a = 1; int *aptr; aptr = &a;
型Tのポインタ値から、それが指している
型Tのモノを見るには、間接演算子*を使う
例：int *bptr; int b;
b = *aptr; /* aと同じ値 */
ポインタって何？（続）
int a = 1; /* int が保存できるメモリを確保し、1を保存*/
int *aptr = &a; /* そのメモリの番地 */
1
aptr
メモリの模式図
ポインタに対して出来ること
T *p; /* pがT型のポインタ */
ポインタの間接参照（そのポインタが指す
モノを取り出す）： *T /* T型のモノ */
ポインタの算術：T ary[8]; T *p = &ary[0];
ならば、p + i と ary[i] とは同じメモリを指
す
なぜポインタがいるのか?
一つの理由は、C言語での関数引数が、
値渡しだから
例
int a = 1; f(a);
とすると、f()に渡されるのは、aの値のコ
ピー．変数aそのものが渡されるのではな
い
プログラム例：swap.cを参照
scanf()系の関数で、読み込んだ結果を保
存する変数に&演算子をつけるのも同じ理
由
ポインタと配列との関係（テキスト１
０章）
式の中に現れる配列は、「Tの配列」から「Tへ
のポインタ」に変換される(ary_ptr.c参照)
このときのポインタは、配列の0番目の成分を
指すポインタ
int a[8], *aptr; aptr = a;
と、
int a[8], *aptr; aptr = &a[0];
とはまったく同じ
例外：配列がsizeof演算子の引数のとき
sizeof (a) = sizeof (int) * 8 /* 上の宣言の元で*/
メモリの確保：静的な確保
これまでは、プログラムの字面に、メモリの
確保が指示されていた：
たとえば、long a[10]; は、sizeof(long) * 10
byteのメモリを確保し、その先頭アドレスをaと
いう名前で識別する
プログラムの実行が始まる前、コンパイル
時にすべてのメモリが確保されている
メモリの動的確保：malloc()
プログラムの実行が始まってから、指定さ
れた大きさのメモリを確保するライブラリ関
数：void *malloc(size_t).
malloc (16); で16byteのメモリを確保し、その
先頭アドレスを返す.
返されるアドレスは、void型のポインタ
Void型のポインタは、任意の型に変換可能な
「総称型」（generic type）
型の明示的変換（キャスト）
Cの型システムでは、一定の規則の下で、
型の変換が行える．
当然行えるべき変換…intからlong, floatか
らdouble, intからfloat, longからdoubleな
ど：int a; long aa; aa = (long) a;
逆もある．（精度の切り捨て）
malloc()は何を返すべき？
総称型：void *
malloc()で確保したメモリは、何に使われ
るか限定できない
何にでも使える型：void *
実際には、void *をほかの型に変換（キャ
スト）して使う
例
void *tmp; tmp = malloc (16);
long *a; a = (long *)tmp;
malloc()の使い方
場合によっては、メモリの確保に失敗する．
その場合、返値がNULL．
void *tmp;
long *a;
tmp = malloc (sizeof (long) * 4);
if (tmp == NULL) /* エラー処理 */
else a = (long *)tmp;
のように使う．使い終わったら、
free(a); /* 解放する */
変数のエクステント
変数の有効期間
関数内で宣言された変数は、その関数内
に制御がある間のみ有効だった（プログラ
ミング演習Ｉの6/15の回の資料参照）
関数内で確保したメモリは、明示的に解放
されるまで有効．
malloc()を使った多倍長計算
プログラム例参照．
レポート課題2
BASE100, DIM 3の場合、
1. a = 23 + 34*100 + 45*100^2, b = 11 +
22*100 + 33*100^2について、a+bを手で計算
せよ．
2. a = 23 + 34*100 + 45*100^2, b = 88 +
77*100 + 44*100^2について、a+bを手で計算
せよ．
レポート課題3
プログラム例mpinteger.cで、BASEを１００
とし、mpinteger-wo-malloc.cのように、引
数として何番目のフィボナッチ数まで計算
するかを指定できるように改造したものを
作成せよ．
レポート課題提出要領
2003年11月4日（火）一杯に、木村まで
メールで送ること．アドレスは
[email protected]
添付ファイルではなく、できるだけメール本
文にレポート本文を記載してください．
参考にした文献や友人のレポートは、その
旨明記すること．

Download Report