Динамічні списки В багатьох задачах кількість даних наперед не встановлена, передбачається введення нових елементів у вже сформований набір даних, відалення окремих елементів чи інші зміни складу й конфігурації набору даних. У цих випадках застосовують динамічні інформаційні структури. Вони формуються на основі взаємозвязку елементів. Так, кожен елемент лінійного списку повязується через відповідні вказівники з одним або декількома сусідніми елементами. Дані Дані Дані Адреса Адреса ……… NULL

Програмно елемент списку можна реалізувати через структурний тип, який містить щонайменше два поля: інформаційне, в якому зберігаються дані цього елемента, та адресне, через яке він повязується з іншим елементом. Наприклад, шаблон структури елементу списку: typedef long elemtype; typedef stuct list_elem { elemtype val; struct list_elem *next; } list; тут elemtype - визначає тип даних лінійного списку. Можна використовувати будь-який стандартний тип даних, включаючи структури; list - визначає структуру елемента лінійного списку ( val - значення, яке зберігається у вузлі, next – покажчик на наступний елемент). Лінійний список, кожен елемент якого містить посилання на один сусідній, називається однозвязним або однонаправленим.

Для звертання до списку достатньо зберігати адресу тільки одного початкового елемента, який називають вершиною або головою списку. Наприклад, адреса початку списку зберігається в змінній-вказівнику first list * first; Кінцевий елемент, який не має наступників, називають хвостом списку, а в його адресне поле заносять константу NULL. Поширені також двозвязні списки, в яких кожен елемент зберігає адреси двох сусідніх. Списки розрізняють також за способом приєднання нових елементів: -приєднання до вершини списку; -приєднання до кінця списку; - вставлення елементів у визначені позиції списку.

Основні операції над списками 1.Включення елемента в початок списку. list *addbeg (list *first, elemtype x) { list *vsp; vsp = (list *) malloc(sizeof(list)); vsp->val=x; vsp->next=first; first=vsp; return first; }

2. Видалення елемента з початку списку. list *delbeg(list *first) { list *vsp; vsp=first->next; free(first); return vsp; }

3. Включення нового елемента у список. list *add(list *pred, elemtype x) { list *vsp; vsp = (list *) malloc(sizeof(list)); vsp->val=x; vsp->next=pred->next; pred->next=vsp; return vsp; } 4. Видалення елемента зі списку.

elemtype del(list *pred) { elemtype x; list *vsp; vsp=pred->next; pred->next=pred->next->next; x=vsp->val; free(vsp); return x; } 5. Друк значень списку. void print(list *first) { list *vsp; vsp=first;

while (vsp) { printf("%i\n",vsp->val); vsp=vsp->next; } } 6. Перевірка, чи порожній список int pust(list *first) { return !first; } 7. Знищення списку list *kill(list *first) { while (!pust(first)) first=delbeg(first); return first; }

Черги Черги – це лінійний список, для якого виконується приєднання елементів до кінця списку і дані зчитуються у тому ж порядку, як їх записували. n n n n next next next … … NULL Черга реалізує принцип FIFO (first in - first out) Приклад: програма запису чисел в чергу, почергове виведення всіх парних елементів #include #include struct st { struct st { int n; int n; st *sp; st *sp; } *first=NULL,*last,*q; } *first=NULL,*last,*q;

void Add (int N) { //Функція приєднання елементу void Add (int N) { //Функція приєднання елементу q=(st*)malloc(sizeof(st)); //Звільнення пам'яті для елементу q=(st*)malloc(sizeof(st)); //Звільнення пам'яті для елементу if (first==NULL) first=q; //Якщо не було елементів робимо if (first==NULL) first=q; //Якщо не було елементів робимо // першим // першим else last->sp=q; // інакше дописуємо елемент в else last->sp=q; // інакше дописуємо елемент в // кінець черги // кінець черги q->n=N; //Заносимо значення в останній q->n=N; //Заносимо значення в останній // елемент // елемент last=q; //Ставимо елемент останнім last=q; //Ставимо елемент останнім last->sp=NULL; last->sp=NULL; } int View() //Функція перегляду першого int View() //Функція перегляду першого // елементу списку // елементу списку { return first->n; } //повертаємо значення елементу { return first->n; } //повертаємо значення елементу

void Delete() void Delete() { if (first==last) q=NULL; //якщо залишився один елемент, if (first==last) q=NULL; //якщо залишився один елемент, // очищаємо чергу // очищаємо чергу else q=first->sp; //інакше видаляємо останній else q=first->sp; //інакше видаляємо останній // елемент // елемент free(first); //очищаємо пам'ять free(first); //очищаємо пам'ять first=q; first=q; } void main() { void main() { int i,k=1; int i,k=1; do { do { scanf("%d",&k); //Вводимо значення елементу scanf("%d",&k); //Вводимо значення елементу if (k!=0) Add(k); //Якщо елемент не нульовий if (k!=0) Add(k); //Якщо елемент не нульовий //додаємо його до черги //додаємо його до черги } while (k!=0); //Доки елемент не дорівнює нулю } while (k!=0); //Доки елемент не дорівнює нулю

while (first!=NULL) {//Доки список не пустий while (first!=NULL) {//Доки список не пустий k=View(); //робимо k рівним першому k=View(); //робимо k рівним першому // елементу в списку // елементу в списку if (k%2==0) printf("%d ",k);//якщо елемент парний if (k%2==0) printf("%d ",k);//якщо елемент парний //виводимо його на екран //виводимо його на екран Delete();//Видаляємо перший елемент Delete();//Видаляємо перший елемент } }

Стеки Різновидом однозвязного списку є стек.... nnnn NULLprev Особливість в тому, що кожен новоприєднаний елемент стає вершиною списку, тому зчитування елементів проводиться в послідовності, зворотній до послідовності їх запису. Програмування стека базується на двох операціях: - приєднання нового елемента до вершини списку; -зчитування та видалення першого елемента списку. Стек реалізує принцип LIFO (last in - first out, останнім прийшов - першим пішов). Прикладом організації стеку може бути дитяча пірамідка, де додавання і знімання кілець здійснюється відповідно до цього принципу.

Приклад: програма перевірки балансу дужок в тексті. Будь-які символи, крім дужок ігноруються #include #include typedef struct st//Оголошення типу STACK { char ch; { char ch; struct st *ps; } STACK; struct st *ps; } STACK; STACK *p=NULL,*q; void putinstack(char w); //Функція запису елемента в //стек //стек char viewstack(); //Функція, яка повертає //значення останнього eлемента //значення останнього eлемента //стеку //стеку void deletestack();//Функція видалення останнього // елементу // елементу void clearstack();//Функція очищення стеку

int main() { char a[100]; char a[100]; scanf("%s",&a);//Введення рядку scanf("%s",&a);//Введення рядку for(int i=0;a[i]!='\n';i++)//До закінчення рядка for(int i=0;a[i]!='\n';i++)//До закінчення рядка { if (a[i]=='(') putinstack(a[i]);//Якщо дужка відкрита, if (a[i]=='(') putinstack(a[i]);//Якщо дужка відкрита, //заносимо її в стек //заносимо її в стек if (a[i]==')') //Якщо дужка закрита if (a[i]==')') //Якщо дужка закрита if (viewstack()=='(') //і якщо остання в стеку if (viewstack()=='(') //і якщо остання в стеку //відкрита //відкрита deletestack(); //видаляємо зі стеку deletestack(); //видаляємо зі стеку //останню дужку //останню дужку else else

{ puts("NO");//в іншому випадку умова puts("NO");//в іншому випадку умова // не виконується // не виконується return 0; //завершення головної функції return 0; //завершення головної функції } } if (p==NULL) puts("YES");//Якщо стек пустий умова if (p==NULL) puts("YES");//Якщо стек пустий умова //виконується //виконується else else{ puts("NO");//якщо ні – умова не puts("NO");//якщо ні – умова не // виконується // виконується clearstack(); clearstack(); }//Звільнюємо виділену пам'ять }//Звільнюємо виділену пам'ять return 0; return 0;}

void putinstack(char w) { q=(st*)malloc(sizeof(st));//Виділення пам'яті для q=(st*)malloc(sizeof(st));//Виділення пам'яті для //одного елементу стека //одного елементу стека q->ps=p;//Запис посилання на q->ps=p;//Запис посилання на //попередній елемент //попередній елемент q->ch=w; //Запис значення q->ch=w; //Запис значення p=q; //Встановлюємо вказівник на p=q; //Встановлюємо вказівник на //останній елемент //останній елемент} char viewstack() { if (p==NULL) return -1;//якщо елемента немає if (p==NULL) return -1;//якщо елемента немає //повертаємо -1 //повертаємо -1 return p->ch;//повертаємо значення останнього return p->ch;//повертаємо значення останнього // елементу // елементу}

void deletestack() { q=p;//Встановлення вказівника q на q=p;//Встановлення вказівника q на //останній елемент //останній елемент p=q->ps;//Встановлення вказівника р на p=q->ps;//Встановлення вказівника р на //попередній елемент //попередній елемент free(q);//Звільнення динамічної пам'яті free(q);//Звільнення динамічної пам'яті} void clearstack() { while (p!=NULL)//Доки стек не буде пустий while (p!=NULL)//Доки стек не буде пустий deletestack();//видаляємо останній елемент deletestack();//видаляємо останній елемент}