終端記号 END (= -1) をもつデータ列二つを,辞書式順序で比較し,その結果を整数値で返す関数を作れ。ただし,データは非負整数(0 以上の整数)であるとする。
ここで,データ列の辞書式順序による比較とは,二つのデータを互いに先頭の要素から順に比較していき,互いに異なる要素に最初に出会ったとき,その要素の大小関係をデータ全体の大小関係と定める比較方法である。
たとえば,{1, 2, 3, 4} と {1, 2, 4, 2} とを比較すると,互いに異なる要素で最初のものは3番目の 3 と 4 とであるので,{1, 2, 3, 4} < {1, 2, 4, 2} という比較結果となる。
ただし,{1, 2, 3} と {1, 2, 3, 4} とのように,一方が他方の先頭部分に含まれるときには,データ長の長い方が大きいとする。したがって, {1, 2, 3} < {1, 2, 3, 4} である。
関数の戻り値は,f(a, b) のように使った場合,次の通りとする。
関数をコーディングする前に,その仕様をきちんと書いておこう。
関数名にある compare は,比較するという意味である。
さて,この問題は,一見難しそうであるが,その比較方法を良く理解すると,驚くほど簡潔にコーディングができる。配列 a, b の最初 a[0]とb[0]とを比較することから始めて,どちらも END ではなくしかも等しい値であればとばして次の要素を見ることを繰り返すことで,文字列の比較がでいる.次の具体的なデータ列を例にとって,その比較過程を見てみる。
a[] = {1, 2, 3, 4, -1}
b[] = {1, 2, 4, 2, -1}
a[0] == b[0], a[1] == b[1] であるが,a[2] != b[2] となっている。
そこで,最後に注目した要素の差 a[2] - b[2] がデータ列 a と b との比較結果となる。
a[] = {1, 2, 3, 4, -1}
b[] = {1, 2, 3, -1}
a[0] == b[0], a[1] == b[1], a[2] == b[2] であるが,b[3] == END である。
ここで,a[3] !=END であるから ,データ列 b の方が短いことが分かり,データ列の比較結果は正の値となる。END == -1
であり正規のデータは正であるから,最後に注目した要素の差 a[3] - b[3] を比較結果とすればよい。
a[] = {1, 2, 3, -1}
b[] = {1, 2, 3, -1}
a[0] == b[0], a[1] == b[1], a[2] == b[2] であるが,a[3] == b[3] == END
となっている。
したがって,二つのデータ列は等しいとがわかり,比較結果は 0 となる。この場合,最後に注目した要素の差 a[3] - b[3]
を比較結果とすればよい。
以上,3通りの場合の比較過程を挙げたが,どの場合も次のような共通の手順で行われている。
したがって,問題の関数は次のようにコーディングできる。
int dataCompare(int a[], int b[]) { int i; for (i = 0; a[i] != END && b[i] != END && a[i] == b[i]; i++); return a[i] - b[i]; }
この関数は,終端記号が正規のデータと比較して小さい,という条件のもとでのみうまく働く。その条件が満たされない場合には,次のようにコーディングする必要がある。
int dataCompare(int a[], int b[]) { int i; for (i = 0; a[i] != END && b[i] != END && a[i] == b[i]; i++); if (a[i] == END && b[i] == END) return 0; if (a[i] == END) return -1; if (b[i] == END) return 1; return a[i] - b[i]; }
dataCompare を用いた例を載せておこう。
main() { int a[] = {1, 2, 3, 4, END}; int b[] = {1, 2, 4, 2, END}; int c[] = {1, 2, 3, END}; printf("%d\n", dataCompare(a, b)); printf("%d\n", dataCompare(a, c)); printf("%d\n", dataCompare(c, c)); }
-1 5 0