Comment supprimer un nœud d’une liste à liens simples

Voici mon code:

#include #include struct node { int x; struct node *next; }; struct node *addNode(struct node *head, int y) { struct node *traverser; traverser = head; if(traverser!=NULL) { while(traverser->next!=NULL) traverser=traverser->next; traverser -> next = malloc(sizeof(struct node)); traverser -> next -> x = y; traverser -> next -> next = NULL; } else { head= malloc(sizeof(struct node)); head -> x=y; head -> next = NULL; } return head; } void display(struct node *head) { struct node *traverser; traverser = head; while(traverser!=NULL) { printf("%d\n",traverser->x); traverser=traverser->next; } } struct node *InitializeList(void) { return NULL; } int main() { struct node *head; head = InitializeList(); head = addNode(head,2); head = addNode(head,15); head = addNode(head,5); head = addNode(head,8); display(head); free(head); getchar(); } 

J’ai besoin de supprimer un noeud principal comme celui-ci

 struct node *head; head = InitializeList(); head = addNode(head,2); head = addNode(head,15); head = addNode(head,5); head = addNode(head,8); display(head); removenode(5); display(head); removenode(8); display(head); free(head); 

C’est mon code pour main () lorsqu’il s’agit de supprimer un nœud spécifique dans mon programme.

Mais comment puis-je le faire? Removenode () n’est qu’un nom de fonction, quel algorithme dois-je utiliser? Ou quoi ou comment l’enlever?

Pas tout à fait une réponse, juste quelques conseils généraux

Pour comprendre ce genre de choses, il suffit généralement de résoudre exactement trois cas.

  • Le noeud à enlever est la tête
  • Le nœud à enlever est la queue
  • le nœud à supprimer est à l’intérieur de la liste

Les grandes sources de problèmes que vous rencontrerez sont

  • en s’assurant que le champ “next” de tous les nœuds précédents est correctement réinitialisé
  • s’assurer que l’appelant obtient ou conserve un pointeur valide sur la nouvelle tête.

Notez qu’il existe une implémentation récursive (think n.next = remove(n.next,val) ) qui fait que ces deux problèmes sont identiques et que vous pouvez le convertir principalement en boucle pour éviter les débordements de stack sur de très longues listes. .


Un sous-problème qui peut survenir est celui de trouver le nœud à supprimer de la liste. Pouvez-vous vous faciliter la vie en séparant leur partie de la recherche du nœud cible à partir d’une remove(node* head, node* target) ?

J’ai écrit un tutoriel sur les listes de liens en C, cela aidera peut-être:

http://www.4pmp.com/2009/10/linked-lists-in-c-push-pop-shift-and-unshift/

Le prototype de l’algorithme doit être:

 struct node * removenode(struct node *head, int y); 

Si vous supprimez le premier élément, le pointeur “tête” d’origine ne sera plus valide.

L’algorithme consiste simplement à parcourir la liste en se souvenant de l’élément précédent (et de la tête) et en recherchant les données. Une fois trouvé, définissez le pointeur suivant de l’élément précédent sur celui de l’élément actuel.

À un niveau élevé, pour supprimer un nœud, vous devez:

1) Pointez sur l’élément qui pointe vers le nœud que vous souhaitez supprimer.

2) Définissez la référence à l’élément que vous souhaitez supprimer pour l’élément que vous souhaitez supprimer de l’élément suivant.

3) Supprimez l’élément que vous souhaitez supprimer.

De cette façon, votre chaîne est maintenue et vous avez libéré cet élément de la mémoire.

Ainsi:

 Head -> Item1 -> Item2 -> Item3 -> NULL 

Si vous voulez supprimer Item2, vous allez comme ceci:

 Head -> Item1 -> Item2 -> Item3 -> NULL ^ ^ (Grab pointers to these items) 

Définissez Item1 à côté de Item2, puis supprimez Item2.

  /--------------\ Head -> Item1 Item2 -> Item3 -> NULL ^ ^ (Delete 2) 

EDIT: Supprimer un élément ou un élément3:

 Head -> Item1 -> Item2 -> Item3 -> NULL ^ ^ (Grab pointers to these items) 

Renouvelez la tête sur Item2, puis supprimez Item1:

  /--------------\ Head Item1 -> Item2 -> Item3 -> NULL ^ ^ (Delete 1) 

OU

 Head -> Item1 -> Item2 -> Item3 -> NULL ^ ^ (Grab pointers to these items) 

Renouvelez la tête sur Item2, puis supprimez Item1:

  /--------------\ Head -> Item1 -> Item2 Item3 -> NULL ^ ^ (Delete 3) 

Voir si cela fonctionne pour vous ou pas, peut-être a été stocké dans mon PC quelque part pour une situation comme celle-ci:

 void RemoveNode(struct node*x) { struct node *temp=x,*tempo=NULL; int i=0,n; printf("\nWould you like to delete a node?\nPress 1 for Yes 2 for No: "); scanf("%d",&i); if(i==1) { printf("Enter nth node to be deleted"); scanf("%d",&n); i=0; if(n==1) { x=temp->next; free(temp); } while(inext; i++; } if(temp->next->next==NULL) { tempo=temp->next; temp->next=NULL; free(tempo); } else { tempo=temp->next; temp->next=temp->next->next; free(tempo); } } else printf("\n No Changes Made\nExiting...."); } 

C’est toujours la tête qui compte.