Учебно-методические материалы для студентов кафедры АСОИУ

Коллекции в java

Цель работы

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

Указания к работе

Выбор определенного класса для работы с коллекциями определяет набор методов, которые будут доступны для объекта этого класса. Например, если используется список (который определяет интерфейс List), то существуют богатый выбор для его реализации: ArrayList, LinkedList, Vector, Stack. Конкретный выбор реализации списка сказывается на эффективности манипуляций с объектами списка. Так, ArrayList хранит элементы в виде массива, а значит, доступ и замена будет выполняться относительно быстро. В то же время LinkedList хранит элементы в виде связного списка, что влечет за собой относительно медленный поиск элементов и быструю операцию добавления/удаления. Рекомендуется ознакомиться с описаниями следующих коллекций по JSDK -документации:

– java.util.Collection ;
– java.util.ArrayList;
– java.util.HashMap;
– java.util.HashSet.

Важно также знание основных классов для работы с коллекциями. Особое внимание при изучении коллекций заслуживают классы Comporator, Collections, Iterator.

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

Интерфейс Collection

Интерфейс Collection содержит набор общих методов, которые используются в большинстве коллекций. Рассмотрим основные из них:

Интерфейс List

Интерфейс List описывает упорядоченный список. Элементы списка пронумерованы, начиная с нуля и к конкретному элементу можно обратиться по целочисленному индексу. Интерфейс List является наследником интерфейса Collection, поэтому содержит все его методы и добавляет к ним несколько своих:

Интерфейс Set

Интерфейс Set описывает множество. Элементы множества не упорядочены, множество не может содержать двух одинаковых элементов. Интерфейс Set унаследован от интерфейса Collection, но никаких новых методов не добавляет. Изменяется только смысл метода add(Object item) – он не добавляет объект item, если он уже присутствует во множестве.

Интерфейс Queue

Интерфейс Queue описывает очередь. Элементы могут добавляться в очередь только с одного конца, а извлекаться с другого (аналогично очереди в магазине). Интерфейс Queue так же унаследован от интерфейса Collection. Специфические для очереди методы:

Методы интерфейса Queue:

Класс Vector

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

Класс Vector реализует интерфейс List, основные методы которого названы выше. К этим методам добавляется еще несколько. Например, метод firstElement() позволяет обратиться к первому элементу вектора, метод lastElement() – к его последнему элементу. Метод removeElementAt(int pos) удаляет элемент в заданной позиции, а метод removeRange(int begin, int end) удаляет несколько подряд идущих элементов. Все эти операции можно было бы осуществить комбинацией базовых методов интерфейса List, так что функциональность принципиально не меняется.

Класс ArrayList

Класс ArrayList – аналог класса Vector. Он представляет собой список и может использоваться в тех же ситуациях. Основное отличие в том, что он не синхронизирован и одновременная работа нескольких параллельных процессов с объектом этого класса не рекомендуется. В обычных же ситуациях он работает быстрее.

Класс Stack

Stack – коллекция, объединяющая элементы в стек. Стек работает по принципу LIFO (последним пришел – первым ушел). Элементы кладутся в стек «друг на друга», причем взять можно только «верхний» элемент, т.е. тот, который был положен в стек последним. Для стека характерны операции, реализованные в следующих методах класса Stack:

Класс Stack является наследником класса Vector, поэтому имеет все его методы (и, разумеется, реализует интерфейс List). Однако если в программе нужно моделировать именно стек, рекомендуется использовать только пять вышеперечисленных методов.

Интерфейс Iterator

Преимущество использования массивов и коллекций заключается не только в том, что можно поместить в них произвольное количество объектов и извлекать их при необходимости, но и в том, что все эти объекты можно комплексно обрабатывать. Например, вывести на экран все шашки, содержащиеся в списке checkers. В случае массива мы пользуемся циклом:

for (int i = 1; i < array.length; i++){
// обрабатываем элемент array[i]
}

Имея дело со списком, мы можем поступить аналогичным образом, только вместо array[i] писать array.get(i). Но мы не можем поступить так с коллекциями, элементы которых не индексируются (например, очередью или множеством). А в случае индексированной коллекции надо хорошо знать особенности ее работы: как определить количество элементов, как обратиться к элементу по индексу, может ли коллекция быть разреженной (т.е. могут ли существовать индексы, с которыми не связано никаких элементов) и т.д.

Для навигации по коллекциям в Java предусмотрено специальное архитектурное решение, получившее свою реализацию в интерфейсе Iterator. Идея заключается в том, что к коллекции «привязывается» объект, единственное назначение которого — выдать все элементы этой коллекции в некотором порядке, не раскрывая ее внутреннюю структуру.

Интерфейс Iterator имеет всего три метода:

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

Iterator iter = coll.iterator(); // coll - коллекция
while (iter.hasNext()) {
// обрабатываем объект, возвращаемый методом iter.next()
}

Для коллекций, элементы которых проиндексированы, определен более функциональный итератор, позволяющий двигаться как в прямом, так и в обратном направлении, а также добавлять в коллекцию элементы. Такой итератор имеет интрефейс ListIterator, унаследованный от интерфейса Iterator и дополняющий его следующими методами:

В интерфейсе List определен метод listIterator(), возвращающий итератор ListIterator для обхода данного списка.

Интерфейс Map

Интерфейс Map из пакета java.util описывает коллекцию, состоящую из пар «ключ – значение», которые широко используются для хранения настроек в файлах конфигурации (см., например, /etc/services). У каждого ключа только одно значение, что соответствует математическому понятию однозначной функции или отображения (Mар). Интерфейс Map содержит следующие методы, работающие с ключами и значениями:

В интерфейс Mар вложен интерфейс Map.Entry, содержащий методы работы с отдельной парой.

Вложенный интерфейс Map.Entry

Этот интерфейс описывает методы работы с парами, полученными методом entrySet() из объекта типа Map.

Методы getKey() и getValue() позволяют получить ключ и значение пары, метод setValue (Оbject value) меняет значение в данной паре.

Дополнительную информацию по использованию перечисленных классов можно получить по следующим ссылкам:

Пример программы

Задание: Вычислить сколько раз каждая буква встречается в тексте.

Решение:

import java.util.HashMap;
import java.util.*;
public class Main {
public static void main(String[] args) {
String txt = " лабораторная работа " ;
HashMap<Character, Integer> map = new HashMap<Character, Integer>(40);
for (int i = 0; i < txt.length(); ++i) {
char c = txt.charAt(i);
//проверяем является ли символ буквой
if (Character.isLetter(c)) {
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
}
//вывод на экран букв с частотой их появления
for (Entry<Character, Integer> entry : map.entrySet()) {
System.out.println("буква: "+entry.getKey()+" кол - во: "+entry.getValue());
}
}
}

Задания к лабораторной работе

  1. Ввести строки из файла, записать их в стек. Вывести строки в файл в обратном порядке.
  2. Ввести число, занести его цифры в стек. Вывести в число, у которого цифры идут в обратном порядке.
  3. Сложить два многочлена заданной степени, если коэффициенты многочленов хранятся в объекте HashMap.
  4. Создать стек из элементов каталога.
  5. Не используя вспомогательных объектов, переставить отрицательные элементы данного списка в конец, а положительные - в начало этого списка.
  6. Организовать вычисления в виде стека.
  7. Выполнить попарное суммирование произвольного конечного ряда чисел следующим образом: на первом этапе суммируются попарно рядом стоящие числа, на втором этапе суммируются результаты первого этапа и т.д. до тех пор, пока не останется одно число.
  8. Задать два стека, поменять информацию местами.
  9. Определить класс Stack. Объявить объект класса. Ввести последовательность символов и вывести ее в обратном порядке.
  10. Умножить два многочлена заданной степени, если коэффициенты многочленов хранятся в списках.
  11. Определить класс Set на основе множества целых чисел, n = размер. Создать методы для определения пересечения и объединения множеств.
  12. Программа получает N параметров вызова (аргументы командной строки). Эти параметры – элементы вектора. Строится массив типа double, а на базе этого массива – объект класса DoubleVector. Далее программа выводит в консоль значения элементов вектора в виде: Вектор: 2.3 5.0 7.3.
  13. Списки (стеки) I(1..N) и U(1..N) содержат результаты N измерений тока и напряжения на неизвестном сопротивлении R. Найти приближённое число R методом наименьших квадратов.

CC-BY-CA Юдин Е.Б., 28.01.2013