Влияние върху производителността
Статичен списък (реализация чрез масив)
Изтегляне 1.47 Mb.
|
Свързани:
saap conspect
- Навигация на страницата:
- Двойно свързани списъци
- Реализация чрез шаблони и обекти
Статичен списък (реализация чрез масив)Масивите изпълняват много от условията на АТД списък, но имат една съществена разлика – списъците позволяват добавяне на нови елементи, докато масивите имат фиксиран размер. Въпреки това е възможна реализация на списък чрез масив, който автоматично увеличава размера си при нужда . Такъв списък се нарича статичен.Свързан списък (динамична реализация)Както видяхме, статичният списък има един сериозен недостатък – операциите добавяне и премахване от вътрешността на списъка изискват пренареждане на елементите. При често добавяне и премахване (особено при голям брой елементи) това може да доведе до ниска производителност. В такива случаи се използват т. нар. свързани списъци. Разликата при тях е в структурата на елементите – докато при статичния списък елементите съдържат само конкретния обект, при динамичния списък елементите пазят информация за следващия елемент. Ето как изглежда един примерен свързан списък в паметта: Изтриването по стойност на елемент работи като изтриването по индекс, но има 2 особености: търсеният елемент може и да не съществува и това налага допълнителна проверка; в списъка може да има елементи със стойност null, които трябва да предвидим и обработим по специален начин. За да работи коректно изтриването, е необходимо елементите в масива да са сравними. Двойно свързани списъциСъществува и т. нар. двойно свързан списък (двусвързан списък), при който всеки елемент съдържа стойността си и два указателя – към предходен и към следващ елемент (или null, ако няма такъв). Това ни позволява да обхождаме списъка, както напред така и назад. Това позволява някои операции да бъдат реализирани по ефективно. Ето как изглежда един примерен двусвързан списък в паметта: Реализация чрез шаблони и обектиКогато по-късно търсим даден елемент, ние го получаваме като обект и се налага да го превърнем в изходния тип. Не ни се гарантира, обаче, че всички елементи в списъка ще бъдат от един и същ тип. Освен това превръщането от един тип в друг отнема време, което забавя драстично изпълнението на програмата.За справяне с описаните проблеми на помощ идват шаблонните класове. Те са създадени да работят с един или няколко типа, като при създаването си ние указваме какъв точно тип обекти ще съхраняваме в тях. Изтегляне 1.47 Mb. Сподели с приятели:
|