C: Supprimer les doublons de la liste des liens non sortingés

Je travaille sur ce problème depuis plus d’heures que ce que je voudrais admettre maintenant et cela me rend fou. Étant donné une simple liste chaînée, disons celle qui stocke un entier ( data ) uniquement en plus d’un pointeur sur le prochain noeud ( next ), j’aimerais un algorithme qui supprime les doublons sans sortinger ni s’appuyer sur des fonctions d’assistance.

Des questions précédentes ont été posées sur les listes de liens non classées en Java, qui tirent parti des fonctions d’assistance offertes par Java. Ceci est ssortingctement pertinent pour C sans l’utilisation de fonctions d’assistance.

J’ai bricolé avec du code et l’ai fait fonctionner dans certains cas, mais pas tous. Voici un exemple complet et vérifiable – j’ai inclus une fonction push() pour créer une liste liée et un main() avec des cas de test, mais la logique à laquelle ma question se rapporte est dans removeDuplicates() uniquement:

 #include  #include  struct node { int data; struct node *next; }; void push(struct node **headRef, int data) { struct node *newNode = malloc(sizeof(struct node)); newNode->data = data; newNode->next = *headRef; *headRef = newNode; } void removeDuplicates(struct node **head) { struct node *currentNode = *head; //The node we compare other nodes against struct node *runningNode = (*head)->next; //The node we are comparing to struct node *runningNodePrev = *head; //The node before the node we are comparing to struct node *runningNodeNext = (*head)->next->next; // The node after the node we are comparing to int count = -1; while (currentNode->next != NULL) { //Ensure we are not looking at the last node -- cannot have comparisons past this node count++; if (count) { //'Base Position' currentNode = currentNode->next; runningNodePrev = currentNode; runningNode = currentNode->next; runningNodeNext = runningNode->next; } printf("\nChecking for a match with %d ... \n", currentNode->data); while (runningNode != NULL) { //Compare each node in the list until we reach the end of the list printf("Inspecting next adjacent node ... \n"); if (runningNode->data == currentNode->data) {//If a duplicate is found printf("Found match ... "); //Ensure link is maintained before removing duplicate node if (currentNode == runningNodePrev) currentNode->next = runningNodeNext; runningNodePrev->next = runningNodeNext; free(runningNode);//Delete duplicate node printf("Deleted duplicate.\n"); } runningNode = runningNodeNext;//Continue searching for duplicates at the first unchecked node runningNodeNext = runningNodeNext->next;//Move running node leader up the list. } } } int main(void) { struct node *t1 = NULL; struct node *t2 = NULL; struct node *t4 = NULL; struct node *t5 = NULL; push(&t1, 1); push(&t1, 1); push(&t1, 1); push(&t1, 1); push(&t2, 6); push(&t2, 1); push(&t2, 2); push(&t2, 3); push(&t2, 4); push(&t2, 5); push(&t2, 6); push(&t4, 4); push(&t4, 2); push(&t4, 3); push(&t4, 2); push(&t4, 1); push(&t5, 0); push(&t5, 0); push(&t5, 1); printf("Testing removeDuplicates()...\n"); printf("Case 1: Calling removeDuplicates({1,0,0}).\n"); printf("Expected result: { 1 0 }\n"); printf("Actual result: { "); removeDuplicates(&t5); ptr = t5; while (ptr != NULL) { printf("%d ", ptr->data); ptr = ptr->next; } printf("}\n"); printf("Case 2: Calling removeDuplicates({1,2,3,2,4}).\n"); printf("Expected result: { 1 2 3 4 }\n"); printf("Actual result: { "); removeDuplicates(&t4); ptr = t4; while (ptr != NULL) { printf("%d ", ptr->data); ptr = ptr->next; } printf("}\n"); printf("Case 3: Calling removeDuplicates({6,5,4,3,2,1,6}).\n"); printf("Expected result: { 6 5 4 3 2 1 }\n"); printf("Actual result: { "); removeDuplicates(&t2); ptr = t2; while (ptr != NULL) { printf("%d ", ptr->data); ptr = ptr->next; } printf("}\n"); printf("Case 4: Calling removeDuplicates({1,1,1,1}).\n"); printf("Expected result: { 1 }\n"); printf("Actual result: { "); removeDuplicates(&t1); ptr = t1; while (ptr != NULL) { printf("%d ", ptr->data); ptr = ptr->next; } printf("}\n"); } 

J’ai également inclus une image décrivant la logique si ce que je fais ne semble pas clair: http://imgur.com/DbnBOq2

 /* Program to remove duplicates in an unsorted linked list */ #include  using namespace std; /* A linked list node */ struct Node { int data; struct Node *next; }; // Utility function to create a new Node struct Node *newNode(int data) { Node *temp = new Node; temp->data = data; temp->next = NULL; return temp; } /* Function to remove duplicates from a unsorted linked list */ void removeDuplicates(struct Node *start) { struct Node *ptr1, *ptr2, *dup; ptr1 = start; /* Pick elements one by one */ while (ptr1 != NULL && ptr1->next != NULL) { ptr2 = ptr1; /* Compare the picked element with rest of the elements */ while (ptr2->next != NULL) { /* If duplicate then delete it */ if (ptr1->data == ptr2->next->data) { /* sequence of steps is important here */ dup = ptr2->next; ptr2->next = ptr2->next->next; delete(dup); } else /* This is sortingcky */ ptr2 = ptr2->next; } ptr1 = ptr1->next; } } /* Function to print nodes in a given linked list */ void printList(struct Node *node) { while (node != NULL) { printf("%d ", node->data); node = node->next; } } /* Druver program to test above function */ int main() { /* The constructed linked list is: 10->12->11->11->12->11->10*/ struct Node *start = newNode(10); start->next = newNode(12); start->next->next = newNode(11); start->next->next->next = newNode(11); start->next->next->next->next = newNode(12); start->next->next->next->next->next = newNode(11); start->next->next->next->next->next->next = newNode(10); printf("Linked list before removing duplicates "); printList(start); removeDuplicates(start); printf("\nLinked list after removing duplicates "); printList(start); return 0; } 

Référence: geeksforgeeks

 void removeDuplicates(struct node **head){ struct node *tmp; while (*head) { /* Look below *head, to see if it has any duplicates */ for (tmp= (*head)->next; tmp; tmp = tmp->next) { if (tmp->data == (*head)->data) break; } /* Found no duplicate: advance head */ if(!tmp) { head = &(*head)->next; continue;} /* Duplicate found :: delete *head */ tmp = (*head)->next; free(*head); *head = tmp; } return; } 

Maintenant, vérifiez les cas de coin:

  • si * head est NULL, la boucle externe n’est jamais exécutée: rien ne se passe
  • if (* head) -> next est NULL, la boucle interne n’est jamais exécutée, donc tmp est toujours NULL après la boucle interne
  • si un doublon est trouvé * head est remplacé par son pointeur -> suivant (qui pourrait être NULL)
  • si aucun doublon n’est trouvé, * head est simplement avancé à son pointeur suivant -> (qui pourrait être NULL)

Ce type de question est souvent posé dans différentes variantes. Habituellement, quand on implémente une liste chaînée, on finit par en arriver à un point où il faut garder beaucoup trop de pointeurs sur divers éléments. À première vue, il peut sembler qu’une seule redirection est plus facile à gérer, alors qu’elle ne transmet pas assez d’informations sur la liste pour effectuer l’opération localement.

Voici la fonction réécrite (mais pas complètement testée) pour utiliser l’abstraction “link” (qui est essentiellement un struct node** ):

 void removeDuplicates(struct node** head) { if(!head) return; struct node **link = head; // We will iterate over the links. Ie the `next` pointers in the list. while(*link) { struct node **rest = &((*link)->next); while(*rest) { if ((*link)->data != (*rest)->data) { rest = &((*rest)->next); // move to the next link } else { // modify the current link of rest to look one past the next struct node *to_remove = *rest; *rest = to_remove->next; free(to_remove); } } link = &((*link)->next); // again, move the the next link } } 

En utilisant un autre niveau d’indirection, il est possible de garantir que l’iterator que nous utilisons pour parcourir la liste n’est invalidé à aucun moment. Il n’ya aucun moyen (sauf erreur d’écriture) que la boucle ci-dessus puisse invalider *link , et il n’est donc pas nécessaire de vérifier avant l’affectation link = &((*link)->next);

Un merci spécial à @StoryTeller – Je n’ai pas vérifié votre solution, mais votre commentaire sur le fait d’avoir trop de pointeurs était sans aucun doute essentiel. J’ai réécrit ma fonction et elle fonctionne maintenant pour 4 cas différents et spéciaux (doublons en fin de liste, en début de liste, au hasard dans la liste, liste composée uniquement de doublons). Voici le bon code:

 void removeDuplicates(struct node** head){ struct node* currentNode = *head; struct node* runningNode = (*head)->next; struct node* runningNodePrev = *head; int count = -1; while(currentNode->next != NULL){ count++; if(count){ currentNode = currentNode->next; runningNodePrev = currentNode; runningNode = currentNode->next; } while(runningNode != NULL){ if(runningNode->data == currentNode->data){ runningNodePrev->next = runningNode->next; free(runningNode); runningNode = runningNodePrev->next; }else{ runningNodePrev = runningNodePrev->next; runningNode = runningNode->next; } } } } 

Cordialement et merci à tous ceux qui ont commenté.