Основи програмування на С ++ для початківців

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

У цій статті я опишу методику роботи з двонаправленим списком в класичному його варіанті. введення списку, висновок і сортування по природному розмаїттю та полях елементів списку. Не буду вдаватися в теорію списків – перейду до опису того, що необхідно зробити для вирішення даного завдання, і по ходу справи опишу чому саме так я організував роботу.

Для побудови списку нам знадобляться дві структури: одна – поля елемента списку. друга – сам елемент списку з якорями, які будуть зв'язувати елементи між собою.

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

Це структура даних списку. У ній повинні міститися поля, які безпосередньо до самого списку (вірніше до його структурі ) відношення не мають, зате зберігають інформацію. ця запис – контейнер (назвемо її так).

Другий запис:

Вона вже покликана зберігати в собі елемент контейнера, в який ми спакуємо дані, і поля для зв'язку з елементами-сусідами в списку.

Для чого знадобився такий розворот на дві структури? Так буде зручніше проводити сортування. У звичайних умовах список сортується шляхом перенаправлення його полів-якорів на інші елементи (наступного і перед в даному прикладі). Тобто,. самі дані, як були в пам'яті так в тій же комірці (осередках) і залишаються, а змінюються лише покажчики на сусідів. І це звичайно добре і правильно, але складно. Чим вище складність, тим більше ймовірність нарватися на баг в програмі. Тому варто спростити програму, щоб можна було не якоря міняти, а дані місцями (як зазвичай це робиться в сортуванні масивів наприклад). Тому доцільніше дані виділити в окремий блок-структуру, щоб перетягувати їх одним оператором, а не тягати кожне поле окремо. Нижче ви побачите що мається на увазі.

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

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

Її теж можна було розділити на дві: Перша створювала б елемент, друга наповнювала б його контейнер корисними даними, але це вже за смаком.

Не забуваємо про процедуру звільнення списку. Залишати сміття в пам'яті – дурний тон, навіть якщо розумна операційка сама вміє чиститься:

процедура виведення:

Така велика вона через “marafeta”. Гарний висновок на екран – досить важлива опціонально програми. Тому ширину для елементів і табличний вигляд варто дотримати.

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

У неї домовимося передавати опції сортування: ім'я поля, яке підлягає сортуванню, і напрямок сортування (по зростанню – по зростанню або по спадаючій – за зменшенням).

У процедурі застосована сортування бульбашкою, як найбільш ходова. У подвійному циклі відбувається виклик функції-аналізатора, яка повинна відповісти сортування, чи потрібно міняти місцями сортовані елементи чи ні. вид, прибравши умови сортування, я спростив код самої процедури сортування. Навіть якщо потрібно буде додавати якісь ще умови або поля, саму сортування вже не доведеться чіпати.

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

вона виконує 4 умови:

  1. Если по зростанню – за зростанням, і сортируемое поле – х:
  2. Если по спадаючій – за зменшенням, і поле той же
  3. Если по зростанню – за зростанням, але сортується друге поле, строковое
  4. Если по спадаючій – по спадаючій з строковим полем

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

Збираємо описане вище в одну програму і дописуємо функцію main():

Зверніть увагу: Я словами вказую, як сортувати список, по якому полю і в якому порядку.

Результат:

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

Про другому методі сортування списку шляхом перезацепленія якорів можете почитати на programmersforum

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

Опишу невеликий код із застосуванням цього контейнера, як альтернатива тому, що описано вище:

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

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

Вибір з цих двох методів варто робити в залежності від кількості корисних даних, що вводяться в елемент списку. Якщо це пара десятка полів з числами або невеликими рядками, то найпростіший спосіб, як раз – переміщення контейнера з корисними даними (як тут). Якщо ж елементи списку мають величезний розмір, то швидше буде виконуватися методика перестановки якорів (зміни останній і наступного для перезацепленія елемента до іншого елементу). У будь-якому випадку вибір за програмістом.

3 думки про "список двонаправлений. Сортування по полях і умов

  1. Це круто, але це ваш алгоритм замінено тільки поле даних в вузлах. Якщо вам потрібно зробити велику роботу, вам потрібно замінити покажчики:
    Сортування недійсними(вузол *&топ, вузол *&кінець) {
    if (топ && топ->наступного) {
    Вузол * ток = Вгору;
    Вузол * перед = nullptr;
    Вузол * TMP = nullptr;
    BOOL прапор = брехня;
    for (int i = 0; я поруч) {
    TMP = current->наступного;
    if (current->дані > tmp->дані) {
    прапор = істина;
    current->наступна = tmp->наступного;
    tmp->Наступного = ток;
    if (попередня)
    prev->наступна = TMP;
    tmp->перед = перед;
    перед = TMP;
    if (струму == Вгору)
    Top = TMP;
    if (!current->наступного)
    End = ток;

    }// якщо кінець
    else {
    перед = ток;
    ток = current->наступного;
    }
    }// Кінець в той час як
    if (!прапор)
    break;
    else {
    ток = Вгору;
    перед = nullptr;
    прапор = брехня;
    }
    }// для кінця
    }
    else
    cout << "\nNo entries for sorting\n";
    }

    1. Azizjan, почитай уважніше статтю. Посилання на метод, де дані залишаються на своєму місці я давав в реченні
      “Про другому методі сортування списку шляхом перезацепленія якорів можете почитати на programmersforum”
      Упевнений що новачкам корисно знати і такий і такий метод.

залишити коментар

Ваша електронна адреса не буде опублікований. Обов'язкові поля позначені * *