c - 在某些测试用例之后，堆被损坏

Question

#include <cstdlib>
#include <stdio.h>
int *starting_time = NULL;
int *frequency_time = NULL;
int *duration_time = NULL;
int *toured_cities = NULL;


int check(int t,int i,int s, int a){
    int k; int p=starting_time[i];
    while (1){
        k= p+frequency_time[i];
        if (k>a) return p;
        else if ((k-t)>=s) return k;
        p=k;
    }
}

void sight_seeing(){
    int c,s,a; int size=4;
    scanf("%d\n%d\n%d",&c,&s,&a);
    starting_time=(int *)realloc(starting_time,size*sizeof(int));
    frequency_time=(int *)realloc(frequency_time,size*sizeof(int));
    duration_time=(int *)realloc(duration_time,size*sizeof(int));
    toured_cities = (int *)realloc(toured_cities,size*sizeof (int));

    for (int i=1;i<c;i++){
        scanf("%d",&starting_time[i]);
        scanf("%d",&frequency_time[i]);
        scanf("%d",&duration_time[i]);
        toured_cities[i]=0;
    }    
    int t = 0;int x = 0;int i=1;int k;bool q;
    while (t<a){
        if (i==c) break;
        if ((starting_time[i]-t)>=s) {
            k=starting_time[i]; 
            x++;
        }
        else{
            k = check(t,i,s,a);
            if ((k+duration_time[i])<a) x++;
            else if ((k+duration_time[i])==a)
            {
                if (i<c-1) k=starting_time[i];
            }
        }
        t=k+duration_time[i];
        if (t>a) toured_cities[i]=0;
        else toured_cities[i]=1;
        i++;
    }
    for (int i=1;i<c;i++){
        if (toured_cities[i]==1) q=1;
        else q=0;
    }
    if (q==1 && x>=0) printf("The maximum sightseeing possible %d \n",x);
    else printf("\nSightseeing is not Impossible\n");
    starting_time = (int *)realloc(starting_time,0);
    frequency_time = (int *)realloc(frequency_time, 0);
    duration_time = (int *)realloc(duration_time,0);
    toured_cities = (int *)realloc(toured_cities,0);
}


int main(int argc, char** argv) {
    int n;
    scanf("%d",&n);
    while (n--){
        sight_seeing();
    }
    return 0;
}

这是我的代码。此代码通过小于 10 的测试用例。但是对于测试用例 100。我收到此错误。

          *** Error in `./prog': free(): invalid next size (fast): 
           0x00002b2db77fac20 ***
            ======= Backtrace: =========
           /lib/x86_64-linux-gnu/libc.so.6(+0x70bcb)[0x2b2db738dbcb]
           /lib/x86_64-linux-gnu/libc.so.6(+0x76f96)[0x2b2db7393f96]
           /lib/x86_64-linux-gnu/libc.so.6(+0x7778e)[0x2b2db739478e]
           ./prog(+0xcd3)[0x2b2db643acd3]
           ./prog(+0x875)[0x2b2db643a875]
           /lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf1)
           [0x2b2db733d2b1]
           ./prog(+0x93a)[0x2b2db643a93a]
            ======= Memory map: ========
           2b2db643a000-2b2db643b000 r-xp 00000000 fd:00 17031175                   
            /home/S5BAtg/prog
            2b2db643b000-2b2db643f000 rw-p 00000000 00:00 0  
              2b2db6448000-2b2db644d000 rw-p 00000000 00:00 0    
              2b2db663b000-2b2db663c000 r--p 00001000 fd:00 17031175                   
            /home/S5BAtg/prog  
            2b2db663c000-2b2db663d000 rw-p 00002000 fd:00 17031175                   
            /home/S5BAtg/prog

这是错误，我收到了。另外，请帮我分析一下代码的复杂性。

Answer 1

主要问题是:

• 您仅为 5 个条目重新分配数组。一旦您读取了 6 的值对于 c ，您可以访问和修改超出这些数组末尾的条目。

还有很多问题:

• 您不能从 C 中的运行时表达式初始化全局对象:int *starting_time = (int *)malloc(sizeof(int));是无效的。实际上，您必须将此代码编译为 C++ 并提供头文件 <cstdlib> .请注意，如果您只是将这些数组指针初始化为 NULL，您的代码将工作相同或者让它们保持未初始化和全局状态。

• 具有短名称的全局变量，如 int c,s,a;被认为是糟糕的风格并且容易出错。您应该将所有这些变量设为本地变量 sight_seeing()功能。

• 数组在 C 中是基于零的，循环 for (int i=1;i<c;i++)只迭代 c-1次，这可能不是故意的。

• 用于验证是否可以完成完整游览的循环中存在逻辑错误:q是为每个城市设置的，因此它的值只反射(reflect)了最后一个城市是否可以访问。

这是一个改进的版本:

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

int check(int t, int i, int a, int s, int *starting_time, int *frequency_time) {
    int k;
    int p = starting_time[i];
    while (1) {
        k = p + frequency_time[i];
        if (k > a)
            return p;
        else
        if (k - t >= s)
            return k;
        p = k;
    }
}

void sight_seeing(void) {
    int c, s, a;

    if (scanf("%d\n%d\n%d", &c, &s, &a) != 3) {
        printf("invalid input\n");
        exit(1);
    }
    int *starting_time = (int*)calloc(c, sizeof(int));
    int *frequency_time = (int*)calloc(c, sizeof(int));
    int *duration_time = (int*)calloc(c, sizeof(int));
    int *toured_cities = (int*)calloc(c, sizeof(int));

    if (!starting_time || !frequency_time || !duration_time || !toured_cities) {
        printf("cannot allocate memory\n");
        exit(1);
    }
    for (int i = 0; i < c; i++) {
        if (scanf("%d%d%d", &starting_time[i], &frequency_time[i], &duration_time[i]) != 3) {
            printf("invalid input\n");
            exit(1);
        }
    }    
    int t = 0;
    int x = 0;
    int i, k;
    bool q;

    for (i = 0; i < c && t < a; i++) {
        if (starting_time[i] - t >= s) {
            k = starting_time[i]; 
            x++;
        } else {
            k = check(t, i, a, s, starting_time, frequency_time);
            if (k + duration_time[i] < a)
                x++;
            else
            if (k + duration_time[i] == a) {
                if (i < c - 1)
                   k = starting_time[i];
            }
        }
        t = k + duration_time[i];
        if (t > a)
            toured_cities[i] = 0;
        else
            toured_cities[i] = 1;
    }
    q = 1;
    for (int i = 0; i < c; i++) {
        if (toured_cities[i] == 0) {
            q = 0;
            break;
        }
    }
    if (q == 1 && x >= 0)
        printf("The maximum sightseeing possible %d \n", x);
    else
        printf("\nSightseeing is not Impossible\n");  // not sure what you mean?

    free(starting_time);
    free(frequency_time);
    free(duration_time);
    free(toured_cities);
}


int main(int argc, char **argv) {
    int n;
    if (scanf("%d", &n) == 1) {
        while (n-- >0) {
            sight_seeing();
        }
    }
    return 0;
}