多次使用 realloc 获取未知大小数组的好方法吗

Question

我将读取一个文件，其中包含一个大小未知的数组像那样

1, 2, 3, ....

5、6、8 ....

该算法使用起来安全且快速吗？

 array =NULL;    /* for realloc */
for(i=0;fgets(line,256,input) != NULL ;++i){
    array =(double**)realloc(array,sizeof(double*)*(i+1));
    value =strtok(line,selector); 
    for(j=0;value != NULL;++j){

        array[i] =(double*)realloc(array[i],sizeof(double)*(j+1));
        sscanf(value,"%lf",&array[i][j]);
        value =strtok(NULL,selector);
    }

}

Answer 1

关于速度：您的算法具有二次复杂度 O(n^2)，其中 n 是每行值的数量或行数。这效率不高。

此问题的正常解决方法是跟踪两个大小，即分配数组的大小和当前正在使用的元素数。通过仅增加当前使用的元素数量（当然，并将值存储在正确的位置）或首先 realloc() 将数组 两次 [=26] 来添加一个值=] 当前大小。这样做的结果是，即使 n 非常大，数组中的平均元素也只会被复制一次。这将复杂度降低到 O(n).

当然，如果您的数组中只有大约十个条目，那么所有这些都是无关紧要的。但是你要求的是速度。

关于安全性：我看到的唯一风险是您通过创建大量临时对象来将您的地址 space 碎片化，这些临时对象只是为了在下一次迭代。这可能导致长运行中的内存饥饿增加，但实际上不可能精确衡量这种影响。

多次使用 realloc 获取未知大小数组的好方法吗

Is it a good way to take an unkown-size array with using realloc many times

c

arrays

malloc

dynamic

realloc