Разработка программных коллекций данных

Министерство науки и высшего образования Российской Федерации 

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 

 
 
 
 
 
 
 
Т.А. РОМАНЕНКО 
 
 
 
 
РАЗРАБОТКА  
ПРОГРАММНЫХ 
КОЛЛЕКЦИЙ ДАННЫХ 
 
Утверждено Редакционно-издательским советом университета 
в качестве учебного пособия 
 
 
 
 
 
 
 
 
 
 
 
НОВОСИБИРСК 
2020 

 

УДК 004.421(075.8) 
         Р 691 
 

Рецензенты: 

канд. техн. наук, доцент А.Б. Крохалева 
канд. техн. наук, доцент Е.Л. Романов 
 
 
 
Работа подготовлена на кафедре вычислительной техники  
для студентов III курса АВТФ, обучающихся по направлениям  
09.03.01 – Информатика и вычислительная техника  
и 09.03.04 – Программная инженерия 
 
 
 
Романенко Т.А. 
Р 691   
Разработка программных коллекций данных: учебное пособие / Т.А. Романенко. – Новосибирск: Изд-во НГТУ, 2020. –  
116 с. 
 
ISBN 978-5-7782-4170-1 
 
Настоящее пособие предназначено для изучения основных типов 
программных коллекций, хранящих множества данных, фундаментальных структур данных и алгоритмов управления ими. Также в пособии предлагается к применению технология проектирования и программирования коллекций, основывающаяся на объектно-ориентированном подходе в программировании. 
 
 
 
УДК 004.421(075.8) 
 
 
ISBN 978-5-7782-4170-1  
 
 
 
 
 
© Романенко Т.А., 2020 
© Новосибирский государственный 
    технический университет, 2020 

 

ПРЕДИСЛОВИЕ 

Организация и представление данных – это естественный процесс, 
сопровождающий разработку любой программы. Причём представление данных в программе и её алгоритм находятся в неразрывной связи. 
Иногда выбранный метод решения задачи определяет необходимое 
представление данных, а иногда первичен выбор структуры данных, который задаёт алгоритм программы. 
В теории и практике программирования широко известны фундаментальные структуры данных и алгоритмы для них (списки, очереди, 
стеки, двоичные деревья поиска, кучи, очереди с приоритетами, хештаблицы, графы, алгоритмы сортировки, поиска). Различные инструментальные среды программирования (IDE) предлагают соответствующие программные средства для этих алгоритмов и структур данных. 
В качестве примера можно привести библиотеку STL (Standard Template Library), спецификация которой является частью стандартизованного языка ANSI/ISO Standard C++.  Библиотека реализована и используется на различных IDE (Windows – C++ Builder и Visual C++, Unix – 
C++). В частности, для наиболее известных структур данных библиотека предлагает набор шаблонов контейнерных классов, воплощающих такие структуры данных как векторы, списки, стеки, очереди, очереди с приоритетами кучи, ассоциативные множества с доступом по 
ключевым значениям данных. Эти контейнеры повсеместно используются при программировании различных приложений, являются базовыми компонентами более сложных форм данных с комбинированной, 
иерархической структурой. 
Данное учебное пособие адресовано студентам, изучающим формы 
организации данных в программах и связанные с ними алгоритмы в рамках дисциплины «Алгоритмы и структуры данных». Пособие содержит 

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

 

1. ТЕХНОЛОГИЯ РАЗРАБОТКИ  
КОЛЛЕКЦИЙ ДАННЫХ 

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

1.1. ПОСТАНОВКА ЗАДАЧИ 

На этом этапе анализируются и детализируются все аспекты задания 
на проектирование коллекции данных. Перед тем как приступить к реализации коллекции, необходимо получить ее описание. Цель постановки задачи – разработать ясное представление того, что надо сделать. 
При этом пока не рассматриваются любые указания того, как будет программироваться коллекция. 
Для проектирования коллекции рекомендуется следовать обобщенному принципу абстракции данных [5]. Коллекция представляется как 
абстрактный тип данных (АТД) – множество данных и множество операций над данными. АТД оговаривает только тип связующей структуры 
в основе множества данных, режим доступа к множеству (стек, очередь, 
прямой доступ, доступ по приоритету, доступ по ключу), набор основных операций. Описание операций должно быть строгим и однозначным для того, чтобы точно указать их воздействие на элементы множества, на изменения в состоянии множества, выходные результаты операций. Для этого используется формат АТД [3, 8], являющийся основой 

для проектирования, а затем и описания программного интерфейса 
между коллекцией и клиентской программой. 
Формат АТД должен включать: 
 общую характеристику АТД, 
 раздел данных, 
 раздел операций. 
Общая характеристика АТД должна формировать внешнее, абстрактное представление о типе множества, его основных свойствах. 
В разделе данных указываются основные параметры множества и 
вид программной структуры для хранения множества. 
В разделе операций  задаётся  набор операций, выполняемых над 
множеством или отдельными его элементами. Учитывая общее назначение будущей коллекции, набор её операций должен быть функционально полным, не противоречивым и не избыточным. Обычно в набор 
операций входят операции опроса и установки общих параметров множества, операции доступа, добавления и удаления отдельных элементов, средства для последовательного доступа ко всем элементам множества (итераторы). 
Операции в АТД представлены в виде спецификаций. В спецификации операции указываются: 
 процесс – краткая формулировка основного действия операции 
без описания деталей реализации, 
 количество и назначение входных параметров, 
 ограничения, накладываемые операцией на входные параметры и 
исходное состояние коллекции (предусловия), 
 результат выполнения операции, в том числе реакция операции 
при нарушении предусловий, 
 постусловия, отражающие изменения в коллекции, произошедшие в результате выполнения операции. 
Предусловия и постусловия составляют контракт между коллекцией 
и использующей её клиентской программой: если программа перед вызовом операции обеспечит соблюдение ее предусловий, то коллекция 
гарантирует, что операция будет успешно завершена и что 
при этом будут достигнуты ожидаемые результаты операции –  
постусловия. 
В качестве примера ниже приведён фрагмент АТД вектора, подобного контейнеру vector, предлагаемого библиотекой STL [5]. 

АТД «ВЕКТОР» 

Общая характеристика 
Вектор – объект, управляющий последовательностью элементов переменной длины. Вектор  реализуется как динамический массив, размер 
которого увеличивается автоматически или по требованию. Элементы 
массива относятся к одному типу T. 
Размерность динамического массива, выделенного для вектора, 
называется ёмкостью вектора (capacity). 
Количество элементов, вставленных в последовательность, называется размером вектора (size). 
Набор операций позволяет управлять вектором как последовательностью: вставлять и удалять элементы по указанным позициям, давать 
прямой доступ по чтению и записи к элементам, в том числе с помощью 
операции индексирования. 
Вектор снабжён итератором произвольного доступа к элементам последовательности, хранящейся в нём. 

Данные: 

Параметры: 
T – тип элементов, хранящихся в векторе 
capacity- ёмкость вектора 
size – размер последовательности в векторе 
Структура хранения коллекции: 
динамический массив элементов типа T – array[capacity] 

Операции: 

Конструктор vector ( ) 
Вход: нет 
Предусловия: нет 
Процесс: создание пустого вектора 
Выход: нет 
Постусловия: создан пустой вектор с числом элементов size  = 0 и с 
емкостью capacity = 0 

Конструктор vector (count, val) 
Вход:  count – ёмкость вектора, val  – значение элементов 
Предусловия: нет 

Процесс: создание в векторе массива array ёмкостью count, заполненного значениями, равными val 
Выход: нет 
Постусловия: создан вектор с последовательностью одинаковых 
значений val, capacity = size = count 

Конструктор копирования vector (Right) 
Вход: Right – ссылка на копируемый вектор 
Предусловия: нет 
Процесс: создание копии вектора Right 
Выход: нет 
Постусловия: создана копия вектора Right с числом элементов size 
= Right. size () в массиве с емкостью capacity = Right Capacity( ) 

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

Опрос размера последовательности size ( ) 
Вход: нет 
Предусловия: нет 
Процесс: возврат текущего количества значений size, хранящихся в 
векторе 
Выход: размер вектора size 
Постусловия: нет 

Резервирование емкости вектора reserve (count) 
Вход: минимальная ёмкость вектора count 
Предусловия: нет 
Процесс: проверка текущей ёмкости вектора capacity и перестройка 
массива array, если count > capacity 
Выход: нет 
Постусловия: array[capacity], capacity ≥ count 

Уменьшение ёмкости вектора shrink_to_fit () 
Предусловия: нет 

Процесс:  уменьшение размера массива array за счёт освобождения 
неиспользованной памяти 
Выход: нет 
Постусловия: array[capacity], capacity = size 

Оператор индексирования [pos] 
Вход: позиция элемента pos 
Предусловия: нет 
Процесс: возврат ссылки на элемент array [ pos ]. 
Контроль выхода за границы массива array не осуществляется 
Выход: ссылка на элемент массива array[pos].  
Постусловия: нет 

Доступ к элементу at(pos) 
Предусловия: 0   pos < size 
Процесс: возврат ссылки на элемент array [pos] 
Выход: ссылка на элемент массива array[pos] или генерация исключения out_of_range при невыполнении предусловия 
Постусловия: нет 

Операция добавления в конец push_back (val) 
Вход: val – значение элемента типа Т 
Предусловия: нет 
Процесс: добавление элемента val в конец вектора 
Выход: нет 
Постусловия: элемент со значением val добавлен в конец вектора, 
размер вектора size = size + 1. Если size > capacity, то capacity = 2 × 
capacity. 

Операция добавления элементов в указанную позицию insert (val, 
pos) 
Вход: val – значение элемента, pos – позиция в векторе для вставки 
Предусловия: 0 ≤ pos ≤ size 
Процесс: добавление элемента val в позицию pos, size =. size + 1 
Если size > capacity, то удвоение емкости массива array 
Выход: нет 
Постусловия: элемент со значением val добавлен в позицию, size = 
size + 1. Если size > capacity, то capacity = 2 × capacity. 

Операция удаления элемента из указанной позиции  erase (pos) 
Вход: pos – позиция в векторе для удаления 
Предусловия: 0 ≤ pos < size 
Процесс: удаление элемента из позиции pos, size = size - 1 
Выход: нет 
Постусловия: элемент в позиции pos удалён, size = size - 1 

Запрос итератора произвольного доступа begin( ) 
Вход: нет 
Предусловия: size ≠ 0 
Процесс: формирование итератора произвольного доступа, установленного на первый элемент последовательности в векторе 
Выход: итератор произвольного доступа, установленный на первый 
элемент begin( ) или «неустановленный» итератор end( ) при невыполнении предусловия 
Постусловия: нет 

Запрос «неустановленного» итератора end( ) 
Вход: нет 
Предусловия: нет 
Процесс: формирование «неустановленного» итератора, указывающего на позицию, следующую за последним элементом последовательности в векторе 
Выход: «неустановленный» итератор произвольного доступа end( ) 
Постусловия: нет 

Запрос итератора произвольного доступа rbegin( ) 
Вход: нет 
Предусловия: size ≠ 0 
Процесс: формирование итератора произвольного доступа, установленного на последний элемент последовательности в векторе end( ) 
Выход: итератор произвольного доступа к элементам  rbegin( ) или 
«неустановленный» итератор rend( ) при невыполнении предусловия 
Постусловия: нет 

Запрос «неустановленного» итератора rend( ) 
Вход: нет 
Предусловия: нет 
Процесс: формирование «неустановленного» итератора произвольного доступа, указывающего на позицию, предыдущую первому элементу последовательности в векторе.