解答は基本的に全文を載せ、解答はソース中の強調されている部分について説明します。小技、テクニックも少し紹介していきますので、余裕のある方はそちらもどうぞ。
#include <stdio.h> #include <stdlib.h> int *make_array(int n, int step, int *sum); int main(){ int n,step,sum,*ari_pro; do{ printf("nの値を入力してください(半角自然数):"); scanf("%d",&n); }while(n<=0); printf("stepの値を入力してください(半角整数):"); scanf("%d",&step); ari_pro = make_array(n,step,&sum); int i; for(i=0;i<n;i++) printf("%d,",ari_pro[i]); printf("\b \n"); printf("合計:%d\n",sum); free(ari_pro); return 0; } int *make_array(int n, int step, int *sum){ int *array; if(!(array = (int *)malloc(sizeof(int)*n))){ printf("error:メモリの確保に失敗しました。\n"); exit(-1); } int i; for(i=0;i<n;i++) *sum += array[i] = i*step; return array; }
#include <stdio.h> #include <stdlib.h> int *make_array(int n, int step, int *sum);
malloc関数を使うので、stdlib.hをインクルードしています。make_array関数は後で説明。
int main(){ int n,step,sum,*ari_pro; do{ printf("nの値を入力してください(半角自然数):"); scanf("%d",&n); }while(n<=0); printf("stepの値を入力してください(半角整数):"); scanf("%d",&step);
メイン関数の最初の部分。sumは配列の合計を保持する変数。ari_proは配列の先頭のアドレスを格納するポインタです。ポインタと変数は、このように一度に宣言することもできます。
do〜whileでは、nの値を入力させています。nは0より大くなければいけないので、nが0以下である限り何度も入力させています。
ari_pro = make_array(n,step,&sum);
make_arrayは作った配列の先頭のポインタを返す関数ですので、それをari_proに格納しています。これで、ポインタ変数ari_proを使って、配列にアクセスできます。(参考:ポインタを使ったアクセス)
引数のうち、sumはポインタを渡していますが、これはsumをmake_array中で変更したいからです。(参考:関数間での値の共有)
int i; for(i=0;i<n;i++) printf("%d,",ari_pro[i]); printf("\b \n"); printf("合計:%d\n",sum); free(ari_pro); return 0; }
結果を表示しています。ari_proを配列として扱っています。free関数は今回はそれほど意味はありませんが、一応書いておきました。
int *make_array(int n, int step, int *sum){ int *array; if(!(array = (int *)malloc(sizeof(int)*n))){ printf("error:メモリの確保に失敗しました。\n"); exit(-1); }
arrayはint型のポインタを返す変数で、整数配列の先頭アドレスを格納します。引数は配列生成のためのn,stepと、配列の要素の合計を保持する変数へのポインタsumです。(参考:関数間での値の共有)
arrayには配列の先頭ポインタを格納します。if文の条件判定文の中で代入しているのですが、少しわかりにくいですね。ここは、
array = (int *)malloc(sizeof(int)*n; if(!array){
としても同じです。解答例では、「代入文は、実行後その左辺と同じ値になる」という性質を利用しています。つまり、「array=〜」という代入文自体が、arrayと同じ値になるのです。今出した例の2行目の「array」を1行目で置き換えると、解答例の状態になりますね。
従ってif文では、「int型n個分の連続領域を確保し、それができなければエラー終了する」という処理をしています。
int i; for(i=0;i<n;i++) *sum += array[i] = i*step; return array; }
こちらは、「代入文は、右から順に評価(計算)される」という性質を利用しています。代入文を分けて丁寧に書くと、
array[i] = i*step; *sum = *sum + array[i];
となります。
最後に、配列の先頭ポインタを返してこの関数は終わりです。
意外と、簡単だったのではないでしょうか?変数と関数、変数とポインタ、ポインタと配列の関係がしっかりわかっていた人は、特に簡単に書けたかと思います。あとは、構造体との関係を理解すれば、ポインタを使って一通りの基本的なプログラムが書けるようになります。
void walk(struct btree *node){ if(node->left) walk(node->left); printf("%d,",node->data); if(node->right) walk(node->right); }
以下は「上のwalk関数はnodeを根とする木の要素を昇順に表示する」の証明である。
nodeが子を持たないとき、明らかに成立する。
あるノードnode1,node2に関して上が成り立つとき、それらをそれぞれ左、右の子に持つノードについて考えてみると、
if(node->left) walk(node->left);
では、walk(node1)が実行され、仮定よりノードの値が昇順で表示される。
printf("%d,",node->data);
ここで表示される値は、二分探索木の定義より、先ほど表示されたどの要素よりも大きいものである。
if(node->right) walk(node->right);
ここではwalk(node2)が実行され、仮定と二分探索木の定義から、親ノードより(同じか)大きな値が昇順で表示される。
以上より、親ノードについてもwalk関数の正しさは保証され、数学的帰納法よりどのような二分探索木についても成り立つことがわかる。(証明終了)
席に戻ってやり直し。