МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра САПР Лабораторна робота №2 Створення i ведення лiнiйних зв’язаних спискiв iз програмною пiдтримкою пулу вiльної пам’ятi з курсу: “Алгоритми и структури данних” Прийняв ЛЬВІВ 2007 Мета роботи Ознайомитися iз способом подання даних в оперативнiй пам'ятi ЕОМ у виглядi лiнiйних зв'язаних спискiв із програмною підтримкою пулу вільного простору. Теоретичні відомості Застосування зв’язаного розподілу, як правило, передбачає існування деякого механізму пошуку вільного простору для нового вузла, коли ми хочемо ввести у список деяку нову інформацію. Для цього звичайно використовується спеціальний список, що називається списком вільного простору. Називатимемо цей список списком AVAIL (або стеком AVAIL). Множина всіх вузлів, які у даний момент не використовуються, зв’язана в список, що нічим від інших не відрізняється і змінна AVAIL вказує на його верхній елемент. Тоді, якщо ми хочемо, щоб значенням змінної зв’язку Х стала адреса нового вузла і цей вузол був збережений для подальшого використання, можна зробити так: Х ( AVAIL, AVAIL ( LINK(AVAIL). (1) із стека видалється верхній вузол і тепер Х вказує на нього. Х ( AVAIL - Х стає вказівником на новий вузол. Якщо вузол більше не потрібний, то для його видалення процес (1) можна виконати так (зворотньо): LINK(X) (AVAIL, AVAIL ( X. (2) Ця операція повертає вузол, адреса якого знаходиться у Х, у список заготовок. Розглядаючи стек AVAIL, ми упустили кілька важливих моментів, наприклад, як побудувати цей стек на початку роботи. Зрозуміло, що це можна зробити, а) зв’язуючи всі вузли, які будуть використовуватися; б) заносячи в AVAIL адресу першого з цих вузлів; в) роблячи зв’язок останнього вузла порожнім. Множина всіх вузлів, які можуть бути використані, називається пулом пам'яті. Існує кілька моментів у роботі із стеком AVAIL: - перевіряти переповнення, тобто чи в (1) вся наявна пам’ять вичерпана. Тоді операцію Х ( AVAIL потрiбно записати так: Якщо AVAIL = ^ ,то переповнення, інакше Х ( AVAIL, AVAIL ( LINK(AVAIL). Можливість переповнення необхiдно враховувати завжди. Якщо виникає переповнення - закiнчуємо роботу. Часто не відомо наперед скільки місця повинен займати пул пам’яті. Небажано, щоб дiлянка зв’язаної пам’яті займала місця більше ніж потрібно( Нехай ми хочемо відвести місце для зв’язаної дiлянки, починаючи з Lo у послідовності зростання адрес, і так щоб ця дiлянка ніколи не виходила за межі значення змінної SEQMIN. Тоді, використовуючи нову змінну POOLMAX, можна діяти так: а) спочатку AVAIL ( ^ ; POOLMASX ( Lo, б) X ( AVAIL Якщо AVAIL = ^, то X ( AVAIL, AVAIL ( LINK(AVAIL), інакше POOLMAX ( POOLMAX+C, де С - розмір вузла; (4) тепер, якщо POOLMAX > SEQMIN, то переповнення; інакше Х (-POOLMAX-C. в) якщо в інших частинах програми зменшується значення SEQMIN, то при SEQMIN < POOLMAX повинен виникнути сигнал переповнення. г) операція AVAIL (X залишається такою, як і (2). Суттєвим результатом вищевказаної процедури є використання мінімально можливого пулу пам’яті. Індивідуальне завдання Реалізувати пул. Текст програми: #include <stdio.h> #include <stdlib.h> #include <conio.h> const number=10; //---DATA STRUCTURES-------------- typedef char element_type; struct unit { element_type element; unit * next; }; //------FUNCTIONS-------- int full_pool (unit *); unit * search(unit *); unit * init_pool(void); void show_pool(unit *); unit * delete_from_pool(unit *,unit *); void insert_pool(unit *,unit **); //------MAIN----------------- void main (void) { clrscr(); unit * first, *pool; first=init_pool(); //--if pool was not created--- if (!first) { printf("\n Error can not crete the pool\n"); getch(); goto l1;}; //---------------------------- pool=first; while (1) { printf("\n 1 - enter the element\n 2 - show pool\n 3 - delete symbol\n 4 - exit\n"); int answer; scanf(" %d",&answer); switch (answer) { case 1: insert_pool(first,&pool); break; case 2: show_pool(first); break; case 3: pool=delete_from_pool(pool,search(first)); break; default: {printf("\n Good bye"); getch(); return;}; } } l1: } //------FUNCTION OF INITIALIZATION POOL-------------------- unit * init_pool(void) { unit * first; first=(unit *)malloc(number*sizeof(struct unit)); if (!first) return NULL; else { for (int i=0;i<number-1;i++) { (first+i)->element=' '; (first+i)->next=(first+i+1);} (first+number-1)->element=' '; (first+number-1)->next=NULL; }; return first; } //-------SHOW POOL-------------------------------------- void show_pool (unit * first) { printf("\n This is your pool \n "); for (int i=0;i<number;i++) printf(" %c",(first+i)->element); printf("\n\n"); } //-----CHEKING IF POOL IS FULL-------------------- int full_pool (unit * first) { //-0--pool is not full--------------- //-1--pool is full------------------ for (int i=0;i<number;i++) if ((first+i)->element==' ') return 0; return 1; } //------INSERT NEW ELEMENT TO THE POOL------------------------- void insert_pool(unit * first, unit ** pool) { if (full_pool(first)) { printf("\n Pool is full\n"); getch(); return;} else { printf("\n Enter the element\n"); element_type symbol; scanf(" %c",&symbol); (*pool)->element=symbol; unit * buf_pointer; buf_pointer=(*pool); (*pool)=(*pool)->next; buf_pointer->next=(*pool); } } //------SEARCH THE ELEMENT-------------------------- unit * search(unit * first) { element_type symbol; printf("\n Enter the element witch you want to delete\n"); scanf(" %c",&symbol); for (int i=0;i<number;i++) if ((first+i)->element==symbol) return (first+i); } //---------DELETE THE ELEMENT------------------------------ unit * delete_from_pool(unit * pool,unit * del_pointer) { pool=del_pointer; del_pointer->element=' '; return pool; } Висновок Після виконаної роботи я ознайомився iз способом подання даних в оперативнiй пам'ятi ЕОМ у виглядi лiнiйних зв'язаних спискiв із програмною підтримкою пулу вільного простору.