演習課題「ノードをつなげよう」
右のコードエリアには、連結リストのデータを順番に出力するためのコードが用意されています。
ノードを正しくつなげて、各データが小さい順に出力されるようにしてください。
プログラムを実行して、正しく表示されれば演習課題クリアです！
期待する出力値
1
2
3
＃08:連結リストを実装しよう (1)
連結リストのつくり方と使い方を学習します。自己参照構造体について理解しましょう。
構造体のメンバに、自身の構造体へのポインタを持つ構造体は「自己参照構造体」と呼ばれます。struct node {
int num;
struct node *next; // 自身の構造体へのポインタ
}
自己参照構造体は、連結リストなどのデータ構造を新たに作成したい場合によく使われます。
構造体を次のように宣言しようとすると、エラーになります。typedef struct {
int num;
Node *next; // typedef で定義した Node 型をその場で使うとエラーになる
} Node;
構造体のメンバを宣言する時点で、Node 型が定義されていないので、エラーになってしまいます。
○ typedef を使う場合には、次のようにする必要があります。typedef struct node {
int num;
struct node *next;
} Node;
※ または、次のようにすることも可能です。struct node {
int num;
struct node *next;
};
typedef struct node Node;
構造体から宣言した変数は、連結リストのノードとして使用できます。#include <stdio.h>
typedef struct node {
int num;
struct node *next;
} Node;
int main(void)
{
// ノードを宣言する
Node node1 = {5, NULL};
Node node2 = {9, NULL};
Node node3 = {3, NULL};
Node node4 = {7, NULL};
}
メンバの next には NULL を代入しています。
NULL は「何もない」ことを表す特別なポインタで、ノードがつながっていないことを表すときにも使われます。
各ノードをつなげるには、次のように記述します。#include <stdio.h>
typedef struct node {
int num;
struct node *next;
} Node;
int main(void)
{
Node node1 = {5, NULL};
Node node2 = {9, NULL};
Node node3 = {3, NULL};
Node node4 = {7, NULL};
node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
}
構造体のメンバの next に、次のノードのアドレスを代入しています。
各ノードのデータを出力するには、次のように記述します。Node *p = &node1;
while (p != NULL) {
printf("%d\n", p->num);
p = p->next;
}
p の指し示すノードが node1 => node2 => node3 => node4 と移り変わっていって、順番に num の値を出力します。
【動作を理解するために重要なところ】
ポインタ p を以下のようにしたとき、p = &node1;
○ 以下の 2 つは同じものを表しますp->num; // アロー演算子を使わなければ、(*p).num
node1.num;
○ 以下の 2 つも同じものを表しますp->next; // アロー演算子を使わなければ、(*p).next
node1.next;
// 連結リストを実装しよう (1)
#include <stdio.h>
typedef struct node {
int num;
struct node *next;
} Node;
int main(void)
{
Node node1 = {5, NULL};
Node node2 = {9, NULL};
Node node3 = {3, NULL};
Node node4 = {7, NULL};
node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
Node *p = &node1;
while (p != NULL) {
printf("%d\n", p->num);
p = p->next;
}
}
次のように、node4 を node1 につなげると循環リストになってしまい、while の処理が終了しなくなってしまいます。#include <stdio.h>
typedef struct node {
int num;
struct node *next;
} Node;
int main(void)
{
Node node1 = {5, NULL};
Node node2 = {9, NULL};
Node node3 = {3, NULL};
Node node4 = {7, NULL};
node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
node4.next = &node1; // node4 を node1 につなげる
Node *p = &node1;
while (p != NULL) {
printf("%d\n", p->num);
p = p->next;
}
}
出力例5
9
3
7
5
9
3
7
5
9
3
7
...
ノードをつなぐ処理を書く際には注意が必要です。
自己参照構造体 - 初心者のためのポイント学習 C 言語
http://www9.plala.or.jp/sgwr-t/c/sec15-5.html
第31回 データ構造(10)～構造体をポインタでつなぐ - もう一度基礎から C 言語
https://www.grapecity.com/developer/support/powernews/column/clang/031/page02.htm