Тема: Динамические структуры данных Организация данных в списковые структуры. Учебная работа № 431206

Учебная работа № 431206. Тема: Динамические структуры данных Организация данных в списковые структуры

Выдержка из похожей работы

…….

Динамические структуры данных: списки

…..чания программы, то занятую ими память можно освободить для
другой информации. В-третьих, использование динамической памяти позволяет
создавать структуры данных переменного размера.
Работа
с динамическими величинами связана с использованием еще одного типа данных —
ссылочного типа. Величины, имеющие ссылочный тип, называют указателями.
Указатель
содержит адрес поля в динамической памяти, хранящего величину определенного
типа. Сам указатель располагается в статической памяти.
Адрес
величины — это номер первого байта поля памяти, в котором располагается
величина. Размер поля однозначно определяется типом.
Далее
будем более подробно обсуждать указатели и действия с ними в языке Pascal,
примеры будем приводить на Pascal и C.
Величина
ссылочного типа (указатель) описывается в разделе описания переменных следующим
образом:
 Var
<идентификатор> : ^<имя типа>;
Вот
примеры описания указателей:
Type Mas1 = Array[1..100] Of Integer;
Var  P1 : ^Integer;
 P2 : ^String;
 Pm : ^Mas1;
Здесь
P1 — указатель на динамическую величину целого типа; P2 — указатель на
динамическую величину строкового типа; Pm — указатель на динамический массив,
тип которого задан в разделе Type.
Сами
динамические величины не требуют описания в программе, поскольку во время
компиляции память под них не выделяется. Во время компиляции память выделяется
только под статические величины. Указатели — это статические величины, поэтому
они требуют описания.
Каким
же образом происходит выделение памяти под динамическую величину? Память под
динамическую величину, связанную с указателем, выделяется в результате
выполнения стандартной процедуры NEW. Формат обращения к этой процедуре:
 NEW(<указатель>);
Считается,
что после выполнения этого оператора создана динамическая величина, имя которой
имеет следующий вид:
 <имя динамической величины> := <указатель>^
Пусть
в программе, в которой имеется приведенное выше описание, присутствуют
следующие операторы:
 NEW(P1); NEW(P2); NEW(Pm);
После
их выполнения в динамической памяти оказывается выделенным место под три
величины (две скалярные и один массив), которые имеют идентификаторы:
P1^,
P2^, Pm^
Например,
обозначение P1^ можно расшифровать так: динамическая переменная, на которую
ссылается указатель P1.
Дальнейшая
работа с динамическими переменными происходит точно так же, как со статическими
переменными соответствующих типов. Им можно присваивать значения, их можно
использовать в качестве операндов в выражениях, параметров подпрограмм и пр.
Например, если переменной P1^ нужно присвоить число 25, переменной P2^
присвоить значение символа “Write”, а массив Pm^ заполнить по порядку
целыми числами от 1 до 100, то это делается так:
 P1^ := 25;
 P2^ := ‘Write’;
 For I := 1 To 100 Do Pm^[I] := I;
Кроме
процедуры NEW значение указателя может определяться оператором присваивания:
 <указатель>
:= <ссылочное выражение>;
В
качестве ссылочного выражения можно использовать
указатель;
ссылочную
функцию (т.е. функцию, значением которой является указатель);
константу
Nil.
Nil
— это зарезервированная константа, обозначающая пустую ссылку, т.е. ссылку,
которая ни на что не указывает. При присваивании базовые типы указателя и
ссылочного выражения должны быть одинаковы. Константу Nil можно присваивать
указателю с любым базовым типом.
До
присваивания значения ссылочной переменной (с помощью оператора присваивания
или процедуры NEW) она является неопределенной.
Ввод
и вывод указателей не допускается.
Рассм…