まふゆちゃんの技術ブログ。

情報系の高校生・高専生・大学生を全力で応援するブログです。

【C言語】よくわかる構造体とリスト構造。(中編)

f:id:Mafuyu7se:20181229193313p:plain
こんばんは・:*+.\( °ω° )/.:+
バーチャル高専女子、まふゆです!
今回はリスト構造解説記事の中編だよ!!
前編書いてからかなり時間が開いてしまったなぁ… ごめんね。

今回の記事では、リストへノードを動的に追加する方法を解説していきます。

前編の内容をしっかり把握している人向けの内容になるので、自信のない人はもう一度読んできてね!!

mafuyu7se.hatenablog.com

■ 本記事の対象読者

前編を読んだよ!!
・「自己参照構造体」と、「片方向の線形リスト」についてだいたい理解できてるよ!!

といった人向けの内容になります。

■ コードの実行環境

・OS:Windows 10
・開発環境:Visual Studio 2017

いつも通り!

■ 注意!!

わかりやすさを重視しているので、ちょっぴり正確性に欠ける内容があるかもしれません…

あと、スマホ版のレイアウトでは若干ソースコードの表示が崩れるから、
PC版での閲覧を推奨します!

スマホのWebブラウザの設定に『PC版サイトを表示』みたいなやつがあるはずなので、それを選択してね。


スポンサーリンク



■ 前回の復習。

前編で、こんな感じの片方向の線形リストを実装したよね。
f:id:Mafuyu7se:20181215232031p:plain
f:id:Mafuyu7se:20181220224642p:plain

コードと実行結果をもう一度載せます。

#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;
}

f:id:Mafuyu7se:20181216190138p:plain

一言で説明すると、ノードを4件繋いでリストを作り、先頭から順番に辿ってデータを画面表示する、という処理です。
前編のまとめでちょっと説明しましたが、このコードはハッキリ言ってリスト構造のメリットを全く活かせていません

わざわざリスト構造にしなくても、STUDENT型の配列(要素数4つ)を宣言して、forループで配列の要素番号[0]~[3]までの4つを出力すればいいよね?

■ じゃあリスト構造を使うメリットって何だよ!

リスト構造を使うメリットとして、
・リスト内の任意の場所に、ノードを追加することができる!
・リスト内の任意のノードを削除することができる!

この2点が挙げられます!!

例をあげて説明しようか。
たとえば、リスト構造を使わずに「要素数4つの配列を宣言してforループで表示する」場合。
以下のようなコードになるよね。

#include <stdio.h>
#include <string.h>

typedef struct student
{
    char name[20];         // 名前
    int id;                // 学籍番号
    struct student *next;  // 次のデータがある場所(使いません)
} STUDENT;

int main(void)
{
    STUDENT students[4];
    int i;

    strcpy(students[0].name, "内田真礼\0");
    students[0].id = 1;

    strcpy(students[1].name, "佐倉綾音\0");
    students[1].id = 2;

    strcpy(students[2].name, "種田梨沙\0");
    students[2].id = 3;

    strcpy(students[3].name, "水瀬いのり\0");
    students[3].id = 4;

    for (i = 0; i < 4; i++)
    {
        printf("学籍番号 : %d\n", students[i].id);
        printf("名前     : %s\n", students[i].name);
        printf("------------------------------------------------------\n");
    }

    return 0;
}

f:id:Mafuyu7se:20181228223959p:plain

当然ですが、このコードでは4件のデータしか扱うことができません。
配列の要素が4個しかないんだから、当然だよね。
プログラムが動き出してから「データをあと1個追加したい!」「このデータを削除したい!」とか思っても、どうしようもありません。

ここで、リスト構造さんの出番です。
配列ではなくリスト構造を使用すれば、プログラムが動き出してから、ユーザの操作によって好きな場所に新しくノードを追加したり、不要なノードを削除したりすることが可能です!!

今回は、「ノードの追加」に焦点を当てて解説するよ。
(「ノードの削除」については後編で説明します…)


スポンサーリンク



■ 登場人物を覚えましょう。

リストへのノードの追加や削除を実装する際に、必ず登場する人がいます。

それは、
・リストの先頭のノードの場所を示す「head(ヘッド)」さん。
・リストの末尾のノードの場所を示す「tail(テール)」さん。
これら2人です。

headとtailは、ノードの存在する「場所」、つまりアドレスを示すもの。
なので、変数の型は「自己参照構造体のポインタ型」になります。

ノードの型がSTUDENT型の場合、STUDENTのポインタ型になるので、

STUDENT *head;
STUDENT *tail;

というふうに宣言するよ。

headとtailのイメージはこんな感じ。
f:id:Mafuyu7se:20181230221743p:plain

headとtailはポインタなので、ノードが存在する「アドレス」が入ります。
上記画像の場合、headには"114514"が、tailには"991542"が入ることになるね。

このとき、head/tailは、アロー演算子(->)を使って、自身のメンバ変数にアクセスできます

例えば、
printf("%d %s %d", head->id, head->name, head->next);
とした場合、
1 内田真礼 334521
というふうに表示することができるよ。

このheadとtail、リスト構造を実装する上でとっても重要な役割を持っているので、しっかりイメージを掴んでから次に進んでね。

■ 「ノードの追加」をやってみよう。

リスト内に新しいノードを追加する方法を解説していくよ。

リスト構造では、「リスト内の好きな場所」にノードを追加することができます。
だけど、まず最初は「リストの末尾にノードを追加する方法」のみを解説します。

とりあえず、以下のコードをコピペして実行してみてね。
現段階ではコードの内容を理解する必要はありません。
後から説明するので、とりあえず動かしてみましょう。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

typedef struct student
{
    char name[20];         // 名前
    int id;                // 学籍番号
    struct student *next;  // 次のデータがある場所
} STUDENT;

STUDENT *head = NULL; // リストの先頭
STUDENT *tail = NULL; // リストの末尾

STUDENT *createNode(void);
void addNodeToList(void);
void printList(void);

int main(void)
{
    char input;
    char command;

    while (1)
    {
        printf("-------------操作方法-------------\n");
        printf("A : リストの末尾にノードを追加します。\n");
        printf("P : リスト内のノードを全て表示します。\n");
        printf("コマンドを入力してください:");

        // 入力されたアルファベットをtoupperで大文字に変換。
        // switch文の判定にアルファベットの大文字を使うため。
        scanf("%s", &input);
        command = toupper(input);

        switch (command)
        {
            case 'A':
                addNodeToList(); // リスト末尾にノード追加。
                break;

            case 'P':
                printList(); // リストの内容を画面表示。
                break;

            default:
                printf("無効なコマンドです。\n");
                break;
        }

        printf("\n");
    }

    return 0;
}

// ノードを生成する関数。
STUDENT *createNode(void)
{
    // 新しいノード1個分のメモリを確保し、その場所を返します。
    STUDENT *newNodePos;
    newNodePos = (STUDENT *)malloc(sizeof(STUDENT));

    return newNodePos;
}

// リストの末尾にノードを追加する関数。
void addNodeToList(void)
{
    STUDENT *newNodePos;
    int inputId;
    char inputName[20];

    // 新しいノードを作成。(1)
    newNodePos = createNode();

    printf("学籍番号を入力:");
    scanf("%d", &inputId);
    newNodePos->id = inputId;

    printf("名前を入力:");
    scanf("%s", inputName);
    strcpy(newNodePos->name, inputName);

    if ((head == NULL) && (tail == NULL))
    {
        // リストが空の場合はこちら。
        // 新しいノードが、先頭かつ末尾になる。
        head = newNodePos;
        tail = newNodePos;
    }
    else
    {
        // リストに1件以上ノードが存在する場合はこちら。
        // 末尾ノード(tail)のnextに、新しいノードの場所をセット。
        tail->next = newNodePos;

        // 追加した新しいノードをtailとする。
        tail = newNodePos;
    }

    // 次のデータは無いので、nextにはNULLをセット。
    tail ->next = NULL;

    printf("ノードを追加しました。\n");
}

// リストの内容を全て表示する関数。
void printList(void)
{
    STUDENT *current;

    if ((head == NULL) && (tail == NULL))
    {
        // 表示するものがない場合は何もせずにreturn。
        printf("リストは空です。\n");
        return;
    }

    // 先頭から表示するので、現在の位置をheadにセット。
    current = head;

    printf("----------------------------------\n");

    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");
            break;
        }
    }
}

main関数でユーザからのコマンド入力を待機し、入力されたアルファベットに応じた処理を行います。
'A'を入力:リストへノードを追加。
'P'を入力:リストの内容を全て表示。

といった感じ。

操作例を以下に示すよ。
Aコマンドで、ノードを4件追加。
f:id:Mafuyu7se:20181229022603p:plain

その後に、Pコマンドでリスト内のノードを全て表示。
f:id:Mafuyu7se:20181229022432p:plain

こんな感じで、好きなだけノードを追加することができます。
学籍番号と名前には自由な値を入れてOKです。
好きな数字や、自分の名前なんかを入力して遊んでみましょう。

では、コードの解説に入ります。
main関数とprintList関数については解説不要だと思うので、
・createNode関数
・addNodeToList関数

上記2点の関数について、説明します!!

■ createNode関数

名前の通り、ノードを生成する関数です。

// ノードを生成する関数。
STUDENT *createNode(void)
{
    // 新しいノード1個分のメモリを確保し、その場所を返します。
    STUDENT *newNodePos;
    newNodePos = (STUDENT *)malloc(sizeof(STUDENT));

    return newNodePos;
}

この関数の戻り値は、「STUDENTのポインタ型」です。

createNodeさんの仕事は、
・メモリからノード1個分の領域を確保する。
・確保した領域の場所を返す。

上記2点になります。
「ノード1個作ったで~!!場所はここな!!」みたいなイメージだね。

で、この関数内で1番のポイントは、"malloc"という関数。
これは"マロック"または"エムアロック"と読みます。
指定したサイズのメモリを確保するときに使う関数だよ。

例えば、
malloc(16);
ならば、16バイト確保。

malloc(sizeof(int));
ならば、int型変数1個分のサイズ(私の環境では4バイト)を確保。
といった具合です。

今回の例では
malloc(sizeof(STUDENT));
になっているよね。

STUDENT型の定義は以下の通り。

typedef struct student
{
    char name[20];         // 1 x 20 = 20バイト
    int id;                // 4バイト
    struct student *next;  // ポインタ型なので、4バイト
} STUDENT;

20 + 4 + 4 = 合計28バイトだね。
したがって、28バイト確保されることになります。

で、確保した領域をSTUDENT型として扱ってもらうために、以下のようにキャスト(型変換)を行っています。

newNodePos = (STUDENT *)malloc(sizeof(STUDENT));

mallocで確保した領域は「型のないただの28バイトの空間」なので、STUDENT型ではありません。
従って、こういうふうにキャストを行うことで、STUDENT型として扱うことができるようになります。
処理系によってはキャストしなくても大丈夫かもしれないけど、私の環境ではキャストしないとコンパイルエラーになりました。

■ addNodeToList関数

新しいノードを作り、それをリストの末尾に追加する関数です。

// リストの末尾にノードを追加する関数。
void addNodeToList(void)
{
    STUDENT *newNodePos;
    int inputId;
    char inputName[20];

    // 新しいノードを作成。(1)
    newNodePos = createNode();

    printf("学籍番号を入力:");
    scanf("%d", &inputId);
    newNodePos->id = inputId;

    printf("名前を入力:");
    scanf("%s", inputName);
    strcpy(newNodePos->name, inputName);

    if ((head == NULL) && (tail == NULL))
    {
        // リストが空の場合はこちら。
        // 新しいノードが、先頭かつ末尾になる。(2)
        head = newNodePos;
        tail = newNodePos;
    }
    else
    {
        // リストに1件以上ノードが存在する場合はこちら。
        // 末尾ノード(tail)のnextに、新しいノードの場所をセット。(3)
        tail->next = newNodePos;

        // 追加した新しいノードをtailとする。(4)
        tail = newNodePos;
    }

    // 次のデータは無いので、nextにはNULLをセット。(5)
    tail ->next = NULL;

    printf("ノードを追加しました。\n");
}

まず、コード内の(1)。
さっき説明したcreateNode関数を使って、新しいノードを生成します。
newNodePos には、新しいノードのアドレスが格納されます。

で、その後にscanfで入力された学籍番号と名前を、新しいノードにセットするよ。
newNodePosはポインタなので、メンバへのアクセスにはアロー演算子(->)を使用します。

続いて(2)。
headとtailが初期値(NULL)の場合、「リストが空である」ことを意味します。
最初の1回目は必ずここを通ることになるのは理解できるよね。
このとき新しく生成されたノードが、リスト内に存在する「唯一のノード」になるので、head(先頭)とtail(末尾)の両方にnewNodePosがセットされます。
ノードが1個しかないのだから、先頭と末尾が同じ場所になるのは当然だよね。

次に(3)。
最初の1回目ではリストが空なので(2)を通りますが、2回目以降はこちらを通ります。
tailのnextにnewNodePosをセットしてるね。
すなわち、一番後ろのノードの「次の場所」として、「新しいノードの場所」をセットしてるわけです。

この時点で、tailの後ろに新しいノードが追加されました。
従って、tailは「一番後ろのノード」ではなくなったわけだよね。
tailの後ろに追加された「新しいノード」の場所を、tailに設定すべきです。
なので、コード内の(4)でtailを更新してあげましょう。

最後に(5)。
「tailの後ろには何も存在しない」ことを示すために、NULLをセットして終了です。

以上が、リスト末尾にノードを追加するための処理になります。

「説明がちょっと分かりにくかった!!」という人は、以下の画像を見て処理の流れのイメージを掴んでください。
以下の4ステップを実施すれば、リスト末尾へのノード追加処理が実装できます。

STEP1:新しいノードを生成。
f:id:Mafuyu7se:20181229223555p:plain

STEP2:tailの「次の場所」に、「新しいノード」の場所をセットする。
f:id:Mafuyu7se:20181229223647p:plain

STEP3:「新しいノード」をtailとする。
f:id:Mafuyu7se:20181229223801p:plain

STEP4:tailの「次の場所」を「NULL」とする。
f:id:Mafuyu7se:20181229223908p:plain

図に書いて考えるとそこまで難しくないでしょ??


スポンサーリンク



■ 「好きな場所」にノードを追加するには?

addNodeToList関数では、リストの末尾にノードを追加したよね。

リスト構造を使えば、リストの末尾だけではなく「好きな場所」にノードを追加できるよ。
例えば、「田所浩二」さんを「佐倉綾音」さんと「種田梨沙」さんの間に挿入することも可能です。

任意の場所にノードを追加する機能を持った、insertNodeToList関数を作成しましょう。
挿入先のノードの"name"を入力して、一致するノードがあれば、その後ろに新しいノードを追加します。
コードは以下の通りです。

void insertNodeToList(void)
{
    char insertTargetName[20] = "";
    STUDENT *current, *temp, *newNodePos;

    int inputId;
    char inputName[20];

    printf("挿入先のノードのnameを入力してください。\n");
    printf("入力されたnameを持つノードの後ろに、新しいノードを挿入します。\n");
    scanf("%s", insertTargetName);

    // リストの先頭から、挿入先ノードを探します。
    current = head;
    while (current != NULL)
    {
        if (strcmp(current->name, insertTargetName) == 0)
        {
            printf("ノードが見つかりました。\n");
            break;
        }
        else
        {
            current = current->next;
        }
    }

    // 挿入先ノードが見つからなかったら、何もせずreturn。
    if (current == NULL)
    {
        printf("ノードが見つかりませんでした。\n");
        return;
    }

    // 新規ノードを作成。
    newNodePos = createNode();

    printf("学籍番号を入力:");
    scanf("%d", &inputId);
    newNodePos->id = inputId;

    printf("名前を入力:");
    scanf("%s", inputName);
    strcpy(newNodePos->name, inputName);

    // tempに、挿入先ノードの「1つ後ろのノード」の場所を一時記憶。(1)
    temp = current->next;

    // 挿入先ノードのnextに、新規ノードを追加。(2)
    current->next = newNodePos;

    // さっき一時記憶した場所(temp)を、新規ノードの「次の場所」にする。(3)
    newNodePos->next = temp;

    printf("ノードを挿入しました。\n");
}

ちょっぴり長いコードですが、重要なのはコード内の(1)(2)(3)だけ。
ここで何をしているのかをしっかり把握しましょう。

まず(1)。
temp = current->next;
tempとは"temporary"の略で、"一時的な"という意味がある英単語です。
プログラミングではよく使われる単語なので、知らなかった人はこの機会に覚えておくといいかも。
tempに、挿入先ノード(current)の「1つ後ろのノード(next)」の場所を一時的に格納します。

次に(2)。
current->next = newNodePos;
挿入先ノードの次に、新規ノードを追加します。

最後に(3)。
newNodePos->next = temp;
(1)で格納したノードを、新規ノードの「次の場所」に設定します。

上記の手順を踏むことで、「任意の場所へのノードの挿入」が実装できます。
画像で解説すると、以下のような感じ。

STEP1:新しいノードを生成。
f:id:Mafuyu7se:20181229223555p:plain

STEP2:挿入先ノードの、「1つ後ろのノード」の場所をtempとする。
f:id:Mafuyu7se:20181230215207p:plain

STEP3:挿入先ノードのnextに、新規ノードの場所をセット。
f:id:Mafuyu7se:20181230215648p:plain

STEP4:新規ノードのnextに、tempをセット。
f:id:Mafuyu7se:20181230215748p:plain

「ノードの挿入」を実装するには、このようにノードの"next"を繋ぎ変えればよいのです。

main関数を以下のように変更して、「I」が入力された時にinsertNodeToList関数が呼ばれるようにしましょう。

int main(void)
{
    char input;
    char command;
    while (1)
    {
        printf("-------------操作方法-------------\n");
        printf("A : リストの末尾にノードを追加します。\n");
        printf("P : リスト内のノードを全て表示します。\n");
        printf("I : リスト内の任意の場所にノードを挿入します。\n");
        printf("コマンドを入力してください:");

        // 入力されたアルファベットをtoupperで大文字に変換。
        // switch文の判定にアルファベットの大文字を使うため。
        scanf("%s", &input);
        command = toupper(input);
        switch (command)
        {
            case 'A':
                addNodeToList(); // リスト末尾にノード追加。
                break;
            case 'P':
                printList(); // リストの内容を画面表示。
                break;
            case 'I':
                insertNodeToList(); // 任意の場所にノードを挿入。
                break;
            default:
                printf("無効なコマンドです。\n");
                break;
        }
        printf("\n");
    }
    return 0;
}

実行結果の例。

まずAコマンドで4個ノードを生成し、それをPコマンドで表示してみます。
f:id:Mafuyu7se:20181230220357p:plain

ここで、Iコマンドの出番です。
「I」を入力後、挿入先ノードの"name"を入力します。
f:id:Mafuyu7se:20181230220710p:plain

挿入先ノードが見つかったら、登録したいノードの学籍番号と名前を入力。
これで挿入が完了しました。
f:id:Mafuyu7se:20181230220945p:plain

最後にPコマンドでリストを表示!!
f:id:Mafuyu7se:20181230221119p:plain

無事、目的の場所にノードを挿入できていることを確認できたね!
学籍番号が順番通りになってないのに違和感があるけど、そこは気にしないでください…。
(「学籍番号」だと順番に表示しなきゃいけない感があるので、「年齢」とかの方が良かったな…と思ったけど修正が面倒なのでもういいや)

■ まとめ

・リスト構造を使うと、「ノードの追加」「ノードの削除」を動的に行うことができるよ!
・リストの先頭を示すheadと、末尾を示すtailは必ず登場するよ!
・動的にノードを追加するには、malloc関数を使ってメモリを確保するよ!
・リストの末尾にノードを追加するには、tailのnextに新しいノードをセットして、新しいノードをtailとすればいいんだよ!
・リストの「好きな場所」にノードを追加するには、対象のノードを探索して、nextを繋ぎ変えればいいんだよ!

「リストからノードを削除する方法」については、後編で解説します!!

それでは、よいお年をお迎えください~・:*+.\( °ω° )/.:+

続きはこちら。
mafuyu7se.hatenablog.com


にほんブログ村 IT技術ブログへにほんブログ村
にほんブログ村 IT技術ブログ C/C++へにほんブログ村