プログラミング演習II 2003年10月29日（第2,3回） 木村巌

今日やること 配列の復習 ポインタの復習 多倍長整数の配列での実現 足し算と繰り上がり malloc()とfree() キャスト（明示的な型変換）

配列 それぞれの型Tについて、T型の配列が存在する（void型、「…を返す関数」型を除く）: T var[16]; 例：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]まで．

配列の要素はすべて同じ型 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のポインタ型」が定義できる 例：integer型のポインタ型変数a……int *a 例：char型のポインタ型変数s…char *s テキスト9章

ポインタって何? 型Tのポインタ型の値は、型Tのモノ（object）のアドレス（メモリ上の場所）

ポインタの作り方 型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 *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の場合、 a = 23 + 34*100 + 45*100^2, b = 11 + 22*100 + 33*100^2について、a+bを手で計算せよ． 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日（火）一杯に、木村までメールで送ること．アドレスはiwao@sci.toyama-u.ac.jp 添付ファイルではなく、できるだけメール本文にレポート本文を記載してください． 参考にした文献や友人のレポートは、その旨明記すること．