Презентація на тему «Списки. Динамічна пам’ять»

Списки. Динамічна пам'ять.

Розрізняють звичайну і динамічну пам'ять організації комп'ютера. В оперативній памяті можна розмістити обмежену кількість даних, зокрема, змінних. Є задачі коли заздалегідь не відомо, скільки змінних буде. У цьому випадку організовують динамічну пам'ять. Принцип динамічної організації пам'яті полягає в тому, що змінні займають пам'ять за необхідністю, опрацьовуються і в потрібний момент вивільняють пам'ять.
Для роботи з такими змінними використовують тип даних- вказівник. Якщо ім'я статистичної змінної задає адресу даного в оперативній пам'яті, то вказівник на динамічну змінну – лише тип даного, а не його розташування в пам'яті. Тип даних вказівник описують за допомогою символу ^ у розділі type так:
Type <назва типу>=^<базовий вказівник>;
В розділі var вказівники на динамічні змінні оголошують:
Var <список вказівників на змінні> : < назва типу >;

На етапі компіляції пам'ять для масивів та записів тут не надається (сам вказівник займає 4 байти). Пам'ять для даних, про можливість появи яких попереджає вказівник, буде надана на етапі виконання програми за допомогою процедури new:
new(<вказівник на змінну>);
Тільки тепер утворилась динамічна змінна, імя якої має такий вигляд:
<вказівник на змінну>^ .
Розрізняють операції над вказівником на динамічну змінну та операції над самою динамічною змінною.
З динамічною змінною можна виконувати операції, визначені для даних відповідного базового типу.
Над вказівниками визначені такі операції переадресації
<вказівник1>:= <вказівник2>;
<вказівник1>:=nil;
Процедура dispose вивільняє пам'ять на котру вказує її параметр. Після чого ця пам'ять може бути розподілена повторно.

Розрізняють такі динамічні лінійні структури:
Стек. Включення і виключення даних відбувається з його вершини.
Черга. Включається даних – з кінця, а виключення – з початку. При роботі з чергою краще використовувати два вказівника: один на початок і один на кінець.
Список. Елементи впорядковані по певній ознаці і від одного елементу формується увесь стек. Включення і виключення даних відбувається в будь-якому місці ланцюга, як і пошук потрібного місця, що теж відбувається по ознаці по котрій створений список.
Прийнято виділяти слідуючі типи зв'язаних списків:
Однозв'язні (однонапрямлені) – лінійні списки;
Однозв'язні-циклічні списки;
Двозв'язні (двонапрямлені) – лінійні списки;
Двонапрямлені циклічні списки;
Якщо елемент списку “знає” не тільки слідуючий, а і попередній, то в списку можливий рух в двох напрямках. Для такої організації достатньо ввести додакткове поле в котрому знаходиться вказівник на попередній елемент:
Data

Робота з стеком
Створення (доповнення новим елементом)
S:=nil; {стек пустий}
New(nov); {виділення памяті для нового елемента стека}
nov^.inf:=10; { в новий елемент заноситься його інформація}
nov^.prt:=S;
S:=nov;
Видалення
dat:=S^.inf; {зчитування інформації з інформаційного поля з вершини стека в змінну dat}
nov:=S; {встановка на вершину стека допоміжного вказівника}
S:=nov^.prt; {вказує на слідуючий елемент. Переміщення вказує вершини стека}
dispose(nov); {видаляє елемент}

Робота з чергою
Створення (доповнення новим елементом)
nach:=nil; {стек пустий і nach вказує на початок черги}
kon:=nil; {kon вказує на кінець черги}
New(p); {виділення пам'яті для першого елемента}
p^.inf:=10; p^.prt:=nil; { в новий елемент заноситься його інформація}
nach:=p; kon:=nil;
Доповнення новим елементом
new(p) {виділення пам'яті для нового елемента}
p^.inf:=5; {занесення інформації в новий елемент}
p^.prt:=nil;
kon^.prt:=p;
kon:=p;
Видалення
dat:=nach; {з'явилась нова змінна для вилучення і збереження елемента}
p:=nach; {установка на видаляємий елемент}
nach:=p^.prt; {вказує на слідуючий елемент}
dispose(p); {видаляє елемент}

Зразок задачі з використання списку
Побудувати динамічну структуру даних наведену нижче.
X1x4x3x1
X1x2x2
Program structura;
Type Point=^ITEM
ITEM=record
Data:integer;
right,left:= Point; end;
Var first,p: Point;
Begin
New(p);
First:=p;
Read(p^.data;
New(p^.left);
{побудуєм 1-й елемент}
{продовження на наступному слайді}

Read(p^.left^.data; {2-й}
New(p^.rigth);
Read(p^.rigth^.data; {4-й}
p:=p^.left;
New(p^.left);
p^.right:=nil;
p:=p^.left;
Read(p^.data); {3-й}
p^.right:=nil;
p^.left:=first;
p:= first^.right;
p^.left:=first^.left;
p^.right:= first^.left^.left;
Write(‘x1x4x3x1');
p:=first;
Writeln(p^.data); {1-й}
p:=p^.right;
Writeln(p^.data); {4-й}
p:=p^.right;
{продовження на наступному слайді}

Writeln(p^.data); {3-й}
p:=p^.left;
Writeln(p^.data); {4-й}
p:=first;
Write(‘x1x4x3x1');
Writeln(p^.data); {1-й}
p:=p^.left;
Writeln(p^.data); {2-й}
p:=p^.left;
Writeln(p^.data); {3-й}
Readkey;
End.
Можна також використати writeln(p^.data,p^.left^.data,p^.left^.left,^.data); замість writeln(p^.data); p:=p^.left; writeln(p^.data); p:=p^.left; writeln(p^.data);