http___fmi.wikidot.com_sdp15_1.xml
http___tjsct.wikidot.com_linked-list.xml
1.1 1.2 2.1 2.2 2.3 3.1 4.1 5.1 6.1 6.2 6.3 6.4 7.1 8.1 8.2 8.3 9.1 9.2 9.3 9.4 9.5 10.1 10.2 11.1 12.1
Свързан списък. Създаване на свързан списък Свързан списък — това е структура от данни, при която последователните елементи се съхраняват на различни места в оперативната памет, а не в последователни полета. Връзката между отделните елементи се осъществява чрез указател към следващия елемент (указателят е неразделна част от самия елемент). Донякъде наподобява верига: - всяко звено е свързано със следващото; - за да имаме достъп до целия списък, нужен е единствено указател към първия елемент (другите се достигат от него); - ако бъде сменен указателят на произволно звено, до всичко след него вече няма да има достъп (все едно да го откачим от веригата). Един последователен списък се задава, като се зададат адресът на началото на списъка и броят на елементите (масивите например са последователни списъци). Ако списъкът е свързан, достатъчен е и само адресът на началото. Останалите елементи се намират по пътя, определен от указателите и маркера за край. Обикновено стойността NULL в указателя за следващ елемент се приема за маркер за край. Предимства и недостатъци Предимството на свързаните списъци е, че лесно се добавя и отстранява елемент в някой от двата края, докато при последователните списъци това изисква разместване на елементите в паметта. Лесно се обединяват два или повече списъка, тъй като наличието на указател към следващия елемент е достатъчно, за да се намери свободно място в оперативната памет и то да се свърже с останалите елементи на списъка. Заеманата памет е право пропорционална на елементите в списъка, защото всеки път се заделя точно колкото трябва за още един елемент. Недостатък е наличието на допълнително място за адрес във всеки елемент. За днешните компютри четири допълнителни байта на елемент не са фатални, но преди е било другояче. Друг недостатък — достъпът до определен елемент предполага в общия случай преглеждането на всички елементи от началото до края на списъка, тоест бавно е. Освен това при големи списъци може да се постигне т. нар. фрагментация на паметта. Какво представлява това, е предмет на друга лекция, но е достатъчно да се каже, че това наистина забавя компютъра. По очевидни причини свързаното представяне е удобно, когато се обработват елементи, чийто брой не е предварително известен. Освен това вариации на свързания списък могат да се използват за моделиране на други структури от данни (стекове, дървета, графи). Програма за създаване на свързан списък #include   #include   using namespace std; struct Student { unsigned nomer; float sr_uspeh; Student *next; }; int main() { int n; char c; Student *first, *ps; first=NULL; n=sizeof(Student); do { ps=new Student; if (ps==NULL) { cout  >ps->nomer; cout >ps->sr_uspeh; cout next=first; first=ps; cout <<"Krai na vuvejdaneto (Y/N)?"; cin.get(); cout<<endl<<endl; c=cin.get(); cout<<endl; } while(c!='Y' && c!='N'); system ("pause"); }
1.1 1.2 1.3 1.4 1.5 2.1 3.1 3.2 3.3 4.1 5.1 5.2 5.3
A linked list is, quite simply, a list in which each element is linked to the next, much like a chain. A linked list commonly keeps pointers to the first and last element, with elements pointing to the next one. Then, one can quickly add elements to the end or remove elements from the front. For this reason, linked lists are very useful in implementing queues. However, since there is no structure in memory, accessing an arbitrary element of the list is very slow. Doubly linked lists A doubly linked list is a linked list in which every node also keeps a pointer to the previous node. This is useful when you want to be able to add and remove items from both ends, rather than just one. However, this comes at a cost of memory space required to hold all the pointers. Circular linked lists A circular linked list is a linked list or a doubly linked list where the node after the last node is the first node. That is, you get a circle if you keep going to the next one. These have the same runtimes as the normal versions, but have their own uses, notably in fibonacci heaps.