Удаление элементов из односвязного списка

Question

Задание: Оставить в списке только последние вхождения одинаковых элементов.

struct List // Создание нового типа данных
{
    int value; // информационная часть
    List* next; // служебная часть
    List(int val = 0, List* p = NULL) // конструктор
    {
        value = val;
        next = p;
    }
};


List* head = NULL;


// Включение элемента в конец списка
List* Add_last(int n, List* head)
{
    List* q = new List(n), *p = head;
    if (head == NULL) return q;
    while (p->next != NULL)
        p = p->next;
    p->next = q;
    return head;
}


// Печать содержимого списка
void Print_list(List* head)
{
    List* p = head;
    puts("\n PRINT LIST");
    if (p == NULL) puts("Список пуст!");
    else
        while (p != NULL)
        {
            printf("%d ", p->value);
            p = p->next;
        }
}


List* remove(List * head) 
{
    List * j, *i = head , *t;
    int count = 0;

    while (i != NULL) // внешний цикл, обход списка
    { 
        for (j = i; j != NULL; j = j->next) // считаю количество одинаковых элементов
            if (j->value == i->value) count++; 

        j = i; // возвращаем указатель в начало


       while (count > 1)
        {
            if (i->value == j->value)
            {
                t = j;
                j = j->next;
                delete t;

                count--;
            }
            else j = j->next;
        }

        i = i->next;

        count = 0;
    }

    return head;
}


int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);

    List* head = NULL;
 
    head = Add_last(1, head);
    head = Add_last(2, head);
    head = Add_last(1, head);
    head = Add_last(1, head);
    head = Add_last(4, head);

    Print_list(head);

    head = remove(head);

    printf("");

    Print_list(head);

    return 0;
}

программа просто прекращает работу после запуска функции remove

P.S. Список односвязный, поэтому я могу двигаться только в одну сторону.

Answer 1

Сложность алгоритма удаления элемента из односвязного списка состоит в том, что нужно менять указатель на следующий, у элемента предшествующего удаляемому. В случае, если удаляем первый в списке, надо менять указатель на список.

Я предлагаю для решения вашей задачи другой алгоритм.

Для начала, сделаем временный, перевернутый список, строящийся путем перемещения элемента (только изменение указателей, а не удаление старого и создание нового) из одного списка в другой. Таким образом, последний из повторов каждого элемента станет первым в новом списке.

Далее будем перемещать из временного списка в результирующий только те элементы, дубликатов которых нет в результирующем списке.

Строить этот результирующий список будем также перевернутым, т.о. мы получим требуемый результат, т.е. исходный список в котором содержатся только последние вхождения одинаковых элементов.

List *remove (List *head)
{
  List *tmp = 0, *t;

  while ((t = head)) { // reverse the list
    head = t->next;

    t->next = tmp;
    tmp = t;
  }

  while ((t = tmp)) { // build result as reverse list
    tmp = t->next;

    // search t in result
    int found = 0;
    for (List *p = head; p; p = p->next)
      if (t->value == p->value) {
        found = 1;
        break;
      }
    if (found)
      delete t;
    else {
      t->next = head;
      head = t;
    }
  }
    
  return head;
}

Что непонятно, спрашивайте в комментариях.

БЛОГ НА HUSL

Удаление элементов из односвязного списка

Ответы (1 шт):