Список – це сукупність записів, кількість яких може змінюватись в ході
виконання програми. При цьому пам’ять для розміщення нового запису
виділяється і вивільняється динамічно по мірі необхідності. Зрозуміло, що для
реалізації такого типу даних необхідно використовувати покажчики, тому
основним елементом такого списку являється запис, що має одне або кілька
полів, які є покажчиками на його власний тип:
type
dinptr=^dinrec;
dinrec=record
re:real;
next:dinptr;
end;
В даному прикладі створено тип-запис dinrec. Зверніть увагу на поле next
типу dinrec, яке є покажчиком на тип dinrec. Наявність таких полів у записах
дає можливість зв’язувати окремі записи у списки.
Для ефективного використання списків необхідно навчитися виконувати
над списками операції створення списків, заповнення даними записів списку,
додавання запису до списку, вилучення запису із списку.
Розглянемо ці
операції на прикладі:
uses crt;
type
dinptr=^dinrec;{опишемо тип-покажчик на запис потрібної структури}
dinrec=record {опишемо тип-запис потрібної структури}
re:real;
next:dinptr;
end;
var
first:dinptr; {об’явимо покажчик, в якому будемо зберігати адресу
першого елементу списку}
elem,tmp:dinptr; {об’явимо ще два покажчики. Вони знадобляться при
виконанні операцій додавання та знищення елементів }
i,counter:integer; {об’явимо змінні цілого типу. Змінна i буде
використовуватись для організації циклів, counter для збереження числа
записів наявних у списку}
begin
clrscr;
counter:=0; {початкова кількість записів 0}
first:=nil;
new(elem); {виділяємо пам’ять під перший запис}
elem^.next:=nil; {присвоюємо початкові значення}
tmp:=nil;
first:=elem; {зберігаємо адресу початку списку}
{створимо і додамо до списку 5 записів, збільшуючи щоразу на одиницю
змінну counter}
for i:=1 to 5 do
begin
elem^.re:=sqr(i); {записуємо дані в інформаційне поле запису}
new(elem^.next); {виділяємо пам’ять під наступний запис}
elem:=elem^.next; {переміщуємось до кінця списку}
inc(counter);
end;
tmp:=first; {tmp тепер вказує на початок списку, як і first}
{виведемо список на екран}
for i:=1 to counter do
begin
writeln(tmp^.re:7:2); {виводимо на екран інформаційне поле запису}
tmp:=tmp^.next; {переміщуємось до наступного запису}
end;
readkey;
tmp:=first; {перейдемо в початок списку}
{знищимо 3-ій запис}
for i:=1 to 2 do {переходимо до 3-го запису}
begin
elem:=tmp; {змінна містить 2-го запису}
tmp:=tmp^.next; {змінна містить адресу 3-го запису}
end;
elem^.next:=tmp^.next;{зв’яжемо 2-ий елемент з четвертим, відкинувши
третій елемент}
dec(counter); {зменшимо на одиницю counter }
dispose(tmp); {звільнимо пам’ять, що містила 3-ій запис}
writeln;
{виведемо на екран список після видалення 3-го запису}
tmp:=first;
for i:=1 to counter do
begin
writeln(tmp^.re:7:2);
tmp:=tmp^.next;
end;
readkey;
{знищимо 1-ий запис}
tmp:=first;
first:=first^.next;
dec(counter);{зменшимо counter}
dispose(tmp);{звільнимо пам’ять, що містила 1-ий запис}
{виведемо список на екран}
tmp:=first;
writeln;
for i:=1 to counter do
begin
writeln(tmp^.re:7:2);
tmp:=tmp^.next;
end;
readkey;
{вставимо новий запис у початок списку}
tmp:=first;
new(elem);
elem^.re:=pi; {запишемо у інформаційне поле запису число 3.14}
elem^.next:=first;
first:=elem;
inc(counter);{збільшимо counter на 1}
{виведемо список на екран}
tmp:=first;
writeln;
for i:=1 to counter do
begin
writeln(tmp^.re:7:2);
tmp:=tmp^.next;
end;
readkey;
{вставимо запис у 3-тю позицію}
tmp:=first;
for i:=1 to 2 do
{перейдемо до того місця списку, куди треба вставити
запис }
begin
elem:=tmp; {збережемо адресу 2-го запису}
tmp:=tmp^.next; {збережемо адресу 3-го запису}
end;
new(elem^.next); {виділимо пам’ять під запис}
elem^.next^.re:=49; {запишемо до інформаційного поля запису число 49}
elem^.next^.next:=tmp; {вставимо запис до списку}
inc(counter); {збільшимо counter на 1 }
writeln; {виведемо список на екран}
tmp:=first;
for i:=1 to counter do
begin
writeln(tmp^.re:7:2);
tmp:=tmp^.next;
end;
readkey;
{перейдемо в початок списку}
tmp:=first;
{послідовно знищимо весь список. Спочатку 1-ий запис, потім 2-ий і т.д.}
for i:=1 to counter do
begin
elem:=tmp ; {збережемо адресу поточного запису }
tmp:=tmp^.next ;{перейдемо до наступного запису}
dispose(elem); {знищимо запис, чию адресу збережено на
попередньому кроці і вивільнимо пам’ять зайняту ним}
dec(counter); {зменшимо counter на 1}
end;
first:=nil;
tmp:=first;
end.
З прикладу видно, що навіть елементарні операції із списками потребують
досить високої кваліфікації, але вони дають змогу оптимально використовувати
пам’ять.
Немає коментарів:
Дописати коментар