В списке удалить все максимальные элементы

Question

Помогите написать цикл поиска максимальных элементов списка и цикл удаления найденных элементов. Мои наработки:

    #include <iostream>

    using namespace std;

    struct Node // Узел
    {
      int value; // Значение узла (значение)
      Node* next; // Следующий элемент узла
    };

    int main(int argc, char const* argv[]) {
      setlocale(LC_ALL, "Rus");

      Node* head = NULL; // голова списка
      Node* tail = NULL; // последний элемент списка

      int currentValue; // текущее значение
      Node* newNode = 0; // текущий узел

      int N;
      cout << "Введите кол-во чисел в списке: ";
      cin >> N;

      for (int i = 0; i < N; i++) {
        cout << "Введите число: ";
        cin >> currentValue;

        newNode = new Node();
        newNode -> value = currentValue;
        newNode -> next = NULL;
        if (head == NULL) {
          head = newNode;
          tail = newNode;
        } else {
          tail -> next = newNode;
          tail = newNode;
        }
      }
      Node* current = head; //Указатель на первый элемент списка (на голову)

      cout << "\nСписок до изменений: \n";
      while (current != NULL) {
        cout << current -> value << " ";
        current = current -> next;
      }
      cout << endl;

      //место для алгоритма удаления максимальных элементов

      current = head;

      cout << "\nСписок после изменений: \n";
      while (current != NULL) {
        cout << current -> value << " ";
        current = current -> next;
      }
      cout << endl;

      return 0;
    }

Answer 1

Для удаления элементов односвязного списка лучше использовать так называемый Carmack list, т.е. прием манипулирования элементами списка по адресу указателя на элемент списка.

Т.е. у нас есть указатель на указатель, который сначала указывает на head. При продвижении по списку он указывает на поле next в стуктуре Node (которое, в свою очередь адресует рассматриваемый элемент списка).

Допустим, что на шаге печати исходного списка мы нашли максимум в нем и запомнили в переменной vmax.

Тогда удаление из односвязного списка элементов равных vmax выглядит вот так:

  Node **p = &head;

  while (*p) {
    if ((*p)->value == vmax)
      *p = (*p)->next;
    else
      p = &(*p)->next;
  }

Остается скорректировать переменную tail.

Опять же, стоя на плечах титанов (в этот раз смотрим, как разбираются с содержимым списков в ядре linux)

#define container_of(field_addr, T, field_name)                        \
  ((T *)((char *)field_addr -                                        \
            (char *)&((T *)0)->field_name))

корректируем tail

  if (p == &head)
    tail = 0;
  else
    tail = container_of(p, Node, next);

БЛОГ НА HUSL

В списке удалить все максимальные элементы

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