如何在C中实现此外部合并分类算法

Question

我需要模拟一个外部排序算法，因为该机器只有96个字节可用。我正在使用32个字节结构，看起来像这样：

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

我已经在将大量的3个寄存器32二进制文件中的大tobesorted.txt文件拆分。例如：

 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合并会输出c e i n r t在退出文件中。当然，应将合并函数概括为一次读取每个排序键，并合并到出口文件中，无论文件输入大小如何。我的合并函数会收到一个可以包含2、3或4个文件的文件数组(不知道函数(，这是上述数组的最低索引，较高的索引和退出文件。看起来这样：

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

Typefile只是typedef FILE* TypeFile;。

我知道我应该一次比较每个寄存器的键，然后如果需要模拟内存限制，则写出最低的出口，但是我不能让自己想到一种方法。循环约束和输入为6个或更多关键角色的情况正在融化我的大脑。最后，我只希望o将初始的tobesorted.txt完全分类，一次将2、3或4个文件合并到更大的文件中，然后继续进行下一个文件。这已经实现，我只需要实现合并函数即可。抱歉，如果我让自己难以理解，英语不是我的母语。感谢你们可以给的任何HEP。

Answer 1

如果您已经分裂并排序了原始"块"文件，那么您需要的就是这样：

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中读取整个文件！(。您所要做的就是仅读取两个排序的文件字符，比较这些字符，然后输出到目标文件。然后，您再次合并这些新的组合文件，直到获得一个大型分类文件。