Применение коллекций в Java 2 обеспечивается специальным средством JavaCollectionFramework.

Иерархия коллекции:

ИнтефейсCollection (базовый «класс») – предусматривает наиболее общие операции для совокупностей элементов.

ИнтефейсSet (множество) – соответствует математическому понятию "множество". Не допускает дубликатов.

Интерфейс List (список), допускает дубликаты.

Интерфейс Queue – как список, но FIFO(что такое FIFO я не знаю).

19. Составные части JCF и их назначение:

JCF состоит из:

Интерфейсов (обозначают функциональность)

Реализаций (ориентируются на один из вариантов реализации)

Алгоритмов (методов решения типовых задач)

Интерфейсы:

Интерфейс Collection – базовый для интерфейсов List (списки), Set (множества) и SortedSet (множества с порядком). Интерфейсы List и SortedSet содержат дополнительные методы, упрощающие некоторые действия:

booleanadd(E e) добавляет e типа E в коллекцию, true, если удалось.

booleanaddAll(Collection<? extends E> c) добавляетвсеэлементыкол. c

voidclear() удаляет все элементы коллекции.

booleancontains(Object o) проверка принадлежности o коллекции

booleanisEmpty() проверяет, что коллекция пуста.

Iterator<E>iterator() создает итератор для перебора элементов коллекции.

booleanremove(Object o) удаляет элемент o из коллекции, true, если удалось.

intsize() дает количество элементов коллекции.

Реализации:

Примеры создания пустого списка с элементами типа String на основе массива и на основе связного списка:

List<String> A=new ArrayList<String>();

List<String> B=new LinkedList<String>();

Алгоритмы:

Алгоритмы для решения типовых задач, в которых данными являются коллекции, содержатся в классе java.util.Collections. Алгоритмы обеспечивают сортировку данных (sort), перемешивание данных (shuffle), поиск элементов (binarySearch), поиск экстремальных элементов (min, max).

20. Назначение интерфейсов и алгоритмов JCF:

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

Алгоритмы для решения типовых задач, в которых данными являются коллекции, содержатся в классе java.util.Collections. Алгоритмы обеспечивают сортировку данных (sort), перемешивание данных (shuffle), поиск элементов (binarySearch), поиск экстремальных элементов (min, max).

21. Примеры (двух) интерфейсов и (двух) реализаций: сходства и различия:

Реализации (классы, реализующие методы интерфейсов):

Примеры создания пустого списка с элементами типа String на основе массива и на основе связного списка:

List<String> A=new ArrayList<String>();

List<String> B=new LinkedList<String>();

Интерфейсы (определяют функциональность коллекции):

m.listA.remove(m.listA.size()-1); // А без последнего элемента

setMA.addAll(setMB); //объеденение множества МА и МВ

22. Преимущества, получаемые от применения JCF в программах:

· Снижает затраты на программирование, т.к. полезные структуры данных и алгоритмы уже готовы

· Повышает эффективность программ, т.к. применяются хорошо сделанные структуры данных и алгоритмы

· Облегчает адаптацию программ, т.к. интерфейсы взаимозаменяемы

· Снижает затраты на изучение, поскольку интерфейсы единообразны

· Снижает затраты на разработку своих интерфейсов, т.к. могут быть использованы типовые интерфейсы

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

23. Коллекции: списки – основные методы интерфейса List:

Список – упорядоченная коллекция (последовательность).

Интерфейс List добавляет к методам интерфейса Collection методы, использующие индекс index элемента:

voidadd(intindex, objectobj) — вставляет элемент obj в позицию index;

booleanaddAll(intindex, Collectioncol) — вставляет все элементы коллекции col;

objectget(intindex) — возвращает элемент, находящийся в позиции index;

intindexOf(Objectobj) — возвращает индекс первого появления элемента obj в коллекции;

intlastindexOf (objectobj) — возвращает индекс последнего появления элемента obj в коллекции;

Listiteratorlistiterator () — возвращает итератор коллекции;

Listiteratorlistiterator (intindex) — возвращает итератор конца коллекции от позиции index;

24. Коллекции: множества – основные элементы интерфейса Set:

Множества - (неупорядоченные) совокупности элементов, не содержащие дублей.

Методы интерфейса Set –такие же, как и методы методыинтерфейсаList

Сами методы закодированы в реализациях: HashSet, TreeSet, LinkedHashSet.

HashSet – таблица с перемешиванием, (быстрый доступ, но порядок может измениться при добавлении новых элементов)

TreeSet – элементы упорядочены по величине, хранятся в виде "черно-красного" дерева

LinkedHashSet – элементы упорядочены моментом появления, порядок элементов не изменяется при добавлении новых элементов

25. Выполнение стандартных операций теории множеств:

Операции для множества (А,B –множества):

· добавить элемент а: А+а add()

· удалить элемент а: А\а remove()

· пересечение множеств А и В retainAll()

· объединение множеств А и В addAll()

· вычитание А \ В removeAll()

· равенство множеств А и В =

· включение множества Вв множество А

 

Метод clear() – удаляет все элементы в коллекции.

setMA.addAll(setMB);//объеденение множества МА и МВ

m.listA.remove(m.listA.size()-1);// A без последнего знака

setMC=setMA;// равенство множеств

int MC = setMC.size();//мощность МС

26. Списки и множества: сходства и различия:

Сходства: оба интерфейса наследники Collection, имеются общие методы от Collection.

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

27. Цикл for-each и его применение в коллекциях:

Цикл перебирает каждый элемент массива A и записывает его в переменную a, для каждого элемента массива выполняется тело цикла:

classForEach{

public static void main(String[ ] arg){

int[ ] A= new int[ ]{1,3,2,4,6,5};

for (int a:A) { a++;System.out.print (a+” “); }

System.out.println();

} }

Внимание! a++ изменяет элемент, но не изменяет коллекцию (для контроля – вывод при помощи обычного цикла).

28. Математическая идея, представленная элементом Map:

Map –"словарь", содержащий пары (ключ, значение). Например (термин, разъяснение). (map – отображение). Запрещается дублирование ключей. Map - математическое понятие "однозначная функция".

Типовые операции:

put – добавить пару (ключ, значение),

get – получить значение для данного ключа,

containsKey – проверить, присутствует ли данный ключ,

containsValue –проверить, присутствует ли данное значение

size – определение размера коллекции (количества пар),

isEmpty – проверка присутствия элементов

Пример: y = x²; I = U/R и так далее.

Вопрос 29. Сравнительный анализ реализаций ArrayList и LinkedList.

 

ArrayList — реализует интерфейс List. Как известно, в Java массивы имеют фиксированную длину, и после того как массив создан, он не может расти или уменьшаться. ArrayList может менять свой размер во время исполнения программы, при этом не обязательно указывать размерность при создании объекта. Элементы ArrayList могут быть абсолютно любых типов в том числе и null.

Конструктор: ArrayList< Тип > имя = new ArrayList<Тип>();

LinkedList — реализует интерфейс List. Является представителем двунаправленного списка, где каждый элемент структуры содержит указатели на предыдущий и следующий элементы. Итератор поддерживает обход в обе стороны. Реализует методы получения, удаления и вставки в начало, середину и конец списка. Порядок элементов соответствует последовательности добавления.

Конструктор: LinkedList<Тип> имя = new LinkedList<Тип>();

ArrayList

Реализация интерфейса List в виде массива переменного размера. Реализует все опциональные операции списка; разрешает добавление любых элементов, в том числе null. (Этот класс, грубо говоря, эквивалентен классу Vector).

· LinkedList

Реализация интерфейса List в виде связного списка. Реализует все опциональные операции списка; разрешает добавление любых элементов, в том числе null. В дополнение к методам интерфейса List, класс LinkedList предоставляет однотипно названные методы для получения, удаления и вставки элемента в начало и конец списка. Эти методы позволяют использовать связные списки в качестве очередей, стеков и очередей с двусторонним доступом.

В ArrayList доступ к элементам быстрее, в отличие от LinkedList в котором операции вставки элементов быстрее. Обращаться к элементам ArrayList можно по индексу. Обращаться к элементам LinkedList можно только пройдя все предыдущие элементы. LinkedList выгодно использовать, если количество элементов постоянно меняется. ArrayList - когда нужно часто обращаться к элементам списка.

Вопрос 30. Параметры по которым сравнивают реализации коллекций.

Основные реализации коллекций.

HashSet — множество базирующееся на хэш-кодах элементов. Порядок элементов при обходе(итерации) не определен. Не допускает дубликатов.

· TreeSet — множество отсортированное в натуральном порядке. Не допускает дубликатов.

· LinkedHashSet — множество базирующееся на хэш-кодах элементов. Порядок элементов соответствует последовательности добавления в коллекцию.

· LinkedList — связанный список. Каждый элемент ссылается на 2 соседних. Порядок элементов соответствует последовательности добавления.

· ArrayList — индексированный список. Каждому элементу соответствует индекс типа int.

· HashMap — ассоциативный массив. В качестве уникальных ключей используется множество базирующееся на хэш-кодах. Порядок элементов не определен.

· LinkedHashMap — ассоциативный массив. В качестве уникальных ключей используется множество базирующееся на хэш-кодах. Порядок элементов соответствует последовательности добавления.

· TreeMap — ассоциативный массив. В качестве уникальных ключей используется отсортированное в натуральном порядке множество.

«±» означает, что функция для коллекции доступна, но ее использование требует большей бдительности, т.к. может повлечь большую трату ресурсов процессора.

Реализации коллекций отличаются способами хранения элементов данных и механизмами доступа к ним. В приведенной ниже таблице приводятся характеристики времени, требуемого на выполнение основных операций в различных реализациях коллекций (а именно, тип зависимости затрачиваемого на выполнение операции времени от размера коллекции):

По поводу реализаций Map:

Класс HashMap полностью реализует интерфейс Map, а также итератор типа iterator. Класс HashMap очень похож на класс Hashtabie и может использоваться в тех же ситуациях.

Класс ТгееМар полностью реализует интерфейс sortedMap. Он реализован как бинарное дерево поиска, значит его элементы хранятся в упорядоченном виде. Это значительно ускоряет поиск нужного элемента.

Порядок задается либо естественным следованием элементов, либо объектом, реализующим интерфейс сравнения Comparator.

 

Вопрос 31. Понятие и назначение итератора

 

В Java API введен интерфейс iterator, описывающий способ обхода всех элементов коллекции. В каждой коллекции есть метод iterator (), возвращающий реализацию интерфейса iterator для указанной коллекции. Получив эту реализацию, можно обходить коллекцию в некотором порядке, определенном данным итератором, с помощью методов, описанных в интерфейсе iteratorи реализованных в этом итераторе. Подобная техника использована в классе

StringTokenizer.

В интерфейсе iterator описаны всего три метода:

логический метод hasNext () возвращает true, если обход еще не завершен;

метод next о делает текущим следующий элемент коллекции и возвращает его в виде объекта класса object;

метод remove о удаляет текущий элемент коллекции.

Можно представить себе дело так, что итератор — это указатель на элемент коллекции. При создании итератора указатель устанавливается перед первым элементом, next() возвращает очередной элемент коллекции, к которой «привязан» итератор (и делает его текущим). Порядок перебора определяет сам итератор.

Метод remove (), пожалуй, излишен, он уже не относится к задаче обхода коллекции, но позволяет при просмотре коллекции удалять из нее ненужные элементы.

Порядок перебора может быть предопределенным, а может и нет.

 

Создание итератора

 

Iterator< Тип > имя_итератора = interf. iterator (); // Где интерфейс — только интерфейсы Set либо List

 

while (имя_итератора.hasNext()) // пройти по каждому элементу

System.out.println(имя_итератора.next()); // Печать каждого элемента

 

Элементы реализующего этот интерфейс коллекции также можно обойти с помощью итераторов.
Да, в этом интерфейсе нет метода iterator, но зато есть метод entrySet(). Этот метод вернёт нам Set, содержащий все пары ключ – значение для этой коллекции.
Выглядеть это все будет так:

 

 

// Для перебора элементов словаря:

for(Map.Entry< Тип >entry: словарь.entrySet()) // Для кажой пары, принодлежащей множеству пар.

{

System.out.print ("key = "+entry.getKey()+" value = "+entry.getValue());

}

Вопрос 32. Сравнение элементов коллекций. Естественное и неистественное сравнение.

Естественное сравнение используется по умолчанию в ряде методов

(например, в сортировке sort) и в конструкторах, т.е. без дополнительных указаний

на метод сравнения.

Естественное отношение порядка сравнивает числа по

положению на числовой оси, символы – по числовому значению кода, строки –

лексикографически. Программист может указать, что следует использовать другой

метод сравнения (Неистественное сравнение). Для этого он должен реализовать интерфейс Comparator.

 

Несколько методов сравнения элементов коллекций:

contains (Object o) - находится ли указанный объект в коллекции;

containsAll (Collection name) - содержатся ли указанные объекты в коллекции.

equals (Object o) - сравнение коллекции с указанным объектом;

addAll (Collection name) — объединение;

retainAll(Collection name) — пересечение;

removeAll(Collection name) — разность;

 

Вопрос 33. Comparable и Comparator

 

 

Интерфейс Comparable предназначен для определения так называемого естественного порядка (naturalordering). Этот интерфейс определен в пакете java.lang. Обратившись к документации мы увидим, что данный интерфейс содержит всего один метод.

publicintcompareTo(Object obj)

Его удобно использовать при сортировке упорядоченных списков или массивов объектов.

Данный метод сравнивает вызываемый объект с obj. В отличие от метода equals, который возвращает true или false, compareTo возвращает:

·0, если значения равны;

·Отрицательное значение, если вызываемый объект меньше параметра;

·Положительное значение, если вызываемый объект больше параметра.

Метод может выбросить исключение ClassCastException, если типы объектов не совместимы при сравнении.

Необходимо помнить, что аргумент метода compareTo имеет тип сравниваемого объекта класса.

Классы Byte, Short, Integer, Long, Double, Float, Character, String ужереализуютинтерфейсComparable.

 

Итак, интерфейс Comparable дает нам возможность задавать порядок на множестве объектов одного или нескольких классов. Однако и этого не всегда хватает. Бывают случаи, когда в одной программе требуется иметь несколько различных вариантов порядка на одном и том же множестве. Например, если у нас есть список сотрудников, то нам может потребоваться порядок по фамилиям и порядок по табельным номерам. В этом случае интерфейс Comparable нас не спасает — он позволяет задать только один порядок.

В описанном случае вместо интерфейса Comparable следует использовать интерфейс Comparator.

 

Обратимся к документации. Интерфейс Comparator имеет два метода.

 

publicint compare(Object o1, Object o2)

 

publicboolean equals(Object obj)

intcompare (Objectobji 1, object obj2) — возвращает отрицательное число, если objl в каком-то смысле меньше obj2; нуль, если они считаются равными; положительное число, если objl больше obj2. Для читателей, знакомых с теорией множеств, скажем, что этот метод сравнения обладает свойствами тождества, антисимметричности и транзитивности;

booleanequals (Objectobj) — сравнивает данный объект с объектом obj, возвращая true, если объекты совпадают в каком-либо смысле, заданном этим методом.

Для каждой коллекции можно реализовать эти два метода, задав конкретный способ сравнения элементов, и определить объект класса SortedMap вторым конструктором. Элементы коллекции будут автоматически отсортированы в заданном порядке.

 

Основным отличием интерфейса Comparator от Comparable является то, что вы можете создавать несколько видов независимых сортировок.

 

Вопрос 34. Сортировка со стандартным и нестандартным отношением порядка.

 

Для стандартной сортировки коллекций существует метод sort():

Collections.sort(сюда_кидаем_коллекцию)

Для массивов:

Arrays.sort(массив)

 

Временами сортировка массивов простых типов в Java заставляет нас потрудиться. Не говоря о сортировке массивов объектов. Теперь же мы можем сортировать и массивы простых типов и массивы объектов, написав относительно малый код, с помощью интерфейса Comparator.

Е сли вы хотите обеспечить способность сортировки ваших собственных классов, тогда вы должны реализовать(implement) Comparator и перезагрузить методcompare(Object obj1, Object obj2) самостоятельно. Затем в параметрах конструктора коллекции указать объект класса, который реализует класс Comparator (стр. 445. Java 2 или 6 лаб. раб.).

Вопрос 35. Вопрос 36. Вопрос 37. Вопрос 38 Поиск элемента в коллекции. Двоичный и прямой поиск. Способ идентификации ситуации «Элемент не найден».

Прямой поиск (Линейный):

 

 

Идея поиска: Разбить массив на на две части и отбросить ту, в которой искомого элемента нет.

Существует два варианта бинарного поиска: итерационный и рекурсивный.

Код рекурсивного поиска:

 

Код итерационного двоичного поиска:

Для поиска элемента в коллекции можно вопсользоваться методом binarySearch() имеет вид:

intbinarySearch(коллекция, элемент)

и возращает индекс первого вхождение элемента в коллекцию. Если при поиске возращается значение “-1”, то элемент не найден.

Вопрос 39. Графический интерфейс пользователя. Составные элементы фрейма.

Графический интерфейспользователя (GUI) – средство и способ взаимодействия пользователя и программы при помощи мышки и клавы.

В Java есть 2 основных пакета для создания графических интерфейсов (GraphicsUserInterface). Это AbstractWindowsToolkit (AWT) и Swing.

Чтобы какой-либо компонент появился на экране его надо сделать видимым и поместить в контейнер.

В контейнер Java помещаются требуемые элементы графического интерфейса. Контейнер можно создать с помощью элементов JFrame, JApplet, JDialog и др.

Структура окна графического приложения:

Контейнер Frame — это полноценное готовое окно со строкой заголовка, в которую помещены кнопки контекстного меню, сворачивания окна в ярлык и разворачивания во весь экран и кнопка закрытия приложения.

Фрейм должен иметь строку заголовка, полосы прокрутки, кнопки — свернуть, разврнуть, закрыть. Нобязательные компоненты: строка меню с выпадающими пунктами. Окно должно быть окружено рамкой, в пределах которой происходит раегирование на действия мышью.

Вопрос 40. Библиотеки Java, поддерживающие графический интерфейс.

AWT и SWING

В ранних версиях Java средства Swing отсутсвовали. Можно счиатать, что они стали попыткой преодолеть трудности, связанные с первой оконной подсистемы –AWT.

Одним из ограничений AWT была платформеннo-ориентированная поддержка визуальных компонентов. Таким образом внешний вид интерфейсных элементов определялся не средствами Java, а используемой платформой. Элементы, создаваемые средством AWT, назывались тяжеловесными.

Платформенно-ориентированная поддержка интерфейсных элементов стала источником ряда проблем. Из-за различия в ОС комоненты по-разному выгядели и даже по-разному вели себя на различных платформах. К тому же использование тяжеловесных компонентов пораждало ряд проблем. Например такие компоненты всегда имели прямоугольную форму и были непрозрачны.

Потребовалось не слишком много времени, чтобы осознать, что ограничения AWT слишком серьёзны и нужен новый подход. Т.о. в 1997 появился набор компонентов Swing. Все компоненты Swing, за небольшим исключением являются легковесными, а это означает, что они полнстью написаны на Java и не зависят от конкретной платформы. Легковесный компонент может иметь форму, отличную от прямоугольной и быть прозрачным.

Общее количество компонентов библиотеки Swing почти вдвое превышает количество компонентов, входящих в библиотеку AWT, и эти компоненты обладают большими функциональными возможностями.

использование Swing - почти всегда предпочтительнее, за исключением тех случаев, когда нужна обратная совместимость с Java 1.

 

Вопрос 41. Компонент и контейнер.

Основное понятие графического интерфейса пользователя (ГИП) — компонент (component) графической системы. В русском языке это слово подразумевает просто составную часть, элемент чего-нибудь, но в графическом интерфейсе это понятие гораздо конкретнее. Оно означает отдельный, полностью определенный элемент, который можно использовать в графическом интерфейсе независимо от других элементов. Например, это поле ввода, кнопка, строка меню, полоса прокрутки, радиокнопка. Само окно приложения — тоже его компонент. Компоненты могут быть и невидимыми, например, панель, объединяющая компоненты, тоже является компонентом.

 

Любой компонент, требующий показа на экране, должен быть добавлен в класс-контейнер. Контейнеры служат хранилищем для визульных компонентов интерфейса и других контейнеров. Простейший пример контейнера - класс Frame, объекты которого отображаются на экране как стандартные окна с рамкой.

Чтобы показать компонент пользовательского интерфейса в окне, требуется создать объект-контейнер, например окно класса Frame, создать требуемый компонент и добавить его в контейнер, а уже затем отобразить его на экране. Несмотря на столь длинный список действий, в исходном тексте этот процесс занимает всего несколько строк:

// Создается текстовый объект

с надписью "Строка"

Label text = new Label("Строка");

// Объект добавляется в некий контейнер

SomeContainer.add (text);

// Отображается контейнер

SomeContainer.Show();