русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Урок 10 — Динамическая память. Односвязный список. Примеры и использование

Рассмотренные ранее структуры данных являлись  статическими.

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

Процедура  выделения памяти связана с процедурой ее освобождения после использования. В Турбо Паскале имеется три пары  процедур  выделения-освобождения  памяти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.

Просмотров: 18853

Вы можете --> Заказать программу или Задать вопрос на форуме

Вернуться воглавление


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.