Есть материал по теме? высылайте! ваша информация будет размещена здесь!
Автор: Altair 4.10.2004 6:08
Указатель - это переменная, которая в качестве своего значения содержит адрес ячейки памяти.
Указатель связанный с некоторым типом данных, называется типизированным. Для объявления типизированного указателя используется значок ^, который помещается перед типом:
var p1:^integer; { p1 может хранить адрес целого числа } p2:^real; { p2 может хранить адрес вещественного числа }
Также можно объявлять указатель, не связывая его при этом с конкретным типом данных. Для этого существует стандартный тип Pointer:
var pp:pointer;
Указатели такого рода называют нетипизированными. Поскольку они не связаны с конкретным типом, то с их помощью удобно размещать динамические данные, структура и тип которых меняются в ходе работы программы:
var pp: pointer; p1,p2: ^integer; p3: ^real; { ... } Begin { ... } { связь указателей одного типа данных (разрешено) } p1:=p2;
{ попытка присваивания разнотипных указателей (запрещено)} p1:=p3;
{ с нетипизированными указателями таких ограничений не существует.} pp:=p3; p1:=pp;
Казалось бы, а стоило ли вводить ограничения (нельзя присваивать разнотипные указатели), и тут же давать средство для обхода этого ограничения (обмен значений через дополнительную НЕтипизированную переменную)? Стоило !!! Дело в том, что использование обмена через переменную типа Pointer придает языку дополнительную гибкость, но это также требует от программиста дополнительных усилий, и свидетельствует о вполне осознанном действии, а не случайной ошибке. Volvo
Динамическая память - это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (64КБ), стека, и тела программы.
Вся ДП рассматривается как массив байтов, который называется кучей. Она располагается в старших адресах сразу же за областью памяти, которую занимает тело программы.
HEAРORG — начало кучи хранится в этой переменной. HEAPEND — конец кучи. HEAPPTR — текущая граница незанятой динамической памяти.
Память под любую динамически размещаемую переменную выделяется процедурой NEW. Параметром обращения к этой процедуре является типизированный указатель. В результате обращения указатель приобретает значение , соответствующее динамическому адресу, начиная с которого можно разместить данные:
var i:^integer; j:^real; begin new(i);
После выполнения этого фрагмента указатель i приобретает значение, которое перед этим имел указатель кучи HEAPPTR, а сам HEAPPTR увеличивает свое значение на 2, так как внутреннее представление типа integer, с которым связан указатель i, составляет 2 байта.
После того как указатель приобрел некоторое значение, т. е. стал указывать на конкретный физический адрес памяти, по этому адресу можно разместить любое значение соответствующего типа. Для этого сразу за указателем без пробелов ставится значок ^ (указатель разыменовывается), например:
i^:=2;{в область памяти i помещено значение 2}.
Значением любого указателя является адрес, а чтобы указать что речь идет не об адресе, а о тех данных, которые расположены по этому адресу, за указателем ставится ^.
Чтобы вернуть байты обратно в кучу, используется процедура DISPOSE.
DISPOSE(i) — возвращает в кучу 2 байта, которые ранее были выделены указателем i.
Для работы с нетипизированными указателями используются процедуры: GETMEM(P,SIZE) — резервирование памяти. FREEMEM(P,SIZE) — освобождение памяти.
Указательная переменная Р может быть в 3-х состояниях:
Содержать адрес какой-либо переменной, память под которую уже выделена.
Содержать постоянный пустой адрес nil.
Находится в неопределенном состоянии.
В неопределённом состоянии указатель бывает в начале работы программы до первого присвоения ему или конкретного адреса или пустого адреса nil , а также после освобождения области памяти на которую он указывает.
Для организации связей между элементами динамических структур данных, требуется чтобы каждый элемента содержал кроме информационных значений, как минимум один указатель. Отсюда следует, что в качестве элементов таких структур необходимо использовать записи, которые могут объединять в одно целое разнородные элементы.
Type TPtr = ^Telem; Telem = record Inf: Real; Link: TPtr End;
Автор: Altair 5.10.2004 10:56
Списки
Указатели являются простым механизмом, позволяющим строить данные со сложной и меняющейся структурой. Используя указатели можно создавать и обрабатывать структуры данных, компоненты которых связаны явными ссылками.
Самый простой способ связать множество элементов - это расположить их линейно в списке. В этом случае каждый элемент содержит только один указатель на следующий элемент списка.
Пусть тип point описан следующим образом:
Код
Type point = ^item; item = record number: integer; next: point end;
Каждая переменная типа point состоит из двух компонентов: индентифицирующего номера и указателя на следующий элемент. Из этих переменных, связав их указателями, можно создать линейный список.
Способ построения линейного списка: начиная с пустого списка, последовательно добавлять элементы в его начало.
Процесс формирования списка из n элементов:
Код
First: = nil; {начало с пустого списка} While n>0 do begin New(r); r^.Next:=first; r^.Number:=n; First:=r; n := n-1 end;
Основные операции со списками
Просмотр списка Процедура, которая выводит на экран значение поля number элементов списка.
Код
procedure Print (first: point); Var r: point Begin R: = first; While r<>nil do begin Writeln ('number = ' ,r^.Number); R:=r^.Next; end;
Поиск в списке Очень частая операция - поиск в списке элементов с заданным значением ключевого поля X. Так же как в случае файлов, поиск ведется последовательно. Он заканчивается либо когда элемент найден, либо когда достигнут конец списка.
Код
Procedure Search (first: point; x: integer; var q: point); { q - возвращает указатель на найденный элемент; q - nil, если элемента с ключем X в списке нет } var r: point; ok: boolean; begin r: = first; ok: = true; while (r<>nil) and ok do if r^.Number=x then ok:=false else r:=r^.Next; q: = r end;
Включить элемент в список Элемент нужно включить в середину списка после элемента, на который указывает ссылка q. Процедура включения записывается следующим образом.
Код
{включить элемент в середину списка перед q^} Procedure Insert (Var q: point; x: integer); { х - значение информационного поля включаемого элемента } Var r: point; Begin New (r); {размещаем элемент в памяти} R^.Number:=x; {меняем ссылку} r^.next:=q^.Next; q^.Next:=r; end;
Если требуется включить перед элементом q^, а не после него, то кажется, что однонаправленная цепочка связей создает трудность, поскольку нет “прохода” к элементам, предшествующим данному. Однако эту проблему можно решить, используя простой прием, который состоит в том, что новый элемент вставляется после q^, но затем происходит обмен значениями между новым элементом и q^.
Код
{включить элемент в середину списка перед q^} Procedure insert_before (Var q: point; x: integer); Var r: point; Begin New(r); {размещаем элемент памяти} {включаем элемент после q^} r^.Next:=q^.Next; q^.Next:=r; {выполняем обмен значениями} r^.Number:=q^.Number; q^.Number:=x end;
Удалить элемент из списка Предположим, что надо удалить элемент, расположенный после элемента, на который указывает ссылка q.
Код
{удаление элемента из середины списка после q^} Procedure Del (Var q: point); Var r: point; Begin r:=q^.Next; q^.Next:=q^.Next^.next; r^.Next:=nil End;
Если следует удалить элемент на который указывается ссылка q, то следует в начале присвоить элементу q^ значение следующего за ним элемента, а затем этот элемент удалить.
Код
{удаление элемента q^} Procedure Delete(Var q: point); Var r: point; Begin r:=q^.next; q^:=r^; r^.Next:=nil; End;
Обратите внимание на то, что удаляемый из списка элемент остается в памяти и к нему имеется доступ к указателю r, так что в дальнейшем этот элемент можно вставить, например, в другой список. Если требуется освободить занимаемую этим элементом память, то следует выполнить:
Код
{ ... } Dispose(r); r:=nil; { ... }
В присоединенном файле содержится RAR архив с модулем для работы со списками и инструкцией по использованию. В нем описанным все здесь перечисленные операции и еще некоторые. Поддержка списков с заглавным элементом и без него.
Стек— это линейный список с определенной дисциплиной обслуживания, которая заключается в том, что элементы списка всегда включаются, выбираются и удаляются с одного конца, называемого вершиной стека. Доступ к элементам здесь происходит по принципу “последним пришел — первым ушел” (LIFO — last in first out), т.е. последний включенный в стек элемент первым из него удаляется.
Стеки моделируются на основе линейного списка.
Включение элемента вершины стека называется операцией проталкивания в стек, а удаление элемента из вершины стека называется операцией выталкивания из стека.
Для работы со стеками необходимо иметь один основной указатель на вершину стека (Тор) и один дополнительный временный указатель (Р), который используется для выделения и освобождения памяти элементов стека.
В присоединенном файле содержится текст модуля для работы со стекоми и инструкция по использованию модуля (все в архиве)
Очередь — это линейный список, в котором элементы включаются с одного конца, называемого хвостом, а выбираются и удаляются с другого конца, называемого вершиной. Дисциплина обслуживания очереди — “первым пришел — первым вышел” (FIFO — First In First Out), т.е. первый включенный в очередь элемент первым из нее и удаляется.
Очередь — это частный случай линейного односвязного списка для которого разрешены только два действия: добавление элемента в конец очереди и удаление элемента из начала очереди.
Для создания очереди и работы с ней необходимо иметь как минимум два указателя:
на начало очереди
на конец очереди
В присоединенном файле модуль для работы с очередью.
Дек Еще один вариант структуры данных - очередь с двойным доступом, или, как ещё ее называют - двухконечная очередь (Double Ended Queue). Для дека добавление и удаление элементов возможны с обоих концов списка.
С деком возможны следующие операции:
Добавление элемента в "голову" дека
Procedure PushStart(Var Deq: TDeq; Ch: TData);
Добавление элемента в "хвост" дека
Procedure PushFinish(Var Deq: TDeq; Ch: TData);
Изъятие элемента из "головы" дека
Function PopStart(Var Deq: TDeq): TData;
Изъятие элемента из "хвоста" дека
Function PopFinish(Var Deq: TDeq): TData;
В присоединенном файле содержится текст модуля для работы с деком.
Реализация сортировки стека В приведенной ниже программе содержимое стека mainStack переносится в отсортированном виде в resStack с использованием дополнительного стека tmpStack):
Исходный код
Const maxStack = 100; Type TType = Integer; TStack = Record stArr: Array[1 .. maxStack] Of TType; currTop: Integer; End;
Procedure Init(Var s: TStack); Begin s.currTop := 0 End;
Procedure Push(Var s: TStack; x: TType); Begin If s.currTop <> maxStack Then Begin Inc(s.currTop); s.stArr[s.currTop] := x; End; End;
Function Pop(Var s: TStack): TType; Begin If s.currTop <> 0 Then Begin Pop := s.stArr[s.currTop]; Dec(s.currTop); End; End;
Function Top(Var s: TStack): TType; Begin Top := s.stArr[s.currTop]; End;
Function IsEmpty(Var s: TStack): Boolean; Begin IsEmpty := (s.currTop = 0) End;
Procedure Print(Var s: TStack); Var i: Integer; Begin For i := 1 To s.currTop Do Write(s.stArr[i]:4); WriteLn End;
Var mainStack, resStack, tmpStack: TStack; i: integer;
begin Init(mainStack); Init(resStack); Init(tmpStack);
For i := 1 To n Do Push(mainStack, arr[i]); Print(mainStack);
While not IsEmpty(mainStack) Do Begin If IsEmpty(resStack) or (Top(resStack) < Top(mainStack)) Then Push(resStack, Pop(mainStack)) Else Begin While (Top(resStack) > Top(mainStack)) and (not IsEmpty(resStack)) Do Push(tmpStack, Pop(resStack)); Push(resStack, Pop(mainStack)); While not IsEmpty(tmpStack) Do Push(resStack, Pop(tmpStack)) End End; Print(resStack) end.
В присоединенном файле - программа сортировки стека s_stack.pas ( 1.65 килобайт )
Кол-во скачиваний: 8027
Реализация сортировки очереди В примере реализуется сортировка очереди (реализованной в виде объекта) без применения дополнительных очередей.
constructor tqueue.init; begin head := nil; tail := nil; end; destructor tqueue.done; begin while empty do get end;
procedure tqueue.put(x: ttype); var p: ptitem; begin new(p); p^.data := x; p^.next := nil; if empty then head := p else tail^.next := p; tail := p end;
function tqueue.get: ttype; var p: ptitem; begin if not empty then begin p := head; head := head^.next;
get := p^.data; dispose(p); end else begin writeln('reading from empty queue'); halt(102) end; end;
function tqueue.empty: boolean; begin empty := not assigned(head) end;
procedure tqueue.print; var p: ptitem; begin p := head; write('(queue) <'); while assigned(p) do begin write(p^.data, ' '); p := p^.next end; writeln('>') end;
function tqueue.get_count: word; var count: word; p: ptitem; begin p := head; count := 0; while assigned(p) do begin inc(count); p := p^.next end; get_count := count end;
{ А вот и сама сортировка очереди } procedure sort(var q: tqueue); var i, j, k, it, it_next: integer; len: word; begin len := q.get_count; for i := 1 to len do begin it := q.get; for j := 1 to len - i do begin it_next := q.get; if it > it_next then begin q.put(it); it := it_next; end else q.put(it_next) end;
Двусвязный список. Двусвязный список, отличается от односвязного только тем, что каждый узел списка имеет указатель не только на следующий элемент, но и на предыдущий.
Некоторые учебники называют этот вид списка самым удобным, и широко используемым, но это не совсем так, ведь с каждым узлом уходит еще на 1 указатель памяти больше, чем у односвязного.
Тем не менее, использовать двусвязный список удобнее - потерять начало списка просто невозможно!
Все основные операции для двусвязных списков,похожи на операции с односвязными, но за счет добавления еще одного указателя, в код вносятся некоторые изменения. В присоединенном файле модуль DList для работы с двусвязными списками. А вот программа, тестирующая модуль и демонстрирующая его возможности.
(одно из возможных расширений модуля - добавление функции поиска элемента, функции удаления элемента, добавленияв начало, и процедуры переворота...).
uses crt, dlist; var l:tlist; begin writeln('Программа,тестирующая модуль DList для работы с двусвязными списками'); writeln('Добавляем первый элемент,список инициализируется автоматически...'); InitListAndAddFirst(1,L); writeln('Теперь добавим элемент 2 после того,на который указывал L... (AddAfter)'); AddAfter(2,l); writeln(' ... и перейдем к концу списка, чтобы добавлять после последнего...(GotoLast)'); GotoLast(l); AddAfter(3,l); GotoLast(l); {... } AddAfter(4,l); GotoLast(l); { ... } AddAfter(5,l); GotoLast(l); { ...} writeln('Полученный список (после добавления в конец) (listprint)'); ListPrint(L); writeln('... вставим после 4 элемент 6'); writeln('Для этого идем в начало списка(GotoFirst) и ищем элемент 4 ... '); gotoFirst(l); {в начало} while (l^.data<>4)and (l^.next<>nil) do l:=l^.next; {ищем} writeln; writeln('Нашли, добавляем... '); addafter(6,l); writeln('...вот, что у нас получилось (ListPrint) :'); ListPrint(L); writeln('Уничтожаем список, очищая память. (ListDestroy)'); ListDestroy(L); end.
Во многом эти списки похожи на обычные двухсвязные, за одним исключением: они закольцованы, т.е., последний элемент в таком списке ссылается на первый. Это вносит свои коррективы в алгоритм добавления элемента к кольцевому списку.
Для описания элемента списка будем пользоваться следующей структурой:
type myType = integer; Ring = ^TRing; TRing = record info: myType; next: Ring; prev: Ring; end;
Добавление элемента
Добавляться новые элементы будут перед элементом, помеченным как first (то есть, перед "головой" списка) по следующему алгоритму:
Поскольку выделение памяти под новый элемент должно производиться независимо от того, пуст список или в нем уже есть элементы, то сделаем это в самом начале процедуры добавления, еще перед проверкой на пустоту списка.
В зависимости от того, пуст наш кольцевой список или уже частично заполнен, дальнейшее выполнение процедуры пойдет по одному из двух путей:
2а) список пуст - устанавливаем указатели prev и next на новый элемент и "помечаем" его как первый (First)
2б) список не пуст - действовать нужно по-другому:
поскольку добавляем в "конец" списка (перед элементом first), то поле next нового элемента указывает на "голову" списка, а поле prev - туда, куда раньше указывал prev "головы";
не забываем про "бывший последним" элемент (элемент на который раньше указывал first^.prev). Поле next этого элемента должно указывать на добавляемый элемент, поскольку новый добавляется после "последнего" (перед "первым");
ну, и наконец, "голова" списка должна теперь указывать prev-ом на новый элемент, он ведь находится в списке ПЕРЕД "головой"...
.
procedure Append(var First: Ring; value: myType); var p: Ring; begin { 1 } new(p); p^.info := value;
if first = nil then begin { 2а } p^.next := p; p^.prev := p; first := p; end else begin { 2б } p^.next := first; p^.prev := first^.prev; first^.prev^.next := p; first^.prev := p; end; end;
Удаление элемента
При удалении элемента из кольцевого списка также рассматриваем два случая:
Список содержит один элемент: проверяем, нужно ли удалять этот элемент, и если нужно - просто удаляем его, и обнуляем First, нет элементов - нет "головы" списка.
Список содержит несколько элементов: переназначаем указатели prev^.next и next^.prev удаляемого элемента так, чтобы ни предыдущий ни последующий элементы больше на P не указывали. После этого проверяем, не удаляется ли "головной" элемент (First), и в случае положительного ответа "продвигаем" First на один элемент вперед (если этого не сделать, то после удаления элемента P указатель на "голову" станет невалидным и его использование приведет к получению неправильных результатов). И только после того, как все вышесказанное выполнено, можно удалять элемент списка, на который указывает P...
{ Удалить из списка, начинающегося с First, элемент, на который указывает P } procedure RemoveItem(var First: Ring; p: Ring); begin if (first^.next = first) and (p = first) then begin dispose(first); first := nil; exit; end;
p^.prev^.next := p^.next; p^.next^.prev := p^.prev; if p = first then first := p^.next; dispose(p); p := nil; end;