C言語入門講座

トップ>コンテンツ>C言語>13.基本アルゴリズム

 当講座はメールマガジン「Cプロダクション」の2000年5月10日から2002年7月31日までの記事を再編集したものです。

13.基本アルゴリズム

13-1. 文字列の検索
13-2. 文字列の置換
13-3. リスト構造
13-4. セレクションソート
13-5. クイックソート

13-1. 文字列の検索

◇文字列検索(テキスト検索)

 まず、テキストファイルと検索文字列を指定し、標準出力に
マッチした行を抽出して表示するプログラムを作成します。

 前回のテストプログラムにファイル入出力機能を付け加えた
ぐらいの単純なのものです。
 さらに、コマンド引数で指定する様に変更すれば、UNIXとかの
grepコマンドと同じようなものができあがります。

◇サンプルプログラム

#include<stdio.h>
#include<string.h>
int match_str(const char *a, const char *b);

void main()
{
FILE *fp;
int chk;
char a[100],fname[256],sstr[100];
printf("検索されるファイル名 : ");
scanf("%s",fname);
printf("検索文字列 : ");
scanf("%s",sstr);

if( (fp=fopen(fname,"r"))==NULL){
printf("ファイル %s が見つかりません\n",fname);return;
}
while(fgets(a,100,fp)!=NULL){
chk = match_str(a, sstr);
if (chk==1){
printf("%s",a);
}
}
}

int match_str(const char *a, const char *b)
{
    int i=0, j=0, max_a, max_b;
    while(1){
        if(a[i]=='\0'){max_a = i; break;}
        i++;
    }
    i=0;
    while(1){
        if(b[i]=='\0'){max_b = i; break;}
        i++;
    }
    for(i=0;i<max_a;i++){
        if(0==strncmp(&a[i],&b[j],1)){
            if(j==max_b-1){return 1;}
            else{j++;}
        }
    }
    return 0;
}

 尚、このプログラムは漢字等の検索もできましたが、2バイト文字に関する
特殊な処理等は一切しておりませんので2バイト文字を使用したテキストファ
イルに検索をかけた場合、違うものまで検出される場合があります。

13-2. 文字列の置換

 テキストファイルと検索文字列そして置換後の文字列を指定し、
標準出力に表示します。
 それでは早速、プログラミング作成を行ってみましょう。
まず、検索用の関数のアルゴリズムを変更して置換用の関数を作成します。

<関数仕様>
関数名:char *permute_str(const char *a, const char *b, const char *c)
引数 :a 検索の対象となる文字列へのポインタ
    b 検索する文字列へのポインタ
        c 置換する文字列へのポインタ
戻り値:置換後の文字列の先頭アドレス


◇置換用の関数
char *permute_str(const char *a, const char *b, const char *c)
{
    int  i=0, max_a, max_b;
    char result[256];
    result[0] = '\0'; // 念のため最初の文字をNULLにする

    // 文字列の最大文字数(半角)を調べる
    max_a = strlen(a);
    max_b = strlen(b);

    for( i = 0; i <= max_a; i++ ){
        if( 0==strncmp(&a[i], b, max_b) ){
            strcat(result,c);
            i += max_b-1;
        }
        else{
            strncat(result,&a[i],1);
        }
    }
    return result;
}

 先ほど作りました置換関数を利用してファイル全文置換を行うプログラムを
以下に紹介します。

◇サンプルプログラム

#include<stdio.h>
#include<string.h>
char *permute_str(const char *a, const char *b, const char *c);

void main()
{
        FILE *fp_i,*fp_o;
        char *res;
        char a[100],fname[256],fname2[256],sstr[100],cstr[100];
        printf("検索されるファイル名 : ");
        scanf("%s",fname);
        printf("出力先のファイル名 : ");
        scanf("%s",fname2);
        printf("置換前の文字列 : ");
        scanf("%s",sstr);
        printf("置換後の文字列 : ");
        scanf("%s",cstr);

        if( (fp_i=fopen(fname,"r"))==NULL){
                printf("ファイル %s が見つかりません\n",fname);return;
        }
        else{
                fp_o=fopen(fname2,"w");
        }
        while(fgets(a,100,fp_i)!=NULL){
                res = permute_str(a, sstr, cstr);
        fprintf(fp_o,"%s",res);
        }
        fclose(fp_i);
        fclose(fp_o);
        return;
}

char *permute_str(const char *a, const char *b, const char *c)
{
    int  i=0, max_a, max_b;
    char result[256];
    result[0] = '\0'; // 念のため最初の文字をNULLにする

    // 文字列の最大文字数(半角)を調べる
    max_a = strlen(a);
    max_b = strlen(b);

    for( i = 0; i <= max_a; i++ ){
        if( 0==strncmp(&a[i], b, max_b) ){
            strcat(result,c);
            i += max_b-1;
        }
        else{
            strncat(result,&a[i],1);
        }
    }
    return result;
}


◇応用例

 文字列置換の応用範囲は広いのですが、今回作成した置換関数はテキスト
エディタの機能としてはもちろん
(VC++ならわざわざ自作するまでも無い気がしますが)
 CGIとHTMLデザインを分離して開発する場合においては、動的HPの
開発アルゴリズムに加えればかなり作業の効率化が行えます。
 私の場合は、ページデザインの変更があっても更新する必要の無い動的HP
生成CGIやサイトの汎用システムとして開発しています。
 (もっともPerl言語で開発してたりしますが・・・)

 こういう不便から生まれたアイディアやアルゴリズムってあまり教えたくは
無いのですね。(未だにCGI中にHTML書く人が沢山いそうなので)


◇タブ→スペース変換

 前回の文字列を置換を利用して、タブをスペースに変換するプログラムを
作ってみます。

置換関数は前に作ったものを利用します。プログラム的には少しの変更で済み
ますが、今回は汎用性を考えて変更せず以前の仕様のまま利用します。

◇サンプルプログラム

#include<stdio.h>
#include<string.h>
char *permute_str(const char *a, const char *b, const char *c);

void main()
{
        FILE *fp_i,*fp_o;
int i,space;
        char *res;
        char a[100],fname[256],fname2[256],sstr[]="\t",cstr[100];
cstr[0]='\0';
        printf("入力ファイル名 : ");
        scanf("%s",fname);
        printf("出力ファイル名 : ");
        scanf("%s",fname2);
        printf("TAB1つ当たりのスペース数 : ");
        scanf("%d",&space);

for (i=1;i<=space;i++){
strcat(cstr," ");
}

        if( (fp_i=fopen(fname,"r"))==NULL){
                printf("ファイル %s が見つかりません\n",fname);return;
        }
        else{
                fp_o=fopen(fname2,"w");
        }
        while(fgets(a,100,fp_i)!=NULL){
                res = permute_str(a, sstr, cstr);
        fprintf(fp_o,"%s",res);
        }
        fclose(fp_i);
        fclose(fp_o);
        return;
}

char *permute_str(const char *a, const char *b, const char *c)
{
    int  i=0, max_a, max_b;
    char result[256];
    result[0] = '\0'; // 念のため最初の文字をNULLにする

    // 文字列の最大文字数(半角)を調べる
    max_a = strlen(a);
    max_b = strlen(b);

    for( i = 0; i <= max_a; i++ ){
        if( 0==strncmp(&a[i], b, max_b) ){
            strcat(result,c);
            i += max_b-1;
        }
        else{
            strncat(result,&a[i],1);
        }
    }
    return result;
}


◇利用例

 これはまさしくテキストエディタ用としてよく使われる機能です。
気の利いたフリーのエディターでは標準でついていたりしますね。
 また、上記のようなコマンドライン型であれはネット上のテキスト整形に
使えるのでは、と思います。(どちらかというとスペース→タブの方かな?)

 次回は、スペース→TAB変換を予定しています。
自分としてはこちらの方が便利な場面が多く、お役に立てるかと思います。

◇スペース→タブ変換

 今回は、スペース→タブ変換。。。
えっ?前回と同じですって???
いえいえ、別に手抜きではありません。前回の逆変換です(爆)
(・・・それが手抜きのようにみえるんだって!)

・・・それはさておき、
 個人的にも、こちらの方がツールに無い分重宝するときがあります。
このメールマガジンでもそうですが、見た目が人によって相違ないよう
タブは使わずスペースを使っています。
 実は、図を描くときなんか全角と半角を混合するのを避けたりして
レイアウトが崩れるのを避けようと努力したりしてました。

・・・で、スペース→タブ変換ですが、メールマガジンやホームページ
等で掲載されているプログラムソースをコピー&ペーストして使いたい!
というときにインデントされているスペースをタブに変換するのです。
もちろん、プログラムのインデントにはタブのほうが断然便利が良いので
こういう機能こそ汎用テキストエディタにあるととてもうれしいのです。
(そういう意味でVC++のエディタは優秀かも、VBのエディタは中途半端)

プログラムも殆ど前回と変わらないのですが、どこが変わったかご注目(笑)

◇サンプルプログラム

#include<stdio.h>
#include<string.h>
char *permute_str(const char *a, const char *b, const char *c);

void main()
{
        FILE *fp_i,*fp_o;
int i,space;
        char *res;
        char a[100],fname[256],fname2[256],sstr[]="\t",cstr[100];
cstr[0]='\0';
        printf("入力ファイル名 : ");
        scanf("%s",fname);
        printf("出力ファイル名 : ");
        scanf("%s",fname2);
        printf("TAB1つ当たりのスペース数 : ");
        scanf("%d",&space);

for (i=1;i<=space;i++){
strcat(cstr," ");
}

        if( (fp_i=fopen(fname,"r"))==NULL){
                printf("ファイル %s が見つかりません\n",fname);return;
        }
        else{
                fp_o=fopen(fname2,"w");
        }
        while(fgets(a,100,fp_i)!=NULL){
                res = permute_str(a, cstr, sstr);
        fprintf(fp_o,"%s",res);
        }
        fclose(fp_i);
        fclose(fp_o);
        return;
}

char *permute_str(const char *a, const char *b, const char *c)
{
    int  i=0, max_a, max_b;
    char result[256];
    result[0] = '\0'; // 念のため最初の文字をNULLにする

    // 文字列の最大文字数(半角)を調べる
    max_a = strlen(a);
    max_b = strlen(b);

    for( i = 0; i <= max_a; i++ ){
        if( 0==strncmp(&a[i], b, max_b) ){
            strcat(result,c);
            i += max_b-1;
        }
        else{
            strncat(result,&a[i],1);
        }
    }
    return result;
}

 前回のプログラムで理解してる方はすでにお分かりだと思います。
はっきりいって間違い探し並みの変更の少なさです。
(難易度:バグ取りレベル)


13-3. リスト構造

◇サンプルプログラム

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

typedef struct item{
        int number;
        struct item *next;
        int index;
} *pStList;

void main()
{
        int index = 1, number;
        char command[10];
        pStList address = NULL;
        pStList add(int, pStList, int);
        void show(pStList);

        while(1){
                printf("Command ? = ");
                scanf("%s",command);
                if( strcmp(command,"add")==0){
                        printf("入力数値 = ");
                        scanf("%d",&number);
                        address = add(number, address, index);
                        index++;
                }
                else if(strcmp(command,"show")==0){
                        show(address);
                }
                else if(strcmp(command,"exit")==0){
                        return;
                }
                else{
                        printf("Unknown Command ...\n");
                }
        }
}

pStList add(int number,pStList address, int index)
{
        pStList NextList;
        NextList = malloc(sizeof *NextList);
        if ( NextList == NULL ) return NULL;
                NextList->number = number;
                NextList->next = address;
                NextList->index = index;

        return NextList;
}

void show(pStList address)
{
        while( address != NULL ){
                printf("No.%d [%d]\n",address->index, address->number);
                address = address->next;
        }
        printf("\n");
}

本当はデータを文字列にして、1番から順番に表示させたいのですが、
そうするとコードが長くなるのでこの辺にとどめました。(時間切れ)

13-4. セレクションソート

 今週は元の流れにもどって基本アルゴリズムを続けます。
検索・置換ができたので今度はデータの並べ替え(ソート)をやってみます。

 今から説明する選択ソートは並べ替えの方法として最も単純なものです。
単純なだけにプログラムもスマートで分かりやすいのですが、データ量が
増えると処理負担が一気に増大するという欠点もあります。


◇いわゆる選択法

 まずは、選択ソートがどういったものなのか説明します。
ソートしたい配列の先頭から最後尾まで探索し、最小値(または最大値)を
検出します。これを先頭と交換し、2回目の探索は先頭から2番目の要素から
出発します。
 これを繰り返して最後まで到達するとソート終了です。

1.探索開始
 ■□□□□□□□□□□□☆□□□□□□□□□□□□
 ├→

2.最小値決定
 □□□□□□□□□□□□★□□□□□□□□□□□■
             ↑          →|

3.交換
 ☆□□□□□□□□□□□□□□□□□□□□□□□□
 └───────────┘

4.二回目探索
 ☆■□□□□□□□□□□□□□□□□□□□□□□□
  ├─────────────────────→|


こんな感じで最後まで続きます。

◇サンプルプログラム

前回の図をここに引用します。

1.探索開始
 ■□□□□□□□□□□□☆□□□□□□□□□□□□
 ├→

2.最小値決定
 □□□□□□□□□□□□★□□□□□□□□□□□■
             ↑          →|

3.交換
 ☆□□□□□□□□□□□□□□□□□□□□□□□□
 └───────────┘

4.二回目探索
 ☆■□□□□□□□□□□□□□□□□□□□□□□□
  ├─────────────────────→|


#include<stdio.h>

main()
{
int i,arr[]={4,6,2,8,3,1,5,0,9,7};
void selectsort_min(int n, int arr[]);

printf("初期状態 = ");
for(i = 0; i < 10; i++) printf("%d",arr[i]);
printf("\n");

selectsort_min(10,arr);

printf("並び替え = ");
for(i = 0; i < 10; i++) printf("%d",arr[i]);
printf("\n");
}


void selectsort_min(int n, int arr[])
{
int i,j,k,min;

for(i = 0; i < n-1 ; i++){
min = arr[i]; k = i;
for (j = i + 1; j < n; j++ ){
if(arr[j] < min){
min = arr[j];
k=j;
}
}
arr[k] = arr[i];
arr[i] = min;
}
}

/* 実行結果
初期状態 = 4628315097
並び替え = 0123456789
Press any key to continue
*/

この探索法ではデータ数をnとすると、1/2*n(n-1) 回探索します。
つまりnが増えればその2乗に比例して探索回数が増えるので
大きなデータには不向きです。


セレクションソートのサンプルを解説します。

 1:void selectsort_min(int n, int arr[])
 2:{
 3:  int i,j,k,min;
 4:
 5:  for(i = 0; i < n-1 ; i++){
 6:    min = arr[i]; k = i;
 7:    for (j = i + 1; j < n; j++ ){
 8:      if(arr[j] < min){
 9:        min = arr[j];
10:        k=j;
11:      }
12:    }
13:    arr[k] = arr[i];
14:    arr[i] = min;
15:  }
16:}

◇解説
 1:void型selectsort_min関数、第一引数(整数型n)、第二引数(整数配列arr)
 5: 計数iは、全体のサーチの最初の要素番号
 6:   まずサーチの最初の要素をminにセット、同時にiの値をkにセット
 7:   計数jはサーチの現在地
 8:   サーチの途中でminの値より小さいものが見つかれば
 9:     minに要素をセットし
10:      そのときのjをkにセットする。
13:   ここでサーチの最初の要素arr[i]を、最小値arr[k]にセットし
14:   arr[i]にminをセットする

インデント(空白)は実際のループ処理に合わせてあけています。

実際のソートでは数列ではなく、文字列を使うのが普通だと思います。
以後のソート関係は文字列ソートでやってみます。


13-5. クイックソート

◇クイックソートの原理

 クイックソートとは名前の通り速く並べ替えを行うアルゴリズムのことです。
一般的にクイックソートが最も平均的(*1)に速いと呼ばれています。

*1 配列の並び方によって他のソート方法より遅くなることがあります。

(1)
まずは並び替えの方法ですが、最初に配列の中の中間値あたりを基準にします。
理想的なのは最大値と最小値の間くらいの値が望ましいのですが、それは不明
であるため、分割等を考慮して配列の中間の値を基準にします。

(2)
次に、その基準値より、小さいものを前に、大きいものを後ろに交換しながら
配列していきます。

(3)
グループ分けが終了した時点で、基準値より手前が2個以上の要素を持って
いた場合、基準値で分割し、その手前の配列で1→3を実行します。

(4)
手前側の配列が無くなったら次は後ろ側の配列に注目し1→4を繰り返します。

このようにグループ分け→分割を繰り返すことによって並び替えを実現します。
この説明だけでは分かりにくいを思いますので、サンプルプログラムの後に
一例をいれて置きました。


◇サンプルプログラム1

#include <stdio.h>
#include <string.h>
void qsort(char[], int, int);

void main()
{
  char str[256];
    int n;
    printf("Input: ");
  scanf("%s",str);
  n = strlen(str);
    qsort(str, 0, n - 1);
    printf("After: %s\n",str);
    return;
}

void qsort(char str[], int first, int last)
{
    int i, j;
    char x, t;

    x = str[(first + last) / 2];
    i = first;
  j = last;
    for(;;i++,j--) {
        while (str[i] < x) i++;
        while (x < str[j]) j--;
        if (i >= j) break;
        t = str[i];
    str[i] = str[j];
    str[j] = t;
    }
    if (first  < i - 1) qsort(str, first , i - 1);
    if (j + 1 < last) qsort(str, j + 1, last);
}

◇ソートの例1
C-Production と入力した場合

C-Production (d を基準)
   ~ ^ ~
C-Pcodurtion (c と r を交換)
   ~ ^ ~
C-Pcdourtion (o と d を交換)
    ~^
C-Pcdourtion (交換対象無し)
    ^
C-Pcd ourtion (左側分割:P を基準:交換対象無し)
  ^
C- P cd ourtion (左側分割:C を基準)
^
-C P cd ourtion (C と - を交換)
~^
-C P cd ourtion (右側選択:c を基準:交換対象無し)
     ^
-C P cd ourtion (右側選択:o を基準)
           ^
-C P cd onrtiou (u と n を交換)
         ~ ^  ~
-C P cd onroitu (t と o を交換)
           ~ ^
-C P cd onroitu (交換対象無し)
             ^
-C P cd onroi tu (左側分割:r を基準)
          ^
-C P cd onior tu (r と i を交換)
          ~ ^
-C P cd onior tu (交換対象無し)
            ^
-C P cd onio r tu (左側分割:n を基準)
         ^
-C P cd inoo r tu (o と i を交換)
        ~^~
-C P cd inoo r tu (交換対象無し)
         ^
-C P cd in oo r tu (右側分割:o を基準)
           ^
-C P cd in oo r tu (o を交換:実質意味無し)
           ~^
-C P cd in oo r tu (交換対象無し)
            ^
-C P cd in oo r tu (右側選択:t を基準)
                ^
-C P cd in oo r tu (交換対象無し:終了)
                ^
-CPcdinoortu

◇qsort関数の解説

 前回、製作しましたqsort関数を解説します。
理論どおり再帰を使った関数なので、ちょっと難しいかもしれませんが
前回のソート例を見ながら追いかけてみてください。

 1:void qsort(char str[], int first, int last)
 2:{
 3:    int i, j;
 4:    char x, t;
 5:
 6:    x = str[(first + last) / 2];
 7:    i = first;
 8:    j = last;
 9:    for(;;i++,j--) {
10:        while (str[i] < x) i++;
11:        while (x < str[j]) j--;
12:        if (i >= j) break;
13:        t = str[i];
14:    str[i] = str[j];
15:    str[j] = t;
16:    }
17:    if (first  < i - 1) qsort(str, first , i - 1);
18:    if (j + 1 < last) qsort(str, j + 1, last);
19:}

1:関数の定義の開始
  str[] ソートの対象にする文字列
  first 文字列の先頭の要素番号
  last  文字列の最後の要素番号

3〜4:変数の宣言
  i 基準より手前側の要素の位置
  j 基準より後ろ側の要素の位置
  x 基準値(文字)
  t 値交換用の変数(Tempのt)

6:基準値の決定
  対象となる文字列の中間点の文字を基準値にします

7〜8:前方・後方それぞれの開始点をセット

9〜15:クイックソート
  前方・後方より基準値と比較して交換対象になる値を探し、
  最初に見つかった場所通しで交換をします。
  交換が終わったら、開始点を一つ中央に寄せて繰り返します。

17:前方部分の分割
  9〜15で交換が出来なくたったとき、基準値の前方の配列が2つ以上の
  要素を持っていれば、分割し前方の配列のみでクイックソートを行います。

18:後方部分のクイックソート
  17でクイックソートが完了したら、残りの後方部分をソートします

19:関数の終わり
  これを再帰的に繰り返すことによって、最終的にソートが完了します


◇スタック方式のアルゴリズム

 クイックソートのアルゴリズム自体は再帰を使いますが、再帰の代わりに
スタックを用いて実現することができます。
再帰を使わずスタックを用いる理由としては、まず再帰が使えない言語でも
利用できるということ、そして再帰では実行時間やメモリーを大量に消費する
場合が考えられます。

 ところでスタックとは何でしょう?
『逆ポーランド記法』でスタックについて解説されることが多いようですが
ついでなのでここで簡単に説明します。

 スタックとはイメージとしてブロックの積み上げのようなものです。
入出力の種別ではFILO(*1)と呼ばれ。最初に入ったデータが最後に出る形式
の配列を意味します。
 それに対して、入力した順番にデータが出されるものをバッファと呼び、
FIFO(*2)形式になっています。イメージとしてはトンネルです。

 説明はここまでで、以下は簡単に図を描いて見ます。

    スタック
   ┌────┐
  ↑│データ4││読
 読│├────┤│み
 み││データ3││込
 込│├────┤│む
 む││データ2││順   下から順に書き込んで行き
 順│├────┤│番   最後に書き込んだデータから
 番││データ1│↓     順番に下に向かって読み込む
───┴────┴───────────────────────────

 これをプログラムで実現する為には、配列やポインタで
データを書き込む度に、要素番号をインクリメントし、
読み込んだときは要素番号をデクリメントします。
 ただし、スタックに使用する容量に十分気をつけないと
スタックオーバーを起こしたとき、プログラムが停止する可能性があります。

*1 FILO (First In Last Out)  ... 先入れ後出し。スタックの方式
*2 FIFO (First In First Out) ... 先入れ先出し。バッファの方式


◇サンプルプログラム2

 それでは、前に出てきたクイックソートプログラムを、スタック仕様で
書き換えてみました。配列の分割部分だけ変わっています。

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

void qsort(char[], int, int);

void main()
{
    char str[256];
    int n;
    printf("Input: ");
    scanf("%s",str);
    n = strlen(str);
    qsort(str, 0, n - 1);
    printf("After: %s\n",str);
    return;
}

void qsort(char str[], int first, int last)
{
    int i, j,p=0;
    char x, t;
    int stack_first[256];
    int stack_last[256];

    while(1){
        x = str[(first + last) / 2];
        i = first;
        j = last;
        for(;;i++,j--) {
            while (str[i] < x) i++;
            while (x < str[j]) j--;
            if (i >= j) break;
            t = str[i];
            str[i] = str[j];
            str[j] = t;
        }

        if (first  < i - 1){
            stack_first[p] = i;
            stack_last[p] = last;
            p++;
            last = i - 1;
            continue;
        }
        if (j + 1  < last){
            first = j + 1;
            continue;
        }
        else {
            p--;
            if(p<0)return;
            first = stack_first[p];
            last = stack_last[p];
            continue;
        }
    }
}

Copyright© 2000-2009 C-Production All Rights Reserved.