I. Data structures
Определение:
В компютърните науки, “Data structure” е начин за запазване и организиране на данни в компютрите за да може да се използват по-ефективно.
Различните видове структури от данни подхождат на различни видове приложения (програми), като някои са специализирани за специфични задачи.
1. Примитивни, съставни и абстрактни типове от данни
Примитивни (наречени още “прости”) са типовете данни, които са вградени на ниско ниво в даден програмен език.
Такива са: int, boolean, float, char, string и т.н. , като различните езици имат различни примитивни типове данни и с различна дължина ( заемано място в паметта )
– int или integer се използва за цели числа
– boolean – от логически тип. Възможни са две стойности – true и false ( 1, 0 )
– float – числа с плаваща запетая (реални числа)
– char – символен тип на данните
– string – символен низ
Съставни са всички структури от данни, за които може да се осъществи достъп до определен елемент от структурата, а не само на структурата като цяло.
Съставните структури от данни се делят на статични и динамични.
– статични са тези при които не може да се добавя или изважда елемент от структурата. За този тип данни се заделя фиксирано количество памет. Такива структури от данни са масивът и записът.
– динамични са тези структури от данни, които се състоят от променлив брой елементи и може да се добавя или изтрива елемент. Такива структури от данни са стекът, опашката, графът, дървото и други.
Абстрактни са тези типове от данни които могат да имат различен начин на реализация, но са еднакви по смисъл (еднакво поведение).
Такива данни са стек (последният влязъл първи излиза) и опашка (първият влязъл първи излиза).
2. Линейни структури от данни -> масиви и списъци
Линейна структура от данни представлява съвкупност от елементи които са организирани в линейна прогресия, при която елементите са подредени един след друг. Само един елент може да бъде достъпван в даден момент от обхождането.
Линейните структури от данни се използват в масивите, свързани списъци, стекове и опашки, и използват по-пълноценно паметта поради това, че се заделя точно определено количество памет и адресите в паметта са последователни.
– масивите са статични структури от данни с фиксиран брой елементи от един тип (в php не е така – там масивите не са статични стуктури от данни).
Всеки един елемент може да бъде достъпван индивидуално чрез индекс и се заделя фиксирано количество системна памет зa масива.
– линейни списъци – последователност от възли ( елемента ), при която всеки един възел съдържа данни и връзка към следващия възел.
Има няколко вида линейни списъци:
– едносвързани – всички елементи са свързани последователно като всеки съдържа данни и с изключение на последния има една връзка към следващия елемент. Списъка се обхожда от началото към края – еднопосочно.
– двусвързани – всички елементи са свързани последователно като всеки съдържа данни и с изключение на последния има две връзки една към следващия и една към предишния елемент. Елементите могат да бъдат обхождани в двете посоки
– циклични – всички елементи са свързани последователно като всеки съдържа данни и има една връзка към следващия елемент, а последния елемент има връзка към първия. Елементите се обхождат само в едната посока.
3. Дървета
Определение:
Не линейна структура от данни при която към всеки елемент (наричан още връх) има нула или повече върхове наследници, които се намират под него в структурата на дървото.
Връх, който има върхове наследници се нарича родител. Всеки връх има най-много един родител. Върховете, които нямат наследници се наричат листа, а корен е връх, който няма родител и е начало на дървото.
Използва се за представяне на йерархични връзки между елементите. Структурата му наподобява клоните на дърво от където идва и наименованието му. Характеризира се с височина и дълбочина.
Вътрешни върхове са всички върхове които не са корен, или листа.
Дълбочината на корена е нула, а със всеки следващ връх се добавя единица.
Примерно за връх номер 19 е едно, за връх 1 е две.
Височина е максималната дълбочина за всички върхове.
– Двоично дърво – не линейна структура от данни при която към всеки елемент (наричани още върхове) има не повече от два върха наследници. Тъй като наследниците не са повече от два е прието да се делят на ляв и десен наследник, съответно има ляво и дясно поддърво.
Обхождането на двоично дърво се осъществява по три основни начина:
– ЛКД (Ляво-Корен-Дясно/Inorder) – обхождането става като първо се обходи лявото поддърво, след това корена и накрая дясното поддърво.
– КЛД (Корен-Ляво-Дясно/Preorder) – в този случай първо се обхожда корена на дървото, после лявото поддърво и накрая дясното.
– ЛДК (Ляво-Дясно-Корен/Postorder) – тук по аналогичен на горните два примера начин, обхождаме първо лявото поддърво, после дясното и накрая коренът.
4. Хешове
– хеш таблица – стуктура от данни обикновено реализирана като масив, за която е характерен директен достъп до елементите, независимо от техния тип. Всеки елемент в хеш таблицата се характеризира с две полета – ключ и данни, които на пръв поглед са разположени в масива случайно и непоследователно.
В позициитге в които няма наредена двойка, има празен елемент.
Хеш таблиците имат определен размер (капацитет), надвишаването на който би довело до колизии.
Степен на запълване се нарича реално число между 0 и 1, което съответства на съотношението между броя на запълнените елементи и текущия капацитет.
На фигурата по-горе имаме три елемента и капацитет m, следователно степента на запълване ще е равна на 3/m.
Ключа е уникален идентификатор, и ако два елемента имат еднакъв ключ, то те се считат за идентични, но ако са различни се предполага, че и данните са различни
При хеш таблиците, броя сравнения които трябва да се извършат за да се установи дали даден ключ има стройност е константен и не зависи от броя на елементите в нея.
Хеш функция е функция която извършва процеса хеширане. Нарича се още трансформираща функция, тъй като трансформира ключа към адрес (ключ от хеш таблица). Хеширането е процес при който по зададен ключ на елемент се определя неговия адрес (ключ в хеш таблицата).
При хеширането, ключът се преобразува чрез определена функция (хеш функция) в адрес на таблица (хеш таблица). В хеш таблицата ключовете се записват или четат по своя хеш адрес.
При хешовете колизиите са неизбежни. Дори при перфектно съставена хеш-функция, колизия ще настъпи най-късно в момента, в който броят на включените елементи ще надхвърли капацитета на хеш таблицата.
5. Граф
Графа има подобна на дървото структура, като дървото се явява като вид граф.
Също като дървото, графа има върхове, но тук върховете могат да бъдат свързани посредством насочени връзки (дъги, ребра), тоест графа е съвкупност от елементи и връзки между тях.
Върхът от който излиза дъгата се нарича предшественик, а този в който влиза – наследник.
Най-общо има няколко вида граф:
– пълен граф при който за всяка двойка върхове съществува дъга, която ги свързва
– ориентиран граф – всички дъги са ориентирани (имат посока)
– неориентиран граф е граф при който дъгите му нямат ориентация.
– симетричен граф – за всяка ориентирана дъга между два върха съществува обратно ориентирана дъга.
– двудолен граф – неориентиран граф за който множеството от върхове може да бъде разбито на подмножества.
– претеглен граф – граф за който дъгите му имат тегла.
– планарен граф – граф който може да бъде нарисуван върху свефа или равнина, така че никои две дъги да не се пресичат.
П. П. В статията са използвани изображения от wikipedia.
Postfix Bind Sender Domain To Dedicated Outgoing IP Address chmod permissions example linux acl