6. Лабораторная работа 6. Списки и динамические массивы

В процессе написания тестовых заданий ознакомьтесь с основными конструкциями языка Java, принципами создания классов и объектов.

В процессе выполнения задания НЕЛЬЗЯ пользоваться утилитными классами Java.

Задание 1.

Создайте класс ScientificLibraryHall, описывающий научный зал библиотеки, который хранит динамический массив научных книг ввиде односвязного циклического списка.

Зал имеет имя по разделу науки.

Нумерация книг сквозная, начинается с 0. Номер книги не хранится.

Создайте соответствующие переменные и методы чтения/установки значений.

Создайте 2 конструктора:

3. принимающий имя зала и кол-во книг в зале;

4. принимающий имя зала и массив книг.

Создайте следующий методы для:

• получения количества книг в зале;

• выводящий на экран список названий всех книг в зале;

• получения общей стоимости всех книг в зале;

• получения книги по ее номеру в зале номеру (возвращает null, если элемент не найден);

• изменения книги по ее номеру;

• добавления книги по номеру;

• удаления книги по номеру.

Создайте метод getBestBook(), возвращающий книгу с самой высокой стоимостью.

Методические указания.

Однонаправленный связный список (односвязный список) – это динамическая структура данных, состоящая из элементов одного типа с определенной структурой: каждый элемент должен содержать данные и ссылку на следующий элемент, например

class Item {

public Book data; // данные

public Item next; // ссылка на такой же следующий элемент

}

Добавьте в этот класс конструктор (какой он должен быть?).

Класс самого списка должен содержать переменные:

• ссылку на первый элемент,

• количество элементов

и методы:

• конструктор(ы)

• isEmpty() – пустой список или нет

• возвращающий количество элементов

• возвращающий ссылку на элемент по номеру (возвращает null, если элемент не найден)

• добавление элемента по заданному номеру возвращает (true/false)

• удаление элемента по заданному номеру возвращает (true/false)

При написании методов добавления/удаления необходимо помнить, что

• проход по списку: если top– это ссылка на первый элемент в классе списка, то проход по списку будет выглядеть следующим образом

if( isEmpty() ) { return; }

Item p = top;

do{

//выполняем действия над текущем эл. списка

//…

p = p.next;

}while(p!=top);

• ссылка nextпоследнего элемента должна указывать на первый элемент, поскольку список циклический (т.е. представляет собой кольцо);

• для добавления/удаления элемента, необходимо встать на предшествующий ему элемент (что будет, если список содержит 1 элемент? если список пустой?);

• добавление в начало изменит ссылки на первый элемент и ссылку nextпоследнего элемента.

• в случае ошибки добавления/удаления элемента соответствующий метод должен возвращать falseи выводить текстовое сообщение (иначеtrue).

Напишите класс однонаправленного связного списка и протестируйте его отдельно от задания 1. После того, как класс будет работать корректно выполните задание 1.

Задание 2.

Создайте класс ScientificLibrary, описывающий научную библиотеку и содержащий динамический массив залов в виде двунаправленного циклического связного списка.

Нумерация залов в библиотеке сквозная, начинается с 0.

Нумерация книг в библиотеке сквозная, начинается с 0 нулевого зала.

Создайте 2 конструктора:

• принимающий количество залов и массив количеств книг по залам;

• принимающий массив залов.

Создайте методы получения:

• количества залов;

• количества книг;

• сумму всех книг в библиотеке;

• массива залов библиотеки;

• объекта зала по его номеру в библиотеке;

• объекта книги по его номеру в библиотеке;

• отсортированного по убыванию цены массива книг библиотеки.

Создайте еще методы:

• выводящий на экран список названий всех залов с количеством книг в них;

• замена зала по его номеру на другой (ссылка на новый зал передается вторым параметром);

• замена книги по ее номеру на другую (ссылка на другую книгу передается вторым параметром);

• добавление книги в библиотеку по ее номеру в библиотеке; ссылка на новую книгу – второй параметр метода; количество залов не увеличивается;

• удаление книги по ее номеру в библиотеке;

• метод getBestBook()получение самой лучшей книги в библиотеке (с самой большой ценой).

Методические указания.

Двунаправленный связный список – это динамическая структура данных, состоящая из элементов одного типа с определенной структурой: каждый элемент должен содержать данные и две ссылки - на следующий элемент и на предыдущий элемент, например

class Item2 {

public Book data; // данные

public Item2 prev; // ссылка на такой же предыдущий элемент

public Item2 next; // ссылка на такой же следующий элемент

}

Добавьте в этот класс конструктор (какой он должен быть?).

Класс самого списка должен содержать переменные:

• ссылку на первый элемент,

• ссылку на последний элемент,

• количество элементов

и методы:

• конструктор(ы)

• isEmpty() – пустой список или нет

• возвращающий количество элементов

• возвращающий ссылку на элемент по номеру (возвращает null, если элемент не найден)

• добавление элемента по заданному номеру возвращает (true/false)

• удаление элемента по заданному номеру возвращает (true/false)

При написании методов добавления/удаления необходимо помнить, что

• проход по списку: аналогичен проходу по односвязному списку;

• ссылка nextпоследнего элемента должна указывать на первый элемент, а ссылкаprevпервого элемента на последний, поскольку список циклический (т.е. представляет собой кольцо);

• реализации методов похожи на методы односвязного списка, но нужно помнить о специфике (две ссылки – на предыдущий и следующий элементы).

Напишите класс двунаправленного связного списка и протестируйте его отдельно от задания 2. После того, как класс будет работать корректно выполните задание 2.

Задание 3.

Проверьте работу классов, создав экземпляр научной библиотеки с различными произвольными значениями количества книг по залам. Добавьте книги в залы, библиотеки; измените книгу; измените зал; удалите книгу; для проверки каждого задания используйте методы распечатки списка залов и книг.

Выведите автора самой лучшей книги; выведите список названий книг по убыванию цены.

47