Remkomplekty.ru

IT Новости из мира ПК
4 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Указатели и динамические структуры данных паскаль

Указатели

Тема: Динамические структуры данных. Статические и динамические переменные. Адреса. Указатели и их объявление.

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

    сама программа пользователя;

системные программы времени выполнения, которые осуществляют вспомогательные действия при работе программы пользователя;

определяемые пользователем структуры данных и константы;

точки возврата для программ;

временная память для хранения промежуточных результатов при вычислении выражений;

временная память при передаче параметров;

буферы ввода-вывода, используемые как временные области памяти, в которых хранятся данные между моментом их реальной физической передачи с внешнего устройства или на него и моментом инициализации в программе операции ввода или вывода;

  • различные системные данные (информация о статусе устройств ввода-вывода и др.).
  • Из этого перечня видно, что управление памятью касается широкого класса объектов.

    До сих пор мы использовали простейший способ распределения памяти — статическое распределение, т. е. распределение памяти при трансляции программы. То есть когда Вы объявляете переменную

    Вы даете указание компилятору выделить память размера, соответствующего заданному типу, т.е. 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 совместимо с любым ссылочным типом.

    Операции «=» и «<>» могут использоваться для сравнения операндов типа указатель. Два указателя равны только в том случае, если они ссылаются на один и тот же объект.

    Указатели и динамические структуры

    До сих пор мы рассматривали программирование, связанное с обработкой только статических данных. Статическими называются такие величины, память под которые выделяется во время компиляции и сохраняется в течение всей работы программы.

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

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

    Работа с динамическими величинами связана с использованием еще одного типа данных — ссылочного. Величины, имеющие ссылочный тип, называют указателями.

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

    Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом.

    Величина ссылочного типа (указатель) описывается в разделе описания переменных следующим образом:

    В стандарте Паскаля каждый указатель может ссылаться на величину только одного определенного типа, который называется базовым для указателя. Имя базового типа и указывается в описании в следующей форме:

    Вот примеры описания указателей:

    Type Massiv=Array[l..100] Of Integer;

    Здесь Р1 — указатель на динамическую величину целого типа; P2 — указатель на динамическую величину символьного типа; PM — указатель на динамический массив, тип которого задан в разделе Type.

    Читать еще:  Конец файла паскаль

    Сами динамические величины не требуют описания в программе, поскольку во время компиляции память под них не выделяется

    Во время компиляции память выделяется только под статические величины. Указатели — это статические величины, поэтому они требуют описания.

    Каким же образом происходит выделение памяти под динамическую величину? Память под динамическую величину, связанную с указателем, выделяется в результате выполнения стандартной процедуры NEW. Формат обращения к этой процедуре выглядит так:

    Считается, что после выполнения этого оператора создана динамическая величина, имя которой имеет следующий вид:

    Пусть в программе, в которой имеется приведенное выше описание, присутствуют операторы

    NEW(Pl); NEW(P2); NEW(PM);

    После их выполнения в динамической памяти оказывается выделенным место под три величины (две скалярные и один массив), которые имеют идентификаторы

    Например, обозначение P1^ можно расшифровать так: динамическая переменная, на которую ссылается указатель Р1.

    На схеме, представленной на рис. 39, показана связь между динамическими величинами и их указателями.

    Дальнейшая работа с динамическими переменными происходит точно так же, как со статическими переменными соответствующих типов. Им можно присваивать значения, их можно использовать в качестве операндов в выражениях, параметров подпрограмм и т.п. Например, если переменной Р1^ нужно присвоить значение 25, переменной P2^ присвоить значение символа ‘W’, a массив PM^ заполнить по порядку целыми числами от 1 до 100, то это делается так:

    For I:=l То 100 Do PM^ [I]:=I;

    Кроме процедуры NEW значение указателя может определяться оператором присваивания:

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

    • ссылочную функцию (т. е. функцию, значением которой является указатель);

    Nil — это зарезервированная константа, обозначающая пустую ссылку, т. е. ссылку, которая ни на что не указывает. При присваивании базовые типы указателя и ссылочного выражения должны быть одинаковыми. Константу Nil можно присваивать указателю с любым базовым типом.

    До присваивания значения ссылочной переменной (с помощью оператора присваивания или процедуры NEW) она является неопределенной.

    Ввод и вывод указателей не допускается. Рассмотрим пример. Пусть в программе описаны следующие указатели:

    Тогда допустимыми являются операторы присваивания

    поскольку соблюдается принцип соответствия типов. Оператор K:=D ошибочен, так как базовые типы у правой и левой части разные.

    Если динамическая величина теряет свой указатель, то она становится «мусором». В программировании под этим словом понимают информацию, которая занимает память, но уже не нужна.

    Представьте себе, что в программе, в которой присутствуют описанные выше указатели, в разделе операторов записано следующее:

    две целые переменные. Указатели получили

    ту же величину, равную 3>

    Таким образом, динамическая величина, равная 5, потеряла свой указатель и стала недоступной. Однако место в памяти она занимает. Это и есть пример возникновения «мусора». На схеме, представленной на рис. 40, показано, что произошло в результате выполнения оператора Р:=D.

    В Паскале имеется стандартная процедура, позволяющая освобождать память от данных, потребность в которых отпала. Ее формат:

    Например, если динамическая переменная P^ больше не нужна, то оператор

    удалит ее из памяти. После этого значение указателя Р становится неопределенным. Особенно существенным становится эффект экономии памяти при удалении больших массивов.

    В версиях Турбо Паскаля, работающих под управлением операционной системы MS DOS, под данные одной программы выделяется 64 килобайта памяти. Это и есть статическая область памяти. При необходимости работать с большими массивами информации этого может оказаться мало. Размер динамической памяти намного больше (сотни килобайт). Поэтому использование динамической памяти позволяет существенно увеличить объем обрабатываемой информации.

    Следует отчетливо понимать, что работа с динамическими данными замедляет выполнение программы, поскольку доступ к величине происходит в два шага: сначала ищется указатель, затем по нему — величина. Как это часто бывает, действует «закон сохранения неприятностей»: выигрыш в памяти компенсируется проигрышем во времени.

    Пример 1. Создать вещественный массив из 10000 чисел, заполнить его случайными числами в диапазоне от 0 до 1. Вычислить среднее значение массива. Очистить динамическую память. Создать целый массив размером 10000, заполнить его случайными целыми числами в диапазоне от -100 до 100 и вычислить его среднее значение.

    MasInt=Array[Diapazon] Of Integer;

    MasReal=Array[Diapazon] Of Real;

    Var Flint: ^Masint;

    For I:=1 То NMax Do

    NEW(Pint); (Выделение памяти под целый массив>

    For I:=l To NMax Do

    WriteLn(‘среднее целое равно:’,MidInt DivMax);

    WriteLn(‘среднее вещественное равно:’, (MidReal/NMax):10:6)

    Связанные списки. Обсудим вопрос о том, как в динамической памяти можно создать структуру данных переменного размера.

    Разберем следующий пример. В процессе физического эксперимента многократно снимаются показания прибора (допустим, термометра) и записываются в компьютерную память для дальнейшей обработки. Заранее неизвестно, сколько измерений будет произведено.

    Если для обработки таких данных не использовать внешнюю память (файлы), то разумно расположить их в динамической памяти. Во-первых, динамическая память позволяет хранить больший объем информации, чем статическая. А во-вторых, в динамической памяти эти числа можно организовать в связанный список, который не требует предварительного указания количества чисел, подобно массиву. Что же такое связанный список? Схематически он выглядит так:

    Каждый элемент списка состоит из двух частей: информационной части (x1, x2 и т.д.) и указателя на следующий элемент списка (p2, р3, и т.д.). Последний элемент имеет пустой указатель Nil. Связанный список такого типа называется однонаправленной цепочкой.

    Для сформулированной выше задачи информационная часть представляет набор вещественных чисел: x1 — результат первого измерения, x2 — результат второго измерения и т

    д., х4 — результат последнего измерения. Связанный список обладает тем замечательным свойством, что его можно дополнять по мере поступления новой информации. Добавление происходит путем присоединения нового элемента к концу списка. Значение Nil в последнем элементе заменяется ссылкой на новый элемент цепочки:

    Связанный список не занимает лишней памяти. Память расходуется в том объеме, который требуется для поступившей информации.

    В программе для представления элементов цепочки используется комбинированный тип (запись). Для нашего примера тип такого элемента может быть следующим:

    Здесь Ре — ссылочный тип на переменную типа Elem. Этим именем обозначен комбинированный тип, состоящий из двух полей: T — вещественная величина, хранящая температуру, P — указатель на динамическую величину типа Elem.

    В таком описании нарушен один из основных принципов Паскаля, согласно которому на любой программный объект можно ссылаться только после его описания. В самом деле, тип Ре определяется через тип Elem, а тот, в свою очередь, определяется через тип Ре. Однако в Паскале допускается единственное исключение из этого правила, связанное со ссылочным типом. Приведенный фрагмент программы является правильным.

    Пример 2. Рассмотрим программу формирования связанного списка в ходе ввода данных.

    Begin (Определение адреса начала списка и его сохранение>

    Указатели и динамические структуры данных паскаль

    Объект данных обладает динамической структурой, если его размер изменяется в процессе выполнения программы или он потенциально бесконечен.

    Классификация структур данных

    Используемые в программировании данные можно разделить на две большие группы:

    Данные статической структуры – это данные, взаиморасположение и взаимосвязи элементов которых всегда остаются постоянными.

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

    Данные динамической структуры:

    К данным динамической структуры относят файлы, несвязанные и связанные динамические данные.

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

    Статические и динамические переменные в Паскале

    Динамическая память (ДП) – это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (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 заглавного звена – ссылку на последнее звено:

    Как видно, здесь список замыкается в своеобразное «кольцо»: двигаясь по ссылкам, можно от последнего звена переходить к заглавному звену, а при движении в обратном направлении – от заглавного звена переходить к последнему. Списки подобного рода называют кольцевыми списками.

    Существуют различные методы использования динамических списков:

    • Стек – особый вид списка, обращение к которому идет только через указатель на первый элемент. Если в стек нужно добавить элемент, то он добавляется впереди первого элемента, при этом указатель на начало стека переключается на новый элемент. Алгоритм работы со стеком характеризуется правилом: «последним пришел – первым вышел».
    • Очередь– это вид списка, имеющего два указателя на первый и последний элемент цепочки. Новые элементы записываются вслед за последним, а выборка элементов идет с первого. Этот алгоритм типа «первым пришел – первым вышел».
    • Возможно организовать списки с произвольным доступом к элементам. В этом случае необходим дополнительный указатель на текущий элемент.

    Указатели в Паскале. Динамическая память на языке Паскаль

    В ТР имена объектов (переменных и др.) д. б. определены до момента использования их в программе. Как отмечалось ранее, ОП персонального компьютера имеет сегментную структуру. Адрес – совокупность двух 16-ти разрядных слов — сегмента и смещения. (Например: $0060:$01А0). Сегмент — участок памяти, имеющий максимальную длину 64К (65536 байт). Начальный адрес каждого сегмента кратен 16 (т.е. 0, 16, 32, и т.д.), следовательно, два сегмента отстоят друг от друга, по крайней мере, на 16 байт. Сегменты адресуют память с точностью до параграфа. Параграф – фрагмент памяти равный 16 байт. Смещение – линейная адресация в сегменте. Она также имеет 16-ти разрядные адреса и адресует память с точностью до байта. При этом глобальные переменные и типизированные константы размещаются в сегменте данных. Такие переменные называются статическими, а память, выделяемая компилятором для их хранения называется статической памятью.

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

    Память, которая выделяется под локальные переменные, называется сегментом стека. Она задается директивой <$M >. Минимальный размер памяти 1К, максимальный 64К, по умолчанию 16к.

    В ТР существует возможность создавать новые переменные в момент работы программы или уничтожать их в соответствие с требованиями задачи. Такие переменные называются динамическими.

    Для динамических переменных отводится динамическая память, которая имеет стековую структуру и называется «кучей» (хипом – Heap-куча). Размер хипа задается директивой <$M >.

    Доступ к статическим переменным осуществляется через их имена.
    Доступ к динамическим переменным осуществляется через указатель на место их расположения в памяти.
    Многие практические задачи трудно или невозможно решить без использования динамической памяти. Например, обработки массивов больших объемов (более 65536 байт).

    Ссылочные типы. Указатели в Паскале

    Указатель – это переменная, которая содержит адрес другой переменной (байта памяти).
    В ТР имеется два вида указателей: указатель на объект некоторого типа (типизированный) и указатель, не связанный с типом.
    Описание указателей.

    Для объявления типизированных указателей используется значок ^, который помещается перед соответствующим типом:

    Type T = ^T1;
    Var A :T;
    где: T – имя типа;
    T 1 — базовый тип (любой в т.ч. указатель);
    ^ — указатель.
    Примеры:
    Var
    a :byte; <выделение памяти для переменной где хранится ее значение>
    a ;^byte;

    Var
    p1 :^integer;
    p2, p3 :^real;

    Для объявления переменных не связывая их, с каким либо типом данных можно использовать указатель без типа (pointer).
    Var
    p :pointer;
    где: pointer — не типизированный указатель, который занимает в памяти 4 байт (2-байта сегмент, 2байта смещение.).

    Операции с указателями

    Для указателей допустимы операции сравнения и присваивания.

    Присваивание. Указателю можно присвоить содержимое другого указателя того же самого типа или константу NIL – пустой, или адрес объекта с помощью функции ADDR или оператора @.

    Пример:
    P1 := PP;
    P2 := NIL;
    P3 := Addr(X);
    P4 := @X;

    Процедуры и функции для работы с указателями и адресами в Паскале

    ADDR(X) – результат POINTER, в котором содержится адрес аргумента. (X –имя любой переменной, процедуры или функции).
    OFS(X):WORD – возвращает значение смещения адреса объекта X.
    SEG(X):WORD – возвращает значение сегмента адреса объекта X.
    CSEG(X):WORD – возвращает текущее значение регистра Cs.
    DSEG(X):WORD – возвращает текущее значение регистра Ds.
    SSEG(X):WORD – возвращает текущее значение регистра Ss.
    SPRT(X):WORD — возвращает текущее значение регистра Sp.
    PRT(SEG,OFS) – преобразует отдельно заданные значение сегмента и смещения к типу указателя.
    MAXAVAIL:LONGINT — возвращает размер наибольшего непрерывного участка кучи.
    MEMXAVAIL:LONGINT — возвращает размер общего свободного пространства кучи.

    Процедуры:
    DISPOSE(TP:POINTER) – уничтожает динамическую переменную и возвращает в кучу фрагмент динамической памяти, который был зарезервирован
    указателем.
    NEW(TP:POINTER) – резервирует фрагмент кучи для размещения переменной.
    GETMEM(P:POINTER; ZIZE:WORD) –выделяет из кучи блок заданного размера и адрес его начала присваивает указателю.
    FREEMEM(P:POINTER; ZIZE:WORD) – освобождает блок заданного размера..
    MARK(P:POINTER) – запоминает текущую вершину кучи (адрес начала свободного участка).
    RELEASE(P:POINTER) – освобождает участок кучи от адреса с P до конца.

    Пример 19.1. Сгенерировать случайным образом массив случайных чисел. Разместить массив в динамической памяти, найти сумму элементов и удалить его с памяти.

    Текст программы

    Program Dinmas;
    Uses CRT;
    Const k1=100; k2=2*k1+1;
    Type
    Item = Real;
    DinArr = array[1..$FFF0 div SizeOf(Item)] of Item;
    DinPrt = ^DinArr;
    Var
    Arr : DinPrt;
    I,N : Word;
    S :Real;
    f :real;
    <$R->
    Begin
    ClrScr;
    Randomize;
    Writeln(‘Введите количество элементов массива N:’);
    Readln(N);

    GetMem(Arr,N*SizeOf(Item));
    Writeln(‘Введите массив X(N):’);
    For i:=1 to N do
    begin
    f:=random(k2);
    Arr^[i]:=k1-f; Write(Arr^[i]:4:2,’ ‘:2)
    < Read(Arr^[i]);>;
    End;
    Writeln;
    S:=0;
    For i:=1 to N do S:=S+Arr^[i];
    Writeln(^G’Результат:’,^J^M,^G’Сумма=’,S);
    FreeMem(Arr,N*SizeOf(Item));
    Repeat Until KeyPressed
    End.

    Результаты работы программы:

    Введите количество элементов массива N:
    200
    Введите массив X(N):
    -35.00 -82.00 45.00 95.00 -26.00 -72.00 1.00 -77.00 10.00 89.00 -38.00
    -48.00 8.00 26.00 13.00 33.00 6.00 82.00 -63.00 -83.00 -23.00 39.00
    6.00 11.00 48.00 72.00 -100.00 -2.00 93.00 68.00 73.00 66.00 -91.00
    6.00 0.00 -19.00 94.00 32.00 -63.00 59.00 87.00 29.00 -93.00 -51.00 3
    4.00 10.00 58.00 0.00 27.00 41.00 6.00 34.00 55.00 -84.00 7.00 -37.00
    -49.00 -6.00 71.00 11.00 -47.00 -85.00 -53.00 51.00 63.00 -80.00 32.
    00 -71.00 -73.00 -27.00 -15.00 -7.00 -68.00 -89.00 32.00 -22.00 -86.00
    -52.00 27.00 -16.00 92.00 19.00 -35.00 -8.00 -78.00 16.00 -94.00 -47
    .00 -8.00 -98.00 -96.00 -5.00 -68.00 37.00 10.00 82.00 -32.00 15.00 2
    2.00 -21.00 11.00 55.00 -15.00 -54.00 -20.00 -79.00 -15.00 -79.00 -13.
    00 -62.00 -59.00 -93.00 -57.00 -42.00 57.00 41.00 -64.00 -43.00 -71.00
    -66.00 49.00 25.00 66.00 89.00 38.00 98.00 -84.00 64.00 71.00 -75.00
    77.00 83.00 27.00 -88.00 49.00 -100.00 59.00 29.00 -57.00 70.00 33.0
    0 -87.00 -8.00 -45.00 23.00 88.00 -51.00 -66.00 5.00 95.00 -28.00 15.
    00 -1.00 -26.00 -63.00 37.00 -76.00 -1.00 96.00 -43.00 -94.00 -29.00
    -78.00 -99.00 4.00 -80.00 -43.00 -5.00 -6.00 -13.00 -1.00 -75.00 80.00
    43.00 -58.00 -31.00 69.00 -81.00 -71.00 -62.00 -21.00 -84.00 4.00 67
    .00 -82.00 -55.00 25.00 -4.00 94.00 75.00 -55.00 -15.00 -86.00 -43.00
    -92.00 5.00 -81.00 -18.00 -33.00 -71.00
    Результат:
    Сумма=-1.8610000000E+03

    Пример 19.2. Сгенерировать случайным образом матрицу случайных чисел. Разместить матрицу в динамической памяти, найти сумму элементов и удалить ее с памяти.

    Program Dinmas;
    Uses CRT;
    Type
    Item = Real;
    DinArr=array[1..$Ff div sizeof(item),1..$ff div sizeof(item)] of Item;
    DinPrt = ^DinArr;
    Var
    Arr : DinPrt;
    k,j,l,I,N : Word;
    S :Real;
    <$R->
    Begin
    ClrScr;
    randomize;
    Writeln(‘Введите количество строк массива N:’); Readln(i);
    Writeln(‘Введите количество столбцов массива N:’); readln (j);
    n:=i*j;

    GetMem(Arr,N*SizeOf(Item));
    < Writeln('Введите массив X(N):');>
    For k:=1 to i do
    for l:=1 to j do Arr^[k,l]:=random (2000);
    S:=0;
    For k:=1 to i do
    for l:=1 to j do S:=S+Arr^[k,l];
    Writeln(^G’Результат:’,^J^M,^G’Сумма=’,S);
    FreeMem(Arr,N*SizeOf(Item));
    Repeat Until KeyPressed
    End.

    Результаты работы программы:

    Введите количество строк массива N:
    1000
    Введите количество столбцов массива N:
    1000
    Результат:
    Сумма= 5.7820716634E+32

    Пример 19.3. Разместить запись в динамической памяти, затем удалить ее с памяти.

    Текст программы:

    Program pointer1;
    <Работа с динамической папятью>
    Uses crt;
    Type
    FriendRec = Record
    Name : string[30];
    Age : Byte;
    End;
    FrPtr = ^FriendRec;
    Var
    p : FrPtr;
    Begin
    ClrScr;
    GetMem(p, SizeOf(FriendRec)); <Выделение памяти в куче>
    Write(‘Введите имя : ‘); Readln(p^.Name);
    Write(‘Введите возраст : ‘); Readln(p^.Age);
    Writeln;
    Writeln(‘Память для записи о имени и возрасте распределена в куче.’);
    Writeln;
    Writeln(‘Имя : ‘,p^.Name);
    Writeln(‘Возраст : ‘,p^.Age);
    Writeln;
    FreeMem(p, SizeOf(FriendRec)); <Освобождение памяти>
    Writeln(‘Память, занимаемая записью о имени и возрасте освобождена.’);
    Repeat until KeyPressed;
    End.

    Результаты работы программы:

    Введите имя: Иванов Александр Григорьевич
    Введите возраст: 33

    Память для записи о имени и возрасте распределена в куче.

    Имя: Иванов Александр Григорьевич
    Возраст: 33

    Память, занимаемая записью о имени и возрасте освобождена.

    Указатели и динамические структуры данных паскаль

    страницы: 1 2 3 4

    Содержание

    Присваивания

    Для указателей действуют гораздо более жёсткие правила совместимости типов, чем для обычных переменных. В операции присваивания могут фигурировать только указатели , адресующие переменные одинаковых типов данных. Нельзя, скажем, записать

    Обойти эти ограничения позволяет универсальность нетипизированного указателя Pointer , совместимого с указателями любых типов:

    У указателей также существует свой «ноль» , который означает, что указатель не указывает никуда:

    Замечание: Если указатель не хранит конкретного адреса (его значение не определено), то это вовсе не означает, что он никуда не указывает. Скорее всего, он всё–таки указывает, но только в какую–нибудь неожиданную (хорошо, если не системную) область памяти.

    Сравнения

    Для указателей определены две операции сравнения: = и <> .

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

    Для разнотипных указателей сравнения невозможны: попытка записать

    вызовет ошибку уже на этапе компиляции.

    Однако сравнивать типизированный и нетипизированный указатели можно.

    Динамически распределяемая память

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

    Задумаемся теперь: а если у переменной есть адрес , но нет имени , можно ли оперировать ею с прежней легкостью? Ответ на этот вопрос: «Да, можно!»

    Итак, пусть у некоторой переменной нет имени . Тем не менее, можно расположить её в памяти, выделив под неё необходимое количество байтов, и т.д. У переменной будет адрес , будет значение, но не будет имени . Следовательно, обратиться к такой переменной можно будет только с помощью указателя .

    «Безымянные» переменные отличаются от «нормальных» переменных:

    1. Нет имени — нечего описывать в разделе var .
    2. Ничего не описано, значит, на этапе компиляции память под переменную не выделена. Следовательно, необходима возможность выделять память (и отменять это выделение) прямо в процессе работы программы. Именно из–за этой гибкости такие переменные и называют динамическими .
    3. Если «потерять» указатель на переменную, то «никто не узнает, где могилка» её: переменная останется недоступным «мусором», занимая место в памяти, вплоть до конца работы программы.

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

    Типизированные указатели

    Для выделения памяти служит стандартная процедура New () :

    Эта процедура ищет в незанятой памяти подходящий по размеру кусок и, «застолбив» это место для безымянной динамической переменной , записывает в типизированный указатель адрес выделенного участка. Поэтому часто говорят, что процедура New () создаёт динамическую переменную . Размер выделяемого «куска памяти» напрямую зависит от типа указателя .

    Например, если переменная p была описана как указатель на Integer –переменную, то процедура New (p) выделит два байта; под Real –переменную необходимо выделить шесть байт и т. д.

    Нетипизированные указатели

    Для того, чтобы выделить память, на которую будет указывать нетипизрованный указатель Pointer , нужно воспользоваться стандартной процедурой GetMem (p : Pointer ; size : Word ) , которая выделит столько байт свободной памяти, сколько указано в переменной size .

    Динамическое освобождение памяти

    Типизированные указатели

    Для уничтожения динамической переменной , то есть для освобождения занимаемой ею памяти, предназначена стандартная процедура

    Процедура Dispose () снимает пометку «занято» с определённого количества байтов, начиная с указанного адреса . Эта область памяти в дальнейшем считается свободной (хотя старое значение бывшей переменной в ней может некоторое время ещё оставаться). Количество освобождаемых байтов определяется типом указателя p .

    В результате освобождения памяти при помощи процедуры Dispose () значение указателя , хранившего адрес освобождённой области, становится неопределённым. Во избежание проблем его лучше сразу же «обнулить»:

    Нетипизированные указатели

    Для того, чтобы освободить память, на которую указывает нетипизрованный указатель , нужно воспользоваться стандартной процедурой FreeMem (p : Pointer ; size : Word ) , которая освободит в памяти столько байтов (начиная с указанного в переменной p адреса ), сколько задано в переменной size .

    Списочные структуры

    Если для каждой динамической переменной описывать и хранить её «личный» указатель , то никакой выгоды на этапе выполнения программы получить не удастся: часть памяти, как и прежде, будет выделяться статически, а её общий объем даже увеличится — ведь каждый указатель требует для себя четыре байта.

    Следовательно, нужно сделать так, чтобы место под хранение адресов будущих переменных также выделялось динамически. Решением этой проблемы и служат списки — специальные динамические структуры.

    Списки применяются, например, в таких ситуациях:

    • программист заранее ничего не знает о том, какой именно объём памяти может потребоваться его программе;
    • некоторые (особенно «тяжёлые») переменные нужны поочередно, и после того как первые «отработали своё», их можно смело стирать из памяти, не дожидаясь конца работы программы, — освобождать место для других «тяжёлых» переменных;
    • в процессе обработки данных нужно провести большую работу по перестройке всей структуры «на ходу»; и т.д.
    Ссылка на основную публикацию
    ВсеИнструменты
    Adblock
    detector
    ×
    ×