-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 语言编程了 25 年。我不使用scanf()except 来回答使用它的 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 回答