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

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

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

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

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

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

content: Робота з чергоюСтворення (доповнення новим елементом)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); {видаляє елемент}

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

content: 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;{продовження на наступному слайді}

content: 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);