Размещено на http://www.allbest.ru/

2

Аннотация

алгоритм программирование язык данные

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

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

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

Содержание

• Введение
• 1 Анализ структуры данных связный список и алгоритмов его обработки
• 2 Разработка алгоритмов программного средства
• 3 Выбор языка программирования
• 4 Программная реализация структур данных и алгоритмов их обработки
• 5 Тестирование программного средства
• Заключение
• Список использованных источников
• Приложение А Программный код

Введение

Сегодня классические структуры данных вроде списков, множеств, деревьев и прочего, а также простейшие алгоритмы, связанные с ними, в подавляющем большинстве случаев реализованы или как стандартный функционал, или как библиотечные функции современных языков программирования. То есть специалист-практик может воспользоваться готовыми качественными реализациями классических алгоритмов, зная способ их вызова или API (интерфейс) в языке программирования. Некоторые алгоритмы и структуры данных настолько популярны и широко используются, что почти всегда применяются в качестве готовых решений, например интерфейс java.utils.List, входящий в Java Collections Framework, предоставляет программисту готовую абстракцию в виде упорядоченного списка с набором стандартных методов для добавления, удаления, получения элементов. Некоторые языки вообще основаны на списках, например Lisp [1, c. 61].

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

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

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

- добавление, удаление элементов сущности;

- поиск;

- вывод элементов (или сохранение в файл).

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

1) проанализировать выбранные структуру данных и алгоритмы ее обработки;

2) разработать алгоритмы программного средства;

3) проанализировать альтернативы и выбрать язык программирования;

4) выполнить программную реализацию структур данных и алгоритмов их обработки;

5) провести анализ сложности разработанных алгоритмов;

6) провести тестирование программного средства и зафиксировать результаты.

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

1. Анализ структуры данных связный список и алгоритмов его обработки

1.1 Общий анализ выбора структур данных в отношении связанных списков

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

- добавления новых данных;

- удаления данных (удаления отдельного узла списка или двусвязного списка полностью);

- поиска данных;

- вывода всего содержимого списка.

Для таких целей естественным образом подходит такой абстрактный тип данных (АТД), как список. Абстрактный тип данных определяет набор функций, независимых от конкретной реализации типа, для оперирования его значениями. Конкретные реализации АТД называются структурами данных [3]. Набор функций для типа список подходит под наши требования. Структурой данных в нашем случае будет двусвязный список.

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



Рисунок 1 - Двусвязный список

Мы используем слово «указание», так как слово указатель имеет специальное значение в некоторых языках программирования, например, в языке C, а в других языках указатели отсутствуют вовсе, вместо них применяются ссылочные типы данных, например, в языке Java. В общем, каждый элемент списка содержит информацию, достаточную для идентификации соседнего элемента (предыдущего или последующего). Также хранится информация о первом («голова», англ. «head») и последнем («хвост», англ. «tail») элементах списка. Это позволяет производить последовательную итерацию по каждому элементу списка.

Двусвязный список имеет как преимущества, так и недостатки. Несомненно, преимуществами можно считать то, что список не может переполниться, если хватает памяти, операции вставки и удаления элементов проще, чем в статических массивах, а также то, что если в основе элементов списка лежат большие записи, то перемещение указателей происходит легче и быстрее, чем перемещение самих записей (посредством копирования). К недостаткам можно отнести эффективность использования памяти, ведь связным структурам нужно место для хранения указателей, и они обладают худшей локальностью, чем массивы (элементы расположены в памяти не последовательно, а хаотично). Но главным недостатком и ограничением для связных списков является то, что в них нет эффективного произвольного доступа к элементам, в отличие от массивов [4, с. 89]. Действительно, для доступа к элементу придется последовательно переходить от каждого элемента к следующему (или к предыдущему при обратном переборе списка).

В свете рассмотренных достоинств и недостатков связных списков, обратим внимание на важные моменты. Во-первых, нам нужно добавлять элементы, и количество добавляемых элементов неизвестно заранее, оно определяется нуждами пользователя. Так как количество элементов заранее не предсказуемо, то такие данные следует организовать в виде списка. [1, c. 62]. Простота самой вставки в нашем случае не имеет особого значения, так как мы можем производить вставку в любое удобное место несортированного списка. Одновременно с этим, не стоит задача долговременного хранения списка студентов в базе данных, а также массового заполнения списка данными, что значит, что список будет небольшим. То есть, единственное значимое ограничение списка в виде невозможности быстрого произвольного доступа к элементам в нашем случае не играет роли. Мы сможем перебирать элементы списка при необходимости, и это не сильно скажется на скорости работы приложения.

Список поддерживает три основных операции: поиск, вставку и удаление [4, с. 87]. Ниже мы опишем основные алгоритмы и проанализируем сложность в виде асимптотической оценки верней границы в О-обозначении для отдельных операций со списком.

1.2 Поиск элемента в двусвязном списке

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

Эта операция занимает O(n) времени, что значит, что он относится к линейному классу сложности [5, c 28], т. е. напрямую зависит от количества элементов в списке, и в целом улучшить ее быстродействие не представляется возможным. Даже если список отсортирован, все равно необходимо перебрать его последовательно для нахождения нужного элемента. Двоичный поиск к спискам неприменим [1, c 64].

Это и приводит к ранее описанному недостатку связанных списков, в них нельзя обеспечить эффективный быстрый доступ к случайному элементу.

1.3 Вставка элемента в двусвязный список

Нам нет необходимости держать список сортированным, поэтому можно вставлять новый элемент туда, куда его проще всего вставить. Для двусвязного списка проще всего делать вставку элемента в начало или в конец, так как в этом случае отпадает необходимость делать обход элементов списка [4, c. 88]. Мы будем делать добавление нового элемента в конец связного списка, ведь мы всегда храним указание на конец списка. Схема добавления нового элемента в конец списка приведена на рисунке 2. На рисунке новые связи показаны пунктирными стрелками.

Рисунок 2 - Вставка элемента в конец двусвязного списка

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

- поместить в новый элемент ссылку на последний элемент списка в качестве указания на предыдущий элемент;

- поместить в новый элемент «нулевую» ссылку (указывающую на отсутствующий элемент) в качестве указания на предыдущий элемент;

- назначить новый элемент последним;

- если последнего элемента в списке нет, что значит он пустой, то назначим новый элемент первым;

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

Такая операция имеет характер O(1) по быстродействию, так как двусвязный список имеет скорость нахождения последнего элемента O(1), ведь указатель на последний элемент двусвязного списка хранится в памяти [1, с. 66].

1.4 Удаление элемента из двусвязного списка

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

Схема удаления элемента представлена на рисунке 3. На рисунке новые связи показаны пунктирными стрелками.



Рисунок 3 - Удаление элемента из двусвязного списка

Для удаления элемента из двусвязного списка нужно выполнить следующие действия:

- поместить в предыдущий перед удаляемым элемент ссылку на следующий после удаляемого элемент в качестве указания на следующий элемент. Если предыдущего элемента нет, то назначить первым элементом следующий после удаляемого элемент (это случай, когда удаляемый элемент является первым);

- поместить в следующий после удаляемого элемент ссылку на предыдущий перед удаляемым элемент в качестве указания на предыдущий элемент. Если следующего после удаляемого элемента нет, то назначить последним элементом предыдущий перед удаляемым элемент (это случай, когда удаляемый элемент является последним);

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

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

Описанные в настоящей главе основные алгоритмы работы с двунаправленными списками представлены в виде блок-схем в следующей главе «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 - Название таблицы

Название языка/технологии	Доступность для разных платформ	Поддержка парадигмы ООП Объектно-ориентированное программирование	Наличие библиотек для быстрой реализации GUI	Наличие бесплатной полнофункциональной среды разработки
C	Да Программа, написанная на языке C, требует компиляции под разные платформы. Для этого требуется учитывать требования кросс-платформенности в тексте программы на языке C, например, в числе прочего, избегая зависимых от компилятора директив.	Нет	Да	Да
Java	Да	Да	Да	Да
C#	Да Только с применением .Net Core	Да	Да	Нет

Все эти языки доступны для разных платформ (например, операционных систем). При этом только 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 создан для реализации фильтрации и поиска студентов с определенными параметрами. Функциональный интерфейс позволяет использовать лямбда-выражения. Благодаря лямбда-выражениям можно избежать написания классов, реализующих функциональный интерфейс, а напрямую переопределять метод сразу при его использовании в виде лямбда-выражения и передавать его в качестве параметра в метод, принимающий параметр типа функционального интерфейса. Это относится к особенностям реализации и не входит в сферу рассмотрения в рамках настоящего отчета.

4.3 Описание классов

Основным классом является Student. В нем описаны все атрибуты для сущности «студент». Студент имеет номер зачетной книжки, имя, фамилию, отчество и дату рождения. Все атрибуты имеют тип данных строка, кроме даты рождения. Дата рождения определена как объект стандартного класса java.time.LocalDate. Этот класс предоставляет удобный интерфейс для работы с датами, включая получение дня, месяца, года, сравнение, преобразование в строку с нужным форматированием.

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

Для нашего класса переопределяем метод equals(), который будем в дальнейшем использовать в операциях доступа к элементам и операциях поиска. Обращаю внимание, что в качестве параметра для метода используем элемент типа java.lang.Object, а не типа Student. Это является правильной практикой всегда по причине того, что целый ряд методов во фреймворке коллекций Java используют в своей реализации метод equals() из класса java.lang.Object, и необходимо переопределять именно его. В нашем же случае, причины несколько другие, а именно:

- для исполнения заявленной нами ранее цели расширяемости приложения, т. к. использование метода equals() с параметром типа Object делает классы и интерфейсы более универсальными и «правильными»;

- в Java присутствует полиморфизм со связыванием времени исполнения, что значит, что мы потенциально можем получать доступ к методу equals() из класса Student через переменные других типов, например, типа Object.

Обычно вместе с методом equals() рекомендуется переопределять метод hashCode(). Однако, в нашем случае такой необходимости нет, так как мы не планируем использовать объекты класса Student в стандартных реализациях коллекций типа Set (например, hashMap).

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

Класс StudentList является реализацией интерфейса StudentListInterface и содержит все методы работы со списком.

Метод add(Student e) обрабатывает нужные нам исключения NullPointerException() и IllegalArgumentException() на случай, если в него передается пустой или неверный параметр. Затем он вызывает метод добавления элемента в конец двусвязного списка addLast(Student e), который в точности воспроизводит ранее описанный в настоящем отчет алгоритм добавления элемента (см. раздел «1.3 Вставка элемента в двусвязный список»).

Метод remove(Object o) также обрабатывает исключения. Затем итерирует каждый элемент и проверяет его на равенство аргументу. Если натолкнулись на искомый элемент, следует удалить его. Это делается вызовом метода unlink(Node x), который реализует удаление текущего элемента из двусвязного списка, как описано в разделе «1.4 Удаление элемента из двусвязного списка».

Метод find(StudentChecks sc) реализует основной алгоритм поиска в двусвязном списке из раздела «1.2 Поиск элемента в двусвязном списке». При этом поиск осуществляется через метод test(Student s) из функционального интерфейса StudentChecks. Это значит, что в программе мы можем использовать любые алгоритмы проверки элемента, например, искать по номеру зачетной книжки, или по совпадению даты рождения. Возвращает значение типа список студентов StudentList. Там мы будем получать отфильтрованные списки для нашего приложения.

Имеются дополнительный метод clear(). Он специфичен для выбранного языка программирования Java. В нем производятся следующие действия:

- обнуляются все ссылки для каждого узла;

- обнуляются ссылки на первый и последний узлы списка;

- размер списка size устанавливается в значение 0.

Это позволяет полностью освободить ресурсы приложения и сделать неиспользуемые объекты списка доступными для автоматического сборщика мусора виртуальной машины Java.

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

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

5. Тестирование программного средства

Программа упакована в исполняемый exe-файл «StudentListApp.exe» для демонстрации работы в ОС Windows.

Главное окно приложения приведено на рисунке 10. Оно содержит сразу короткий демонстрационный список студентов. Все кнопки имеют всплывающие подсказки.

Рисунок 10 - Главное окно приложения «Student List App»

При нажатии на кнопку «Добавить» получаем предложение заполнить данные для добавляемого студента, как показано на рисунке 11 ниже

Рисунок 11 - Попытка добавления пустой записи

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



Рисунок 12 - Заполненный данные студента

Рисунок 13 - Результат добавления студента в список

После добавления можно найти студента в списке. Для примера осуществим поиск студента по номеру зачетной книжки, как показано на рисунке ниже.

Рисунок 14 - Результат поиска студента по кнопке «Найти»

Если пользователь желает вывести весь список, нужно нажать кнопку «Показать все». После этого будет отображен весь список.

Можно выделить нужного студента (при необходимости можно предварительно осуществить поиск нужного студента) и удалить его из списка нажатием кнопки «Удалить». Продемонстрировано на рисунке 15. Удалим студента с номером зачетной книжки «666114» KorablevaNatalia. На экран приложения выводится информация о факте удаления студента из списка.

Рисунок 15 - Результат удаления студента из списка

Закончив работу со списком, можно экспортировать его в файл по кнопке «Экспорт». Нужно выбрать место сохранения для файла списка (рисунок 16).

Рисунок 16 - Выбор файла для сохранения списка

В результате CSV-файл сохранен на диске D. На рисунке 17 показано место сохранения файла, на рисунке 18 - содержимое файла списка студентов.

Рисунок 17 - Место сохранения файла на компьютере

Рисунок 18 - Содержимое экспортированного списка студентов

При необходимости можно удалить всех студентов из списка, нажав на кнопку «Очистить список», как показано на рисунке 19.

Рисунок 19 - Удаление всех студентов из списка

Созданный ранее файл можно использовать для загрузки из него списка студентов. Продемонстрируем результат импорта списка студентов из файла на рисунках 20 и 21 ниже. Если файл не в формате CSV или формат данных неверный, то данные загрузить не получится.

Рисунок 20 - Окно выбора файла для импорта списка

Рисунок 21 - Успешная загрузка списка студентов из файла

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

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

Заключение

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

Для разработки такой программы были изучены и реализованы следующие алгоритмы:

- добавление, удаление элементов сущности;

- поиск в списке сущностей;

- добавление элементов в список (и загрузка элементов из файла);

- вывод элементов (или сохранение в файл).

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

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

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

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

Список использованных источников

алгоритм программирование язык данные

1 Керниган, Брайан У., Пайк, Роб. Практика программирования.: Пер. с англ. - М.: Издательский дом "Вильяме", 2004. - 288 с.

2 Payne, Bryson. Learn Java the easy way: a hands-on introduction to programming. - San Francisco : No Starch Press, Inc., 2018. - 288 c.

3 ВикипедиЯ Свободная энциклопедия [Электронный ресурс] - Режим доступа: https://ru.wikipedia.org/wiki/Абстрактный_тип_данных. - 22.04.2020

4 Скиена С. Алгоритмы. Руководство по разработке. - 2-е изд.: Пер. с англ. - СПб.: БВХ-Петербург, 2011. - 720 с.: ил.

5 Курносов М.Г., Берлизов Д.М. Алгоритмы и структуры обработки информации. - Новосибирск: Параллель, 2019. - 211 с.

Приложение (обязательное)

Программный код

Файл «Student.java»

import java.time.LocalDate;

import java.time.format.DateTimeFormatter;

import java.time.format.FormatStyle;

import java.lang.Object;

class Student {

public Student(int gradeBook, String surname, String firstName, String secondName, LocalDate birthDate) {

super();

this.gradeBook = gradeBook;

this.surname = surname;

this.firstName = firstName;

this.secondName = secondName;

this.birthDate = birthDate;

}

private int gradeBook;

private String surname;

private String firstName;

private String secondName;

private LocalDate birthDate;

public int getGradeBook() {

return gradeBook;

}

public String getSurname() {

return surname;

}

public String getFirstName() {

return firstName;

}

public String getSecondName() {

return secondName;

}

public LocalDate getBirthDate() {

return birthDate;

}

/**

* Так как номер зачетной книжки в реализации списка является уникальным,

* считаем объекты равными при равенстве номеров зачетной книжки

*/

@Override

public boolean equals(Object obj) {

if (obj instanceof Student) {

Student st = (Student) obj;

return (getGradeBook() == st.getGradeBook());

} else {

return false;

}

}

@Override

public String toString() {

return getGradeBook() + ";" + getSurname() + ";" + firstName + ";" + secondName + ";" + birthDate;

}

public static Student parseString(String str) {

String[] data = str.split(";");

LocalDate bd = LocalDate.parse(data[4]);

return new Student(Integer.parseInt(data[0]), data[1], data[2], data[3], bd);

}

public String[] getColumnsArray() {

String[] colArr = new String[5];

colArr[0] = Integer.toString(gradeBook);

colArr[1] = surname;

colArr[2] = firstName;

colArr[3] = secondName;

colArr[4] = birthDate.format(DateTimeFormatter.ofLocalizedDate(FormatStyle.SHORT));

return colArr;

}

}

Файл «StudentChecks.java»

@FunctionalInterface

public interface StudentChecks {

boolean test(Student s);

}

Файл «StudentList.java»

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.File;

import java.io.FileReader;

import java.io.FileWriter;

import java.io.IOException;

class StudentList implements StudentListInterface {

int size = 0;

/**

* Указатель на первый узел.

*/

Node first;

/**

* Указатель на последний узел.

*/

Node last;

/**

* Конструктор пустого списка.

*/

public StudentList() {

}

// Определение узла списка

private static class Node {

Student item;

Node next;

Node prev;

Node(Node prev, Student element, Node next) {

this.item = element;

this.next = next;

this.prev = prev;

}

}

// Методы реализации

/**

* Добавляет указанный элемент в конец списка.

*

* <p>

* Метод такой же, как интерфейсный {@link #add}.

*

* @param e элемент для добавления

*/

private void addLast(Student e) {

final Node l = last;

final Node newNode = new Node(l, e, null);

last = newNode;

if (l == null)

first = newNode;

else

l.next = newNode;

size++;

}

/**

* Удаляет все ссылки на непустой узел списка x.

*/

Student unlink(Node x) {

final Student element = x.item;

final Node next = x.next;

final Node prev = x.prev;

if (prev == null) {

first = next;

} else {

prev.next = next;

x.prev = null;

}

if (next == null) {

last = prev;

} else {

next.prev = prev;

x.next = null;

}

x.item = null;

size--;

return element;

}

public void printList() {

for (Node x = first; x != null;) {

Node next = x.next;

System.out.println(x.item.toString());

x = next;

}

}

boolean checkGradeBookUnique(int gradeBook) {

return (find(st -> {

return st.getGradeBook() == gradeBook;

}).size == 0);

}

// Интерфейсные методы

@Override

public int size() {

return size;

}

/**

* Добавляет указанный элемент в конец списка.

*

* <p>

* Такой же как метод {@link #addLast}.

*

* @param e элемент для добавления в список.

* @return {@code true}, так как изменяет список.

* @throws IllegalArgumentException, если добавляемый элемент не может быть

* добавлен из-за совпадения номера зачетной

* книжки.

* @throws NullPointerException, если указанный элемент пустой

*/

@Override

public boolean add(Student e) {

if (e == null) {

throw new NullPointerException();

} else if (!checkGradeBookUnique(e.getGradeBook())) {

throw new IllegalArgumentException();

} else {

addLast(e);

return true;

}

}

/**

* Удаляет первое вхождение указанного элемента их списка, если такой элемент в

* списке есть. Если такого элемента в списке нет, список не меняется. Более

* строгое описание, удаляет элемент с наименьшим индексом {@code i}, такой

* что{@code Objects.equals(o, get(i))} Возвращает {@code true}, если список

* содержал указанный элемент (то есть, этот список был изменен вызовом этого

* метода).

*

* @param o элемент, который будет удален, если он имеется в списке

* @return {@code true}, если список содержал указанный элемент

* @throws ClassCastException, если тип указанного элемента отличается от

* {@code Student}

* @throws NullPointerException, если указанный элемент пустой ({@code null})

*/

@Override

public boolean remove(Object o) {

if (o == null) {

throw new NullPointerException();

} else if (!(o instanceof Student)) {

throw new ClassCastException();

} else {

for (Node x = first; x != null; x = x.next) {

if (o.equals(x.item)) {

unlink(x);

return true;

}

}

}

return false;

}

/**

* Удаляет все элементы списка. После выполнения метода список пустой.

*/

@Override

public void clear() {

// Удаление всех ссылок помогает Сборщику мусора Java

// очистить память от неиспользуемых узлов, даже если

// будет существовать Итератор по списку

for (Node x = first; x != null;) {

Node next = x.next;

x.item = null;

x.next = null;

x.prev = null;

x = next;

}

first = last = null;

size = 0;

}

private String outOfBoundsMsg(int index) {

return "Index: " + index + ", Size: " + size;

}

private boolean isElementIndex(int index) {

return index >= 0 && index < size;

}

private void checkElementIndex(int index) {

if (!isElementIndex(index))

throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

Node node(int index) {

if (index < (size >> 1)) {

Node x = first;

for (int i = 0; i < index; i++)

x = x.next;

return x;

} else {

Node x = last;

for (int i = size - 1; i > index; i--)

x = x.prev;

return x;

}

}

public Student get(int index) {

checkElementIndex(index);

return node(index).item;

}

public StudentList find(StudentChecks sc) {

StudentList targetList = new StudentList();

for (Node x = first; x != null; x = x.next) {

if (sc.test(x.item)) {

targetList.add(x.item);

}

}

return targetList;

}

public StudentList readFromFile(File file) throws IOException {

StudentList targetList = new StudentList();

String str;

BufferedReader br = new BufferedReader(new FileReader(file));

int counter = 0;

while ((str = br.readLine()) != null) {

counter++;

if (counter > 1) {

targetList.add(Student.parseString(str));

}

}

br.close();

return targetList;

}

public void saveToFile(File targetFile) throws IOException {

BufferedWriter bw = new BufferedWriter(new FileWriter(targetFile));

// заголовок csv файла

bw.write("Номер зачетной книжки;Имя;Фамилия;Отчество;Дата рождения");

for (Node x = first; x != null;) {

Node next = x.next;

bw.write(System.getProperty("line.separator") + x.item.toString());

x = next;

}

bw.close();

}

}

Файл «StudentListApp.java»

import java.time.LocalDate;

import java.time.Month;

import java.time.format.*;

import javax.swing.JFrame;

import javax.swing.JLabel;

import java.awt.Dimension;

import java.awt.Font;

import java.text.NumberFormat;

import javax.swing.SwingConstants;

import javax.swing.UIManager;

import javax.swing.event.*;

import javax.swing.table.AbstractTableModel;

import javax.swing.JFormattedTextField;

import javax.swing.JTextField;

import javax.swing.JButton;

import javax.swing.JFileChooser;

import javax.swing.JTable;

import javax.swing.JTextArea;

import javax.swing.JScrollPane;

import java.awt.event.ActionListener;

import java.io.File;

import java.io.IOException;

import java.awt.event.ActionEvent;

public class StudentListApp extends JFrame implements TableModelListener {

/**

*

*/

private static final long serialVersionUID = 1L;

// Объявления переменных, доступных внутри класса в целом

private JFormattedTextField formattedTxtGradeBook;

private JTextField txtSurname;

private JTextField txtFirstName;

private JTextField txtSecondName;

private final DateTimeFormatter shortFormatter = DateTimeFormatter.ofLocalizedDate(FormatStyle.SHORT);

private JFormattedTextField formattedTxtBirthDate;

private JTextArea txtAreaPrompt;

private JButton btnShowAll;

private JScrollPane scrollPane;

private StudentListTableModel tableModel;

private JTable table;

private StudentList list;

private String[] columnNames = { "Номер з/к", "Фамилия", "Имя", "Отчетсво", "Дата рождения" };

// Конструктор, создающий окно GUI приложения

public StudentListApp() {

// Модельный список для отладки приложения

list = new StudentList();

Student st1 = new Student(666111, "Ivanov", "Ivan", "Ivanovich", LocalDate.of(1990, Month.APRIL, 1));

Student st2 = new Student(666112, "Petrov", "Petr", "Petrovich", LocalDate.of(1991, Month.AUGUST, 10));

Student st3 = new Student(666113, "Korableva", "Tatiana", "Petrovna", LocalDate.of(1990, Month.SEPTEMBER, 7));

Student st4 = new Student(666114, "Korableva", "Natalia", "Petrovna", LocalDate.of(1989, Month.MAY, 5));

list.add(st1);

list.add(st2);

list.add(st3);

list.add(st4);

setTitle("Student List App");

setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

getContentPane().setLayout(null);

// Объявления и свойства элементов GUI

JLabel lblGradeBook = new JLabel("Номер зачетной книжки:");

lblGradeBook.setHorizontalAlignment(SwingConstants.RIGHT);

lblGradeBook.setFont(new Font("Tahoma", Font.PLAIN, 12));

lblGradeBook.setBounds(10, 50, 149, 14);

getContentPane().add(lblGradeBook);

JLabel lblSurname = new JLabel("Фамилия:");

lblSurname.setHorizontalAlignment(SwingConstants.RIGHT);

lblSurname.setFont(new Font("Tahoma", Font.PLAIN, 12));

lblSurname.setBounds(10, 82, 149, 14);

getContentPane().add(lblSurname);

JLabel lblFirstName = new JLabel("Имя:");

lblFirstName.setHorizontalAlignment(SwingConstants.RIGHT);

lblFirstName.setFont(new Font("Tahoma", Font.PLAIN, 12));

lblFirstName.setBounds(10, 114, 149, 14);

getContentPane().add(lblFirstName);

JLabel lblSecondName = new JLabel("Отчество:");

lblSecondName.setHorizontalAlignment(SwingConstants.RIGHT);

lblSecondName.setFont(new Font("Tahoma", Font.PLAIN, 12));

lblSecondName.setBounds(10, 146, 149, 14);

getContentPane().add(lblSecondName);

JLabel lblBirthDate = new JLabel("Дата рождения:");

lblBirthDate.setHorizontalAlignment(SwingConstants.RIGHT);

lblBirthDate.setFont(new Font("Tahoma", Font.PLAIN, 12));

lblBirthDate.setBounds(10, 175, 149, 14);

getContentPane().add(lblBirthDate);

JLabel lblNewLabel = new JLabel("Приложение для ведения списка студентов");

lblNewLabel.setFont(new Font("Tahoma", Font.BOLD, 14));

lblNewLabel.setHorizontalAlignment(SwingConstants.CENTER);

lblNewLabel.setBounds(10, 11, 664, 24);

getContentPane().add(lblNewLabel);

formattedTxtBirthDate = new JFormattedTextField(shortFormatter);

formattedTxtBirthDate.setBounds(169, 174, 309, 20);

getContentPane().add(formattedTxtBirthDate);

formattedTxtBirthDate.setValue(LocalDate.now().format(shortFormatter));

NumberFormat gradeBookFormat = NumberFormat.getIntegerInstance();

gradeBookFormat.setParseIntegerOnly(true);

gradeBookFormat.setGroupingUsed(false);

formattedTxtGradeBook = new JFormattedTextField(gradeBookFormat);

formattedTxtGradeBook.setBounds(169, 45, 309, 20);

getContentPane().add(formattedTxtGradeBook);

formattedTxtGradeBook.setColumns(10);

txtSurname = new JTextField();

txtSurname.setColumns(10);

txtSurname.setBounds(169, 78, 309, 20);

getContentPane().add(txtSurname);

txtFirstName = new JTextField();

txtFirstName.setColumns(10);

txtFirstName.setBounds(169, 111, 309, 20);

getContentPane().add(txtFirstName);

txtSecondName = new JTextField();

txtSecondName.setColumns(10);

txtSecondName.setBounds(169, 144, 309, 20);

getContentPane().add(txtSecondName);

JButton btnAdd = new JButton("Добавить");

btnAdd.addActionListener(new ActionListener() {

public void actionPerformed(ActionEvent e) {

addStudent();

}

});

btnAdd.setFont(new Font("Tahoma", Font.BOLD, 12));