マージのアルゴリズム　解答ページ | Programming Place Plus　アルゴリズムとデータ構造編【その他のアルゴリズム】　第４章

#include <stdio.h>
#include "ppps_int_slist.h"

#define LIST_A_SIZE  (10)
#define LIST_B_SIZE  (5)

static void merge(PPPSIntSlist result, const PPPSIntSlist a, const PPPSIntSlist b);

int main(void)
{
    PPPSIntSlist a = ppps_int_slist_create();
    PPPSIntSlist b = ppps_int_slist_create();
    PPPSIntSlist c = ppps_int_slist_create();


    // リスト a, b を初期化
    for( int i = 0; i < LIST_A_SIZE; ++i ){
        ppps_int_slist_add_tail( a, i * 2 );
    }
    for( int i = 0; i < LIST_B_SIZE; ++i ){
        ppps_int_slist_add_tail( b, i * 3 );
    }

    // マージ実行
    merge( c, a, b );

    puts( "リストＡ" );
    ppps_int_slist_print( a );
    puts( "リストＢ" );
    ppps_int_slist_print( b );
    puts( "リストＣ" );
    ppps_int_slist_print( c );

    ppps_int_slist_delete( a );
    ppps_int_slist_delete( b );
    ppps_int_slist_delete( c );

    return 0;
}

/*
    マージ
*/
void merge(PPPSIntSlist result, const PPPSIntSlist a, const PPPSIntSlist b)
{
    PPPSIntSlist i = (a == NULL) ? NULL : a->next;
    PPPSIntSlist j = (b == NULL) ? NULL : b->next;
    PPPSIntSlist k = result;

    while( i != NULL || j != NULL ){
        if( i == NULL ){
            // 配列 a の終端に行き着いていたら、残された配列 b の要素を全コピー
            while( j != NULL ){
                ppps_int_slist_add_tail( k, j->value );
                k = k->next;
                j = j->next;
            }
        }
        else if( j == NULL ){
            // 配列 b の終端に行き着いていたら、残された配列 a の要素を全コピー
            while( i != NULL ){
                ppps_int_slist_add_tail( k, i->value );
                k = k->next;
                i = i->next;
            }
        }
        else{
            // 配列 a と b の先頭要素で、小さい方を result へ
            if( i->value <= j->value ){
                ppps_int_slist_add_tail( k, i->value );
                k = k->next;
                i = i->next;
            }
            else{
                ppps_int_slist_add_tail( k, j->value );
                k = k->next;
                j = j->next;
            }
        }
    }
}

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

static void merge(FILE* result, FILE* a, FILE* b);

int main(void)
{
    FILE* a = fopen( "a.txt", "r" );
    FILE* b = fopen( "b.txt", "r" );
    FILE* c = fopen( "c.txt", "w" );

    // マージ実行
    merge( c, a, b );

    fclose( a );
    fclose( b );
    fclose( c );

    return 0;
}

/*
    マージ
*/
void merge(FILE* result, FILE* a, FILE* b)
{
    #define WORD_LEN_MAX (10)   // １行に書かれた文字列の最大長

    char buf_a[WORD_LEN_MAX + 1];  // +1 は '\0' の分
    char buf_b[WORD_LEN_MAX + 1];  // +1 は '\0' の分
    int buf_a_enabled = 0;         // buf_a に有効なデータが格納されているか
    int buf_b_enabled = 0;         // buf_b に有効なデータが格納されているか


    while( !feof(a) || !feof(b) ){

        // バッファに読み込み済みでなければ、先頭要素（先頭行）を読み込んでおく
        if( !buf_a_enabled && !feof(a) ){
            fgets( buf_a, sizeof(buf_a), a );
            buf_a_enabled = 1;
        }
        if( !buf_b_enabled && !feof(b) ){
            fgets( buf_b, sizeof(buf_b), b );
            buf_b_enabled = 1;
        }


        if( feof(a) ){
            // 配列 a の終端に行き着いていたら、残された配列 b の要素を全コピー
            if( buf_b_enabled ){
                fputs( buf_b, result );
            }
            while( !feof(b) ){
                fgets( buf_b, sizeof(buf_b), b );
                fputs( buf_b, result );
            }
        }
        else if( feof(b) ){
            // 配列 b の終端に行き着いていたら、残された配列 a の要素を全コピー
            if( buf_a_enabled ){
                fputs( buf_a, result );
            }
            while( !feof(a) ){
                fgets( buf_a, sizeof(buf_a), a );
                fputs( buf_a, result );
            }
        }
        else{
            // 配列 a と b の先頭要素で、小さい方を result へ
            if( strcmp( buf_a, buf_b ) <= 0 ){
                fputs( buf_a, result );
                buf_a_enabled = 0;
            }
            else{
                fputs( buf_b, result );
                buf_b_enabled = 0;
            }
        }
    }

    #undef WORD_LEN_MAX
}