Kontentke ótiw

Maǵlıwmatlar strukturası

Wikipedia, erkin enciklopediya
Xesh kestesi retinde belgili maǵlıwmatlar strukturası

Informatikada maǵlıwmatlar strukturası (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ı.[1][2] 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ǵı,[3] yaǵnıy bul maǵlıwmatlar tuwralı algebralıq struktura.

Qollanılıwı[redaktorlaw | derekti redaktorlaw]

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ı.[4]

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ı.[5]

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.[6]

Ámelge asırıw[redaktorlaw | derekti redaktorlaw]

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.[7] 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.[8]

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.[9]

Mısallar[redaktorlaw | derekti redaktorlaw]

Python 3 programmalastırıw tiliniń standart tip ierarxiyası.

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

  • 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.[11]
  • 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[redaktorlaw | derekti redaktorlaw]

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ı.[12][13]

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.[14]

Derekler[redaktorlaw | derekti redaktorlaw]

  1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms, Third Edition, 3rd, The MIT Press, 2009. ISBN 978-0262033848. 
  2. Black, Paul E.. Dictionary of Algorithms and Data Structures [online]. National Institute of Standards and Technology, 15 December 2004. 
  3. Wegner, Peter; Reilly, Edwin D.. Encyclopedia of Computer Science. John Wiley and Sons, 2003-08-29. ISBN 978-0470864128. 
  4. „Abstract Data Types“. Virginia Tech - CS3 Data Structures & Algorithms. 10-fevral 2023-jılda túp nusqadan arxivlendi. Qaraldı: 15-fevral 2023-jıl.
  5. „1.5 Applications of a Hash Table“. University of Regina - CS210 Lab: Hash Table. 27-aprel 2021-jılda túp nusqadan arxivlendi. Qaraldı: 14-iyun 2018-jıl.
  6. „When data is too big to fit into the main memory“. Indiana University Bloomington - Data Structures (C343/A594) (2014). 10-aprel 2018-jılda túp nusqadan arxivlendi.
  7. Vaishnavi, Gunjal; Shraddha, Gavane; Yogeshwari, Joshi (2021-06-21). "Survey Paper on Fine-Grained Facial Expression Recognition using Machine Learning". International Journal of Computer Applications 183 (11): 47–49. doi:10.5120/ijca2021921427. http://www.ijcaonline.org/archives/volume183/number11/vaishnavi-2021-ijca-921427.pdf. 
  8. Nievergelt, Jürg; Widmayer, Peter (2000-01-01), Sack, J. -R.; Urrutia, J. (red.), „Chapter 17 - Spatial Data Structures: Concepts and Design Choices“, Handbook of Computational Geometry, Amsterdam, 725–764-bet, ISBN 978-0-444-82537-7, qaraldı: 2023-11-12 {{citation}}: Unknown parameter |publisher= ignored (járdem)
  9. Dubey, R. C.. Advanced biotechnology : For B Sc and M Sc students of biotechnology and other biological sciences.. New Delhi: S Chand, 2014. ISBN 978-81-219-4290-4. OCLC 883695533. 
  10. Seymour, Lipschutz. Data structures, Revised first, New Delhi, India: McGraw Hill Education, 2014. ISBN 9781259029967. OCLC 927793728. 
  11. Walter E. Brown. „C++ Language Note: POD Types“. Fermi National Accelerator Laboratory (29-sentyabr 1999-jıl). 3-dekabr 2016-jılda túp nusqadan arxivlendi. Qaraldı: 6-dekabr 2016-jıl.
  12. „The GNU C Manual“. Free Software Foundation. Qaraldı: 15-oktyabr 2014-jıl.
  13. Van Canneyt. „Free Pascal: Reference Guide“. Free Pascal (sentyabr 2017).
  14. Mark Moir and Nir Shavit. „Concurrent Data Structures“. cs.tau.ac.il. 1-aprel 2011-jılda túp nusqadan arxivlendi.

Qosımsha oqıw[redaktorlaw | derekti redaktorlaw]

  • Alfred Aho, John Hopcroft, and Jeffrey Ullman, Data Structures and Algorithms, Addison-Wesley, 1983,  
  • G. H. Gonnet and R. Baeza-Yates, 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[redaktorlaw | derekti redaktorlaw]