Методичка С++ (DINAMICO)

Посмотреть архив целиком

15



Иванова Г.С., Ничушкина Т.Н.

Конспект лекций

по курсу "Алгоритмические языки и программирование".

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

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

Под эту категорию подпадают все переменные и константы, объявленные в Паскале и обозначенные идентификаторами. Это определяется статической структурой Паскаль - программы, обуславливающей расположение ее объектов в непрерывной области памяти длиной не более 64к, называемой сегментом данных, к которому примыкает стек размером 16к.

Однако, помимо привычной схемы, Паскаль дает возможность образовывать новые переменные в любой момент работы программы без учета ее статической структуры, сообразуясь с потребностями решаемой задачи. Точно также допускается уничтожение созданных переменных в произвольный момент выполнения. Переменные, созданием и уничтожением которых может явно управлять программист, называются динамическими. Память для таких переменных берется из свободной, называемой «кучей», размер которой составляет ~ 200 ~300к. Эта цифра получится, если из общей памяти вычесть размер, занятый системными компонентами и самой программой на Паскале.

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

1.1 Адресация оперативной памяти. Указатели.

Наименьшей адресуемой единицей памяти ПЭВМ является байт. Для обращения к конкретному байту необходимо иметь адрес .

Здесь адрес конкретного байта определяется как А=Аб+смещение, где Аб - адрес сегмента. Физический адрес при этом определяется Аф=Аб*16+смещение.

Для формирования адреса в МП 80386 и выше используются 32 разряда, что составляет 2 слова типа word. Первое слово содержит адрес сегмента, второе - адрес смещения внутри сегмента.

Сегмент - это непрерывный участок памяти, имеющий длину 64к и начинающийся с адреса, кратного 16 ( 0,16,32,.....).

Смещение - это количество байт, которое нужно отступить от начала сегмента, чтобы определить конкретный адрес.

Параграф - фрагмент памяти длиной 16 байт.

Сегмент адресует память до параграфа, а смещение - до байта. Каждому сегменту соответствует отдельно адресуемая непрерывная область памяти. Сегменты могут следовать один за другим без промежутка, с некоторым интервалом или перекрывать друг друга.

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


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

Примеры объявления указателей представлены ниже:

VAR p1:^integer; {типизированный указатель или указатель целого типа}

p2:^real; {типизированный указатель или указатель вещественного типа}

p3:^char; {типизированный указатель или указатель символьного типа}

p: pointer; {нетипизированный указатель или указатель неопределенного типа}

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

TYPE point1=^integer;{новый ссылочный тип - указатель на целое}

point2=^char; {новый ссылочный тип - указатель на символ}

VAR p1:point1; {переменная ссылочного типа point1}

p2:point2; { переменная ссылочного типа point2}


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

TYPE ppointer = ^percon; {тип person еще не определен}

percon = record { определение типа person}

name: string: next: ppointer;

end;

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

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

1.Присваивание. Указателю присваивается значение другого указателя. Допускается присваивать указателю только значение того же или неопределенного типа. Например:

VAR p1,p2:^integer;

p3:^real;

p: pointer;

.Допустимые операции Недопустимые операции

p1:=p2; p:=p3; p1:=p3;

p1:=p; p1:=p; p3:=p2;

2. Доступ к переменной по указателю (операция разыменования). Чтобы получить доступ к переменной по указателю, необходимо после переменной - указателя поставить знак «. При этом значение имеет тип, совпадающий с базовым типом указателя. Например:

p1^ - означает « переменная, на которую указывает p1». Так как p1 указатель на целое, то p1^ - -это значение целой, расположенной по адресу p1.Если написать

p1^:=2; то содержимое ячейки памяти, адресуемой указателем станет равным 2.

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

p1^:=p^+2;

При этом содержимое ячейки изменится и станет равным 4.

3. Взятие указателя. Это унарная операция, которая строится из знака операции - символа @ (амперсанд) и одного операнда - переменной любого типа. Например, если имеется описание:


TYPE p =^integer;

VAR p1:p;

i: integer;

.....то последовательность операций

p1:=@i;

p1^:=2;

приведет к присвоению переменной i значения 2.

4. Отношения. Это бинарные операции сравнения указателей на равенство и неравенство. Операции проверяют, ссылаются ли два указателя на одну и ту же область памяти, и обозначаются обычным образом - знаком «=» и «<>». Например:

sign:=p1=p2 { sign приобретает значение true или false в зависимости от значений указателей}

if p1<> nil then ...

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

Если описать переменную pp1, используя предыдущий пример, следующим образом:

VAR pp1:^p1;

то в качестве своих возможных значений она получит множество указателей, ссылающихся на целые значения. Применив операцию

pp1:=@p1; мы получим связи, изображенные на схеме.

Для получения значения ячейки i, необходимо дважды применить операцию разыменывания. В нашем случае pp1^^ - имеет тип integer и равно 2.

  1. Процедуры и функции, работающие с указателями.

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

Таблица 1.

Вызов функции

Тип функции

Результат

1.

ADDR(x}

pointer

Возвращает адрес аргумента. (имя пер., функции, процедуры). Аналогична операции - @.

2.

SEG(x]

word

Возвращает адрес сегмента указанного объекта.

3.

OFS(x)

word

Возвращает смещение адреса указанного объекта.

4.

CSEG

word

Возвращает текущее значение регистра адреса программного сегмента - CS.

5.

DSEG

word

Возвращает текущее значение регистра адреса сегмента данных - DS.

6.

PTR(seg,ofs)

pointer

Возвращает значение указателя по заданным seg и ofs.

7.

SIZEOF(x)

word

Возвращает длину указанного объекта в байтах.



  1. Управление динамической памятью.

Определяемые в примерах предыдущих разделов указатели, для простоты объяснения, содержали адреса некоторых статических объектов. Однако, основное назначение указателей - это адресация динамических объектов. Для динамических объектов программист заказывает память требуемого размера из динамической памяти. Вся динамическая память в Паскале рассматривается как подобная стеку структура, называемая «кучей». Физически «куча» располагается в старших адресах, сразу за областью, занимаемой программой. Схема распределения оперативной памяти представлена на рис.1.


Рис. 1.

На рисунке HeapOrg - указатель на начало динамической области

HeapEnd - указатель на конец динамической области

HeapPtr - указатель на текущее значение границы свободной динамической области

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

1. Наиболее распространенный способ - использование процедуры или функции new. Вызов осуществляется следующим образом:

процедуры - NEW (<имя переменной ссылочного типа >);

<имя переменной ссылочного типа>:=NEW(<ссылочный тип >);

Примеры использования:

TYPE p = ^integer;

pa = ^real;

VAR pp : p;

ppa :pa;

.......................

new(pp); {динамическая область вся доступна pp = HeapOrg, HeapPtr=HeapOrg+2}

pp^ := 5; {по адресу заносим число 5 }

ppa: = new(pa); {в памяти уже есть число 5 типа integer, поэтому ppa=HeapOrg+2

HeapPtr=HeapPtr+6, так как тип указателя pa - real длиной 6 байт}

ppa^ :=35.5;

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

Процедура DISPOSE(<имя переменной ссылочного типа >)

Для переменных из предыдущего примера процедура вызывается так:

dispose(pp);

dispose(ppa);

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

Чередование обращений NEW и DISPOSE может привести к фрагментации памяти. Для уменьшения этого явления можно использовать процедуры MARK и RELEASE.

MARK - запоминает значение в переменной указателе, определенном в качестве параметра.

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

New(p1);

new(p2);

mark(p);

new(p3);

new(p4);

release(p);

Следует заметить, что совместное использование процедур Dispose и Release недопустимо.

  1. Динамическую память можно выделять фрагментом указанного размера. Для этой цели в Паскале используется процедура GetMem (p,size).

Эта процедура запрашивает у системы память требуемого размера. Указанного в параметре size (запрашиваемый объем не должен превышать 64к) и помещает адрес выделенного системой фрагмента в переменную типа указатель с имеем p. После использования память обязательно нужно освободить процедурой FreeMem (p,size), которая по адресу указателя p освобождает фрагмент размером size.

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

Избежать подобной ситуации можно несколькими способами.

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

Maxavail: longint; возвращает размер максимального непрерывного участка памяти

Memavail: longint; возвращает размер всей свободной памяти, состоящей из суммы всех свободных фрагментов.

Второй способ заключается в возможности перехватить системную ошибку. Для этого необходимо определить свою подпрограмму обработки ошибки, в которой вместо признака ошибки HeapFunc:=0 (0 означает ошибку использования динамической памяти), необходимо задать Heapfunc:=1. Пример такой подпрограммы приведен ниже:

{$F+}

FUNCTION HeapFunc (size: word) : integer: far;

begin HeapFunc: =1; end;

{$F-}

В программе необходимо определить адрес подпрограммы обработки ошибки, который задается с помощью операции взятия адреса HepError:=@HeapFunc . Использование такой подпрограммы приведет к тому, что процедуры New и GetMem вернут указатель nil и выполнение программы не будет прервано. Управление система передаст в программу в точку возврата из процедуры, в которой возникла ошибка. Именно здесь пользователь имеет возможность сам решить, как поступить при наличии такой ошибки.

Пример 1. Программа подсчитывает сумму элементов массива большой размерности. Для размещения такого массива потребуется n*m*6 байт памяти. Нетрудно подсчитать, что одного сегмента здесь явно не хватит. Использование динамического массива по схеме указатель на элемент требует n*m*4 байта памяти, что превышает, при больших n и m (например при n=200,m=200), 64к. Решение можно найти, если подойти к массиву как к массиву строк, где каждая строка адресуется отдельным указателем, как указано на схеме.

Тогда одного сегмента достаточно для адресации 64000байт/4=16000 строк. Так как указатель может адресовать целый сегмент, то в каждой строке можно разместить 64000байт/6=10677. Однако эти цифры достижимы только при наличии доступной памяти. Поэтому в программе осуществляется проверка наличия доступной памяти путем перехвата ошибки, которую выдает система при отсутствии памяти, с помощью собственной функции обработки ошибок



program ex_large_mas;

const

nn=16000; {в сегменте длиной 64к можно разместить 64к/4 = 16000 указателей длиной 4б}

var

i,j,n,m:word;

ptrstr:array[1..nn] of pointer; {статический массив указателей на строки по m элементов в строке}

s:real;

type

realpoint=^real;

{функция возвращающая указатель на вещественное число по адресу его сегмента и смещения }

function addrR(i,j:word):realpoint;

begin

addrR:=ptr(seg(ptrstr[i]^),ofs(ptrstr[i]^)+(j-1)*sizeof(real))

end;

{ пользовательская функция обработки ошибок}

{$F+}

function heapfunc(size:word):integer;

begin heapfunc:=1; end;

{$F-}

begin randomize;

heaperror:=@heapfunc;{подключение пользовательской функции обработки ошибок}

writeln('Введите n,m');

readln(n,m);

for i:=1 to n do

begin getmem(ptrstr[i],m*sizeof(real));{запрос на память под строку вещественных чисел}

if ptrstr[i]=nil then begin {если памяти не хватает то выйти }

writeln(' Нет места в "куче"');

for j:=1 to i-1 do

freemem(ptrstr[j],m*sizeof(real)); {освободить уже выделенную память}

halt(2); end;

for j:=1 to m do addrR(i,j)^:=random; {если память есть заполнить массив случайными числами}

end;

s:=0;

for i:=1 to n do

for j:=1 to m do

s:=s+addrR(i,j)^;

writeln('Значение суммы =',s:15:10);

writeln('Среднее значение =',s/(n*m):15:10);

for i:=1 to n do

freemem(ptrstr[i],m*sizeof(real)); {освободить использованную память }

end.


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

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

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

Например:

TYPE ukzap = ^element; {ссылочный тип - указатель на запись}

element = record {новый тип - элемент, представляет собой запись о студенте}

name: string[16]; {фамилия}

b1,b2,b3: 2..5; {три отметки по экзаменам}

p: ^real; {указатель на вещественное число - размер стипендии}

next: ukzap; {переменная ссылочного типа ukzap - указатель на след. элемент}

end;

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

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

Элемент такого списка можно описать, как в ранее описанном примере:

TYPE ukzap = ^element;

element = record

name: string[16];

telefon:string[7];

next: ukzap;

end;

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

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


Элемент такого списка можно описать, используя ранее введенное определение:

TYPE ukzap = ^element;

element = record

name: string[16];

telefon:string[7];

next: ukzap;

pred:ukzap;

end;

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

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

а.) у первого элемента списка указатель на предыдущий элемент должен отсутствовать, так как такового у первого элемента нет и поэтому указатель pred устанавливается равным nil.

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

  1. N - связные списки. Каждый элемент такого списка содержит n полей ссылочного типа Указатели, определенные с помощью этих полей, предназначены для хранения адресов расположения в памяти элементов списка. Элемент такого списка можно описать следующим образом:

TYPE ukzap = ^element;

element = record

name: string[16];

telefon:string[7];

uk1: ukzap;

uk2:ukzap;

..................

ukn: ukzap;

end;


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

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

Стек - динамический список (односвязный или двусвязный), и добавление нового элемента в который, и удаление очередного элемента списка осуществляется только с первого элемента списка. При этом первый элемент принято называть вершиной стека. Это позиция, в которой находится последний по времени поступления в стек элемент. Он же является тем элементом, который можно выбрать из стека. Выбранный элемент удаляется из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранным из него элементом.

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

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

Наиболее интересными манипуляциями со списками являются:


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





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

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

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

program ex_ochered;

type ukp=^cpisel; {указатель на элемент списка}

cpisel= record { запись типа «элемент списка»}

inf:integer;

p:ukp

end;

var spis:boolean;

pb:ukp; {первый элемент списка}

k,l:integer;

procedure formspsl(n:integer;var pob:ukp);

{процедура формирование списка целых чисел в виде очереди с помощью датчика случайных чисел}

var i,c:integer;

po, { текущий элемент списка}

poe:ukp; { последний элемент списка}

begin

randomize;

c:=random(20);

new(po); {запрос на выделение памяти для размещения элемента списка}

pob:=po; {фиксация адреса первого элемента}

poe:=po; {фиксация последнего элемента списка}

po^.inf:=c; {занесение информации в элемент списка}

po^.p:=nil; {занесение в поле указателя элемента списка адреса nil}

for i:=2 to k do {цикл добавления остальных элементов}

begin

new(po);

c:=random(20);

po^.inf:=c;

po^.p:=nil;

poe^.p:=po; {занесение в поле указателя последнего элемента адреса очередного}

poe:=po {текущий элемент становится последним элементом}

end;

end;

procedure udalsp(l:integer;var pob:ukp;var spis:boolean);

{ удаление всех элементов списка, кратных l }

var po,pot:ukp;

begin

spis:=true;

while ((pob^.inf mod l)=0) and (pob^.p<>nil) do {цикл, пока первый элемент списка кратен l и не конец списка}

begin

po:=pob;pob:=pob^.p;

dispose(po)

end;

po:=pob;pot:=pob;

while po^.p<>nil do begin {пока не конец списка}

if (po^.inf mod l)=0 then begin {если элемент кратен l}

pot^.p:=po^.p;dispose(po);

po:=pot^.p end

else begin

pot:=po;po:=po^.p end

end;

if po=pob then begin {если остался один первый элемент и он кратен l}

if (po^.inf mod l )=0 then

begin

dispose(pob);

writeln(' список ликвидирован ');

spis:=false;

end end

else begin

if (po^.inf mod l)=0 then begin {если последний элемент кратен l}

pot^.p:=po^.p;

dispose(po); end

end;

end;

procedure pechsp(pob:ukp);

var po:ukp;

{процедура печати сформированного в виде очереди списка }

begin

po:=pob; {присвоение текущему указателю адреса начала списка}

while po^.p<>nil do {цикл пока не конец списка}

begin write(po^.inf:5); {печать информации элемента списка}

po:=po^.p {переадресация на следующий элемент}

end;

writeln(po^.inf:5);

end;


{ Основная программа }

begin

{ формирование списка}

writeln(' введите длину списка k <= 15');

readln(k);

formspsl(k,pb);

{ печать сформированного списка }

writeln(' сформированный список ');

pechsp(pb);readln;

writeln('введите число для удаления кратных ему');

readln(l);

udalsp(l,pb,spis);

{ печать списка после удаления чисел кратных l}

if spis then begin

writeln(' список после удаления чисел, кратных ',l:5);

pechsp(pb);end;

readln

end.

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

program spisok2;

type

point2=^dvspis; { указатель на элемент двунаправленного списка}

str1=string[20]; { элемент двунаправленного списка}

dvspis=record

fam:string;

pred,posl:point2

end;

var first, { указатель на начало списка}

last:point2; { указатель на конец списка}


function fio(ss:str1):str1;

{функция выравнивания фамилии по левой границе}

var i:integer;

begin

for i:=length(ss)+1 to 20 do

ss:=ss+' ';

fio:=ss

end;

{ процедура печати списка в прямом направлении }

procedure pechspf(f:point2);

var q:point2;

begin

q:=f;

writeln(' печать списка в прямом направлении ');

while q<>nil do begin

writeln(fio(q^.fam));

q:=q^.posl

end

end;

{ процедура печати списка в обратном направлении }

procedure pechspl(l:point2);

var q:point2;

begin

q:=l;

writeln(' печать списка в обратном направлении ');

while q<>nil do begin

writeln(fio(q^.fam));

q:=q^.pred

end

end;

procedure formspd(var first,last:point2); {процедура формирования двунапрвленного списка}

var

tek,tk:point2; { рабочие указатели списка}

st:str1;

i,j:integer;

begin

writeln(' введите фамилию из списка в конце списка - пустая строка');

{ начало формирования списка в процедуре}

readln(st); {чтение очередной фамилии}

new(tek); {запрос памяти под текущий элемент}

tek^.fam:=st; {заполнение информационного поля текущего элемента}

tek^.pred:=nil; {заносим в указатель на предыдущий элемент nil}

tek^.posl:=nil; {заносим в указатель на последующий элемент nil}

first:=tek; {запоминаем значение адреса первого элемента списка}

tk:=first; {запоминаем адрес элемента как предыдущего}

readln(st);

while length(st)<>0 do {цикл пока есть фамилии}

begin

new(tek); {запрос памяти под текущий элемент}

tek^.fam:=st;

tek^.posl:=nil; {заносим в указатель на последующий элемент nil}

tek^.pred:=tk; {заносим в указатель на предыдущий элемент текущего элемента адрес предыдущего}

tk^.posl:=tek; {заносим в указатель на последующий элемент предыдущего элемента адрес текущего}

tk:=tek; {текущий элемент становится предыдущим}

readln(st);

end;

last:=tk; {последний текущий запоминаем как последний элемент списка}

{ конец формирования списка в программе}

end;

{ Основная программа}

begin

formspd(first,last);

pechspf(first);

pechspl(last);

readln;

end.

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

program stek;

type point=^zap; {указатель на запись о деталях}

zap=record {запись о деталях}

det:string[10];

diam:real;

p:point;

end;

var r,q,f:point;

a:zap;

c:integer;

begin {формирование стека}

new(r); {запрос на память}

r^.p:=nil; {запись в указатель признака конца списка}

writeln('Вводите названия деталей и диаметры в порядке:');

writeln(' название детали диаметр ');

writeln(' для окончания набрать название детали - end ');

readln(r^.det,r^.diam); {данные о деталях}

read(a.det);

while a.det<>'end' do

begin readln(a.diam);

q:=r; {запоминаем новый элемент как вершину стека}

new(r); {выделяем память под новый элемент}

r^.det:=a.det;

r^.diam:=a.diam;

r^.p:=q; {заносим адрес старой вершины в указатель нового элемента}

read(a.det);

end;

{ Конец формирования списка }

q:=r; {сохранение вершины стека}

c:=0;

repeat

if q^.diam<1 then {если элемент следует удалить}

begin

if c=0 then begin r:=r^.p; q:=r end {удаление "верхнего" элемента}

else begin q:=q^.p; f^.p:=q end {удаление следующего элемента}

end

else begin {элемента не удаляется}

f:=q; q:=q^.p; c:=1 end;

until q=nil; {пока не конец списка}

{фрагмент печати стека с оставшимися элементами}

q:=r; {пересохранение вершины стека}

if q=nil then writeln('список пуст, все детали удалены')

else

while q<>nil do

begin writeln(q^.det:11,q^.diam:5:1);

q:=q^.p;

end;

end.

Пример 5. Программа реализует игру "считалка" используя кольцевой список. В кругу стоят n человек. Каждый раз из круга выходит человек, на которого падает номер m. Счет начинается со следующего. Водит оставшийся. Определить кому "водить". Решение задачи использует особенность всех считалок - характеристическое число. Это число определяется количеством слов считалки. Его можно определить путем простого подсчета слов считалки, введенной с клавиатура. А можно просто ввести это число непосредственно с клавиатуры, что и сделано в программе.

program exkolco;

Function Play(n,m:integer):integer;

type child_ptr=^child;

child=record

name:integer;

p:child_ptr;

end;

var First,Next,Pass:child_ptr;

j,k:integer;

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

new(First);

First^.name:=1;

Pass:=First;

for k:=2 to N do

begin new(Next);

Next^.name:=k;

Pass^.p:=Next;

Pass:=Next;

end;

{ Замыкание круга }

Pass^.p:=First;

{ Повторение считалки N-1 раз }

Pass:=First;

for k:=n downto 2 do

begin for j:=1 to m-1 do

begin Next:=Pass;

Pass:=Pass^.p;

end;

writeln(Pass^.name);

Next^.p:=Pass^.p;

dispose(Pass);

Pass:=Next^.p;

end;

Play:=Pass^.name;

end;

var n1,m1: integer;

begin

writeln(‘введите количество игроков и характеристическое число считалки’);

readln(n1,m1);

writeln('Водит игрок ',play(n1,m1):6);

end.

  1. Бинарные деревья.

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


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


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

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

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

в) два указателя на вершину влево вниз и на вершину вправо вниз (указатели на корни двух поддеревьев этого узла).

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

Существуют определенные правила работы с бинарными деревьями. Различают следующие операции:

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

Рассмотрим пример формирования бинарного дерева на примере последовательности целых чисел. Пусть дана следующая последовательность целых чисел {10, 2, 4, 11, 15, 3, 6, 8, 1, 2, 5}.Тогда дерево, сформированное по правилам добавления новых элементов, представлено на схеме ниже.



2.Удаление записи с указанным ключом. Непосредственное удаление записи реализуется в зависимости от того, какая вершина удаляется. Можно выделить 4 случая:

а) Удаляемая вершина отсутствует. Выдается соответствующее сообщение.

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

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

г) Удаляемая вершина содержит две ветви, исходящие из нее. В Этом случае нужно найти подходящий узел, который можно вставить на место удаляемого, причем этот подходящий узел должен легко перемещаться. Такой узел всегда существует: это либо самый правый элемент левого поддерева, либо самый левый элемент правого поддерева удаляемого узла. Для иллюстрации рассмотрим предыдущий пример. Пусть из дерева необходимо удалить узел, содержащий элемент с числом 4. Удаляемый узел содержит две ветви. По правилу ищем подходящий для замены удаляемого узла. В левой подветви правого элемента нет. Переходим к правой подветви. Крайний левый элемент - узел 5. Именно он заменит узел 4. После преобразования дерево выглядит как показано на схеме слева.

Если вершин, удовлетворяющих условию удаления, в дереве может оказаться несколько, следует заранее обговорить ситуацию. Действия могут быть следующими:

  • удаляется первая, обнаруженная вершина:

  • удаляется последняя, обнаруженная в дереве вершина:

  • удаляются все удовлетворяющие условию вершины.

2.Поиск записи в дереве. В этом случае от корня просматривается дерево по следующему алгоритму. Если значение ключа в искомом узле меньше чем в корневом, то поиск переходит в левую подветвь. Если больше или равно - то в правую подветвь. И так в каждом следующем узле до тех пор, пока не отыщется искомый узел. Узел может отсутствовать. Тогда выдается соответствующее сообщение. В противном случае узел помечается как найденный (запоминается его адрес. После этого узел может обрабатываться в соответствии с алгоритмом программы).

  1. Сортировка с использованием дерева. Так как дерево формируется по определенным выше правилам, то сортировка данных, находящихся в дереве, осуществляется соответствующим обходом дерева. Для этого обход начинается с корня. Затем обходятся все левые элементы левых ветвей, а если таких нет то фиксируется значение соответствующей вершины и просматриваются правые узлы. В этих узлах опять просмотр начинается с левых элементов. После того, левое поддерево просмотрено, осуществляется переход к правому поддереву. В нем алгоритм поиска повторяется. Ниже приводится пример формирования и сортировки с помощью бинарного дерева. Представлены полный и рекурсивный варианты обхода бинарного дерева.

Пример 6. Программа строит бинарное дерево из вводимых с клавиатуры целых чисел, а затем осуществляет обход дерева для печати отсортированных данных.

program sort;

const lim=100; { максимальная "глубина" дерева }

type top_ptr=^top; {указатель на вершину дерева}

top=record {вершина дерева - запись, содержащая целое число и указатели на левое и правое поддеревья этой вершины}

value:integer;

left,right:top_ptr;

end;

var next_number:integer;

r:top_ptr;

{процедура добавления новой вершины в дерево }

procedure add(r:top_ptr;n:integer);

var pass,succ:top_ptr;

begin pass:=r;

while pass<>nil do {ищется вершина, после которой надо вставить новую}

begin succ:=pass;

if n

else pass:=pass^.right;

end;

new(pass); {создание нового элемента}

with pass^ do

begin value:=n;

left:=nil;

right:=nil;

end;

if n {подсоединение нового элемента}

else succ^.right:=pass;

end;

{Процедура сортировки - нерекурсивный вариант обхода бинарного дерева}

procedure tree1(r:top_ptr);

var pass:top_ptr;

mem_top:record {имитация стека для хранения указателей}

nom:0..lim; {глубина дерева}

adres:array[1..lim] of top_ptr;{массив указателей на вершины}

end;

begin pass:=r; {корень дерева}

with mem_top do {ищется самый левый узел}

begin nom:=0;

while (pass<>nil) or (nom<>0) do {цикл пока указатель не nil}

if pass<>nil then

begin

if nom=lim then {проверка достаточности места в массиве}

begin writeln('Увеличьте lim');

exit;

end;

nom:=nom+1; {увеличить указатель стека на 1}

adres[nom]:=pass; {запомнить в стеке указатель на число}

pass:=pass^.left; {перейти к левой подветви}

end

else begin pass:=adres[nom]; {если указатель nil, восстановить указатель из стека}

nom:=nom-1; {уменьшить стек на 1, удалив из него то что напечатали}

write(pass^.value:4); {напечатать значение величины}

pass:=pass^.right; {переход к правой пподветви}

end;

end;

end;

{процедура сортировки - рекурсивный вариант обхода дерева}

procedure tree2(r:top_ptr);

begin

if r<>nil then begin

tree2(r^.left);

write(r^.value:4);

tree2(r^.right);

end;

end;

{основная программа}

begin {формирование исходного дерева}

writeln('Введите числа');

read(next_number);

new(r);

with r^ do

begin value:=next_number;

left:=nil;

right:=nil;

end;

read(next_number);

while not EOF do

begin add(r,next_number); {вызов процедуры добавления элемента в дерево}

read(next_number)

end;

readln;

writeln('Последовательность по нерекурсивному варианту:');

tree1(r);

writeln;

writeln('Последовательность по рекурсивному варианту:');

tree2(r);

writeln

end.


Как вывод следует отметить, что использование бинарных деревьев при сортировках позволяет достичь эффективности алгоритма, близкого к эффективности дихотомического (двоичного) поиска. Особенно эффективна работа в случае сбалансированного бинарного дерева. Сбалансированным является бинарное дерево, у которого обе ветви одинаково «ветвисты». Для приведения дерева к сбалансированному виду существуют специальные алгоритмы балансировки. Кроме того, некоторые алгоритмы трансляции выражений, использующиеся в компиляторах для преобразования формул в форму, понятную компьютеру, используют бинарные деревья. Однако, вследствие сложности и объемности подобных алгоритмов, в данную методическую разработку они не включены.


Случайные файлы

Файл
33141.rtf
en.doc
33569.rtf
150615.rtf
1891-1.rtf