C
プログラミング
第 8 回
構造体と再帰
基幹理工学部
本日の授業内容
構造体
▶前期の復習
⋆ 宣言，初期化，メンバ， ▶再考
⋆ 構造体へのポインタ ⋆ アロー演算子 ⋆ 構造体を返す関数再帰とは
再帰による計算
▶階乗
n!
▶フィボナッチ数列
a
n+2= a
n+1+ a
n再帰の除去
構造体変数の宣言
#include <stdio.h>
struct student
{
char name[20]
;
int
math
;
int
phys
;
};
int main(void){
struct student
a, b;
struct student c={"Frank", 90};
構造体
とは１つ以上の要素を集めて作
られるデータ構造．異なる型の要素を
自由に組み合わせられる．
構造体タグ
は宣言した構造体の型を代
表する識別子である．
メンバ
が構造体を構成する変数．
初期化は配列と同様．各メンバに対す
る初期値を，先頭から順に並べる．
与えられていない要素は０で初期化さ
れる．
メンバの参照
構造体の各メンバを参照するには，
構造体メンバ演算子（
.
）
を利用する．
#include <stdio.h>
#include <string.h> /*strcpy 関数を使うのに必要*/ struct student{ char name[20]; int math; int phys; }; int main(void){ struct student a, b; strcpy(a.name,"Frank"); a.math = 90;
a.phys = 83; …
構造体型変数の代入
代入演算子（
=
）を用いて，構造体全体を一括してコピーできる．
ただし，両辺の構造体の型は同一でなければいけない．
配列では一括代入ができない（復習）
#include <stdio.h> #include <string.h> /*strcpy 関数を使うのに必要*/ structstudent{ char name[20]; int math; int phys; }; int main(void){ structstudent a,b; strcpy(a.name, "Frank"); a.math = 90;a.phys = 83;
printf(" Name:%sY=n",a.name); printf(" Math:%dY=n",a.math); printf(" Physics:%dY=n",a.phys);
b=a;
printf(" Name:%sY=n",b.name); printf(" Math:%dY=n",b.math); printf(" Physics:%dY=n",b.phys); return 0; } 【実行結果】 Name:Frank Math:90 Physics:83 Name:Frank Math:90 Physics:83
構造体へのポインタ
構造体変数を宣言する際，ポインタとして宣言することもできる．
構造体を指すポインタは構造体の先頭のメンバのアドレスをもつ．
構造体型変数のアドレスは，
アドレス演算子
(&)
を用いる．
struct student
{
char name[20];
int
math;
int
phys;
};
int main(void){
struct student
a,
*pa
;
pa = &a;
…
と宣言した場合右のようにメモリが確保される．
ポインタ
メモリ内容
pa
a.name
a.math
a.phys
構造体へのポインタ
構造体変数を宣言する際，ポインタとして宣言することもできる．
構造体を指すポインタは構造体の先頭のメンバのアドレスをもつ．
構造体型変数のアドレスは，
アドレス演算子
(&)
を用いる．
struct student
{
char name[20];
int
math;
int
phys;
};
int main(void){
struct student
a,
*pa
;
pa = &a;
…
と宣言した場合右のようにメモリが確保される．
ポインタ
メモリ内容
pa
a.name
a.math
a.phys
構造体へのポインタ
ポインタの指す構造体のメンバを参照する際は，
アロー演算子
(-
>)
を利用して，
ポ
インタ名
-
>
メンバ名
とする．
これは
(*
ポインタ名
).
メンバ名
と同じ意味だが一般には上を使う．
#include <stdio.h> #include <string.h> structstudent{ char name[20]; int math; int phys; }; int main(void){structstudent a,*pa; strcpy(a.name, "Frank"); a.math = 90;
a.phys = 83;
printf(" Name:%sY=n",a.name); printf(" Math:%dY=n",a.math); printf(" Physics:%dY=n",a.phys);
pa=&a;
strcpy(pa->name, "Thomas"); pa->phys = 92;
printf(" Name:%sY=n",pa->name); printf(" Math:%dY=n",pa->math); printf(" Physics:%dY=n",pa->phys); return 0; } 【実行結果】 Name:Frank Math:90 Physics:83 Name:Thomas Math:90 Physics:92
構造体へのポインタ
ポインタの指す構造体のメンバを参照する際は，
アロー演算子
(-
>)
を利用して，
ポ
インタ名
-
>
メンバ名
とする．
これは
(*
ポインタ名
).
メンバ名
と同じ意味だが一般には上を使う．
#include <stdio.h> #include <string.h> structstudent{ char name[20]; int math; int phys; }; int main(void){structstudent a,*pa; strcpy(a.name, "Frank"); a.math = 90;
a.phys = 83;
printf(" Name:%sY=n",a.name); printf(" Math:%dY=n",a.math); printf(" Physics:%dY=n",a.phys);
pa=&a;
strcpy(pa->name, "Thomas"); pa->phys = 92;
printf(" Name:%sY=n",pa->name); printf(" Math:%dY=n",pa->math); printf(" Physics:%dY=n",pa->phys); return 0; } 【実行結果】 Name:Frank Math:90 Physics:83 Name:Thomas Math:90 Physics:92
演習
.
...
下のプログラムを実行した場合の出力はどのようになるか考えよ．
#include <stdio.h> #include <string.h> structstudent{ char name[20]; int math; int phys; }; int main(void){structstudent a,*pa; strcpy(a.name, "Frank"); a.math = 90;
a.phys = 83;
printf(" Name:%sY=n",a.name); printf(" Math:%dY=n",a.math); printf(" Physics:%dY=n",a.phys); pa=&a;
strcpy(pa->name, "Thomas"); pa->phys = 92;
printf(" Name:%sY=n",pa->name); printf(" Math:%dY=n",pa->math); printf(" Physics:%dY=n",pa->phys); printf(" Name:%sY=n",a.name); printf(" Math:%dY=n",a.math); printf(" Physics:%dY=n",a.phys); return 0; } 【実行結果】 Name:Frank Math:90 Physics:83 Name:Thomas Math:90 Physics:92 Name:Thomas Math:90 Physics:92
演習
.
...
下のプログラムを実行した場合の出力はどのようになるか考えよ．
#include <stdio.h> #include <string.h> structstudent{ char name[20]; int math; int phys; }; int main(void){structstudent a,*pa; strcpy(a.name, "Frank"); a.math = 90;
a.phys = 83;
printf(" Name:%sY=n",a.name); printf(" Math:%dY=n",a.math); printf(" Physics:%dY=n",a.phys); pa=&a;
strcpy(pa->name, "Thomas"); pa->phys = 92;
printf(" Name:%sY=n",pa->name); printf(" Math:%dY=n",pa->math); printf(" Physics:%dY=n",pa->phys); printf(" Name:%sY=n",a.name); printf(" Math:%dY=n",a.math); printf(" Physics:%dY=n",a.phys); return 0; } 【実行結果】 Name:Frank Math:90 Physics:83 Name:Thomas Math:90 Physics:92 Name:Thomas Math:90 Physics:92
構造体を使ったプログラム
構造体を使ったサンプルプログラム
#include <stdio.h> struct student{ /*構造体の宣言*/ char name[20]; int math; int phys; double ave; };void Average(struct student*std){
/*平均値を計算する関数*/ int sum;
sum = std->math + std->phys; std->ave =(double)sum/2; }
int main(void){
struct student S1 = {"Frank",90,83}; Average(&S1);
printf("Name =%sY=n",S1.name); printf("Math =%dY=n",S1.math); printf("Phys =%dY=n",S1.phys); printf("Ave =%.2fY=n",S1.ave); return 0; } 【実行結果】 Name =Frank Math =90 Phys =83 Ave =86.50
構造体を返す関数
代入が可能な構造体は，関数の戻り値として使うこともできる．
前頁のプログラムを構造体を返す関数として関数
Average
に関係する箇所を書き換
えれば次のようになる．
struct studentAverage(struct student temp){ temp.ave = (double) (temp.math + temp.phys)/2;
returntemp; } int main(void){ … S1=Average(S1); …
構造体型配列
構造体全体を１つの要素とする配列を宣言することができる．
struct
構造体 配列名
[
要素数
];
今まで学習した配列や構造体と同様に扱うことができる．
struct student
Std[20]
;
…
for(i=0;i<N;i++){
Std[i]
.ave = (double)(
Std[i]
.math+
Std[i]
.phys)/2;
}
演習
.
ファイル名：081.c
..
...
20
人分のデータ（番号，数学・物理の各点数，２教科の平均点）を以下の数式に従って入
力し，20
人の数学・物理・２教科の平均点の平均を求めるプログラムを作成せよ．
学籍番号は
100
から
119
とする．
学籍番号
N
に対して数学の点数は （N*29
+83)%100,
物理の点数は
(N*13
+58)%100
とする．
表記は，20
人分のデータと平均を表示するようにせよ．
データを入力するときは次のような関数を作って行うこと．
void InputData(struct student *X)
/*
student
は構造体タグ
*/
表記は以下のようにせよ．
100|
83 |
58 |
70.5
101|
12 |
71 |
41.5
...
118|
5 |
92 |
48.5
119|
34 |
5 |
19.5
| 48.5| 51.5|
50.0
構造体へのポインタ（再考）
第
3
回講義で学習したことが構造体型配列についても同様に行うことができる．
例えば，
struct student Std[20];
と構造体型変数の宣言を行った場合，
Std
は構造体型配列の先頭の要素を指すポイ
ンタになる．
【配列表現】
struct student Std[N]; int i; for(i=0;i<N;i++){ Std[i].No = 100+i; InputDATA(&Std[i]); Std[i].ave = (Std[i].math+Std[i].phys)/2.0; }【ポインタ表現】
struct student Std[N], *p_Std; int i; p_Std = Std; for(i=0;i<N;i++){ p_Std->No = 100+i; InputDATA(p_Std); p_Std->ave = (p_Std->math+p_Std->phys)/2.0; p_Std ++; }構造体へのポインタ（再考）
第
3
回講義で学習したことが構造体型配列についても同様に行うことができる．
例えば，
struct student Std[20];
と構造体型変数の宣言を行った場合，
Std
は構造体型配列の先頭の要素を指すポイ
ンタになる．
【配列表現】
struct student Std[N]; int i; for(i=0;i<N;i++){ Std[i].No = 100+i; InputDATA(&Std[i]); Std[i].ave = (Std[i].math+Std[i].phys)/2.0; }【ポインタ表現】
struct student Std[N], *p_Std; int i; p_Std = Std; for(i=0;i<N;i++){ p_Std->No = 100+i; InputDATA(p_Std); p_Std->ave = (p_Std->math+p_Std->phys)/2.0; p_Std ++; }構造体へのポインタ（再考）
前頁のポインタによる表現を以下のように変えることもできる．
【ポインタ表現】
struct student Std[N], *p_Std; int i; p_Std = Std; for(i=0;i<N;i++){ p_Std->No = 100+i; InputDATA(p_Std); p_Std->ave = (p_Std->math+p_Std->phys)/2.0; p_Std ++; }【ポインタ表現２】
struct student Std[N], *p_Std; int i; p_Std = Std; for(i=0;i<N;i++){ (p_Std+i)->No = 100+i; InputDATA(p_Std+i); (p_Std+i)->ave = ((p_Std+i)->math+(p_Std+i)->phys)/2.0; }再帰関数呼び出し
.
再帰関数呼び出しとは…
..
...
何らかの計算・操作を行いたいとき，それを実現するのがたまたま自分自身と同じ
関数であれば，その関数を呼び出すことができる．このような関数の呼び出しを
再
帰関数呼び出し
という．
関数の呼び出しがどこかで止まり、大元の呼び出しに戻ってこられるように作らな
くてはならない．
.
再帰関数呼び出しの長所と短所
..
...
【長所】再帰を使うと、プログラムを簡潔に書くことができます．
【短所】考えるのが難しい．
【短所】実行速度が遅くなり，メモリの消費量も増える．
再帰による計算（例）
階乗の計算
1!
= 1
2!
= 1! × 2
3!
= 2! × 3 = (1! × 2) × 3
一般には，
n!
= (n − 1)! × n
= (n − 2)! × (n − 1) × n
= · · ·
#include <stdio.h> int factorial( int n ){int m; if( n==0 || n==1 ){ printf("1"); return 1; }else{ printf("%d *(",n); m = n * factorial( n-1 ); printf(")"); return m; } } int main(void){ N= 5; factorial(N); return 0; }
再帰による計算（例
2
）
フィボナッチ数列
f (0)
= 0
f (1)
= 1
f (2)
= f (1) + f (0) = 1
f (3)
= f (2) + f (1) = 2
f (n)
= f (n − 1) + f (n − 2)
int fibonacci( int n ){
if( n==0 ){
return 0;
} else if( n == 1){
return 1;
} else {
return
fibonacci
(n-1)+
fibonacci
(n-2);
}
再帰の必要性
階乗の計算やフィボナッチ数列は，再帰を使わなくても計算することができる．
あらかじめ決められた手順を繰り返すのであれば，繰り返し（ループ）構文で表現
することができる．
再帰のプログラムをループで書き直すことを
再帰除去
するという．
再帰除去されたプログラムは，再帰という関数呼び出しがなくなるので，一般的に
効率が良くなる．
再帰除去の例
【再帰を使った例】
int factorial( int n ){
int m;
if( n==0 || n==1 ){
printf("1");
return 1;
}else{
printf("%d *(",n);
m = n *
factorial( n-1 )
;
printf(")");
return m;
}
}
【再帰除去した例】
int factorial( int n ){
int i, m=1;
printf("1");
for( i=2; i<=n; i++){
printf("*%d",i );
m = m *i;
}
return m;
}
再帰除去の例２
再帰を使った例
int fibonacci( int n ){ if( n==0 ){
return 0; } else if( n == 1){
return 1; } else {
return fibonacci(n-1)+fibonacci(n-2); }
}
再帰除去した例
int fibonacci( int n ){ int i, fn, fn1=1, fn2=0; if( n==0 ){ return 0; } else if( n == 1){ return 1; } else {
for( i=2; i<=n;i++){
fn=fn1+fn2; fn2=fn1; fn1=fn; }
return fn; }
