PricingLoginStart free
C Academy · レッスン

走査と検索

リストをたどります。

レッスン 3/413 ステップ

「走査と検索」はCoddyKit上の無料C Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。

リストをたどる

走査とは、各ノードを順番に訪問することです。headから始め、NULLに到達するまでnextポインターをたどります。

ほとんどすべてのリストアルゴリズムは、この単純な走査を基礎にしています。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(10);
    head->next = make(20);
    for (struct Node *p = head; p != NULL; p = p->next)
        printf("%d ", p->value);
    printf("\n");
    return 0;
}

走査のパターン

標準的なループでは、移動用ポインターpを使います。headで初期化し、pがNULLでない間処理を続け、p = p->nextで進めます。

走査中にhead自体を変更しないでください。リストの先頭を失ってしまいます。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    struct Node *p = head;
    while (p) { printf("%d ", p->value); p = p->next; }
    printf("\n");
    return 0;
}

ノードを数える

長さを求めるには、リストを走査し、ノードごとにカウンターを1増やします。

個数がどこにも保存されていないため、これはO(n)の操作です。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int length(struct Node *head) {
    int n = 0;
    for (struct Node *p = head; p; p = p->next) n++;
    return n;
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    printf("length = %d\n", length(head));
    return 0;
}

値を合計する

走査を使うとデータを集計できます。ここでは、リスト内のすべての整数値を合計します。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(5);
    head->next = make(10);
    int sum = 0;
    for (struct Node *p = head; p; p = p->next) sum += p->value;
    printf("sum = %d\n", sum);
    return 0;
}

値を検索する

値を探すには、リストを走査して各ノードを比較します。一致する値が見つかったらノード（またはその位置）を返し、末尾まで到達したら失敗を示します。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

struct Node *find(struct Node *head, int v) {
    for (struct Node *p = head; p; p = p->next)
        if (p->value == v) return p;
    return NULL;
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    printf("found 2: %d\n", find(head, 2) != NULL);
    printf("found 9: %d\n", find(head, 9) != NULL);
    return 0;
}

位置を見つける

ノードではなく、一致した値のインデックスが必要な場合もあります。走査中にカウンターを保持し、値が見つかった時点でその値を返します。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int index_of(struct Node *head, int v) {
    int i = 0;
    for (struct Node *p = head; p; p = p->next, i++)
        if (p->value == v) return i;
    return -1;
}

int main(void) {
    struct Node *head = make(7);
    head->next = make(8);
    printf("%d\n", index_of(head, 8));
    return 0;
}

n番目のノードにアクセスする

連結リストには直接インデックスでアクセスする機能がありません。位置nに到達するには、headからn回進む必要があります。

そのため、ランダムアクセスは配列のO(1)に対してO(n)になります。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

struct Node *at(struct Node *head, int n) {
    struct Node *p = head;
    for (int i = 0; i < n && p; i++) p = p->next;
    return p;
}

int main(void) {
    struct Node *head = make(10);
    head->next = make(20);
    head->next->next = make(30);
    printf("%d\n", at(head, 2)->value);
    return 0;
}

最後のノードを見つける

末尾を取得するには、p->nextがNULLになるまでたどります。そのノードが最後のノードです。

head自体がNULLになる空のリストには注意してください。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    struct Node *p = head;
    while (p->next) p = p->next;
    printf("last = %d\n", p->value);
    return 0;
}

最大値を見つける

検索と集計を組み合わせると、走査中に現在の最大値を追跡して、最も大きい値を見つけられます。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(3);
    head->next = make(9);
    head->next->next = make(5);
    int best = head->value;
    for (struct Node *p = head->next; p; p = p->next)
        if (p->value > best) best = p->value;
    printf("max = %d\n", best);
    return 0;
}

再帰的な走査

リストは再帰的にたどることもできます。現在のノードを処理してから、nextに対して再帰呼び出しを行います。

これは簡潔に書けますが、リストの長さに比例するスタック領域を使うため、非常に長いリストでは反復処理のほうが安全です。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

void print_rec(struct Node *p) {
    if (!p) { printf("\n"); return; }
    printf("%d ", p->value);
    print_rec(p->next);
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    print_rec(head);
    return 0;
}

空のリストに備える

すべての走査関数は、空のリスト（head == NULL）を適切に処理できる必要があります。

標準的なループなら、すでに対応できます。条件p != NULLが最初から偽になるため、本文は一度も実行されません。

#include <stdio.h>

struct Node { int value; struct Node *next; };

int length(struct Node *head) {
    int n = 0;
    for (struct Node *p = head; p; p = p->next) n++;
    return n;
}

int main(void) {
    struct Node *head = NULL;
    printf("empty length = %d\n", length(head));
    return 0;
}

クイックチェック

リストの走査コストについての理解度を確認しましょう。

対話的なレッスンで答える

まとめ

リストの走査と検索の方法を学びました。

  • 走査のパターンは、headから始め、NULLでない間ループし、p = p->nextで進むことです。
  • 個数のカウント、合計、最大値の検索は、すべて走査を基礎にしています。
  • 検索では各ノードを比較します。インデックスによるアクセスはO(n)です。
  • 走査は再帰的にも行えますが、長いリストでは反復処理のほうが安全です。空のリストも必ず処理してください。
無料で開始

AI チューターと学ぶ C — 無料

ブラウザでリアルコードを書いて実行し、24/7 の AI チューターから瞬時にサポートを受け、ウェブまたはアプリで続きから学習できます。

コース
39
レッスン
144
無料で学習を始めるコース全体を表示

よくある質問

「走査と検索」レッスンは無料ですか？

はい。「走査と検索」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。

「走査と検索」で何を学びますか？

リストをたどります。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

C Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「走査と検索」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このC Academyレッスンでコードを書いて実行できますか？

はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 単方向連結リスト
  2. 挿入と削除
  3. 走査と検索
  4. 双方向連結リスト
← C Academyに戻る