Динамические структуры данных pascal abc

Программирование. Динамические списки Pascal-Паскаль

• Скачено бесплатно: 6955
• Куплено: 414

• Pascal-Паскаль->Программирование. Динамические списки Pascal-Паскаль

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

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

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

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

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

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

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

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

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

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

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

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

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

Предположим, например, что у вас есть программа, требующая массива в 400 строк по 100 символов каждая. Для этого массива требуется примерно 40К, что меньше максимума в 64К. Если остальные ваши переменные помещаются в оставшиеся 24К, массив такого объема проблемы не представляет. Но что если вам нужно два таких массива? Это потребовало бы 80К, и 64К сегмента данных не хватит. Другим общим примером является сортировка. Обычно когда вы сортируете большой объем данных, то делаете копию массива, сортируете копию, а затем записываете отсортированные данные обратно в исходный массив. Это сохраняет целостность ваших данных, но требует также наличия во время сортировки двух копий данных.

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

Динамическая память (ДП) – это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (64 Кб), стека (16 Кб) и собственно тела программы. Размер динамической памяти можно варьировать. По умолчанию ДП – вся доступная память ПК.

ДП – это фактически единственная возможность обработки массивов данных большой размерности. Многие практические задачи трудно или невозможно решить без использования ДП. Например, при разработке САПР статическое распределение памяти невозможно, т.к. размерность математических моделей в разных проектах может значительно различаться.

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

Адресация динамических переменных осуществляется через указатели. Их значения определяют адрес объекта.

Для работы с динамическими переменными в программе должны быть выполнены следующие действия:

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

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

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

Указатели

Для работы с динамическими программными объектами в Паскале предусмотрен ссылочный тип или тип указателей. В переменной ссылочного типа хранится ссылка на программный объект (адрес объекта).

Указатель – это переменная, которая в качестве своего значения содержит адрес байта памяти.

Объявление указателей

Указатель, связанный с некоторым определенным типом данных, называют типизированным указателем. Его описание имеет вид:

Пример фрагмента программы объявления указателя

Указатель, не связанный с каким-либо конкретным типом данных, называется нетипизированным указателем. Для описания нетипизированного указателя в Паскале существует стандартный тип pointer. Описание такого указателя имеет вид:

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

Значения указателей – адреса переменных в памяти. Адрес занимает четыре байта и хранится в виде двух слов, одно из которых определяет сегмент, второе – смещение.

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

Пример фрагмента программы объявления указателя различных типов

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

Выделение и освобождение динамической памяти

Вся ДП рассматривается как сплошной массив байтов, который называется кучей.

Расположение кучи в памяти ПК.

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

• Heaporg – начало кучи;
• Heapend – конец кучи;
• Heapptr – текущая граница незанятой ДП.

Выделение памяти под динамическую переменную осуществляется процедурой:

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

Пример фрагмента программы объявления указателя различных типов

Графически действие процедуры new можно изобразить так:

Освобождение динамической памяти осуществляется процедурой:

Следует помнить, что повторное применение процедуры 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) Пример описания списка

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

Формирование списка

Чтобы список существовал, надо определить указатель на его начало.

Пример описания списка

Создадим первый элемент списка:

Продолжим формирование списка. Для этого нужно добавить элемент либо в конец списка, либо в голову.

А) Добавим элемент в голову списка. Для этого необходимо выполнить последовательность действий:

• получить память для нового элемента;
• поместить туда информацию;
• присоединить элемент к голове списка.

Б)Добавление элемента в конец списка. Для этого введем вспомогательную переменную, которая будет хранить адрес последнего элемента. Пусть это будет указатель с именем hv (хвост).

Просмотр списка

Удаление элемента из списка

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

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

В)Удаление из конца списка. Для этого нужно найти предпоследний элемент.

Прохождение списка. Важно уметь перебирать элементы списка, выполняя над ними какую-либо операцию. Пусть необходимо найти сумму элементов списка.

Динамические объекты сложной структуры

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

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

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

Наличие в каждом звене двунаправленного списка ссылки как на следующее, так и на предыдущее звено позволяет от каждого звена двигаться по списку в любом направлении. По аналогии с однонаправленным списком здесь есть заглавное звено. В поле Pred этого звена фигурирует пустая ссылка nil, свидетельствующая, что у заглавного звена нет предыдущего (так же, как у последнего нет следующего).

В программировании двунаправленные списки часто обобщают следующим образом: в качестве значения поля Next последнего звена принимают ссылку на заглавное звено, а в качестве значения поля Pred заглавного звена – ссылку на последнее звено:

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

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

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

Программирование

Исходники Pascal (127)

Справочник

Справочник по паскалю: директивы, функции, процедуры, операторы и модули по алфавиту

Часть 1. Массивы и последовательности. Запросы.

Учебное пособие содержит полное описание возможностей языка PascalABC.NET, связанных с динамическими массивами и последовательностями, включая обзор всех запросов для последовательностей, как входящих в стандартную библиотеку платформы .NET (в рамках интерфейса LINQ to Objects), так и разработанных специально для стандартной библиотеки PascalABC.NET. Особое внимание уделяется средствам PascalABC.NET, не имеющим прямых аналогов в стандартной библиотеке .NET, в частности, подпрограммам для генерации, ввода и вывода массивов и последовательностей. Детально обсуждаются особенности последовательностей как структур, выполняющих отложенную обработку данных.

Часть 2. Минимумы и максимумы. Списки, множества, словари, стеки и очереди. Многомерные структуры.

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

Изложение сопровождается многочисленными примерами, причем основная часть примеров представляет собой решения задач из электронного задачника Programming Taskbook, встроенного в систему PascalABC.NET.

Для преподавателей программирования, старшеклассников и студентов.

Лицензия

Авторские права на публикуемые материалы принадлежат автору книги Абрамяну Михаилу Эдуардовичу.

лабораторные работы и задачи по программированию и информатике, егэ по информатике

Стеки

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

Существуют такие сокращения:

LIFO = Last In -> First Out — с английского языка «Кто последним вошел, тот первым вышел»

FILO = First In -> Last Out — «первым вошел, последним вышел»

Последовательные этапы засылки в стек чисел 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;

Рассмотрим подробную работу со стеком на примере:

Алгоритм выполнения задания:

1. изначально стек пустой;
2. в цикле просматриваем каждый символ строки;
3. если текущий символ – открывающая угловая скобка, то вставляем ее на вершину стека;
4. если текущий символ – закрывающая угловая скобка, то проверяем верхний элемент стека: там должна находиться открывающая угловая скобка (иначе — ошибка);
5. в конце стек должен стать пустым, иначе — ошибка.

Создаем структуру стека:

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 Поделитесь уроком с коллегами и друзьями: