Глава_06

Задача. Данный пример иллюстрирует применение на практике изученных алгоритмов.

Решение. Мы попробуем смоделировать проблему, которую можно было бы решить используя рассмотренные методы. Остановимся на следующем сценарии. Из файла поочередно считываются слова и формируется массив, содержащий слова только в единственном экземпляре, после чего элементы массива сортируются и выводятся.

Алгоритм. На рис 6.15 представлена та часть программы, которая отвечает за создание массива уникальных слов. После этого массив выводится, сортируется и выводится еще раз.

Программа. С помощью метода selectionSort осуществляется сортировка строк. Как отмечалось в разделе 3.6 оператор < нельзя применять для сравнения объектов ( в частности наших объектов String). Поэтому мы воспользуемся методом compareTo или compareToIgnoreCase. Тот же метод будет использован в процессе поиска. Далее следует текст программы.

Тестирование. Разработана программа, которая для открытия файла использует класс Filer, благодаря чему возможна работа с любыми данными. Применяется метод сортировки selectionSort. Чтобы упростить процедуру считывания и максимально увеличить количество слов, которые могут повторяться, мы реорганизовали файл и ввели пробелы между всеми словами и символами.

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

Объявим массив, в который будем складывать слова, считанные из файла:

String group [] = new String[100];

Затем откроем файл при помощи метода open класса Filer, которому передадим в параметр имя файла.

System.out.print("Where are the words? "); Stream fin = Filer.open("sort.java");

Затем в цикле while будем пословно считывать из fin, и складывать в массив group считанные слова при помощи функции search. Функция search не только складывает переданное ей слово в массив group, но и проверяет, не содержится ли оно уже массиве. Если не содержится, то складывает его в массив, если уже содержится, то условие if не выполняется и программа переходит к считыванию следующего слова. По достижении конца файла, выводится сообщение о том, сколько слов считано из файла в массив group. При этом, повторяю слова в массиве group будут уникальны.

int count=0; try {


          while (count < 100) 
{

            String word = fin.readString();

            if (! search(group,count,word)) 
{

              group[count] = word;

              count ++;

            }
          }

} catch (EOFException e) 
{

          System.out.println(count + " words read.\n\n");
        }

Далее происходит вывод на экран слов из массива group при помощи функци report(). В параметр этой функции передается массив и число элементов, которые необходимо считать:

System.out.print("Original\n"); System.out.print("========\n"); report(group,count);

Затем функция сортировки:

selectionSort(group, count);

И снова вывод:

System.out.print("\n\nSorted\n"); System.out.print("======\n"); report(group,count);

Теперь рассмотрим подробнее функции, которые использованы в этой программе:

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

String temp;
int chosen;

for (int leftmost = 0; leftmost < n-1; leftmost++) {

chosen = leftmost;
for (int j = leftmost+1; j < n; j++)

if (a[j].compareTo(a[chosen]) < 0)

chosen = j;

temp = a[chosen];
a[chosen] = a[leftmost];
a[leftmost] = temp;

}

Функции search() передается массив, число элементов массива, и слово, которое необходимо проверить. Если оно в массиве не встретилось, то возвращается true, если встретилось, то false.

for (int i = 0; i < n; i++)
if (x.compareTo(a[i])==0) return true;
return false;

Функция report() выводит на экран переданный ей массив слов. При этом обратите внимание как интересно в функции report() при выводе сделана табуляция: