MENU
  1. ホーム
  2. C言語
  3. アルゴリズム
  4. [C言語] 構造体を線形探索する方法を解説

[C言語] 構造体を線形探索する方法を解説

C言語で構造体を線形探索する方法は、配列内の各要素を順番にチェックして目的のデータを見つける手法です。

構造体の配列を用意し、ループを使用して各構造体のメンバを比較します。

例えば、構造体のメンバが特定の値と一致するかを確認するために、forループやwhileループを使用します。

一致する要素が見つかった場合、そのインデックスやポインタを返すことで、目的のデータにアクセスできます。

この方法は、データが少ない場合に有効ですが、大量のデータには効率的ではありません。

この記事でわかること
  • 線形探索の基本アルゴリズムとその実装方法
  • 構造体配列に対する線形探索の具体例
  • 構造体の動的メモリ確保やネストを用いた応用例
  • 線形探索とバイナリ探索の違い
  • 構造体のメンバが多い場合の効率的な探索方法

目次から探す

線形探索の実装方法

線形探索の基本アルゴリズム

線形探索は、データ構造内の要素を順番にチェックして、特定の条件に一致する要素を見つけるアルゴリズムです。

最も単純な探索方法であり、以下のような手順で実装されます。

  1. データ構造の最初の要素から順に、各要素をチェックする。
  2. 探索条件に一致する要素が見つかった場合、その要素のインデックスを返す。
  3. 最後の要素までチェックしても見つからない場合、探索失敗として特定の値(通常は-1)を返す。

このアルゴリズムは、データが無秩序である場合や、データ量が少ない場合に有効です。

構造体配列に対する線形探索の実装

構造体配列に対する線形探索は、各構造体の特定のメンバを条件として探索を行います。

以下に、学生情報を格納した構造体配列から特定の学生を探索する例を示します。

#include <stdio.h>
#include <string.h>
// 学生情報を格納する構造体
typedef struct {
    char name[50];
    int id;
} Student;
// 学生IDを基に線形探索を行う関数
int linearSearch(Student students[], int size, int targetId) {
    for (int i = 0; i < size; i++) {
        if (students[i].id == targetId) {
            return i; // 見つかった場合、インデックスを返す
        }
    }
    return -1; // 見つからなかった場合、-1を返す
}
int main() {
    Student students[] = {
        {"Alice", 101},
        {"Bob", 102},
        {"Charlie", 103}
    };
    int size = sizeof(students) / sizeof(students[0]);
    int targetId = 102;
    int index = linearSearch(students, size, targetId);
    if (index != -1) {
        printf("学生 %s が見つかりました。\n", students[index].name);
    } else {
        printf("学生が見つかりませんでした。\n");
    }
    return 0;
}
学生 Bob が見つかりました。

この例では、学生IDを基に構造体配列を線形探索し、該当する学生の名前を出力しています。

線形探索の効率性と限界

線形探索の効率性は、データの量に直接依存します。

以下に、線形探索の効率性と限界を示します。

スクロールできます
特徴説明
時間計算量O(n) – データ量が増えると、探索時間も比例して増加します。
メモリ使用量O(1) – 追加のメモリをほとんど必要としません。
利点実装が簡単で、データが無秩序でも使用可能です。
欠点データ量が多い場合、効率が悪くなります。

線形探索は、データが少ない場合や、データが無秩序である場合に適していますが、大量のデータを扱う場合は、より効率的な探索アルゴリズム(例：バイナリ探索)を検討する必要があります。

構造体の線形探索の具体例

学生情報の検索

学生情報を格納した構造体配列から、特定の学生を名前で検索する例を示します。

以下のコードでは、学生の名前を基に線形探索を行い、該当する学生のIDを出力します。

#include <stdio.h>
#include <string.h>
// 学生情報を格納する構造体
typedef struct {
    char name[50];
    int id;
} Student;
// 学生名を基に線形探索を行う関数
int searchStudentByName(Student students[], int size, const char* targetName) {
    for (int i = 0; i < size; i++) {
        if (strcmp(students[i].name, targetName) == 0) {
            return students[i].id; // 見つかった場合、学生IDを返す
        }
    }
    return -1; // 見つからなかった場合、-1を返す
}
int main() {
    Student students[] = {
        {"Alice", 101},
        {"Bob", 102},
        {"Charlie", 103}
    };
    int size = sizeof(students) / sizeof(students[0]);
    const char* targetName = "Charlie";
    int studentId = searchStudentByName(students, size, targetName);
    if (studentId != -1) {
        printf("学生 %s のIDは %d です。\n", targetName, studentId);
    } else {
        printf("学生が見つかりませんでした。\n");
    }
    return 0;
}
学生 Charlie のIDは 103 です。

この例では、学生の名前を基に構造体配列を線形探索し、該当する学生のIDを出力しています。

商品データの検索

商品データを格納した構造体配列から、特定の商品をIDで検索する例を示します。

以下のコードでは、商品IDを基に線形探索を行い、該当する商品の名前を出力します。

#include <stdio.h>
#include <string.h>
// 商品情報を格納する構造体
typedef struct {
    char name[50];
    int id;
} Product;
// 商品IDを基に線形探索を行う関数
int searchProductById(Product products[], int size, int targetId) {
    for (int i = 0; i < size; i++) {
        if (products[i].id == targetId) {
            return i; // 見つかった場合、インデックスを返す
        }
    }
    return -1; // 見つからなかった場合、-1を返す
}
int main() {
    Product products[] = {
        {"Laptop", 201},
        {"Smartphone", 202},
        {"Tablet", 203}
    };
    int size = sizeof(products) / sizeof(products[0]);
    int targetId = 202;
    int index = searchProductById(products, size, targetId);
    if (index != -1) {
        printf("商品 %s が見つかりました。\n", products[index].name);
    } else {
        printf("商品が見つかりませんでした。\n");
    }
    return 0;
}
商品 Smartphone が見つかりました。

この例では、商品IDを基に構造体配列を線形探索し、該当する商品の名前を出力しています。

社員名簿の検索

社員名簿を格納した構造体配列から、特定の社員を名前で検索する例を示します。

以下のコードでは、社員の名前を基に線形探索を行い、該当する社員のIDを出力します。

#include <stdio.h>
#include <string.h>
// 社員情報を格納する構造体
typedef struct {
    char name[50];
    int id;
} Employee;
// 社員名を基に線形探索を行う関数
int searchEmployeeByName(Employee employees[], int size, const char* targetName) {
    for (int i = 0; i < size; i++) {
        if (strcmp(employees[i].name, targetName) == 0) {
            return employees[i].id; // 見つかった場合、社員IDを返す
        }
    }
    return -1; // 見つからなかった場合、-1を返す
}
int main() {
    Employee employees[] = {
        {"Tanaka", 301},
        {"Suzuki", 302},
        {"Yamada", 303}
    };
    int size = sizeof(employees) / sizeof(employees[0]);
    const char* targetName = "Suzuki";
    int employeeId = searchEmployeeByName(employees, size, targetName);
    if (employeeId != -1) {
        printf("社員 %s のIDは %d です。\n", targetName, employeeId);
    } else {
        printf("社員が見つかりませんでした。\n");
    }
    return 0;
}
社員 Suzuki のIDは 302 です。

この例では、社員の名前を基に構造体配列を線形探索し、該当する社員のIDを出力しています。

構造体と線形探索の応用

構造体の動的メモリ確保と線形探索

動的メモリ確保を用いることで、実行時に必要なメモリを確保し、柔軟に構造体配列を扱うことができます。

以下の例では、動的に確保した構造体配列に対して線形探索を行います。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 学生情報を格納する構造体
typedef struct {
    char name[50];
    int id;
} Student;
// 学生IDを基に線形探索を行う関数
int linearSearch(Student* students, int size, int targetId) {
    for (int i = 0; i < size; i++) {
        if (students[i].id == targetId) {
            return i; // 見つかった場合、インデックスを返す
        }
    }
    return -1; // 見つからなかった場合、-1を返す
}
int main() {
    int size = 3;
    Student* students = (Student*)malloc(size * sizeof(Student));
    // 学生情報を動的に設定
    strcpy(students[0].name, "Alice");
    students[0].id = 101;
    strcpy(students[1].name, "Bob");
    students[1].id = 102;
    strcpy(students[2].name, "Charlie");
    students[2].id = 103;
    int targetId = 102;
    int index = linearSearch(students, size, targetId);
    if (index != -1) {
        printf("学生 %s が見つかりました。\n", students[index].name);
    } else {
        printf("学生が見つかりませんでした。\n");
    }
    free(students); // メモリの解放
    return 0;
}
学生 Bob が見つかりました。

この例では、mallocを用いて動的にメモリを確保し、構造体配列を操作しています。

探索後はfreeでメモリを解放します。

構造体のネストと線形探索

構造体の中に別の構造体を含めることができ、これをネストと呼びます。

以下の例では、ネストされた構造体を含む配列に対して線形探索を行います。

#include <stdio.h>
#include <string.h>
// 住所情報を格納する構造体
typedef struct {
    char city[50];
    char street[50];
} Address;
// 社員情報を格納する構造体
typedef struct {
    char name[50];
    int id;
    Address address;
} Employee;
// 社員名を基に線形探索を行う関数
int searchEmployeeByName(Employee employees[], int size, const char* targetName) {
    for (int i = 0; i < size; i++) {
        if (strcmp(employees[i].name, targetName) == 0) {
            return i; // 見つかった場合、インデックスを返す
        }
    }
    return -1; // 見つからなかった場合、-1を返す
}
int main() {
    Employee employees[] = {
        {"Tanaka", 301, {"Tokyo", "Shibuya"}},
        {"Suzuki", 302, {"Osaka", "Namba"}},
        {"Yamada", 303, {"Nagoya", "Sakae"}}
    };
    int size = sizeof(employees) / sizeof(employees[0]);
    const char* targetName = "Suzuki";
    int index = searchEmployeeByName(employees, size, targetName);
    if (index != -1) {
        printf("社員 %s が見つかりました。住所: %s, %s\n", employees[index].name, employees[index].address.city, employees[index].address.street);
    } else {
        printf("社員が見つかりませんでした。\n");
    }
    return 0;
}
社員 Suzuki が見つかりました。住所: Osaka, Namba

この例では、社員情報に住所情報をネストし、社員名を基に線形探索を行っています。

構造体のポインタを用いた線形探索

構造体のポインタを用いることで、メモリ効率を向上させることができます。

以下の例では、構造体のポインタを用いて線形探索を行います。

#include <stdio.h>
#include <string.h>
// 商品情報を格納する構造体
typedef struct {
    char name[50];
    int id;
} Product;
// 商品IDを基に線形探索を行う関数
int searchProductById(Product* products, int size, int targetId) {
    for (int i = 0; i < size; i++) {
        if (products[i].id == targetId) {
            return i; // 見つかった場合、インデックスを返す
        }
    }
    return -1; // 見つからなかった場合、-1を返す
}
int main() {
    Product products[] = {
        {"Laptop", 201},
        {"Smartphone", 202},
        {"Tablet", 203}
    };
    int size = sizeof(products) / sizeof(products[0]);
    int targetId = 203;
    int index = searchProductById(products, size, targetId);
    if (index != -1) {
        printf("商品 %s が見つかりました。\n", products[index].name);
    } else {
        printf("商品が見つかりませんでした。\n");
    }
    return 0;
}
商品 Tablet が見つかりました。

この例では、構造体のポインタを用いて商品IDを基に線形探索を行い、該当する商品の名前を出力しています。

ポインタを用いることで、関数呼び出し時のメモリ使用量を抑えることができます。

よくある質問

構造体の中に配列がある場合、線形探索はどう行うのか？

構造体の中に配列がある場合、線形探索は通常の構造体メンバに対する探索と同様に行います。

配列の要素を探索条件にする場合、構造体の各インスタンスに対して、その配列をループで回し、条件に一致するかをチェックします。

例：if (strcmp(structArray[i].arrayMember[j], target) == 0) { /* 処理 */ }

線形探索とバイナリ探索の違いは何か？

線形探索とバイナリ探索は、データの探索方法において異なるアプローチを取ります。

  • 線形探索は、データを順番にチェックしていくため、データが無秩序でも使用可能ですが、時間計算量はO(n)です。
  • バイナリ探索は、データがソートされていることを前提に、データを半分に分割しながら探索を行うため、時間計算量はO(log n)で、線形探索よりも効率的です。

構造体のメンバが多い場合、線形探索の効率を上げる方法はあるか？

構造体のメンバが多い場合、線形探索の効率を上げるためには、以下の方法を検討できます。

  • 検索対象のメンバを優先的にチェックすることで、不要な比較を減らす。
  • 構造体の配列をソートし、バイナリ探索を使用することで、探索時間を短縮する。
  • ハッシュテーブルなどのデータ構造を使用して、探索を高速化する。

まとめ

構造体を用いた線形探索は、シンプルで実装が容易な探索手法です。

この記事では、構造体の線形探索の基本から応用までを解説し、具体例を通じて理解を深めました。

これを機に、実際のプログラムで構造体と線形探索を活用し、効率的なデータ処理を実現してみてください。

目次に戻る

当サイトはリンクフリーです。出典元を明記していただければ、ご自由に引用していただいて構いません。

C言語
C++
Python
HTML
Java
HTTP

関連カテゴリーから探す

アルゴリズム
  • URLをコピーしました！

関連記事

目次から探す