C Функция оставить только уникальные узлы в одиночном списке

Question

У меня проблема: в функции программа должна сравнивать два узла и удалять одну из них, если значения узлов одинаковы (пример: A -> B -> B -> C >>> A -> B -> C). В нескольких словах: он должен оставлять только уникальные узлы.

Шаги, которые я сделал: созданный список из данных, данных в файле данных, и он отлично распечатывается. Теперь я пытаюсь сравнить два узла.

Шаги, которые я собираюсь сделать: Поместите два значения узлов в две разные переменные, а затем сравните эти два и, если последний узел равен предыдущему, удалите последнюю и каким-то образом привяжите предыдущий узел к следующему узлу. Затем цикл повторяется снова и снова.

Вопрос: Как сравнить узел с другим?

Вот код, который я прямо сейчас:

#include <stdio.h> 
#include <stdlib.h> 
#define LENGTH 255 

struct node { 
    int info; 
    struct node *next; 
} *head = NULL; 

int create(FILE **data){ 
    char read[LENGTH]; 
    printf("Write data file name: "); 
    scanf("%s", read); 
    *data = fopen (read, "r"); 

    if (data == NULL) { 
     printf("Error reading given file."); 
    } 

    return 0; 
} 

int put_Symbols_into_list(FILE *data) { 

    struct node *new_node, *current; 
    char c; 

    printf("Data given: "); 
    while (!feof(data)){ 
     new_node = (struct node*)malloc(sizeof (struct node)); 
     c = fscanf(data, "%s", &new_node -> info); 
     printf("%s ", &new_node -> info); 

     if (head == NULL){ 
      head = new_node; 
      current = new_node; 
     } else { 
      current -> next = new_node; 
      current = new_node; 
     } 
    } 

} 

int delete_Same_Symbols() { 

} 

int main() { 
    FILE *data; 
    struct node *n; 
    create(&data); 
    put_Symbols_into_list(data); 
    delete_Same_Symbols(); 
    //display_List(n); 
    return 0; 
} 

Answer 1

Эффективный способ удаления дубликатов заключается в следующем:

1. Sort the list 
2. Run through the list once deleting any adjacent duplicates. 

Работает ли это решение для вас, зависит от того, может ли ваши данные будут приказал.

Answer 2

Пройдите список от головы до конца и сохраните таблицу хэшей. Для каждого элемента проверьте, находится ли значение в хэш-таблице: если да, удалите узел; else положите значение в хеш-таблицу.

Сложность времени: O (n) в среднем (при условии, что время доступа хэш-таблицы равно O (1) в среднем).

Answer 3

Я дам вам функцию, которая удалит дубликаты. Предполагая, что ваш код работает нормально, и что информация является INT значение Обратите внимание, что если информация является строкой, то вам нужно STRCMP функцию вместо head->info == info.

int exist(NODE *head, int info) { 
    while (head && head->info != info) // strcmp(info,head->info) != 0 
     head = head->next; 

    return head->info == info; // strcmp(info,head->info) 
} 

void removeDuplicates(NODE **phead, int info) { 
    NODE *tmp = *phead; 
    while (tmp->info != info) // strcmp(info,head->info) != 0 
     tmp = tmp->next; 
    NODE *tmp1 = tmp->next; 
    tmp->info = tmp1->info; // strcpy(tmp->info,tmp1->info) 
    tmp->next = tmp1->next; 
    free(tmp1); 
}