МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ Національний унiверситет "Львiвська полiтехнiка" Звіт до лабораторної роботи N 1 з курсу "Теорiя алгоритмiв i математичнi основи представленння знань" Створення i ведення лiнiйних спискiв Прийняв: _________________ Львів 2008 1. МЕТА РОБОТИ Ознайомитися iз способом подання даних в оперативнiй пам’ятi ЕОМ у виглядi лiнiйних спискiв. Оволодiти алгоритмами роботи з послiдовними i зв’язаними лiнiйними списками. 2. КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI Необхiдно рацiонально використовувати системнi ресурси, у першу чергу пам’ять. Для правильного застосування пам’ятi важливо розумiти способи подання у нiй даних i методи роботи з ними. У лабораторнiй роботi розглядаються структури даних у виглядi лiнiйних спискiв. Лiнiйний список - це множина, яка складається з n>=0 вузлiв X[1], X[2],, X[n], для якої якщо n>0, то X[1] є першим вузлом; якщо 1<k<n, то k-му вузлу X[k] передує X[k-1] i за ним йде X[k+1]; X[n] є останнiм вузлом. Операцiї, якi можна виконувати з лiнiйним списком: отримати доступ до k-го вузла списку, щоб проаналiзувати i/або змiнити його вмiст; ввести новий вузол безпосередньо перед k-м вузлом; 3) видалити k-вузол; 4) об'єднати кiлька лiнiйних спискiв в один; 5) зробити копiю лiнiйного списку; 6) видалити вузол iз списку; 7) знайти вузол iз заданим значенням у деякому полi. Iснують два методи зберiгання структур даних у пам’ятi комп’ютера. Перший метод розподiлу, який використовує переваги одновимiрної властивостi пам’ятi, називається послiдовним розподiлом. Другий метод розподiлу, що базується на зберiганнi адреси чи розташування кожного елемента списку, вiдомий пiд назвою зв’язаного розподiлу (рис.1). послiдовний розподiл: зв’язаний розподiл: Перший метод не використовується, якщо: 1. Вимоги до пам’ятi є непередбачуваними. 2. Даними, що зберiгаються у пам’ятi, iнтенсивно манiпулюють. Зв’язаний список графiчно можна зобразити у виглядi, показаному на рис.2 NodeType - iм’я типу структури запису, який мiстить ці поля. Використання зв’язаного розподiлу, як правило, передбачає iснування деякого механiзму пошуку вiльного простору для нового вузла, коли ми хочемо ввести у список деяку нову iнформацiю. Для цього необхiдно пiдтримувати пул або список вiльних вузлiв, який називається списком вiльного простору. Пiд час операцiї вставлення вiльний вузол видаляється iз списку вiльного простору i розмiщується у призначений лiнiйний список. I, навпаки, видалений вузол повертається до списку вiльного простору i може бути використаний для наступних вставок. Така схема управлiння пам’яттю має очевиднi переваги - у даний момент використовується простiр пам’ятi, що вiдповiдає фактичному обсяговi даних. Iснують два пiдходи до застосовування списку вiльного простору: пiдтримка списку вiльного простору засобами мови програмування i програмна пiдтримка (застосування пiдтримує власний список вiльної пам’ятi). 3. ІНДИВІДУАЛЬНЕ ЗВДАННЯ Варіант 13 13) Змiнити вмiст k-го вузла #include <iostream.h> #include <conio.h> int k,m; struct nova { int nomer; nova *dali; }; nova *element, *pershij, *poperednij, *novyj, *fix; void stvorspysok(void); void vuvid(void); void ph(void); void main() { clrscr(); cout<<"stvorennja spusky, dlja zakin4ennja -> vvedit' 0\n"; stvorspysok(); cout<<"\n------\n"; vuvid(); cout<<"\nm:\n"; cin>>m; cout<<"\ninfo dlja powyky"; cin>>k; ph(); cout<<"\n"; cout<<"novuj spusok\n"; vuvid(); getch(); } //--------------------------- void stvorspysok(void) { element=new (nova); pershij=element; do { poperednij=element; cin>>element->nomer; element->dali=new (nova); element=element->dali; } while (poperednij->nomer!=0); poperednij->dali=NULL;} //--------------------------- void vuvid(void) { element=pershij; while(element!=NULL) {cout<<element->nomer; element=element->dali;} } //---------------------------- void ph(void) { element=pershij; while(element!=NULL) { if (element->nomer==k) {element->nomer=m;} element=element->dali;}} висновок: при виконанні цієї лабораторної роботи я ознайомився iз способом подання даних в оперативнiй пам’ятi ЕОМ у виглядi лiнiйних спискiв. Оволодiти алгоритмами роботи з послiдовними i зв’язаними лiнiйними списками.