2013年10月13日(第342回)
- 大学学園祭について
- まるよし Train Pops ~ 国語と遊ぼう! 第26便 「発声」
- 安全とコストのバランスについて
- エコラン参加について
- 五味が答える!~かかってこいや~
担当:前田勝(4EI)、山野(2C)、五味(教員)
※今回放送しました まるよし Train Pops ~ 国語と遊ぼう! 第26便 は収録環境の不具合のためお聞きづらくなっておりました。お聞きの方にご迷惑をおかけしました。
構造体と関数とアロー演算子
前回の授業で、構造体の入れ子などの話をしたので、 構造体のポインタ渡しと、オブジェクト指向について話を行う。 オブジェクト指向については、プログラム記述はテスト範囲とはしないことを伝えておく。
ポインタ渡しによる関数化
構造体の配列に対する処理の例として、入力処理と出力処理を関数化する例を示す。
struct Person { char name[ 10 ] ; int age ; } ; void input( struct Person* p ) { scanf( "%s%d" , (*p).name , &( (*p).age ) ) ; } void output( struct Person* p ) { scanf( "%sさんの年齢は%d歳です\n" , (*p).name , (*p).age ) ; } void main() { struct Person data[ 10 ] ; for( int i = 0 ; i < 10 ; i++ ) { input( &(data[i]) ) ; output( &(data[i]) ) ; } }
ただし、(*p).name といった記載は、面倒なので、 p->nameといった記載が可能。
このプログラムでは、main内部には、Person内部のデータについての 記載がない。このため、Personというデータの内部を知らなくても、 10件分のデータの入力出力が記述できる。 こういった、データ構造や関数内の処理を知らなくても、プログラム記述が できることを隠蔽化と呼ぶ。 特に、関数を用いることで、関数内部の処理手順を知らなくてもよくなり、 これは「手続きの隠蔽化」と呼ばれる。 また、構造体を用いることで、データ構造の内部を知らなくてもよいことは、 「データの隠蔽化」と呼ばれ、この2つの隠蔽化をうまく使えば、 プログラム作成の分業化ができるようになる。
オブジェクト指向
前述の構造体を用いたプログラムは、オブジェクト指向の考え方の 入口となる。このプログラムは、C++であれば。
class Person { private: char name[ 10 ] ; int age ; public: void input() { scanf( "%s%d" , name , &age ) ; } void output() { printf( "%sさんは%d歳です。\n" , name , age ) ; } } ; void main() { Person data[ 10 ] ; for( int i = 0 ; i < 10 ; i++ ) { data[ i ].input() ; data[ i ].output() ; } }
コンピュータの構成とプログラムが動くしくみ
プログラムが、OSによってRAMに呼び出されて動く仕組みや、高級言語の動くしくみを説明する。
コンピュータの構成
コンピュータの基本的構成部品は、CPU,主記憶,補助記憶,周辺装置。 CPUは、メモリから機械語の命令を読み取り(Fetch)、解析(Decode)、メモリ読み出し(Read)、実行(Execute)、メモリ書き込み(Write)を繰り返す。 メモリは、読み出しだけのROMと、読み書きのRAMから構成されるが、 ROMだけでは自由にプログラムを入れ替えて動かすことができない。
コンピュータは電源が入ると、OSを起動するために、ROMに入っている周辺装置を扱い方のBIOSを使い、 OSを起動させるためのプログラム(ブートローダ)を起動する。ブートローダは最終的にOSを起動させ、 ユーザプログラムの起動を待つ。ユーザのプログラム起動要求により、補助記憶装置から プログラムを主記憶に読み出し、実行を行う。
プログラムが動くしくみ
プログラムといっても、コンパイラ方式、インタプリタ方式などがある。 コンパイラは高級言語で書かれたプログラムを、直接実行可能な機械語に変換しておく。 このため、実行時の速度は速い。しかし、プログラムの実行するには、コンパイル・リンクなどの手間が必要となる。また、元々のプログラムがどういった記述なのか解析は困難。 インタプリタ方式は、高級言語のソースを必要に応じて命令の意味を解析し、その都度実行を行う。 このため、プログラムの試作段階で動作を確認しながら開発を行う際には便利である。 しかし、プログラムを実行する際に、高級言語のソースコードが必要となる。 最近では、バイトコードインタプリタ方式と呼ばれる方式もよく利用される。 高級言語の命令を、実行しやすい機械語に近いシンプルな命令にコンパイルし、実行を行う。
一般的なコンパイラ方式では、プログラムを実行するまでに、
- 高級言語のソースを、コンパイルし中間コードを生成。
- 中間コードと、ライブラリ(一般的な関数の処理の中間コードをまとめたもの)を組み合わせて、機械語を生成(リンク処理)
といった手順をとる。
最近のOSは、マルチユーザ・マルチタスクであるため、ライブラリの機械語は同時に動く他のプログラムでも同じように使われている場合が多い。この時、ライブラリの機械語コードがメモリ上に複数あると、 メモリの無駄や、ライブラリの更新の手間が増える。 このため、最近のOSでは、動的リンクライブラリという方式を使い、ライブラリを共有して用いる。
2013年10月6日(第341回)
- 鯖江CM対象応募について
- まるよし Train Pops ~ 国語と遊ぼう! 第25便 「外国語と外来語」
- ベトナムの話
担当:前田勝(4EI)、山野(2C)、西(教員)
構造体
後期の中間試験までで、構造体について説明の予定。
構造体がなかったら
構造体がない場合、同じようなデータが複数現れると、 配列にしたりすることになるが、そのバリエーションでは、 単純に配列にするだけでは不十分となる。
#define SIZE 50 char name[ SIZE ][ 20 ] ; int math[ SIZE ] ; int sci[ SIZE ] ; int eng[ SIZE ] ; // 複数の学科 char m_name[ SIZE ][ 20 ] ; int m_math[ SIZE ] ; : int ei_name[ SIZE ][ 20 ] ; int ei_math[ SIZE ] ; :
m_name , ei_name といった名前を使い分ける必要があり、 同じような処理をまとめることが難しい。
構造体を使う
複数の異なるデータを、1つの型としてまとめるものが、 構造体。最近のオブジェクト指向では、構造体の概念を 拡張したものなので、必ず使えるようになっておく必要あり。
struct Student { char name[ 20 ] ; int math ; int sci ; int eng ; } ; struct Student saitoh ; struct Student data[ 50 ] ; saitoh.math = 80 ; strcpy( saitoh.name , "t-saitoh" ) ; strcpy( data[ 0 ].name , "aoyama" ) ; data[ 0 ].eng = 90 ;
基本は、構造体変数名.要素名 で参照すれば、普通の変数と同じ。
構造体は入れ子にすることもできる。
struct Birthday { int year ; int month ; int day ; } ; struct Person { char name[ 20 ] ; int age ; struct Birthday bday ; } ; struct Person saitoh = { "t-saitoh" , 48 , { 1965 , 2 , 7 } } ;
このように、データ構造をブロック化することを、データの構造化と呼ぶ。 同じように、if (…) { while(…) { … } } といった、ような 入れ子にすることは、手続きの構造化と呼ばれる。 この2つの構造化を合わせて、構造化プログラミングと呼ぶ。
2分探索木
後期最初の授業ということで、今までの内容の総括っぽい 質問を交えながらの授業。
単純リストでは、中央値の参照がO(N)であるため、 そのままでは2分探索法のような処理はできない。
そこで、データと2つの枝からなるノードを作り、 データより小さい値を要素にもつ枝を左に、 大きいものは右枝に格納し、この状態がどこでも成り立つようにする。この方式は、2分木(2分探索木)と呼ばれる。
struct Tree { int data ; struct Tree* left ; struct Tree* right ; } ; struct Tree* tcons( int v , struct Tree* l , struct Tree* r ) { struct Tree* n ; n = (struct Tree*)malloc( sizeof( struct Tree ) ) ; if ( n != NULL ) { n->data = v ; n->left = l ; n->right = r ; } return n ; } int find( struct Tree* p , int key ) { while( p != NULL ) if ( p->data == key ) return 1 ; else if ( p->data < key ) p = p->left ; else p = p->right ; } return 0 ; } void main() { struct Tree* top = tcons( 53 , tcons( 28 , tcons( 14 , NULL , NULL ) , tcons( 40 , NULL , NULL ) ) , tcons( 80 , tcons( 63 , NULL , NULL ) , tcons( 91 , NULL , NULL ) ) ) ; if ( find( top , 80 ) ) printf( "find 80\n" ) ; }
この方式であれば、m段のピラミッド状の木であれば、データ件数 N = 2m-1となり、 m段が綺麗に充填されていれば、最悪の場合のループ回数がmであることから、 処理速度は、O(log(N))となる。
データの挿入では、NULLが入った末端まで辿り着いて、新しい枝を挿入することから、 挿入場所の決定(O(log N)),枝追加(O(1))の時間であり、配列(O(N))などに比べても高速となる。 ただし、このデータのような data 部が小さい場合には、data 1件につき2本のポインタを 使用することから、メモリの使用効率は良くない。
ヒープ
2分木とおなじ考え方で、配列の添字をうまくつかった方式にヒープがある。 この方式では、前述の2分探索木のデータを、配列に以下のように格納する。
添字 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
データ | 53 | 28 | 80 | 14 | 40 | 63 | 91 |
この方式を取れば、i番目の要素の左枝は(i*2+1) , 右枝は(i*2+2)といった 簡単な計算で求められる。この方式であれば、ポインタは不要となる。 ただし、新たなデータの挿入処理では、段の上からデータを入れ替えを繰り返すなどの 処理が必要となる。
次回には、このデータを操作するための処理で、再帰呼び出しなどを用いる事例を紹介。
texlive-full でかっ
紀要の原稿の修正で、ファイルを触ったら、 epsファイルの位置がずれるトラブル。
いろいろ試したけど、うまくいかない。 以前は動いていたので、texlive の更新 のトラブルと考え、ひとまず texlive 関連を アンインストールし、stable にて再インストール。
# aptitude remove texlive # aptitude install texlive/stable
すりゃいいんだろうけど、どれ消す、どれ入れるだ、 選択肢を選ぶのが大変なので、一時的に apt-source から testing,unstable を消して インストールを行う。