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