如何用Divide et impera（分治法）批量查找含指定术语的文件？

需求回顾 #

从键盘读取一个最多31字符的术语，查找所有包含该术语的文件；目标文件每行最多存储31字符的术语，所有目标文件的路径存储在documente.txt中，要求用**分治法（Divide et impera）**实现。

现有代码的问题排查 #

• 重复写入文件名：gasit函数中只要文件内有一行匹配术语，就会写入一次文件名，若文件有多行匹配会重复输出同一个文件名，不符合“记录包含该术语的文件”的核心需求。
• 错误处理不友好：子函数直接调用exit(1)退出程序，无具体错误提示，不利于调试定位问题。
• 输出文件未初始化：每次运行时index.out以追加模式打开，会保留之前的查询结果，未实现单次查询的独立输出。
• 边界检查缺失：缺少术语长度校验、文件列表为空的判断，内存分配失败时未做资源回滚。

修复后的完整代码 #

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

// 计算文件的最大行长度和总行数
int lungime(FILE *f, int *nr_linii)
{
    int lung = 0;
    int maxim = -1;
    int c;
    (*nr_linii) = 0;
    while ((c = fgetc(f)) != EOF)
    {
        if (c == '\n')
        {
            (*nr_linii)++;
            if (lung > maxim)
                maxim = lung;
            lung = 0;
        }
        else
        {
            lung++;
        }
    }
    // 处理最后一行无换行的情况
    if (lung > 0)
    {
        (*nr_linii)++;
        if (lung > maxim)
            maxim = lung;
    }
    return maxim;
}

// 检查单个文件是否包含目标术语，找到后仅写入一次文件名
void gasit(char cautat[], char *nume_fis)
{
    FILE *fis = fopen(nume_fis, "r");
    if (fis == NULL)
    {
        fprintf(stderr, "Eroare la deschiderea fisierului: %s\n", nume_fis);
        return; // 不再直接退出，返回主函数继续处理其他文件
    }
    FILE *g = fopen("index.out", "a");
    if (g == NULL)
    {
        fprintf(stderr, "Eroare la deschiderea fisierului index.out\n");
        fclose(fis);
        return;
    }

    char cuv[32]; // 预留空间存储终止符
    int gasit_flag = 0;
    while (fgets(cuv, sizeof(cuv), fis) != NULL && !gasit_flag)
    {
        // 移除换行符
        size_t len = strlen(cuv);
        if (len > 0 && cuv[len - 1] == '\n')
        {
            cuv[len - 1] = '\0';
        }
        // 匹配术语
        if (strcmp(cuv, cautat) == 0)
        {
            gasit_flag = 1;
            fprintf(g, "%s\n", nume_fis);
        }
    }

    fclose(fis);
    fclose(g);
}

// 分治法处理文件列表：拆分列表，递归处理子列表
void divide_et_impera(char **a, int st, int dr, char *termen)
{
    if (st == dr)
    {
        gasit(termen, a[st]);
    }
    else
    {
        int mij = (st + dr) / 2;
        divide_et_impera(a, st, mij, termen);
        divide_et_impera(a, mij + 1, dr, termen);
    }
}

int main()
{
    FILE *f = fopen("documente.txt", "r");
    if (f == NULL)
    {
        fprintf(stderr, "Eroare la deschiderea fisierului documente.txt\n");
        return 1;
    }

    // 读取目标术语
    char termen[32];
    printf("Termenul de cautat: ");
    if (fgets(termen, sizeof(termen), stdin) == NULL)
    {
        fprintf(stderr, "Eroare la citirea termenului\n");
        fclose(f);
        return 1;
    }
    // 移除换行符
    size_t len_termen = strlen(termen);
    if (len_termen > 0 && termen[len_termen - 1] == '\n')
    {
        termen[len_termen - 1] = '\0';
    }
    // 检查术语长度是否符合要求
    if (strlen(termen) > 31)
    {
        fprintf(stderr, "Termenul trebuie sa aiba maxim 31 de caractere\n");
        fclose(f);
        return 1;
    }

    // 清空输出文件
    FILE *out_init = fopen("index.out", "w");
    if (out_init != NULL)
    {
        fclose(out_init);
    }

    // 获取文件列表的行数和最大行长度
    int n;
    int lung_max = lungime(f, &n);
    if (n == 0)
    {
        fprintf(stderr, "Fisierul documente.txt este gol\n");
        fclose(f);
        return 1;
    }

    // 分配内存存储文件路径
    char **calea = (char **)malloc(n * sizeof(char *));
    if (calea == NULL)
    {
        fprintf(stderr, "Eroare la alocarea memoriei\n");
        fclose(f);
        return 1;
    }
    for (int i = 0; i < n; i++)
    {
        calea[i] = (char *)malloc(lung_max + 2); // +2 用于换行符和终止符
        if (calea[i] == NULL)
        {
            fprintf(stderr, "Eroare la alocarea memoriei pentru calea fisierului\n");
            // 释放已分配的内存
            for (int j = 0; j < i; j++)
            {
                free(calea[j]);
            }
            free(calea);
            fclose(f);
            return 1;
        }
    }

    // 重新读取文件路径到数组中
    fseek(f, 0, SEEK_SET);
    int i = 0;
    while (fgets(calea[i], lung_max + 2, f) != NULL && i < n)
    {
        size_t len_calea = strlen(calea[i]);
        if (len_calea > 0 && calea[i][len_calea - 1] == '\n')
        {
            calea[i][len_calea - 1] = '\0';
        }
        i++;
    }

    // 调用分治法进行查找
    divide_et_impera(calea, 0, n - 1, termen);

    // 释放内存
    for (i = 0; i < n; i++)
    {
        free(calea[i]);
    }
    free(calea);
    fclose(f);

    return 0;
}

关键修复说明 #

• 避免重复写入：在gasit中添加gasit_flag，找到第一个匹配项后停止遍历文件，仅写入一次文件名。
• 优化错误处理：替换exit(1)为错误提示并返回，确保单个文件打开失败时，程序能继续处理其他文件。
• 初始化输出文件：主函数中先以w模式打开index.out并关闭，清空之前的查询结果。
• 增强边界检查：添加术语长度校验、文件列表为空的判断，以及内存分配失败时的资源释放逻辑。
• 缓冲区优化：将cuv数组大小设为32，确保能容纳31字符的术语加终止符。

内容的提问来源于stack exchange，提问作者Francesco Totti