任意の個数の任意の長さの文字列の領域を動的に確保、参照する方法は？

Question

前提・実現したいこと

任意の個数の任意の長さの文字列の領域を動的に確保したい、参照したい。

以下の問題をC言語で解くにあたり、障害が発生したのでお力添えください。
https://atcoder.jp/contests/abc042/tasks/abc042_b

辞書順に文字列を連結するというシンプルな問題なのですが、

文字列について、
最初に任意の個数の任意の長さをユーザーに入力させるという仕様があります。

制約に従って当初から静的に文字列の個数や長さを定義することもできるのですが、
理解を深めるために動的に領域を確保することにチャレンジしたいと思います。

mallocをつかった場合 文字列の個数、文字列＋ヌル文字分の1で必要な領域は確保できると思うのですが、
その呼び出し方法（S[i])が間違っているのか正常にprintされません。

どこが間違っているのかご指摘いただけますでしょうか？

該当のソースコード

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

int main(void){
    int N,L;
    char *S;
    scanf("%i %i", &N,&L);

    S = malloc(sizeof(char)*N*(L+1)); //**任意の個数の任意の長さの文字列の領域を動的に確保する方法はこれで正しいのか？**
    for (int i=0; i<N; i++){
        scanf("%*s",N,S[i]);
    }
    //qsort(S,N,sizeof(*S),(int(*)(const void *, const void *))strcmp);　　まだ未検証の部分です


    //以下のループが正常に実行されていないようです（各インデックスの文字列の内容がprintされない）　なにが間違っているのでしょうか？
    for(int i=0; i<N; i++){
        printf("%s",S[i]);
    }


    free(S);

    return 0;

}

補足情報

42tokyoの試験が控えており、C言語で学習しています。(本当は3月試験の予定でしたが、コロナの影響で・・・）

Answer 1

S[i]は*(S+i)と等価です。
つまり先頭からi番目の要素となっており、意図したアドレスへのアクセスになっていません。
&S[i * (L + 1)]ですね。

scanf("%*s",N,S[i]);
書式指定%*sは読み取ったものを格納しません。
引数も誤っています。

あなたがやりたいことは
scanf("%s", &S[i * (L + 1)]);と
printf("%s", &S[i * (L + 1)]);でしょう。

(追記)
printの文字数を指定する書式指定%*sとは異なり、scanfの書式指定%*sは読み捨てを意味しています。
L文字制限をかけたいならこんな感じですね。

    char format[15];
    sprintf(format, "%%%ds%%*[^\n]%%*c", L);
    for (int i = 0; i < N; i++) {
        scanf(format, &S[i * (L + 1)]);
    }

%*[^\n]でL文字を超えた部分の改行文字以外を読み捨て。
%*cで改行文字を読み捨て。

Comments

[omologic]

詳細に解説いただきありがとうございました。

はじめ、まったく意味がわかりませんでしたが、
なるほど、char型のポインタはインデックス1増加につき、1つのchar分しか進まないのですね。

またprintについても &がいる件について、指摘されてはじめて気づきました。

文字列はアドレスを渡さないと%sで表示されないんでしたね・・・

Answer 2

char* の変数 S から S[i] で出てくるのは当然 char です.
printf の "%s" はアドレスを要求しますから, 正常には実行できないでしょう.

考え方としまして, (malloc は成功していると思いますので) malloc の個所で char S[N*(L+1)]; と書いてある"つもり"でその後の処理を書くと良いのではと思います.

Comments

[omologic]

ご回答ありがとうございました。

おかげ様で、char型のポインタ変数に対して、インデックスを使っても、
勝手に文字列に合わせて進んでくれるものではないということを理解できました。

Answer 3

領域を確保するのはmalloc関数でできます
確保した領域を開放するのはfree関数です

ここらへんのキーワードでぐぐれば解説が出てきますね

んで、

    printf("%s",S[i]);

これが間違っています
フォーマット文字列%sは文字列を指定します。が、char型を引数にしてますんで、でたらめな出力しますね

Comments

[omologic]

ご回答ありがとうございます。

はい、ご指摘のとおりmallocを使うだろうというところは予想できたのですが（掲載ソースコードのとおり）、
インデックスでうまく文字列を表示することができず、なにが間違っているのか見当がついていない状況です。自分なりにググってみましたが、適切な情報を見つけることができませんでした。

[y_waiwai]

回答に追記しています

[omologic]

文字列の取り扱いがよく分からなかったんですが、char型のポインタだとインデックス1増加につき、あくまで1バイトずつしかすすまないってことなんですね。　あいまいな理解だったのですがようやく理解できました。ありがとうございます。

[y_waiwai]

１．Sに領域確保したアドレスを代入してるが、そのSの中身はなにも設定していない。
　　Sの中身はデタラメの内容となる
２．Sに入っている文字列を出力するなら、
printf("%s",S);
とするべし。
しかし、1.の指摘のように、Sの内容は初期化されてないので、これでもデタラメの内容が出力される

Answer 4

文字長チェックとかばっさり省略

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

int comp(const void* px, const void* py) {
  const char* x = *(const char**)px;
  const char* y = *(const char**)py;
  return strcmp(x,y);
}

int main(void){ 
  char** table;
  char* result;
  int N;
  int L;
  scanf("%d", &N);
  scanf("%d", &L);
  
  table = (char**)malloc(sizeof(char*)*N);
  int i;
  for ( i = 0; i < N; ++i ) {
    table[i] = (char*)malloc(L+1);
    scanf("%s", table[i]);
  }
  qsort(table, N, sizeof(char*), comp);
  result = (char*)malloc(N*L+1);
  *result = '\0';
  for ( i = 0; i < N; ++i ) {
    strcat(result, table[i]);
    free(table[i]);
  }
  free(table);
  puts(result);
  free(result);
  return 0;
}

Comments

[omologic]

qsortの実装までご教示いただきまして、ありがとうございます。
丁度つまづいていたところなので、大変助かりました。

見当違いの質問かもしれませんが、ソート対象がchar型のポインターのポインターかと思うのですが、qsortで使う要素サイズの指定に sizeof(char**) ではなく、sizeof(char*)を使っているのは、どのみちchar型のポインターもポインターのポインターも同じサイズだから、ということでしょうか？

[episteme]

> qsortで使う要素サイズの指定に sizeof(char**) ではなく、sizeof(char*)を使っているのは

要素の型が char* なので要素サイズは sizeof(char*) です。

[omologic]

あ、確かにそうですね＾＾；

ポインターのポインターを使うケースがいままであまりなかったため、頭が混乱しておりました・・・。

一歩前進、成長出来た気がします！
本当にありがとうございます！

Answer 5

なにはともあれ、scanfのデータを受け取るところとか、printfの"%s"に対応するところにポインタが指定されていない時点でどうあがいてもダメでしょ。

2次元配列を考えてて、うまく行かなくて1次元にしたけどなんだか中途半端に前の考えが残っちゃってる、とかいうところかしら?
mallocによる確保の仕方はとりあえずそれでOK。
(追記:本当は失敗したときのチェックをいれるのがお作法)

さてどう格納すべきか。
今のプログラム、どうしようもなく間違っているけどその間違い方からすると
S[0]～0番目の文字列
S[1]～ 1番目の文字列
S[2]～ 2番目の文字列
とか考えてないかしら?
もしそう格納すると、0番めに"Hello", 1番めに"World"を格納すると、
0番めを格納した時点でHello
1番めはS[1]から重なるからHWorld
になっちゃうでしょ。

そこの格納の仕方はこうなるはず。
S[0]～S[L]: 0番めの文字列
S[L+1]～S[2L+1]:1番めの文字列
S[2(L+1)]～S[3L+2]:2番めの文字列
<以下略>
一般化すれば
S[i*(L+1)]～L+1文字分、ということですね。
なので、配列のその場所に取り込むscanfは
scanf("%s",&S[i*(L+1)])あるいは同じことだけどscanf("%s",S+i*(L+1))
対応するprintfは
printf("%s",&S[i*(L+1)])あるいはprintf("%s",S+i*(L+1))
になるでしょう。

---

あるいは、コンパイラがgccやclangであれば可変長配列が使えるので、要素数Nの配列へのポインタ(つまり二次元配列)を動的に宣言出来るから、この場合は

int main(void){
    int N,L;
    scanf("%i %i", &N,&L);

    char (*S)[L+1] = (char(*)[L+1])malloc(sizeof(char)*N*(L+1));//確保する領域サイズは先と変わらない
    //これで、S[N][L+1]という二次元配列を確保したことになる
    for (int i=0; i<N; i++){
        scanf("%s",S[i]);
    }
<略>
    for(int i=0; i<N; i++){
        printf("%s",S[i]);
    }

というのもあり。

---

今回はそうする必然性はないけれど、二次元のデータ構造を格納する時のパターンのひとつとしては

int main(void){
    int N,L;
    scanf("%i %i", &N,&L);

    char** S=(char**)malloc(sizeof(char*)*N);//今度は確保の仕方が違う
    for(int i=0; i<N; i++){
        S[i]=(char*)malloc(sizeof(char)*(L+1));
    }
    for (int i=0; i<N; i++){
        scanf("%s",S[i]);
    }
<略>
    for(int i=0; i<N; i++){
        printf("%s",S[i]);
    }

というのも知っておくべき。ただし、これはCの文法でいう「二次元配列」とは違うというのは覚えておいたほうがいい。(Javaだとこういうのを二次元配列というのがまたややこしい)

---

最後に、どうでもいいといえばどうでもいいけど、「障害が発生した」という言い方は、コンピュータのシステムを扱っているギョーカイではユーザーじゃなくてシステム側に問題が出たことの意味だったりする。今回の話にはちょっと不適切。

---

追記。
printfでは書式指定子中に"*"があるとパラメータから取り込んだ数値に置き換えてくれる機能があって、scanfでもそれが使えるような勘違いをしたので修正したわけですけれど、そういうことをしたいのなら

char format[32];
int L=10;
sprintf(format,"%%%ds",L); //結果、formatは"%10s"という文字列になる
scanf(format,S[i]); //書式指定子は文字列リテラルである必要はない

なんていう手段はあります。

Comments

[SHOMI]

>配列のその場所に取り込むscanfはscanf("%*s",L,&S[i*(L+1)])あるいは同じことだけどscanf("%*s",L,S+i*(L+1))
文字数を指定できるprintfの書式指定"%*s"とは異なり、scanfの書式指定"%*s"は読み取っても格納しないことを示しているのでだめですよ。

[omologic]

>thkanaさん

ご指摘のとおり、二次元配列をイメージしていたんですが、
領域確保する時点で、一次元配列でしかないことに気付き、インデックスの挙動がうまくわからないまま実装を進めていました。

gccを使っているので可変長配列が使えます。
多くの書籍では可変長配列の方法を紹介していないみたいなので、使わない方がよいのかと思っていました。そうでもないんでしょうか？

ポインターのポインターを使って二次元配列風に取り扱うことが出来るんですね
当初この方法みたいなのがあればな、と思っていたので、こちらを試しに実装してみます。

[omologic]

>SHOMIさん

scanfは*を使えないの知らなかったので指摘助かりました。
scanfは入力文字数を変数を参照して制限できないということになりますよね？

[SHOMI]

>多くの書籍では可変長配列の方法を紹介していないみたいなので、使わない方がよいのかと思っていました。そうでもないんでしょうか？
gccが独自サポートしていた可変長配列(VLA)はC99標準に取り込まれましたが、その後C11でオプションに格下げされました。
C++でもサポートされていません。
そのためでしょうね。
移植性を気にしなくてよい競技プログラミングで使う分には問題ないでしょう。

[SHOMI]

>scanfは入力文字数を変数を参照して制限できないということになりますよね？
はい。

[thkana]

scanfの"*"は...失念していました。修正します。

可変長配列は、事実上gccとclangの「ローカル拡張」になってしまっているので、そこで閉じた世界なら(事実上Windows/Microsoft Cが絡まないなら)あり、互換性を気にするなら非推奨、というところでしょうか。競技プログラミングはgccっぽいので紹介しましたが、テクニックの優先順位的に紹介は最後に持っていったほうがよかったかな。
(使えそうだから(?)独自拡張でgccが取り入れて規格化までしたけれどCの拡張に熱心でないMSが突っぱねてオプション規格に落ちた、なんてストーリーなんでしょうかね)

[omologic]

いろいろご解説ありがとうございました。

できるだけ現場準拠で学んでいければと思っております。
まぁ、現場ごとに違うというだろうから、手段は複数持っておけるようにしたいと思います。複数種のやり方を教えていただきありがとうございました。