Besoin de conseils sur l'extrait de code

Question

J'ai écrit une fonction "insert" pour insérer un entier dans un tableau d'entiers. Cela fonctionne, mais je ne sais pas si c'est le meilleur algorithme.

Voici mon code:

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

Il y a un bug majeur dans votre allocation de mémoire. stackp est un tableau automatique (pile), ce qui signifie que sa durée de vie prend fin dès le retour de l'insertion. Vous devez utiliser une autre méthode d'allocation. Vous pouvez demander à l'appelant d'allouer un nouveau tableau et de passer les deux pointeurs, ou vous pouvez le faire vous-même avec malloc (n'oubliez pas de libérer).

Cependant, le reste semble correct. C'est à peu près le seul algorithme pour un insert non sur place. Vous pouvez être en mesure de le faire un peu plus rapidement avec des astuces spéciales (par exemple copier deux ints à la fois). memmove et memcopy peuvent utiliser de telles optimisations sur certaines architectures.

De plus, de nombreux algorithmes écriraient stackp[index] lorsque la position est trouvée, plutôt qu'à la fin. Mais l'algorithme de base est fondamentalement le même.

Une alternative serait de faire l'insertion sur place (en déplaçant uniquement les éléments après la position d'insertion), plutôt que d'utiliser une nouvelle matrice. Vous développez souvent avec realloc. Cela est préférable dans de nombreuses situations, car il permet d'économiser du temps de copie et d'éviter un nouvel emplacement de mémoire (ce qui peut également fragmenter le tas). Enfin, une autre structure de données est entièrement une liste chaînée. Cela élimine totalement le besoin de copier des éléments, mais utilise plus de mémoire et empêche l'accès aléatoire.

Answer 2

Il y a une erreur grave ici. Le stackp de tableau est une variable locale, et vous le renvoyez comme résultat. Vous obtiendrez probablement une erreur de segmentation si vous voulez lire/écrire à nouveau ce tableau, en dehors de la fonction "insert".

Pour corriger, vous devez allouer un tableau dynamique comme:

int *stackp;

stackp = (int*)malloc(size(int)*(len+1));