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

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

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

f:id:Mafuyu7se:20181229193313p:plain
こんばんは・:*+.\( °ω° )/.:+
バーチャル高専女子、まふゆです!
2週間ぶりの記事更新だね…。
リスト構造の解説記事も、今回でいよいよ大詰めです。

今回は「片方向の線形リスト」において、
・リストからノードを動的に削除する方法
について解説していきます!!

前編・中編の内容を理解している人向けの内容になっているよ!
自信のない人はもう一度読んできてね。
mafuyu7se.hatenablog.com
mafuyu7se.hatenablog.com

■ 本記事の対象読者

前編中編を読んだよ!!
・「リスト構造」における、「head」と「tail」について理解できてるよ!!
・malloc関数を使って、リストへ動的にノードを追加する方法を知っているよ!!

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

■ コードの実行環境

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

いつも通り!

■ 注意!!

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

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

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


スポンサーリンク



■ コードの準備。

今回は、中編で使ったコードに機能を追加していく形で話を進めていきます。
中編で使ったコードと同じものを以下に用意しているので、これをコピペして使ってもOKですよ♡

#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);
void insertNodeToList(void);

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

// ノードを生成する関数。
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;
        }
    }
}

// リスト内の任意の場所にノードを挿入する関数。
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つ後ろのノード」の場所を一時記憶。
    temp = current->next;

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

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

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

コードをざっと読んで、前回学んだ内容を思い出したら次に進みましょう。


スポンサーリンク



■ 「ノードの削除」を実装しよう。

上記コードでは、以下3点の操作を行うことができます。
・リスト末尾にノードを追加する。('A'コマンド)
・リスト先頭から末尾までを表示する。('P'コマンド)
・リスト内の任意の場所にノードを挿入する。('I'コマンド)

今回は、これらに
・任意のノードをリストから削除する。('D'コマンド)
を追加する形で実装していきます。

やることは以下2点。
・ノードをリストから削除する機能を持った"deleteNodeFromList関数"を追加する。
・main関数で、'D'が入力されたときにdeleteNodeFromList関数が呼ばれるようにする。

deleteNodeFromList関数の内容はこんな感じ。

void deleteNodeFromList(void)
{
    char deleteTargetName[20] = "";
    STUDENT *current, *prev;

    printf("削除するノードのnameを入力してください。\n");
    scanf("%s", deleteTargetName);

    // リストの先頭から、nameが一致するノードを探します。
    current = head;
    prev = NULL;

    while (current != NULL)
    {
        if (strcmp(current->name, deleteTargetName) == 0)
        {
            // ノードが見つかればループ終了。
            printf("ノードが見つかりました。\n");
            break;
        }
        else
        {
            // 現在のノードを1つ前のノード(prev)として記憶。(1)
            prev = current;
            current = current->next;
        }
    }

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

    if (current == head)
    {
        // 削除対象が先頭のノードだった場合。(2)
        // 先頭の次のノードを新しいheadとする。
        head = current->next;

        // 削除対象のノードを開放。
        free(current);
    }
    else
    {
        // 削除対象が先頭のノードではない場合。(3)
        // 「削除対象の1つ前」のnextに、「削除対象の1つ後ろ」をセット。
        prev->next = current->next;

        // 削除対象のノードを開放。
        free(current);
    }

    printf("削除が完了しました。\n");
}

そんなに難しいことはしていません。
探索対象のnameを入力して、nameが一致するノードを探す処理はinsertNodeToList関数と一緒だね。

ただ、ひとつ違う点があります。それはコード内の(1)。
現在のノード(current)のnameが探索対象と違うものだった場合の処理だね。
currentを次のノードに更新する前に、
prev = current;
という処理が行われています。

ここで、currentの1つ前のノードの場所を、prevという変数に記憶しています。
何故こんなことをしているのかというと、リストからノードを削除する際に、削除対象ノードの「1つ前」のノードが必要になるからです。
どういう使い方をするかは、あとで説明するよ。

ちなみにprevは「previous」の略で、「以前の」という意味をもつ英単語です。
プログラミング業界では、「next」と対照的な意味を持つ言葉としてよく使われるので、覚えておきましょう。

次にコード内の(2)と(3)。
実際にノードの削除を行っているのはここです。
ここが、今回の記事での一番のポイントになります。

まず、(2)。
削除対象のノードが先頭(head)の場合、こちらに分岐します。

処理の内容としては、
・headの次のノードを、新しいheadとする。
・削除対象のノードをfree関数で開放する。

という流れです。

画像で表すと以下のような感じ。

STEP1:削除対象(current)のノードのnextを、新しいheadとする。
f:id:Mafuyu7se:20190114170227p:plain

STEP2:削除対象(current)のノードをfree関数で開放する。
f:id:Mafuyu7se:20190114171153p:plain
これだけ。簡単でしょ?
STEP1でcurrentをリスト管理対象から外して、STEP2で実際に削除するようなイメージだね。

ノードの開放には、free(フリー)関数を使います。
free関数はmalloc関数で確保したメモリ領域を開放するために使われる関数です。

mallocで確保できるメモリ領域には上限があります。
不要になったメモリ領域はfreeで開放するようにしましょう。

メモリさんはみんなのものだから、独り占めはダメです。
他のプロセスさんもメモリを使いたいはずなので、使わないのなら積極的に譲ってあげようね。
無駄にメモリを消費しないようなコードを書くことを常に心掛けましょう。

そして次に(3)。
削除対象のノードがheadではない場合、こちらに分岐します。
ここで、ようやくprevが登場します。
さっき説明したとおり、prevはcurrentの一つ前のノードのことです。

処理の内容は、
・prevのnextを、削除対象ノードのnextとする。
・削除対象のノードをfree関数で開放する。

という流れ。

さっきと同じように図で説明するよ。
"種田梨沙"さんのノードを削除対象とした場合はこんな感じ。

STEP1:prevのnextを、削除対象(current)ノードのnextとする。
f:id:Mafuyu7se:20190114172427p:plain

STEP2:削除対象(current)のノードをfree関数で開放する。
f:id:Mafuyu7se:20190114172654p:plain
こうすれば、途中のノードを削除しても、リスト構造を保つことができるよね。

あと、これはそこまで大切な話ではないんだけど、一応補足しておきます。
上記画像ではfree関数でデータを「削除している」ような表現を使っていますが、実際にデータがメモリ上から消えるわけではありません。
free関数はあくまでメモリ領域を「開放する」だけであって、そこにあるデータそのものの削除は行わないんです。
要するに、「まだデータは入ってるけど、私はここの領域はもう使わないので、誰かが勝手に書き換えてもいいですよ~」っていう状態にするわけだね。

■ 「ノードの削除」をやってみよう。

ノード削除処理の実装が終わったね。
main関数を以下のように変更して、削除処理を行う関数を呼び出せるようにしましょう。
'D'が入力されたとき、deleteNodeFromList関数を呼ぶようにするよ。

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

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

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

        switch (command)
        {
            case 'A':
                addNodeToList(); // リスト末尾にノード追加。
                break;
            case 'P':
                printList(); // リストの内容を画面表示。
                break;
            case 'I':
                insertNodeToList(); // 任意の場所にノードを挿入。
                break;
            case 'D':
                deleteNodeFromList(); // 任意のノードを削除。
                break;
            default:
                printf("無効なコマンドです。\n");
                break;
        }

        printf("\n");
    }

    return 0;
}

コードを実行後、Aコマンドを4回実行して以下のようなリストを作りました。
f:id:Mafuyu7se:20190114174945p:plain

'D'コマンドを入力後、削除対象ノードのnameを入力したら、削除が完了します。
f:id:Mafuyu7se:20190114175231p:plain

削除完了後、'P'コマンドで表示した結果がこちら。
f:id:Mafuyu7se:20190114175407p:plain
無事削除されていることが確認できたね。

他のノードも削除してみましょう。
f:id:Mafuyu7se:20190114175536p:plain

削除完了後、'P'コマンドでリストを表示。
f:id:Mafuyu7se:20190114175658p:plain
バッチリ削除できていますね!完璧です。


スポンサーリンク



■ malloc-free論争について。

これは完全に余談なので、興味がない人は別に読まなくてもいいです。

Cプログラマ界隈では、昔から「malloc-free論争」というものがたびたび勃発します。
簡単に言うと、
「mallocで確保した領域は、終了する前に必ずfreeで開放しなければならない!」
という主張と、
「プログラム終了時にOSさんが開放してくれるんだから、別に開放しなくても良くない?」
という主張がぶつかり合うわけですね。

私としては、どちらの主張も正しいと思っています。
こういうのは開発現場の状況によってどちらが正しいのかは変わってきます。
要はケース・バイ・ケースです。便利な言葉だね。

怖い人に絡まれるのは嫌なので、私からこの件について詳しくは説明しませんが、興味がある人は「malloc free 論争」とかでググってみてね。勉強になることは間違いないです。
5chとかのネット掲示板で時々プログラマ同士が互いに罵りあっているのを見かけますが、ああいうのは見苦しいので真似しないようにしましょう。

■ まとめ

・malloc関数で動的に確保した領域が不要になったら、free関数を使って開放するよ!
・削除対象ノードがリストの先頭(head)なら、headの次のノードを新しいheadにするよ!
・削除対象ノードがリストの先頭(head)以外なら、削除対象ノードの一つ前(prev)のnextに、削除対象ノードのnextをセットするよ!
・「malloc-free論争」は、どちらの主張が正しいかは状況によって変わってくるよ!

「片方向の線形リスト」について、前編/中編/後編の3回にわたって解説してきました。
これは最も基本的なデータ構造なので、使い所も非常に多いんです。
C言語プログラマを目指すなら必ず習得しておくべきだよ。
ここまで読んでくれたあなたなら、きっとリスト構造の基礎を完璧に理解しているはず!!

不明点があれば、記事にコメントするなり、TwitterでリプライやDM飛ばすなりしてくれれば対応しますよ。

ではでは~・:*+.\( °ω° )/.:+

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