Студопедия — Итераторы. В коллекциях широко используются итераторы
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Итераторы. В коллекциях широко используются итераторы

 

Итераторы

 

В коллекциях широко используются итераторы. В Java итератор – это вспомогательный объект, используемый для прохода по коллекции объектов. Как и сами коллекции, итераторы базируются на интерфейсе. Это интерфейс java.util.Iterator. Т.е. любой итератор, как бы он не был устроен, имеет следующие три метода:

 

boolean hasNext() – проверяет есть ли еще элементы в коллекции

Object next() – выдает очередной элемент коллекции

void remove() – удаляет последний выбранный элемент из коллекции.

 

Интерфейс Collection имеет метод Iterator iterator(). Это обязывает все классы коллекций создавать поддержку итераторов (обычно реализованы с использованием inner-классов, удовлетворяющих интерфейсу Iterator).

 

Пример программы, демонстрирущей работу со списками и множествами:

 

package kture.kn092.novikov.lab1;

 

import java.util.ArrayList;

import java.util.Collection;

import java.util.HashSet;

import java.util.Iterator;

import java.util.List;

import java.util.Set;

 

public class Lab1Main {

 

public static void main(String[] args) {

List list = new ArrayList(); // Создает новый список

fillCollection(list);

System.out.println("The List:");

printCollection(list);

 

System.out.println();

 

Set set = new HashSet(); // Создает новое множество

fillCollection(set);

System.out.println("The Set:");

printCollection(set);

}

 

/**

* Наполняет коллекцию элементами типа String

* @param col - Collection

* */

private static void fillCollection(Collection col){

col.add("First");

col.add("First");

col.add("First");

col.add("Second");

col.add("Second");

col.add("Third");

col.add("Fourth");

col.add("Fifth");

}

 

/**

* Распечатывает коллекцию в стандартный поток вывода. Каждый элемент с новой строки.

* @param col - Collection

* */

private static void printCollection(Collection col){

for (Iterator iter = col.iterator(); iter.hasNext();) {

Object element = iter.next();

System.out.println(element);

}

}

}

 

Результат выполнения программы:

 

The List:

First

First

First

Second

Second

Third

Fourth

Fifth

 

The Set:

Fourth

Fifth

Third

Second

First

 

Как видим, в список List добавились все элементы в той последовательности, в которой мы их добавляли. Если же мы используем Set, в него добавляются только неповторяющиеся элементы. Причем их последовательность не обязательно совпадает с последовательностью добавления элементов.

В JDK интерфейс Map имеет три основные реализации: HashMap, LinkedHashMap и TreeMap.

HashMap дает неупорядоченное множество ключей. Для прохода по всем занесенным в HashMap объектам мы можем при помощи метода values() получить список объектов и пройти по нему, например, используя итератор. Но последовательность объектов в этом случае будет произвольной. Для получения упорядоченного множества значений следует применять TreeMap.

Класс TreeMap отличается от HashMap тем, что его элементы упорядочены по ключу. В дополнение к обычным конструкторам имеет конструктор public TreeMap(Comparator c).Если же применяется конструктор по умолчанию, то объекты-ключи должны удовлетворять интерфейсу Comparable.В связи с упорядоченностью по ключу, TreeMap имеет дополнительные методы, основанные на наличии порядка. Это методы firstKey(), lastKey(), и др.

Сортировка элементов коллекций подробно описана в п. 3.2.8.

 

Пример программы с использованием HashMap(HashMap дает неупорядоченное множество ключей.):

 

Map map = new HashMap();

 

// Заполнить его чем-нибудь

map.put("one", "111");

map.put("two", "222");

map.put("three", "333");

map.put("four", "333");

 

// Вывести словарь

System.out.println(map);

 

// Получить и вывести все ключи

Set keyset = map.keySet();

System.out.println("Set of keys: " + keyset);

 

// Получить и вывести значение по ключу

String val = (String)map.get("one");

System.out.println("one=" + val);

 

// Получить и вывести все значения

Collection valcol = map.values();

System.out.println("Collection of values: " + valcol);

 

// Получить и вывести все пары

Set entryset = map.entrySet();

System.out.println("Set of entries: " + entryset);

 

В результате выполнения программы на экран будет выведено:

 

{three=333, two=222, four=333, one=111}

Set of keys: [three, two, four, one]

Collection of values: [333, 222, 333, 111]

 

one=111

 

Set of entries: [three=333, two=222, four=333, one=111]

 

3.2.3 Списки

 

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

 

В классе LinkedList имеется ряд методов, которые не входят в интерфейс List:

addFirst() и addLast() - добавить в начало и в конец списка

removeFirst() и removeLast() - удалить первый и последний элементы

getFirst() и getLast() - получить первый и последний элементы

 

Эти методы позволяют использовать объекты LinkedList в качестве стека, очереди и дека (двусторонней очереди).

Для доступа к элементам списка можно использовать итератор, как было показано в предыдущем примере, либо индекс элемента:

 

List col = new ArrayList(10);

//Заполнить коллекцию объектами Integer

for (int i = 0; i < 10; i++){

col.add(new Integer(i));

}

//Распечатать коллекцию с испольованием итератора

for (Iterator iter = col.iterator(); iter.hasNext();){

Integer i = (Integer)iter.next();

System.out.println(i);

}

 

Основными классами, которые реализуют интерфейс Set являются HashSet, LinkedHashSet и TreeSet. HashSet построен на основе HashMap, т.е. внутри данного класса инкапсулируется объект HashMap, в котором значения соответствуют автоматически генерируемым хэш-кодам. За счет этого не допускается добавление в него повторяющихся элементов – перед добавлением происходит проверка на существование такого элемента во множестве. Однако данные хранятся в HashSet в произвольном порядке, который может не соответствовать порядку их добавления. Если необходимо соблюдать ту же последовательность объектов во множестве, с которой они были в него добавлены, необходимо использовать LinkedHashSet. Это проиллюстрировано в следующем примере:

 

package kture.kn092.novikov.lab1;

 

import java.util.Set;

import java.util.HashSet;

import java.util.LinkedHashSet;

import java.util.Iterator;

 

public class SetExample {

 

public static void main(String[] args) {

SetExample se = new SetExample();

System.out.println("HashSet:");

HashSet hs = new HashSet();

se.fillSet(hs);

se.printSet(hs);

 

System.out.println("LinkedHashSet:");

LinkedHashSet lhs = new LinkedHashSet();

se.fillSet(lhs);

se.printSet(lhs);

}

 

private void fillSet(Set s) {

s.add("one");

s.add("two");

s.add("three");

s.add("four");

s.add("five");

}

 

private void printSet(Set s) {

Iterator i = s.iterator();

while (i.hasNext())

System.out.println(i.next());

}

}

 

Класс TreeSet отличается от HashSet тем, что он основан не на HashMap, а на TreeMap.

 

3.2.4 Упорядочивание элементов коллекций

 

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

В Java эта задача решаетя стандартными средствами библиотеки языка, а именно — путем задания интерфейсов, используемых при задании порядка. При этом, Java позволяет сравнивать объекты как одного, так и разных классов.

Для задания порядка используются следующие интерфейсы: java.lang.Comparable и java.util.Comparator. Они дают два различных способа задания порядка.

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

public int compareTo(Object o) - сравнивает объект с другим объектом.

Таким образом, чтобы создать упорядоченное множество объектов, реализующих интерфейс Comparable, нам достаточно просто пометстить их в SortedSet.

Например, класс String реализует интерфейс Comparable (строки сортируются по алфавиту, причем сначала идут все строки, начинающиеся с больших букв, а затем - с маленьких). Поэтому их можно помещать в SortedSet. Например, в результате выполения кода

public static void main(String[] args) {

Set set = new TreeSet();

set.add("Betha");

set.add("gamma");

set.add("alfa");

set.add("betha");

set.add("Gamma");

set.add("Alfa");

System.out.println(set);

}

Вы получите:

[Alfa, Betha, Gamma, alfa, betha, gamma]

 

Рассмотрим пример создания собственного класса, реализующего интерфейс Comparable.

 

import java.util.Set;

import java.util.TreeSet;

 

public class EmployeesProcessor {

 

public static void main(String[] args) {

Set emps = new TreeSet();

emps.add(new Employee("Vasya", 500));

emps.add(new Employee("Petya", 300));

emps.add(new Employee("Sanya", 1000));

emps.add(new Employee("Alex", 100));

System.out.println(emps);

}

}

 

class Employee implements Comparable{

 

private String name;

private int salary;

 

public Employee(String name, int salary){

this.name = name;

this.salary = salary;

}

 

public int compareTo(Object obj){

int otherSalary = ((Employee)obj).getSalary();

if (salary == otherSalary){

return 0;

}

else{

return (salary > otherSalary)? 1: -1;

}

}

 

public String toString(){

return name + ": " + salary;

}

 

public String getName() {

return name;

}

 

public int getSalary() {

return salary;

}

 

}

Здесь в сортируемое множество помещаются объекты класса Employee (сотрудник), для которого определен метод compareTo, задающий правило сравнения по возрастанию зарплаты. В результате выполнения программы получаем:

[Alex: 100, Petya: 300, Vasya: 500, Sanya: 1000]

 

Недостатком такого механизма (реализация интерфейса Comparable) является то, что в этом случае невозможно задавать несколько правил сортировки. Например, если в одном случае вам нужно сортировать строки с учетом регистра, а в другом - без, то переопределив метод compareTo() для сортровки с учетом регистра, вы не можете сделать это же для сортировки без учета регистра. И тут на помощь приходит интерфейс Comparator. В этом случае создается отдельный вспомогательный класс, реализующий этот интерфейс, и уже на основании этого объекта будет производиться сортировка. В этом классе нужно реализовать метод compare(Object o1, Object o2), возвращающий целое значение (правила работы такие же, как и у compareTo(Object o). Теперь объект этого класса можно передать в конструктор TreeSet, и он будет сортировать объекты не на основании метода compareTo(), а на основании результатов выполенения метода compare() компаратора.

Изменим нашу Программу таким образом, чтобы сотрудники печатались в порядке возрастания имен:

 

 

import java.util.Comparator;

import java.util.Set;

import java.util.TreeSet;

 

public class EmployeesProcessor {

 

public static void main(String[] args) {

Set emps = new TreeSet(Employee.EMPLOYEE_NAME_COMPARATOR);

emps.add(new Employee("Vasya", 500));

emps.add(new Employee("Petya", 300));

emps.add(new Employee("Sanya", 1000));

emps.add(new Employee("Alex", 100));

System.out.println(emps);

}

}

 

class Employee implements Comparable{

 

public static final Comparator EMPLOYEE_NAME_COMPARATOR = new Comparator(){

public int compare(Object o1, Object o2){

Employee e1 = (Employee)o1;

Employee e2 = (Employee)o2;

return e1.getName().compareTo(e2.getName());

}

};

 

private String name;

private int salary;

 

public Employee(String name, int salary){

this.name = name;

this.salary = salary;

}

 

public int compareTo(Object obj){

int otherSalary = ((Employee)obj).getSalary();

if (salary == otherSalary){

return 0;

}

else{

return (salary > otherSalary)? 1: -1;

}

}

 

public String toString(){

return name + ": " + salary;

}

 

public String getName() {

return name;

}

 

public int getSalary() {

return salary;

}

 

}

В итоге программа распечатает:

[Alex: 100, Petya: 300, Sanya: 1000, Vasya: 500]

 

3.2.5 Сортировка и поиск с использованием Arrays и Collections

 

Класс Arrays обеспечивает сортировку и поиск в массивах, а класс Collections — в коллекциях. Если посмотреть документацию, то можно увидеть, что оба эти класса не имеют public-конструктора, и все их методы статические. В таких классах мы пользуемся их статическими методами без порождения объекта класса.

Класс Arrays Имеет множество методов sort(...) для массивов всех примитивных типов, и такое же множество методов binarySearch(...). Методы sort(...) позволяют сортировать массивы, а методы binarySearch(...) — производить эффективный бинарный поиск в отсортированном массиве.
Алгоритм бинарного поиска состоит в разбиении массива на две примерно равные части. Средний элемент массива сравнивается с ключом, что позволяет выяснить, в какой из частей расположен искомый элемент. После этого процедура повторяется для выбранной части массива. И так далее, пока не будет найден искомый элемент массива.

Кроме методов sort(...) для массивов примитивных типов есть 4 метода sort(...) для массивов объектов:

public static void sort(Object[] a)

public static void sort(Object[] a, int fromIndex, int toIndex)

public static void sort(Object[] a, Comparator c)

public static void sort(Object[] a, int fromIndex, int toIndex, Comparator c)

 

Первые два метода подразумевают, что класс(ы) объектов массива удовлетворяет(ют) интерфейсу Comparable. Вторые два метода требуют передачи в качестве последнего параметра объекта-компаратора, который удовлетворяет интерфейсу Comparator и обеспечивает сравнение объектов массива.

 

Пример

Пусть у нас есть массив строк sAry, т.е.

String[] sAry;

тогда

Arrays.sort(sAry);

отсортирует этот массив.

Аналогично методам sort(...) есть два метода binarySearch(...)для массивов объектов:

public static int binarySearch(Object[] a, Object key)

public static int binarySearch(Object[] a, Object key, Comparator c)

 

Первый из них подразумевает, что объекты массива удовлетворяют интерфейсу Comparable, во втором для сравнения объектов массива используется компаратор. Компаратор должен быть тем же, который был использован при сортировке массива.

Что является результатом binarySearch(...)? Этот метод возвращает индекс найденного элемента массива, если элемент был найден. Если же элемент не найден, то binarySearch(...) возвращает величину (-i-1), где i — это индекс элемента, после которого нужно вставить искомый элемент для того, чтобы сохранился порядок сортировки.

Пример

int ind = Arrays.binarySearch(sAry, "Иванов");

if (ind < 0){

System.out.println("Иванов отсутствует");

}

 

Класс Collections

Предназначен для работы с коллекциями, а не массивами. Как и класс Arrays имеет ряд методов для сортировки и двоичного поиска.

public static void sort(List list)

public static void sort(List list, Comparator c)

public static int binarySearch(List list, Object key)

public static int binarySearch(List list, Object key, Comparator c)

 

Эти методы аналогичны одноименным методам класса Arrays, только в качестве первого параметра принимают List (список).

 

3.3 Описание лабораторной установки

 

Лабораторная работа выполняется в диалоговом режиме с использованием ПК. Оперативный обмен информацией с ПК осуществляется с помощью дисплея и пакета прикладных программ. Количество применяемых технических средств обеспечивает индивидуальный режим выполнения лабораторной работы.

 

3.4 Порядок выполнения и методические указания по выполнению работы

 

1. Реализуйте при помощи коллекций функциональность, соответствующую выданному варианту задания.

2. Оформите отчет по лабораторной работе

 

 

3.5 Содержание отчета

 

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

- цель работы;

- текст программы;

- результаты работы программы;

- выводы о приобретенных знаниях и умениях.

 

3.6 Контрольные вопросы

 

1. Назовите основные свойства коллекций.

2. Назовите разновидности коллекций.

3. Для чего используются итераторы?

 

 

ЗАДАНИЯ

 

Вариант 1

  • Создать класс Point (должен иметь два поля - координаты x и y). Разместить объекты этого класса во множестве в порядке удаленности от начала координат и вывести на экран. Затем отсортировать объекты в порядке убывания значения координаты x и вывести на экран. Использовать интерфейсы Comparable и Comparator.
Вариант 2

  • Создать множество одномерных целых массивов, упорядоченных по количеству элементов в них. Меньшим считается тот массив, в котором элементов меньше
Вариант 3

  • Создать класс, который в конструкторе принимал бы предложение (одну строку - набор слов, разделенных пробелами) и предоставлял методы для получения количества слов в предложении, а также словаря использованных слов в алфавитном порядке без учета регистра.
Вариант 4

  • Создать класс, строящий частотный словарь текста. В таком словаре каждому трехбуквенному сочетанию должно приписывается количество его вхождений в текст. Сочетания букв, которых в тексте нет, в словарь попадать не должны. Сочетания в словаре не должны содержать пробелы и знаки препинания. Текст для анализа должен передаваться в конструкторе. Реализовать метод, который в качестве параметра принимал бы трехбуквенное сочетание и возвращал количество его входжений.
Вариант 5

  • Разработать контейнерный класс «Телефонный справочник», который бы содержал произвольное количество абонентов. Каждый абонент имеет фамилию и один номер телефона. Фамилии разных абонентов могут быть одинаковыми, номера телефонов – нет. Справочник должен выполнять поиск номеров телефонов по фамилии и поиск фамилии по номеру телефона.
Вариант 6

  • Разработать абстрактный класс Person и объявить в нем абстрактный метод getName(). Создать два наследника этого класса - Student и Teacher, в которых реализовать этот метод. Создать класс-контейнер, который представлял бы собой список объектов класса Person (объекты других классов в него добавлять нельзя). Объекты в контейнере должны храниться в алфавитном порядке имен. Реализовать в контейнере метод, распечатывающий имена всех студентов и преподавателей на консоль (каждого с новой строки).
Вариант 7

  • Реализовать класс-стек, реализующий методы добавления элементов, извлечения и очистки.
Вариант 8

  • Реализовать класс-очередь, реализующий методы добавления элементов, извлечения и очистки.
Вариант 9

  • Создать класс-хранилище спортсменов. В него должно быть возможно добавлять только объекты спортсменов, для которых задается номер и имя (номера не обязательно должны следовать по порядку). Хранилище должно позволять осуществлять поиск объектов по номеру и по фамилии.
Вариант 10

  • Создать класс-автомобиль с атрибутами: марка, номер, цвет. Создать класс-хранилище для этих машин, в котором реализовать методы добавления машин, а также извлечения списка всех машин по заданной марке.
Вариант 10

  • Создать класс-автомобиль с атрибутами: марка, номер, цвет. Создать класс-хранилище для этих машин, в котором реализовать методы добавления машин, а также извлечения списка всех машин по заданной марке.
Вариант 11

  • Создать класс-контейнер, в который можно было бы помещать только объекты класса Building (класс создать самостоятельно, одним из полей должно быть количество этажей). В контейнере здания должны храниться в порядке возрастания количества этажей (должен быть метод, который возвращает коллекцию зданий в отсортированном виде).
Вариант* 12

  • Создать класс, реализующий основные методы и функциональность класса HashSet (реализовать интерфейс Set). Продемонстрировать его свойства множества (невозможность добавления одинаковых объектов, и т.д.).
Вариант 13

  • Создать класс-контейнер, в который можно было бы помещать строки различной длины. Строки должны храниться в порядке убывания их длин (должен быть метод, который возвращает коллекцию содержащихся строк в заданном порядке).
Вариант 14

  • Создать класс-контейнер, в который можно было бы помещать только объекты класса Book (класс создать самостоятельно, одним из полей должно быть количество страниц). В контейнере книги должны храниться в порядке убывания количества страниц (должен быть метод, который возвращает коллекцию книг в отсортированном виде).
Вариант 15

  • Создать класс-контейнер, в который можно было бы помещать только объекты класса Student (класс создать самостоятельно, он должен иметь поля имя (уникальное) и группа). Реализовать методы для получения одного студента по имени и коллекции студентов по группе.
Вариант 16

  • Создать класс-контейнер, в который можно помещать только объекты класса Telefon (класс создать самостоятельно, должен иметь поля фирма и модель). Реализовать методы для получения всех телефонов по заданной фирме и по заданной модели.
Вариант* 17

  • Создать класс, обладающий функциональностью класса LinkedList и реализующий его основные методы (желательно реализовывать интерфейс List). Объекты в нем должны храниться в связном списке.
Вариант** 18

  • Создать класс, обладающий функциональностью класса ArrayList и реализующий его основные методы (желательно реализовывать интерфейс List). Объекты в нем должны храниться в массиве.
 




<== предыдущая лекция | следующая лекция ==>
Итераторы | 

Дата добавления: 2015-10-19; просмотров: 513. Нарушение авторских прав; Мы поможем в написании вашей работы!



Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

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

Правила наложения мягкой бинтовой повязки 1. Во время наложения повязки больному (раненому) следует придать удобное положение: он должен удобно сидеть или лежать...

ТЕХНИКА ПОСЕВА, МЕТОДЫ ВЫДЕЛЕНИЯ ЧИСТЫХ КУЛЬТУР И КУЛЬТУРАЛЬНЫЕ СВОЙСТВА МИКРООРГАНИЗМОВ. ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА БАКТЕРИЙ Цель занятия. Освоить технику посева микроорганизмов на плотные и жидкие питательные среды и методы выделения чис­тых бактериальных культур. Ознакомить студентов с основными культуральными характеристиками микроорганизмов и методами определения...

САНИТАРНО-МИКРОБИОЛОГИЧЕСКОЕ ИССЛЕДОВАНИЕ ВОДЫ, ВОЗДУХА И ПОЧВЫ Цель занятия.Ознакомить студентов с основными методами и показателями...

Основные структурные физиотерапевтические подразделения Физиотерапевтическое подразделение является одним из структурных подразделений лечебно-профилактического учреждения, которое предназначено для оказания физиотерапевтической помощи...

Почему важны муниципальные выборы? Туристическая фирма оставляет за собой право, в случае причин непреодолимого характера, вносить некоторые изменения в программу тура без уменьшения общего объема и качества услуг, в том числе предоставлять замену отеля на равнозначный...

Тема 2: Анатомо-топографическое строение полостей зубов верхней и нижней челюстей. Полость зуба — это сложная система разветвлений, имеющая разнообразную конфигурацию...

Studopedia.info - Студопедия - 2014-2024 год . (0.013 сек.) русская версия | украинская версия