0

以下是 Valgrind 的报告：

==31109== Invalid read of size 8
==31109==    at 0x400D95: Array_Shellsort (in /home/shay/a/ashanbha/368summer/pa2/pa2)
==31109==    by 0x4006CB: main (in /home/shay/a/ashanbha/368summer/pa2/pa2)
==31109==  Address 0x5207238 is 8 bytes before a block of size 240 alloc'd
==31109==    at 0x4C29F73: malloc (vg_replace_malloc.c:309)
==31109==    by 0x400A92: Generate_2p3q_Seq (in /home/shay/a/ashanbha/368summer/pa2/pa2)
==31109==    by 0x400CBE: Array_Shellsort (in /home/shay/a/ashanbha/368summer/pa2/pa2)
==31109==    by 0x4006CB: main (in /home/shay/a/ashanbha/368summer/pa2/pa2)
==31109==
31970.000000
==31109==
==31109== HEAP SUMMARY:
==31109==     in use at exit: 0 bytes in 0 blocks
==31109==   total heap usage: 4 allocs, 4 frees, 9,376 bytes allocated
==31109==
==31109== All heap blocks were freed -- no leaks are possible
==31109==
==31109== For lists of detected and suppressed errors, rerun with: -s
==31109== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

下面是生成函数：

  long *Generate_2p3q_Seq (int n, int *seq_size)
  {
    *seq_size = seqsize(n);
    long *sequence = malloc (sizeof(long) * *seq_size);
    printf("size: %d \n",*seq_size);
    sequence[0] = 1;
    int two = 0;
    int three = 0;
    for (int i = 1; i < *seq_size; i++)
    {
      if ((sequence[two] * 2) > (sequence[three] * 3))
      {
        sequence[i] = sequence[three] * 3;
        three++;
      }
      else if ((sequence[two] * 2) < (sequence[three] * 3) )
      {
        sequence[i] = sequence[two] * 2;
        two++;
      }
      else
      {
        sequence[i] = sequence[two] * 2;
        three++;
        two++;
      }
    }
    return sequence;                                                                                          
  }

以下是我的 shellsort 函数：

 void Array_Shellsort (long *array, int size, double *n_comp)
  {
    int seqsize = 0;
    long * sequencearray = Generate_2p3q_Seq(size,&seqsize);
      long interval = sequencearray[seqsize - 1];
    int i = 1;
    int in,out;
    long temp;
    *n_comp = 0;
    while (interval > 0)
    {
      for (out = interval; out < size; out++)
      {
        temp = array[out];
        in = out;
 
        while (in > interval - 1 && array[in - interval] >= temp)
        {
          array[in] = array[in - interval];
          in -= interval;
          (*n_comp)++;
        }
        array[in] = temp;
        (*n_comp)++;
      }
      i += 1;
      interval = sequencearray[seqsize - i];
    }
    free(sequencearray);
  }

我在 main 中释放了我的实际数组（不是我的序列）。我很好奇是什么导致了 8 的无效读取大小，因为 valgrind 说没有泄漏。我也很好奇 4 个分配器的来源，因为我只为实际数组和序列数组分配。

4

1 回答 1

0

我想出了我的问题的答案。这两行导致问题：

i += 1;
interval = sequencearray[seqsize - i];

这可以通过一个简单的 if 语句来解决，如果它无效则中断（条件是 seqsize - i < 0，它是无效的，你会中断。

于 2020-07-21T05:51:57.530 回答