Войти на сайт

или
Регистрация

Навигация


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 - это бинарное дерево, наиболее важный случай.

Древовидная структура имеет рекурсивную природу, так как наследники узла соответственно могут пониматься как корни деревьев. Бинарное дерево можно изобразить следующим образом:

 

Таким образом, динамические структуры данных, как показывает автор, являются наиболее эффективным способом распределения оперативной памяти и соответственно необходимо их использовать в программе, применяя указатели.



Информация о работе «Алгоритмы и структуры данных. Программирование в Cи»
Раздел: Информатика, программирование
Количество знаков с пробелами: 61871
Количество таблиц: 4
Количество изображений: 0

Похожие работы

Скачать
29246
1
2

... , которая определяет последовательность действий над некоторыми объектами и после конечного числа шагов приводит к по лучению требуемого результата. ЭВМ — исполнитель алгоритмов. Обсуждение методических вопросов изучения темы «Алгоритмы работы с величинами» буде проводить в программистском аспекте. Составление любой программы для ЭВМ начинается с построения алгоритма. Как известно, всякий ...

Скачать
29193
3
0

... профессором Н. Виртом, язык назван в честь французского математика и по замыслу автора предназначался для обучения программированию. Однако язык получился на столько удачным, что стал одним из основных инструментов прикладных и системных программистов при решении задач вычислительного и информационно-логического характера. В 1979 году был подготовлен проект описания языка – Британский стандарт ...

Скачать
17900
0
0

... для диалогового стиля разработки программ, когда отдельные части программы можно написать, проверить и выполнить в ходе создания программы, не отключая интерпретатора. По набору входных языков различают системы программирования одно- и многоязыковые. Отличительная черта многоязыковых систем состоит в том, что отдельные части программы можно составлять на разных языках и помощью специальных ...

Скачать
9572
0
0

... процедуры и функция (программирование) функции макросы * глобальная переменная глобальные переменные * класс программирование классы * Обобщённое программирование шаблоны Обычно стандартная библиотека содержит основные алгоритмы и структуры данных, необходимые для: * работы с динамически распределяемая память динамической памятью * файловыми операциями ввода-вывода * операциями ввода- ...

0 комментариев


Наверх