質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.91%

C言語 ヒープソート callocでの領域確保

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 196

junnnnchan

score 18

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define swap(type, x, y) \
    do                   \
    {                    \
        type t;          \
        t = x;           \
        x = y;           \
        y = t;           \
    } while (0)
/*--- 会員データ ---*/
typedef struct
{
    int no;        /* 番号 */
    char name[20]; /* 氏名 */
} Member;
/*--- 会員の番号の昇順比較関数 ---*/
int AscendingMemberNoCmp(const Member *x, const Member *y)
{
    return x->no < y->no ? -1 : x->no > y->no ? 1 : 0;
}
/*--- 会員の番号の降順比較関数 ---*/
int DescendingMemberNoCmp(const Member *x, const Member *y)
{
    return x->no < y->no ? 1 : x->no > y->no ? -1 : 0;
}
/*--- 会員の氏名の昇順比較関数 ---*/
int AscendingMemberNameCmp(const Member *x, const Member *y)
{
    return strcmp(x->name, y->name);
}
/*--- 会員の氏名の降順比較関数 ---*/
int DescendingMemberNameCmp(const Member *x, const Member *y)
{
    return strcmp(y->name, x->name);
}
/*--- 会員データ(番号と氏名)の表示(改行あり)---*/
void PrintLnMember(const Member *x)
{
    printf("%d %s\n", x->no, x->name);
}
/*--- 全データの表示 ---*/
void Print(const Member *data, int *m, int n)
{ //     Print(data, sortindex, ndata);
    int i;
    for (i = 0; i < n; i++)
        PrintLnMember(data + i);
}

void Number_compare(Member *a, int *m, int n, int compare(const Member *y, const Member *z))
{ //heapsort(data, sortindex, ndata, AscendingMemberNoCmp
    int i;
    int max = 9;
    //max == 9;
    for (i = 0; i <= max; i++)
        m[i] = 0;
    /*度数分布表作成*/ //ok
    for (i = 0; i < n; i++)
        m[a[i].no]++;
    /*累積分布表作成*/ //ok
    for (i = 1; i <= max; i++)
    {
        m[i] += m[i - 1];
    }
    /*目的配列の作成*/
    Member *b = calloc(n + 1, sizeof(Member));
    for (i = n - 1; i >= 0; i--)
        b[--m[(a[i].no)]] = a[i];
    /*配列のコピー*/
    for (i = 0; i < n; i++)
        a[i] = b[i];
    if (compare == DescendingMemberNoCmp)
    {
        for (i = 0; i < (n / 2); i++)
            swap(Member, a[n - i - 1], a[i]);
    }
    /*解放*/
    free(b);
    b = NULL;
}

void Name_compare(Member *a, int *m, int n, int compare(const Member *y, const Member *z))
{ //heapsort(data, sortindex, ndata, AscendingMemberNoCmp
    int i;
    int max = 118; //uの10進数
    Member *b = calloc(max, sizeof(Member));
    int *s = calloc(max, sizeof(*m) + 1);
    for (i = 0; i <= max; i++)
        s[i] = 0;
    /*度数分布表作成*/ //ok
    for (i = 0; i < n; i++)
        s[*(a[i].name)]++;
    /*累積分布表作成*/
    for (i = 1; i <= max; i++)
        s[i] += s[i - 1];
    for (i = n - 1; i >= 0; i--)
        b[--s[*(a[i].name)]] = a[i];
    /*配列のコピー*/
    for (i = 0; i < n; i++)
    {
        a[i] = b[i];
    }
    /*降順の場合、昇順で並べた配列を逆順にする*/
    if (compare == DescendingMemberNameCmp)
    {
        for (i = 0; i < (n / 2); i++)
            swap(Member, a[n - i - 1], a[i]);
    }
    /*解放*/
    free(b);
    free(s);
    b = NULL;
    s = NULL;
}
/*--- ヒープソート ---*/
void heapsort(Member *a, int *m, int n, int compare(const Member *y, const Member *z))
{ // heapsort(data, sortindex, ndata, AscendingMemberNoCmp);
    //ndata == 8
    if (compare == AscendingMemberNoCmp)
        Number_compare(a, m, n, AscendingMemberNoCmp);
    if (compare == DescendingMemberNoCmp)
        Number_compare(a, m, n, DescendingMemberNoCmp);
    if (compare == AscendingMemberNameCmp)
        Name_compare(a, m, n, AscendingMemberNameCmp);
    if (compare == DescendingMemberNameCmp)
        Name_compare(a, m, n, DescendingMemberNameCmp);
}
/*--- メニュー ---*/
typedef enum
{
    TERMINATE,
    ASCEND_NO,
    ASCEND_NAME,
    DESCEND_NO,
    DESCEND_NAME,
    PRINT_ALL
} Menu;
/*--- メニュー選択 ---*/
Menu SelectMenu(void)
{
    int i, ch;
    char *mstring[] = {
        "番号で昇順ソート", "名前で昇順ソート",
        "番号で降順ソート", "名前で降順ソート",
        "データを表示"};

    do
    {
        for (i = TERMINATE; i < PRINT_ALL; i++)
        {
            printf("(%2d) %-22.22s ", i + 1, mstring[i]);
            if ((i % 3) == 2)
                putchar('\n');
        }
        printf("( 0) 終了 :");
        scanf("%d", &ch);
    } while (ch < TERMINATE || ch > PRINT_ALL);

    return (Menu)ch;
}
/*--- メイン ---*/
int main(void)
{
    Menu menu;
    Member data[] = {
        {1, "takahashi"}, {3, "konishi"}, {5, "ueda"}, {7, "sato"}, {9, "niimi"}, {8, "okonishi"}, {2, "motoike"}, {4, "agemi"}};
    int ndata = sizeof(data) / sizeof(data[0]);
    int i, *sortindex = calloc(ndata, sizeof(int));
    for (i = 0; i < ndata; i++)
        sortindex[i] = i; /* data[]の添字を管理する配列*/
    do
    {
        switch (menu = SelectMenu())
        {
        case ASCEND_NO: /* 番号で昇順にソート */
            heapsort(data, sortindex, ndata, AscendingMemberNoCmp);
            break;
        case ASCEND_NAME: /* 名前で昇順にソート */
            heapsort(data, sortindex, ndata, AscendingMemberNameCmp);
            break;
        case DESCEND_NO: /* 番号で降順にソート */
            heapsort(data, sortindex, ndata, DescendingMemberNoCmp);
            break;
        case DESCEND_NAME: /* 名前で降順にソート */
            heapsort(data, sortindex, ndata, DescendingMemberNameCmp);
            break;
        case PRINT_ALL: /* 全データを表示 */
            Print(data, sortindex, ndata);
            break;
        }
    } while (menu != TERMINATE);
    free(sortindex);
    sortindex = NULL;
    return 0;
}

Name_compare関数の    int *s = calloc(max, sizeof(*m) + 1);
についての質問です。
<質問>
int *s = calloc(max, sizeof(*m) + 1);の場合は、うまく機能するのですが
int *s = calloc(max, sizeof(*m));の場合は、プログラムが強制終了してしまいます。
なぜなのか、原因をご教授お願いします。
ちなみに、*sは*sortindexだと領域が足りないため、増やそうと思い*sというのを宣言しました。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

checkベストアンサー

+1

 int *s = calloc(max, sizeof(*m) + 1);

int* m なので sizeof(*m) すなわち sizeof(int) ... これってたったの 4 ですけど、いいんですか?

[追記] ごめん早トチリ。

0~maxのmax+1個のint領域を確保せにゃならんのなら
calloc(max+1, sizeof(*m)) // sizeof(*m)バイト max+1個分の領域を確保

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/07/22 15:39

    これだとs[max-1]までしか確保していない。という解釈で正しいでしょうか?
    なのでcalloc(max + 1, sizeof(*m))にするのがベストということで解釈しました。

    キャンセル

  • 2020/07/22 15:40

    ですね、配列は0-originで勘定するので 要素数maxだと s[0]~s[max-1] が使える範囲。

    キャンセル

  • 2020/07/22 15:43

    理解できました!ありがとうございます!

    キャンセル

0

    for (i = 1; i <= max; i++)
        s[i] += s[i - 1];

ここでs[max]にアクセスしていますので、calloc(max, sizeof(*m))では足りません。

calloc(max + 1, sizeof(*m))は必要ですが、callocの2引数は単に掛け算するだけですので、 calloc(max, sizeof(*m) + 1)でも余分に取れて問題がなかったのではないかと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/07/22 15:37

    なるほど!
    確認なのですが、”余分に取れて問題がなかった”というのは、sizeof(*m)+1をmax個確保した時に、(+1)*max個の余分な領域があり、そこにs[max]が入る領域が生まれた->s[max]が入れた。と解釈したのですが、ただしいでしょうか?

    キャンセル

  • 2020/07/22 15:42

    そうですね、sizeof(*m)が118より小さければ「sizeof(*m)+1をmax個」の方が大きくなります。

    キャンセル

  • 2020/07/22 15:44

    ありがとうございます!理解できました!

    キャンセル

0

max 個の値」を確保するとインデックスとして許されるのは最小が 0 で最大は max-1 です。

直後の

for (i = 0; i <= max; i++)
        s[i] = 0;

では最後のループで s[max] にアクセスしてしまうので領域外へのアクセスになってしまいます。

要素の大きさを大きく指定しても結果的に確保する要領は必要以上になるので問題なく動くように見えますが、むしろ max の方を max+1 としなければなりません。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/07/22 15:40

    なるほど!
    理解できました。ありがとうございます!

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.91%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る