(1) 实现模式匹配算法BF算法，自己设计不同规模的测试样例，分别进行匹配成功与失败的测试； （2）将稀疏矩阵按照三元组法存储，并在此基础上求其转置矩阵（使用两种方式实现）。 （3）使用合适的方式分析两项实验的时间复杂度。 用C语言利用菜单函数实现上面要求

(1) Boyer-Moore字符串搜索算法（也称为BF算法）是一种用于查找文本串中特定模式的高效算法。它的核心思想是在遇到不匹配字符时，不是回溯整个字符串，而是从模式的末尾开始调整位置。首先，你需要定义几个关键部分的变量，如坏字符规则、好后缀规则等。然后，你可以创建一个简单的C程序，例如：

#include <stdio.h>
#include <string.h>

void boyer_moore(char *text, char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    int bad_chars[256] = {0}; // 初始化坏字符数组
    for (int i = 0; i < m - 1; i++) {
        bad_chars[pattern[i]] = m - i - 1;
    }
    
    int pattern_index = m - 1, text_index = n - 1;
    while (text_index >= 0 && pattern_index >= 0) {
        if (text[text_index] == pattern[pattern_index]) {
            text_index--;
            pattern_index--;
        } else {
            int skip = bad_chars[(int)text[text_index]];
            if (skip > pattern_index) {
                text_index -= skip + 1;
            } else {
                text_index--;
            }
        }
    }
    if (pattern_index == -1) {
        printf("Pattern found at index %d\n", text_index + 1);
    } else {
        printf("Pattern not found\n");
    }
}

// 测试样例
int main() {
    const char *test_cases[] = {"ababc", "abaxc", "abacx"};
    const size_t test_case_count = sizeof(test_cases) / sizeof(test_cases[0]);
    
    for (size_t i = 0; i < test_case_count; i++) {
        printf("Testing with case %s...\n", test_cases[i]);
        boyer_moore(test_cases[i], "abc");
    }
    return 0;
}

记得运行这个程序并观察结果，包括成功的匹配（如"ababc"）和失败的匹配（如"abaxc"）。

(2) 稀疏矩阵通常使用三元组法（也称压缩存储法）存储，其中包含行索引、列索引和值。转置矩阵的实现可以分为两种：直接遍历原矩阵和利用映射数据结构。一种简单的方式是通过两层循环交换行和列：

typedef struct SparseMatrixEntry {
    int row, col, value;
} SparseMatrixEntry;

SparseMatrix transposed(SparseMatrix matrix) {
    int rows = matrix.entries.size();
    int cols = matrix.values.size() / rows;
    SparseMatrix transposed = malloc(sizeof(SparseMatrix));
    transposed.rows = cols;
    transposed.cols = rows;
    transposed.entries.resize(cols);

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            transposed.entries[j].row = i;
            transposed.entries[j].col = matrix.entries[i * cols + j].col;
            transposed.entries[j].value = matrix.entries[i * cols + j].value;
        }
    }

    return transposed;
}

// 示例使用
SparseMatrix sparse_matrix = ...; // 假设已经初始化好的稀疏矩阵
SparseMatrix transposed_sparse = transposed(sparse_matrix);

// 时间复杂度分析：O(M*N)，M是原矩阵的非零元素数，N是转置后的列数（假设矩阵是对称的）

(3) 第一个实验（BF算法）时间复杂度分析通常是O(n + m)，n是文本长度，m是模式长度；第二个实验（稀疏矩阵转置）在对称的情况下是O(MN)，M是行数也是列数，N是非零元素总数。实际时间会受稀疏程度影响。