Свързан списък. Създаване на свързан списък.

15. Свързан списък. Създаване на свързан списък

Свързан списък — това е структура от данни, при която последователните елементи се съхраняват на различни места в оперативната памет, а не в последователни полета. Връзката между отделните елементи се осъществява чрез указател към следващия елемент (указателят е неразделна част от самия елемент). Донякъде наподобява верига:

• всяко звено е свързано със следващото;
• за да имаме достъп до целия списък, нужен е единствено указател към първия елемент (другите се достигат от него);
• ако бъде сменен указателят на произволно звено, до всичко след него вече няма да има достъп (все едно да го откачим от веригата).

Един последователен списък се задава, като се зададат адресът на началото на списъка и броят на елементите (масивите например са последователни списъци). Ако списъкът е свързан, достатъчен е и само адресът на началото. Останалите елементи се намират по пътя, определен от указателите и маркера за край. Обикновено стойността NULL в указателя за следващ елемент се приема за маркер за край.

Предимства и недостатъци

Предимството на свързаните списъци е, че лесно се добавя и отстранява елемент в някой от двата края, докато при последователните списъци това изисква разместване на елементите в паметта. Лесно се обединяват два или повече списъка, тъй като наличието на указател към следващия елемент е достатъчно, за да се намери свободно място в оперативната памет и то да се свърже с останалите елементи на списъка. Заеманата памет е право пропорционална на елементите в списъка, защото всеки път се заделя точно колкото трябва за още един елемент.
Недостатък е наличието на допълнително място за адрес във всеки елемент. За днешните компютри четири допълнителни байта на елемент не са фатални, но преди е било другояче. Друг недостатък — достъпът до определен елемент предполага в общия случай преглеждането на всички елементи от началото до края на списъка, тоест бавно е. Освен това при големи списъци може да се постигне т. нар. фрагментация на паметта. Какво представлява това, е предмет на друга лекция, но е достатъчно да се каже, че това наистина забавя компютъра.
По очевидни причини свързаното представяне е удобно, когато се обработват елементи, чийто брой не е предварително известен. Освен това вариации на свързания списък могат да се използват за моделиране на други структури от данни (стекове, дървета, графи).

Програма за създаване на свързан списък

#include <iostream>
#include <cstdlib> 
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 <<"Nyama svobodna pamet."<<endl<<endl;
exit(1); }
cout <<"Nomer na studenta:"<<endl<<endl;
cin>>ps->nomer;
cout<<endl<<endl;
cout<<"Sreden uspeh:"<<endl<<endl;
cin>>ps->sr_uspeh;
cout<<endl<<endl;
ps->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"); }