木子n1

木子n1

关注
发信
关注(28)粉丝(399)

汽车零部件软件开发常用搜索算法

五种常见的搜索算法在C语言环境中的应用及解析

一、线性搜索（Linear Search）

线性搜索是最基础的查找算法，适用于对未排序或无特定结构的数据集合进行搜索。在C语言中实现时，线性搜索通过遍历数组或链表中的每一个元素，并与目标值进行比较，直至找到匹配项或者遍历完所有元素。其时间复杂度为O(n)，其中n代表数据集的大小。

#include <stdbool.h> // 引入bool类型

// 定义线性搜索函数，返回值为找到元素的位置（下标），未找到则返回-1
int linear_search(const int array[], const int size, const int target) {
    for (int i = 0; i < size; ++i) {
        if (array[i] == target) {
            return i;
        }
    }

    return -1;
}

// 示例主函数
int main(void) {
    const int input_array[] = {1, 3, 5, 7, 9};
    const int search_target = 5;

    // 调用线性搜索函数
    int index = linear_search(input_array, sizeof(input_array) / sizeof(input_array[0]), search_target);

    if (index != -1) {
        printf("Element found at index: %d\n", index);
    } else {
        printf("Element not found in the array.\n");
    }

    return 0;
}

二、二分搜索（Binary Search）

二分搜索是一种高效的搜索算法，要求数据集事先已排序。它通过不断将搜索范围减半来快速定位目标值。对于长度为n的有序数组，二分搜索的时间复杂度为O(log n)。

#include <stdbool.h> // 引入bool类型

// 二分搜索函数，输入参数为已排序数组、数组大小和目标值，返回值为目标值在数组中的索引（如果存在），否则返回-1表示未找到
int binary_search(const int array[], const int size, const int target) {
    int left = 0;
    int right = (size - 1);

    while (left <= right) {
        int mid = (left + right) / 2;

        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            left = mid + 1;
        } else { // array[mid] > target
            right = mid - 1;
        }
    }

    return -1; // 目标值不在数组中
}

// 示例主函数
int main(void) {
    const int input_array[] = {1, 3, 5, 7, 9};
    const int search_target = 5;

    // 检查输入数组是否已排序
    for (int i = 1; i < sizeof(input_array) / sizeof(input_array[0]); ++i) {
        assert(input_array[i] >= input_array[i - 1]);
    }

    // 调用二分搜索函数
    int index = binary_search(input_array, sizeof(input_array) / sizeof(input_array[0]), search_target);

    if (index != -1) {
        printf("Element found at index: %d\n", index);
    } else {
        printf("Element not found in the array.\n");
    }

    return 0;
}

// 注意：在实际嵌入式开发中，assert()宏可能不被推荐使用，此处仅用于演示目的。

三、哈希表搜索（Hash Table Search）

哈希表是一种通过哈希函数将键转化为索引，从而实现高效查找的数据结构。理想情况下，哈希表能在常数时间内完成查找操作。在C语言中，可以使用数组和指针构建简单哈希表。

#include <stdbool.h> // 引入bool类型

// 假设我们使用一个固定大小的哈希表，这里以16为例
#define HASH_TABLE_SIZE 16

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

// 初始化哈希表为全空标志
HashEntry hash_table[HASH_TABLE_SIZE] = {0};

// 简单哈希函数示例，实际应用中可能需要更复杂的哈希函数减少冲突
int simple_hash(int key) {
    return key % HASH_TABLE_SIZE;
}

// 插入数据到哈希表，如果存在冲突则进行线性探测
void hash_table_insert(int key, int value) {
    int index = simple_hash(key);
    while (hash_table[index].key != 0 && hash_table[index].key != key) {
        index = (index + 1) % HASH_TABLE_SIZE; // 探测下一个槽位
    }
    hash_table[index].key = key;
    hash_table[index].value = value;
}

// 在哈希表中查找键值对，返回true表示找到，false表示未找到
bool hash_table_search(const int target_key, int *found_value) {
    int index = simple_hash(target_key);
    while (hash_table[index].key != 0) {
        if (hash_table[index].key == target_key) {
            *found_value = hash_table[index].value;
            return true;
        }
        index = (index + 1) % HASH_TABLE_SIZE; // 探测下一个槽位
    }

    return false;
}

// 示例主函数
int main(void) {
    hash_table_insert(3, "apple");
    hash_table_insert(7, "banana");

    int found_value;
    bool is_found = hash_table_search(7, &found_value);

    if (is_found) {
        printf("Element found: %d\n", found_value); // 在实际嵌入式开发中，应替换为合适的输出方式
    } else {
        printf("Element not found in the hash table.\n"); // 同样应替换为合适的方式
    }

    return 0;
}

四、位图搜索（Bitmap Search）

位图搜索主要用于标识大量整数值是否存在的一种方法，特别适合于空间有限且整数分布范围相对较小的情况。在C语言中，位图通常表现为一个字节数组，每个比特位对应一个可能的状态。

#include <stdbool.h>

// 假设最大支持的标记数量为MAX_MARKS
#define MAX_MARKS 32

// 定义位图结构体
typedef struct {
    unsigned int bitmap[MAX_MARKS / (sizeof(unsigned int) * 8)]; // 按照单片机平台上的整型宽度来确定数组大小
} Bitmap;

// 初始化位图
void bitmap_init(Bitmap *bmp) {
    for (unsigned int i = 0; i < sizeof(bmp->bitmap) / sizeof(bmp->bitmap[0]); ++i) {
        bmp->bitmap[i] = 0;
    }
}

// 设置位图中指定位置的标志位
void bitmap_set(Bitmap *bmp, int mark) {
    assert(mark >= 0 && mark < MAX_MARKS); // MISRA C要求：确保输入值有效
    bmp->bitmap[mark / (sizeof(unsigned int) * 8)] |= (1 << (mark % (sizeof(unsigned int) * 8)));
}

// 清除位图中指定位置的标志位
void bitmap_clear(Bitmap *bmp, int mark) {
    assert(mark >= 0 && mark < MAX_MARKS);
    bmp->bitmap[mark / (sizeof(unsigned int) * 8)] &= ~(1 << (mark % (sizeof(unsigned int) * 8)));
}

// 查找位图中是否存在指定位置的标志位
bool bitmap_search(const Bitmap *bmp, int mark) {
    assert(mark >= 0 && mark < MAX_MARKS);
    return (bmp->bitmap[mark / (sizeof(unsigned int) * 8)] & (1 << (mark % (sizeof(unsigned int) * 8)))) != 0;
}

// 示例主函数
int main(void) {
    Bitmap bmp;
    bitmap_init(&bmp);

    bitmap_set(&bmp, 5);
    bitmap_set(&bmp, 9);

    if (bitmap_search(&bmp, 5)) {
        printf("Mark 5 is set.\n"); // 在实际嵌入式开发中，应替换为合适的输出方式
    } else {
        printf("Mark 5 is not set.\n");
    }

    if (bitmap_search(&bmp, 9)) {
        printf("Mark 9 is set.\n");
    } else {
        printf("Mark 9 is not set.\n");
    }

    return 0;
}

五、有限状态机（FSM）搜索

有限状态机（FSM）主要用于处理输入序列并根据当前状态决定下一步行为。在搜索场景下，FSM可用于识别模式、解析语法等任务。在C语言中，可以使用结构体存储状态信息以及状态转移函数指针。

#include <stdbool.h>

// 定义状态机的状态枚举
typedef enum {
    FSM_STATE_IDLE = 0,
    FSM_STATE_PROCESSING,
    FSM_STATE_FINISHED,
    // ...其他状态...
    FSM_STATE_COUNT // 用于获取状态总数
} FSM_State_t;

// 定义事件枚举
typedef enum {
    FSM_EVENT_NONE = 0,
    FSM_EVENT_START,
    FSM_EVENT_DATA_RECEIVED,
    FSM_EVENT_FINISH,
    // ...其他事件...
    FSM_EVENT_COUNT // 用于获取事件总数
} FSM_Event_t;

// 状态机结构体
typedef struct {
    FSM_State_t current_state;
} FSM_t;

// 状态转移函数指针类型定义
typedef void (*StateTransitionFunction)(FSM_t *fsm, FSM_Event_t event);

// 状态转移表
static const StateTransitionFunction state_transition_table[FSM_STATE_COUNT][FSM_EVENT_COUNT] = {
    [FSM_STATE_IDLE] = {
        [FSM_EVENT_START] = fsm_idle_on_start,
        // 其他事件处理函数...
    },
    [FSM_STATE_PROCESSING] = {
        [FSM_EVENT_DATA_RECEIVED] = fsm_processing_on_data_received,
        // 其他事件处理函数...
    },
    // 其他状态下的事件处理函数...
};

// 空闲状态下接收到开始事件的处理函数
static void fsm_idle_on_start(FSM_t *fsm, FSM_Event_t event) {
    if (event == FSM_EVENT_START) {
        fsm->current_state = FSM_STATE_PROCESSING;
        // ...其他操作...
    }
}

// 处理中的状态下接收到数据事件的处理函数
static void fsm_processing_on_data_received(FSM_t *fsm, FSM_Event_t event) {
    if (event == FSM_EVENT_DATA_RECEIVED) {
        // ...处理数据...
    }
    // 根据实际情况更新状态
}

// 初始化状态机
void fsm_init(FSM_t *fsm) {
    fsm->current_state = FSM_STATE_IDLE;
}

// 状态机主循环，接收并处理事件
void fsm_process_event(FSM_t *fsm, FSM_Event_t event) {
    assert(event >= 0 && event < FSM_EVENT_COUNT); // MISRA C要求：确保输入值有效
    assert(fsm != NULL); // 确保指针非空

    state_transition_table[fsm->current_state][event](fsm, event);
}

// 示例主函数
int main(void) {
    FSM_t fsm;
    fsm_init(&fsm);

    // 假设从某个接口接收事件
    while (true) {
        FSM_Event_t event = get_next_event(); // 获取下一个事件的函数，此处仅为示例
        fsm_process_event(&fsm, event);
    }

    return 0;
}

总结：不同的搜索算法有各自适用的场景和优势，理解它们的工作原理并在实际项目中合理选择和应用是提高软件性能和资源利用率的关键。上述代码片段仅为简要示例，在实际开发过程中需结合具体需求和约束条件进行详细设计和优化。

02-19 09:12
Powered by LMLPHP ©2024 木子n1 0.004456