需要有关代码段的建议

Question

我写了一个"插入"函数来将整数插入到整数数组中.它有效,但我不知道它是否是最好的算法.

这是我的代码:

int* insert(int *dest, size_t len, unsigned int index, int value)
{
int x = 0, i = 0;
int *stackp = calloc(len+1, sizeof(int));

if(index > (len-1)) return dest;

while(x < len) {
    if(x == index) {
        ++x;
    } else {
        *(stackp+x) = *(dest+i);
        ++x, ++i;
    }
}

*(stackp+index) = value;
free(dest);
dest = stackp;

return dest;

}

Answer 1

您的内存分配存在一个主要错误. stackp是一个自动(堆栈)数组,这意味着它的生命周期一旦插入返回就结束.您必须使用其他分配方法.你可以让调用者分配一个新的数组并传入两个指针,或者你可以自己malloc做(不要忘记免费).

但是,其余的看起来都很好.这几乎是非就地插入的唯一算法.使用特殊技巧(例如,一次复制两个整数),您可以更快地完成它. memmove并且memcopy可以在某些体系结构上使用这种优化.

此外,许多算法会stackp[index]在找到位置时写入,而不是在结束时写入.但核心算法基本相同.

另一种方法是就地插入(仅在插入位置之后移动元素),而不是使用新的数组.你经常会扩展realloc.在许多情况下这将是首选,因为它节省了复制时间并避免malloc了新的内存位置(也可能使堆碎片化).

最后,替代数据结构完全是链表.这完全消除了复制元素的需要,但使用更多内存并防止随机访问.