整数を2つの入力ファイルから昇順に並べ替える方法はありますか？

Question

私は、2つのファイルから整数入力を受け取るプログラムを作成しようとしています。私は昇順に2つのファイルを持ち、出力ファイルはこれらの2つを1つのファイルにマージして、昇順に並べる必要があります。

while((fscanf(inputFile1, "%d", &temp1) == 1) && (fscanf(inputFile2, "%d", &temp2) == 1)) 
{ 
    printf("temp1: %d\n", temp1); 
    printf("temp2: %d\n", temp2); 

    if (temp1 > temp2) 
    { 
    fprintf(outputFile, "%d\n", temp2); 
    fprintf(outputFile, "%d\n", temp1); 
    } 
    else if (temp1 < temp2) 
    { 
    fprintf(outputFile, "%d\n", temp1); 
    fprintf(outputFile, "%d\n", temp2); 
    } 
    else if (temp1 == temp2) 
    { 
    fprintf(outputFile, "%d\n", temp1); 
    fprintf(outputFile, "%d\n", temp2); 
    } 
} 

File 1 File 2 
5   1 
10  43 
30  55 
50  98 
345  500 

Output 
1 
5 
10 
43 
30 
55 
50 
98 
345 
500 

それはほぼ完了ですが、ファイルのいずれかが（> 43 30のような）別のファイル内の前の行よりも多い/少ない数を持っていたときに問題があります。出力が完全にソートされるように、この問題をどのように修正できますか？

Answer 1

各ファイルから1つの番号を読み取っていますが、同じファイルから2つの連続する番号を取得する必要がある場合は失敗します。

代わりに、＃1と＃2のファイルから数値を読み取り、その数値が小さい方のファイルから読み込みを続ける必要があります。

Answer 2

いつでも両方から読む必要はありません。いずれかのファイルの現在の値が3,6,8...、もう1つが7,9,10...の場合7を失うので、2番目のファイルから次の値を読み飛ばす必要があります。 1番目のファイルで7より小さいすべての値を読み取るためにループを実行し、2番目のファイルから次の値を読み取る必要があります。

int last = 1; // Initializing last to 1 so that it is read in the 1st cycle 
int in1, in2, temp1, temp2; 

fscanf(inputFile2, "%d", &in2); //Initializing in2 for valid 1st comparison 

while(1) 
{ 

    if(last == 1 && fscanf(inputFile1, "%d", &temp1) == 1){ 
     in1 = temp1; 
    } else last = 0; 
    if(last == 2 && fscanf(inputFile2, "%d", &temp2) == 1){ 
     in2 = temp2; 
    } else last = 0; 

    if(last == 0) break; // Will be 0 only if both reads fail 

    printf("temp1: %d\n", in1); 
    printf("temp2: %d\n", in2); 

    if (in1 < in2) 
    { 
     fprintf(outputFile, "%d\n", in1); 
     last = 1; 
    } 
    else 
    { 
     fprintf(outputFile, "%d\n", in2); 
     last = 2; 
    } 
} 

Answer 3

あなたのコードでは、2つの問題があります - 最初は、両方のファイルが同じ数のエントリを持っていることを前提とし、そして第二に、あなたは、出力の数字はペアの最初のファイル/秒のファイルまたはその逆に来ることを想定しています。

これは、一度に1つの数値を読み取ることで解決できます。一方の側からまたは他方の側から番号があることを示すフラグを設定し、欠落している側の番号を読み取り、出力に1つの番号を書き込みます。それから、次の読み上げのために番号を取った側に印を付け、プロセスを繰り返します。

int have1 = 0, have2 = 0; 
for (; ;) { 
    int temp1, temp2; 
    have1 = have1 || 1==fscanf(inputFile1, "%d", &temp1); 
    have2 = have2 || 1==fscanf(inputFile2, "%d", &temp2); 
    // We ran out of numbers in both files - exit 
    if (!have1 && !have2) { 
     break; 
    } 
    if (!have2 || (have1 && temp1 < temp2)) { 
     fprintf(outputFile, "%d\n", temp1); 
     have1 = 0; 
    } else if (!have1 || (have2 && temp2 < temp1)) { 
     fprintf(outputFile, "%d\n", temp2); 
     have2 = 0; 
    } else { 
     fprintf(outputFile, "%d\n", temp1); 
     have1 = 0; 
     fprintf(outputFile, "%d\n", temp2); 
     have2 = 0;   
    } 
} 

Answer 4

あなたは昇順の番号の2つの列を持っていた実用的なケースを考えてみましょう、そしてあなたは、昇順に読み出すたかった：

メインループは次のようになります。各列に1つの指を置いて、その列の次の値を指している可能性が最も高いでしょう。あなたは小さいものを選び、大声でそれを読んで、その指を下に動かします。これはコードが実装するアルゴリズムです。

擬似コードのアルゴリズムを見てみましょう。

まず、両方のファイルから最初の値を読み取る必要があります。我々がちょうど出力、他のファイルの内容に必要がある場合には、ソースファイルのいずれかが空であることが起こることがあります。初期条件の世話を

Read value1 from the first file. 
If we cannot, then: 
    Loop: 
     Read value2 from the second file. 
     If we cannot: Return. 
     Output value2 
    End loop 
End if 

Read value2 from the second file. 
If we cannot, then: 
    Loop: 
     Output value1 
     Read value1 from the first file. 
     If we cannot: Return. 
    End loop 
End if 

、そして今、私たちは最初からvalue1を持っています2番目のファイルからvalue2を削除し、メインループに入ることができます。

私たちが朗読した列の中で指を下に動かしたように、各反復で小さな値を出力し、そのソースファイルから次の数値を読み込みます。

また、データがなくなると、もう一方のファイルの内容が出力されます。

私は、すべての等しい値が最初のファイルから最初に出力されるロジックを選択したことに注意してください（つまり、両方の列が等しい値を持つ場合は最初に最初の列を読み込みますその後の2番目の列）。これはstable sortにする必要があります。

Loop: 

    If value1 <= value2, then: 
     Output value1 
     Read value1 from the first file. 
     If we cannot, then: 
      Loop: 
       Output value2 
       Read value2 from the second file. 
       If we cannot: Return. 
      End loop 
     End if 
    Else: 
     Output value2 
     Read value2 from the second file. 
     If we cannot, then: 
      Loop: 
       Output value1 
       Read value1 from the second file. 
       If we cannot: Return. 
      End loop 
     End if 
    End if 
End loop 

Cでは、関数として実装するのは非常に簡単です。おそらくvoid interleave_ints(FILE *in1, FILE *in2, FILE *out)。すべてのループは、上記（即ち、while (1) { ... }又はdo { ... } while(1);又はfor (;;) { ... }）、及び機能において、あなたが呼び出し元に戻りreturn;を使用することができ、無限である

注意。

Answer 5

小さい、トリッキーな解決策。あなたに興味があるなら、私はコメントを追加します。

#include <stdio.h> 

int main() { 
    FILE *file_1 = fopen("file_1.txt", "r"); 
    FILE *file_2 = fopen("file_2.txt", "r"); 

    int num; 
    int tmp; 
    int max = 0; 
    int i = 0; 

    FILE *stream[2] = {file_1, file_2}; 

    while(fscanf(stream[i], "%d", &num) == 1) { 
     if(! max) { 
      max = num; 
      i = i^1; 
      continue; 
     } 

     if(max < num) { 
      i = i^1; 
      tmp = max; 
      max = num; 
      num = tmp; 
     } 

     printf("%d\n", num); 
    } 
    printf("%d\n", max); 

    fclose(file_1); 
    fclose(file_2); 
    return 0; 
} 

入力：

file_1.txt

5 
10 
30 
50 
345 

file_2.txt

1 
43 
55 
98 
500 

出力：

1 
5 
10 
30 
43 
50 
55 
98 
345 
500