文字列のソートの演習
整列
整列 バブルソート、選択ソートの演習
選択ソート
バブルソート
整列 文字列のソートの演習（ここ）
整列 クイックソート、ヒープソートの演習
文字列を読み込んで並べかえる必要がよく生じる。たくさんの文字列の扱いと、整列に必要な文字列の比較について学んでおこう。
文字列と、文字の配列
ひとつの文字列は文字の配列に格納される。 char buf[1024]; とすると、bufは文字(char)の配列で、1024文字まで格納できるので、これで1024文字までの文字列を扱えるが、以下の理由で実際には一文字足りない 1023 文字までである。
C言語では文字列の長さを変数として持たない。このため、終わりをデータ自体に示すことが決められていて、ヌル文字 \0 が用いられる。プログラムでは NUL で記述される。（NULL ポインタとはよく混同されるので気をつける）
https://ja.wikipedia.org/wiki/ヌル終端文字列
C言語には strXXX() という関数が文字列を扱うために標準で用意され、これらの関数では文字列の末尾をヌル文字 \0 で識別する。このため、 buf[1024] に目一杯文字をいれたとしても最後には \0を加えなければならず、意味のある文字は 1023 文字となる。
改行文字
画面に表示された文字列の最後には「改行」が入ることが多い。C言語中では \n で表記する。
このため abc\n という文字列はC言語中では、[a][b][c][\n][\0] という具合に実際には改行とヌル文字の2文字が余分に入っている。
たくさんの文字列の扱い
一つの文字列は文字の配列で、その先頭のポインタ（文字列のポインタ）を使ってプログラムで扱う。
複数の文字列をまとめるときには、「文字列のポインタの配列」を使う。わかりづらいが「ポインタの配列」である。
code:mojiretsunopointer.c
#include<string.h>
#include<stdio.h>
int main(void){
int i;
char s0[] = "a\n"; // "xxx" は「文字列定数」で、見えないけれど最後に \0 が自動的につく
char s1[] = "b\n";
char s2[] = "cc\n";
char *bunsyo3; // 文字列のポインタ が 3個ある配列 = ポインタの配列
bunsyo0 = s0;
bunsyo1 = s1;
bunsyo2 = s2;
printf("%lu\n", sizeof(s0) );
printf("%lu\n", sizeof(s1) );
printf("%lu\n", sizeof(s2) );
for(i=0; i<3; i++){
printf("%s", bunsyoi);
printf("%lu\n", strlen(bunsyoi));
}
}
クイズ
プログラム中の sizeof(s0) は配列 s0 の大きさ、strlen(bunsyo[i]) は文字列bunsyo[i]の長さを示している。なにが違うだろうか。
文字列同士の比較
strcmp(s1, s2) は文字列へのポインタ s1とs2からそれぞれの文字列を辞書順で比較し、s1の方が後ろならプラス、s1とs2が一致するならゼロ、s1の方が前ならマイナス（負の値）を返す。
strcmp("abd", "acb") > 0 と書くと、"abd" のほうが "acb" より辞書で後ろかどうかを判断することになる。この場合は後ろでないのでstrcmp("abd", "acb") はマイナスとなり、strcmp("abd", "acb") > 0 　は偽（1以外）となる。
文字列の並べ替え
たくさんの文字列は文字列のポインタの配列であり、文字列はその一つひとつの要素である。このため、文字列の並び替えは、このポインタを、配列の中で並べ変えればよい。この部分の断片は次のようになる。
code: sortmojiretsu01.c
char * bunsyo10;
readbunsyo(bunsyo);
sortmojiretsu(bunsyo){
int i, j;
char * wp;
for(i= /* .... */ ){
for(j= /*..... */ ){
if(strcmp(bunsyoi, bunsyoj) > 1 ) {
wp = bunsyoi;
bunsyoi = bunsyoj;
bunsyoj = wp;
}
}
}
}
並べ替えを完成させ、以下の全体と組み合わせるとソートするプログラムになる。
文字列を10行読み込み、並べ替えるプログラム
code:mojiretusort.c
#include<string.h>
#include<stdio.h>
int main(void){
char * bunsyo10;
char inputbuf1024;
int n, i;
n = 0;
while(fgets(inputbuf, sizeof(inputbuf), stdin) != NULL){
bunsyon = strdup(inputbuf);　// strdup() は、文字列サイズのメモリ領域を確保( malloc() )して返す。
// この領域は本来、最終的に、free() で開放する必要がある。
n++;
}
printf("%d lines\n", n);
sortmojiretsu(bunsyo, 0, n-1);
for(i=0; i<n; i++){
printf("<%s>\n", bunsyoi);
}
}
クイズ
bunsyho[i] の値を入れ替えることはどういう意味か。図を描いて説明してみよう。
演習
1）sortmojiretsu() を書き、プログラムを完成させよう。
2）プログラムを修正し、1000行の文章データをソートしてみよう。
./mojiretsusort < file1000gyou.txt
#Cプログラミングの演習