Geum.ru

Тема: Програмування. Основні етапи розробки прикладних програм

Вид материалаДокументы
Подобный материал:
1   2   3   4   5   6   7   8   9   10   ...   14
ТЕМА: Вказівники.

Розглянуті раніше типи даних являли собою значення певного типу, які знаходилися в межах деякого діапазону і володіли певними спільними властивостями. В Pascal, крім даних інформаційного характеру (цифри, рядки), є особливий тип даних, що є адресами у пам'яті деякий комірок. Адресу теж можна вважати інформацією, але вона має подвійний зміст: інформація місця розміщення іншої інформації.

Доступ до будь-якого елемента даних легко реалізується через ідентифікатор змінної, проте до цього ж можна отримати доступ, вказавши адресу пам'яті, де розміщується відповідна змінна: звернутися до людини можна за її іменем-ідентифікатором або вказавши місце знаходження її.

Доступ до об’єктів за адресою пам'яті здійснюється через спеціальні величини.

Вказівник – це такий же складений тип даних, як масиви, рядки; але він не є сукупністю елементів деякого базового типу.

Значеннями вказівників є чотирибайтні числа, проте це не є числа типу longint. Адреса являє собою комбінацію із 2-х 2-байтних цілих чисел. Одне із цих чисел є адресою початку сегменту в пам'яті, друге число – зміщення відповідної комірки пам'яті від початку сегменту.

Тема: Адресація пам'яті.

Початково оперативна пам'ять ЕОМ вимірювалася десятками Кбайт, тому всі програми, які виконувалися були обмежені за розміром.

З середини 80-х теоретично обґрунтовано і практично реалізовано використання 1 Мб пам'яті, при цьому постала проблема неможливості подальшого розширення її.

Через пару років використовували, крім основної пам'яті (1 Мб) – додаткову та розширену пам'ять, проте базова пам'ять залишається в межах 1 Мб і саме в ній починають виконуватися більшість програмних робіт.

Всі комірки пронумеровані від нуля до деякого кінцевого значення, що в 16-вій системі координат .

Звичайно при програмуванні не зручно користуватися адресами, що визначаються числом, розміром 2,5 байта.

Звуження до 2 байт дало б пам'ять 65536, а розширення до 3-х дало б пам'ять більшу ніж можна було б зробити на той час (більше ніж 4 мільярди – 4 Гб). Тому для адресації 1 Мб пам'яті вирішили умовно розділити її на окремі сегменти, причому сегменти могли перекривати один одного і розмір міг бути різним, але не більше 65536, це зроблено тому, що в межах сегменту можна користуватися для адреси 2-хбайтними числами.

Сегменти в пам'яті виділяються не в довільному місці, а лиш з байта, номер якого кратний 16.

Тепер для збереження адреси початку сегменту нема потреби використовувати п’ять 16-вих цифр, а лише чотири, а останній 0 завжди зберігається в пам'яті. Таким чином, для збереження повної адреси байта у пам'яті, використовується 2 2-хбайтних числа: адреса сегменту із 4-х цифр та зміщення байту в межах сегменту. Повна адреса обчислюється як сума

XXXX0 адреса

+XXXX зміщення



ZZZZZ повна адреса.

Наприклад Пам'ять – вулиця з деякою кількістю рядків 0 – 9999. замість того, щоб користуватися 4-значними числами, квартири умовно розміщуються в будинках по 100 квартир з нумерацією від 0 до 99. повний номер квартири визначається за формулою .

1234=12*100+34.

35 квартира з номером 34 у 13 будинку з номером 12.

Тема: Оголошення та операції над вказівними величинами.

Вказівники оголошуються при допомозі спеціальної операції . Ця операція застосовується над деяким базовим типом, при цьому такі вказівники можуть зберігати адреси величин саме цього базового типу.

Хоча всі вказівники - це адреси, проте вказівники на різні базові типи є несумісними.

Наприклад.

TYPE

Pint=INTEGER;

Pchar=CHAR;

Pstring=STRING;

PPint=Pint;

PPPint=PPint;

Тут оголошено 5 типів вказівників:

Pint – вказівник цілих чисел; Pchar – вказівник на символи; Pstring – вказівник на рядки; PPint – вказівник на вказівник на цілі; PPPint – вказівник на вказівник на вказівник на цілі.

Хоча всі оголошені типи є вказівниками, проте всі вони не сумісні між собою.

В Pascal є стандартний вказівний тип, який сумісний з будь-яким із вказівників. Тип – pointer.

Змінні у програмі можуть оголошуватися або через раніше названі вказівні типи, або явним чином.

Наприклад.

VAR

Pi1:Pint;

Pi2:integer;

PPi1:PPint;

PPi2:Pint;

PPPi1:PPPint;

PPPi2:PPint;

Кожна з 3-х пар змінних є величинами еквівалентних вказівних типів. Перша змінна в кожній парі оглушена через ідентифікатор вказівного типу, друга – явним чином, через операцію . Між змінними кожної пари можна виконувати операції присвоєння.

Значення кожної із змінних – це адреса деякої величини відповідного типу, якщо вказівником не задано значення, то ним буде значення з довільною адресою, що розміщувалася на момент виконання операції.

Для того, щоб отримати адресу деякої змінної базового типу, використовується унарна операція взяття адреси (@).

VAR0000000

i1,i2:integer;

BEGIN

Pi1:=@i1;

PPi1:@Pi1;

PPi2:=@@i1

END;


Змінній Рі1 присвоєна адреса і1; змінній РРі1 присвоєна адреса адреси і1; змінній РРі2 присвоєно теж саме значення, але двократним використанням @.

Якщо потрібно отримати значення деякої величини, адреса якої відома, використовується інша операція – це унарна posfx-на операція і позначається .

Ці унарні операції виконуються в напрямі від ідентифікатора змінної. Операція @ виконується з права на ліво, а - з ліва на право.

Для того, щоб застосування операції розіменування вказівника було коректним. Цей вказівник повинен бути попередньо зв’язаний зі змінною оператором @.

Використання вказівників типу pointer дозволяє узгодити поля пам'яті різних типів. Це один із способів перетворення типів.

Взагалі операції присвоєння між вказівниками можливі між однаковими або еквівалентними типами.

VAR

Pi1:Pint;

Pi2:integer;

PPi1:PPint;

PPi2:Pint;

Pc1:Pchar;

Pc2:char

... ... ... ...

Pi1:=PPi1;

Pi1:=PPi1; {не можливі}

Pi1:=Pc1;

Pi1:=Pc!;


Pi1:=Pi2;

Pi1:=Pi2;

PPi1:=PPi2; {можливі}

Pc1:=Pc2;

Pi1:=PPi1

Як вже відмічалося значення вказівного типу є чотирибайтні числа. формально ці числа розділяються на дві частини по 2 байти: старше, менше слово. Старше слово є адресою початку сегменту; молодше слово – зміщення комірки пам'яті від початку сегмента.

Із усіх можливих значень, які існують, особливе значення має nil, що означає вказівник „в нікуди”. Цей вказівник не співпадає із 1 Мб з жодним і фактично є абстрактним поняттям. Реально в пам'яті такої комірки немає. Значення nil – це не нуль для цілих чи дійсних чисел.

Будь-який із вказівників може набувати значення nil, проте не можна застосовувати операцію розіменування вказівника, оскільки nil не вказує на якусь конкретну ділянку пам'яті.

Тема: Динамічні змінні.

Застосування вказівників дозволило реалізувати особливий вид змінних – динамічних.

На відмінну від іншого виду змінних (статичні), які існують протягом всього часу виконання програми, динамічні змінні можуть створюватися і знищуватися в будь-який момент програми спеціальними програмами.

Статичні змінні - це всі змінні, що оголошені в розділі var незалежно від типу. Ці змінні розміщуються в спеціальному сегменті пам'яті, що називають статичною пам’яттю або програмним стеком (не більше 64 Кб). Ці змінні слідують в порядку оголошення у програмі. Вони з'являються на початку виконання програми і стек звільняється при завершені програми.

Враховуючи, що стек не перевищує 1 сегменту пам'яті, а отже кількість статичних змінних буде обмежена.

Динамічні змінні розміщуються в особливій частині оперативної пам'яті, що називається динамічною пам’яттю, або Heap-областю, або кучею. Під кучу відводиться вся вільна на момент виконання програми пам'ять. Враховуючи, що перших 360 Кб базової пам'яті займає ОП, то максимальний розмір буде 640 Кб.

Реально всі програми, які виконуються паралельно із Pascal-програмою теж частково використовують оперативну пам'ять.

Всі динамічні змінні створюються виключно спеціальними командами, так само вони і знищуються.

Для створення і знищення динамічних змінних є три групи підпрограм:
  1. NEW ( var p:point); DISPOSE(var p:pointer).
  2. MARK (var p:pointer); RELASE (var p:pointer).
  3. GETMEM (var p:pointer; size:longint); FREEMEM (var p:pointer; size:longint).

Перші процедури в кожній групі створюють динамічні змінні; другі – знищують. Використання кожної із груп процедур визначається потребами програми, оскільки результати їх роботи відмінні.

При створенні динамічних змінних процедурою New, в якості фактичного параметра використовується статична змінна вказівного типу.

VAR

Pi1:Pint;

Ppi1:PPint;

Pc:Pchar;

Ps:string;

BEGIN

New(Pi1);

New(PPi1);

New(Pc);

New(Ps);

END.

Тут створюється 4 динамічних змінних, на які є статичні вказівники. Перша динамічна змінна матиме тип integer, друга – вказівний тип на integer, третя – тип char, четверта – тип string.

Динамічні змінні розміщуються у пам'яті не неперервним чином, а, починаючи з кожного нового 8 б блоку. Таким чиною створення динамічних змінних малих розмірів є малоефективним, оскільки з користю використовується 1\8, 1\4.

Якщо динамічна змінна створена процедурою New, то знищення можна провести лише відповідною Dispose. Відповідна ділянка кучі звільнюється, а параметр вказівника втрачає своє значення.

При звільненні частини кучі процедурою Dispose з'являються вільні фрагменти пам'яті можливо достатньо великого розміру. Чи будуть при новому створені динамічні змінні розміщуватися в звільнених ділянках? При новому створені, динамічні змінні розміщуються, починаючи з першого 8-мибайтного блоку після останньої динамічної змінної в мові Рascal завжди рівне адресі початку першого 8-мибайтного блоку після останньої динамічної змінної в кучі: Heap ptr.

Всі новостворені динамічні змінні розміщуються, починаючи з адреси Heap ptr. Після кожного нового створення Heap ptr збільшує своє значення.

Друга група підпрограм для створення динамічних змінних оперує лише з динамічними змінними типу pointer і розміром цієї змінної 4 байти.

В якості інформаційної комірки використовувати її малоефективно.

При створені динамічних змінних процедурою Mark(р), її параметр типу pointer отримує значення вказівника Heap ptr. Таким чином змінна р фіксує стан динамічної пам'яті процедурою Mark.

Після фіксації стану, в ній можуть бути створені або знищенні динамічні змінні попередніми процедурами, при цьому вказівник Heap ptr буде отримувати нове значення. Повернутися до зафіксованого раніше процедурою Mark значення Heap ptr можна процедурою Release(p) з цим самим значенням. При цьому не відбувається знищення чи добавлення даних до зафіксованого значення.

Всі динамічні змінні, що знаходяться вище цього значення будуть вважатися знищеними. Виникає питання: що буде в наступній ситуації.

New(p1);

New(p2);

Mark(p);

Dispose(p1);

Dispose(p2);

Release(p);

Така ситуація не відновлює дані, хоча Heap ptr вказує на вершину раніше зайнятої кучі. Утворюються пустоти, в яких не вдасться розмістити нові динамічні змінні.

При розміщенні динамічних змінних у пам'яті, потрібно враховувати, що неможливість чергової операції створення динамічної змінної із-за відсутності місця в кучі, призводить до зупинки програми, тому потрібно контролювати стан динамічної пам'яті на наявності вільного простору. Для цього Pascal має стандартні функції без параметрів.

MemAvail:longint;

MaxAvail:longint;

MemAvail повертає своїм значенням загальний розмір вільної пам'яті в перерахунку на 8-мибайтні блоки. Цей розмір видається в байтах.

MaxAvail повертає своїм значенням розмір максимальної неперервної вільної ділянки в кучі в перерахунку на 8-мибайтні блоки. Таким чином при операціях багатократного створення динамічних змінних варто користуватися наступною перевіркою

if MaxAvail>=sizeof(<базовий тип>) then New(…)

else writeln(‘немає місця’);


Тема: Динамічні структури даних.

Використання вказівники та динамічних змінних дозволяє будувати нові структури даних, які називаються динамічними. Вони розміщуються в динамічній частині пам'яті і можуть як завгодно змінювати свій розмір, тобто кількість елементів, таким чином дечим подібні до типізованих файлів, які теж можуть змінювати свій розмір. Проте є деякі принципові відмінності:
  1. Файли розміщуються в зовнішній пам'яті, а динамічні структури в оперативній.
  2. Типізовані файли фактично є файлами прямого доступу, що означає довільний доступ до елементів. В динамічних структурах доступ до елементів виключно послідовний.

Зв’язок між елементами в динамічних структурах реалізуються при допомозі вказівників, кожен елемент такої структури в свою чергу є складеною структурою: інформаційна частина містить корисні дані, а вказівна містить адресу наступного елемента.

Тема: Списки. Атрибути списків.

Згадані вище динамічні структури даних в програмуванні називають списками. Під списком розуміється деяка послідовна структура даних, кожен елемент якої містить два компоненти: інформаційне поле та вказівні поля. Саме через вказівники здійснюється зв’язок елементів у списку.

Доступ до всього списку реалізується через фіксований вказівник у вигляді статичної змінної на перший елемент списку – голова списку. Всі решта елементів утворюють так званий хвіст списку. Останній елемент списку переважно вказує в nil – це є ознака кінця списку.

В залежності від кількості вказівних полів в кожному елементі списку, розрізняють однозв’язні списки (один вказівник) п-зв’язні списки (п вказівників) .

Крім такого поділу по зв’язності, списки бувають лінійними, деревами, графами та ін.

В двонапрямлених списках доступ до елементів однаково здійснюється при русі від першого до останнього за вказівником next, або від останнього до першого за вказівником prev.

Якщо елементи списку мають два вказівних поля, але список не лінійних, а розгалужений, то отримується список у вигляді бінарного дерева.

Тема: Лінійні однонапрямлені списки.

Такі списки складаються з елементів, які є комбінацією двох полів: інформаційного та вказівного на наступний елемент.

Вказівне поле матиме тип вказівника на базовий тип, що є типом всього елемента списку, при цьому допускається рекурсивність оголошення типу списку.


TYPE

list1=el_list1;

el_list1=record

inf:integer;

next:list1

END;


В програмі доступ до таких однонапрямлених змінних здійснюється через фіксований вказівник – статичну змінну. Ця змінна не може змінювати свого значення, оскільки може призвести до втрати адреси всього списку. Останній елемент списку вказує в nil.

Формування списку здійснюється при допомозі процедур створення динамічних змінних, при цьому кожний новий елемент зв’язується вказівником з попереднім елементом або своїм вказівником із наступним. Формування списку може здійснюватися за двома принципами:
  1. Стек.
  2. Черга.

При формуванні списку за правилом стеку: кожен новий елемент ставиться у список в якості голови.

Якщо список формується за правилом черги, то кожен новий елемент добавляється у хвіст списку. Фіксований вказівник вказує на один і той же елемент, при цьому потрібно мати ще один фіксований вказівник на останній елемент списку.

Відмінність між списками чергами і стеками лише у порядку заповнення елементами. Всі решта операцій по переміщенню, вставці, видаленню абсолютно однакові.

Традиційно, над лінійними списками виконують наступні дії:
  1. Формування.
  2. Перегляд.
  3. Пошук елемента за вказаним інформаційним полем.
  4. Вставка нового елемента після деякого елемента із вказаним значенням.
  5. Вставка елемента перед деяким елементом.
  6. Видалення елемента із вказаним значенням.
  1. Формування однонапрямленого списку.

Для реалізації операції в програмі достатньо мати 4 статичні змінні.

а). Стек.

VAR

first, last,p,q:list1;

o:string;

n,i,a,k:integer;

BEGIN

writeln('введіть кількість елементів у списку');

readln(n);

for i:=1 to n do

begin

new(p);

writeln('введіть елемент списку');

readln(a);

p.inf:=a;

p.next:=first;

first:=p

end;

б). Черга.

writeln('введіть кількість елементів у списку');

readln(n);

first:=nil;

last:=nil;

new(p);

writeln('введіть елемент списку');

readln(a);

p.inf:=a;

last:=p;

first:=p;

for i:=2 to n do

begin

new(p);

writeln('введіть наступний елемент списку');

readln(a);

p.inf:=a;

last.next:=p;

last:=p

end;

Оскільки при створення першого елементу передбачаються операції з вказівником first, а створення решти елементів не потребує використання first, то при побудові списку за правилом черги формування першого елементу відрізняється від формування останніх.
  1. Перегляд всього списку. Перегляд списку передбачає рух від голови списку до кінця.

PROCEDURE RESIV (first,p:list1);

BEGIN

p:=first;

while p<>nil do

begin

write(p.inf,',');

p:=p.next

end;

writeln

END;

3.Пошук за вказаним інформаційним полем.

writeln('введіть шуканий елемент');

readln(a);

while (p<>nil) do

begin

if p.inf=a then

begin

writeln ('під номером № ‘,k+1);

i:=i+1;

end;

p:=p.next;

k:=k+1

end;

if k=0 then writeln ('немає')

else writeln ('кількість ',i)

4.Вставка нового елементу після деякого елементу.

p:=first;

writeln ('введіть елемент, після якого потрібно вставити новий');

readln(k);

while p<>nil do

begin

if p.inf=k then

begin

new(q);

writeln('введіть елемент, який потрібно вставити');

readln(a);

q.inf:=a;

q.next:=p.next;

p.next:=q

end;

p:=p.next

end;

5. Вставка нового елементу перед деяким елементом. Вставка нового елемента перед деяким елементом є складнішим, оскільки список є структурою з послідовним доступом. Вставка перед деяким елементом х – це теж саме, що й вставка після попереднього елемента з значенням п.

writeln ('введіть елемент, перед яким потрібно вставити новий');

readln(k);

p:=first;

if p=nil then writeln ('список пустий')

else

if p.inf=k then {вставка перед першим}

begin

new(q);

writeln ('введіть елемент, який потрібно вставити');

readln(a);

q.inf:=a;

q.next:=p;

first:=q

end

else

begin

while (p.next<>nil) and (p.next.inf<>k) do

p:=p.next;

if p.next=nil then writeln ('немає такого елементу ')

else

begin

new(q);

writeln('введіть елемент, який потрібно вставити');

readln(a);

q.inf:=a;

q.next:=p.next;

p.next:=q

end

end;

6. Видалення. Для видалення елементу із вказаним інформаційним плем потрібно знову ж як і для вставки перед мати вказівник на попередній елемент, тому операція видалення матиме декілька варіантів: пустий список, видаляється перший елемент, відсутність у списку шуканого елементу, шуканий елемент довільний, крім першого.


writeln('введіть елемент, який потрібно вилучити');

readln(a);

p:=first;

if p=nil then writeln ('список пустий')

else

if p.inf=a then

begin

first:=p.next;

dispose(p)

end

else

begin

while (p.next<>nil) and (p.next.inf<>a) do

p:=p.next;

if p.next=nil then writeln ('такого елементу немає')

else

begin

q:=p.next;

p.next:=q.next;

dispose(q)

end

end;