ポインター(+malloc関数)を利用した線形リストの実現

これが本講義でベストとする方法です。まず上記の配列を利用する方法には問題があります.配列はデータがいくつあるのかをあらかじめ決めないといけません。→ 漠然と100くらいとか 1000くらい...として決めておくとメモリが無駄になります. プ ログラム中で宣言された変数は,コンパイル時にスタック領域に確保されます.例えば, int a[100]と宣言した → int型のメモリ領域が100個分確保したということです.もし,100個以上のデータが出現したらそれ以上は格納できません.

この問題を解決するのが ポインターとmalloc/calloc関数を利用した動的メモリ確保です.

mallocで動的に生成されたメモリ領域は名前(変数名)がありませんが、ポインタ変数によりその領域を指し示す(実質、変数名を割り当てる)ことができます。

関連項目

以下の項目は理解しておくこと

ポインタの復習

例えば、上記の図のように、

P=mallocNode();

と書くと、mallocNodeで確保された領域は、Pというポインタ変数で呼ぶ事ができます。そして、その状態で

Q=P;

と書くと、mallocNodeで確保された領域は、QでありまたPでもあります

ポインターを利用した線形リストのイメージ

構造体の構造

下記のように、次のデータの位置を指し示すポインタ変数がメンバーとしてあることに注意してください

//単方向リスト

typedef struct _node{

char *name; //名前を管理するポインタ

struct _node *next; //次のノードの情報を管理するポインタ

}Node ;

注意事項(復習)

ポインターを利用する場合、具体的なメモリのアドレス(番地)を意識することはしません。そこで、上記の図にようにポインタ変数がどこを指しているのかを意識する必要があります。

ポインタ+動的 なメモリ確保によるリストプログラムの考え方

以下の説明では、malloc, calloc,mallocNodeという関数が出てきますが、新たなメモリ領域を生成するという点で同様なものであると考えて読み替えてください。

1.最初のデータを格納するメモリ領域を動的確保(mallocNode)

2.その領域の場所をポインタ変数(top)で捕捉

3.次のデータを格納するメモリ領域を動的確保(mallocNode)

4.その領域の場所をポインタ変数(new)で捕捉

5.topの次にnewが来るように(newをリストの末尾にする)

6.その領域の場所をポインタ変数(tail)で捕捉

7.次のデータを格納するメモリ領域を動的確保(mallocNode)

8.その領域の場所をポインタ変数(new)で捕捉

9.newをリストの末尾に追加

10.末尾のノードをtailとする

データの数だけmalloc で メモリ(変数)を生成し,作成されたメモリ領域の位置(アドレス)をたどっていくようにリストを作ればよいわけですが、いきなりそのプログラムを見ても意味不明だと思いますので、まずは簡単なサンプルで説明します。

1.とりあえず2チーム分のデータを格納するメモリ領域をcallocで確保し、ポインタと関連付けます。

Node *node1 = mallocNode();
Node *node2 = mallocNode();

この記述が意味することは,

「mallocNode関数によって確保された領域を,node1、node2というポインタで指し示します」ということです.

node1、node2にはそれぞれ異なったメモリ領域が確保されたということを理解してください。

2.各ノードにデータを格納する

node1->name="nishioka";
node1->name="yamato";

3. 構造体メンバーのnextに次のノードの情報を渡す

node1->next = node2;

この記述は、「node1の次 は、node2である」ということを意味します。

4.先頭ノードから検索する

以下のように辿っていきます。

Node *head =node1;
Node  *now = head;
  //(コ)リストの端になるまでnowを移動しながらデータを出力
  while(now!=NULL){
    printf("%s\n",now->data);
    now=now->next;
  }

注意!メモリの解放を意識すること

callocで確保したメモリ領域は、free関数を利用して解放するのが一般的です。ただし、解放したアドレスの対して再度解放しようとした際の挙動は、環境(OS)などによって変わってきます。