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

Описанные в настоящей главе основные алгоритмы работы с двунаправленными списками представлены в виде блок-схем в следующей главе «2 Разработка алгоритмов программного средства».

2. Разработка алгоритмов программного средства

В современной практике высшего образования в РФ, к сожалению, принято требовать от студентов составления блок-схем, которые должны отвечать требованиям ГОСТ 19.701-90 (ИСО 5807-85). Полезность блок-схем подвергается сомнению со стороны большинства людей из академических кругов и известных специалистов-практиков. Например, известна цитата Фредерик П. Брукс-мл., приводимая в его труде "Мифический человеко-месяц":

Покажите мне ваши блок-схемы, спрятав таблицы данных, - и я по-прежнему буду теряться в догадках. Покажите таблицы - и блок-схемы, как правило, не понадобятся, поскольку будут очевидны [1].

Под таблицами данных понимаются структуры данных.

Имеет место порочный круг: для простейших алгоритмов блок-схемы не нужны, для сложных алгоритмов они слишком примитивны и громоздки. Универсально лучшим механизмом описания как простейших алгоритмов, так и сложных является словесное описание с приведением псевдо-кода и, в случае необходимости, рисунками в свободной форме.

К слову, создаваемая в рамках настоящей работы программа для ведения списка студентов очевидным образом полностью описывается своим графическим интерфейсом, т. о. укрупненная блок-схема, по сути, не нужна, а алгоритмы отдельных действий с двусвязным списком вроде добавления вообще умещаются в несколько строчек словесного описания, которое приведено в главе «1 Анализ структуры данных связный список и алгоритмов его обработки» настоящей работы.

Для блок-схем используем стандартные элементы согласно требованиям ГОСТ 19.701-90 (ИСО 5807-85).

Укрупненная блок-схема приведена на рисунке 4 на следующей странице. Словесное описание каждого из основных алгоритмов уже приведено в главе «1 Анализ структуры данных связный список и алгоритмов его обработки»:

- поиск элемента в двусвязном списке приведен в разделе 1.2, блок-схема для него показана на рисунке 5;

- порядок вставки элемента в двусвязный список описан в разделе 1.3, блок-схема для него показана на рисунке 6;

- удаление элемента из двусвязного списка описано в разделе 1.4, блок-схема для него показана на рисунке 7.

Обратим внимание, что в программе используются именно эти алгоритмы, они являются основными. Остальные алгоритмы являются или вспомогательными и не относятся к двусвязному списку, или напрямую проистекают из описанных выше основных алгоритмов, например, операция очистки списка является тривиальной и заключается (в случае двусвязного списка) в удалении ссылок на начало и конец списка. В нашей программе, по причинам, подробно описанным в главе «4 Программная реализация структур данных и алгоритмов их обработки», мы дополнительно пройдем по каждому элементу списка и удалим все ссылки из-за особенностей используемого языка программирования.

Рисунок 4 - Укрупненная блок-схема программы

Рисунок 4, лист 1

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

Рисунок 5 - блок-схема алгоритма поиска нужного элемента в двусвязном списке

Рисунок 5, лист 1

В настоящей работе предлагается реализация программы, в которой вставка элемента осуществляется в конец списка. Это покрывает все наши нужды по добавлению элементов в список студентов. Блок-схема с описанием вставки элемента приведена на рисунке 6. Последний узел списка сохраняется во вспомогательной переменной l. Затем конструируется новый узел newNode, в котором ссылка на следующий элемент next пустая. Он устанавливается в качестве последнего узла списка last. Если последнего узла списка не было (l = null), то новый узел становится также и первым. В противном случае для предыдущего последнего узла списка l вместо пустой добавляется ссылка на следующий узел newNode.

Рисунок 6 - блок-схема алгоритма вставки элемента в конец двусвязного списка

Порядок удаления элемента из двусвязного списка приведен в виде блок-схемы на рисунке 7. На блок-схеме показан алгоритм удаления известного узла списка. Перед удалением нужного узла необходимо провести его поиск согласно вышеописанному алгоритму поиска элемента в двусвязном списке. После определения нужного узла x нужно переместить ссылки в правильном порядке: заменить в предыдущем узле prev ссылку на следующий, затем в следующем узле next заменить ссылку на предыдущий. При этом, если удаляем первый элемент, то ссылки в предыдущем узле менять не нужно, просто указать следующий узел в качестве первого first. Аналогично, если удаляется последний элемент. Это учтено в представленной блок-схеме. После того, как ссылки на текущий узел x будут потеряны, операция удаления фактически завершена. Дополнительно можно также удалить ссылку на сам элемент, так как в некоторых языках программирования это позволит сборщику мусора при необходимости освободить память от неиспользуемых объектов.

Рисунок 7 - блок-схема алгоритма удаления известного (текущего) элемента из двусвязного списка

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

3. Выбор языка программирования

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

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

Так как предлагается для демонстрации результата применить графический интерфейс пользователя (GUI), следует использовать универсальные языки программирования общего назначения, т. е. такие, которые позволят как реализовать общую логику работы списка, так и просто работать с графическими элементами.

Проведем анализ некоторых случайно выбранных языков программирования, С, Java и C# - все они универсальные, т. е. подходят для реализации любых задач. Результат анализа кратко представлен в таблице 1.

Таблица 1 - Название таблицы

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

Из приведенного списка языки Java и C# поддерживают парадигму ООП, что дает преимущества при реализации задач из предметной области. Например, сущность студент, и структура данных список студентов естественным образом укладываются в возможности описания их в виде классов с инкапсуляцией соответствующих методов, которые можно разделить на методы, связанные со студентами, и методы, связанные со списком, как с отдельной сущностью. Продвинутые возможности этих языков, например, применение сокрытия данных, применение интерфейсов, делают программы более гибкими и безопасными. Язык C не обладает такими преимуществами и требует высокого уровня квалификации программиста для обеспечения скорости разработки, безопасности, гибкости и расширяемости кода программы, сравнимой с возможностями ООП.

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

Язык программирования C# не имеет бесплатной среды разработки и, в целом, не имеет такой экосистемы свободно распространяемого и открытого ПО, как, например, языки C и Java. В то же время, для разработки на языке Java имеется полностью бесплатная среда разработки eclipse IDE, которая имеет полностью функциональный WYSIWYG what-you-see-is-what-you-get (в пер. с англ. «получаешь то, что видишь»), т. е. редактор пользовательских интерфейсов в интерактивном режиме реального времени. редактор GUI для быстрого конструирования пользовательских интерфейсов для фреймворка Java Swing, который самостоятельно генерирует исходный код, а также считывает исходный код и генерирует изменения макета GUI. Фреймворк Swing позволяет получить GUI, который будет работать на любой платформе, включая популярные MS Windows, Mac OS (OS X), а также Linux дистрибутивы [2, с. 50].

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

Разработка программного кода ведется с применением следующего бесплатного ПО:

- Интегрированная среда разработки Eclipse IDE Version: 2020-03 (4.15.0);

- wysiwyg плагин WindowBuilder 1.9.3 для Java Swing.

4. Программная реализация структур данных и алгоритмов их обработки

4.1 Общее описание

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

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

- применение объектно-ориентированного подхода;

- размещение отдельных классов в отдельных файлах;

- «программирование от интерфейсов».

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

Итогом применения этих принципов стала следующая структура программы в разбивке на классы:

- Student (в файле Student.java);

- StudentChecks (в файле StudentChecks.java);

- StudentListInterface (в файле StudentListInterface.java);

- StudentList (в файле StudentList.java) Класс StudentList содержит внутренний класс Node (пер. с англ. «узел»), который описывает элемент списка и является частью реализации этой структуры данных.;

- StudentListApp (в файле StudentListApp.java).

Представление классов в окне «Просмотрщика пакетов» в интегрированной среде разработки «Eclipse IDE» показано на рисунке 8.

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

Рисунок 8 - Представление классов в среде разработки «Eclipse IDE»

4.2 Описание интерфейсов

Интерфейс StudentListInterface описывает все необходимые нам переменные и методы, которые обязательно должны быть реализованы:

- size - количество элементов списка;

- add(Student e) - метод добавления элемента;

- remove(Object o) - метод удаления элемента;

- clear() - метод очистки всего списка.

Все методы интерфейса имеют полое описание, которое оформлено в виде специальных комментариев в стиле Javadoc. Например, описание метода add (добавить элемент) приведено на рисунке 6 ниже.

Рисунок 9 -- Пример комментария метода add в программе

Функциональный Функциональным интерфейсом в экосистеме Java называется интерфейс с единственным абстрактным методом. Это делает возможным применение лямбда-выражений, как приема, сокращающего объем кода. интерфейс StudentChecks создан для реализации фильтрации и поиска студентов с определенными параметрами. Функциональный интерфейс позволяет использовать лямбда-выражения. Благодаря лямбда-выражениям можно избежать написания классов, реализующих функциональный интерфейс, а напрямую переопределять метод сразу при его использовании в виде лямбда-выражения и передавать его в качестве параметра в метод, принимающий параметр типа функционального интерфейса. Это относится к особенностям реализации и не входит в сферу рассмотрения в рамках настоящего отчета.