mallocを使った課題
授業での malloc , free を使ったプログラミングを踏まえ、以下のレポートを作成せよ。
以下のデータのどれか1つについて、データを入力し、何らかの処理を行うこと。
課題は、原則として、(自分の出席番号%3)+1 についてチャレンジすること。
- 名前と電話番号
- 名前と年齢(もしくは生年月日)
- 名前と身長・体重
このプログラムを作成するにあたり、以下のことを考慮しmallocを適切に使うこと。
- 名前は、長い名前の人が混ざっているかもしれない。
- 保存するデータ件数は、10件かもしれない1000件かもしれない。(データ件数は、処理の最初に入力すること。)
ただし、mallocの理解に自信がない場合は、名前もしくはデータ件数のどちらか一方は固定値でも良い。
レポートには、(a)プログラムリスト, (b)プログラムの説明, (c)正しく動いたことがわかる実行例, (d)考察 を記載すること。
考察には、自分のプログラムが正しく動かない事例はどういう状況でなぜ動かないのか…などを検討したり、プログラムで良くなった点はどういう所かを説明すること。
malloc()とfree()
malloc()とfree()
malloc() は、動的(ヒープ領域)にメモリを確保する命令で、データを保存したい時に malloc() を実行し、不要になった時に free() を実行する。
malloc() では、alloca() と同じように、格納したいデータの byte 数を指定する。また、malloc() は、確保したメモリ領域の先頭を返すが、ヒープメモリが残っていない場合 NULL ポインタを返す。処理が終わってデータ領域をもう使わなくなったら、free() で解放する必要がある。
基本的には、確保したメモリ領域を使い終わった後 free() を実行しないと、再利用できないメモリ領域が残ってしまう。こういう処理を繰り返すと、次第にメモリを食いつぶし、仮想メモリ機能によりハードディスクの読み書きで性能が低下したり、最終的にOSが正しく動けなくなる可能性もある。こういった free() 忘れはメモリーリークと呼ばれ、malloc(),free()に慣れない初心者プログラマーによく見られる。
ヒープメモリは、プロセスの起動と共に確保され、プログラムの終了と同時にOSに返却される。このため、malloc()と処理のあとすぐにプロセスが終了するようなプログラムであれば、free() を忘れても問題はない。授業では、メモリーリークによる重大な問題を理解してもらうため、原則 free() は明記する。
文字列を保存する場合
#include <stdlib.h> char* names[ 10 ] ; char buff[ 1000 ] ; // 名前を10件読み込む void inputs() { for( int i = 0 ; i < 10 ; i++ ) { if ( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { names[ i ] = (char*)malloc( strlen(buff)+1 ) ; if ( names[ i ] != NULL ) strcpy( names[ i ] , buff ) ; } } } // 名前を出力する void prints() { for( int i = 0 ; i < 10 ; i++ ) printf( "%s" , names[ i ] ) ; } void main() { // 文字列の入力&出力 inputs() ; prints() ; // 使い終わったら、free() で解放 for( int i = 0 ; i < 10 ; i++ ) free( names[ i ] ) ; }
文字列を保存する場合には、上記の names[i] への代入のような malloc() と strcpy() を使うことが多い。
このための専用の関数として、strdup() がある。基本的には、以下のような機能である。char* strdup( char* s ) { char* p ; if ( (p = (char*)malloc( strlen(s)+1 )) != NULL ) strcpy( p , s ) ; return p ; }また、入力した文字列をポインタで保存する場合、以下のようなプログラムを書いてしまいがちであるが、図に示すような状態になることから、別領域にコピーする必要がある。
char buff[ 1000 ] ; char* name[10] ; for( int i = 0 ; i < 10 ; i++ ) { if ( fgets( buff , sizeof(buff) , stdin ) != NULL ) name = buff ; }
配列に保存する場合
任意サイズの配列を作りたい場合には、malloc() で一括してデータの領域を作成し、その先頭アドレスを用いて配列として扱う。
#include <stdlib.h> void main() { int size ; int* array ; // 処理するデータ件数を入力 scanf( "%d" , &size ) ; // 整数配列を作る if ( (array = (int*)malloc( sizeof(int) * size )) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) array[i] = i*i ; // あんまり意味がないけど for( i = 0 ; i < size ; i++ ) printf( "%d¥n" , array[i] ) ; // mallocしたら必ずfree free( array ) ; } }
構造体の配列
同じように、任意サイズの構造体の配列を作りたいのであれば、配列サイズに「sizeof( struct Complex ) * データ件数」を指定すればいい。
#include <stdlib.h> struct Complex { double re , im ; } ; // 指定した場所にComplexを読み込む。 int input_Complex( struct Complex* p ) { return scanf( "%f %f" , &(p->re) , &(p->re) ) == 2 ; } // 指定したComplexを出力 void print_Complex( struct Complex* p ) { printf( "%f+j%f¥n" , p->re , p->im ) ; } void main() { int size ; struct Complex* array ; // 処理する件数を入力 scanf( "%d" , &size ) ; // 配列を確保して、データの入力&出力 if ( (array = (struct Complex*)malloc( sizeof(struct Complex) * size )) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) if ( !input_Complex( &array[i] ) ) break ; for( i = 0 ; i < size ; i++ ) print_Complex( &array[i] ) ; // mallocしたら必ずfree free( array ) ; } }
派生と継承
前回の派生と継承のイメージを改めて記載する。
// 基底クラス class Person { private: char name[ 20 ] ; int age ; public: Person( const char s[] , int x ) : age( x ) { strcpy( name , s ) ; } void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス(Student は Person から派生) class Student : public Person { private: char dep[ 20 ] ; int grade ; public: Student( const char s[] , int x , const char d[] , int g ) : Person( s , x ) // 基底クラスのコンストラクタ { // 追加された処理 strcpy( dep , d ) ; grade = g ; } void print() { Person::print() ; // 基底クラスPersonで名前と年齢を表示 printf( "- %s %d\n" , dep , grade ) ; } } ; void main() { Person saitoh( "t-saitoh" , 55 ) ; Student yama( "yamada" , 21 , "ES" , 1 ) ; Student nomu( "nomura" , 22 , "PS" , 2 ) ; saitoh.print() ; // 表示 t-saitoh 55 yama.print() ; // 表示 yamada 21 // - ES 1 nomu.print() ; // 表示 nomura 22 } // - PS 2
このような処理でのデータ構造は、次のようなイメージで表される。
派生クラスでの問題提起
基底クラスのオブジェクトと、派生クラスのオブジェクトを混在してプログラムを記述したらどうなるであろうか?
上記の例では、Person オブジェクトと、Student オブジェクトがあったが、それをひとまとめで扱いたいこともある。
以下の処理では、Person型の saitoh と、Student 型の yama, nomu を、一つの table[] にまとめている。
void main() { Person saitoh( "t-saitoh" , 55 ) ; Student yama( "yamada" , 21 , "ES" , 1 ) ; Student nomu( "nomura" , 22 , "PS" , 2 ) ; Person* table[3] = { &saitoh , &yama , &nomu , } ; for( int i = 0 ; i < 3 ; i++ ) { table[ i ]->print() ; } }
C++では、Personへのポインタの配列に代入する時、Student型ポインタは、その基底クラスへのポインタとしても扱える。ただし、このように記述すると、table[] には、Person クラスのデータして扱われる。
このため、このプログラムを動かすと、以下のように、名前と年齢だけが3人分表示される。
t-saitoh 55 yamada 21 nomura 22
派生した型に応じた処理
上記のプログラムでは、 Person* table[] に、Person*型,Student*型を混在して保存をした。しかし、Person*として呼び出されると、yama のデータを表示しても、所属・学年は表示されない。上記のプログラムで、所属と名前を表示することはできないのだろうか?
// 混在したPersonを表示 for( int i = 0 ; i < 3 ; i++ ) table[i]->print() ; // Student は、所属と名前を表示して欲しい t-saitoh 55 yamada 21 - ES 1 nomura 22 - PS 2
上記のプログラムでは、Person型では、後でStudent型と区別ができないと困るので、Person型に、Person型(=0)なのか、Student型(=1)なのか区別するための type という要素を追加し、type=1ならば、Student型として扱うようにしてみた。
// 基底クラス class Person { private: int type ; // 型識別情報 char name[ 20 ] ; int age ; public: Person( int tp , const char s[] , int x ) : type( tp ) , age( x ) { strcpy( name , s ) ; } int type_person() { return type ; } void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス(Student は Person から派生) class Student : public Person { private: char dep[ 20 ] ; int grade ; public: Student( int tp , const char s[] , int x , const char d[] , int g ) : Person( tp , s , x ) // 基底クラスのコンストラクタ { // 追加された処理 strcpy( dep , d ) ; grade = g ; } void print() { Person::print() ; // 基底クラスPersonで名前と年齢を表示 printf( "- %s %d\n" , dep , grade ) ; } } ; void main() { // type=0 は Person 型、type=1は Student 型 Person saitoh( 0 , "t-saitoh" , 55 ) ; Student yama( 1 , "yamada" , 21 , "ES" , 1 ) ; Student nomu( 1 , "nomura" , 22 , "PS" , 2 ) ; Person* table[3] = { &saitoh , &yama , &nomu , } ; for( int i = 0 ; i < 3 ; i++ ) { switch( table[i]->type_person() ) { case 0 : table[i]->print() ; break ; case 1 : // 強制的にStudent*型として print() を呼び出す。 // 最近のC++なら、(static_cast<Student*>(table[i]))->>print() ; ((Student*)table[i])->print() ; break ; } } }
しかし、このプログラムでは、プログラマーがこのデータは、Personなので type=0 で初期化とか、Studentなので type=1 で初期化といったことを記述する必要がある。また、型情報(type)に応じて、その型にふさわしい処理を呼び出すための switch 文が必要になる。
もし、派生したクラスの種類がいくつもあるのなら、型情報の代入は注意深く書かないとバグの元になるし、型に応じた分岐は巨大なものになるだろう。実際、オブジェクト指向プログラミングが普及する前の初期の GUI プログラミングでは、巨大な switch 文が問題となっていた。
仮想関数
上記の、型情報の埋め込みと巨大なswitch文の問題の解決策として、C++では仮想関数(Virtual Function)が使える。
型に応じて異なる処理をしたい関数があったら、その関数の前に virtual と書くだけで良い。このような関数を、仮想関数と呼ぶ。
// 基底クラス class Person { private: char name[ 20 ] ; int age ; public: Person( const char s[] , int x ) : age( x ) { strcpy( name , s ) ; } virtual void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス(Student は Person から派生) class Student : public Person { private: char dep[ 20 ] ; int grade ; public: Student( const char s[] , int x , const char d[] , int g ) : Person( s , x ) // 基底クラスのコンストラクタ { // 追加された処理 strcpy( dep , d ) ; grade = g ; } virtual void print() { Person::print() ; // 基底クラスPersonで名前と年齢を表示 printf( "- %s %d\n" , dep , grade ) ; } } ; void main() { // type=0 は Person 型、type=1は Student 型 Person saitoh( "t-saitoh" , 55 ) ; Student yama( "yamada" , 21 , "ES" , 1 ) ; Student nomu( "nomura" , 22 , "PS" , 2 ) ; Person* table[3] = { &saitoh , &yama , &nomu , } ; for( int i = 0 ; i < 3 ; i++ ) { table[i]->print() ; } }
クラスの中に仮想関数が使われると、C++ では、プログラム上で見えないが、何らかの型情報をオブジェクトの中に保存してくれる。
また、仮想関数が呼び出されると、その型情報を元に、ふさわしい関数を自動的に呼び出してくれる。このため、プログラムも table[i]->print() といった極めて簡単に記述できるようになる。
関数ポインタ
仮想関数の仕組みを実現するためには、関数ポインタが使われる。
以下の例では、返り値=int,引数(int,int)の関数( int(*)(int,int) )へのポインタfpに、最初はaddが代入され、(*fp)(3,4) により、7が求まる。
int add( int a , int b ) { return a + b ; } int mul( int a , int b ) { return a * b ; } void main() { int (*fp)( int , int ) ; fp = add ; printf( "%d\n" , (*fp)( 3 , 4 ) ) ; // 3+4=7 fp = mul ; printf( "%d\n" , (*fp)( 3 , 4 ) ) ; // 3*4=12 int (*ftable[2])( int , int ) = { add , mul , } ; for( int i = 0 ; i < 2 ; i++ ) printf( "%d\n" , (*ftable[i])( 3 , 4 ) ) ; }仮想関数を使うクラスが宣言されると、一般的にそのコンストラクタでは、各クラス毎の仮想関数へのポインタのテーブルが型情報として保存されるのが一般的。仮想関数の呼び出しでは、仮想関数へのポインタを使って処理を呼び出す。このため効率よく仮想関数を動かすことができる。
効率のよいメモリ使用と動的メモリ確保
次にメモリの利用効率の話について解説する。
配列宣言でサイズは定数
C言語では、配列宣言を行う時は、配列サイズに変数を使うことはできない。
最近のC(C99)では、実は下記のようなものは、裏で後述のalloca()を使って動いたりする。(^_^;
void foo( int size ) { int array[ size ] ; // エラー for( int i = 0 ; i < size ; i++ ) array[ i ] = i*i ; } void main() { foo( 3 ) ; foo( 4 ) ; }
メモリ利用の効率
配列サイズには、定数式しか使えないので、1クラスの名前のデータを覚えるなら、以下のような宣言が一般的であろう。
#define MEMBER_SIZE 50 #define NAME_LENGTH 20 char name[ MEMBER_SIZE ][ NAME_LENGTH ] ;
しかしながら、クラスに寿限無とか銀魂の「ビチグソ丸」のような名前の人がいたら、20文字では足りない。(“t-saitoh”くんは配列サイズ9byte、”寿限無”くんは配列220byte といった使い方はできない) また、クラスの人数も、巨大大学の学生全員を覚えたいとい話であれば、 10000人分を用意する必要がある。 ただし、10000人の”寿限無”ありを考慮して、5Mbyte の配列を準備したのに、与えられたデータ量が100件で終わってしまうなら、その際のメモリの利用効率は極めて低い。
このため、最も簡単な方法は、以下のように巨大な文字配列に先頭から名前を入れていき、 文字ポインタ配列に、各名前の先頭の場所を入れる方式であれば、 途中に寿限無がいたとしても、問題はない。
char array[2000] = "ayuka¥0mitsuki¥0t-saitoh¥0tomoko¥0....." ; char *name[ 50 ] = { array+0 , array+6 , array+14 , array+23 , ... } ;
この方式であれば、2000byte + 4byte(32bitポインタ)×50 のメモリがあれば、 無駄なメモリ空間も必要最低限とすることができる。
参考:
寿限無(文字数:全角103文字)
さる御方、ビチクソ丸(文字数:全角210文字)
引用Wikipedia
大きな配列を少しづつ貸し出す処理
// 巨大な配列 char str[ 10000 ] ; // 使用領域の末尾(初期値は巨大配列の先頭) char* sp = str ; // 文字列を保存する関数 char* entry( char* s ) { char* ret = sp ; strcpy( sp , s ) ; sp += strlen( s ) + 1 ; return ret ; } int main() { char* names[ 10 ] ; names[ 0 ] = entry( "saitoh" ) ; names[ 1 ] = entry( "jugemu-jugemu-gokono-surikire..." ) ; return 0 ; } // str[] s a i t o h ¥0 t o m o k o ¥0 // ↑ ↑ // names[0] names[1]
このプログラムでは、貸し出す度に、sp のポインタを後ろに移動していく。
スタック
この貸し出す度に、末尾の場所をずらす方式にスタックがある。
int stack[ 100 ] ; int* sp = stack ; void push( int x ) { *sp = x ; // 1行で書くなら sp++ ; // *sp++ = x ; } int pop() { sp-- ; return *sp ; // return *(--sp) ; } int main() { push( 1 ) ; push( 2 ) ; push( 3 ) ; printf( "%d¥n" , pop() ) ; printf( "%d¥n" , pop() ) ; printf( "%d¥n" , pop() ) ; return 0 ; }
スタックは、最後に保存したデータを最初に取り出せる(Last In First Out)から、LIFO とも呼ばれる。
このデータ管理方法は、最後に呼び出した関数が最初に終了することから、関数の戻り番地の保存や、最後に確保した局所変数が最初に不要となることから、局所変数の管理に利用されている。
alloca() 関数
局所変数と同じスタック上に、一時的にデータを保存する配列を作り、関数が終わると不要になる場合には、alloca() 関数が便利である。alloca の引数には、必要なメモリの byte 数を指定する。100個の整数データを保存するのであれば、int が 32bit の 4byte であれば 400byte を指定する。ただし、int 型は16bitコンピュータなら2byteかもしれないし、64bitコンピュータなら、8byte かもしれないので、sizeof() 演算子を使い、100 * sizeof( int ) と書くべきである。
#include <alloca.h> void foo( int size ) { int* p ; // p = (int*)alloca( sizeof( int ) * size ) ; for( int i = 0 ; i < size ; i++ ) p[ i ] = i*i ; } void main() { foo( 3 ) ; foo( 4 ) ; }
alloca() は、指定された byte 数のデータ領域の先頭ポインタを返すが、その領域を 文字を保存するために使うか、int を保存するために使うかは alloca() では解らない。alloca() の返り値は、使う用途に応じて型キャストが必要である。文字を保存するなら、(char*)alloca(…) 、 intを保存するなら (int*)alloca(…) のように使う。
ただし、関数内で alloca で確保したメモリは、その関数が終了すると、その領域は使えなくなる。このため、最後に alloca で確保したメモリが、最初に不要となる…ような使い方でしか使えない。
ポインタの加算と配列アドレス
ポインタの加算と配列アドレス
ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。
// ポインタ加算の例 int a[ 5 ] = { 11 , 22 , 33 , 44 , 55 } ; void main() { int* p ; // p∇ p = &a[2] ; // a[] : 11,22,33,44,55 // -2 +0 +1 printf( "%d¥n" , *p ) ; // 33 p[0] printf( "%d¥n" , *(p+1) ) ; // 44 p[1] printf( "%d¥n" , *(p-2) ) ; // 11 p[-2] p = a ; // p∇ printf( "%d¥n" , *p ) ; // a[] : 11,22,33,44,55 p++ ; // → p∇ printf( "%d¥n" , *p ) ; // a[] : 11,22,33,44,55 p += 2 ; // → → p∇ printf( "%d¥n" , *p ) ; // a[] : 11,22,33,44,55 }
ここで、注意すべき点は、ポインタの加算した場所の参照と、配列の参照は同じ意味となる。
*(p + 整数式) と p[ 整数式 ] は同じ意味
特に配列 a[] の a だけを記述すると、配列の先頭を意味することに注意。
構造体とポインタ
構造体を関数に渡して処理を行う例を示す。
struct Person { char name[ 10 ] ; int age ; } ; struct Person table[3] = { { "t-saitoh" , 55 } , { "tomoko" , 44 } , { "mitsuki" , 19 } , } ; void print_Person( struct Person* p ) { printf( "%s %d\n" , (*p).name , // * と . では . の方が優先順位が高い // p->name と簡単に書ける。 p->age ) ; // (*p).age の簡単な書き方 } void main() { for( int i = 0 ; i < 3 ; i++ ) { print_Person( &(table[i]) ) ; // print_Person( table + i ) ; でも良い } }
構造体へのポインタの中の要素を参照する時には、アロー演算子 -> を使う。
C言語の制御構文の基礎(part2)
制御構文とフローチャート
構文の入れ子
文と複文
C言語の文法で、{,} は複数の処理をまとめる複文とよばれる。
これに対して、a = 123 ; といったセミコロンで終わる「処理 ;」は単文という。
制御構文は、「if ( 条件) 文」で文となる。このため、文が単文であれば、{,} は不要である。
if ( 条件 ) { a = 123 ; } if ( 条件 ) a = 123 ; // 中括弧は不要
同じように、「while(条件) 文」、「for(A,B,C) 文」、「do 文 while(条件) ;」も、それぞれ文を構成する。
{,} の複文は、{ 文 文 文… } のように、一連の文を実行し、それを1つの文として扱うための機能である。
文と処理順序の理解(レポート2-1)
プログラムの制御構造の確認として、以下のレポートを次回講義までに提出せよ。
以下の3つ(No.1,No.2,No.3)の問題から、
M科,C科,B科の学生は(自分の出席番号 % 2)+1 の問題、E科,EI科の学生は、(自分の出席番号 % 3)+1について、プログラムのフローチャートを描き、その実行順序を20ステップめまで答えよ。
レポートには、
- 元プログラム
- フローチャート
- 実行順序
- 変数の変化がわかる内容
- (できれば、実際にプログラムを動かし、正しいことを検証)
を明記すること。
No.1
No.2
No.3
Excel で計算式の基礎(part1)
情報制御基礎では、プログラムで計算する所を、Excel のような表計算ソフトを用いて検証してもらったりする予定なので、Excel で計算式を使う方法を説明する。
セルの場所と簡単な式
簡単な、品名・単価・個数・価格の表を考える。以下の表のように、列の名前と、品名・単価・個数まで入力した後、単価と個数をかけた価格を求めるとする。
Excel では、表の列には左から、A,B,C,D… , 表の行には上から1,2,3,4,5 と番号が振られていて、特定の列・特定の行のデータを表す時には、列行を組み合わせ、A1に品名、B3に¥80、C5に4 が入っている。
例えば、D2 に、ノート単価120円、ノート個数3個をかけた値を入れたい場合は、D2の場所に、
=B2*C2
を書き込めば、その場所には360が表示される。
D3には、”=B3*C3″を入力すれば、160 が表示される。しかし、この様な式を何度も入力するのは面倒である。
この場合、セル・カーソルを、D2 に合わせ、[右ボタン]-[コピー]を行い、D3 で[右ボタン]-[貼り付けオプション]-[貼り付け]を行えば、”=B3*C3″が入力される。
ここで注意しないといけないのが、式を張り付ける場合には、貼り付け先のセルの場所が一つ下の行なので、行番号を表す2の部分が1つ下の行番号3に書き換えられて、貼り付けが行われる。(相対参照)
関数式
例えば、下左図のような、数字とその平方根の表を作る場合、A2 に 1、B2に =sqrt( A2 ) を入力、A3 に =A2+1 を入力したあと、B2の式をB3にコピー&ペーストし、A3,B3 を A4~A6にペーストすればいい。
B2に入力したような、sqrt( A2 ) のようなものは、関数式と呼ばれる。
また、A3,B3 といった複数の行・列をまとめた範囲を示す時は、A3:B3 といった表記方法であらわす。
絶対参照と相対参照
最初の例に戻って、単価と個数の積で今度は税率を加えて計算する例を考える。また、税率は後で変化するかもしれないので、B1 のセルに税率を記入しておく場合を考える。
この場合、D3 には、” =B3*C3*(1+B1) ” を入力すればいい。
ただ、このように式を入力すると、D3 の計算式を、D4,D5,D6 にコピーすると、セル D4 には =B4*C4*(1+B2) が入力されてしまい、B2 には単価という文字が記載されているため、正しい結果が求まらない。
こういった場合には、絶対参照を用いる。D3 に記入する式を
=B3*C3*(1+$B$2)
とし、この D3 の式を D4 にコピー&ペーストすると、列記号、行番号の前に$がついた部分の式は、貼り付け場所に応じて変化しない。
このような、$B$2 といったセルの参照は、絶対参照と呼ぶ。これに対し、B2 といったセル参照は、貼り付け場所に応じて書き換えられるので、相対参照と呼ぶ。
絶対参照と相対参照が混ざった、$B2, B$2 といった書き方もある。
式の入力時にF4ボタンを押す度に、B2→$B$2→B$2→$B2→B2 と変化する
$B2 は、式をコピーすると列部分はBのまま、行部分は場所に合わせて変化する。
B$2 は、式をコピーすると列部分は場所に合わせて変化し、行部分は2のままとなる。
レポート課題(2-2)
Excel で、xを0〜180度まで変化させたときのsin(x),位相をyとした時のsin(x+y)の値の表を作り、グラフ機能で表示せよ。
レポートには、セルにどのような式を入力したかの説明と、結果のグラフ(解りやすいように表示を工夫すること)をつけること。
派生と継承
隠ぺい化の次のステップとして、派生・継承を説明する。
派生を使わずに書くと…
元となるデータ構造(例えばPersonが名前と年齢)でプログラムを作っていて、 途中でその特殊パターンとして、所属と学年を加えた学生(Student)という データ構造を作るとする。
// 元となる構造体(Person) struct Person { char name[ 20 ] ; // 名前 int age ; // 年齢 } ; // 初期化関数 void set_Person( struct Person* p , char s[] , int x ) { strcpy( p->name , s ) ; p->age = x ; } // 表示関数 void print_Person( struct Person* p ) { printf( "%s %d\n" , p->name , p->age ) ; } void main() { struct Person saitoh ; set_Person( &saitoh , "t-saitoh" , 50 ) ; print_Person( &saitoh ) ; }
パターン1(そのまんま…)
上記のPersonに、所属と学年を加えるのであれば、以下の方法がある。 しかし以下パターン1は、要素名がname,ageという共通な部分があるようにみえるが、 プログラム上は、PersonとPersonStudent1は、まるっきり関係のない別の型にすぎない。
このため、元データと共通部分があっても、同じ処理を改めて書き直しになる。
// 元のデータに追加要素(パターン1) struct PersonStudent1 { // Personと同じ部分 char name[ 20 ] ; // 名前 int age ; // 年齢 // 追加部分 char dep[ 20 ] ; // 所属 int grade ; // 学年 } ; void set_PersonStudent1( struct PersonStudent1* p , char s[] , int x , char d[] , int g ) { // set_Personと同じ処理を書いている。 strcpy( p->name , s ) ; p->age = x ; // 追加された処理 strcpy( p->dep , d ) ; p->grade = g ; } // 名前と年齢だけ表示 void print_PersonStudent1( struct PersonStudent1* p ) { // print_Personと同じ処理を書いている。 printf( "%s %d\n" , p->name , p->age ) ; } void main() { struct PersonStudent1 yama1 ; set_PersonStudent1( &yama1 , "yama" , 22 , "PS" , 2 ) ; print_PersonStudent1( &yama1 ) ; }
パターン2(元データの処理を少し使って…)
パターン1では、同じような処理を何度も書くことになり、面倒なので、 元データ用の関数をうまく使うように書いてみる。
// 元のデータに追加要素(パターン2) struct PersonStudent2 { // 元のデータPerson struct Person person ; // 追加部分 char dep[ 20 ] ; int grade ; } ; void set_PersonStudent2( struct PersonStudent2* p , char s[] , int x , char d[] , int g ) { // Personの関数を部分的に使う set_Person( &(p->person) , s , x ) ; // 追加分はしかたない strcpy( p->dep , d ) ; p->grade = g ; } void print_PersonStudent2( struct PersonStudent2* p ) { // Personの関数を使う。 print_Person( &p->person ) ; } void main() { struct PersonStudent2 yama2 ; set_PersonStudent2( &yama2 , "yama" , 22 , "PS" , 2 ) ; print_PersonStudent2( &yama2 ) ; }
このパターン2であれば、元データ Person の処理をうまく使っているので、 プログラムの記述量を減らすことはできるようになった。
しかし、print_PersonStudent2() のような処理は、元データ構造が同じなのに、 いちいちプログラムを記述するのは面倒ではないか?
そこで、元データの処理を拡張し、処理の流用ができないであろうか?
基底クラスから派生クラスを作る
オブジェクト指向では、元データ(基底クラス)に新たな要素を加えたクラス(派生クラス)を 作ることを「派生」と呼ぶ。派生クラスを定義するときは、クラス名の後ろに、 「:」「public/protected/private」基底クラス名を書く。
// 基底クラス class Person { private: char name[ 20 ] ; int age ; public: Person( const char s[] , int x ) : age( x ) { strcpy( name , s ) ; } void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス(Student は Person から派生) class Student : public Person { private: // 追加部分 char dep[ 20 ] ; int grade ; public: Student( const char s[] , int x , const char d[] , int g ) : Person( s , x ) // 基底クラスのコンストラクタ { // 追加された処理 strcpy( dep , d ) ; grade = g ; } } ; void main() { Person saitoh( "t-saitoh" , 50 ) ; saitoh.print() ; Student yama( "yama" , 22 , "PS" , 2 ) ; yama.print() ; }
ここで注目すべき点は、main()の中で、Studentクラス”yama”に対し、yama.print() を呼び出しているが、パターン2であれば、print_PersonStudent2()に相当するプログラムを 記述していない。 しかし、この派生を使うと Person の print() が自動的に流用することができる。 これは、基底クラスのメソッドを「継承」しているから、 このように書け、名前と年齢「yama 22」が表示される。
さらに、Student の中に、以下のような Student 専用の新しい print()を記述してもよい。
class Student ...略... { ...略... // Student クラス専用の print() void print() { // 親クラス Person の print() を呼び出す Person::print() ; // Student クラス用の処理 printf( "%s %d\n" , dep , grade ) ; } } ; void main() { ...略... Student yama( "yama" , 22 , "PS" , 2 ) ; yama.print() ; }
この場合は、継承ではなく機能が上書き(オーバーライト)されるので、 「yama 22 / PS 2」が表示される。
派生クラスを作る際の後ろに記述した、public は、他にも protected , private を 記述できる。
public だれもがアクセス可能。 protected であれば、派生クラスからアクセスが可能。 派生クラスであれば、通常は protected で使うのが一般的。 private 派生クラスでもアクセス不可。
仮想関数への伏線
上記のような派生したプログラムを記述した場合、以下のようなプログラムでは何が起こるであろうか?
class Student ... { : void print() { Person::print() ; // 名前と年齢を表示 printf( " %s %d¥n" , dep , grade ) ; // 所属と学年を表示 } } ; void main() { Person saitoh( "t-saitoh" , 55 ) ; saitoh.print() ; // t-saitoh 55 名前と年齢を表示 Student mitsu( "mitsuki" , 19 , "E" , 4 ) ; Student ayuka( "ayuka" , 17 , "EI" , 2 ) ; mitsu.print() ; // mitsuki 19 / E 4 名前,年齢,所属,学年を表示 ayuka.print() ; // ayuka 17 / EI 2 名前,年齢,所属,学年を表示 Person* family[] = { &saitoh , &mitsu , &ayuka , // 配列の中に、Personへのポインタと } ; // Studentへのポインタが混在している // 派生クラスのポインタは、 // 基底クラスのポインタとしても扱える for( int i = 0 ; i < 3 ; i++ ) family[ i ]->print() ; // t-saitoh 53/mitsuki 18/ayuka 16 } // が表示される。
ソートアルゴリズム
前回の授業のハノイの塔は、単純な再帰方程式で処理時間のオーダーが巨大となる一例として示した。そこで、プログラムの中でよく利用されるデータの並び替え(ソート)で処理時間の分析を行ってみる。
様々なソートアルゴリズム
データの有名な並び替えアルゴリズムとその処理時間のオーダーを示す。
- バブルソート O(N2)
- 選択法 O(N2/2)
- クイックソート O( N log N )
- マージソート O( N log N )
マージソートの分析
マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。
このことから、再帰方程式は、以下のようになる。
この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが、 となる。
:
よって、
選択法とクイックソートの処理時間の比較
データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。
- データ件数 N = 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
- データ件数何件以上なら、クイックソートの方が高速になるか答えよ。
設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。
実数型と取り扱いの注意
実数型(float / double)
実数型は、単精度実数(float型)と、倍精度実数(double型)があり、それぞれ32bit,64bitでデータを扱う。
単精度型(float)では、符号1bit,指数部8bit,仮数部23bitで値を覚え、数値としては、以下の値を意味する。(精度が低いので普通のコンピュータではあまり使われることはない)
符号✕ 1.仮数部 ✕ 2指数部-127
倍精度型(double)では、符号1bit,指数部11bit,仮数部52bitで値を覚え、数値としては、以下の意味を持つ。
符号✕ 1.仮数部 ✕ 2指数部-1023
倍精度型を使えば、正しく計算できるようになるかもしれないが、実数型はただの加算でも仮数部の小数点の位置を合わせたりする処理が必要で、浮動小数点専用の計算機能を持っていないような、ワンチップコンピュータでは整数型にくらべると10倍以上遅い場合もある。
実数の注意点
C言語でプログラムを作成していて、簡単な数値計算のプログラムでも動かないと悩んだことはないだろうか?解らなくて友達のプログラムを真似したら動いたけど、なぜ自分のプログラムは動かなかったのか深く考えたことはあるだろうか?
単純な合計と平均
整数を入力し、最後に合計と平均を出力するプログラムを以下に示す。
しかし、C言語でこのプログラムを動かすと、10,10,20,-1 と入力すると、合計(sum)40,件数(cnt)3で、平均は13と表示され、13.33333 とはならない。
小数点以下も正しく表示するには、どうすればいいだろうか?
ただし、変数の型宣言を “double data,sum,cnt ;” に変更しないものとする。
// 入力値の合計と平均を求める。 #include <stdio.h> int main() { int data ; int sum = 0 ; int cnt = 0 ; for(;;) { printf( "数字を入力せよ。-1で終了¥n" ) ; scanf( "%d" , &data ) ; if ( data < 0 ) break ; cnt = cnt + 1 ; sum = sum + data ; } printf( "合計 %d¥n" , sum ) ; printf( "平均 %d¥n" , sum / cnt ) ; }
C言語では、int型のsum / int型のcnt の計算は、int 型で計算を行う。このため、割り算だけ実数で行いたい場合は、以下のように書かないといけない。
printf( "平均 %lf¥n" , (double)sum / (double)cnt ) ;
// (double)式 は、sum を一時的に実数型にするための型キャスト
まずは動く例
以下のプログラムは、見れば判るけど、th を 0度〜360度まで5度刻みで変化させながら、y = sin(th) の値を表示するプログラム。
// sin の値を出力 #include <stdio.h> #include <math.h> int main() { double th , y ; for( th = 0.0 ; th <= 360.0 ; th += 5.0 ) { y = sin( th / 180.0 * 3.1415926535 ) ; printf( "%lf %lf¥n" , th , y ) ; } return 0 ; }
動かないプログラム
では、以下のプログラムはどうだろうか?
// case-1 ---- プログラムが止まらない #define PI 3.1415926535 int main() { double th , y ; // 0〜πまで100分割でsinを求める for( th = 0.0 ; th != PI ; th += PI / 100.0 ) { y = sin( th ) ; printf( "%lf %lf¥n" , th , y ) ; } return 0 ; }
// case-2 ---- y の値が全てゼロ int main() { int th ; double y ; for( th = 0 ; th <= 360 ; th += 5 ) { y = sin( th / 180 * 3.1415926535 ) ; printf( "%d %lf¥n" , th , y ) ; } return 0 ; }
どちらも、何気なく読んでいると、動かない理由が判らないと思う。そして、元のプログラムと見比べながら、case-1 では、「!=」を「<=」に書き換えたり、case-2 では、「int th ;」を「double th ;」に書き換えたら動き出す。
では何が悪かったのか…
回答編