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

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

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

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

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

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

6 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. Видалення елемента зі списку.

7 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;

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

9 Черги Черги – це лінійний список, для якого виконується приєднання елементів до кінця списку і дані зчитуються у тому ж порядку, як їх записували. 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;

10 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; } //повертаємо значення елементу

11 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); //Доки елемент не дорівнює нулю

12 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();//Видаляємо перший елемент } }

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

14 Приклад: програма перевірки балансу дужок в тексті. Будь-які символи, крім дужок ігноруються #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();//Функція очищення стеку

15 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

16 { 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;} 17 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;//повертаємо значення останнього // елементу // елементу}

18 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();//видаляємо останній елемент}