0

以下の文は5つの数値の入力を受け取ってnumberlistとして値を返すプログラムです。
双方向リストの勉強をしています。今回のコードは片方向リストです

最後にあるwhileループだけカンマを出力しないようにしたいのですが、こういうときはどうするのが最も空間計算量が少なくて済みますか?

一応、endという構造体のアドレスをつくってi=4のときに結びつけるようにしたつもりなのですがうまくいきません。

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

struct number{
  int num;
  struct number *next;
};

int main(){
  struct number *p, *head, *end;
  end=(struct number *)malloc(sizeof(struct number));
  int i;
  printf("input 5 number:");
  for(i=0;i<5;i++){
    if(i==0){
      p=(struct number *)malloc(sizeof(struct number));
      head=p;
      if(i==4){
        end=p;
        p->next=NULL;
      }
    }else{
    p->next=(struct number *)malloc(sizeof(struct number));
    p=p->next;
    }
    scanf("%d", &p->num);
    p->next=NULL;
  }
  p=head;
  printf("number list:");
  while(p!=NULL){
    if(p==end){
      printf("%d", p->num);
      p=p->next;
    }else{
    printf("%d, ", p->num);
    p=p->next;
    }
  }
  printf("\n");
  return 0;
}
4
  • 空間計算量というモノがよく分からないのですが、p->nextNULL値かどうかで判断する方法があります。 while(p!=NULL){ printf("%d%s", p->num, (p->next ? ", " : "")); p=p->next; }
    – user39889
    Commented 2019年11月3日 6:57
  • このコードにおいて、 end は不要に見えます(@metropolis 氏の指摘する通り、 p->nextNULL であることが終端を表しているので)
    – PicoSushi
    Commented 2019年11月3日 7:09
  • @PicoSushi さん、リストを作っていく際にはendが有った方が良いのでは?
    – kunif
    Commented 2019年11月3日 7:16
  • 確かにそうですね、今回のコードについてのみ注目していました。
    – PicoSushi
    Commented 2019年11月4日 11:17

4 件の回答 4

2

こんな風に考えられます。

  • 変数は初期化しておきましょう。

    struct number *p, *head, *end;
    
  • これは不要です。

    end=(struct number *)malloc(sizeof(struct number));
    
  • i0の時しか実行されない部分でi4か判定しても意味が無いですよ。
    なのでwhileループでのif(p==end){の判定は常に成功しません。

    if (i == 0) {
        ...
        if (i == 4) {
            end = p;
            p->next = NULL;
        }
    }
    
  • forループは他の処理も色々と冗長です。

まとめると以下のようになります。

int main() {
    struct number * p = NULL, * head = NULL, * end = NULL; // 変数は初期化する
    //end = (struct number*)malloc(sizeof(struct number)); // これは不要です
    int i;
    printf("input 5 number:");
    for (i = 0; i < 5; i++) {
        // ループ内の処理を整理
        p = (struct number*)malloc(sizeof(struct number));
        p->next = NULL;
        if (i == 0) {
            head = p;
        }
        else {
            end->next = p;
        }
        end = p;
        scanf("%d", &p->num);
    }
    p = head;
    printf("number list:");
    while (p != NULL) {
        // 元の処理に近いならこちら
        if (p == end) {
            printf("%d", p->num);
        }
        else {
            printf("%d, ", p->num);
        }
        // あるいは @metropolis さんコメントの以下の処理にする
        //printf("%d%s", p->num, (p->next ? ", " : ""));
        p = p->next;
    }
    printf("\n");
    return 0;
}
0

 任意の記号でデータを区切りたいときに使う方法です。
 「区切り記号」の初期値を空文字列としておき、最初の出力後に「区切り記号」に望みの記号を設定します。

 具体的なコードは、以下のとおりです。伽語蓮弥さんのコードを使わせてもらいました。

#include <stdio.h>
#include <stdlib.h>
typedef struct tNumber {
    int current;
    struct tNumber *next;
} TNumber;
int main(const int argc, const char *argv[])
{
    enum { Max = 5 };
    TNumber *ptr = (TNumber *)malloc(sizeof(TNumber));
    TNumber *head = ptr;
    for(size_t idx = 0; Max > idx; ++idx) {
        scanf("%d", &ptr->current);
        ptr->next = (Max - 1 != idx) ? (TNumber *)malloc(sizeof(TNumber)) : NULL;
        ptr = ptr->next;
    }
    ptr = head;
    fprintf(stderr, "number list:");
    char *dlmt = "";    //★追加
    while(NULL != ptr) {
        fprintf(stderr, "%s%d", dlmt, ptr->current);    //★変更
        dlmt = ", ";    //★追加
        ptr = ptr->next;
    }
    fprintf(stderr, "\n");  //★追加
    return EXIT_SUCCESS;
}

「最後にあるwhileループだけカンマを出力しないようにする」点での空間計算量はO(1)です。データ数によらず一定です。
ここで紹介する方法以外の、他の方の方法でもO(1)です。
今回のケースで「空間計算量」という用語を使うのは少し大げさだと思いました。

0

先に回答しましたが、コード全体の書き方を見直しました。
【主な見直しのポイント】

  • 項目毎のメモリ確保
    使用するメモリを一括して確保するようにしました。
    mallocで小さいサイズの領域を多数確保するのは、速度性能の観点でも使用領域量の観点でも不利です。数百のオーダでは問題になりませんが数千を超すオーダの場合は気になります。 

  • 比較演算子の書き方
    変数 演算子 定数

    コンパイラや静的チェックの機能が貧弱だった時代には定数 演算子 変数の書き方も「あり」だと考えていましたが、人間は左から右に読むことが自然ですので、直した方がよいと考えました。
     NULL != ptrを読むとき、視線が変数ptrに動いて、その後にNULLに動くので疲れます。

#include <stdio.h>
#include <stdlib.h>
typedef struct TNumber TNumber;
struct TNumber {
    int value;
    TNumber *next;
};
#define INPUT_DATA_NUM (5)
int main(const int argc, const char *argv[])
{
    TNumber *data = (TNumber *)malloc(sizeof(TNumber) * INPUT_DATA_NUM);
    for(int i = 0; i < INPUT_DATA_NUM; i++) {
        data[i].next = &data[i + 1];
        scanf("%d", &data[i].value);
    }
    data[INPUT_DATA_NUM - 1].next = NULL;

    fprintf(stderr, "number list:");
    char *dlmt = "";
    while(data != NULL) {
        fprintf(stderr, "%s%d", dlmt, data->value);
        dlmt = ", ";
        data = data->next;
    }m
    fprintf(stderr, "\n");
    return 0;
}

業務でプログラムを書くとき(再利用するとき)、使用する領域をヒープ(malloc)も限定することはためらいを覚えます。※mmapや共有メモリなど使用するプロセスによってはアドレスが変わりかねないからです。TNumberのリンクはポインタでなく整数型の変数にしたくなります。※デバッグのときアドレスを計算するのが面倒だというのが本音でもあります。ということで、また別解です。

【リンクに整数型の変数を使用する版】

#include <stdio.h>
#include <stdlib.h>
typedef struct TNumber TNumber;
struct TNumber {
    int value;
    int next;
};
#define INPUT_DATA_NUM (5)
#define DATA_NONE (-1)
int main(const int argc, const char *argv[])
{
    TNumber *data = (TNumber *)malloc(sizeof(TNumber) * INPUT_DATA_NUM);
    for(int i = 0; i < INPUT_DATA_NUM; i++) {
        data[i].next = i + 1; //次のデータ
        scanf("%d", &data[i].value);
    }
    data[INPUT_DATA_NUM - 1].next = DATA_NONE;

    fprintf(stderr, "number list:");
    TNumber *current = data;
    char *dlmt = "";
    for(;;) {
        fprintf(stderr, "%s%d", dlmt, current->value);
        dlmt = ", ";
        if(current->next == DATA_NONE) {
            break;
        }
        current = &data[current->next];
    }
    fprintf(stderr, "\n");
    return 0;
}
0

kunifさんの回答akira ejiriさんの回答を踏まえた回答です。

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

// typedefすると経済的だと思います
// まとめて宣言するべきではありません
/*
struct number{
    int num;
    struct number *next;
};
*/
typedef struct tNumber{
    int num;
    struct tNumber *next;
} TNumber;

// mainの引数が必要ないならvoidにしましょう
//int main(){
int main(void) {
    // マジックナンバーには名前をつけましょう
    enum { MaxDataQty=5 };

    // まとめて宣言するべきではありません
    //struct number *p, *head, *end;

    // 宣言と初期化は同時に出来ます
    // forループの中にあるif文の中身を持ってきました
    // メモリは1回で必要なだけ確保するほうが経済的なようです
    // このまま進めますが、変数の名前は意味が分かりやすいものにするべきです
    TNumber *p = (TNumber *)malloc(sizeof(TNumber) * MaxDataQty);

    // 宣言と初期化は同時に出来ます
    // forループの中にあるif文の中身を持ってきました
    // endの対義語はstartだと思います
    TNumber *start = p;

    // 宣言と初期化は同時に出来ます
    TNumber *end;

    // 上記のように宣言と初期化は同時に出来ます
    // 利用する前に別の値が代入されます
    //end=(struct number *)malloc(sizeof(struct number));

    // for文内でしか利用しないなら後から宣言/初期化出来ます
    //int i;

    // 文字列リテラルは定数として名前をつけるべきです
    printf("input 5 number:");

    // ループカウンタはiでも構いませんが、idxでも長くはないと思います
    // マジックナンバーには名前をつけましょう
    //for(i=0;i<5;i++){
    for (size_t idx = 0; MaxDataQty > idx; ++idx){
        /*
        if(i==0){
            // この中身はループ初回のみ実行されます
            // 変数の初期化なので宣言時に代入することができます
            p=(struct number *)malloc(sizeof(struct number));
            head=p;
            // ここからは最後のループ時に実行されるようにしたいです
            // このif文の外に出します
            if(i==4){
                end=p;
                p->next=NULL;
            }
        }else{
            // この中身は基本的に毎回実行したい内容です
            // このif文の外に出します
            p->next=(struct number *)malloc(sizeof(struct number));
            p=p->next;
        }
        */

        // if文の中から持ってきました
        // マジックナンバーには名前をつけましょう
        //if(i==4){
        if ((MaxDataQty - 1) == idx) {
            // p[idx]が現在のアドレスです
            // ループの最後で毎回更新するように変更するとこのif文が必要なくなります
            //end=p;
            end = &p[idx];

            // p[idx]が現在のアドレスです
            // 3項演算子を利用して代入するので必要なくなりました
            //p->next=NULL;
        }

        // if文の中から持ってきました
        // p[idx]が現在のアドレスです
        // 次の分のメモリは既に確保してあります
        // 3項演算子を利用して最後のループならNULLを代入します
        //p->next=(struct number *)malloc(sizeof(struct number));
        p[idx].next = ((MaxDataQty - 1) != idx) ? &p[idx+1] : NULL;

        // p[idx]が現在のアドレスなので必要なくなりました
        //p=p->next;

        // p[idx]が現在のアドレスです
        //scanf("%d", &p->num);
        scanf("%d", &p[idx].num);

        // 上記で必ず代入されるので必要なくなりました
        //p->next=NULL;
    }

    // endの対義語はstartだと思います
    //p=head;
    p = start;

    // 文字列リテラルは定数として名前をつけるべきです
    printf("number list:");

    while (p != NULL) {
        // 3項演算子を利用すると1行で書くことが出来ます
        // "% d"と書くと数字の前に半角スペースが1個入ります
        // リストの最後でなければ","を最後なら"\n"を数字の後に入れます
        /*
        if(p==end){
            printf("%d", p->num);
            p=p->next;
        }else{
            printf("%d, ", p->num);
            p=p->next;
        }
        */
        printf("% d%s", p->num, ((p != end) ? "," : "\n"));
        p = p->next;
    }

    // ループ内で処理したので必要なくなりました
    //printf("\n");

    // EXIT_SUCCESSはstdlib.hで定義されています
    //return 0;
    return EXIT_SUCCESS;
}

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。