C: Удалить дубликаты из несвязанного связанного списка.

Я работаю над этой проблемой в течение нескольких часов, чем я хотел бы признать сейчас, и это сводит меня с ума! Учитывая простой связанный список, скажем, который хранит целое число ( data ) только в дополнение к указателю на следующий узел ( next ), мне нужен алгоритм, который удаляет дубликаты без сортировки или использования вспомогательных функций.

Предыдущие вопросы заданы в отношении несортированных связанных списков в Java, которые используют вспомогательные функции, предлагаемые Java. Это строго относится к C без использования вспомогательных функций.

Я возился с кодом и получил это для работы в некоторых случаях, но не для всех. Вот полный, проверяемый пример: у меня есть функция push() для создания связанного списка и main() с тестовыми removeDuplicates() , но логика, о которой мой вопрос относится, относится только к removeDuplicates() :

 #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"); } 

Я также включил изображение, которое описывает логику, если неясно, что я делаю: 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 tricky */ 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; } 

    Ссылка: 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; } 

    Теперь проверьте угловые шкафы:

    • если * head NULL, внешний цикл никогда не выполняется: ничего не происходит
    • if (* head) -> next is NULL, внутренний цикл никогда не выполняется, поэтому tmp по-прежнему NULL после внутреннего цикла
    • если найден дубликат * head заменен на его -> следующий указатель (который может быть NULL)
    • если дубликат не найден, * головка просто переместится на свой -> следующий указатель (который может быть NULL)

    Такого рода вопрос задают много в разных вариантах. Обычно, когда кто-то реализует связанный список, он в конечном итоге подходит к точке, где нужно удержать слишком много указателей на различные элементы. На первый взгляд может показаться, что с одним redirectм легче работать, когда на самом деле он не передает почти достаточную информацию о списке, чтобы выполнить операцию локально.

    Здесь функция перезаписана (но не полностью протестирована), чтобы использовать абстракцию «link» (которая по существу является 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 } } 

    Используя другой уровень косвенности, можно гарантировать, что iterator, который мы используем для перемещения по списку, не будет признан недействительным в любой момент. Невозможно (запретить ошибки при написании), что вышеописанный цикл может аннулировать *link , и поэтому нет необходимости проверять перед link = &((*link)->next); назначения link = &((*link)->next);

    Особая благодарность @StoryTeller – я не проверял ваше решение, но ваш комментарий о том, что слишком много указателей, определенно был ключевым. Я переписал свою функцию, и теперь она работает для 4-х различных и специальных случаев (дубликаты в конце списка, в начале списка, случайно в списке, список, состоящий исключительно из дубликатов). Вот правильный код:

     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; } } } } 

    Приветствия и спасибо всем, кто прокомментировал.