後期の中間試験までで、構造体について説明の予定。

構造体がなかったら

構造体がない場合、同じようなデータが複数現れると、 配列にしたりすることになるが、そのバリエーションでは、 単純に配列にするだけでは不十分となる。

#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 といった名前を使い分ける必要があり、 同じような処理をまとめることが難しい。

構造体を使う

複数の異なるデータを、１つの型としてまとめるものが、 構造体。最近のオブジェクト指向では、構造体の概念を 拡張したものなので、必ず使えるようになっておく必要あり。

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つの構造化を合わせて、構造化プログラミングと呼ぶ。

後期最初の授業ということで、今までの内容の総括っぽい 質問を交えながらの授業。

単純リストでは、中央値の参照がO(N)であるため、 そのままでは２分探索法のような処理はできない。

そこで、データと２つの枝からなるノードを作り、 データより小さい値を要素にもつ枝を左に、 大きいものは右枝に格納し、この状態がどこでも成り立つようにする。この方式は、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 = 2^m-1となり、 m段が綺麗に充填されていれば、最悪の場合のループ回数がmであることから、 処理速度は、O(log(N))となる。

データの挿入では、NULLが入った末端まで辿り着いて、新しい枝を挿入することから、 挿入場所の決定(O(log N)),枝追加(O(1))の時間であり、配列(O(N))などに比べても高速となる。 ただし、このデータのような data 部が小さい場合には、data 1件につき2本のポインタを 使用することから、メモリの使用効率は良くない。

ヒープ

2分木とおなじ考え方で、配列の添字をうまくつかった方式にヒープがある。 この方式では、前述の2分探索木のデータを、配列に以下のように格納する。

この方式を取れば、i番目の要素の左枝は(i*2+1) , 右枝は(i*2+2)といった 簡単な計算で求められる。この方式であれば、ポインタは不要となる。 ただし、新たなデータの挿入処理では、段の上からデータを入れ替えを繰り返すなどの 処理が必要となる。

次回には、このデータを操作するための処理で、再帰呼び出しなどを用いる事例を紹介。

紀要の原稿の修正で、ファイルを触ったら、 epsファイルの位置がずれるトラブル。

いろいろ試したけど、うまくいかない。 以前は動いていたので、texlive の更新 のトラブルと考え、ひとまず texlive 関連を アンインストールし、stable にて再インストール。

# aptitude remove texlive
# aptitude install texlive/stable

すりゃいいんだろうけど、どれ消す、どれ入れるだ、 選択肢を選ぶのが大変なので、一時的に apt-source から testing,unstable を消して インストールを行う。