Навигация
Динамические структуры данных
61871
знак
4
таблицы
0
изображений
7. Динамические структуры данных
В этой главе автор рассматривает совершенно иной способ хранения данных в памяти. 7.1 Динамическое управление памятьюДо сих пор речь шла только об объектах данных, для которых компилятор C предоставляет память и ее количество и величина должны быть определены к началу перевода программы в машинные коды. Такие объекты называют статическими.
Работать с ними не всегда удобно, так как в процессе выполнения программы возникает необходимость увеличить размеры памяти, выделенной для этой структуры. Для борьбы с этим необходимо определять такие объекты с максимальной величиной.
Наиболее приемлемым решением здесь будет применение динамически распределяемой памяти, т.е. определять объекты во время действия, т.е. динамично. Это решение позволяет оперативно освобождать большое количество памяти и избегать ее переполнения или напрасного расходования при статическом распределении.
Динамические объекты определяются несколько по-другому. К ним обращаются не по имени, а только по их адресу. Эта адресация возникает при распределении памяти и назначается обычно с помощью переменных-указателей. Динамическое распределение памяти происходит посредством стандартных функций языка Cи:
· void *malloc (size_t size) – занимает определенную связную область памяти и поставляет из нее начальный адрес.
· void *calloc (size_t nobj, size_t size) – возвращает начальный адрес большой области; содержание этой области инициализируется значением 0.
· void * realloc (void *ptr, size_t size) - изменение величины размещения блока памяти.
· void free(void *) – используется для освобождения области памяти, которая больше не используется.
· size_t sizeof (something) – определяет длину аргумента.
При использовании указателей, которые служат в качестве значений, возвращаемых функцией, нужно следить, чтобы они не указывали на локальные объекты, которые исчезают после работы функции.
7.2 Динамические структуры данныхДинамические структуры данных, как поясняет Юрген Плате в следующих параграфах, изменяют свою структуру и занятое ими пространство памяти во время выполнения программы. Они формируются из отдельных элементов, так называемых 'узлов', между которыми существуют определенные взаимосвязи. Речь в основном при этом идет о структурах, которые обозначаются как 'списки' или 'деревья'.
Отношение отдельных узлов выстраиваются следующим образом: указатель одного узла указывает на место памяти «соседа». Самыми важными из этих структур данных являются:
· Линейные списки - простые цепочные списки, двойные цепочные списки, специальные формы, буфер(FIFO), стек(LIFO).
· Деревья - Бинарные деревья – 2 соседа, многодорожные деревья - больше чем 2 соседа.
· Общие графы
Линейные списки используют элементы, в которых указаны связанные сведения в форме строки символов. Элементы списков можно представить наглядно следующим образом:
| Информация элементов списка (строки символов, например, имя) | Указатель на следующий элемент |
При построении цепочного списка отдельные элементы списка выстраиваются в определенном порядке друг за другом:
где символ электрической массы в конце списка указывает на NULL-указатель, который показывает конец списка, а root - указатель, показывающий происхождение списка (как правило, глобальная переменная)
Еще одна важная динамическая структура, о которой рассказывает автор в этой главе – древовидная. Древовидные структуры играют очень важную роль в организации данных. Их используют в следующих случаях:
· при построении родословного дерева;
· как организационная структура предприятия
· при распределении текста по главам, разделам, абзацам и т.д.
Дерево определяется следующим образом:
· Древовидные структуры имеют разветвления, которые могут исходить из начального элемента структуры и из самих разветвлений до тех пор, пока конечных точек не достигнут.
· Элементы дерева называют узлами, причем начальный элемент называется корневым узлом, а конечные точки – листами.
· Линии соединения двух узлов называется ребрами. Последовательность ребер от корня до любого узла называется путем.
· Узлы, которые одинаково удалены от корня образуют уровень дерева. Общее число уровней указывает глубину дерева.
· Максимальное количество наследников, которые имеет узел, определяют степень дерева. Дерево степени 2 - это бинарное дерево, наиболее важный случай.
Древовидная структура имеет рекурсивную природу, так как наследники узла соответственно могут пониматься как корни деревьев. Бинарное дерево можно изобразить следующим образом:
Таким образом, динамические структуры данных, как показывает автор, являются наиболее эффективным способом распределения оперативной памяти и соответственно необходимо их использовать в программе, применяя указатели.
Похожие работы
... , которая определяет последовательность действий над некоторыми объектами и после конечного числа шагов приводит к по лучению требуемого результата. ЭВМ — исполнитель алгоритмов. Обсуждение методических вопросов изучения темы «Алгоритмы работы с величинами» буде проводить в программистском аспекте. Составление любой программы для ЭВМ начинается с построения алгоритма. Как известно, всякий ...
... профессором Н. Виртом, язык назван в честь французского математика и по замыслу автора предназначался для обучения программированию. Однако язык получился на столько удачным, что стал одним из основных инструментов прикладных и системных программистов при решении задач вычислительного и информационно-логического характера. В 1979 году был подготовлен проект описания языка – Британский стандарт ...
... для диалогового стиля разработки программ, когда отдельные части программы можно написать, проверить и выполнить в ходе создания программы, не отключая интерпретатора. По набору входных языков различают системы программирования одно- и многоязыковые. Отличительная черта многоязыковых систем состоит в том, что отдельные части программы можно составлять на разных языках и помощью специальных ...
... процедуры и функция (программирование) функции макросы * глобальная переменная глобальные переменные * класс программирование классы * Обобщённое программирование шаблоны Обычно стандартная библиотека содержит основные алгоритмы и структуры данных, необходимые для: * работы с динамически распределяемая память динамической памятью * файловыми операциями ввода-вывода * операциями ввода- ...
0 комментариев