Лабораторная работа N9
ДИНАМИЧЕСКАЯ ПАМЯТЬ
1. ЦЕЛЬ РАБОТЫ: изучение динамических структур данных на примере односвязных списков, процедур для выделения и освобождения памяти.
2. ОСНОВНЫЕ СВЕДЕНИЯ
Рассмотренные ранее структуры данных являлись статическими. Это означает, что память под эти данные выделялась на этапе компиляции. Такое выделение памяти не всегда удобно, т.к. заранее трудно предвидеть, например, размер массива для сортировки или число уравнений в системе. Поэтому в Турбо Паскале существует возможность выделения памяти не на этапе компиляции, а на этапе исполнения программы - динамическая память.
Процедура выделения памяти связана с процедурой ее освобождения после использования. В Турбо Паскале имеется три пары процедур выделения-освобождения памяти: New - Dispose, GetMem - FreeMem, Mark - Release. Чаще всего используется пара New для выделения памяти и Dispose для ее освобождения. Подчеркнем, что использование Dispose для освобождения выделенной динамической памяти не является обязательным, после выхода из программы динамическая память освобождается автоматически, но частое использование процедуры выделения памяти без ее освобождения может привести к состоянию невозможности дальнейшего выделения памяти и к остановке программы.
Рассмотрим работу с динамической памятью на примере односвязного списка. Такой список содержит записи с информационной частью (например, фамилия, имя, отчество, адрес, номер телефона и т.д.) и ссылочной частью (например, адрес следующей или предыдущей записи). Такой список принципиально отличается от массива тем, что в массиве записи упорядочены, удаление одной записи приводит к необходимости переписывать остальные записи на место предыдущих, в то время как в связном списке следует лишь переставить указатель. Число записей в массиве фиксировано, в связном списке - нет.
program spisok;{односвязный список}
type uk=^rec;
rec = record
fio : string[15];{ ФИО пациента}
davl : integer; { давление}
v : uk { указатель на следующую запись}
end;
var tek, pred, perv, rab : uk; {указатели на текущую, предыдущую,
первую, рабочую записи}
k : integer;
begin
{ввод 5 записей пациентов}
new (tek); {выделение памяти}
write ('введите фамилию пациента: '); readln (tek^.fio);
write ('введите давление: '); readln (tek^.davl);
tek^.v := nil; {следующей записи пока нет}
pred:=tek; perv:=tek;
for k:=2 to 5 do
begin
new (tek); {выделение памяти}
pred^.v := tek;
write ('введите фамилию пациента: '); readln (tek^.fio);
write ('введите давление: '); readln (tek^.davl);
tek^.v:=nil; {следующей записи пока нет}
pred:=tek;
end;
{удаление записей пациентов с давлением большим 140}
tek:=perv; {указатель-на начало списка}
pred:=nil; {предыдущей записи пока нет}
while tek<>nil do
begin
if tek^.davl>140 then
begin
rab:=tek;
if tek<>perv then pred^.v:=tek^.v
else perv:=tek^.v;
if tek^.v=nil then {запись последняя}
if tek<>perv then{список не пуст}
pred^.v:=nil else {список пуст} perv:=nil;
dispose (rab);
end
else pred:=tek;{переставляем указатель предыдущей записи, если текущую запись не удаляли}
tek:=tek^.v; {переход к следующей записи}
end;
{печать оставшихся записей}
writeln ('Оставшиеся записи в односвязном списке');
if perv<>nil then {список не пуст} begin
tek:=perv;
while tek<>nil do
begin
writeln('ФИО ',tek^.fio,' давление ', tek^.davl);
tek:=tek^.v {переход к след. записи}
end end
end.
В данной программе rec - запись, содержащая сведения о пациенте: fio - фамилия, имя, отчество (15 символов), davl - давление (целое число), v - указатель на следующую запись. Тип указатель занимает в памяти 4 байта (2 байта сегментный регистр, 2 байта смещение), независимо от размера переменной, на которую он указывает. При описании типа указателя uk : ^rec; допускается употреблять неописанный тип rec (тип rec описан позже). Перед типом rec ставится символ ^ (карат), что означает: uk является указателем на тип rec. Когда речь идет о конкретной переменной, на которую указывает указатель, знак карата переносится в конец имени указателя, например, tek^.davl означает поле "давление" записи, на которую указывает указатель tek.
Для выделения памяти используется процедура new(<указатель>). В данном случае new(tek) означает выделение памяти для записи, на которую указывает tek. Таким образом, tek - это адрес в оперативной памяти, с которой начинается вновь образованная переменная tek^, имеющая тип записи rec. Конечно, заранее знать этот адрес невозможно, поэтому выделение динамической памяти производится на этапе исполнения (RunTime). Тип uk (указатель на rec) имеют переменные tek, pred, perv, rab для текущей, предыдущей, первой, рабочей записей. Односвязный список всегда проходится в одном направлении, в данном случае от начала к концу, для установки на начало служит указатель на первую запись perv. В записи имеется ссылочная (адресная) часть v - указатель на следующую запись. Для последней записи списка, это - указатель в никуда, имеющий имя nil.
В начале программы вводится 5 записей пациентов. Ввод первой записи описан отдельно от остальных для инициализации указателей (в частности, указателя pred на предыдущую запись, которая ранее не существовала и определяется только после ввода первой записи).
Для каждой записи вначале ссылочному полю v присваиваем nil, что означает отсутствие следующей записи. В дальнейшем, при выделении памяти следующей записи процедурой new в это поле записывается текущий указатель, но не для текущей, а для предыдущей записи. В последней же записи на месте v остается nil.
Затем в программе описано удаление записей пациентов с давлением, большим 140. Односвязный список просматривается с начала, для чего текущему указателю tek присваивается значение perv указателя на первую запись. Просматривается поле давление tek^.davl для текущей записи и если оно больше 140, запись подлежит удалению. При этом действия различны, является ли удаляемая запись первой или нет.
Если удаляемая запись первая, то указатель на первую запись perv нужно передвинуть на следующую запись perv:=tek^.v. Если требуется удалить и следующую запись, она вновь будет первой, и вновь указатель первой записи будет изменен, как и следует.
Если же удаляемая запись не первая, то указатель предыдущей записи устанавливаем на адрес, на который указывает ссылка в текущей записи, таким образом, текущая запись будет пропущена в списке.
Если удаляемая запись последняя (tek^.v=nil), то следует в ссылочной части предыдущей записи установить признак конца списка pred^.v:=nil, если эта предыдущая запись существует (список не пуст, т.е. удалены не все записи). Если же удалены все записи, следует установить perv:=nil.
Далее в программе следует печать оставшихся записей, если список не пуст. Устанавливаем текущий указатель на первую запись и выводим на экран информационные поля fio и davl, затем переходим к следующей записи tek:=tek^.v.
Достарыңызбен бөлісу: |
