Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ЛІНІЙНІ ОДНОЗВ’ЯЗНІ ТА ДВОЗВ’ЯЗНІ СПИСКИ
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №5
з навчальної дисципліни “Програмування складних алгоритмів”
Тема:
ЛІНІЙНІ ОДНОЗВ’ЯЗНІ ТА ДВОЗВ’ЯЗНІ СПИСКИ
Варіант 7
Київ 20____
Мета:
Метою лабораторної роботи є ознайомитися з основами роботи з двозв’язним списком, однозв’язним списком, стеком та чергою.
Теоретична частина
Список – це лінійна послідовність елементів, кожен з яких має вказівник на своїх сусідів. Якщо елементи списку не мають вказівників на своїх сусідів, то список називають нелінійним. Кожен елемент списку повинен складатися, як мінімум з двох полів – це інформаційне поле та вказівник на наступний елемент. Інформаційне поле може набувати вигляду змінної будь-якого типу.
Над списками визначено наступні основні операції :
Додавання нового елемента, перед заданим;
видалення заданого елемента;
знаходження елемента за заданими властивостями;
перевірка чи порожній список;
сортування або впорядковування елементів списку за певним критерієм;
визначення розміру списку.
В залежності від типу та кількості зв’язків списки бувають таких видів:
Однонапрямлені:
Лінійний список, в якому кожний елемент має вказівник на наступний, називається однонапрямленим або однозв’язним списком, він є найпростішим типом списків. Одним з недоліків однонапрямленого списку – це те, що по однонапрямленому списку можна рухатися тільки в одному напрямку: від першого до останнього вузла, що при розв’язанні задач може викликати незручності. Так, наприклад, неможливо визначити адресу попереднього елемента.
Двонапрямлені:
Двонапрямленим або двозв’язним списком називається динамічна структура, кожен з елементів якої має вказівник як на наступний, так і на попередній елемент.
У такому списку набагато простіше видаляти та переставляти елементи, так як відомі адреси попереднього та наступного елементів списку.
Циклічні:
Циклічними або кільцевими списками називають двонапрямлені або однонапрямлені списки, в яких вказівник останнього вузла вказує на адресу першого вузла, або навпаки.
Завдання по варіанту
1. Створити лінійний однозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та настуні поміняти місцями. Виконати завдання згідно варіанту.
2. Створити двозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його. Виконати завдання згідно варіанту з двозв’язним списком.
№ Варіанту
Індивідуальне завдання
7
За один перегляд списку i без використання додаткових списку надрукувати елементи списку в наступному порядку: спочатку всi числа, менші за A, потім всi iншi числа. В кожнiй з груп зберегти взаємний порядок.
Результати виконання лабораторної роботи.
/
/
Створена програма працює з одно- та дво- зв’язним списками. Вона виконує поставлені задачі для обох видів списків.
Програмний код
import java.util.*; public class LR5 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.print("Виберіть список:\n1 - Однозв'язний\n2 - Двозв'язний\nВибір: "); int choiceOfTask = scan.nextInt(); if(choiceOfTask == 1) { SinglyLinkedList sList = new SinglyLinkedList(); System.out.print("\nВведіть кількість елементів: "); int amountOfElem = scan.nextInt(); for (int i = 0; i < amountOfElem; i++) { sList.addNode((int) (Math.random() * 20 - 10)); } System.out.println("Однозв'язний список: "); sList.display(); System.out.println("Завдання 1(1). Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та настуній поміняти місцями"); System.out.print("Введіть число: "); int value = scan.nextInt(); sList.task1(value); System.out.println("Результат:"); sList.display(); System.out.println("Завдання 1(2). За один перегляд списку i без використання додаткових списку надрукуватиелементисписку в наступному порядку: спочатку всi числа, меншi за A, потiм числа всi iншi числа.В кожнiй з груп зберегти взаємний порядок."); System.out.print("Введіть число: "); value = scan.nextInt(); sList.task12(value); sList.deleteList(); } if(choiceOfTask == 2) { DoublyLinkedList dList = new DoublyLinkedList(); System.out.print("\nВведіть кількість елементів: "); int amountOfElem = scan.nextInt(); for (int i = 0; i < amountOfElem; i++) { dList.addNode((int) (Math.random() * 20 - 10)); } System.out.println("Двозв'язний список:"); dList.display(); System.out.println("Завдання 2(1). Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та настуній поміняти місцями"); System.out.print("Введіть число: "); int value = scan.nextInt(); dList.task1(value); System.out.println("Результат:"); dList.display(); System.out.println("Завдання 2(2). За один перегляд списку i без використання додаткових списку надрукуватиелементисписку в наступному порядку: спочатку всi числа, меншi за A, потiм числа всi iншi числа.В кожнiй з груп зберегти взаємний порядок."); System.out.print("Введіть число: "); value = scan.nextInt(); dList.task12(value); dList.deleteList(); } } } class SinglyLinkedList { class Node{ int data; Node next; public Node(int data) { this.data = data; this.next = null; } } public Node head = null; public Node tail = null; public void addNode(int data) { Node newNode = new Node(data); if(head == null) { head = newNode; tail = newNode; } else { tail.next = newNode; tail = newNode; } } public void display() { Node current = head; if(head == null) { System.out.println("List is empty"); return; } while(current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } public void task1(int value) { Node current = head; while(current.next != null){ if(current.data == value){ head = head.next; } if (current.next.data == value) { if(current.next.next != null) { current.next = current.next.next; int t = current.data; current.data = current.next.data; current.next.data = t; } else{ current.next = null; break; } } current = current.next; } } public void task12(int value) { Node current = head; ArrayList<Integer> list = new ArrayList<Integer>(); while(current != null){ if(current.data < value) { System.out.print(current.data + " "); current = current.next; } else{ list.add(current.data); current = current.next; } } for (int i = 0; i < list.size(); i++) System.out.print(list.get(i)+" "); } void deleteList() { head = null; } } class DoublyLinkedList { class Node{ int data; Node previous; Node next; public Node(int data) { this.data = data; } } Node head, tail = null; public void addNode(int data) { Node newNode = new Node(data); if(head == null) { head = tail = newNode; head.previous = null; tail.next = null; } else { tail.next = newNode; newNode.previous = tail; tail = newNode; tail.next = null; } } public void display() { Node current = head; if(head == null) { System.out.println("Doubly linked list is empty"); return; } while(current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } public void task1(int value) { DoublyLinkedList.Node current = head; while(current != null) { if (current.data == value) { if(current != head) { int temp = current.previous.data; current.previous.data = current.next.data; current.next.data = temp; current.previous.next = current.next; } else{ head = head.next; } } current = current.next; } } public void task12(int value) { DoublyLinkedList.Node current = head; ArrayList<Integer> list = new ArrayList<Integer>(); while(current != null){ if(current.data < value) { System.out.print(current.data + " "); current = current.next; } else{ list.add(current.data); current = current.next; } } for (int i = 0; i < list.size(); i++) System.out.print(list.get(i)+" "); } void deleteList() { head = null; } }
Висновки.
При виконанні лабораторної роботи ознайомився з роботою списків. Для кожного списку створено методи для додавання нових елементів, для очищення списку та для реалізацію завдання.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора