List 連鎖の基礎

構造体を連鎖してList構造を構築します。

前田稔の超初心者のプログラム入門

List構造

  1. 複数の要素の並びを扱うデータ構造として配列があります。
    しかし、配列には次のような欠点があります。
    これらの欠点を一挙に解決してくれるのが List 構造です。
  2. List 構造とはセルをポインタで連鎖したデータ構造です。
    セルは次のセルに連鎖するためのポインタとデータ領域で構成されます。
    最も単純なセルは次のようになります。
    ポインタ データ
  3. セルをポインタで連鎖した List 構造の概念図です。
    次のセル データ1
        ↓
    次のセル データ2
        ↓
        ・・・
    次のセル データn-1
        ↓
    null データn

プログラムの説明

  1. 次のセルに連鎖するためのポインタ(*pt)とデータ領域(v)の宣言です。
    *top は List 構造の先頭ポインタです。
    /*★ List 連鎖の基礎    前田 稔 ★*/
    #include <stdio.h>
    
    struct  LST
    {   struct  LST *pt;
        int     v;
    };
    
    struct  LST *top= NULL;     //List の先頭ポインタ
    
  2. *wk は List 構造の作業用ポインタです。
    i はループのカウンタで、今回は i の値(1~5)をデータ領域(v)に格納しています。
    構造体の領域は new LST; で割り当てます。
    ループから抜け出したときに *top に List 構造の先頭ポインタが格納されています。
    完成した List を「List 構造」で説明したように、図で表してみて下さい。
    //☆ MAIN
    void  main()
    {   int     i;
        struct  LST *wk;
    
        //List を連鎖
        for(i=1; i<6; i++)
        {   wk= new LST;
            wk->v= i;
            wk->pt= top;
            top= wk;
        }
    
  3. 完成した List を *top からたどってデータ領域(v)を印字しています。
    印字される順番を考えてみて下さい。
        //List をたどって印字
        for(wk=top; wk!=NULL; wk=wk->pt)    printf("%5d",wk->v);
    
  4. new LST; で割り当てた領域を開放します。
    List の末端から開放するのが原則なので free() 関数で再起的に開放しています。
        //List を開放
        free(top);
    }
    
  5. 再起的に List を開放する関数です。
    開放する前にデータ領域(v)を印字しています。
    印字される順番を考えてみて下さい。
    // 再帰で領域を開放する
    void  free(struct LST *lst)
    {   if (lst==NULL)  return;
        free(lst->pt);
        printf("%3d開放",lst->v);
        delete lst;
        return;
    }
    
  6. List を使ったプログラムの例は Binary Tree ソート などを参照して下さい。

超初心者のプログラム入門(C/C++)