こんばんは･:*+.\( °ω° )/.:+
バーチャル高専女子、まふゆです！
今回は久々にC言語を扱った記事になります。
最近、フォロワーさんから「C言語のリスト構造が理解できないから説明して！」っていう依頼がよく来るんだよね。
今回はそんな皆さんの期待に応えるべく、リスト構造を分かりやすく解説するよ！！
ちなみに、今回解説するのは「片方向の線形リスト」のみになります。
これが一番カンタンで、リスト構造の考え方の基本になるものだからね。
■ 本記事の対象読者
・学校の授業で自己参照構造体のリスト構造を習ったけど、全然理解できない！！
・リスト構造とか以前に、そもそも構造体がよくわからない！！
といった人向けの内容になります。
■ コードの実行環境
・OS：Windows 10
・開発環境：Visual Studio 2017
いつも通り！
■ 注意！！
わかりやすさを重視しているので、ちょっぴり正確性に欠ける内容があるかもしれません…
あと、スマホ版のレイアウトでは若干ソースコードの表示が崩れるから、
PC版での閲覧を推奨します！
スマホのWebブラウザの設定に『PC版サイトを表示』みたいなやつがあるはずなので、それを選択してね。
スポンサーリンク
■ まずは構造体についての解説。
一番最初に、"構造体"について説明しようか。
知っている人は飛ばしてもOKです。
構造体っていうのは、複数の変数をまとめて、1つの型として扱うときに使うものです。
たとえば"名前"と"学籍番号"を持った、"学生"を表す構造体を定義するときは、こんな書き方をするよ。
struct student { char name[20]; // 名前 int id; // 学籍番号 };
structは"これは構造体ですよ！"っていう意味で、構造体を定義するときには必ず必要なもの。
後ろにあるstudentは、構造体の"タグ名"です。これは好きな名前を付けられます。
そして、{}の中に、構造体に入れたい変数を必要な分だけ宣言します。
これらの変数のことを、"構造体のメンバ変数"、あるいは単に"構造体のメンバ"と呼ぶから覚えておいてね。
今回の場合はchar型配列の"name"と、int型の"id"が、student構造体のメンバになるね。
あと、閉じカッコの後ろのセミコロンを忘れるとコンパイルエラーになるから、気をつけてね！(私もよく付け忘れます...)
構造体を使ったコードの例を、以下に示すよ。
#include <stdio.h> #include <string.h> struct student { char name[20]; // 名前 int id; // 学籍番号 }; int main(void) { struct student mafuyu; // (1) strcpy(mafuyu.name, "Mafuyu Nanase\0"); mafuyu.id = 810; printf("%sさんの学籍番号は、%dです。\n", mafuyu.name, mafuyu.id); // (2) return 0; }
上記コードの(1)に注目！！
定義した構造体を実際に使える形で宣言するときは、"struct タグ名"を使って宣言を行うよ。
このようにして宣言されたものを、"構造体変数"と呼びます。
構造体変数を宣言するときも、通常の変数と同じように任意の名前を付けます。
つまり、"struct student型"の"mafuyu"を宣言してるわけだね。
そして(2)。
名前と学籍番号をprintfで表示しているんですが、参照している変数名に注目してみよう。
名前 → mafuyu.name
学籍番号 → mafuyu.id
このように、構造体のメンバ変数にアクセスする際には、".(ピリオド)"を使います。
で、このピリオドのことをドット演算子って呼びます。
「構造体変数名.メンバ変数名」という形だね。
これは基本中の基本なので、絶対に覚えておいてください！！
一応コードの実行結果も載せておくね。
■ 構造体の「型」を定義しましょう。
ところで、さっきのコード。
構造体変数を宣言するときに、
struct student mafuyu;
という書き方をしていたよね。
この書き方、コードが冗長になってしまうので、プロの人にはあまり好まれません。
「struct student」のように2語じゃなくて、「int」「float」「char」みたいに1語で書いたほうがスマートです。
そのためにはまず、構造体の定義のしかたををちょっと変える必要があるよ。
以下は、変更前のコード。
struct student { char name[20]; // 名前 int id; // 学籍番号 };
そして、以下が構造体の型を1語で描けるように変更したコード。
typedef struct student { char name[20]; // 名前 int id; // 学籍番号 } STUDENT;
最初に"typedef"が付いてるね。
これは、"今から型を定義するぜ！！"という意味です。
そして、最後に"STUDENT"が付いてるね。
これが"型名"です。
今回の場合、"student"が"タグ名"、"STUDENT"が"型名"になります。
型名もタグ名と同じように、任意の名前を指定できるよ。
こういうふうに構造体を定義すると、
STUDENT mafuyu;
というふうに構造体変数を宣言できます。
もちろん、タグ名も定義されているので
struct student mafuyu;
と書くことも可能です。
ちなみに、
struct STUDENT mafuyu;
っていう書き方はダメです。エラーになります。
「なんで型名が全部大文字なんだ？」って思った人もいるかと思いますが、これは単なる私のクセというか、私の中のコーディングルールです。小文字でもちゃんと動作します。
私が"typedef enum"とか"typedef struct"とかで新しい型を定義するときは、全て大文字で定義することにしているよ。単語の区切りには、アンダースコア(_)を使います。
こうすることで、プリミティブな型(intとかfloatとかcharとか、最初から定義されている型)との区別がパッと見でできる、というメリットがあります。
言い換えると、「あ、コレは私が作った型だな」っていうのが一目でわかるってこと。
メリットと感じるかどうかはその人次第なので、真似しても真似しなくてもいいです。
まぁそれは割とどうでもよくって、ここで私が一番言いたいのは「構造体を定義するときは、typedefで型名を定義したほうがスマートだよ！！」ってことです。
スポンサーリンク
■ 自己参照構造体について。
ここから先は、"ポインタ"についての知識をある程度持っていると、スムーズに理解できるよ。
できれば、以下のポインタ解説記事を先に読んでおいてほしいな…
読まなくても理解できるような書き方をするつもりだけど、一応ね。
さて、ようやく今回の記事のミソである「自己参照構造体」の解説に入ります。
自己参照構造体とは、「自身の構造体のポインタ型変数」を持った構造体です。
なんか難しそうだね！！
言葉で書くと難しく感じてしまうので、実際にコードを見てもらいましょう。
簡単だから安心してください。
まずは、普通の構造体。自己参照構造体ではありません。
typedef struct student { char name[20]; // 名前 int id; // 学籍番号 } STUDENT;
これを自己参照構造体にすると、以下のようになります。
typedef struct student { char name[20]; // 名前 int id; // 学籍番号 struct student *next; // 次のデータがある場所 } STUDENT;
nextっていう、struct studentのポインタ型のメンバ変数が増えています。
"ポインタ"は"アドレス"のことだって、ポインタ解説記事で説明したよね。
アドレスは要するに、メモリ上の番地(場所)のこと。
つまり、"次のデータが存在する場所"を格納するのがnextです。
いいですか？大事なことだからもう一回言うよ。
nextには、"次のデータが存在する場所"を格納します！！
場所だよ、場所。
nextには、「XXXXXX番地」みたいな感じで、"場所を示す値"が入るんだよ。
なおこのとき、構造体のメンバとして構造体のポインタ型変数を宣言するには、structとタグ名を使って
struct student *next;
という書き方をしてください。
この段階ではまだSTUDENT型は定義されていないので、
STUDENT *next;
という書き方をすることはできません。
■ 「片方向の線形リスト」をイメージしてみよう。
そもそも「リスト」ってなんだ？？って思っている人もいるかもしれませんが、あまり難しく考えてはいけません。
要するに、「複数のデータが繋がったもの」って考えれば大体OKです。
「自己参照構造体」を使った「片方向の線形リスト」について、図を使って説明してみるよ。
まず、自己参照構造体ではない普通の構造体。
typedef struct student { char name[20]; // 名前 int id; // 学籍番号 } STUDENT;
図で表すと、こんなイメージだね。
これを自己参照構造体にします。
typedef struct student { char name[20]; // 名前 int id; // 学籍番号 struct student *next; // 次のデータがある場所 } STUDENT;
さっきと同じように図で表すと、こんな感じです。
自己参照構造体には、「next」がついてます。
nextは、「次のデータがある場所」を示していることはさっき説明したね。
これがあると、「片方向の線形リスト」が実装できます！！
教科書とかでは、こんな感じで例が示されているんじゃないかな。
このリスト、4つの要素(STUDENT型の構造体変数)で構成されているよね。
リストを構成するこれら一つ一つの要素を、"ノード"と呼びます。
つまり、「このリストは4つのノードで構成されている」わけです。
このタイプのリストは、各ノードが「次のデータの場所」の情報を持っていますが、「前のデータの場所」の情報は持っていません。
なので、「片方向」のリストと呼ばれます。
リストの一番最後データのnextには"NULL"をセットすることで、「一番最後の要素であること」を表現できるよ。
あと、なぜ「線形」リストと呼ばれているかというと、一次元の「線」のように、先頭～末尾までが一本道になっているからです。
ちなみに、各ノードが「次のデータの場所(next)」「一つ前のデータの場所(prev)」の2つを持っていれば、「双方向」のリストになるよ。
「双方向のリスト」については今回は解説しません。
さっきの「片方向の線形リスト」の図、もうちょっと分かりやすい形に変えてみましょう。
・STUDENT型のノードを4つ生成。
・各ノードのname、idに具体的な数値を入れる。
・それらを繋いで、片方向の線形リスト構造にする。
上記3点の操作を行った結果がこちら。
各ノードのnextの値に注目！！
ここには、次のデータのアドレス(番地)が入っていることがわかると思います。
こういうふうにして、次のデータがある場所を把握しているんだよ。
それぞれのノードは全てPCのメモリ上に存在しているのですが、これらが存在する場所はコンピュータさんが勝手に決めるので、バラバラです。
上のイメージ図でも、めちゃくちゃな数値になっているよね。
各ノードがバラバラの場所に存在していても、こんな感じで「次のノードがある場所」をnextにセットすることで、連なったデータとして扱うことができるんです。
リスト構造のイメージ、固まってきたかな？
■ 実装してみましょう。
さっきのイメージ図を、そのまま実装してみましょう。
以下のコードを見てね。
ちょっと頭の悪いコードだけど、リスト構造の初学者さんにはわかりやすい内容になっていると思います。
(C言語マスターの人はいろいろツッコみたくなる内容かもしれないけど、我慢してね♡)
#include <stdio.h> #include <string.h> // 自己参照構造体の「STUDENT型」を定義！ typedef struct student { char name[20]; // 名前 int id; // 学籍番号 struct student *next; // 次のデータがある場所 } STUDENT; STUDENT createStudent(char *studentName, int studentId); int main(void) { // STUDENT型のポインタ。現在の「場所」を表すよ。 STUDENT *current; // 4件のノードを生成。(1) // この時点では、まだリスト構造になっていません。 STUDENT student1 = createStudent("内田真礼\0", 1); STUDENT student2 = createStudent("佐倉綾音\0", 2); STUDENT student3 = createStudent("種田梨沙\0", 3); STUDENT student4 = createStudent("水瀬いのり\0", 4); // 各ノードについて、「次の場所」をセット。 // ここでリスト構造になります。(2) student1.next = &student2; student2.next = &student3; student3.next = &student4; student4.next = NULL; // whileループを使って、リスト内の全データを表示するよ。(3) // 「現在の場所」に、リスト先頭の「student1」の場所をセット！ current = &student1; while (1) { printf("学籍番号 : %d\n", current->id); printf("名前 : %s\n", current->name); printf("自身のノードの場所 : %d\n", current); printf("次のノードの場所 : %d\n", current->next); printf("------------------------------------------------------\n"); if (current->next != NULL) { // 次の場所がNULLではない、つまり次のデータがある。 // 「現在の場所」を次の場所に移動します。 current = current->next; } else { // 次の場所がNULLなら、現在の場所はリストの末尾。 // もう次のデータはないので、breakでループ終了。 printf("最後まで表示したよ！！\n\n"); break; } } return 0; } // 新しいノードを生成する関数。 STUDENT createStudent(char *studentName, int studentId) { STUDENT newStudent; // 新しいSTUDENT型変数に、nameとidをセットして返す。 strcpy(newStudent.name, studentName); newStudent.id = studentId; return newStudent; }
実行結果はこちら。
各ノードについて、
・学籍番号
・名前
・自身のノードの場所
・次のノードの場所
を順番に表示してるね。
これらのノードはリスト構造になっているので、「次のデータの場所」を辿っていくことで、このように順番に表示することができます。
さっきのコードはちょっぴり長いので、少しずつ分解して解説するね。
■ ノードを生成して、繋ぎましょう。
まずは、上記コード内の(1)。
// 4件のノードを生成。(1) // この時点では、まだリスト構造になっていません。 STUDENT student1 = createStudent("内田真礼\0", 1); STUDENT student2 = createStudent("佐倉綾音\0", 2); STUDENT student3 = createStudent("種田梨沙\0", 3); STUDENT student4 = createStudent("水瀬いのり\0", 4);
STUDENT型のノードを4件生成しています。
これら4つのノードを使ってリスト構造を実現するわけですが、この時点では各ノードのnextに値がセットされていません。
すなわち、これらのノードはメモリ上のバラバラの場所に存在しており、繋がっていない状態です。
続いて(2)。
// 各ノードについて、「次の場所」をセット。 // ここでリスト構造になります。(2) student1.next = &student2; student2.next = &student3; student3.next = &student4; student4.next = NULL;
各ノードのnextに、「次のノードの場所」がセットされているね。
nextはポインタなので、「&student2」「&student3」「&student4」といったように、「&」を使ってアドレスをセットします。
こうすることで、「student2さんはこの場所にあるよ！」「student3さんはこの場所にあるよ！」といった情報を、各ノードのnextにセットできます。
student4は一番最後のノードなので、nextにNULLをセットしよう。
こうすることで、student4が最後のノードであることを判別できるようになります。
■ 先頭から、順番にデータを表示しよう。
次に(3)。
ループ処理で、リスト内のデータを全て画面表示します。
// whileループを使って、リスト内の全データを表示するよ。(3) // 「現在の場所」に、リスト先頭の「student1」の場所をセット！ current = &student1; while (1) { printf("学籍番号 : %d\n", current->id); printf("名前 : %s\n", current->name); printf("自身のノードの場所 : %d\n", current); printf("次のノードの場所 : %d\n", current->next); printf("------------------------------------------------------\n"); if (current->next != NULL) { // 次の場所がNULLではない、つまり次のデータがある。 // 「現在の場所」を次の場所に移動します。 current = current->next; } else { // 次の場所がNULLなら、現在の場所はリストの末尾。 // もう次のデータはないので、breakでループ終了。 printf("最後まで表示したよ！！\n\n"); break; } }
whileループの中を見てほしいんだけど、
「student1」「student2」「student3」といった、各ノードの名前が一度も使われていないよね。
そのかわりに、"current"というものが使われています。
currentは「STUDENTのポインタ型」です。
main関数の冒頭で宣言しています。
これを使って、「現在表示すべきノードの場所」を表現することができます。
最初に表示するのは、リストの先頭であるstudent1だよね。
なので、ループに入る前に、currentの初期位置としてstudent1がある場所を示す「&student1」をセットします。
そして、現在のノード(current)における学籍番号や名前などの情報を出力します。
そのあと、次のノードがあるなら、currentを次のノードへと更新します。
次のノードがなければ、breakでループを終了するよ。
スポンサーリンク
■ アロー演算子について。
最後にちょっと補足。
whileループ内の処理で、見慣れない記号がでてきたのに気づいたかな？
構造体のメンバ変数にアクセスするために、"->"という記号が使われています。
printf("学籍番号 : %d\n", current->id); printf("名前 : %s\n",current->name); printf("自身のノードの場所 : %d\n", current); printf("次のノードの場所 : %d\n", current->next);
if (current->next != NULL) { // 次の場所がNULLではない、つまり次のデータがある。 // 「現在の場所」を次の場所に移動します。 current = current->next; }
さっき、idやnameといった構造体のメンバ変数にアクセスするには、".(ドット演算子)"を使うって説明したよね。
それなのに、このコードでは"->"という記号が使われているね。
ちなみに、この記号は矢印に見えるので、"アロー演算子"と呼ばれます。
これはC言語のちょっと難しい仕様なんだけど、
・構造体変数のメンバへのアクセスには、ドット演算子を使う。
・構造体変数のポインタからメンバにアクセスするには、アロー演算子を使う。
っていう決まりがあります！めんどくさいね！！！
そういう決まりなので、これは覚えるしかありません。
具体的な例を示すと、
・"STUDENT student;"として宣言されたなら、idにアクセスするときの表記は"student.id"になる。
・"STUDENT *student;"として宣言されたなら、idにアクセスするときの表記は"student->id"になる。
ということになります。
■ まとめ
・「リスト」っていうのは、要するに「複数のデータが繋がったもの」だよ！
・リストを構成するひとつひとつのデータのことを、「ノード」と呼ぶよ！
・"次のノードの場所"のような情報をメンバ変数として持った構造体を、「自己参照構造体」と呼ぶよ！
・自己参照構造体を繋げると、「リスト構造」が実現できるよ！
・「リスト構造」を使うと、「次のノードの場所」を辿っていくことで、順番にノードにアクセスできるよ！
・構造体変数のメンバへのアクセスには、ドット演算子(.)を使うよ！
・構造体変数のポインタからメンバにアクセスするには、アロー演算子(->)を使うよ！
ちょっと多いけど、これらは全部大切なことなので、しっかりと覚えておいてね！！
ちなみに今回の記事で紹介したコードなんですが、実は"リスト構造"のメリットをほとんど活かせていません。
リスト構造には、
・新しいノードを、ユーザの操作によって任意の場所に追加することができる！
・不要なノードを、ユーザの操作によって削除することができる！
というおいしいメリットがあるんだけど、今回はそこには触れませんでした。
これらについては、中編・後編でしっかり解説する予定だからちょっと待っててね！！
ではでは～･:*+.\( °ω° )/.:+
続きはこちら。
mafuyu7se.hatenablog.com
