La permutation de nœuds en double liste chaînée

Je suis en train de mettre en œuvre une fonction swap de deux nœuds de mon double liste chaînée, afin de trier le contenu du répertoire courant. Mais ma fonction semble "supprimer" certains éléments de ma liste, voici le code :

void node_swap(struct s_node *left, struct s_node *right)
{
  struct s_node *tmp;

  tmp = left->prev;
  if (tmp)
   {
      tmp->next = right;
      right->prev = tmp;
   }
  else
      right->prev = NULL;

  left->prev = right;
  left->next = right->next;
  right->next = left;
  right->next->prev = left->prev;
}

Je ne vois pas où est le mal dans tout cela ?

Pourquoi ne pas juste changer les données?
Pourquoi ne pouvez-vous pas juste changer le contenu des données des deux nœuds?
J'ai pu, mais n'est-ce pas de cette façon plus lente ?
Dépend des données. Quel est votre de données de type?
Mes nœuds sont composées d'un char *nom, et les deux pointeurs *prev, *suivant.
Puis il suffit de passer d'un char * est clairement plus rapide que le remplacement de 4 struct s_node *s.
BTW: Êtes-vous permutation des nœuds pour être capable de trier la liste?
Oui, je suis en train de trier ma liste.
Alors vous devriez plutôt regarder mergesort, et de diviser la liste en deux, à l'aide d'un fast-pointeur (un pointeur de marcher deux nœuds) et une lente pointeur en sautant juste un nœud dans la liste. Quand le jeûne pointeur est à la fin de la liste, la lenteur de pointeur est au milieu de la liste. C'est là que vous diviser et conquérir.

InformationsquelleAutor Kernael | 2013-11-20

c linked-list

3

Dire que c'est de votre structure initiale TMP -> L -> R -> X Vous n'êtes pas la mise à jour de la X->prev correctement. Dans votre dernière ligne right->next->prev = left->prev; droit->suivant est à gauche. Si vous êtes à la mise à jour de la précédent de la gauche qui est faux. Au lieu de cela, vous devriez faire
```
if(left->next != null)
   left->next(which is X)->prev = left
```
Donc, je pense que cela va fonctionner
```
void node_swap(struct s_node *left, struct s_node *right)
{
  struct s_node *tmp;

  tmp = left->prev;
  if (tmp)
      tmp->next = right;
  right->prev = tmp;

  left->prev = right;
  left->next = right->next;
  right->next = left;
  if(left->next != null)
     left->next(which is X)->prev = left
}
```
- Essayé, mais le résultat semble être le même, je suis encore en train de perdre 3 éléments lorsque le tri est terminé.
- btw, vous devriez mettre un null vérifier avant de le faire. C'est que vous ne devriez pas le faire si le premier R->suivant est null
- Toujours le même résultat... Compris que les deux éléments sont correctement imprimées sont le premier et le dernier, tous les éléments entre eux ont été "perdus".
InformationsquelleAutor inankupeli
1

Du code affiché dans votre question, je suis en déduire que votre fonction est en supposant que vous échangez nœuds adjacents.

Essayez ce qui suit:
```
if ( left->prev )
    left->prev->next = right;

if ( right->next )
    right->next->prev = left;

left->next  = right->next;
right->prev = left->prev;

right->next = left;
left->prev = right;
```
EDIT: à la Suite de votre commentaire dans la question d'origine, il est beaucoup plus rapide pour effectuer les opérations suivantes:
```
char* tmpName = right->name;
right->name = left->name;
left->name = tmpName;
```
- votre solution ne fonctionne qu'avec les nœuds adjacents (p. ex. x - A - B -y mais pas x - A - y - B - z)
- oui, j'ai supposé nœuds adjacents sont supposés après l'examen du code en question. Je vais éditer le post pour le spécifier.
- Merci, ça marche, même si Valgrind semble un peu en colère à ce sujet, deux " saut Conditionnel ou déplacer dépend de la valeur non initialisée(s)"
- vous devez vérifier que left et right ne sont pas NULL à la première ligne de votre fonction. Si l'un (ou les deux) est NULL, l'affichage d'une erreur et retour.
- Fait un if (!gauche || !droite) {return ;} au début de la fonction, mais Valgrind encore de sortie de ces erreurs.
- Je suppose que, le valgrind avertissements sont causés par le reste de votre code qui construit la liste.
- Je doute que cela soit le cas, ces erreurs ne s'affiche que lorsque j'utilise cette méthode.
InformationsquelleAutor ajcaruana

Si vous écrivez ce que vous voulez faire, vous pouvez réaliser un vraiment simple et directe de la solution.

[[code de travail est à la fin de la réponse]]

Par exemple, si vous avez deux nœuds que vous voulez échanger (disons A et B), il y a deux possibilités en fonction de la position des nœuds. Ils pourraient être adjacentes ou non.

Adjacentes cas

Dans les autres cas, vous pouvez écrire:

[X] - [A] - [B] - [Y]

A->prev = X;
A->next = B;
B->prev = A;
B->next = Y;

Si vous échangez avec B, vous obtiendrez ceci:

[X] - [B] - [A] - [Y]

A->prev = B;
A->next = Y;
B->prev = X;
B->next = A;

C'est ce que vous voulez obtenir. Vous devez réorganiser les pointeurs pour permuter les deux nœuds A et B.

Si vous utilisez une matrice de la forme de la règle sera plus intuitif:

     A B               A B 
prev X A    =>    prev B X
next B Y          next Y A

Ou tout simplement écrire les matrices seul:

X A   --\   B X
B Y   --/   Y A

Avis, que la matrice de permutation pivote de 90 degrés dans le sens horaire. Si vous indexez les éléments dans la matrice, vous pouvez faire une assotiation table:

0 1  --\  2 0
2 3  --/  3 1

Donc, si vous stocker les pointeurs dans un tableau, vous pouvez facilement réorganiser:

0,1,2,3 -> 2,0,3,1

Non adjacentes cas

Que vous pouvez faire une règle similaire pour les non adjacentes cas ainsi:

[W] - [A] - [X] - ... - [Y] - [B] - [Z]

A->prev = W;
A->next = X;
B->prev = Y;
B->next = Z;

Swap de A par B:

[W] - [B] - [X] - ... - [Y] - [A] - [Z]

A->prev = Y;
A->next = Z;
B->prev = W;
B->next = X;

     A B               A B 
prev W Y    =>    prev Y W
next X Z          next Z X

W Y   --\   Y W
X Z   --/   Z X

0 1  --\  1 0
2 3  --/  3 2

0,1,2,3 -> 1,0,3,2

Pointeurs vers les nœuds

Parce que nous avons affaire à des listes liées, il ne suffit pas de changer les pointeurs dans les nœuds. Nous venons de mettre à jour les pointeurs pointant vers notre nœuds que nous voulons inverser. Ce pointeurs sont situés dans le quartier de la swapable objets.

Avis, que les pointeurs qui sont situés dans les ganglions que nos pointeurs points sont toujours dirigées à nous-mêmes.

A->prev->next = A
A->next->prev = A

Donc après la mise à jour des pointeurs de fonction de la règle d'association, vous n'avez qu'à pointer l'extérieur des pointeurs vers le nœud donné, et vous avez terminé! Assurez-vous, que le voisin existe bien sûr.

Vous devez également vérifier si le nœud est lié avant que le nœud B. Si non, vous devez permuter les deux paramètres. Grâce kralyk pour le heads up.

C'est assez d'informations pour écrire les fonctions qui ne l'échange.

Permutation de fonction et de ses fonctions d'assistance

int areTheyNeighbours(Node A,Node B) {
return ( A->next == B && B->prev == A ) || ( A->prev == B && B->next == A );
}
void refreshOuterPointers(Node A) {
if (A->prev != NULL)
A->prev->next = A;
if (A->next != NULL)
A->next->prev = A;
}
void swap(Node A,Node B) {
Node swapperVector[4];
Node temp;
if (A == B) return;
if (B->next == A) {
temp = A;
A = B;
B = temp;
}
swapperVector[0] = A->prev;
swapperVector[1] = B->prev;
swapperVector[2] = A->next;
swapperVector[3] = B->next;
if (areTheyNeighbours(A,B)) {
A->prev = swapperVector[2];
B->prev = swapperVector[0];
A->next = swapperVector[3];
B->next = swapperVector[1];
} else {
A->prev = swapperVector[1];
B->prev = swapperVector[0];
A->next = swapperVector[3];
B->next = swapperVector[2];
}
refreshOuterPointers(A);
refreshOuterPointers(B);
}

Programme de travail pour la présentation

La optput du programme suivant:

Initial state:   [1]-[2]-[3]-[4]
--------------------------------
[1] <-> [2]:     [2]-[1]-[3]-[4]
[1] <-> [2]:     [1]-[2]-[3]-[4]
[2] <-> [1]:     [2]-[1]-[3]-[4]
[2] <-> [1]:     [1]-[2]-[3]-[4]
--------------------------------
[1] <-> [3]:     [3]-[2]-[1]-[4]
[1] <-> [3]:     [1]-[2]-[3]-[4]
[3] <-> [1]:     [3]-[2]-[1]-[4]
[3] <-> [1]:     [1]-[2]-[3]-[4]
--------------------------------
[1] <-> [4]:     [4]-[2]-[3]-[1]
[1] <-> [4]:     [1]-[2]-[3]-[4]
[4] <-> [1]:     [4]-[2]-[3]-[1]
[4] <-> [1]:     [1]-[2]-[3]-[4]
--------------------------------
[2] <-> [3]:     [1]-[3]-[2]-[4]
[2] <-> [3]:     [1]-[2]-[3]-[4]
[3] <-> [2]:     [1]-[3]-[2]-[4]
[3] <-> [2]:     [1]-[2]-[3]-[4]
--------------------------------
[2] <-> [4]:     [1]-[4]-[3]-[2]
[2] <-> [4]:     [1]-[2]-[3]-[4]
[4] <-> [2]:     [1]-[4]-[3]-[2]
[4] <-> [2]:     [1]-[2]-[3]-[4]
--------------------------------
[3] <-> [4]:     [1]-[2]-[4]-[3]
[3] <-> [4]:     [1]-[2]-[3]-[4]
[4] <-> [3]:     [1]-[2]-[4]-[3]
[4] <-> [3]:     [1]-[2]-[3]-[4]

Vous pouvez exécuter le code en une seconde, en suivant ce lien:
http://codepad.org/UHcmmag1

Lien mis à jour avec la nouvelle fonction de permutation: http://codepad.org/LbRYjvPr

#include <stdio.h>
#include <stdlib.h>
typedef struct node_v {
int id;
struct node_v* prev;
struct node_v* next;
} Node_v;
typedef Node_v* Node;
void print(Node node) {
while (node->prev != NULL)
node = node->prev;
printf("   [%d]",node->id);
while (node->next != NULL) {
node = node->next;
printf("-[%d]",node->id);
}
printf("\n");
}
void connect(Node first,Node second) {
first->next = second;
second->prev = first;
}
Node createNode(int id) {
Node node = (Node)malloc(sizeof(Node_v));
node->id = id;
node->prev = NULL;
node->next = NULL;
return node;
}
int areTheyNeighbours(Node A,Node B) {
return ( A->next == B && B->prev == A ) || ( A->prev == B && B->next == A );
}
void refreshOuterPointers(Node A) {
if (A->prev != NULL)
A->prev->next = A;
if (A->next != NULL)
A->next->prev = A;
}
void swap(Node A,Node B) {
Node swapperVector[4];
Node temp;
if (A == B) return;
if (B->next == A) {
temp = A;
A = B;
B = temp;
}
swapperVector[0] = A->prev;
swapperVector[1] = B->prev;
swapperVector[2] = A->next;
swapperVector[3] = B->next;
if (areTheyNeighbours(A,B)) {
A->prev = swapperVector[2];
B->prev = swapperVector[0];
A->next = swapperVector[3];
B->next = swapperVector[1];
} else {
A->prev = swapperVector[1];
B->prev = swapperVector[0];
A->next = swapperVector[3];
B->next = swapperVector[2];
}
refreshOuterPointers(A);
refreshOuterPointers(B);
}
int main() {
Node n1 = createNode(1);
Node n2 = createNode(2);
Node n3 = createNode(3);
Node n4 = createNode(4);
connect(n1,n2);
connect(n2,n3);
connect(n3,n4);
printf("\nInitial state:");
print(n2);
printf("--------------------------------\n");
printf("[1] <-> [2]:  ");
swap(n1, n2);
print(n1);
printf("[1] <-> [2]:  ");
swap(n1, n2);
print(n1);
printf("[2] <-> [1]:  ");
swap(n2, n1);
print(n1);
printf("[2] <-> [1]:  ");
swap(n2, n1);
print(n1);
printf("--------------------------------\n");
printf("[1] <-> [3]:  ");
swap(n1, n3);
print(n2);
printf("[1] <-> [3]:  ");
swap(n1, n3);
print(n2);
printf("[3] <-> [1]:  ");
swap(n3, n1);
print(n2);
printf("[3] <-> [1]:  ");
swap(n3, n1);
print(n2);
printf("--------------------------------\n");
printf("[1] <-> [4]:  ");
swap(n1, n4);
print(n3);
printf("[1] <-> [4]:  ");
swap(n1, n4);
print(n3);
printf("[4] <-> [1]:  ");
swap(n4, n1);
print(n3);
printf("[4] <-> [1]:  ");
swap(n4, n1);
print(n3);
printf("--------------------------------\n");
printf("[2] <-> [3]:  ");
swap(n2, n3);
print(n3);
printf("[2] <-> [3]:  ");
swap(n2, n3);
print(n3);
printf("[3] <-> [2]:  ");
swap(n3, n2);
print(n3);
printf("[3] <-> [2]:  ");
swap(n3, n2);
print(n3);
printf("--------------------------------\n");
printf("[2] <-> [4]:  ");
swap(n2, n4);
print(n3);
printf("[2] <-> [4]:  ");
swap(n2, n4);
print(n3);
printf("[4] <-> [2]:  ");
swap(n4, n2);
print(n3);
printf("[4] <-> [2]:  ");
swap(n4, n2);
print(n3);
printf("--------------------------------\n");
printf("[3] <-> [4]:  ");
swap(n3, n4);
print(n4);
printf("[3] <-> [4]:  ");
swap(n3, n4);
print(n4);
printf("[4] <-> [3]:  ");
swap(n4, n3);
print(n4);
printf("[4] <-> [3]:  ");
swap(n4, n3);
print(n4);
printf("--------------------------------\n");
return 0;
}

Cela ne fonctionne pas si A et B sont voisins, mais B vient avant A (Ie. si vous essayez de permuter [2] <-> [1]). Dans ce cas, vous devez faire pivoter votre matrice de -90°, ou de détecter que B est précédente Une et swap A et B pointeurs en premier. Honnêtement, je pense que les matrices de compliquer le code. Je venais d'utiliser un swapper fonction/macro.
Absolument commentaire valide. Un peu de vérification avant la permutation de la méthode résout le problème. Le Code sera mis à jour.
Ainsi, la matrice de transformation est juste l'idée derrière le simple swapper fonction. Vous pouvez venu avec l'échange par la méthode de jongler avec les pointeurs de trop, mais je pense que l'approche avec des matrices est un peu plus clair.
Ok, merci pour la mise à jour 🙂

InformationsquelleAutor tiborsimon

Très court code qui fonctionne de manière très efficace, a passé 2 heures sur ce:

Vous devez remplacer les deux nœuds...

Mais aussi assurez-vous de conserver les liens qui existent entre les 2 échangé des nœuds et le troisième et dernier, dans les deux directions.

static inline void  swap_list(t_lst **lst)
{
t_lst   *tmp;
if ((*lst)->next)   //you need to make sure you have at least 2 items in your list
{
tmp = *lst;                 //let's store 1st node's address, that will become the second one after the swap
*lst = (*lst)->next;        //Reversely our 2nd one will become the 1st one after the swap. It also allows us to set the beginning of our list.
/*
** Now you need to work on the 6 links that exist : between the last elem (that may be the 2nd one)
** and the 1st one you have 2 links (next and prev), same between the 1st one
** and the 2nd one (2 links again) and finally 2 links between the 2nd one
** and the 3d one (that may be the first node)
*/
tmp->next = (*lst)->next;   //tmp will have second position and needs to point to the third elem. Since *lst is now (*lst)->next, here we refer to the 3rd elem.
tmp->next->prev = tmp;      //we have then to tell this third elem where stands the second one with this line.
(*lst)->prev = tmp->prev;   //before destroying the link to last node that tmp contains, we assign it to the future 1st elem of our list
tmp->prev = *lst;           //now we can safely tell the second node its link to the first.
(*lst)->next = tmp;         //and reversely tells where is the second elem after the first.
(*lst)->prev->next = *lst;  //finally we tell the last node where it the first one.
}
}

J'espère que cela peut aider.

ps : dans le cas où vous vous demandez:

typedef struct      s_lst
{
void            *data; //or a more specific type if you wish
struct s_lst    *prev;
struct s_lst    *next;
}                   t_lst;

InformationsquelleAutor Antonin GAVREL

Vous devez vous connecter pour publier un commentaire.