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

トップページアルゴリズムとデータ構造編【その他のアルゴリズム】第4章

問題①

問題① 2つの単方向線形リスト(【データ構造】第3章)をマージするプログラムを作成してください。


本編で説明したように、2ウェイマージのアルゴリズムは、データ列の先頭要素にさえアクセスできれば実現できます。そのため、単方向の線形リストでも実現可能です。

以下の解答例では、単方向線形リストの実装に、コードライブラリの ppps_int_slist を使用しています。

#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( "リストA" );
    ppps_int_slist_print( a );
    puts( "リストB" );
    ppps_int_slist_print( b );
    puts( "リストC" );
    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;
            }
        }
    }
}

実行結果:

リストA
0
2
4
6
8
10
12
14
16
18
リストB
0
3
6
9
12
リストC
0
0
2
3
4
6
6
8
9
10
12
12
14
16
18

問題②

問題② 1行ごとに1つの文字列(10文字以内)が記述された2つのテキストファイルを、文字列の昇順に並ぶようにマージして、1つのテキストファイルを作り出すプログラムを作成してください。


いったん、テキストファイル全体を読み取ってしまえば簡単に扱えますが、ここでは先頭の1行分のメモリだけで実現できることを示します。

#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)   // 1行に書かれた文字列の最大長

    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
}

a.txt と b.txt は、適当にキーボードを押して作ったものです。以下のような感じになっています。

a.txt

emgo
engw
gnqo
ige
nwroi
pqiog
rneowg
wegnoi
wenpw
wnpe

b.txt

bnwqnbwq
bonri
noag
nowb
qbo

merge関数の中に、buf_a と buf_b という配列がありますが、これは1行分の最大長に末尾の ‘\0’ の分を足した要素数しかありません。これだけあれば、マージ作業が実現できます。逆にこれがないと、a.txt と b.txt のそれぞれの先頭行のうち、どちらを先に取り出すべきか判定できません。


参考リンク



更新履歴

’2018/2/22 要素数を意味している「サイズ」について、「要素数」に表記を改めた。

’2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

’2013/1/6 新規作成。



第4章のメインページへ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る