リストの演習
リストの基礎（ここ）
リストはデータとポインタを組にしたノードが、順につながったデータ構造である。
code:link.c
typedef struct Node{
int data;
struct Node * next;
} Node;
int main(void){
Node n1, n2, n3;
n1.data = 1;
n1.next = &n2;
n2.data = 2;
n2.next = &n3;
n3.data = 3;
n3.next = NULL;
printf("%d\n", (*(n1.next)).data);
}
n1 の中にある next がn2を指して(&n2はn2へのポインタなので)つながり、n2.next は n3 へ、そしてn3からは NULL で、終了となっている。
このため (*(n1.next)).dataは、n1 しか使わないが n2.data を意味として表している。
クイズ
n3.data と同じ意味の表現を n1 を使って表してみよう
答え (*((*(n1.next)).next)).data
先頭の n1 からはじめて、途中の n2, n3 の名前を使わずにデータのアクセスができるところがリンクの特徴である。これは言い換えると、プログラム中では先頭のポインタだけを管理すればいいという意味になる。
しかし、カッコが多くなりとても分かりずらいので、これを簡単に記述する記法 -> がC言語にはある。
ポインタの指す変数の中身、という意味である。
構造体へのポインタ -> 構造体メンバ と書くことができる
code:list2.c
int main(void){
Node n1, n2, n3;
n1.data = 1;
n1.next = &n2;
n2.data = 2;
n2.next = &n3;
n3.data = 3;
n3.next = NULL;
printf("%d\n", (&n1)->data);
printf("%d\n", (&n1)->next->data);
printf("%d\n", (&n1)->next->next->data);
}
(&n1)->data のうち(&n1)は、構造体変数n1へのポインタである。そして(&n1)->data はn1のメンバ data のことであり、つまり n1.data と同じ意味がある。(&n1)のところがポインタでなければならないのが -> 記法の特徴である。
(&n1)->next->dataの前半(&n1)->nextは、n1のメンバのnextでこれは構造体へのポインタである。(&n1)->nextがポインタで、その内容は n2 を指していることになっている。このため(&n1)->next->dataはポインタ(&n1)->nextの指す構造体 n2 のメンバdataのことである。表示すれば 2 であることが確認できる。
リストは、ノードが一列につながった形をしていて、これを Linked List とも呼ぶ。この一列のつながりでデータの保存をしているところは、配列とも似ている。
リストと配列の主な性質の違いを次の表にまとめる
table: リストと配列
リスト 配列
データアクセス シーケンシャル ランダム
挿入 簡単 困難
削除 簡単 困難（工夫はある）
検索 データが多くなると遅い 速い（工夫により）
データ個数の上限 後から実行中に増やせる 事前に決めた個数しか使えない
使い方 すこし面倒 簡単
データアクセスがシーケンシャルである、というのは、一個目から順番にたどらなければならない、という意味である。
ランダムなデータアクセスとは、添字の番号を指定すれば、すぐにそのデータを取り出すことができることである。
これらの性質から、動作中にデータが増える場合や、データの挿入や削除が頻繁にあるようなデータを扱うときには、リストが用いられる。ワードプロセッサ、エディタは、こうした性質があるのでたいていはリストで実装されている。
リストをつないでみよう
code:list2-2.c
typedef struct Node{
int data;
struct Node * next;
} Node;
Node * node_new();
void node_print(Node * np);
int main(void){
Node *np, *l;
np = node_new();
np->data = 1; // 一つ目のデータだけ、2個め以降と扱いが違う気がする
l = node_new();
l->data = 2;
np->next = l;
l = node_new();
l->data = 3;
np->next->next = l; // もっといい方法はないだろうか
l = node_new();
l->data = 4;
np->next->next->next = l; // もっともっといい方法はないだろうか
node_print(np);
}
Node * node_new(){
Node *l;
l = malloc(sizeof(Node)); // 新しいノードを作成してメモリを確保する。名前はなくポインタで識別する。
l->data = 0;
l->next = NULL;
return l; // 新しいノードのポインタを返す。
}
void node_print(Node * np){
while(1){
if(np == NULL) break;
printf("%d -> ", np->data);
np = np->next; // ここ重要
}
printf("\n");
}
クイズ
ノード一つ目だけ変数名が異なり、扱いが違う。
これは、一個目が「1個目のノード」という意味と、「リストの代表」という意味の二つの意味を持っているから。
代表を別の変数にすれば、一個目からすべて同じ扱いができるはず。どうしたらいいだろうか。
三番めのノードをつなぐとき np->next->next = l として next が多段になってしまっている。
この調子では100番めのノードは next を99回続けなければならない。もっといい方法はないだろうか。
やりたいことは、いつも「一つ前のノードのnextにつなぐ」だけである。node_print()を見てみよう。
クイズの方針で書き直すと次の list3.c のようになる。list2.c と見比べてみよう。
code:list3.c
typedef struct Node{
int data;
struct Node * next;
} Node;
Node * node_new();
void node_print(Node * np);
int main(void){
Node n, *l, *s;
s = &n; // header
l = node_new();
l->data = 1;
s->next = l;
s = s->next;
l = node_new();
l->data = 2;
s->next = l;
s = s->next;
l = node_new();
l->data = 3;
s->next = l;
s = s->next;
node_print(n.next);
}
Node * node_new(){
Node *l;
l = malloc(sizeof(Node));
l->data = 0;
l->next = NULL;
return l;
}
void node_print(Node * np){
while(1){
if(np == NULL) break;
printf("%d -> ", np->data);
np = np->next;
}
printf("\n");
}
リストの特徴はあらかじめ数を決めないデータを扱えるところにある。
たとえばlist4.cのように100個のデータを発生（繰り返し）のたびに保存することができる。
code:list4.c
typedef struct Node{
int data;
struct Node * next;
} Node;
Node * node_new();
void node_print(Node * np);
int main(void){
Node n, *l, *s;
int i;
s = &n; // header
for(i = 1; i<100; i++){
l = node_new();
l->data = i; // いろいろな i を代入
s->next = l;
s = s->next;
}
node_print(n.next);
}
Node * node_new(){
Node *l;
l = malloc(sizeof(Node));
l->data = 0;
l->next = NULL;
return l;
}
void node_print(Node * np){
while(1){
if(np == NULL) break;
printf("%d -> ", np->data);
np = np->next;
}
printf("\n");
}
この例では、ヘッダー（最初の一個の前、リストの代表）として名前 n のあるノードを使っているが mallocで確保した名前のないノードを使うことが多い。
リストの基礎の演習（2問）
1) 1から9までを二周もつようなリストを作って表示しよう。
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 というようなリストである
2) list.4のノードは整数 int を data として持っている。
一文字を data として持つ Node に変更して、aからzまでをリストにつないで表示しよう
参考 : aからzまでの文字を表示するプログラムの断片
code: a2z.c
char data;
for(data='a'; data<='z'; data++){
printf("%c -> ", data);
}
printf("\n");
リストの演習（ここ）