mallocによる動的メモリ確保の説明が終わったので、 次のステップとしてリスト構造の話を行う。 アパートの回覧板の管理をイメージしてもらいながら、 次のデータの場所を管理する方法を説明。

int top = 3 ;
struct List {
int  data ;
int  next ;
} list[ 10 ] = {
{ 5 , 4 } , //0
{ 4 , 0 } , //1
{ 2 , 1 } , //2
{ 1 , 2 } , // 3
{ 8 ,-1 } , //4
} ;
for( int i = top ; i >= 0 ; i = list[ i ].next )
printf( "%d" , list[ i ].data ) ; // 昇順に表示される。

次に、この次のデータの「配列添え字」ではなく、 データ１件毎にメモリを確保し、次のメモリの番地をつなぐために、 以下のような方法をとる。

struct List {
int  data ;
struct List* next ;
} ;
// 理解してもらうためにあえて面倒な処理をそのまま書く
struct List* top ;
top = (struct List*)malloc( sizeof( struct List ) ) ;
top->data = 1 ;
top->next = (struct List*)malloc( sizeof( struct List ) ) ;
top->next->data = 2 ;
top->next->next = (struct List*)malloc( sizeof( struct List ) ) ;
top->next->next->data = 3 ;
top->next->next->next = NULL ;
// もう少し簡単に
struct List* cons( int x , struct List*n ) {
struct List* ans ;
if ( (ans = (struct List*)malloc(sizeof(struct List))) != NULL ) {
ans->data = x ;
ans->next = n ;
}
return ans ;
}
struct List* top = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;

この例で、データがいかに作られるのか説明の後、そのデータを扱うプログラムとして、 リストの件数・合計・最大値を求めるプログラムを、考えてもらったり、再帰呼び出しで 書いてもらう。

// 例：リストの件数
int count( struct List*p ) {
for( int c = 0 ; p != NULL ; p = p->next )
c++ ;
return c ;
}
// ループを使わずに再帰で合計
int sum( struct List*p ) {
if ( p == NULL )
return 0 ;
else
return p->data + sum( p->next ) ;
}

授業後にテストの質問として、過去問題の質問に答える。 昨年度の出題のネタだけど、ポインタと動的確保したデータのイメージを 確認する出題をしているが、詳しく授業でまだ説明していない。 来週は、テスト前対策ということで、説明を加えようか…

// 以下のようなメモリ確保を行った場合の、データの格納イメージは？
struct Complex {
double re , im ;
} ;
struct Complex data1[ 2 ] ;
struct Complex* data2
= (struct Complex*)malloc( sizeof( struct Complex ) * 2 ) ;
struct Complex* data3[ 2 ] = {
(struct Complex*)malloc( sizeof( struct Complex ) ) ,
(struct Complex*)malloc( sizeof( struct Complex ) ) ,
} ;
struct Complex** data4 ;
= (struct Complex**)malloc( sizeof( struct Complex* ) * 2 ) ;
data4[0] = (struct Complex*)malloc( sizeof( struct Complex ) ) ;
data4[1] = (struct Complex*)malloc( sizeof( struct Complex ) ) ;