Динамические структуры данных паскаль
Программирование и базы данных
Ещё один сайт сети «Информационная база»
Primary menu
Post navigation
Pascal Динамические структуры данных
Линейные
списки, изучение основных операций
Списком называется структура данных, каждый элемент
которой посредством указателя связывается со следующим элементом. Из
определения следует, что каждый элемент списка содержит как минимуму
одно поле данных (назовем его data
и для простоты считаем его типа Integer ),
оно может иметь сложную структуру, и поле ссылки на следующий элемент
(назовем его next ). Поле ссылки
последнего элемента списка имеет значение Nil .
Указатель на начало списка (первый элемент) является значением отдельной
переменной. Пример списка, содержащего в поле данных целые числа 3. 5,
1, 9, приведен на рисунке.
Описание элемента списка, используемого в течение данного понятия, имеет
вид:
Основн ые операции с элементами списка:
просмотр элементов списка;
вставка элементов в список;
удаление элемента из списка;
Просмотр элементов списка, если он создан,
очевидная процедура.
Ее рекурсивная реализация:
Измените ее так, чтобы элементы списка выводились, начиная с последнего.
Вставка элемента в список возможна логически в его начало, конец и
середину. Разберем эти случаи. Вставка в начало имеет вид:
Procedure Ins_begin(Var first:pt;
el:Integer);
« Кра сными »
отрезками на рисунке выделены действия, выполняемые в процедуре. С
помощью цифр на рисунке и в тексте процедуры показаны действия
соответствующих операторов.
Вставка в конец списка осуществляется с
помощью следующей процедуры. Вопрос о том, каким образом значением
указателя last стал адрес последнего элемента
списка, пока оставим открытым.
Procedure
Ins_end(Var last:pt; el:Integer);
Вставку в средину списка проиллюстрируем очередным рисунком.
Очевидно, что для вставки элемента в список необходимо знать, как
минимум, адрес предшествующего элемента списка, т. е. элемента, после
которого осуществляется вставка. И мы считаем, что этот элемент не
последний. При вставке разрывается существующая связь (отмечена
«крестиком») и появляются две новые связи, выделенные на рисунке
«жирными» отрезками.
Пусть мы создаем упорядоченный по неубыванию список элементов
(информационная часть любого элемента списка меньше информационных
частей следующих за ним элементов списка или равна им). Для того, чтобы
найти место для вставки очередного элемента (значение указателя рх на
рисунке), следует просматривать элементы списка до тех пор, пока
вставляемый элемент больше информационной части текущего элемента.
Procedure
Ins_med(Var first:pt; el:Integer);
И наконец, общая логика вставки элемента в упорядоченный список.
Создаваемый список отличается от декларированного в начале тем, что он
описывается двумя указателями: на первый и последний элементы списка.
Procedure
Ins(Var first,last:pt; el:Integer);
If eKfirst».data Then
Ins_begin(first,el) Else
If el>last».data Then
Ins_end(last,el) Else Ins_med (first,el);
Ввод исходных данных при создании упорядоченного списка осуществляется с
клавиатуры. Напомним, что признак конца файла (Eof = True) в этом случае
вырабатывается при нажатии клавиш Ctrl+Z. Все действия по организации
ввода представлены в процедуре Solve.
Procedure
Solve(Var first,last:pt);
лабы по информатике, егэ
лабораторные работы и задачи по программированию и информатике, егэ по информатике
Занятие №15. Часть 2: Динамические структуры данных: стеки и очереди
Стеки
Стек — динамическая структура данных, в которой добавление и удаление элементов доступно только с одного конца (с верхнего (последнего) элемента).
Существуют такие сокращения:
Последовательные этапы засылки в стек чисел 1, 2, 3
Над стеком выполняются следующие операции:
- добавление в стек нового элемента;
- определение пуст ли стек;
- доступ к последнему включенному элементу, вершине стека;
- исключение из стека последнего включенного элемента.
Создание структуры узла:
Добавление элемента в стек:
procedure Push( var Head: PNode; x: char); var NewNode: PNode; begin New(NewNode); < выделение памяти >NewNode^.data := x; < запись символа >NewNode^.next := Head; < сделать первым узлом >Head := NewNode; end;
Забор элемента с вершины:
function Pop ( var Head: PNode ): char; var q: PNode; begin if Head = nil then begin < если стек пустой >Result := char(255); < неиспользуемый символ, т.е. ошибка >Exit; end; Result := Head^.data; < берем верхний символ >q := Head; < запоминаем вершину >Head := Head^.next; < удаляем вершину >Dispose(q); < удаление из памяти >end;
Проверка, пустой ли стек:
function isEmptyStack ( S: Stack ): Boolean; begin Result := (S = nil); end;
Объявления в основной программе:
var S: PNode; . S := nil;
Рассмотрим подробную работу со стеком на примере:
Алгоритм выполнения задания:
- изначально стек пустой;
- в цикле просматриваем каждый символ строки;
- если текущий символ – открывающая угловая скобка, то вставляем ее на вершину стека;
- если текущий символ – закрывающая угловая скобка, то проверяем верхний элемент стека: там должна находиться открывающая угловая скобка (иначе — ошибка);
- в конце стек должен стать пустым, иначе — ошибка.
Создаем структуру стека:
const MAXSIZE = 50; type Stack = record < стек рассчитан на 50 символов >tags: array[1..MAXSIZE] of char; size: integer; < число элементов >end;
Процедура добавления элемента в стек:
procedure Push( var S: Stack; x: char); begin if S.size = MAXSIZE then Exit; // выход, если произошло переполнение стека S.size := S.size + 1; S.tags[S.size] := x; // добавляем элемент end;
Функция взятия элемента с вершины:
function Pop ( var S:Stack ): char; begin if S.size = 0 then begin Result := char(255); // 255 — пустой символ, ошибка — стек пуст Exit; end; Result := S.tags[S.size]; S.size := S.size — 1; end;
Создаем функцию для проверки, пустой ли стек:
function isEmptyStack ( S: Stack ): Boolean; begin Result := (S.size = 0); end;
var expr: string; br1, br2: char; < угловые скобки >i, k: integer; upper: char; < верхний символ, снятый со стека >error: Boolean; < признак ошибки >S: Stack; begin br1 := ‘ ‘; S.size := 0; error := False; writeln(‘Введите html-текст’); readln(expr); . < здесь вставляется цикл с обработкой строки >if not error and isEmptyStack(S) then writeln(‘Текст верный.’) else writeln(‘Текст составлен неверно.’) end.
Обработка строки в цикле:
for i:=1 to length(expr) < проходимся по всем символам строки expr >do begin if expr[i] = br1 then begin < открывающая скобка br1; < ошибка: стек пуст или не та скобка >break; end; if error then break; // была ошибка, значит, прерываем цикл end;
Очереди
Очередь — динамическая структура данных, у которой в каждый момент времени доступны только два элемента: первый и последний. Добавление элементов возможно только с одного конца (конца очереди), а удаление элементов – только с другого конца (начала очереди).
Существует сокращение для очереди: FIFO = First In – First Out, с английского — «Кто первым вошел, тот первым вышел».
Для очереди доступны следующие операции:
- добавить элемент в конец очереди (PushTail);
- удалить элемент с начала очереди (Pop).
Работа с очередью обычным массивом:
Это достаточно простой способ, который подразумевает два неблагоприятных момента: заблаговременное выделение массива, сдвиг элементов при удалении из очереди. 
Работа с очередью с помощью кольцевого массива:
Если в очереди 1 элемент: 
Если очередь пуста: 
Если очередь заполнена: 
Определение размера массива (при пустой и заполненной очереди): 
Очередь в Паскале (использование кольцевого массива)
Создание структуры: 
type Queue = record data: array[1..MAXSIZE] of integer; head, tail: integer; end;
Как добавить в очередь: 
procedure PushTail( var Q: Queue; x: integer); begin if Q.head = (Q.tail+1) mod MAXSIZE + 1 then Exit; < очередь уже полна >Q.tail := Q.tail mod MAXSIZE + 1; Q.data[Q.tail] := x; end;
Как выбрать из очереди: 
function Pop ( var S: Queue ): integer; begin if Q.head = Q.tail mod MAXSIZE + 1 then begin Result := MaxInt; Exit; end; Result := Q.data[Q.head]; Q.head := Q.head mod MAXSIZE + 1; end;
Создание очереди посредством списка
Объявление узла: 
type PNode = ^Node; Node = record data: integer; next: PNode; end; type Queue = record head, tail: PNode; end;
Добавляем новый элемент: 
procedure PushTail( var Q: Queue; x: integer ); var NewNode: PNode; begin New(NewNode); NewNode^.data := x; NewNode^.next := nil; if Q.tail <> nil then Q.tail^.next := NewNode; Q.tail := NewNode; if Q.head = nil then Q.head := Q.tail; end;
Выбираем элемент из списка: 
function Pop ( var S: Queue ): integer; var top: PNode; begin if Q.head = nil then begin Result := MaxInt; Exit; end; top := Q.head; Result := top^.data; Q.head := top^.next; if Q.head = nil then Q.tail := nil; Dispose(top); end;
Дек — англ. double ended queue, т.е. очередь с двумя концами – это динамическая структура данных, добавлять и удалять элементы в которой можно с обоих концов.
Деревья
Дерево – это структура данных, которая состоит из узлов и соединяющих их направленных ребер или дуг; в каждый узел за исключением корневого ведет только одна дуга.
- Корнем называется главный или начальный узел дерева.
- Листом называется узел, из которого не выходят дуги.
Перечислим некоторые иерархические отношения в дереве:
1 — предок для всех других узлов в дереве
6 — потомок для узлов 5, 3 и 1
3 — родитель узлов 4 и 5
5 — сын узла 3
5 — брат узла 4
Двоичные деревья
В двоичном (бинарном) дереве каждый узел имеет не более двух дочерних узлов (сыновей).
Объявление: 
type PNode = ^Node; < указатель на узел >Node = record data: integer; < данные >left, right: PNode; end;
Поиск по дереву:
При поиске в дереве используется понятие ключ. Ключ — это характеристика узла, по которой осуществляется поиск.
В левую сторону отходят узлы с меньшими ключами, а в правую — с большими. 
- если дерево пустое, значит, ключ не найден;
- если ключ узла равен k, то остановка;
- если ключ узла меньше k, то искать k в левом поддереве;
- если ключ узла больше k, то искать k в правом поддереве.
Сравним поиск в массиве c n элементами с поиском в бинарном дереве:
Поиск в массиве: каждое сравнение — отбрасываем 1 элемент.
Число сравнений – N.
При каждом сравнении отбрасывается половина оставшихся элементов.
Число сравнений
Поиск в бинарном дереве на Паскале:
Создадим функцию для поиска. На вход функции из главной программы подаются два параметра: tree — адрес корня дерева и x — искомое число. Функция возвращает адрес узла с искомым значением или nil, если ничего не найдено.
function SearchInTree(Tree: PNode; x: integer): PNode; begin if Tree = nil then begin Result := nil; Exit; end; if x = Tree^.data then Result := Tree else if x
Динамические структуры данных паскаль
Объект данных обладает динамической структурой, если его размер изменяется в процессе выполнения программы или он потенциально бесконечен.
Классификация структур данных
Используемые в программировании данные можно разделить на две большие группы:
Данные статической структуры – это данные, взаиморасположение и взаимосвязи элементов которых всегда остаются постоянными.
Данные динамической структуры – это данные, внутреннее строение которых формируется по какому-либо закону, но количество элементов, их взаиморасположение и взаимосвязи могут динамически изменяться во время выполнения программы, согласно закону формирования.
Данные динамической структуры:
К данным динамической структуры относят файлы, несвязанные и связанные динамические данные.
Заметим, что файлы в данной классификации отнесены к динамическим структурам данных. Это сделано исходя из вышеприведенного определения. Хотя удаление и вставка элементов в середину файла не допускается, зато длина файла в процессе работы программы может изменяться – увеличиваться или уменьшаться до нуля. А это уже динамическое свойство файла как структуры данных.
Статические и динамические переменные в Паскале
Динамическая память (ДП) – это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (64 Кб), стека (16 Кб) и собственно тела программы. Размер динамической памяти можно варьировать. По умолчанию ДП – вся доступная память ПК.
ДП – это фактически единственная возможность обработки массивов данных большой размерности. Многие практические задачи трудно или невозможно решить без использования ДП. Например, при разработке САПР статическое распределение памяти невозможно, т.к. размерность математических моделей в разных проектах может значительно различаться.
Адресация динамических переменных осуществляется через указатели. Их значения определяют адрес объекта.
Для работы с динамическими переменными в программе должны быть выполнены следующие действия:
- Выделение памяти под динамическую переменную;
- Инициализация указателя;
- Освобождение памяти после использования динамической переменной.
Программист должен сам резервировать место, определять значение указателей, освобождать ДП.
Вместо любой статической переменной можно использовать динамическую, но без реальной необходимости этого делать не стоит.
Указатели
Для работы с динамическими программными объектами в Паскале предусмотрен ссылочный тип или тип указателей. В переменной ссылочного типа хранится ссылка на программный объект (адрес объекта).
Указатель – это переменная, которая в качестве своего значения содержит адрес байта памяти.
Объявление указателей
Указатель, связанный с некоторым определенным типом данных, называют типизированным указателем. Его описание имеет вид:
Пример фрагмента программы объявления указателя
Указатель, не связанный с каким-либо конкретным типом данных, называется нетипизированным указателем. Для описания нетипизированного указателя в Паскале существует стандартный тип pointer. Описание такого указателя имеет вид:
С помощью нетипизированных указателей удобно динамически размещать данные, структура и тип которых меняются в ходе выполнения программы.
Значения указателей – адреса переменных в памяти. Адрес занимает четыре байта и хранится в виде двух слов, одно из которых определяет сегмент, второе – смещение.
Следовало бы ожидать, что значение одного указателя можно передать другому. На самом деле можно передавать значения только между указателями, связанными с одним типом данных. Указатели на различные типы данных имеют различный тип, причем эти типы несовместимы.
Пример фрагмента программы объявления указателя различных типов
Однако это ограничение не распространяется на нетипизированный указатель. В программе допустимы будут следующие действия:
Выделение и освобождение динамической памяти
Вся ДП рассматривается как сплошной массив байтов, который называется кучей.
Расположение кучи в памяти ПК.
Существуют стандартные переменные, в которых хранятся значения адресов начала, конца и текущей границы кучи:
- Heaporg – начало кучи;
- Heapend – конец кучи;
- Heapptr – текущая граница незанятой ДП.
Выделение памяти под динамическую переменную осуществляется процедурой:
В результате обращения к этой процедуре указатель получает значение, соответствующее адресу в динамической памяти, начиная с которого можно разместить данные.
Пример фрагмента программы объявления указателя различных типов
Графически действие процедуры new можно изобразить так:
Освобождение динамической памяти осуществляется процедурой:
Пример фрагмента программы процедуры Dispose
Следует помнить, что повторное применение процедуры dispose к свободному указателю может привести к ошибке.
Процедура dispose освобождает память, занятую динамической переменной. При этом значение указателя становится неопределенным.
Любые действия над указателем в программе располагаются между процедурами new и dispose.
При использовании динамически распределяемых переменных часто возникает общая проблема, называемая утечкой динамической памяти. Утечка памяти – это ситуация, когда пространство выделяется в динамически распределяемой памяти и затем теряется – по каким-то причинам ваш указатель не указывает больше на распределенную область, так что вы не можете освободить пространство. Общей причиной утечек памяти является переприсваивание динамических переменных без освобождения предыдущих. Простейшим случаем является следующий:
Пример фрагмента программы
При первом вызове New в динамически распределяемой памяти выделяется 2 байта, и на них устанавливается указатель IntPointer. Второй вызов New выделяет другие 2 байта, и IntPointer устанавливается на них. Теперь у вас нет указателя, ссылающегося на первые 2 байта, поэтому вы не можете их освободить. В программе эти байты будут потеряны.
Присваивание значений указателю
Для инициализации указателей существует несколько возможностей.
- процедура new отводит блок памяти в области динамических переменных и сохраняет адрес этой области в указателе;
- специальная операция @ ориентирует переменную-указатель на область памяти, содержащую уже существующую переменную. Эту операцию можно применять для ориентации на статическую и динамическую переменную.
Например,
Операции с указателями
Для указателей определены только операции присваивания и проверки на равенство и неравенство. В Паскале запрещаются любые арифметические операции с указателями, их ввод-вывод и сравнение на больше-меньше.
Еще раз повторим правила присваивания указателей:
- любому указателю можно присвоить стандартную константу nil, которая означает, что указатель не ссылается на какую-либо конкретную ячейку памяти;
- указатели стандартного типа pointer совместимы с указателями любого типа;
- указателю на конкретный тип данных можно присвоить только значение указателя того же или стандартного типа данных.
Указатели можно сравнивать на равенство и неравенство, например:
В Паскале определены стандартные функции для работы с указателями:
- addr( x) – тип результата pointer, возвращает адрес x (аналогично операции @), где x – имя переменной или подпрограммы;
- seg( x) – тип результата word, возвращает адрес сегмента для x;
- ofs( x) – тип результата word, возвращает смещение для x;
- ptr( seg, ofs) – тип результата pointer, по заданному сегменту и смещению формирует адрес типа pointer.
Присваивание значений динамическим переменным
После того, как динамическая переменная объявлена, ей можно присваивать значения, изменять их, использовать в выражениях и т.д. Для этого используют следующее обращение: переменная_указатель^. Такое обращение называется операция разадресации (разыменования). Таким образом происходит обращение к значению, на которое указывает указатель, т.е. к данным. Если же за переменной_указателем значок ^ не стоит, то имеется в виду адрес, по которому расположены данные.
Динамически размещенные данные можно использовать в любом месте программы, где допустимо использование выражений соответствующего типа.
Недопустимо использовать выражения, подобные следующим:
Адрес —>R:= sqr( R^) + I^ -17 R^:= sqr( R) nil do
Begin
Writeln (u^.inf);
u:= u^.next;>
end;
Удаление элемента из списка
А)Удаление первого элемента. Для этого во вспомогательном указателе запомним первый элемент, указатель на голову списка переключим на следующий элемент списка и освободим область динамической памяти, на которую указывает вспомогательный указатель.
Б) Удаление элемента из середины списка. Для этого нужно знать адреса удаляемого элемента и элемента, стоящего перед ним. Допустим, что digit – это значение удаляемого элемента.
В)Удаление из конца списка. Для этого нужно найти предпоследний элемент.
Прохождение списка. Важно уметь перебирать элементы списка, выполняя над ними какую-либо операцию. Пусть необходимо найти сумму элементов списка.
Динамические объекты сложной структуры
Использование однонаправленных списков при решении ряда задач может вызвать определенные трудности. Дело в том, что по однонаправленному списку можно двигаться только в одном направлении, от головы списка к последнему звену. Между тем нередко возникает необходимость произвести какую-либо операцию с элементом, предшествующим элементу с заданным свойством. Однако после нахождения элемента с данным свойством в однонаправленном списке у нас нет возможности получить удобный и быстрый способ доступа к предыдущему элементу.
Для устранения этого неудобства добавим в каждое звено списка еще одно поле, значением которого будет ссылка на предыдущее звено.
Динамическая структура, состоящая из звеньев такого типа, называется двунаправленным списком, который схематично можно изобразить так:
Наличие в каждом звене двунаправленного списка ссылки как на следующее, так и на предыдущее звено позволяет от каждого звена двигаться по списку в любом направлении. По аналогии с однонаправленным списком здесь есть заглавное звено. В поле Pred этого звена фигурирует пустая ссылка nil, свидетельствующая, что у заглавного звена нет предыдущего (так же, как у последнего нет следующего).
В программировании двунаправленные списки часто обобщают следующим образом: в качестве значения поля Next последнего звена принимают ссылку на заглавное звено, а в качестве значения поля Pred заглавного звена – ссылку на последнее звено:
Как видно, здесь список замыкается в своеобразное «кольцо»: двигаясь по ссылкам, можно от последнего звена переходить к заглавному звену, а при движении в обратном направлении – от заглавного звена переходить к последнему. Списки подобного рода называют кольцевыми списками.
Существуют различные методы использования динамических списков:
- Стек – особый вид списка, обращение к которому идет только через указатель на первый элемент. Если в стек нужно добавить элемент, то он добавляется впереди первого элемента, при этом указатель на начало стека переключается на новый элемент. Алгоритм работы со стеком характеризуется правилом: «последним пришел – первым вышел».
- Очередь– это вид списка, имеющего два указателя на первый и последний элемент цепочки. Новые элементы записываются вслед за последним, а выборка элементов идет с первого. Этот алгоритм типа «первым пришел – первым вышел».
- Возможно организовать списки с произвольным доступом к элементам. В этом случае необходим дополнительный указатель на текущий элемент.
Динамические структуры данных C++
Динамические структуры данных C++
Сперва давайте разберемся, что это такое и с чем это следует кушать. Динамические структуры данных — это любая структура данных, занимаемый объем памяти которой не является фиксированным. Иными словами, в подобной структуре может храниться как два, пять, двадцать элементов, так и одно большое ничего. Размер подобной структуры ограничен только объемом оперативной памяти компьютера.
Существует несколько разновидностей динамических структур: список, дерево.
Прежде чем переходить к описанию структур, следует запомнить несколько простых определений:
- Потомок — элемент структуры, идущий после текущего. В зависимости от вида динамической структуры у элемента может быть более одного потомка.
- Предок — элемент структуры, идущий до текущего.
- Головной элемент (Head) — первый элемент списка.
- Хвостовой элемент (Tail) — последний элемент списка.
Структура данных Список
Список — это линейная динамическая структура данных, у каждого элемента может быть только один предок и только один потомок. По сути своей это очень похоже на обыкновенный массив, с той лишь разницей, что размер его не имеет ограничений. Списки также подразделяются на несколько
типов.
- Односвязный список — элемент имеет указатель только на своего потомка.
- Двусвязный список — элемент имеет указатели и на потомка, и на родителя.
- Замкнутый (кольцевой, циклический) список — головной и хвостовой элементы которого указывают друг на друга.
На базе простого однонаправленного списка могут быть построены такие структуры данных, как очередь (queue) и стек (stack).
Очередь есть ничто иное, как список, операции чтения и добавления элементов в котором подвержены определенным правилам. При этом, при чтении элемента, он удаляется из очереди. Все операции проводятся по принципу «Первый пришел, первый вышел» (FIFO — first in, first out). Таким образом, для чтения в очереди доступна только голова, в то время как добавление проводится только в хвост.
Стек во многом похож на очередь, с той лишь разницей, что извлечение и добавление элементов в нем происходит по правилу «Последний пришел, первый вышел» (LIFO — last in, first out). Добавление и извлечение элементов проводится от головы. По принципу похоже на работу обоймы огнестрельного оружия.
Двусвязный список на языке C++
Рассмотрим пример реализации простейшего двусвязного списка. Этот и последующие примеры кода будут приведены на языке c++. В примере реализованы операции добавления нового элемента в список и вывод элементов на форму.
Элемент списка
Список
Структура данных Дерево
Дерево — несколько более интересная структура. В отличие от списка, у одной записи может быть более одного потомка, но только один предок. Кроме того в дереве явно выделяется только головной элемент, называемый корнем (Root). Среди деревьев также существует разбиение на подтипы.
- Бинарное дерево — у каждой вершины дерева может быть не более двух потомков.
- Сильно разветвленное дерево — у вершины может быть n-ое число потомков.
В свою очередь для бинарных деревьев существует разбиение в зависимости от высоты поддеревьев, информационной части вершин и т.д. (АВЛ-деревья, красно-черные деревья, и др.).
В отличие от списка при обходе дерева может быть применено насколько различных путей:
Бинарное дерево поиска на языке C++
Рассмотрим реализацию простейшего бинарного дерева поиска. В данном примере используется поперечный обход дерева.
Бинарное дерево
Одним из интересных примеров сильно разветвленного дерева является так называемая TRIE-структура или БОР. Подобная структура данных можем быть очень
полезна при создании алгоритма наподобие Т9, потому как в каждой вершине бора содержится всего один символ алфавита или символ конца слова.
Префиксное дерево
При реализации любой динамической структуры средствами языка c++ следует очень внимательно следить за памятью. Наиболее частые ошибки в данном случае регистрируются как «access violation», то есть обращение к не размеченной области памяти. Обычно лечится внимательным изучением трассировки и поиском, где поезд пошел не в тот тоннель.
Ну и на сладкое: рассмотрим пример интерактивного ввода дерева. По клику на мышку. Для этого незначительно расширим реализацию простого бинарного дерева. Единственное, что нам понадобится на форме — Image.
Динамические структуры данных С++. Заключение
Удачных вам экспериментов с динамическими структурами, коллеги.
Кроме того, рекомендую прочитать статью Set C# | Структура данных Множество C#. А также подписывайтесь на группу ВКонтакте, Telegram и YouTube-канал. Там еще больше полезного и интересного для программистов.
Указатели
Тема: Динамические структуры данных. Статические и динамические переменные. Адреса. Указатели и их объявление.
В любой вычислительной системе память относится к таким ресурсам, которых всегда не хватает. Управление памятью — одна из главных забот программиста, так как для него очень важно создавать программы, эффективно использующие память, ведь во время выполнения программы память необходима для следующих элементов программ и данных:
- сама программа пользователя;
системные программы времени выполнения, которые осуществляют вспомогательные действия при работе программы пользователя;
определяемые пользователем структуры данных и константы;
точки возврата для программ;
временная память для хранения промежуточных результатов при вычислении выражений;
временная память при передаче параметров;
буферы ввода-вывода, используемые как временные области памяти, в которых хранятся данные между моментом их реальной физической передачи с внешнего устройства или на него и моментом инициализации в программе операции ввода или вывода;
Из этого перечня видно, что управление памятью касается широкого класса объектов.
До сих пор мы использовали простейший способ распределения памяти — статическое распределение, т. е. распределение памяти при трансляции программы. То есть когда Вы объявляете переменную
Вы даете указание компилятору выделить память размера, соответствующего заданному типу, т.е. 2*100=200 байт. Если в программе на нужный программный объект мы ссылаемся по имени А[3], то машинный код содержит ссылку на номер ячейки памяти (адрес байта), начиная с которой размещается этот объект.
Адреса задаются двумя 16-тиразрядными словами (тип word) — сегментом и смещением. Каждое из них способно адресовать 216=65536 байт (64 Кбайт). Для адресации пространства размером в 1 Мбайт требуется 20 разрядов. Сегменты адресуют память с точностью до параграфа — фрагмента памяти в 16 байт. Смещение адресует память с точностью до байта, но впределах сегмента. Реальный (абсолютный) адрес складывается из значения сегмента, сдвинутого на 4 разряда влево (умноженного на 16), и смещения. Фрагмент программы вычисления абсолютного адреса в реальном режиме:
Программа на Паскале получает один сегмент данных, поэтому область памяти, в которой могут быть размещены статические переменные Вашей программы, ограничена 64 Кбайтами. При попытке исполнить программу, требующую большего размера памяти, будет выдана ошибка:
Error 49: Data Segment too large
При динамическом распределении памяти Вы можете запросить блоки размером до одного сегмента (64 Кбайт) каждый, причем их можно требовать в пределах основной памяти (640 Кбайт) в реальном режиме и без программных ограничений в защищенном.
Бывают такие данные, размер которых выясняется только при выполнении программ. Кроме того, иногда мы не знаем, будет существовать некоторый объект или нет.
Например, в программе для обработки текстов (такие программы называются «текстовыми процессорами») требуется организовать поиск слов, определенных пользователем. Естественно, что определить заранее длину слова, которое будет задано, невозможно. Часто программный объект, причем значительного размера, бывает нужен на непродолжительное время. Использование статических программных объектов в таких случаях очень неэффективно, поскольку программа должна быть рассчитана на максимальные размеры объектов. Область памяти, в которой могут быть размещены статические переменные, ограничена, и, рассчитывая на максимальный размер переменных, мы ограничиваем их количество. В Паскале, кроме статических, предусмотрены динамические объекты. Память под них отводится во время исполнения программы, а когда программный объект можно удалить, память освобождается.
И статические, и динамические переменные вызываются по их адресам. Без адреса не получить доступ к нужной ячейке памяти, но, используя статические переменные, непосредственно адрес Вы не указываете, а обращаетесь к переменной по имени. Компилятор размещает переменные в памяти и подставляет нужные адреса в коды команд.
Адресация динамических переменных происходит через указатели. В Паскале можно определить переменные, которые имеют тип указатель, их значения определяют адрес объекта. Для работы с динамическими переменными в программе должны быть предусмотрены:
- выделение памяти под динамическую переменную;
присвоение указателю на динамическую переменную адреса выделенной памяти (инициализация указателя);
Программист сам должен резервировать место под переменную, определять значения указателей, освобождать память — удалять динамические переменные. Для использования динамической переменной где-то в статике должен быть указатель на нее. Компилятор предусматривает место под указатель, об инициализации указателя должен заботиться программист.
Вместо любой статической переменной можно использовать динамическую, но без реальной необходимости этого делать не стоит. Переменные простых типов нет смысла размещать в динамической области, поскольку они занимают меньше места, чем указатель на них. Например, указатель на целое занимает 4 байта, само целое — 2 байта. Кроме того, при динамическом распределении памяти удлиняется текст программы, снижаются наглядность и быстродействие. Это объясняется тем, что, во-первых, нужно во время исполнения программы определять значения указателей, а во-вторых, усложняется доступ к значению переменной.
Указатели и их объявление
Для работы с динамическими программными объектами в Паскале предусмотрен ссылочный тип или тип указателей. В переменной ссылочного типа хранится ссылка на программный объект (адрес объекта). Указатель состоит из сегмента и смещения. По правилам Паскаля указатели на разные типы данных имеют различные типы, причем эти типы несовместимы, т.е. указатели на разные типы данных не могут ссылаться на один объект.
Чтобы связать ссылочный тип с определенным типом данных, используется символ ^, помещаемый перед именем типа. Например, имеется тип массив:
Переменные ссылочного типа могут определяться как статические, при этом по общим правилам объявления переменных возможна запись с явным и неявным определением ссылочного типа.
Для получения данных, соответствующих указателю, символ «^» приводится после имени указателя. Действия с элементами массива типа А могут быть описаны через действия над указателями В и С.
После выполнения этого кода i-е элементы массивов, на которые указывают В и С, будут равны.
Указатели могут ссылаться на любой тип данных, кроме файлового.
Разберем простой пример, обратив еще раз внимание на синтаксис:
Первый оператор присваивает целочисленной переменной, на которую ссылается Р, значение 16, второй прибавляет к значению переменной х значение 16, второй прибавляет к значению переменной х значение 16. Аналогично определяются и используются указатели на переменные любого типа, в том числе и определенного пользователем.
Обратите внимание, что указатель является обычной статической переменной, а переменная, на которую он указывает — динамической.
Схематически можно представить себе указатель так:
Указательная переменная Р может быть в трех состояниях.
1. Содержать адрес какой-либо переменной, память под которую уже выделена.
2. Содержать специальный пустой адрес Nil.
3. Находиться в неопределенном состоянии.
В неопределенном состоянии указатель бывает в начале работы программы до первого присваивания ему или конкретного адреса, или пустого адреса Nil, а также после освобождения области памяти на которую он указывает.
Схематически различия между состоянием Nil и неопределенным состоянием можно изобразить так:
Использование имени указателя в программе означает обращение к адресу ячейки памяти, на которую он указывает. Чтобы обратиться к содержимому ячейки, на которую указывает указатель, требуется после его идентификатора поставить символ ^. Эта операция еще называется разыменованием.
Для представления указателя на строку с завершающим нулем в Паскале имеется предопределенный тип PChar. В модуле System этот тип описывается следующим образом:
Паскаль поддерживает набор расширенных правил, позволяющих работать со строками с завершающим нулем, используя тип PChar.
Иногда связи между ссылкой и переменной не существует по смыслу задачи, в этом случае с указателем нельзя связать никакой объект, а ссылка должна быть пустой. Зарезервированное слово Nil обозначает константу со значением указателя, который ни на что не указывает. После присвоения
указатель не будет указывать ни на какой объект. Значение Nil совместимо с любым ссылочным типом.
Операции «=» и «<>» могут использоваться для сравнения операндов типа указатель. Два указателя равны только в том случае, если они ссылаются на один и тот же объект.
