Выпускная квалификационная работа бакалавра

Цель работы: целью данной работы является реализация инструментального программного средства, которое позволит автоматически генерировать код по спроектированной структуре данных.
Объект исследования: контейнерные классы из Стандартной библиотеки шаблонов и алгоритмы работы с ними.
Ключевые слова: проектирование структур данных, стандартная библиотека шаблонов, оценка сложности алгоритмов.
Выпускная квалификационная работа состоит из 11 параграфов, 71 страницы, включает 62 рисунка, 1 таблицу, 7 источников.
Результаты работы:
В результате данной работы реализовано инструментальное программное средство, позволяющее проектировать структуры данных. Эти структуры базируются на выбранных контейнерах из STL и имеют минимальный набор функций для работы с ними.
СОДЕРЖАНИЕ

РЕФЕРАТ 3
СОДЕРЖАНИЕ 4
ВВЕДЕНИЕ 5
1 Постановка задачи 7
2 Контейнеры в STL 7
3 Последовательные контейнеры 10
4Ассоциативные контейнеры 12
5Проектирование пользовательской структуры 14
6 Функциональный интерфейс 17
7Шаблон структуры 19
8Оценка сложности базовых функций 21
9Обобщенные алгоритмы для работы с суперпозицией контейнеров 53
10Тестирование структуры 56
11Структура программы 61
Node 61
ЗАКЛЮЧЕНИЕ 71
СПИСОК ЛИТЕРАТУРЫ 72

ВВЕДЕНИЕ
Работа с разными структурами данных является неотъемлемой частью разработки программного обеспечения. Сложность реализации и качество работы программ существенно зависит от их правильного выбора. Это понимание дало начало языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом модульности, позволяющим структурам данных безопасно переиспользоваться в различных приложениях. Объектно-ориентированный язык C++ является примером такого подхода.
В настоящее время для языка C++ имеются библиотеки, в которых реализованы основные структуры и алгоритмы работы с ними, в частности Стандартная Библиотека Шаблонов (Standard Template Library (STL)). Для каждой структуры данных в STL определен ряд стандартных функций. Они имеют разные реализации, которые эффективно использовать для различных задач. Основные из них это функции вставки, удаления и поиска элементов, а также функции, которые реализуют доступ к элементам. От их выбора существенно зависит время работы алгоритма, так как они предлагают различные компромиссы в сложности выполнения.
Использование данной библиотеки позволяет значительно повысить универсальность программ и их переносимость, а также её использование ускоряет разработку конечного продукта.
Чаще всего приходится из основных структур STL проектировать свои составные структуры. Целью данной работы будет разработка программы, которая при помощи визуальных средств позволит делать это автоматически. Результатом её работы будет библиотека для языка C++, в которой будет содержаться реализация пользовательской структуры данных.
Так как в библиотеке будет составная структура, то необходимо учитывать особенности всех включенных в неё контейнерных классов.
Выбирая различные способы работы с каждой структурой, можно сильно влиять на работу всей суперпозиции в целом. Чтобы обеспечить приемлемую сложность выполнения базовых операций в составной структуре, необходимо комбинировать предложенные стандартные функции в зависимости от текущей ситуации. Таким образом, нужно реализовать такие алгоритмы работы с полученной структурой, которые бы учитывали многие её особенности. Очевидно, что эти алгоритмы будут работать медленнее по сравнению с работой стандартных алгоритмов в наилучших и худших случаях. С другой стороны, можно обеспечить улучшенную работу по сравнению со стандартной работой алгоритмов в средних случаях.
1 Постановка задачи
Целью данной работы является реализация инструментального программного средства, которое позволит автоматически генерировать код по спроектированной структуре данных. При этом необходимо:

1. 
   Разработать визуальные средства для проектирования структуры;
   
2. 
   Применять следующие контейнеры из STL: вектор, двусторонняя очередь, список, множество, множество с дубликатами, словарь и словарь с дубликатами;
   
3. 
   Выбрать алгоритмы для работы с суперпозициями этих контейнеров, которые будут учитывать особенности каждого из них. Для этого необходимо:
   

1. 
   Проанализировать стандартные функции для каждого контейнера в отдельности;
   
2. 
   Выявить из них те, которые имеют минимальные временные затраты;
   
3. 
   Основываясь на выбранных функциях, построить основные алгоритмы для работы с составной структурой.
   

4. 
   На основе выбранных алгоритмов реализовать следующие функции для работы со структурой: доступ к элементам, добавление новых элементов, поиск и удаление уже имеющихся элементов;
   
5. 
   Результатом работы программного средства должна быть библиотека для языка C++.
   

2 Контейнеры в STL
При разработке программного обеспечения часто можно выделить некоторые стандартные решения, которые в дальнейшем можно переиспользовать. К ним относятся обобщённые алгоритмы, структуры данных и различные вспомогательные функции. Такие решения обычно выделяют в библиотеки, которые в дальнейшем могут стать стандартизированными и поставляться любым компилятором языка. Примером этого является Стандартная библиотека шаблонов (Standard Template Library(STL)).
Стандартная библиотека шаблонов входит в стандартную библиотеку языка C++. В неё включены реализации наиболее часто используемых контейнеров и алгоритмов, что избавляет программистов от повторной реализации базовых решений.
Выделяют следующие основные компоненты:

1. 
   Контейнер — хранение набора объектов в памяти;
   
2. 
   Итератор — обеспечение средств доступа к содержимому контейнера;
   
3. 
   Алгоритм — определение вычислительной процедуры;
   
4. 
   Адаптер — адаптация компонентов для обеспечения различного интерфейса;
   
5. 
   Функциональный объект — сокрытие функции в объекте для использования другими компонентами.
   

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

1. 
   Вектор - динамический массив с произвольным доступом и автоматическим изменением размера;
   
2. 
   Двусторонняя очередь - контейнер, похожий на вектор, но с возможностью быстрой вставки и удаления из обоих концов;
   
3. 
   Список - двусвязный список, элементы которого хранятся в произвольных участках памяти;
   
4. 
   Множество - упорядоченное множество уникальных элементов;
   
5. 
   Множество с дубликатами - множество с повторяющимися элементами;
   
6. 
   Словарь - упорядоченный ассоциативный массив пар "ключ- значение";
   
7. 
   Словарь с дубликатами - словарь с повторяющимися ключами.
   

Вектор, двусторонняя очередь и список являются последовательными контейнерами, то есть обеспечивают хранение конечного количества однотипных величин в виде непрерывной последовательности. Они поддерживают указанный пользователем порядок вставляемых элементов.
Множество, множество с дубликатами, словарь и словарь с дубликатами являются ассоциативными контейнерами, то есть элементы вставляются в некотором предварительно определенном порядке. Эти контейнеры обеспечивают быстрый доступ к своим элементам, так как основаны на сбалансированных деревьях поиска.
3 Последовательные контейнеры
Вектор (vector) похож по принципу работы на стандартный массив, но с дополнительными возможностями, такими как автоматическое изменение размера при вставке или удалении элемента. Автоматическое изменение размера заключается в том, что если при работе с вектором происходит превышение текущего размера, то объём выделенной памяти увеличивается в полтора раза. Но операция перераспределения памяти имеет большую сложность, поэтому лучше знать заранее изначальный размер вектора. Память под него выделяется не поэлементно каждый раз, а сразу под группу элементов. После перестроения все итераторы, ссылающиеся на элементы вектора, становятся недействительными, так как вектор может быть перемещён в другой участок памяти. Вставка в вектор и удаление элемента из него занимают время, пропорциональное количеству сдвигаемых элементов на новые позиции. Если при вставке перераспределения не происходит, все итераторы сохраняют свои значения, иначе они становятся недействительными. Все итераторы после места удаления становятся недействительными. Вектор эффективно реализует произвольный доступ к элементам, добавление в конец и удаление из конца. Также он поддерживает и связанное хранение. По этим причинам контейнер vector является наиболее предпочтительным последовательным контейнером для большинства областей применения.
Двусторонняя очередь (deque) - это последовательный контейнер, который похож на вектор. Она также поддерживает произвольный доступ к элементам, но, в отличие от вектора, может обеспечить вставку и удаление из обоих концов очереди за постоянное время и не поддерживает связное хранение. Операции вставки и удаления элементов внутри очереди занимают время, пропорциональное количеству перемещаемых элементов. Распределение памяти также выполняется автоматически. Доступ к элементам осуществляется за постоянное время, но немного медленнее, чем для вектора. Поведение итераторов отличается от итераторов в векторе. Если вставка и удаление происходят во внутренних элементах, то итераторы становятся недействительными. После добавления в любой из концов значения итераторов также будут недействительными, но после выборки из концов становятся недействительными только те итераторы, которые были связаны с этими элементами.
Класс список (list) реализован в STL в виде двусвязного списка, то есть каждый узел содержит информацию о следующем и предыдущем элементах. Список не предоставляет произвольного доступа к своим элементам, но зато вставка и удаление выполняется за постоянное время. Перемещение на несколько узлов требует времени, пропорционального количеству узлов, необходимых для перемещения. После выполнения операции вставки и удаления значения всех итераторов остаются действительными. Операции инкремента и декремента у итераторов списка выполняются за постоянное время.

4. 
   Ассоциативные контейнеры
   

Множество (set) - это ассоциативный контейнер, в котором хранятся значения ключей, которые должны быть уникальными. В данном контейнере элементы хранятся в упорядоченном виде, поэтому для ключей должно быть определено отношение "меньше". Добавление очередного элемента производится при условии, что он не является дублем для какого-нибудь элемента из множества. Значения элементов в наборе невозможно изменять напрямую. Для этого прежние значения необходимо удалить, а после вставить элементы с новыми значениями.
Во множествах с дубликатами (multiset) ключи при необходимости могут повторяться. Из этого следует, что операция вставки элементов всегда выполняется успешно. Элементы, которые имеют одинаковые ключи, хранятся во множестве в порядке их добавления. Так как имеются одинаковые ключи, то вводятся и разные функции поиска. Есть функции, которые возвращают первый найденный элемент, которые возвращают количество одинаковых элементов. Также есть функции, которые возвращают элементы до и после последовательности одинаковых ключей. При удалении элементов по ключу удаляются все элементы, имеющие ключ удаления.
В словаре (map) как и во множестве хранятся ключи, но каждому из них сопоставлено некоторое значение. Таким образом, можно сказать, что ключ ассоциирован с элементом. Для создания такой пары "ключ - значение" применяется шаблон pair. У этого шаблона есть два параметра: first и second. При создании объекта пары требуется присвоить ей значение явным образом.
Для ключей должны выполняться те же свойства, что и для ключей во множестве.
В словаре имеется доступ к элементу по ключу с помощью оператора T& operator[](const key_type& x). Данной операцией можно получать и добавлять новые значения элементов в словарь.
В словарях с дубликатами (multimap) разрешается хранение элементов с одинаковыми ключами. Для них не определена операция доступа по индексу. Добавление новых элементов выполняется успешно в любом случае. Все свойства ключей похоже на свойства ключей множества с дубликатами.
Для всех ассоциативных контейнеров операции вставки не повреждают связанные с ними итераторы и ссылки, а операции удаления делаю недействительными только те итераторы и ссылки, которые связаны с удаляемыми элементами.

4. 
   Проектирование пользовательской структуры
   

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

1. 
   Корневые узлы;
   
2. 
   Терминальные узлы;
   
3. 
   Узлы ветвления;
   
4. 
   Свободные узлы.
   

Корневым узлом называется такой узел, которому соответствует вершина с нулевой степенью захода, то есть в данную вершину не ведёт ни одна дуга. Такой узел будет единственным и будет обязательно входить в структуру по умолчанию.
Терминальным узлом называется такой узел, которому соответствует вершина только с одной входящей дугой и из этой вершины не исходит ни одной дуги.
Узлом ветвления называется любой другой узел, которому соответствует какая-либо вершина из дерева.
Узел называется свободным, если нет вершины, которой он соответствует, то есть этот узел не принадлежит дереву.
Каждый узел будет иметь свой уровень вложенности. Под уровнем будем понимать длину пути от корня до узла. Сам корень имеет нулевой уровень вложенности.
Проектирование будет производиться с рядом ограничений:

1. 
   При создании связи между узлами родительским узлом может быть только элемент из дерева, при условии, что он не имеет конечный тип, а дочерним узлом может быть только свободный узел;
   
2. 
   Конечный тип могут иметь только терминальные вершины последнего уровня;
   
3. 
   Терминальный узел с конечным типом не имеет потомков;
   
4. 
   Узлы одного уровня имеют одинаковый тип.
   

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

1	2	3
4	5	6
7	8	9

Её можно представить, например, следующими структурами:

Рисунок 1 - Реализация матрицы с помощью векторов.

или

Рисунок 2 - Реализация матрицы с помощью списков.

Учитывая особенности вектора и списка, в результате получатся совершенно разные по своим свойствам структуры.
Перед созданием библиотеки нужно будет также указать название для спроектированной структуры и конечный тип для неё. Название структуры не должно содержать в себе символы табуляции и использовать зарезервированные слова для языка C++. В качестве конечного типа может быть указан как стандартный тип данных (int, float, char и т.д.), так и любой пользовательский. Но, если при использовании стандартного типа можно гарантировать работоспособность структуры, то при пользовательском типе данных это невозможно. Создатель структуры должен быть уверен, что его тип данных является корректным.
Во время создания библиотеки все веденные данные о структуре проходят проверку на корректность. В случае её успешного завершения происходит анализ связей между узлами. Для этого применяется обход полученного дерева в ширину. Начиная с нулевого уровня и заканчивая последним, анализируется информация о каждом узле текущего уровня. Из него берётся информация, которая будет необходима для составления кода в библиотеке. К ней относится количество потомков у каждого узла, тип контейнера на уровне и значения для инициализации, введенные в терминальные узлы последнего уровня. После окончания обхода также запоминается информация о названии структуры и конечный тип. По этим собранным данным происходит дальнейшее формирование библиотеки, используя заготовленный шаблон.
6 Функциональный интерфейс
Для любой структуры данных необходим набор минимальных функций, который определяет её интерфейс. К этим базовым функциям относятся такие функции как доступ к элементам, добавление новых элементов, поиск и удаление уже имеющихся элементов. Без реализации этого интерфейса теряется весь смысл самой структуры, задачей которой является хранение и обработка множества однотипных и/или логически связанных данных. Но все эти функции важны только тогда, когда структура имеет функцию, которая отвечает за её размещение в памяти.
Для реализации функции создания структуры нужно применить некий унифицированный способ, который будет применим ко всем контейнерам. В STL поддерживается функция изменения размера. Она добавляет новые элементы к текущему контейнеру, если новый размер будет больше текущего, и удаляет элементы, если новый размер будет меньше текущего размера. По умолчанию все контейнеры имеют нулевой размер. Если будет происходить добавление элементов, то новые элементы будут проинициализированы нулевыми значениями. Для создания структуры у нас имеется вся необходимая информация. Это количество потомком каждого узла и значения для инициализации терминальных узлов последнего уровня. Для последовательных контейнеров можно использовать алгоритм, основанный на прямом обходе дерева. Посещаем очередной узел и задаем ему размер, который соответствует количеству его потомков. Начиная перебирать его потомков, повторяем прошлую операцию. Если оказываемся в терминальном узле последнего уровня, то смотрим, есть ли у него значение для инициализации. Если есть, то делаем присвоение. В результате будет захвачена память под все узлы структуры. Но данный подход применим только в том случае, когда в составной структуре используются только последовательный контейнеры. У ассоциативных контейнеров нет функции изменения размера до заданного значения. Он будет изменяться только при добавлении новых элементов. Поэтому в данном случае нужно применить обратный обход дерева. Начиная с терминальных вершин, захватываем память под элементы и помещаем их в родительские вершины. В результате такого обхода и использования функции вставки удастся захватить память под спроектированную структуру.
Рассмотрим функцию доступа к элементам. Так как полученная структура будет иметь некоторый уровень вложенности n, то и для обращения к некоторому элементу нужно использовать n индексов. Каждый такой индекс определяет нахождение элемента в текущем поддереве. На каждом уровне структуры нужно обратиться к узлу по соответствующему индексу и получить доступ к интересующему элементу. Особенность данной функции заключается в том, что если на каком-то уровне индекс превышает количество потомков узла, то этот узел изменит размер до этого индекса.
Функция добавления нового элемента аналогична функции доступа к элементам. Также по n индексам находится положение для нового элемента и происходит его добавление. Это возможно сделать, так как все контейнеры поддерживаю функцию вставки элемента в произвольное место.
В функции поиска элемента нас интересуют только терминальные вершины последнего уровня. Производим обратный обход дерева и при достижении вершин последнего уровня сравниваем их ключ с ключом, по которому производится поиск. При совпадении заканчиваем эту процедуру.
Функция удаления элемента аналогична функции доступа к элементам, но индекс каждого уровня должен быть меньше количества потомков узла. Удаление элемента производится при помощи функции, которую поддерживают все контейнеры.
Таким образом, реализация минимального набора функций представляется возможной. Это позволит обеспечить нормальную работу со спроектированной структурой, так как на основе этих базовых функций можно составить множество различных функций любой сложности.

7. 
   Шаблон структуры
   

Extensible Markup Language (XML) — это язык разметки или, другими словами, средство описания документа. Хотя этот язык создавались Консорциумом Всемирной паутины, прежде всего, как средства представления информационных ресурсов Веб-2, он, тем не менее, нашёл широкое применение в различных областях информационных технологий. Одна из них - это функция языка-посредника при обмене данными между программными системами.
В языке используется простой формальный синтаксис, при помощи которого создается структура документа. Благодаря этому, документ удобно обрабатывать как человеку, так и программам. Вся структура разбивается на две основные части: корневой элемент и пролог. Корневой элемент обязательно должен присутствовать в документе, так как он определяет его суть. Корень может содержать в себе вложенные элементы и символьные данные. В свою очередь, вложенные элементы тоже могут содержать в себе другие элементы. Все элементы документа подчиняются правилу: любой элемент, начинающийся внутри другого элемента, должен заканчиваться внутри элемента, в котором он начался. Внутри элементов могут встречаться символьные данные и атрибуты. Атрибуты применяются для добавления к элементу логической единицы типа имя-значение. Наличие пролога в документе необязательно. Он может включать в себя объявления, инструкции обработки или комментарии. Обычно его начинают с объявления XML, хотя это не является критичным.
В данной работе в xml документе хранится шаблон для создания библиотеки со спроектированной структурой. При анализе полученной структуры в данный шаблон записывается вся необходимая информация об используемых контейнерах, ветвлении, инициализации, имени структуры и конечного типа. Также в данном шаблоне содержится информация об общих элементах кода, которые должны быть в библиотеке, независимо от вида спроектированной структуры. К общим элементам относятся списки подключаемых элементов из STL, список используемых пространств имён, определения всех базовых функций, необходимых для работы со структурой. Все основные функции имеют зарезервированные имена в рамках создаваемой библиотеки, а также фиксированный набор входных параметров для них. Параметры могут различаться только количеством индексов, по которым происходит доступ к интересующему элементу структуры.
Имея такой заполненный шаблонный файл, можно создать требуемую библиотеку для языка C++, которая будет полностью соответствовать той структуре, которая представлена визуальными средствами. Также по данному файлу можно проверить корректность обработки всей информации о созданной структуре, так как удобно просматривать внутреннюю структуру полученного документа.

7. 
   Оценка сложности базовых функций
   

По стандарту языка C++ имеем следующие сложности базовых функций для контейнеров:
Таблица 1 - Оценка сложности базовых функций для контейнеров из STL.