Статическое и динамическое выделение памяти

Статическое и динамическое выделение памяти

Недостатки:

ü работа в динамической памяти увеличивает время работы программы;

ü алгоритмы для динамических структур обычно более сложны, трудны для отладки по сравнению с аналогичными алгоритмами для статических данных;

ü существуют алгоритмы, реализация которых более эффективна на обычных данных (например, в ряде задач индекс элемента в массиве можно просто вычислять, в то время как использование списковых структур потребует обхода списка).

Достоинства:

ü большая экономия памяти;

ü ряд алгоритмов более эффективен при реализации их с использованием динамических структур (например, вставка элемента в массив на определенное место потребует перемещения части элементов массива, а при вставке в середину списка – нескольких операторов присваивания).

Указатель(другое название – ссылка)– это переменная, содержащая адрес, по которому хранится некоторое значение.

Помимо адреса, указатель может содержать специальное значение nil. Такой указатель называется пустым.

Следует различать случаи, когда значение ссылки не определено и когда значение ссылки является nil. Значение nil не является адресом какой-либо переменной, однако его можно сравнивать с любым другим адресом. Это позволяет распознавать указатели, которые, в некоторый момент выполнения программы, не ссылаются ни на какую переменную.

Описание указателей

В языке Pascal для обозначения типа указателей используется знак ^:

Type

имя_типа = ^тип;

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

Примеры:

Type

uk_real = ^real;

uk_z=^z;

z=record

inf: integer;

adr: uk_z;

end;

Var

p : uk_real; // указатель на значение типа real

q : uk_z; // указатель на значение типа z (запись)

r : ^boolean; // указатель на значение типа boolean

Динамические структуры

Стеком называется динамическая структура данных, у которой в каждый момент времени доступен только верхний (последний) элемент.

Очередью называется динамическая структура, у которой в каждый момент времени доступны два элемента: первый и последний. Из начала очереди элементы можно удалять, а к концу — добавлять.

Дек (deque — Double-Ended QUEue — двухконцевая очередь) – усложнённая очередь. В каждый момент времени у дека доступны как первый, так и последний элемент, причём добавлять и удалять элементы можно и в начале, и в конце дека. Таким образом, дек — это симметричная двусторонняя очередь. Реализация дека при помощи массива ничем не отличается от реализации обычной очереди, а вот в терминах списков дек удобнее представлять двусвязным линейным списком.

Списком будем называть некоторую последовательность элементов, связанных посредством указателей. В списке элементы связаны друг с другом логически. Логический порядок следования элементов списка определяется с помощью указателей и может не совпадать с физическим порядком их расположения в памяти. Каждый элемент списка состоит из двух частей. Первая часть содержит непосредственно данные, принадлежащие элементу, и является информационной. Вторая часть содержит указатель и является справочной. Указатель определяет место элемента в списке. На рисунке 1 показана общая идея представления списка, состоящего из 5-ти элементов. Стрелка обозначает указатель.

Эл. 1 Эл. 2 Эл. 3 Эл 4 Эл. 5

Рис. 1

Указатель первого элемента определяет место (адрес, индекс) следующего элемента списка. Отсутствие указателя (пустой указатель или 0 на месте указателя) означает, что данный элемент последний в списке.

Элементы в списке могут быть связаны различным образом:

· однонаправленные списки – это списки, в которых для каждого элемента указатель задает место положения только следующего элемента (см. рисунок 1) или только предыдущего (см. рисунок 2).

Эл. 1 Эл. 2 Эл. 3 Эл 4 Эл. 5

Рис. 2

· двунаправленные списки – это списки, в которых для каждого элемента задаются два указателя, которые определяют место положения, как следующего, так и предыдущего элемента (см. рисунок 3).

Эл. 1 Эл. 2 Эл. 3 Эл 4 Эл. 5

Рис. 3

Списки также бывают линейными (это все ранее приведенные рисунки) и кольцевыми(см. рисунки ниже).

Эл. 1 Эл. 2 Эл. 3 Эл 4 Эл. 5

Рис. 4

Эл. 1 Эл. 2 Эл. 3 Эл 4 Эл. 5

Рис. 5

Эл. 1 Эл. 2 Эл. 3 Эл 4 Эл. 5

Рис. 6

ЗАМЕЧАНИЯ:

ü стек и очередь лучше реализовывать на массиве;

ü дек лучше представлять двунаправленным списком;

ü при поиске чего-либо в массиве, файле, списке первое условие должно проверять существование элемента, с которым будем работать, а потом всё остальное;

ü при работе с массивом, списком надо всегда думать о трёх вариантах: как работать с началом, как работать с серединой, как работать с концом.

Операции над списками:

· Создание списка;

· Вывод элементов списка;

· Поиск нужного элемента в списке;

· Вставка элемента в список (в начало списка, в произвольное место списка);

· Удаление элемента из списка (из начала списка, из произвольного места списка);

· Проверка, пуст ли список;

· Очистка списка.

Type

Uk=^z;

Z=record

inf: integer;

adr: uk;

end;

Var

adrn, adrt : uk;

i, n : byte;

Begin

readln (n); {задаем количество элементов списка}

new(adrt); {выделяем память под 1-ый элемент списка и присваиваем адрес переменной-указателю adrt }

adrn:=adrt; {запоминаем адрес 1-ого элемента списка}

for i:=1 to n-1 do

begin

readln(adrt^.inf); {считываем значение элемента списка и заносим в информационную часть}

new(adrt^.adr); {выделяем память под следующий элемент списка и вносим адрес этого элемента в адресную часть}

adrt:= adrt^.adr {с помощью переменной-указателя adrt запоминаем адрес для следующего элемента списка}

end;

readln(adrt^.inf); {считываем значение последнего элемента списка и заносим в информационную часть }

adrt^.adr:=nil; {в адресную часть последнего элемента внесли значение nil}

writeln(‘Элементы списка:’);

adrt:=adrn; {указываем в качестве адреса текущего элемента списка адрес 1-ого элемента}

while adrt<>nil do {пока в адрес текущего элемента не nil делать}

begin

write(adrt^.inf, ’ ‘); {выводим информационную часть текущего элемента списка}

adrt:=adrt^.adr; {запоминаем адрес следующего элемента списка}

end;

End.

Статическое и динамическое выделение памяти

Недостатки:

ü работа в динамической памяти увеличивает время работы программы;

ü алгоритмы для динамических структур обычно более сложны, трудны для отладки по сравнению с аналогичными алгоритмами для статических данных;

ü существуют алгоритмы, реализация которых более эффективна на обычных данных (например, в ряде задач индекс элемента в массиве можно просто вычислять, в то время как использование списковых структур потребует обхода списка).

Достоинства:

ü большая экономия памяти;

ü ряд алгоритмов более эффективен при реализации их с использованием динамических структур (например, вставка элемента в массив на определенное место потребует перемещения части элементов массива, а при вставке в середину списка – нескольких операторов присваивания).

Указатель(другое название – ссылка)– это переменная, содержащая адрес, по которому хранится некоторое значение.

Помимо адреса, указатель может содержать специальное значение nil. Такой указатель называется пустым.

Следует различать случаи, когда значение ссылки не определено и когда значение ссылки является nil. Значение nil не является адресом какой-либо переменной, однако его можно сравнивать с любым другим адресом. Это позволяет распознавать указатели, которые, в некоторый момент выполнения программы, не ссылаются ни на какую переменную.

Описание указателей

В языке Pascal для обозначения типа указателей используется знак ^:

Type

имя_типа = ^тип;

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

Примеры:

Type

uk_real = ^real;

uk_z=^z;

z=record

inf: integer;

adr: uk_z;

end;

Var

p : uk_real; // указатель на значение типа real

q : uk_z; // указатель на значение типа z (запись)

r : ^boolean; // указатель на значение типа boolean

Динамические структуры

Стеком называется динамическая структура данных, у которой в каждый момент времени доступен только верхний (последний) элемент.

Очередью называется динамическая структура, у которой в каждый момент времени доступны два элемента: первый и последний. Из начала очереди элементы можно удалять, а к концу — добавлять.

Дек (deque — Double-Ended QUEue — двухконцевая очередь) – усложнённая очередь. В каждый момент времени у дека доступны как первый, так и последний элемент, причём добавлять и удалять элементы можно и в начале, и в конце дека. Таким образом, дек — это симметричная двусторонняя очередь. Реализация дека при помощи массива ничем не отличается от реализации обычной очереди, а вот в терминах списков дек удобнее представлять двусвязным линейным списком.

Списком будем называть некоторую последовательность элементов, связанных посредством указателей. В списке элементы связаны друг с другом логически. Логический порядок следования элементов списка определяется с помощью указателей и может не совпадать с физическим порядком их расположения в памяти. Каждый элемент списка состоит из двух частей. Первая часть содержит непосредственно данные, принадлежащие элементу, и является информационной. Вторая часть содержит указатель и является справочной. Указатель определяет место элемента в списке. На рисунке 1 показана общая идея представления списка, состоящего из 5-ти элементов. Стрелка обозначает указатель.

Эл. 1 Эл. 2 Эл. 3 Эл 4 Эл. 5

Рис. 1

Указатель первого элемента определяет место (адрес, индекс) следующего элемента списка. Отсутствие указателя (пустой указатель или 0 на месте указателя) означает, что данный элемент последний в списке.

Элементы в списке могут быть связаны различным образом:

· однонаправленные списки – это списки, в которых для каждого элемента указатель задает место положения только следующего элемента (см. рисунок 1) или только предыдущего (см. рисунок 2).

Эл. 1 Эл. 2 Эл. 3 Эл 4 Эл. 5

Рис. 2

· двунаправленные списки – это списки, в которых для каждого элемента задаются два указателя, которые определяют место положения, как следующего, так и предыдущего элемента (см. рисунок 3).

Эл. 1 Эл. 2 Эл. 3 Эл 4 Эл. 5

Рис. 3

Списки также бывают линейными (это все ранее приведенные рисунки) и кольцевыми(см. рисунки ниже).

Эл. 1 Эл. 2 Эл. 3 Эл 4 Эл. 5

Рис. 4

Эл. 1 Эл. 2 Эл. 3 Эл 4 Эл. 5

Рис. 5

Эл. 1 Эл. 2 Эл. 3 Эл 4 Эл. 5

Рис. 6

ЗАМЕЧАНИЯ:

ü стек и очередь лучше реализовывать на массиве;

ü дек лучше представлять двунаправленным списком;

ü при поиске чего-либо в массиве, файле, списке первое условие должно проверять существование элемента, с которым будем работать, а потом всё остальное;

ü при работе с массивом, списком надо всегда думать о трёх вариантах: как работать с началом, как работать с серединой, как работать с концом.

Операции над списками:

· Создание списка;

· Вывод элементов списка;

· Поиск нужного элемента в списке;

· Вставка элемента в список (в начало списка, в произвольное место списка);

· Удаление элемента из списка (из начала списка, из произвольного места списка);

· Проверка, пуст ли список;

· Очистка списка.