Нужен совет по фрагменту кода

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 нового места в памяти (которое также может фрагментировать кучу).

Наконец, альтернативная структура данных полностью представляет собой связанный список. Это полностью исключает необходимость копирования элементов, но использует больше памяти и предотвращает произвольный доступ.

Answer 2

Здесь есть серьезная ошибка. Массив stackp является локальной переменной, и вы возвращаете ее как результат. Вы, вероятно, получите ошибку сегментации, если захотите снова прочитать / записать этот массив вне функции «вставки».

Чтобы исправить это, вам нужно выделить динамический массив, например:

int *stackp; </p> <p>stackp = (int*)malloc(size(int)*(len+1));