Maǵlıwmatlar strukturası

Informatikada **maǵlıwmatlar strukturası** (*[[Inglis tili|ingl]]. data structure*) - bul maǵlıwmatlardı shólkemlestiriw hám ádette maǵlıwmatlarǵa ónimli kiriw ushın tańlanatuǵın saqlaw formatı bolıp tabıladı. Anıǵıraq aytqanda, maǵlıwmatlar strukturası - bul maǵlıwmatlar mánislerin, olardıń arasındaǵı qatnaslardıń hám maǵlıwmatlarǵa qollanıwǵa bolatuǵın funkciyalardıń yamasa operaciyalardıń jıynaǵı, yaǵnıy bul maǵlıwmatlar tuwralı algebralıq struktura.

## Qollanılıwı
Maǵlıwmatlar strukturaları abstrakt maǵlıwmatlar tipleriniń (ingl. ADT - abstract data types) tiykarı retinde xızmet etedi. Abstrakt maǵlıwmatlar tipiniń logikalıq formasın anıqlaydı. Maǵlıwmatlar strukturası maǵlıwmatlar tipiniń fizikalıq formasın ámelge asıradı.

Maǵlıwmatlar strukturalarınıń hár túrli tipleri qosımshalardıń hár túrli túrlerine sáykes keledi, al ayırımları anıq wazıypalarǵa joqarı qánigelestirilgen. Mısalı, relyaciyalıq maǵlıwmatlar bazaları maǵlıwmatlardı izlew ushın ádette B-terek indekslerin paydalanadı, al kompilyatordı ámelge asırıw ádette indentifikatorlardı izlew ushın xesh kestelerin paydalanadı.

Maǵlıwmatlar strukturaları úlken maǵlıwmatlar bazaları hám internetti indekslew xızmetleri sıyaqlı paydalanıw ushın maǵlıwmatlardıń úlken kólemin ónimli basqarıw quralın támiyinleydi. Ádette, ónimli maǵlıwmatlar strukturaları ónimli algoritmlerdi proektlestiriwdiń gilti bolıp tabıladı. Ayırım formal proektlestiriw metodları menen programmalastırıw tilleri programmalıq támiynattı proektlestiriwdegi tiykarǵı shólkemlestiriwshi faktor retinde algoritmlerge emes, al maǵlıwmatlar strukturasına ayrıqsha itibar qaratadı. Maǵlıwmatlar strukturaları tiykarǵı yadta da, qosımsha yadta da saqlanǵan informaciyanı saqlawdı hám izlewdi shólkemlestiriw ushın paydalanılıwı múmkin.

## Ámelge asırıw
Maǵlıwmatlar strukturaların hár túrli programmalastırıw tilleri menen usılların qollanıw arqalı ámelge asırıwǵa boladı, biraq olardıń barlıǵı maǵlıwmatlardı ónimli shólkemlestiriw hám saqlawdıń ulıwma maqsetin bólisedi. Maǵlıwmatlar strukturaları ádette, kompyuterdiń yadınıń qálegen ornınan maǵlıwmatlardı alıw hám saqlaw uqıplıǵına tiykarlanadı, kórsetkish arqalı belgilenedi - yad adresin bildiretuǵın bit qatarı, onı ózi yadta saqlawǵa hám programma menen basqarıwǵa boladı. Solay etip, massiv penen jazıw maǵlıwmatlar strukturaları arifmetikalıq ámeller menen maǵlıwmatlar elementleriniń adreslerin esaplawǵa tiykarlanǵan, al baylanıstırılǵan maǵlıwmatlar strukturaları strukturanıń ózinde maǵlıwmatlar elementleriniń adreslerin saqlawǵa tiykarlanǵan. Maǵlıwmatlardıń dúzilisine bul usıl algoritmlerdiń ónimliligi menen kólemine tereń tásir etedi. Mısalı, massivlerdegi yadtı qatar bólistiriw tez kiriwdi hám ózgertiw háreketin jeńilletedi, bul maǵlıwmatlardı retli qayta islew scenariylerinde optimallastırılǵan ónimlilikke ákeledi.

Maǵlıwmatlar strukturasın ámelge asırıw ádette sol strukturanıń úlgilerin jaratatuǵın hám basqaratuǵın proceduralar jıynaǵın jazıwdı talap etedi. Maǵlıwmatlar strukturasınıń ónimliligin sol operaciyalardan bólek analizlew (tallaw) múmkin emes. Bul baqlaw abstrakt maǵlıwmatlar tipiniń teoriyalıq koncepciyasın, olarda orınlanatuǵın operaciyalar menen tikkeley bolmaǵan maǵlıwmatlar strukturasın hám sol operaciyalardıń matematikalıq qásiyetlerin (olardıń keńislik penen waqıt bahasın qosqanda) xoshametleydi.

## Mısallar

Ádette ápiwayı maǵlıwmatlar tiplerine tiykarlanǵan maǵlıwmatlar strukturalarınıń kóplegen túrleri bar. Belgili mısallar:

* Massiv – belgili bir tártiptegi elementlerdiń sanı, ádette barlıǵı birdey tipli (tilge baylanıslı jeke elementlerdiń barlıǵı birdey tipke májbúr bolıwı múmkin yamasa hár qanday derlik tipte bolıwı múmkin). Qanday element kerek ekenin kórsetiw ushın elementlerge pútin indeks arqalı erisiledi. Ádettegi ámelge asırıwlar massivlerdiń elementleri ushın qońsı yad sózlerin bóledi (biraq bul bárqulla zárúrlik emes). Massivler turaqlı uzınlıqtı yamasa ólshemin ózgertiwge boladı.
* Baylanıstırılǵan dizim (ápiwayı dizim dep te ataladı) - túyinler dep atalatuǵın hár qanday tiptegi maǵlıwmatlar elementleriniń sızıqlı kollekciyası, bunda hárbir túyinniń óz mánisi bar hám baylanıstırılǵan dizimdegi keyingi túyindi kórsetedi. Baylanıstırılǵan dizimniń massivke qaraǵanda tiykarǵı artıqmashılıǵı mınada: mánislerdi dizimniń qalǵan ornın almastırmay-aq bárhama ónimli kirgiziwge hám óshiriwge boladı. Belgili bir elementke tosınnan kiriw sıyaqlı ayırım basqa háreketler dizimlerde massivlerge qaraǵanda ástenirek. 
* Jazıw (kortej yamasa struktura dep te ataladı) toplanǵan maǵlıwmatlar strukturası bolıp tabıladı. Jazıw - ádette belgilengen san izbe-izlikte hám ádette atlar menen indekslengen basqa mánislerden ibarat mánis. Jazıwlardıń elementleri ádette maydanlar yamasa aǵzalar dep ataladı. Obyektke baǵdarlanǵan programmalastırıw kontekstinde jazıwlar olardı obyektlerden ajıratıw ushın ápiwayı eski maǵlıwmatlar strukturası retinde belgili.
* Xesh kesteleri, sonday-aq xesh kartaları retinde belgili, giltlerge tiykarlanǵan mánislerdi tez alıwdı támiyinleytuǵın  maǵlıwmatlar strukturaları. Olar giltlerdi massivtegi indekslerge salıstırıw ushın xeshlew funkciyasın paydalanadı, bul ortasha jaǵdayda turaqlı waqıtta kiriwge imkaniyat beredi. Xesh kesteleri ádette sózliklerde, keshlerde hám maǵlıwmatlar bazasın indekslewde qollanıladı. Degen menen, xesh soqlıǵısıwları júz beriwi múmkin, bul olardıń ónimliligine tásir etiwi múmkin. Soqlıǵısıwlardı qayta islew ushın shınjır hám ashıq adreslew sıyaqlı usıllar qollanıladı.
* Grafikler – bul obyektler arasındaǵı qatnaslardı kórsetetuǵın, jiyekler menen qosılǵan túyinlerdiń jıynaǵı. Grafiklerdi basqalar menen qatar sociallıq tarmaqlardı, kompyuter tarmaqların hám avtotransport tarmaqların modellestiriw ushın paydalanıwǵa boladı. Olar biyiklerden (túyinler) hám jiyeklerden (túyinler arasındaǵı baylanıslar) ibarat. Grafikler baǵdarlanǵan yamasa baǵdarlanbaǵan bolıwı múmkin hám olardıń ciklleri yamasa ciklı bolıwı múmkin. Grafikli ótiw algoritmleri keńlik-birinshi izlew hám tereńlik-birinshi izlewdi qamtıydı.
* Stekler (stacks) menen gezekler (queues) - massivler yamasa baylanıstırılǵan dizimler arqalı ámelge asırılıwı múmkin abstrakt maǵlıwmatlar tipleri bolıp tabıladı. Stektiń eki tiykarǵı háreketi bar: «Aqırǵısı kiriw, birinshisi shıǵıw» (LIFO) qaǵıydasına sáykes keletuǵın push (stektiń joqarı jaǵına element qosadı) hám pop (stekten eń joqarı elementti alıp taslaydı). Gezeklerdiń (queues) eki tiykarǵı háreketi bar: birinshi kirgen, birinshi shıqqan (FIFO) principine sáykes gezekke qoyıw (gezektiń artına element qosadı) hám gezekke qoyıw (gezektiń aldıńǵı jaǵınan elementti alıp taslaydı).
* Terekler elementlerdiń ierarxiyalıq shólkemin bildiredi. Terek tárepleri menen baylanıstırılǵan túyinlerden ibarat, bir túyin túbir, al qalǵan barlıq túyinler ishki tereklerdi quraydı. Terekler hár túrli algoritmler menen maǵlıwmatlardı saqlaw scenariylerinde keńnen qollanıladı. Binar terekler (ásirese úyindiler), AVL terekleri hám B-terekleri tereklerdiń ayırım ataqlı túrleri bolıp tabıladı. Olar maǵlıwmatlardı ónimli hám optimal izlewge, saralawǵa hám ierarxiyalıq usınıwǵa imkaniyat beredi.
* Terek, sonıń menen qatar prefiks teregi retinde belgili, qatarlardı ónimli shıǵarıp alıw ushın paydalanılatuǵın arnawlı terek maǵlıwmatlar strukturası. Hár tárepi belgini bildiretuǵın qatardıń belgilerin túyinler retinde saqlawǵa háreket etedi. Olar ásirese avtotoltırıw, imlanı tekseriw hám sózdi kirgiziw sıyaqlı tekstti qayta islew scenariylerinde paydalı. Háreketler qatarlarda tez izlewdi hám prefiks tiykarındaǵı háreketlerdi qosadı. 

## Tildi qollaw
Kóplegen assembler tillerinde hám BCPL (ingl. Basic Combined Programming Language - tiykarǵı biriktirilgen programmalastırıw tili) sıyaqlı ayırım tómen dárejeli tillerde maǵlıwmatlar strukturaları ushın ornatılǵan qollap-quwatlaw joq. Ekinshi jaǵınan, kóplegen joqarı dárejeli programmalastırıw tillerinde hám MASM sıyaqlı ayırım joqarı dárejeli assembler tillerinde jazıwlar menen massivler sıyaqlı belgili bir maǵlıwmatlar strukturası ushın arnawlı sintaksis yamasa basqa ornatılǵan qollaw bar. Mısalı, C (BCPL-diń tikkeley áwladı) hám Paskal tilleri vektorlardan (bir ólshemli massivler) hám kóp ólshemli massivlerden basqa sáykesinshe strukturalar menen jazıwlardı qollaydı.

Kóplegen programmalastırıw tillerinde maǵlıwmatlar strukturasın ámelge asırıwdı hár túrli baǵdarlamalar menen qayta paydalanıwǵa imkaniyat beretuǵın kitapxana mexanizminiń qanday da bir túri bar. Házirgi tiller ádette eń kóp tarqalǵan maǵlıwmatlar strukturaların ámelge asıratuǵın standart kitapxanalar menen birge keledi. Mısallar C++ te standart shablonlar kitapxanası, Java kollekciyaları sheńberi hám Microsoft .NET Framework bolıp tabıladı.

Házirgi tillerde de ulıwma modullik programmalastırıwdı, kitapxana moduliniń interfeysi menen onı ámelge asırıwdı ajıratıwdı qollaydı. Ayırımlar klientlerge ámelge asırıw maǵlıwmatların jasırıwǵa imkaniyat beretuǵın anıq emes maǵlıwmatlar túrlerin usınadı. C++, Java hám Smalltalk sıyaqlı obyektke baǵdarlanǵan programmalastırıw tilleri ádette usı maqset ushın klaslardı paydalanadı..

Kóplegen belgili maǵlıwmatlar strukturalarında bir neshe esaplaw aǵımlarına maǵlıwmatlar strukturasınıń bir anıq versiyasına bir waqıtta kiriwge imkaniyat beretuǵın versiyaları bar.

## Derekler

## Qosımsha oqıw

* Alfred Aho, John Hopcroft, and Jeffrey Ullman, *Data Structures and Algorithms*, Addison-Wesley, 1983,  
* G. H. Gonnet and R. Baeza-Yates, *[https://users.dcc.uchile.cl/~rbaeza/handbook/hbook.html Handbook of Algorithms and Data Structures - in Pascal and C]*, second edition, Addison-Wesley, 1991,  
* Ellis Horowitz and Sartaj Sahni, *Fundamentals of Data Structures in Pascal*, Computer Science Press, 1984,  

## Sırtqı siltemeler

* Descriptions from the Dictionary of Algorithms and Data Structures
* Data structures course
* [An Examination of Data Structures from .NET perspective](http://msdn.microsoft.com/en-us/library/aa289148(VS.71).aspx)
* Schaffer, C. ''Data Structures and Algorithm Analysis''