Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ЛІНІЙНІ ОДНОЗВ’ЯЗНІ ТА ДВОЗВ’ЯЗНІ СПИСКИ
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 5
з дисципліни «Програмування складних алгоритмів»
Тема «ЛІНІЙНІ ОДНОЗВ’ЯЗНІ ТА ДВОЗВ’ЯЗНІ СПИСКИ»
Варіант № 24
Дата «6» травня 2022
Мета роботи: Метою лабораторної роботи є ознайомитися з основами роботи з двозв’язним списком, однозв’язним списком, стеком та чергою.
Завдання до роботи
Методичні вказівки
Лабораторна робота спирається на знання й уміння, отримані при вивченні наступних питань лекції: Однозв’язний список є динамічною структурою даних, яка реалізує формування та обробку набору елементів. Елементи однозв’язного списку можуть бути посортованими або не посортованими. Однозв’язний список може зберігатися: в оперативній пам’яті; у файлі. Двозв’язний лінійний список – це список, в якому попередній компонент посилається на наступний, а наступний на попередній.
Завдання до лабораторної роботи:
1. Створити лінійний однозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та настуні поміняти місцями. Виконати завдання згідно варіанту.
2. Створити двозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його. Виконати завдання згідно варіанту з двозвязним спмском.
Завдання
/
1.2. Теоретичні відомості
Список – це лінійна послідовність елементів, кожен з яких має вказівник на своїх сусідів. Якщо елементи списку не мають вказівників на своїх сусідів, то список називають нелінійним. Кожен елемент списку повинен складатися, як мінімум з двох полів – це інформаційне поле та вказівник на наступний елемент. Інформаційне поле може набувати вигляду змінної будь-якого типу.
Над списками визначено наступні основні операції :
Додавання нового елемента, перед заданим;
видалення заданого елемента;
знаходження елемента за заданими властивостями;
перевірка чи порожній список;
сортування або впорядковування елементів списку за певним критерієм;
визначення розміру списку.
В залежності від типу та кількості зв’язків списки бувають таких видів:
Однонапрямлені:
Лінійний список, в якому кожний елемент має вказівник на наступний, називається однонапрямленим або однозв’язним списком, він є найпростішим типом списків. Одним з недоліків однонапрямленого списку – це те, що по однонапрямленому списку можна рухатися тільки в одному напрямку: від першого до останнього вузла, що при розв’язанні задач може викликати незручності. Так, наприклад, неможливо визначити адресу попереднього елемента.
Двонапрямлені:
Двонапрямленим або двозв’язним списком називається динамічна структура, кожен з елементів якої має вказівник як на наступний, так і на попередній елемент.
У такому списку набагато простіше видаляти та переставляти елементи, так як відомі адреси попереднього та наступного елементів списку.
Циклічні:
Циклічними або кільцевими списками називають двонапрямлені або однонапрямлені списки, в яких вказівник останнього вузла вказує на адресу першого вузла, або навпаки.
1.3. Результати роботи
Було створенно програму, яка створіює лінійний однозв’язний та двозв’язний списки. Виконує над ними операції, такі як видалення та заміна елементів.
1.4. Лістинг програми
package Algoritm.ua; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) { ArrayList<Integer> numbers = new ArrayList<Integer>(); Scanner scanner = new Scanner(System.in); int count = 20; for (int i = 0; i < count; i++) { numbers.add((int) (Math.random() * 20)); } System.out.println(Arrays.toString(numbers.toArray())); System.out.print("Введіть ключ пошуку: "); int key = scanner.nextInt(); int index = 0; for (int i = 0; i < numbers.size(); i++) { if (numbers.get(i) == key) { index = i; break; } } if (index != 0 | numbers.get(0) == key) { numbers.remove(index); if (index != 0) { int value = numbers.get(index - 1); numbers.remove(index - 1); numbers.add(value); System.out.println("\nРезультат роботи"); System.out.println(Arrays.toString(numbers.toArray())); System.out.printf("\nЧисло %d видалено зі списку", key); System.out.printf("\nЧисло %d поміняно місцями з наступними числами.\nТобто переміщено в кінець списку", value); } if (index == 0) { System.out.println("\nРезультат роботи"); for (var num : numbers) { System.out.print(" " + num); } System.out.printf("\nЧисло %d видалено зі списку", key); } } else System.out.println("\nNumber not found..."); System.out.print("\nВведіть змінну А: "); int a = scanner.nextInt(); ArrayList<Integer> arr1 = new ArrayList<>(); ArrayList<Integer> arr2 = new ArrayList<>(); for (int i = 0; i < numbers.size(); i++) { if (numbers.get(i) < a) { arr1.add(numbers.get(i)); } else { arr2.add(numbers.get(i)); } } System.out.println("\n\nЗавдання №1.2"); System.out.println("Початковий масив: " + Arrays.toString(numbers.toArray())); System.out.println("\nРезультат сортування згідно завдання №1"); System.out.printf("Масив чисел менших %d: ", a); System.out.println(Arrays.toString(arr1.toArray())); System.out.print("Масив усіх інших чисел: "); System.out.println(Arrays.toString(arr2.toArray())); System.out.println("\n\nЗавдання №2.1"); LinkedList<Integer> linkedList = new LinkedList<Integer>(); int count2 = 20; for (int i = 0; i < count2; i++) { linkedList.add((int) (Math.random() * 20)); } System.out.println("Початковий масив:"); System.out.println(Arrays.toString(linkedList.toArray())); System.out.print("\nВведіть ключ пошуку: "); int key2 = scanner.nextInt(); int index2 = -1; for (int i = 0; i < linkedList.size(); i++) { if (linkedList.get(i) == key2) { index2 = i; break; } } if (index2 != -1) { linkedList.remove(index2); System.out.println("Відредагований масив: "); System.out.println(Arrays.toString(linkedList.toArray())); } else System.out.println("\nNumber not found..."); System.out.print("\nВведіть змінну А: "); int a2 = scanner.nextInt(); ArrayList<Integer> array1 = new ArrayList<>(); ArrayList<Integer> array2 = new ArrayList<>(); for (int i = 0; i < linkedList.size(); i++) { if (linkedList.get(i) < a) { array1.add(linkedList.get(i)); } else { array2.add(linkedList.get(i)); } } System.out.println("\n\nЗавдання №2.2"); System.out.println("Початковий масив: " + Arrays.toString(linkedList.toArray())); System.out.println("\nРезультат сортування згідно завдання №1"); System.out.printf("Масив чисел менших %d: ", a2); System.out.println(Arrays.toString(array1.toArray())); System.out.print("Масив усіх інших чисел: "); System.out.println(Arrays.toString(array2.toArray())); } }
Результат виконання:
/
1.5. Висновки по роботі
При виконанні лабораторної роботи №5 було отримано практичні навички з роботи списками :створення, видалення та заміна.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора