C言語でブロック移動アルゴリズムを実装した

学習にあたって使用した環境

ideone.com (https://ideone.com/) ※オンライン上でプログラミング学習ができるサイト

参考資料

C言語による最新アルゴリズム辞典 (奥村晴彦著/1991年初版技術評論社：249ページ)

ブロック移動アルゴリズムの概要

文字列内のブロックを入れ替えるアルゴリズムである。

(以下は参考資料により引用)

エディタの命令、例えばテキスト xyz12345abcdefg 中でブロック12345をブロックabcdの後に移動すると、xyzabcd12345efgとなる。この操作は12345とabcdとを交換すること、あるいは12345abcdを右に4文字だけ回転することでもある。

今回は、"PROGRAMMING"と"PRINCIPLES"の2単語で構成される文字列"PROGRAMMINGPRINCIPLES"を、単語を入れ替えて"PRINCIPLESPROGRAMMING"とする処理を実装した。

ソースコード

moveblock.c

/* ブロック移動 block move */

#include <stdio.h>
#include <stdlib.h>

char sentense[] = "PROGRAMMINGPRINCIPLES";

int main(void) {
    printf("%s\n",sentense);
    // 文字列移動関数を呼び出す
    rotate(0, 10, 20);  
    printf("%s\n", sentense);

    return EXIT_SUCCESS;
}

// 文字列反転関数
// 文字列長が奇数の場合には、中央の文字だけは反転しない
void reverse(int i,int j){
    // 置換するためのtmp変数
    int t;
    while(i < j){
        t = sentense[i];
        sentense[i] = sentense[j];
        sentense[j] = t;

        // 処理する文字列位置を一つずつずらす
        i++;
        j--;

        printf("%s i=%d j=%d (reverse)\n", sentense, i, j);
    }
}

// 文字列移動関数
// reverse関数を呼び出す
// 第一引数：入れ替える文字列の左側部分の開始位置
// 第二引数：入れ替える文字列の右側部分の開始位置
// 第三引数：入れ替える文字列全体の文字列
void rotate(int left, int mid, int right){
    reverse(left, mid);
    reverse(mid + 1,right);
    reverse(left, right);
}

実行結果

期待した通りの結果になった。

result.txt(任意)

Success #stdin #stdout 0s 4488KB

PROGRAMMINGPRINCIPLES
GROGRAMMINPPRINCIPLES i=1 j=9 (reverse)
GNOGRAMMIRPPRINCIPLES i=2 j=8 (reverse)
GNIGRAMMORPPRINCIPLES i=3 j=7 (reverse)
GNIMRAMGORPPRINCIPLES i=4 j=6 (reverse)
GNIMMARGORPPRINCIPLES i=5 j=5 (reverse)
GNIMMARGORPSRINCIPLEP i=12 j=19 (reverse)
GNIMMARGORPSEINCIPLRP i=13 j=18 (reverse)
GNIMMARGORPSELNCIPIRP i=14 j=17 (reverse)
GNIMMARGORPSELPCINIRP i=15 j=16 (reverse)
GNIMMARGORPSELPICNIRP i=16 j=15 (reverse)
PNIMMARGORPSELPICNIRG i=1 j=19 (reverse)
PRIMMARGORPSELPICNING i=2 j=18 (reverse)
PRIMMARGORPSELPICNING i=3 j=17 (reverse)
PRINMARGORPSELPICMING i=4 j=16 (reverse)
PRINCARGORPSELPIMMING i=5 j=15 (reverse)
PRINCIRGORPSELPAMMING i=6 j=14 (reverse)
PRINCIPGORPSELRAMMING i=7 j=13 (reverse)
PRINCIPLORPSEGRAMMING i=8 j=12 (reverse)
PRINCIPLERPSOGRAMMING i=9 j=11 (reverse)
PRINCIPLESPROGRAMMING i=10 j=10 (reverse)
PRINCIPLESPROGRAMMING

所感

プログラミング学習環境としてのideone.comは大変使い勝手がよい。利用方法は調べたらもっとありそうなので、今後の課題とする。
やはり、書いて動かしてみると理解が進みやすい。
実際にこのアルゴリズムを製品コードに組み込むケースを想定すると、若干の手直しが必要になりそうと思う。(グローバル変数の文字列をガシガシ編集したりするのはどうなんだろう、という観点)

[C言語アルゴリズム]ブロック移動