МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра САПР Звіт до лабораторної роботи №13 на тему «СПИСКИ, СТЕКИ, ЧЕРГИ, КІЛЬЦЯ В МОВІ ПРОГРАМУВАННЯ С» з курсу «Проблемно-орієнтовані мови програмування» ЛЬВІВ 2011 Мета роботи Навчитися використовувати динамічний розподіл пам’яті для роботи зі списками, чергами і кільцями. Теоретичні відомості Список - це набір елементів (найчастіше структурних змінних), розташованих у динамічній пам'яті й зв'язаних між собою з вказівниками на ці елементи. Спосіб зв'язку елементів, який застосовується, визначає тип списку. Списки бувають лінійними й кільцевими, однозв'язними й двозв’язними. Елемент однозв'язного списку містить крім безпосередньо "корисної" інформації також інформацію про наступний або попередній елемент списку. Відповідно елемент двозв’язного списку містить інформацію, як про наступний, так і про попередні елементи. Останній елемент кільцевого списку містить вказівник на перший елемент списку. Якщо список розташовується в оперативній пам'яті, то інформація для пошуку наступного об'єкта - адреса (вказівник) у пам'яті. Якщо зв'язний список зберігається у файлі на диску, то інформація про наступний елемент може включати зсув елемента від початку файлу, положення вказівника запису/зчитування файлу, ключ запису або будь-яку іншу інформацію, що дозволяє однозначно відшукати наступний елемент списку. Черга - це список з таким способом зв'язку між елементами, при якому нові елементи додаються строго в кінець списку, а вибираються для обробки строго з початку. Принцип організації черги можна описати так: "першим прийшов - першим пішов" (FІFO - Fіrst Іn, Fіrst Out). Черга елементів може бути реалізована з використанням масивів, зв'язного списку або іншим способом. Щоб не обмежувати максимальне число елементів у черзі, найбільше доцільно її побудова у вигляді однозв'язного списку. Додавання нових елементів відбувається завжди в кінець списку (в "хвіст"). Останній елемент позначається особливим чином, наприклад поле вказівника на наступний елемент дорівнює NULL. Рекомендується при роботі із чергою використовувати два вказівники: один - на початок черги, а другий -на її кінець. Це спростить як вибір елементів із черги, так і їхнє додавання. Стек - це список з таким способом зв'язку між елементами, при якому нові елементи додаються строго в початок списку й вибираються для обробки також строго з початку списку (за принципом "першим прийшов - останнім пішов" (FІLO - Fіrst Іn, Last Out), тобто перший занесений у стек елемент буде оброблений останнім). Кільце - це список, елементи якого утворюють замкнуту кругову систему, тобто останній створений елемент повинен містити вказівник на перший елемент. Списки можуть бути двoнаправленими, що дає можливість обходу списків у двох напрямках. У лінійних списків у перших елементах вказівник на попередній елемент, як правило, дорівнює нулю. У двoнаправленного кільця перший елемент вказує на останній, а останній - на перший. Індивідуальне завдання Написати програму для видалення будь-якого елемента зі списку. Текст програми #include<stdio.h> #include<conio.h> #include<string.h> #include<math.h> #include<iostream.h> struct st { char chA; struct st *next; }; struct st head = {NULL, NULL}, *p; void message(); void insert() { char c; cout<<"Which element add? "; cin>>c; struct st cur; cur.next=NULL; p=head.next; cur.chA=c; for(p = &head; p->next ; p = p->next); cur.next = p->next; p->next = &cur; message(); } void del() { char c; cout<<"Which element delete?"; cin>>c; for(p = &head; p->next &&p->next->chA!=c ; p = p->next); struct st *tmp; tmp = p->next->next; p->next = tmp; message(); } void show() { int j=0; struct st *c=head.next; for(p = c;p ; p = p->next, j++) { cout<<p->chA; if(p->next) cout<<"->"; } message(); } void message() { cout<<"\na-add element\ns-show list\nd-delete element\ne-exit"<<endl; switch(getch()) { case 'a': insert(); break; case 's': show(); break; case 'd': del(); break; case 'e': exit(1); break; default: { cout<<"\nError\n"; message(); } } } int main() { message(); return 0; } Результати обчислень
Висновок: Я навчився використовувати динамічний розподіл пам’яті для роботи зі списками, чергами і кільцями.