Введение в коллекции хранения данных
Покупка
Основная коллекция
Тематика:
Программирование на C и C++
Издательство:
Новосибирский государственный технический университет
Автор:
Катасонов Денис Николаевич
Год издания: 2023
Кол-во страниц: 64
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-7782-4965-3
Артикул: 875936.01.99
В учебном пособии изложен теоретический материал, который применяется при решении задач хранения и обработки данных в системах кодирования и передачи информации, а также при решении аналогичных задач во время разработки программного обеспечения высокого уровня. Приведено описание трех практических заданий, в ходе выполнения которых можно получить навыки программирования коллекций данных.
Учебное пособие предназначено студентам III курса АВТФ направления 27.03.04 «Управление в технических системах», а также может быть полезно всем интересующимся вопросами программирования на языке C++.
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Министерство науки и высшего образования Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Д. Н. КАТАСОНОВ ВВЕДЕНИЕ В КОЛЛЕКЦИИ ХРАНЕНИЯ ДАННЫХ Утверждено Редакционно-издательским советом университета в качестве учебного пособия НОВОСИБИРСК 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. Схематичное представление коллекции после добавления четырех элементов