русс | укр

Мови програмуванняВідео уроки php mysqlПаскальСіАсемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

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


Linux Unix Алгоритмічні мови Архітектура мікроконтролерів Введення в розробку розподілених інформаційних систем Дискретна математика Інформаційне обслуговування користувачів Інформація та моделювання в управлінні виробництвом Комп'ютерна графіка Лекції


Шановні українці! Матеріал був перекладений з російської мови. Тому можуть бути незначні помикли...

Урок 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 залишається нічого.

Потім у програмі описано видалення записів пацієнтів з тиском, великим 140. Однозв'язний список проглядається з початку, для чого поточного вказівником tek присвоюється значення perv вказівника на перший запис. Проглядається поле тиск tek^.davl для поточного запису і якщо воно більше 140, запис підлягає видаленню. При цьому дії різні, є чи видалена запис першої чи ні.

Якщо видалена запис перша, то показівник на перший запис perv потрібно перенести на наступний запис perv:=tek^.v. Якщо потрібно видалити запис, вона знову буде першою, і знову покажчик першого запису буде змінено, як і слід. Якщо ж видалена запис не перша, то покажчик попереднього запису встановлюємо на адресу, на який вказує посилання в поточного запису, таким чином, поточний запис буде пропущена в списку.

Якщо видалена запис остання (tek^.v=nil), то слід в посилальної частини попереднього запису встановіть ознаку кінця списку pred^.v:=nil, якщо ця попередній запис існує (список не порожній, тобто видалені не всі записи). Якщо ж видалені всі записи, слід встановити perv:=nil.

Далі в програмі слід друк останніх записів, якщо список не порожній. Встановлюємо поточний показівник на перший запис і виводимо на екран інформаційні поля fio davl, потім переходимо до наступного запису tek:=tek^.v.

Переглядів: 1210

Повернутися взміст


Онлайн система числення Калькулятор онлайн звичайний Науковий калькулятор онлайн