НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №5 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «ЛІНІЙНІ ОДНОЗВ’ЯЗНІ ТА ДВОЗВ’ЯЗНІ СПИСКИ» Варіант 13 Київ 2022 Мета: Метою лабораторної роботи є ознайомитися з основами роботи з двозв’язним списком, однозв’язним списком, стеком та чергою. Теоретичні відомості Лінійні списки - найпростіша форма організації даних з рекурсивною структурою. Цю форму застосовують найчастіше тоді, коли треба обробити деяку сукупність даних, кількість елементів яких заздалегідь не визначена, а взаємний порядок проходження відіграє важливу або вирішальну роль. Лінійний односпрямований (однозв'язний) список – дані динамічної структури, що являють собою сукупність лінійно зв'язаних однорідних елементів, до яких дозволяється додавати елементи на голови (початку) або в кінець (хвіст) списку, між будь-якими двома іншими і видаляти будь-який елемент. Для роботи з лінійним однозв'язним списком потрібні такі вказівники: 1) на голову списку Head; 2) кінець списку Tail, але можна обійтися й без нього; 3) k-й елемент списку; 4) тимчасовий для виділення пам'яті під елементи, які додаються, і для звільнення елементів, що видаляються (ідентифікатор р). Застосування однозв’язних лінійних списків може викликати певні труднощі, тому що за даним списком можна рухатися тільки в одному напрямку, від заголовної до останньої ланки списку. Тим часом нерідко необхідно здійснити обробку елементів, що передують елементу із заданою властивістю. Однак після знаходження елемента із заданою властивістю за допомогою функції для однозв’язного списку, у нас немає можливості зручного і швидкого доступу до попередніх йому елементів. Для досягнення цієї мети доведеться ускладнити алгоритм і свідомо ще раз послідовно перебирати елементи списку, починаючи з його заголовної ланки, що і незручно, і нераціонально. Щоб усунути цю незручність, додамо в кожну ланку списку ще один вказівник, значенням якого буде посилання на попередню ланку списку (next - вказівник на наступну, prev - на попередню ланку). Таку структуру називають двозв’язний список. Завдання до лабороторної роботи: 1. Створити лінійний однозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та настуні поміняти місцями. Виконати завдання згідно варіанту. 2. Створити двозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його. Виконати завдання згідно варіанту з двозвязним спмском. / Рисунок 1. Завдання 13 варіанту. Результат роботи/ Висновки: розроблено програму, що виконує створення однозв’язного списку, який має таку функціональність: є методи додавання у кінець списку нового елементу, вилучення вказаного елементу, міняючи місцями два сусідніх, та перевірка чи є підпослідовність зростаючою, та, якщо так, то ця підпослідовність перевертається в оборотньому порядку. Програмний код class SinglyLinkedList { private Element firstElement; public void add(int data) { if (firstElement == null) { firstElement = new Element(data, null); return; } Element last = firstElement; while (last.next != null) { last = last.next; } last.next = new Element(data, null); } public void display() { if (firstElement == null) { System.out.println("Пусто, нема що дивитись"); return; } Element current = firstElement; while(current.next != null) { System.out.print(current.data + " -> "); current = current.next; } System.out.print(current.data); } public void removeAndSwap(int data) { Element current = firstElement; do { current = current.next; if (current.data == data) { Element parent = firstElement; while(parent.next != current) parent = parent.next; parent.next = current.next; int temp = parent.data; parent.data = current.next.data; current.next.data = temp; return; } } while(current.next.next != null); System.out.println("Елемент або не знайдено, або він крайній"); return; } public void reversePartIfAscending(int n) { Element current = firstElement; int i = 1; List<Integer> ascendingList = new ArrayList<Integer>(); while(i <= n) { if (current.data > current.next.data && i != n) { System.out.printf("\nПослідовність від 1 до %d не впроядкована за зростанням!\n", n); return; } ascendingList.add(current.data); current = current.next; i++; } ascendingList.sort(Collections.reverseOrder()); List<Integer> descendingList = ascendingList; current = firstElement; i = 1; while(i <= n) { current.data = descendingList.get(i-1); current = current.next; i++; } } class Element { public int data; public Element next; public Element(int data, Element next) { this.data = data; this.next = next; } } }