Основы программирования на С++ для начинающих

Список двунаправленный. Сортировка по полям и условиям

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

Для построения списка нам понадобятся две структуры: Одна – поля элемента списка. Вторая – сам элемент списка с якорями, которые будут связывать элементы между собой.

Первая структура может выглядеть так:

Это структура данных списка. В ней должны содержаться поля, которые непосредственно к самому списку (вернее к его структуре ) отношения не имеют, зато хранят информацию. Эта запись – контейнер (назовем ее так).

Вторая запись:

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

Для чего понадобился такой разворот на две структуры? Так будет удобнее производить сортировку. В обычных условиях список сортируется путем перенаправления его полей-якорей на другие элементы (Next и Prev в данном примере). Т.е. сами данные, как были в памяти так в той же ячейке (ячейках) и остаются, а меняются только указатели на соседей. И это конечно хорошо и правильно, но сложно. Чем выше сложность, тем больше вероятность нарваться на баг в программе. Поэтому стоит упростить программу, чтобы можно было не якоря менять, а данные местами (как обычно это делается в сортировке массивов к примеру). Поэтому целесообразнее данные выделить в отдельный блок-структуру, чтоб перетягивать их одним оператором, а не таскать каждое поле отдельно. Ниже вы увидите что имеется ввиду.

Для работы со списком нужны переменные головы списка и, по необходимости, хвоста:

И вот так уже будет выглядеть процедура наполнения списка:

Ее тоже можно было разделить на две: Первая создавала бы элемент, вторая наполняла бы его контейнер полезными данными, но это уже по вкусу.

Не забываем о процедуре освобождения списка. Оставлять мусор в памяти – дурной тон, даже если умная операционка сама умеет чиститься:

Процедура вывода:

Такая большая она из-за “марафета”. Красивый вывод на экран – достаточно важная опциональность программы. Поэтому ширину для элементов и табличный вид стоит соблюсти.

Теперь переходим к самому интересному – сортировке списка. Процедуру сортировки я разбил на две части, убрав из нее условия проверки, которые анализируют нужно ли сортируемые элементы продвигать по списку в зависимости от условия. Сама же процедура сортировки выглядит так:

В нее договоримся передавать опции сортировки: Имя поля, которое подлежит сортировке, и направление сортировки (asc – по возрастанию или desc – по убыванию).

В процедуре применена сортировка пузырьком, как самая ходовая. В двойном цикле происходит вызов функции-анализатора, которая должна ответить сортировке, нужно ли менять местами сортируемые элементы или нет. Видите, убрав условия сортировки, я упростил код самой процедуры сортировки. Даже если нужно будет добавлять какие-то еще условия или поля, саму сортировку уже не придется трогать.

Функция анализатор выглядит так:

Она выполняет 4 условия:

  1. Если asc – по возрастанию, и сортируемое поле – х:
  2. Если desc – по убыванию, и поле то же
  3. Если asc – по возрастанию, но сортируется второе поле, строковое
  4. Если desc – по убыванию с строковым полем

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

Собираем описанное выше в одну программу и дописываем функцию main():

Обратите внимание: Я словами указываю, как сортировать список, по какому полю и в каком порядке.

Результат:

сортировка двунаправленного списка в С++

О втором методе сортировки списка путем перезацепления якорей можете почитать на programmersforum

По просьбе коллег по сайту (которые конечно же правильно заметили) стоит хотя бы вкратце упомянуть о прелестях C++ и STL. Имею ввиду класс list, который собственно олицетворяет списки (двунаправленные). Посыл простой: Все, что нужно для работы со списком уже сделали. По хорошему, программисту, работающему со списками, конечно же стоит в бытовых случаях избирать для работы STL.

Опишу небольшой код с применением этого контейнера, как альтернатива тому, что описано выше:

сортировка двунаправленного списка в С++

Если задача позволяет использовать STL – используйте. Решение окажется надежнее и не будет траты времени на изобретения своего механизма хранения списков.

Выбор из этих двух методов стоит делать в зависимости от количества полезных данных, что вводятся в элемент списка. Если это пара десятка полей с числами или небольшими строками, то самый простой способ, как раз – перемещение контейнера с полезными данными (как здесь). Если же элементы списка имеют огромный размер, то быстрее будет выполняться методика перестановки якорей (изменения Last и Next для перезацепления элемента к другому элементу). В любом случае выбор за программистом.

3 thoughts on “Список двунаправленный. Сортировка по полям и условиям

  1. It’s cool but this your algorithm replaced only data fields in nodes. If you gotta do great job you need replace pointers:
    void Sort(Node *&Top, Node *&End) {
    if (Top && Top->next) {
    Node *current = Top;
    Node *prev = nullptr;
    Node *tmp = nullptr;
    bool flag = false;
    for (int i = 0; i next) {
    tmp = current->next;
    if (current->data > tmp->data) {
    flag = true;
    current->next = tmp->next;
    tmp->next = current;
    if (prev)
    prev->next = tmp;
    tmp->prev = prev;
    prev = tmp;
    if (current == Top)
    Top = tmp;
    if (!current->next)
    End = current;

    }// The if end
    else {
    prev = current;
    current = current->next;
    }
    }// The while end
    if (!flag)
    break;
    else {
    current = Top;
    prev = nullptr;
    flag = false;
    }
    }// The for end
    }
    else
    cout << "\nNo entries for sorting\n";
    }

    1. Azizjan, почитай внимательнее статью. Ссылку на метод, где данные остаются на своем месте я давал в предложении
      “О втором методе сортировки списка путем перезацепления якорей можете почитать на programmersforum”
      Уверен что новичкам полезно знать и такой и такой метод.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *