List 連鎖の基礎

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

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

List構造

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

プログラムの説明

  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 の値(１～５)をデータ領域(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++)

※・