0

考虑到机器只有 96 字节的可用内存，我需要模拟一个外部排序算法。我正在使用如下所示的 32 字节结构： 

typedef struct {
    char usedmemory[31];
    char key;
}Register32;

我已经将一个大的 tobesorted.txt 文件拆分为 3 个 Register32 二进制文件。例如： 

 I N T E R C A L A C A O B A L A N C E A D A

分为8个文件，内部排序，从file0.bin到file7.bin，包含31个字节的垃圾，1个字节是用于始终对寄存器进行排序的键。 

file0.bin containing INT  
file1.bin containing CER  
file2.bin containing AAL  
file3.bin containing ACO  
file4.bin containing ABL  
file5.bin containing ACN  
file6.bin containing ADE  
file7.bin containing A

我的任务是在任何给定时间将这些文件中的 2、3 或 4 个“合并”到退出文件中，并继续合并它们，直到我把初始单词全部整理出来。示例：将 file0 与 file1 合并将在退出文件中输出 CEINRT。当然，合并功能应该概括为一次读取每个排序键并合并到退出文件中，而不管文件输入大小如何。我的 Merge 函数接收一个文件数组，该数组可以包含 2、3 或 4 个文件（函数未知）、所提及数组的最低索引、较高索引和退出文件。它看起来像这样： 

void MergeFunction(TypeFile* entry, int lowerindex,int higherindex, TypeFile exitfile){
       int i, j, count = 0;
}

TypeFile 只是一个typedef FILE* TypeFile;.

我知道如果我需要模拟内存限制，我应该一次比较每个寄存器的键，然后将最低值写入 exitfile，但我无法让自己想办法做到这一点。循环约束和输入长度为 6 个或更多关键字符的情况正在融化我的大脑。最后，我只想让最初的 tobesorted.txt 完全排序，一次将 2、3 或 4 个文件合并成一个更大的文件，然后继续下一个。这已经实现了，我只需要实现 Merge 功能。对不起，如果我让自己难以理解，英语不是我的母语。感谢你们能给予的任何帮助。

4

1 回答 1

0

如果您已经对原始“块”文件进行了拆分和排序，那么您需要的是这样的：

void mergeFiles(FILE* fIn1, FILE* fIn2, FILE* fOut)
{
    int ch1;
    int ch2;
    ch1 = fgetc(fIn1);
    ch2 = fgetc(fIn2);
    // merge files
    while ((ch1 != EOF) && (ch2 != EOF))
    {
        if (ch1 < ch2)
        {
            fputc(ch1, fOut);
            ch1 = fgetc(fIn1);
        }
        else
        {
            fputc(ch2, fOut);
            ch2 = fgetc(fIn2);
        }
    }

    // write the rest of one of the files
    if (ch2 == EOF)
    {
        while (ch1 != EOF)
        {
            fputc(ch1, fOut);
            ch1 = fgetc(fIn1);
        }
    }
    else
    {
        while (ch2 != EOF)
        {
            fputc(ch2, fOut);
            ch2 = fgetc(fIn2);
        }
    }
    fflush(fOut);
}

这个想法是合并排序算法的合并阶段只要求您获取要合并的两个子数组中的每一个的第一个元素。因此，流输入（例如文件）也符合此要求（即您不必将整个文件读入 RAM！）。您所要做的就是逐个字符地读取两个已排序的文件，比较这些字符，然后输出到目标文件中较小的一个。然后你再次合并这些新的组合文件，直到你得到一个大的排序文件。

于 2017-06-07T00:08:37.150 回答