J'essaie de me renseigner sur les structures de données et les algorithmes par moi-même. J'ai écrit ma propre liste à double lien en C et maintenant je veux écrire quelques algorithmes à effectuer sur la liste. Quel est le moyen préféré d'échanger des éléments de la liste? Est-il préférable d'échanger le contenu ou de réorganiser les pointeurs qui pointent vers l'élément de liste suivant et précédent?Comment échanger des éléments dans une liste?
Réorganisez les pointeurs. L'échange des éléments de données peut avoir des effets secondaires. En particulier, vous avez peut-être stocké une référence à un nœud quelque part en dehors de la fonction, et habituellement lorsque vous réorganisez l'ordre des nœuds dans une liste, vous ne voulez pas que les personnes détenant une référence à un nœud découvrent soudainement que le noeud pointe vers de nouvelles données. En effet, généralement, la caractéristique d'identification importante d'un nœud est les données qu'il pointe vers et non sa position dans la liste.
Le swap canonique se fait via le pointeur réagencement, n'a pas d'effets secondaires et est bien sûr plus rapide:
void swap (node *a, node *b) {
node *tmp;
tmp = a;
a = b;
b = tmp;
}
... mais si chaque nœud connaît sa position dans la liste chaînée, ces positions ne vont pas changer avec ce swap. –
Si chaque nœud connaît sa position, vous pouvez facilement ajouter quelques lignes pour les modifier également. –
Euh ... Qu'est-ce que ce code est censé faire exactement? Il échange deux ponters locaux dans une fonction. La fonction n'a aucun effet externe. Dans quel but? – AnT
En fonction du type de contenu étant stocké dans les éléments de la liste chaînée, en échangeant le contenu réel de l'élément serait difficile (pensez à une liste chaînée de chaînes de longueur différentes par exemple) donc il est plus facile d'échanger les pointeurs qui pointent vers les éléments de la liste suivante et précédente.
Dépend de la manière dont vous avez attribué le contenu.
Si vous stockez le pointeur sur le contenu, le changement de contenu n'est pas un gros problème. Si vous avez une grande structure qui fait partie de votre nœud, alors changer les pointeurs pourrait être plus efficace que de copier tout le contenu.
J'ai tendance à me ranger du côté de ce que la plupart des gens ont déjà dit. Un peu d'arrière-plan vous aidera probablement: l'échange de pointeurs est garanti, alors que l'échange d'objets n'est pas toujours aussi simple qu'il n'y paraît. Pensez aux temporaires qui peuvent/seront créés et des exceptions (et je veux dire en général et non pas une fonctionnalité de langage C++) peuvent se produire et laisser votre conteneur (liste) dans un état indésirable. Recherchez les invariants dans votre conteneur - c'est-à-dire qu'un échange doit laisser intacte la taille de la liste ainsi que les éléments intacts et la conception.
Je vais l'acheter. Bonne observation. – John
Cela a beaucoup de sens. Je vous remercie! – Lucas