今回は片方向リストについて紹介します。
■対象者
リストとは?
リストの動作イメージがつかない・・・
という人が対象です。
■リストを使うメリット
①要素の挿入、削除が可能。
配列では要素を追加しようとすると、要素を全て移動させる必要があり、時間がかかる。
②メモリの節約につながる。
配列では宣言した段階でメモリが連番で用意されるため、メモリが空いていないと使えない。リストは連番である必要はない。
■リストとは?
リストとは、個々のデータがポインタを利用して次々と繋がっている構造を持つデータのことです。ポインタが次の変数を示して連結している構造を持つデータのこと。
(復習:ポインタとは?⇒アドレスを記憶することのできる変数。
int *p;
ポインタ型:ポインタの中にどのような型の変数のアドレスが格納されているか教えてくれるもの。int型の変数のアドレスが格納してあることを教えてくれている。
ポインタ値:ポインタに格納されている値のこと。つまり、アドレスのこと。
ポインタ変数:ポインタ型で宣言された変数のこと。つまり、pのこと。)
リスト構造には
・片方向リスト:後ろのデータしか参照できない。一方通行。
・双方向リスト:前と後ろ両方のデータを参照することができる。
が存在する。
■実装コード
#include "stdafx.h"
typedef struct tag{
int data;
struct tag *next; //構造体タグ(構造体の型)がlistである構造体を用意。ポインタnextが指す型はlist型になる
}list ; //構造体タグとしてlistを宣言しておかないと、listを型として持つメンバがある為コンパイルエラーとなる。listが構造体変数。
/*typedef struct {
char StationName[10];
struct list *next; //構造体タグ(構造体の型)がlistである構造体を用意。ポインタnextが指す型はlist型になる
}list; //上記と論理的には同じであるが、最初にlistが構造体タグであることをコンパイラ―に教えておく必要がある。*/
int main()
{
list node1,node2,node3;
list *p;
node1.data = 1;
node2.data = 2;
node3.data = 3;
node1.next = &node2;
node2.next = &node3;
node3.next = NULL;
p = &node1;
printf("p->data=%d\n", p->data);
printf("p->next->data=%d\n", p->next->data);
printf("p->next->next->data=%d\n", p->next->next->data);
p = node1.next;
printf("p->data=%d\n", p->data);
return 0;
}
実行結果
■図による概要説明
nodeはこのようにint型のdataとポインタnextの箱からなります。
そして、nextは次の箱の先頭アドレスを指して次々と繋がっています。
また、listの先頭はポインタpが指しており、最後はNULLというどこでもないところ指すようになっています。
上記の図はp=&node1を代入した状態の図です。従って、今、pはnode1の先頭アドレスを指しています。
そのため、printf("p->data=%d",p->data)では,node1のdataである1が表示されます。
同様に、p=&node2とした場合は、pはnode2の先頭アドレスを指している為、node2のdataである2を表示します。
毎回pにそれぞれのアドレスを代入していては、連結させている意味がないので、
p->next->dataとするとpが指すnode1のポインタnextが指す要素であるdataにアクセスできます。
つまり、p=&node2としてp->dataとp=&nodeとしてp->next->dataは同じ2を指します。
このようにして、次々と要素にアクセスすることが可能となります。
要素の追加と削除については次回。
読んでいただきありがとうございました。