リスト構造の導入

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 ) ; // 昇順に表示される。

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

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 ) ) ;
 

2015年12月

    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

アーカイブ

Google

このブログ記事について

このページは、T-Saitohが2010年6月 4日 11:56に書いたブログ記事です。

ひとつ前のブログ記事は「高等専門学校機関別認証評価の説明会参加」です。

次のブログ記事は「LEDメッセンジャーを行き先表示板に」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。