Programmation C des listes liées supprimer un noeud à la position N

EDIT: Compris le problème. Aussi, si vous avez trouvé cela via Google ou un autre moteur de recherche, voici où je me suis trompé et comment le réparer.

Ma méthode deleteNode () parcourait correctement la liste avec le temp correct et en gardant la tête intacte. Là où je me suis trompé, c’est ce que je revenais à la suite de la méthode. Je retournais soit temp ou newNode, ce qui est incorrect car il parcourt la liste jusqu’à ce qu’il trouve la position définie. Une fois qu’il a trouvé cette position définie, il réaffecterait le pointeur -> suivant pour pointer vers le pointeur suivant-> suivant>, ce qui est correct, mais là encore, je renvoyais la mauvaise chose. Comme nous avions parcouru la liste à l’aide de temp / NewNode, nous avons perdu l’en-tête et nous renvoyions la position trouvée et tout ce qui se trouvait encore dans les positions suivantes de la liste.

La façon dont nous corrigeons cela renvoie la tête (qui est ce qui est passé dans la méthode). La raison pour laquelle cela fonctionne est qu’il faut comprendre le fonctionnement de LinkedLists. Les pointeurs de chaque nœud pointent sur le nœud suivant. Ex. nous avons une liste chaînée | A | | – | B | | – | C | | – | D | | – | E | | – | F | |

Si nous voulons supprimer le nœud C, nous nous dirigeons vers le nœud B à l’aide du pointeur temp, puis affectons le paramètre B-> à côté de temp-> next-> next, ignorant ainsi le nœud C et affectant le nœud D.

REMARQUE: (d’après ce que je sais, cela ne libère pas réellement la mémoire du noeud C, ce n’est donc pas une bonne pratique car vous pouvez provoquer des memory leaks de cette façon). Utilisez la méthode free () sur le noeud C.

Voici le code que j’ai fini par utiliser

struct node* DeleteNode(struct node* head, int pos) { struct node* temp = head; int length = LinkedListLength(temp); int i; if(pos  length){ printf("ERROR: Node does not exist!\n"); }else{ if(pos == 1){ head = head->next; //move from head (1st node) to second node }else{ for(i = 1; i next; } temp->next = temp->next->next; } } return head; } 

J’espère que cela m’aide à comprendre comment j’ai résolu le problème.

//////////////////////////////////////////////////////// ////////////////////////////////////////////////////////
//////////////////////////////////////////////////////// ////////////////////////////////////////////////////////
POSTE ORIGINAL
//////////////////////////////////////////////////////// ////////////////////////////////////////////////////////
//////////////////////////////////////////////////////// ////////////////////////////////////////////////////////

EDIT: Note: C’est un devoir que j’ai passé quelques jours (environ 4 heures) à programmer, je suis juste coincé sur cette partie-là. Vous pouvez voir ma tentative ci-dessous

J’ai été en mesure d’insérer et de supprimer depuis le début / la fin, mais il semble que mon nœud de suppression situé à la position N dans la liste liée ne fonctionne pas.

Mon psuedocode ressemble à ceci:

  1. LinkedList: 1,3,5,7,9,23
  2. Saisir LinkedList
  3. Créer un nouveau noeud de structure A = head
  4. Se déplacer dans la liste liée jusqu’à la position
  5. Assigne un noeud à noeud-> suivant
  6. retourner la liste liée

EXEMPLE DE SAISIE

 Node structure int data; struct node* next; int values[] = {1,3,5,7,9,23}; struct node* llist = CreateList(values,6); llist = DeleteNode(llist, 1); llist = DeleteNode(llist, 5); llist = DeleteNode(llist, 3); 

Ce qui devrait laisser la liste avec les valeurs 3, 5, 9 une fois le code exécuté. Cependant, il remplace le premier nœud par un 0

Code actuel:

 struct node* DeleteNode(struct node* head, int pos) { struct node* temp = head; struct node* newNode = head; int length; int i; printf("DeleteNode: position = %d \nBefore: ", pos); PrintList(temp); if(pos <= 0){ //node does NOT exist printf("ERROR: Node does not exist!\n"); }else{ //node DOES exist length = LinkedListLength(temp); if(length < pos){ //if length next; }else if(pos == 1){ newNode = temp->next; }else{ for(i = 1; i next; newNode->next; } if(temp->next == NULL){ newNode = NULL; }else{ newNode = temp->next; } } printf("After: "); PrintList(newNode); printf("\n"); } } return newNode; } 

EDIT # 2: Typo de code

Merci d’avance pour toute aide. D’après ce que j’ai conclu de mon problème, c’est que je ne parcoure pas la liste correctement, mais je ne sais pas pourquoi je ne le fais pas.

    Dans votre code, vous avez la ligne

     newNode->next; 

    dans votre boucle. Cette opération ne fait rien.

    Vous avez aussi

     newNode-> = NULL; 

    ce qui n’est pas valide C, et je ne sais pas comment vous avez pu comstackr cela.

    Mais vraiment, n’utilisez pas cette boucle. Une liste chaînée est l’une des structures de données récursives les plus élémentaires. En conséquence, presque tous les algorithmes les manipulant sont les plus élégants en tant que solution récursive.

     typedef struct node node_t; node_t* delete_at_index(node_t* head, unsigned i) { node_t* next; if(head == NULL) return head; next = head->next; return i == 0 ? (free(head), next) /* If i == 0, the first element needs to die. Do it. */ : (head->next = delete_at_index(next, i - 1), head); /* If it isn't the first element, we recursively check the rest. */ } 

    Supprimer un nœud donné n d’une liste à lien unique peut se résumer à cette opération:

    • Définissez le pointeur qui pointe sur n pour pointer sur n->next .

    Vous pouvez le décomposer en deux opérations:

    • Trouvez le pointeur qui pointe vers n ;
    • Définissez ce pointeur sur n->next .

    La complication découle du fait que le pointeur pointant vers n peut être le champ p->next du noeud précédent dans la liste ou le pointeur principal (si n est le premier noeud de la liste).

    Votre code ne semble pas être complet – il ne définit jamais le champ ->next d’un nœud, il est donc difficile de dire ce qui ne va pas.

    Votre DeleteNode ne supprime pas un nœud, il supprime les nœuds pos situés au début de la liste. Vous essayez donc de supprimer 9 éléments d’une liste qui n’en contient que 6, ce qui aboutit bien sûr à une liste vide (NULL). En outre, votre code est trop complexe et contient des traces d’essais précédents. S’il vous plaît ne faites pas cela pour vous-même ou pour nous; fournir un code propre et simple et il sera plus facile à comprendre et à corriger.

     // Remove list's node located at specified position. // Arguments: // head -- list's head // pos -- index of a node to be removed (1-based!!!) struct node* DeleteNode(struct node* head, int pos) { struct node* node; struct node* prev; int length; int i; printf("DeleteNode: position = %d \nBefore: ", pos); PrintList(head); // Check position's lower bound. Should be >= 1 if(pos <= 0) { //node does NOT exist printf("ERROR: Node does not exist!\n"); return head; } // Seek to the specified node, and keep track of previous node. // We need previous node to remove specified node from the list. for(i=1, prev = 0, node = head; i < pos && node != 0; i++) { prev = node; node = node->next; } // Out of range if(0 == node) { printf("ERROR: Index out of bounds!\n"); return head; } // @node points to a list's node located at index pos // @prev points to a previous node. // Remove current node from the list. if(0 == prev) { head = node->next; } else { prev->next = node->next; } free(node); return head; } 

    Compris, votre boucle for n’atteint pas la position souhaitée. Mieux vaut utiliser égal à signer pour la contrainte que cela fonctionnera. par exemple

     for (i=1;i<=position-1;i++) { }