Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Введение в коллекции хранения данных

Покупка
Основная коллекция
Артикул: 875936.01.99
Доступ онлайн
500 ₽
В корзину
В учебном пособии изложен теоретический материал, который применяется при решении задач хранения и обработки данных в системах кодирования и передачи информации, а также при решении аналогичных задач во время разработки программного обеспечения высокого уровня. Приведено описание трех практических заданий, в ходе выполнения которых можно получить навыки программирования коллекций данных. Учебное пособие предназначено студентам III курса АВТФ направления 27.03.04 «Управление в технических системах», а также может быть полезно всем интересующимся вопросами программирования на языке C++.
Катасонов, Д. Н. Введение в коллекции хранения данных : учебное пособие / Д. Н. Катасонов. - Новосибирск : Изд-во НГТУ, 2023. - 64 с. - ISBN 978-5-7782-4965-3. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2246221 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Министерство науки и высшего образования Российской Федерации 
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 
 
 
 
 
 
Д. Н. КАТАСОНОВ 
 
 
 
 
 
 
 
ВВЕДЕНИЕ В КОЛЛЕКЦИИ 
ХРАНЕНИЯ ДАННЫХ 
 
Утверждено Редакционно-издательским советом университета 
в качестве учебного пособия 
 
 
 
 
 
 
 
 
 
 
 
 
НОВОСИБИРСК 
2023 
 


УДК 004.6(075.8) 
         К291 
 
 
Рецензенты: 
Г. В. Саблина, канд. техн. наук, доцент 
Н. А. Коломеец, канд. физ.-мат. наук, научный сотрудник ИМ СО РАН 
 
 
 
 
Работа подготовлена на кафедре автоматики 
 
 
Катасонов Д. Н. 
К291   
Введение в коллекции хранения данных : учебное пособие / 
Д. Н. Катасонов. – Новосибирск : Изд-во НГТУ, 2023. – 64 с. 
 
ISBN 978-5-7782-4965-3 
 
В учебном пособии изложен теоретический материал, который применяется при решении задач хранения и обработки данных в системах 
кодирования и передачи информации, а также при решении аналогичных задач во время разработки программного обеспечения высокого 
уровня. Приведено описание трех практических заданий, в ходе выполнения которых можно получить навыки программирования коллекций 
данных. 
Учебное пособие предназначено студентам III курса АВТФ направления 27.03.04 «Управление в технических системах», а также может 
быть полезно всем интересующимся вопросами программирования на 
языке C++. 
 
УДК 004.6(075.8) 
 
 
ISBN 978-5-7782-4965-3  
 
 
 
 
 
© Катасонов Д. Н., 2023 
© Новосибирский государственный 
    технический университет, 2023 
 


 
 
 
 
 
 
ÎÃËÀÂËÅÍÈÅ 
Введение ................................................................................................................... 4 
1. КОЛЛЕКЦИЯ ДАННЫХ «ВЕКТОР» ................................................................ 5 
2. КОЛЛЕКЦИЯ ДАННЫХ «СПИСОК» ............................................................. 17 
   2.1. Добавление данных ...................................................................................... 19 
   2.2. Добавление данных в произвольную позицию ......................................... 20 
   2.3. Удаление данных ......................................................................................... 21 
   2.4. Операции поиска данных ............................................................................ 22 
   2.5. Итератор ....................................................................................................... 23 
   2.6. Очереди ......................................................................................................... 32 
3. ДВОИЧНОЕ ДЕРЕВО ПОИСКА ..................................................................... 35 
   3.1. Добавление данных в бинарное дерево ..................................................... 38 
   3.2. Удаление элемента дерева .......................................................................... 45 
   3.3. Операции поиска в дереве ........................................................................... 47 
   3.4. Итератор бинарного дерева ......................................................................... 54 
   3.5. Практические рекомендации при реализации бинарного дерева ............ 56 
4. ПРАКТИЧЕСКИЕ ЗАДАНИЯ .......................................................................... 58 
   4.1. Общие требования ....................................................................................... 58 
   4.2. Коллекция «Вектор» .................................................................................... 60 
   4.3. Коллекция «Список» ................................................................................... 61 
   4.4. Коллекция «Дерево» .................................................................................... 61 
Библиографический список .................................................................................. 63 
 
 
 


 
 
 
 
 
 
ÂÂÅÄÅÍÈÅ 
 
Процесс передачи данных неразрывно связан не только с необходимостью представления данных в удобном для передачи виде, но 
и с необходимостью формирования буферных очередей для хранения 
данных, ожидающих отправки в канал связи или последующей обработки. Может также возникнуть задача поиска необходимых для отправки данных в некотором исходном множестве. Организация процесса хранения данных неразрывно связана с разработкой любого программного обеспечения. Следует отметить, что от способа представления данных зачастую зависят производительность и нюансы практической реализации того или иного алгоритма. Иногда выбранный способ 
представления данных может определять способ практической реализации алгоритма, и наоборот: способ практической реализации может 
определять необходимый способ представления данных. В настоящем 
учебном пособии будут рассмотрены такие способы (структуры данных, коллекции) хранения данных, как «вектор», структура на базе 
списка и «дерево». Применение перечисленных коллекций можно увидеть практически в любом существующем программном обеспечении. 
Демонстрация примеров реализации рассматриваемых алгоритмов 
будет осуществляться при помощи Си-подобного псевдокода. Следует 
учитывать, что в ряде случаев бездумное копирование псевдокода может привести к ошибкам при компиляции, а затем, после их исправления, к появлению исключений, вызванных ошибочным обращением 
к памяти. 
 
 
 
 
 


 
 
 
 
 
 
1. ÊÎËËÅÊÖÈß ÄÀÍÍÛÕ «ÂÅÊÒÎл 
В ряде задач возникает необходимость сохранения данных таким образом, чтобы была возможность быстрого чтения и замены данных по 
их индексу. Такую возможность предоставляет обыкновенный одномерный массив, который обычно представлен в виде указателя на его 
начало: T *pArray. Тип Т – это тип данных, которые хранит массив; примем это обозначение и далее. Возможность быстрого доступа по индексу достигается за счет того, что массив лежит в памяти в виде единого фрагмента. Следует также отметить, что в результате такого способа размещения в памяти время доступа к любому элементу массива 
будет одинаковым. Строго говоря, термины «быстрый доступ» и «одинаковое время доступа» не совсем корректные. Понятие «быстрый» потребует уточнения, по отношению к чему доступ является быстрым, 
а время доступа не может быть одинаковым в случае применения многозадачной операционной системы реального времени, в которой происходят регулярные переключения между выполняемыми процессами. 
Правильно будет сказать, что операция доступа к любому элементу массива имеет равную константную трудоемкость. 
Однако применение простого массива на практике зачастую сопровождается некоторыми трудностями. В результате это оборачивается 
дополнительными накладными расходами в виде увеличения количества переменных и программного кода, которые не относятся к решению требуемой задачи. Поясним появление таких накладных расходов 
на простом примере. Забегая вперед, следует сказать, что накладные 
расходы в любом случае останутся, но их можно несколько сократить. 
Пусть в процессе работы некоторого алгоритма требуется сохранять 
данные. Для этого объявляется переменная-указатель и используется 
оператор new или функция calloc. При этом одной переменной-указателя нам будет явно недостаточно, потому что адрес, хранимый в этой 


переменной, указывает только на первую ячейку массива. Конечно, для 
доступа к остальным ячейкам указатель можно сдвинуть и использовать 
операцию разыменования, но если не запомнить, сколько сдвигов было 
сделано, то произойдет потеря начального адреса массива. Как следствие, это приведет к утечке памяти и потере данных. Чтобы избежать 
такой ситуации, придется завести переменную-индекс, которая будет 
увеличиваться при добавлении данных в массив, т. е. доступ к массиву 
будет осуществлен строчкой вида pArray[index] или *(pArray + index). 
Кроме этого, неплохо бы иметь данные о размере массива и количестве 
свободного места1. Таким образом, в качестве накладных расходов будут как минимум две дополнительные переменные – переменная-индекс 
и переменная, хранящая размер массива. Наличие таких переменных потребует от программиста некоторой внимательности, чтобы исключить 
несанкционированное изменение значений этих переменных. Кроме 
того, в случае если объем добавляемых в массив данных заранее неизвестен, рано или поздно возникнет ситуация, при которой свободное место в массиве закончится. Разумеется, в этом случае можно использовать оператор realloc или выполнить перераспределение памяти вручную. Однако и это приведет к накладным расходам в виде усложнения 
программного кода основного алгоритма. Следует также отметить, что 
реализация такого механизма внутри алгоритма уже не сможет быть использована в другой точке программы с другим типом данных. Помимо 
этого, к накладным расходам, разумеется, следует отнести сами операции перераспределения памяти и проверки на наличие свободного места 
в массиве, но от этих расходов при использовании массива никак не 
уйти. 
Однако при этом всё же остается возможность «спрятать» рассмотренные операции и унифицировать их для произвольного типа данных. 
Одним из способов является разработка шаблонного класса, приватными членами которого будут являться следующие: 
1) указатель на массив (pArray); 
2) переменная индекс (nIndex); 
3) переменная, которая хранит текущий размер массива (nSize). 
 
                                                     
1 Разумеется, внимательный читатель предложит использовать статический 
массив и оператор sizeof. Однако применение статического массива приведет 
к полному отсутствию возможности изменения размера массива. 


Публичными методами такого класса могут быть следующие: 
1) добавление элемента в массив (PushBack (data)); 
2) получение ссылки на элемент массива по его индексу (T& operator[index], T& at(index)); 
3) запрос количества элементов в массиве (INT size()); 
4) проверка на пустоту (BOOL IsEmpty()); 
5) очистка коллекции. 
Применяются и другие методы, например резервирование места 
в массиве. Рассмотрим алгоритм добавления элемента в конец коллекции (конец массива). На рис. 1 изображено схематичное представление 
массива. 
 
Рис. 1. Схематичное представление  
коллекции «Вектор» 
Пустой массив (рис. 1) состоит из четырех ячеек. Указатель pArray 
содержит адрес первой ячейки, а переменная nIndex имеет нулевое значение. Добавление нового элемента в массив будет выполнено операцией pArray[nIndex] или путем разыменования (pArray + nIndex), после чего будет осуществлен инкремент переменной nIndex. Схематичное изображение состояния массива после выполнения четырех операций добавления элемента показано на рис. 2. 
 
Рис. 2. Схематичное представление коллекции 
 после добавления четырех элементов 


Доступ онлайн
500 ₽
В корзину