Questions fréquentes (FAQ)
Page 1 sur 1
Questions fréquentes (FAQ)
Bonjour a tous. J'aimerais savoir s'il est possible de supprimer un élement d'un tableau dynamique...
J'ai lu a quelque part que c'était impossible.
Est-ce vrai? Et sinon quels sont les alternatives??
Tout est possible. La question est plutôt "est-ce efficace ?"
Pour supprimer un élément d'un tableau, il y a 2 façons de faire :
- Marquer l'élément 'supprimé'. Il faut pour cela soit une valeur particulière, soit un marqueur (flag) dans la structure de données si c'est un tableau de structures. L'élément marqué 'supprimé' est alors ignoré des traitements. Par contre l'accès direct est faussé, à moins de passer par un tableau d'indexation (à mettre à jour à chaque fois qu'on marque un élément 'supprimé').
- Déplacer physiquement tous les éléments suivant l'élément supprimé, de 1 emplacement. C'est couteux (memmove()), au moins une fois, mais ensuite l'accès est direct.
Autre solution, travailler non pas avec un tableau mais une liste chainée. Problème, l'accès est purement séquentiel (mais une indexation est toujours possible).
Tout ceci pour dire que le choix des structures de données dépend fortement de la nature des traitement que l'on compte effectuer. Il n'est pas absurde d'imaginer que les même données soient stockées sous la forme d'une liste chainée pour certains traitements, et sous la forme d'un tableau dynamique pour d'autres traitements. Sachant que la combinaison des deux est toujours possible via un tableau d'index.
Un tableau d'indexation? Il reste que c'est un tableau et qu'il faut supprimer les élements là aussi?
(Mon problème est pour un serveur socket, un tableau de structure pour stocker tous les clients connectés, donc supprimés un quand il se deconnecte...)
Pour ça, une liste chainée est bien adaptée.
Connexion : on ajoute en tête (le plus simple et le plus rapide)
Déconnexion : on supprime où il faut. (Ca peut être n'importe où).
Si je déclare un tableau t[2][2], je voudrais savoir si tous les éléments de ce tableau sont contigüs en mémoire ou non.
Oui, ils sont contigus.
Jusqu'à aujourd'hui, je ne le croyais pas mais plus je cherche, plus c'est confus dans ma tête. J'ai essayé de le découvrir en faisant des tests mais ça reste assez confus.
En gros, pouvez-vous m'expliquer comment ça se passe en mémoire s'il vous plait ?
Il n'y a aucune différence entre un tableau de 1 ou de n dimensions en mémoire. C'est un tableau comme un autre, c'est à dire une succession d'élément identiques et contigus.
La seule chose qui change, c'est la façon de l'indexer. On utilise un index par dimension :
1 dimension N : [i] avec i de 0 à N-1
2 dimensions N et M : [i][j] avec i de 0 à N-1 et j de 0 à M-1
etc.
Mais alors, si un tableau multidimensionnel est stocké de la même manière qu'un tableau unidimensionnel, si dans le tableau tab[2][2],
tab[1][0] = 4;
et
*(tab+2) = 4
Ces instructions produisent-elles le même résultat ?
Non. tab n'a pas le type int * et ne peut être utilisé pour accéder en 1D. Il faut un pointeur séparé de type int * initialisé avec l'adresse de tab et la cast qui va bien (horrible...)
Il vaut mieux s'en tenir aux dimensions définies et laisser les indices dans les plages requises...
Si je fais ceci:
Oui, c'est normal. Ce qui fonctionne, c'est ceci :
Alors en C les tableaux multidimensionnels sont bien représentés simplement comme des tableaux de tableaux ?
Si tu définis "int tab[2][3]" par exemple il y aura un tableau de deux éléments dont chaque élément est un tableau de trois entiers. Donc pour indicer ça tu dois d'abord choisir un des deux tableaux que contient tab (en les indiçant comme des éléments normaux) puis tu te retrouves dans un tableau à une dimension. Avec "int tab[4][5][6]" ça donnerait quatre tableaux de cinq tableaux de six entiers. Si j'ai bien compris...
Concrètement si on fait :
___________
1|2|3|4|5|6|
Donc on peut venir avec un pointeur "pointer" chacun des éléments du tableau :
int *pt = (int*)tab;
ainsi pt[0] = 1
...
pt[5] = 6
Et qu'est-ce que vous pensez de cette pratique ?
C'est la technique du tableau dynamique linéaire à N dimensions. Si c'est bien géré, ça fonctionne. Je recommande l'usage de fonctions 'accesseurs'.
Quand on déclarre ceci :
Et donc, si tab[0] est un int*, tab est un int** qui pointe sur un tableau de 2 int*.
*(*tab+2) car on veut la valeur qui est à l'adresse de la valeur pointé par tab décalé de 2.
Et là, ça t'affiche bien 4.
Avec 3 dimensions, c'est toujours pareil (j'ai laissé volontairement le +0 pour qu'on voit bien où devrait se faire le décalage d'adresse) :
Pour en revenir à ce que tu disais, ici,
On peut donc directement y accéder en faisant :
*(*(*(tab))+5)
Donc au final, ça fait *(**tab+5)
Je pense que c'est cette forme que tu cherchais au tout début.
- Code:
int *mallocedInt = NULL;
mallocedInt = malloc(sizeof(int) * 10);
mallocedInt[6] = 222;
J'ai lu a quelque part que c'était impossible.
Est-ce vrai? Et sinon quels sont les alternatives??
Tout est possible. La question est plutôt "est-ce efficace ?"
Pour supprimer un élément d'un tableau, il y a 2 façons de faire :
- Marquer l'élément 'supprimé'. Il faut pour cela soit une valeur particulière, soit un marqueur (flag) dans la structure de données si c'est un tableau de structures. L'élément marqué 'supprimé' est alors ignoré des traitements. Par contre l'accès direct est faussé, à moins de passer par un tableau d'indexation (à mettre à jour à chaque fois qu'on marque un élément 'supprimé').
- Déplacer physiquement tous les éléments suivant l'élément supprimé, de 1 emplacement. C'est couteux (memmove()), au moins une fois, mais ensuite l'accès est direct.
Autre solution, travailler non pas avec un tableau mais une liste chainée. Problème, l'accès est purement séquentiel (mais une indexation est toujours possible).
Tout ceci pour dire que le choix des structures de données dépend fortement de la nature des traitement que l'on compte effectuer. Il n'est pas absurde d'imaginer que les même données soient stockées sous la forme d'une liste chainée pour certains traitements, et sous la forme d'un tableau dynamique pour d'autres traitements. Sachant que la combinaison des deux est toujours possible via un tableau d'index.
Un tableau d'indexation? Il reste que c'est un tableau et qu'il faut supprimer les élements là aussi?
(Mon problème est pour un serveur socket, un tableau de structure pour stocker tous les clients connectés, donc supprimés un quand il se deconnecte...)
Pour ça, une liste chainée est bien adaptée.
Connexion : on ajoute en tête (le plus simple et le plus rapide)
Déconnexion : on supprime où il faut. (Ca peut être n'importe où).
Si je déclare un tableau t[2][2], je voudrais savoir si tous les éléments de ce tableau sont contigüs en mémoire ou non.
Oui, ils sont contigus.
Jusqu'à aujourd'hui, je ne le croyais pas mais plus je cherche, plus c'est confus dans ma tête. J'ai essayé de le découvrir en faisant des tests mais ça reste assez confus.
En gros, pouvez-vous m'expliquer comment ça se passe en mémoire s'il vous plait ?
Il n'y a aucune différence entre un tableau de 1 ou de n dimensions en mémoire. C'est un tableau comme un autre, c'est à dire une succession d'élément identiques et contigus.
La seule chose qui change, c'est la façon de l'indexer. On utilise un index par dimension :
1 dimension N : [i] avec i de 0 à N-1
2 dimensions N et M : [i][j] avec i de 0 à N-1 et j de 0 à M-1
etc.
Mais alors, si un tableau multidimensionnel est stocké de la même manière qu'un tableau unidimensionnel, si dans le tableau tab[2][2],
tab[1][0] = 4;
et
*(tab+2) = 4
Ces instructions produisent-elles le même résultat ?
Non. tab n'a pas le type int * et ne peut être utilisé pour accéder en 1D. Il faut un pointeur séparé de type int * initialisé avec l'adresse de tab et la cast qui va bien (horrible...)
Il vaut mieux s'en tenir aux dimensions définies et laisser les indices dans les plages requises...
Si je fais ceci:
- Code:
#include <stdio.h>
int main(void)
{
int tab[2][2] = {0};
*(tab+2) = 4;
printf("%d\n", tab[1][0]);
return 0;
}
Oui, c'est normal. Ce qui fonctionne, c'est ceci :
- Code:
#include <stdio.h>
int main (void)
{
int tab[2][2] = { {0} };
int *p = (int *) tab;
tab[1][0] = 4;
printf ("%d\n", p[2]);
printf ("%d\n", *(p + 2));
return 0;
}
Alors en C les tableaux multidimensionnels sont bien représentés simplement comme des tableaux de tableaux ?
Si tu définis "int tab[2][3]" par exemple il y aura un tableau de deux éléments dont chaque élément est un tableau de trois entiers. Donc pour indicer ça tu dois d'abord choisir un des deux tableaux que contient tab (en les indiçant comme des éléments normaux) puis tu te retrouves dans un tableau à une dimension. Avec "int tab[4][5][6]" ça donnerait quatre tableaux de cinq tableaux de six entiers. Si j'ai bien compris...
Concrètement si on fait :
- Code:
int tab[2][3] = {{1,2,3},{4,5,6}};
___________
1|2|3|4|5|6|
Donc on peut venir avec un pointeur "pointer" chacun des éléments du tableau :
int *pt = (int*)tab;
ainsi pt[0] = 1
...
pt[5] = 6
Et qu'est-ce que vous pensez de cette pratique ?
- Code:
#define D1_TAB1 5
#define D2_TAB1 4
<...>
int *p_tab1 = malloc (D1_TAB1*D2_TAB1*sizeof(int));
if (p_tab1 == NULL)
{
fprintf (stderr, "Zut.\n");
}
else
{
*(p_tab1+2*D2_TAB1+3) = 5; /* p[2][3] = 5; */
free (p_tab1);
}
<...>
C'est la technique du tableau dynamique linéaire à N dimensions. Si c'est bien géré, ça fonctionne. Je recommande l'usage de fonctions 'accesseurs'.
- Code:
#include <stdio.h>
#include <stdlib.h>
#define D1_TAB1 5
#define D2_TAB1 4
int main (void)
{
int err = 0;
int *p_tab1 = malloc (D1_TAB1 * D2_TAB1 * sizeof *p_tab1);
if (p_tab1 == NULL)
{
perror ("Zut.");
err = EXIT_FAILURE;
}
else
{
*(p_tab1 + 2 * D2_TAB1 + 3) = 5; /* p[2][3] = 5; */
printf ("%d\n", p_tab1[2 * D2_TAB1 + 3]);
free (p_tab1);
p_tab1 = NULL;
}
return err;
}
Quand on déclarre ceci :
- Code:
int tab[2][2];
Et donc, si tab[0] est un int*, tab est un int** qui pointe sur un tableau de 2 int*.
- Code:
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int tab[2][2] = {{0} };
tab[1][0] = 4;
printf("%d\n", *(*tab+2) );
return 0;
}
*(*tab+2) car on veut la valeur qui est à l'adresse de la valeur pointé par tab décalé de 2.
Et là, ça t'affiche bien 4.
Avec 3 dimensions, c'est toujours pareil (j'ai laissé volontairement le +0 pour qu'on voit bien où devrait se faire le décalage d'adresse) :
- Code:
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int tab[2][2][2] = {{{0} } };
tab[1][0][1] = 4;
printf("%d\n", tab[1][0][1] );
printf("%d\n", *(tab[1][0]+1) );
printf("%d\n", *(*(tab[1]+0)+1) );
printf("%d\n", *(*(*(tab+1)+0)+1) );
return 0;
}
Pour en revenir à ce que tu disais, ici,
- Code:
tab[1][0][1] = 4;
On peut donc directement y accéder en faisant :
*(*(*(tab))+5)
Donc au final, ça fait *(**tab+5)
Je pense que c'est cette forme que tu cherchais au tout début.
Page 1 sur 1
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum
|
|