0

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

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. Список односвязный, поэтому я могу двигаться только в одну сторону.

4

1 ответ 1

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

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

6
  • Прокомментируйте понятие "последние вхождения одинаковых элементов" (вот слово "последние" меня очень смущает здесь, что это значит?). Тот же самый вопрос к @artem_tmm.
    – 0andriy
    21 мар 2021 в 17:09
  • @0andriy, для меня очевидно, что это означает, что каждый элемент в списке с одинаковым значением value должен встречаться в списке один раз. При этом в списке должен остаться последний по времени включения в список такой элемент. Понятно, или дальше что-то про seqnum расписать?
    – avp
    21 мар 2021 в 18:32
  • А как вы знаете, что последний по времени == последнему в списке? Короче говоря, это слово здесь просто лишнее, надо так и писать, список из неповторяющихся элементов.
    – 0andriy
    21 мар 2021 в 20:26
  • @0andriy, ну, для понимания, что последний по времени == последний в списке просто посмотрите на функцию List* Add_last(int n, List* head). Если написать просто -- список неповторяющихся, то не определено, любой ли из повторяющихся можно оставить. Поэтому в вопросе и есть слова про последний
    – avp
    21 мар 2021 в 20:50
  • Но последний сам по себе может значить всё, что угодно. Это не добавляет ясности, а наоборот. Тогда надо добавлять пояснения, какой «последний». Скорее всего имелось в виду «последний встретившийся в списке от начала». А добавленный по времени — нет гарантии, что вы это как-то узнаете (в коде может быть и другие функции изменения списка).
    – 0andriy
    21 мар 2021 в 21:32

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.