Файл: Операции, производимые с данными (Типы структур данных и предметная область).pdf

ВВЕДЕНИЕ

Технология программирования представляет собой совокупность средств и методов, необходимых для разработки программного обеспечения. Решающее значение для специалиста в области информационных технологий и программирования имеет выбор парадигмы программирования, определяющей успешность реализации программного продукта, и соответствующего ей языка программирования [11.]. За последние 50 лет появились сотни языков, поддерживающих различные парадигмы, причем некоторые из них используют несколько парадигм (такие языки называют мультипарадигменными). Однако, несмотря на большое количество языков программирования, существует несколько действительно важных концепций программирования, и не так много языков, которые были бы актуальны на протяжении более десяти лет. Именно парадигмы программирования определяют общий способ проектирования прикладных программ [3.]. Парадигмой программирования называют используемый различными языками подход к программированию, то есть, проще говоря, набор идей и понятий, определяющих стиль написания программ. Среди основных парадигм программирования выделяют объектно-ориентированную, императивную, декларативную, структурную, функциональную и логическую. Большинство языков программирования, активно используемых в современной разработке прикладных программ, являются мультипарадигменными [4.].

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

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

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

Для достижения обозначенных целей были выбраны следующие методы исследования: систематизация специальной литературы и мировых информационных ресурсов по проблеме исследования.

1. Теоретические сведения

1.1 Типы структур данных и предметная область

Структуры данных играют довольно важную роль в разработке программного обеспечения [12.]. По сути, они представляют собой всего лишь специальные форматы для организации и хранения данных.

Структура данных – это контейнер, который хранит данные в определенном макете [1.]. Этот «макет» позволяет структуре данных быть эффективной в некоторых операциях и неэффективной в других.

Структуры данных активно используются в различных областях знаний, находя широкое применение в многочисленных научных и практических приложениях [10.]. Структуру данных можно считать некоторой совокупностью однотипных и/или логически связанных данных, которую можно хранить и обрабатывать как единое целое. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.

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

В простейших контейнерах акцент сделан на самих значениях. Например, органайзер, представляющий собой список запланированных событий, используется для хранения набора элементов – предстоящих событий. Можно добавить новое значение в список, проверить, найдено ли значение в списке и удалить значение из списка. В словаре, с другой стороны, данные разделены на две части. Каждый элемент, хранящийся в словаре, представлен парой ключ / значение. Ключ используется для доступа к элементу. С помощью ключа можно получить доступ к значению, которое обычно содержит больше информации [5.].

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

В ходе работы были поставлены и решены следующие задачи:

1. Определен функционал ИСС «Банковские вклады»;
2. Обоснован выбор структур данных, оптимальных для разработки приложения;
3. Спроектирована модульная структура приложения;
4. Разработаны алгоритмы работы модулей;
5. Выполнена реализация и тестирование программного приложения средствами языка Python версии 3.7.

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

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

Для выполнения поставленной в работе задачи была выбрана такая структура данных, как «линейный односвязный список» (ЛОС), позволяющая хранить информацию о банковских вкладах.

Взаимодействие с пользователем осуществляется при помощи графического интерфейса.

1.2 Линейный односвязный список

Односвязный список – структура данных, в которой каждый элемент является отдельным объектом и состоит из двух элементов: данных и ссылки на следующий узел (рисунок 1). 

Принципиальным преимуществом связанного списка перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задается его внутренними связями [6.].

«Голова» списка (head) – это первый элемент списка; «хвостом» списка называют оставшуюся часть списка без «головы».

Рисунок 1 – Организация данных в односвязном списке

Базовые операции, которые можно выполнять со списками [13.]:

1. Добавление узла в список.

Функция добавления узла в список принимает два аргумента:

• указатель на узел, после которого происходит добавление;
• данные для добавляемого узла.

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

• создание добавляемого узла и заполнение его поля данных;
• переустановка указателя узла, предшествующего добавляемому, на добавляемый узел;
• установка указателя добавляемого узла на следующий узел (тот, на который указывал предшествующий узел).

Процедуру добавления узла можно отобразить схемой, представленной на рисунке 2.

Рисунок 2 – Добавление узла в список

1. Удаление узла из списка.

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

Удаление узла из списка включает в себя следующие этапы [14.]:

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

Процедуру удаления узла можно отобразить схемой, представленной на рисунке 3.

Рисунок 3 – Удаление узла из списка

1. Получение длины списка.

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

1. Поиск элемента в списке.

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

Линейный поиск [7.] – очень простой и понятный алгоритм поиска в структуре данных. Нужный элемент ищется путем обхода списка от начала до конца до тех пор, пока не будет найден. Заданный элемент для поиска сравнивается со всеми элементами, присутствующими в списке, и при успешном сопоставлении (когда значения равны) возвращается номер текущего элемента в списке или число -1.

На рисунке 4 проиллюстрировано начало работы алгоритма линейного поиска в предположении, что ищется число 3,8. Поиск начинается с первого элемента – при первом сравнении 1,5 не равно 3,8, поэтому выполняется переход к следующему элементу.

Рисунок 4 – Начало работы алгоритма линейного поиска

Следующее сравнение представлено на рисунке 5. Число 2,7 также не равно 3,8, поэтому алгоритм выполняет переход к следующему элементу.

Рисунок 5 – Второй шаг алгоритма линейного поиска

На третьем шаге алгоритма выполняется еще одно сравнение (рисунок 6), которое позволяет сделать вывод о том, что искомый элемент найден. Алгоритм возвращает позицию этого элемента (индекс 2 при индексировании с нуля).

Рисунок 6 – Последний шаг алгоритма линейного поиска

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

Процедура поиска отражена на рисунке 7 в виде блок-схемы.

Для реализации приложения учета банковских вкладов наиболее удобно использовать односвязный список, поскольку каждая заявка (с информацией о вкладе) может быть представлена как конкретный элемент списка. Заявку можно удалить из списка, или же можно добавить в список новую заявку. Также списки обеспечивают эффективное (за константное время) добавление и удаление элементов [8., 9.].

Рисунок 7 – Поиск элемента в списке

1.3 Алгоритмы для производимых операций

Программное приложение, или АИС «Банковские вклады» содержит информацию по заявкам на вклады (включая уже открытые вклады; понятия «заявка на вклад» и «вклад» далее используются взаимозаменяемо) и поддерживает следующие функции:

1. Добавление вклада. Пользователю предлагается ввести данные для добавления заявки на вклад в список (рисунок 8).
2. Удаление вклада. Пользователь имеет возможность выбрать конкретный вклад и удалить его; при этом высвечивается сообщение об ошибке, если пользователь не выбрал ни один вклад, но вызвал функцию удаления (рисунок 9).