-1

私はこのコードをCで記述しましたが、小さな入力や考えられるすべてのテストケースでうまく機能します。ただし、大きなファイルを入力として指定すると、SIGABRTエラーが発生します。誰かが私にその理由を説明できますか？

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

void q_sort(char **numbers, int left, int right)
{
    int  l_hold, r_hold,temp;  
    char *pivot;

    l_hold = left;
    r_hold = right;
    pivot = numbers[left];

    while (left < right)
    {
        while (strcmp(numbers[right],pivot)>=0 && (left < right))
            right--;

        if (left != right)
        {
            numbers[left] = numbers[right];
            left++;
        }

        while (strcmp(numbers[left],pivot)<0 && (left < right))
            left++;

        if (left != right)
        {
            numbers[right] = numbers[left];
            right--;
        }
    }

    numbers[left] = pivot;
    temp = left;
    left = l_hold;
    right = r_hold;

    if (left < temp)
        q_sort(numbers, left, temp-1);

    if (right > temp)
        q_sort(numbers, temp+1, right);
}

int main()
{   
    int x,y,i,j;
    int *arr;
    char **str;
    int *count;
    while(1)
    {
        scanf("%d%d",&x,&y);
        if(x==0 && y==0)break;
        str =(char **)malloc(sizeof(char *)*x);
        count=(int*)malloc(sizeof(int)*x);
        i=0;
        while(i<x)
        {
            str[i]=(char *)malloc(sizeof(char)*y);
            scanf("%s",str[i]);
            i++;
        }
        //sizeof(str)/sizeof(*str)
        q_sort(str,0,x-1);// sizeof(str) / sizeof(char *), sizeof(char *),cmp);
        i=0;
        j=0;
        arr=(int *)malloc(sizeof(int)*x);
        while(i<x)
        {
            arr[j]=1;
            while(i<x-1 && strcmp(str[i],str[i+1])==0)
            {
                i++;
                arr[j]+=1;
            }
            j++;
            i++;
        }

        for(i=0;i<x;i++)
        {
            count[i]=0;
        }
        i=0;
        while(i<j)
        {
            count[arr[i]-1]++;
            i++;
        }
        for(i=0;i<x;i++)
        {
            printf("%d\n",count[i]);
        }
        free(count);
        free(arr);
        for(i=0;i<x;i++)
            free(str[i]);
        free(str);

    }
    return 0;
}
4

1 に答える 1

1

与えられたデータ ファイル:

20 20
absinthe000001
absinthe000002
...
absinthe000020

Valgrind は (繰り返し) 警告します。

==27941== Conditional jump or move depends on uninitialised value(s)
==27941==    at 0xCB9A: strcmp (mc_replace_strmem.c:721)
==27941==    by 0x100000AAB: q_sort (qs.c:16)
==27941==

また、1 または 0 を含む一連の行も取得します。

下付き文字が制御不能になっています。クイックソートルーチンに添字の出力を追加して、何が問題なのかを確認してください。データを読み取った後に印刷を追加して、データが想定どおりであることを確認します。

あなたは言う：

小さな入力と私が考えることができるすべてのテストケースでうまく機能します

私がしようとすると：

0 20

入力として、それはひどく誤動作します:

==28056== 
==28056== Invalid read of size 8
==28056==    at 0x100000A63: q_sort (qs.c:12)
==28056==  Address 0x100006160 is 0 bytes after a block of size 0 alloc'd
==28056==    at 0xB823: malloc (vg_replace_malloc.c:266)
==28056==    by 0x100000BB7: main (qs.c:57)
==28056==

私がしようとすると：

1 20
absinthe000001

1 の長いストリームが出力されます。私がしようとすると：

2 20
absinthe000001
absinthe000002

0 と 1 が交互に続く長いストリームが得られます。率直に言って、あなたは多くのケースを試したとは思いません。ソート コードは、0、1、2 行を正しく処理できる必要があります。

もちろん、問題の一部は、ループがあり、呼び出しwhile (1)をチェックしないことです。scanf()

while(1)
{
    scanf("%d%d",&x,&y);

間違ったテスト！

while (1)
{
    if (scanf("%d%d", &x, &y) != 2)
        break;

使用しないでくださいscanf()。初心者のプログラマーが正しく使用するのは非常に困難です。私が C でプログラミングしたのは、四半世紀以上前のことです。scanf()それを使用するSOの質問に答える以外は使用しません。私はfgets()行を読んでsscanf()解析するために使用します。正しく処理するのははるかに簡単で、より良いエラー報告を得ることができます (scanf()壊れた後に残ったものだけでなく、エラーのある行全体を報告できるため)。

char buffer[4096];

while (fgets(buffer, sizeof(buffer), stdin) != 0)
{
    if (sscanf(buffer, "%d%d", &x, &y) != 2)
        break;
    str = (char **)malloc(sizeof(char *)*x);
    count = (int*)malloc(sizeof(int)*x);
    for (i = 0; i < x; i++)
    {
        if (fgets(buffer, sizeof(buffer), stdin) != 0)
            break;
        str[i] = (char *)malloc(sizeof(char)*y);
        if (sscanf(buffer, "%s", str[i]) != 1)
            break;
    }

malloc()呼び出しの結果を確認する必要があります。失敗すると、セグメンテーション違反または同様のエラーが発生します。おそらく、データを に読み込む際のオーバーフローを防ぐフォーマット文字列を作成する必要がありますstr[i]。

于 2012-12-21T18:07:00.107 に答える