Лінійні однозв’язні та двозв’язні списки. Звіт до лабораторної роботи з Програмування складних алгоритмів. Робота № 100391

Перехід до торгівельного партнера Binance

Лінійні однозв’язні та двозв’язні списки

Інформація про навчальний заклад

ВУЗ:

Національний технічний університет України Київський політехнічний інститут

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

Інформація про роботу

Рік:

2022

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Програмування складних алгоритмів

Завантажити

Частина тексту файла (без зображень, графіків і формул):

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №5 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Лінійні однозв’язні та двозв’язні списки» Варіант № 20 Дата «18» червня 2022 Мета роботи: Метою лабораторної роботи є ознайомитися з основами роботи з двозв’язним списком, однозв’язним списком, стеком та чергою. Завдання до лабораторної роботи: 1. Створити лінійний однозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та наступні поміняти місцями. Виконати завдання згідно варіанту. 2. Створити двозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його. Виконати завдання згідно варіанту з двозв’язним списком. Завдання для варіанту 20: Видалити зі стеку всі елементи, які знаходяться перед мінімальним. Теоретичні відомості Списками називається динамічна структура даних, що являє собою множину зі змінної кількості елементів, що представлені в одному і тому ж форматі. Вони мають механізми для додавання та видалення певних елементів. Довжина списку дорівнює кількості елементів, які містяться в списку, список з нульовою довжиною називається порожнім списком. Списки є одним з методів організації множини даних, в якому елементи певного типу утворюють ланцюжок. Структура, в якій кожен елемент заданий в певному форматі та вони пов’язані між собою за допомогою вказівників, що записані в самих елементах, називається зв’язним списком. Елементи списків прийнято задавати як структуру даних з двома або більше полями — полем даних та вказівником на сусідній елемент. Поле вказівника останнього елемента на наступний, так само як поле вказівника першого елемента на попередній, повинно містити пустий вказівник — NULL. Сам список буде являти собою посилання на перший його елемент, який прийнято називати head. Також може мати посилання на останній елемент списка — tail. Однозв’язний список – це структура даних, що представляє з себе множину елементів, кожен з яких містить посилання на наступний елемент. Посилання в останньому елементі вказує на NULL. / Рисунок 1 — Візуалізація роботи однозв’язного списку Елементарними функціями над однозв’язними списками є: ініціалізація списку; додавання елемента у список; видалення елемента зі списку; друк (виведення) списку; пошук даних у списку. Для оптимізації та прискорення деяких операцій у списках може бути доцільно мати можливість переходити між вершинами в обидва напрямки. Для цього застосовується така динамічна структура даних як двоспрямований (двозв'язний) список. Двозв'язний список — це структура даних, що являє собою множину елементів, кожен з яких містить посилання на попередній та на наступний елемент. Посилання першого елемента на попередній та посилання останнього на наступний дорівнюють NULL. Сам список можна представити як посилання на перший елемент списку, а також останній, що дозволить здійснювати обхід списку з кінця в оберненому напрямку. / Рисунок 2 — Візуалізація роботи двозв’язного списку Стек — це динамічна структура даних, що зазвичай побудована на основі лінійного списку та працює за принципом LIFO (last in, first out, з англ. останнім прийшов – першим вийшов). Це означає, що елемент, що був останнім доданий в стек, буде витягнутий з нього в першу чергу. На відміну від списків, в стеку не можна отримати доступ до довільного елемента. Є можливість лише видаляти або додавати елементи, використовуючи особливі методи. Для пояснення стеку часто використовують аналогії з реального життя. Прикладом може послугувати стопка тарілок. Кожна нова тарілка ставиться зверху, а коли ми беремо тарілку зі стопки, то беремо її зверху, тобто ту, яку поставили останньою. Отже, стек має такі властивості: додаванняя елементів завжди відбувається з одного і того ж боку; діставання елементів завжди відбувається з того ж боку, що і додавання; доступ можна отримати лише до елемента, що був доданий останнім, всі інші лежать нерухомо, доки до них не дойде черга. Результат роботи / Висновки: У ході виконання даної лабораторної роботи було отримано практичні навички основ роботи з двозв’язним списком, однозв’язним списком, стеком та чергою. Код програми package com.company;import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.Scanner; public class LR_5 { public static void main(String[] args) { System.out.println("ЛР №5. Варіант 20"); System.out.println("Завдання 1. Створити лінійний однозв’язний список, вивести його"); SingleList singleList = new SingleList(); for (int i = 0; i< 10; i++) singleList.add((int)(Math.random() * 20) - 10); singleList.display(); System.out.println("Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та настуні поміняти місцями."); System.out.println("Вкажіть ключ (значення елементу):"); int key = new Scanner(System.in).nextInt(); singleList.task1_1(key); singleList.display(); System.out.println("Завдання варіанту: Видалити зі списку всі елементи, які знаходяться перед мінімальним"); singleList.task1_2(); singleList.display(); System.out.println("\nЗавдання 2. Створити двозв’язний список, вивести його"); DoubleList doubleList = new DoubleList(); for (int i = 0; i< 10; i++) doubleList.add((int)(Math.random() * 20) - 10); doubleList.display(); System.out.println("Якщо в списку є елемент із заданим ключем, вилучити його."); System.out.println("Вкажіть ключ (значення елементу):"); key = new Scanner(System.in).nextInt(); doubleList.task2_1(key); doubleList.display(); System.out.println("Завдання варіанту з двозвязним списком: Видалити зі списку всі елементи, які знаходяться перед мінімальним"); doubleList.task2_2(); doubleList.display(); } } class SingleList { 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) return; Element current = firstElement; while(current.next != null) { System.out.print(current.data + " | "); current = current.next; } System.out.print(current.data + "\n"); } public void task1_1(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); } public void task1_2() { Element current = firstElement; Element min = current; while(current.next != null) { if (current.data < min.data) min = current; current = current.next; } if (current.data < min.data) //Перевірка останнього min = current; firstElement = min; //Видалення усіх елементів, що знаходяться перед мінімальним } class Element { public int data; public Element next; public Element(int data, Element next) { this.data = data; this.next = next; } } } class DoubleList { Element firstElement; public void add(int data) { if (firstElement == null) { firstElement = new Element(data, null, null); return; } Element last = firstElement; while (last.next != null) last = last.next; last.next = new Element(data, last, null); } public void display() { Element current = firstElement; while(current.next != null) { System.out.print(current.data + " | "); current = current.next; } System.out.print(current.data + "\n"); } public void task2_1(int data) { if (firstElement.data == data) //Перевірка першого елементу { firstElement = firstElement.next; return; } Element current = firstElement.next; while (current.next != null) //Перевірка усіх основинх елементів { if (current.data == data) { current.previous.next = current.next; return; } current = current.next; } if (current.data == data) //Перевірка останнього елемнту current.previous.next = current.next; } public void task2_2() { Element current = firstElement; Element min = current; while(current.next != null) { if (current.data < min.data) min = current; current = current.next; } if (current.data < min.data) //Перевірка останнього min = current; firstElement = min; //Видалення усіх елементів, що знаходяться перед мінімальним } class Element { public int data; public Element previous; public Element next; public Element(int data, Element previous, Element next) { this.data = data; this.previous = previous; this.next = next; } } }

Звіт до лабораторної роботи Програмування складних алгоритмів

22.05.2023 11:05-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись