Liste double de liens inversée en C++

Question

J'ai essayé de comprendre comment inverser l'ordre d'une liste doublement liée, mais pour une raison quelconque, dans ma fonction, void reverse() s'exécute en boucle une fois, puis tombe en panne pour une raison quelconque. Pour répondre à quelques questions, je m'auto-apprends avec l'aide de mes frères. Ce n'est pas tout le code, mais j'ai une fonction display() qui imprime tous les nœuds par ordre chronologique de start_ptr et un commutateur qui active certaines fonctions comme

case 1 : add_end(); break; 
    case 2 : add_begin(); break; 
    case 3 : add_index(); break; 
    case 4 : del_end(); break; 
    case 5 : del_begin(); break; 
    case 6 : reverse(); break; 

C'est le Geist de mon code:

#include <iostream> 
using namespace std; 

struct node 
{ 
    char name[20]; 
    char profession[20]; 
    int age; 
    node *nxt; 
    node *prv; 
}; 

node *start_ptr = NULL; 

void pswap (node *pa, node *pb) 
{ 
    node temp = *pa; 
    *pa = *pb; 
    *pb = temp; 
    return; 
} 

void reverse() 
{ 
    if(start_ptr==NULL) 
    { 
     cout << "Can't do anything" << endl; 
    } 
    else if(start_ptr->nxt==NULL) 
    { 
     return; 
    } 
    else 
    { 
     node *current = start_ptr; 
     node *nextone = start_ptr; 
     nextone=nextone->nxt->nxt; 
     current=current->nxt; 
     start_ptr->prv=start_ptr->nxt; 
     start_ptr->nxt=NULL; 
     //nextone=nextone->nxt; 
     while(nextone->nxt!= NULL) 
     { 
      pswap(current->nxt, current->prv); 
      current=nextone; 
      nextone=nextone->nxt; 
     } 
     start_ptr=nextone; 
    } 
} 

Answer 1

Essayez ceci:

node *ptr = start_ptr; 
while (ptr != NULL) { 
    node *tmp = ptr->nxt; 
    ptr->nxt = ptr->prv; 
    ptr->prv = tmp; 
    if (tmp == NULL) { 
     end_ptr = start_ptr; 
     start_ptr = ptr; 
    } 
    ptr = tmp; 
} 

Answer 2

Vous pouvez simplifier reverse() un peu. Je ferais quelque chose comme ceci:

void reverse() 
{ 
    if(start_ptr == NULL) 
    { 
     cout << "Can't do anything" << endl; 
    } 
    else 
    { 
     node *curr = start_ptr; 
     while(curr != NULL) 
     { 
      Node *next = curr->next; 
      curr->next = curr->prev; 
      curr->prev = next; 
      curr = next; 
     } 
     start_ptr = prev;  
    } 
} 

Explication: L'idée de base est tout simplement de visiter chaque Node et échanger les liens vers previous et next. Lorsque nous passons curr au Node suivant, nous devons stocker le nœud suivant afin que nous ayons toujours un pointeur lorsque nous définissons curr.next à prev.

Answer 3

EDIT: Ma première implémentation, qui était correcte mais pas parfaite. Votre implémentation est assez compliquée. Pouvez-vous essayer ceci:

node * reverse(Node * start_ptr) 
{ 
    Node *curr = start_ptr; 
    Node * prev = null; 
    Node * next = null; 
    while(curr) 
    { 
     next = curr->nxt; 
     curr->nxt = prev; 
    curr->prv = next; 
     prev = curr; 
     curr = next; 
    } 
    return start_ptr=prev; 
} 

Voici ma solution mise à jour:

node * reverse() 
{ 
    node *curr = start_ptr; 
    node * prev = NULL; 
    node * next = NULL; 
    while(curr) 
    { 
     next = curr->nxt; 
     curr->nxt = prev; 
     curr->prv = next; 
     prev = curr; 
     curr = next; 
    } 
    return start_ptr=prev; 
} 

La logique était correcte. Mais le problème était que j'acceptais dans l'argument d'entrée start_ptr. Ce qui signifie que je retournais la copie locale de celui-ci. Maintenant, ça devrait marcher.

Answer 4

Votre fonction pswap est erronée vous devriez échanger le pointeur et ne pas essayer de créer des objets temporaires et de les échanger. Devrait être comme ça (il pourrait y avoir d'autres erreur plus tard)

void pswap (node *&pa, node *&pb) 
{ 
    node* temp = pa; 
    pa = pb; 
    pb = temp; 
    return; 
} 

Answer 5

Je suggère de maintenir un lien vers le dernier noeud.
Sinon, trouvez le dernier nœud. Parcourez la liste en utilisant les liens "précédents" (ou, dans votre cas, prv).

Il n'est pas nécessaire de changer les liens. Traverser en utilisant le pointeur prv va automatiquement visiter les nœuds dans l'ordre inverse.

Answer 6

Regardez

valuesnextone=nextone->nxt->nxt; 

Ici nextone->nxt peut être nul. En dehors de cela, essayez d'utiliser des pointeurs vers des pointeurs dans la fonction de permutation.

Answer 7

Solution simple.inverse en moins d'un demi-nombre d'itérations au total sur la liste

template<typename E> void DLinkedList<E>::reverse() { 
    int median = 0; 
    int listSize = size(); 
    int counter = 0; 

    if (listSize == 1) 
    return; 

    DNode<E>* tempNode = new DNode<E>(); 

    /** 
    * A temporary node for swapping a node and its reflection node 
    */ 
    DNode<E>* dummyNode = new DNode<E>(); 

    DNode<E>* headCursor = head; 
    DNode<E>* tailCursor = tail; 

    for (int i = 0; i < listSize/2; i++) { 
     cout << i << "\t"; 

     headCursor = headCursor->next; 
     tailCursor = tailCursor->prev; 

     DNode<E>* curNode = headCursor; 
     DNode<E>* reflectionNode = tailCursor; 

     if (listSize % 2 == 0 && listSize/2 - 1 == i) { 
      /** 
      * insert a dummy node for reflection 
     * for even sized lists 
     */ 
     curNode->next = dummyNode; 
     dummyNode->prev = curNode; 

     reflectionNode->prev = dummyNode; 
     dummyNode->next = reflectionNode; 

    } 
    /** 
    * swap the connections from previous and 
      * next nodes for current and reflection nodes 
    */ 

    curNode->prev->next = curNode->next->prev = reflectionNode; 

    reflectionNode->prev->next = reflectionNode->next->prev = curNode; 

    /** 
    * swapping of the nodes 
    */ 

    tempNode->prev = curNode->prev; 
    tempNode->next = curNode->next; 

    curNode->next = reflectionNode->next; 
    curNode->prev = reflectionNode->prev; 

    reflectionNode->prev = tempNode->prev; 
    reflectionNode->next = tempNode->next; 

    if (listSize % 2 == 0 && listSize/2 - 1 == i) { 
     /** 
     * remove a dummy node for reflection 
     * for even sized lists 
     */ 
     reflectionNode->next = curNode; 
     curNode->prev = reflectionNode; 
    } 

    /** 
    * Reassign the cursors to position over the recently swapped nodes 
    */ 
     tailCursor = curNode; 
     headCursor = reflectionNode; 

    } 

    delete tempNode, dummyNode; 
} 

template<typename E> int DLinkedList<E>::size() { 
    int count = 0; 
    DNode<E>* iterator = head; 

    while (iterator->next != tail) { 
     count++; 
     iterator = iterator->next; 
    } 
    return count; 
} 

Answer 8

Une très simple et solution O (n) en utilisant deux pointeurs:

start = tête du doublement LL

struct node *temp, *s; 
s = start; 

while(s != NULL){ 
    temp = s->prev; 
    s->prev = s->next; 
    s->next = temp; 
    s = s->prev; 
} 

//if list has more than one node 
if(current != NULL){ 
    start = temp->prev; 
} 

Answer 9

Mon code pour l'inversion de la liste à double liaison,

Node* Reverse(Node* head) 
{ 
// Complete this function 
// Do not write the main method. 


if(head != NULL) { 

    Node* curr = head; 
    Node* lastsetNode = curr; 
    while(curr != NULL) { 

     Node* frwdNode = curr->next; 
     Node* prevNode = curr->prev; 


     if(curr==head) {     
      curr->next = NULL; 
      curr->prev = frwdNode; 
      lastsetNode = curr; 
     } 
     else { 
      curr->next = lastsetNode; 
      curr->prev = frwdNode; 
      lastsetNode = curr; 
     } 



     curr = frwdNode; 
    } 

    head = lastsetNode; 
} 


return head; 
}