Покажчики.

Імена даних вказують адреси байтів пам’яті ЕОМ, де розташовані дані. З кожним типом даних Т пов’язується множина адрес, за якими можуть розташовуватися ці данні. Така множина адрес є носієм типу “покажчик на Т”. Змінні цього типу називаються покажчиками, а їхніми значеннями є адреси об’єктів типу Т.

В мові С описи таких замінних будуються за допомогою операції * (“значення за адресою”). Наприклад:

char *pc, *ppc; - змінні pc та ppc є покажчиками на char.

Адреси значень типу Т задаються виразами “покажчик на Т”. Найпростішим виразом такого типу є & v, де & - знак операції “взяття адреси”, v - ім’я змінної або вираз, що задає елемент масиву, член структури або об’єднання. Наприклад:

char ch, *oc;

pc= & ch; - вираз та покажчик pc мають значення адресу змінної ch.

За допомогою покажчиків відбувається доступ та зміна значень даних без вживання їхніх імен. Якщо pe позначає довільний вираз типу “покажчик типу Т”, то вираз * pe має значення типу Т, яке розташоване за адресою, визначеною значенням pe. Якщо x, y - змінні, px, py - відповідно покажчики на них, то вирази x = y, *px = y, x = *py, *px = *py еквівалентні.

Операції * та & обернені, тобто вирази *(& p) і p, & (*p), i p еквівалентні.

Для покажчиків дозволені наступні операції.

Нехай pe та pv позначають відповідно довільний вираз і змінну типу “покажчик на Т”, ie - цілий вираз. Вираз pe + ie має значення val(pe) + val(ie) sizeof(T) типу pe, тобто значення покажчика збільшується на ціле число розмірів даних типу Т. Аналогічно, вирази pe - ie val(pe)-val(ie) sizeof(T). Вирази pv++, ++pv (pv--, --pv) збільшують (зменшують) значення pv на sizeof(T). Аналогічно pv+ = ie та pv- = ie збільшують або зменшують pv на val(ie) sizeof(T). Вираз pe1- pe2 означае ціле число об’єктів типу Т, які можна розмістити в пам’яті, починаючи з адреси val(pe1) val(pe2), тобто val(pe1- pe2)= (val(pe1)- val(pe2))/ sizeof(T).

Вирази відношення на покажчиками мають вигляд

pe1 S pe2,

де S- один з знаків операцій ==,! =, <, < =, >, > =/.

Ці операції аналогічні операціям відношення з арифметичними операндами. Вираз pe[ie] еквівалентний виразу *(pe + ie) і має значення типу Т. Якщо pe містить знаки операції, то слід писати (pe) [ie], тому що операція [] має найвищій пріоритет.

Вживання інших операцій над покажчиками неприпустиме. Значення покажчиків на один тип можна перетворити в значення покажчиків на інший тип. Але такі перетворення не завжди безпомилкові, тому що адреси об’єктів, які займають 2 чи більше байтів, можуть бути тільки парними. Деякі реалізації допускають використання цілих значень як адрес, і навпаки, тобто можливі вирази вигляду pv = ie, ’iv = pe. Приклад:

Для визначеного опису

float *px, *pz;

double *py, y;

a) вираз px++ p, збільшує val(px) на 4;

b) вираз py--=2 зменшує val(px) на 16;

c) після обчислення виразу pz=*(& px) +1; val(pz) -val(px) = 4;

d) якщо val(pz) =val(px) + 4, то після обчислення виразу px=(pz=px) +1; val(px) =val(pz) + 4.

Лінійні списки.

Лінійний список - це скінченна послідовність однотипних елементів (вузлўв), можливо, з

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

При роботі з списками часто доводиться виконувати такі операції:

· знайти елемент із заданною властивістю;

· визначити i-й елемент у лінійному списку;

· внести додатковий елемент до або після вказанного вузла;

· вилучити певний елемент зі списку;

· упорядкувати вузли лінійного списку в певному порядку.

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

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

Зв'язане зберігання лінійних списків. Тут рекурсивні структури даних зв'язуються одним з полів у ланцюг, початок якого вказується покажчиком списку. При простому зв'язанному зберіганні списку цўлих чисел кожний елемент ї структурою типу LISTN, складеною з поля

val для значення елемента списку та поля next для покажчика на наступний елемент списку. Опис

typedef struct node

{ int val;

struct node * next; } LISTN, *LISTP;

визначаї структуру одного елемента списку типу LISTN і покажчика на нього типу LISTP. У роботі зі списками в зв'язанному зберіганні використовується функція new(v, pn), яка виділяє вільну ділянку пам'яті для зберігання вузла списку, встановлює val i next в v та pn і повертає покажчик на сформований вузел:

/*new-формування вузла списку*/

LISTP new(v, pn)

int v;

LIST pn;

{ char * calloc();

LISTP p;

if (p=(LISTP) calloc (1, sizeof (LISTN)))

{p-> next=pn; p-> val=v;

return p; }

else error (" переповнення");

}

Функцўя lform створюї зв'язний список F=< d1, d2, d3> з трьох елементів і повертаї покажчик на перший елемент:

LISTP lform(d1, d2, d3)

int d1, d2, d3;

{ LISTP new (), p;

p=new(d3, NULL); p = new(d2, p);

return new(d1, p);

}

Функція lprnd друкує значення і-го вузла, а функція lprbnd друкує обох сусідів вузла, на який показує p (d1-покажчик першого елемента лінійного списку, що зберігається зв'язано):

/*lprnd- друкування значення ў-го вузла*/

lprnd(d1, i)

LISTP d1;

int i;

{ int j;

for (j=1; j< i& & d1; j++)

d1=d1-> next;

if (! d1) error (“немає вузла”);

printf(" %_=_%d\n", i, d1-> val);

}

/*lprbnd - друкування сусідів вузла, на який показує p*/

lprbnd(d1, p)

LISTP d1, p;

{if (! p!! d1==p!!! p-> next)

error (“немає сусіда”);

while(d1& & d1-> next! =p)

d1=d1-> next;

if (! d1) error (“немає сусіда”);

printf(" %d_%d\n", d1-> val, (p-> next)-> val);

}

Зв'язане зберігання лінійного списку дозволяє ефективно вилучати чи додавати новий вузол із значенням dv за елементом, визначеним покажчиком h! =NULL. Функції ldelet i linst

реалізують відповідно ці операції:

/*ldelet- вилучення вузла за вузлом *p */

ldelet(p)

LISTP p;

{ LISTP r;

if (! (r=p-> next))

error (" немаї вузла");

p-> next=r-> next; free(r);

}

/*linst-додавання вузла зІ значенням dv за вузлом *p*/

linst(dv, p)

int dv;

LISTP p;

{ LISTP new ();

p-> next=new(dv, p-> next);

}

Функція lptar частково упорядковує непорожній список d1 зі значеннями k₁, k₂,..., k_n, перетворюючи його в список вузлів < k'₁, k'₂,..., k'_s, k₁, k''₁, k''₂,..., k''_i>, s+t+1=l так, що k'_i< k₁ для 1< =i< =...< =s, k''_j> =k₁ для 1< =j< =t; вона повертає покажчик на частково упорядкований список:

/*lptar- часткове упорядкування зв'язанного списку*/

LISTP lptar(d1)

LISTP d1;

{int aux; LISTP p, r;

aux=d1-> val; p=d1;

while(r=p-> next)

if(r-> val< aux)

{p-> next=r-> next;

r-> next=d1; d1=r;

}

else p=r;

return d1;

}

Кількість дій, потрібних для виконання вказанних операцій над списком у зв'язанному зберіганні, оцінюється співвідношеннями: для функцій lprnd, lprbnd- O(l); для функцўй ldelet, linst-O(1); для функцій lptar-O(l).

Зв'язане зберігання лінійного списку називається списком з двома зв'язками, якщо кожний вузол (структура) маї два поля для зберігання покажчиків-посилань на попередній та наступний елементи лінійного списку.

Зв'язане зберігання лінійного списку називається циклічним списком, якщо його останній елемент показує на перший елемент, а покажчик списку p- останній елемент.

При розв'язанні конкретних задач можуть вникати й інші різновиди зв'язанного зберігання.