C言語によるデータの検索方法

2年 ago
優斗, 朝陽
2 minutes

C言語では、線形探索、二分探索、ハッシュ表などの方法でデータの検索ができます。

  1. 線形探索：
    線形探索は最も単純な探索方法で、データ集合内のすべての要素を探索し、それらを逐次目標値と比較して、目標値が見つかるか、またはデータ集合全体が探索されるまで続けます。
#include <stdio.h>

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  // 返回目标值在数组中的索引
        }
    }
    return -1;  // 表示未找到目标值
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 3;
    int result = linearSearch(arr, n, target);
    if (result == -1) {
        printf("未找到目标值\n");
    } else {
        printf("目标值在数组中的索引为：%d\n", result);
    }
    return 0;
}
  1. データ集合を半分ずつに分割し、目的の値と比較することでターゲットの値がどちらの半分にあるのかを推定し、該当する半分で別の二分検索を実行することで、目的の値が見つかるか見つからないことを特定するまで続けます。
#include <stdio.h>

int binarySearch(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;  // 返回目标值在数组中的索引
        }
        if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;  // 表示未找到目标值
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 3;
    int result = binarySearch(arr, 0, n - 1, target);
    if (result == -1) {
        printf("未找到目标值\n");
    } else {
        printf("目标值在数组中的索引为：%d\n", result);
    }
    return 0;
}
  1. ハッシュテーブル：キーと値のペアを格納するデータ構造で、キーを固定サイズの配列にマップすることで効率的なデータ検索を実現。
#include <stdio.h>
#include <stdbool.h>

#define SIZE 10

typedef struct {
    int key;
    int value;
} Entry;

Entry hashTable[SIZE];

int hashCode(int key) {
    return key % SIZE;
}

void insert(int key, int value) {
    int index = hashCode(key);
    while (hashTable[index].key != 0) {
        index = (index + 1) % SIZE;
    }
    hashTable[index].key = key;
    hashTable[index].value = value;
}

bool search(int key, int* value) {
    int index = hashCode(key);
    int count = 0;
    while (hashTable[index].key != 0) {
        if (count > SIZE) {
            return false;  // 哈希表已满，未找到目标值
        }
        if (hashTable[index].key == key) {
            *value = hashTable[index].value;
            return true;  // 找到目标值
        }
        index = (index + 1) % SIZE;
        count++;
    }
    return false;  // 未找到目标值
}

int main() {
    insert(1, 10);
    insert(2, 20);
    insert(3, 30);
    int target = 2;
    int value;
    if (search(target, &value)) {
        printf("目标值的键：%d，值：%d\n", target, value);
    } else {
        printf("未找到目标值\n");
    }
    return 0;
}
bannerAds