Inverser le lien lié en C

Question

J'ai du mal à inverser ma liste de doublons (avec seulement une sentinelle arrière) en C, je l'approche en changeant les pointeurs et voici le code que j'ai jusqu'à présent:

/* Reverse the deque 

param: q pointer to the deque 
pre: q is not null and q is not empty 
post: the deque is reversed 
*/ 
/* reverseCirListDeque */ 
void reverseCirListDeque(struct cirListDeque *q) 
{ 
struct DLink *back = q->backSentinel; 
struct DLink *second = q->backSentinel->prev; 
struct DLink *third = q->backSentinel->next; 

while (second != q->backSentinel->next){ 
    back->next = second; 
    third = back->prev; 
    back->next->prev = back; 
    back = second; 
    second = third; 
} 
} 

Mais il ne semble pas fonctionner, je l'ai testé avec un deque qui ressemble à ceci: 1, 2, 3 la sortie est: 3 et ce processus semble gâcher la valeur réelle des nombres. c'est à dire. 2 devient 2.90085e-309 ... Je pense que le changement de pointeur est foiré mais je ne peux pas trouver le problème. Et même si cela ne signifie pas que mon code est correct. il compile bien.

Answer 1

S'il s'agit d'une liste à double liaison, vous ne devriez pas avoir besoin de changer de pointeur du tout. permuter un peu plus les charges utiles:

pointer1 = first 
pointer2 = last 
while pointer1 != pointer2 and pointer2->next != pointer1: 
    temp = pointer1->payload 
    pointer1->payload = pointer2->payload 
    pointer2->payload = temp 
    pointer1 = pointer1->next 
    pointer2 = pointer2->prev 

Si par sentinelle en arrière, vous voulez dire que le pointeur last (comme dans aucun premier pointeur est disponible), alors vous devez jeter étape en arrière le deque pour le trouver. Il est difficile de croire cependant que ce serait le cas car ce serait une deque assez inefficace (qui est supposée être une file d'attente double).

Answer 2

Les structures liées comme les deques se prêtent facilement à la récursivité, donc j'ai tendance à privilégier un style récursif pour les structures liées. Cela nous permet également de l'écrire de façon incrémentielle afin que nous puissions tester chaque fonction facilement. Boucler comme votre fonction a de nombreux inconvénients: vous pouvez facilement introduire fencepost errors et il tend vers de grandes fonctions qui prêtent à confusion. D'abord, vous avez décidé de le faire en échangeant les pointeurs, non? Donc, écrire une fonction pour échanger des pointeurs:

void swapCirListDequePointers(
    struct cirListDeque** left, 
    struct cirListDeque** right) 
{ 
    struct cirListDeque* temp = *left; 
    *left = *right; 
    *right = temp; 
} 

Maintenant, écrire une fonction qui inverse les pointeurs dans un seul nœud:

void swapPointersInCirListDeque(struct cirListDeque* q) 
{ 
    swapCirListDequePointers(&(q->prev),&(q->next)); 
} 

Maintenant, mettez ensemble récursive:

void reverseCirListDeque(struct cirListDeque* q) 
{ 
    if(q == q->backSentinel) 
     return; 

    swapPointersInCirListDeque(q); 

    // Leave this call in tail position so that compiler can optimize it 
    reverseCirListDeque(q->prev); // Tricky; this used to be q->next 
} 

Je ne suis pas sûr exactement comment votre structure est conçue; ma fonction suppose que votre deque est circulaire et que vous appellerez cela sur la sentinelle.

EDIT: Si votre deque n'est pas circulaire, vous aurez envie d'appeler swapPointersInCirListDeque(q) sur la sentinelle, donc passer swapPointersInCirListDeque(q) avant l'instruction if.

Si vous prévoyez d'utiliser le backSentinel après cela, vous devriez le changer aussi, puisqu'il est maintenant le devant de la liste. Si vous avez un frontSentinel, vous pouvez simplement ajouter swapCirListDequePointers(&(q->frontSentinel),&(q->backSentinel)); à swapPointersInCirListDeque. Sinon, vous devrez passer dans le premier nœud avec q et définir q->backSentinel à cela.

Answer 3

Vous avez déjà reçu quelques suggestions; voici une autre possibilité:

// Assumes a node something like: 
typedef struct node { 
    struct node *next, *prev; 
    int data; 
} node; 

et assume également quelques variables (GLOBALS pour le moment) et nommé headtail qui pointent vers la tête et la queue du deque, respectivement.

void reverse() { 
    node *pos = head; 
    node *temp = pos->next; 

    head = tail; 
    tail = pos; 

    while (pos != NULL) { 
     node *t = pos->prev; 
     pos->prev = pos->next; 
     pos->next = t; 
     pos = temp; 
     if (temp) 
      temp = temp->next; 
    } 
} 

Au moins pour le moment, cela ne pas - Assumer toute factionnaires seulement des pointeurs NULL pour indiquer les extrémités de la liste.

Si vous êtes juste stocker int s dans le deque, la suggestion de Paxdiablo est un bon (sauf que la création d'un nœud doublement lié à contenir qu'une int est un gaspillage massif). En supposant qu'en réalité vous stockez quelque chose de suffisamment grand pour que les nœuds doublement liés aient du sens, vous préférez également éviter de déplacer ces données plus que nécessaire, du moins en règle générale.