Տվյալների կառուցվածքներ

Համակարգչային գիտության մեջ տվյալների կառուցվածքը տվյալների կազմակերպման և պահպանման ձևաչափ է, որը սովորաբար ընտրվում է տվյալների արդյունավետ հասանելիության համար^[1][2][3]։ Ավելի ճիշտ, տվյալների կառուցվածքը տվյալների արժեքների, դրանց միջև փոխհարաբերությունների և գործառույթների կամ գործողությունների հավաքածու է, որը կարող է կիրառվել տվյալների վրա ^[4], այսինքն՝ այն տվյալների վերաբերյալ հանրահաշվական կառուցվածք է:

Տվյալների կառուցվածք, որը հայտնի է որպես հեշ աղյուսակ :

Կիրառություն

Տվյալների կառուցվածքները ծառայում են որպես վերացական(աբստրակտ) տվյալների տեսակների (ADT) հիմք: ADT-ն սահմանում է տվյալների տեսակի տրամաբանական ձևը: Տվյալների կառուցվածքը իրականացնում է տվյալների տեսակի ֆիզիկական ձևը^[5]։

Տվյալների կառուցվածքների տարբեր տեսակներ հարմար են տարբեր տեսակի հավելվածների համար, իսկ որոշները խիստ մասնագիտացված են կոնկրետ խնդիրներ լուծելու համար: Օրինակ, ռելյացիոն տվյալների բազաները սովորաբար օգտագործում են B-tree ինդեքսներ՝ տվյալներ փնտրելու համար^[6], մինչդեռ կոմպիլյատորների իրականացումների մեջ սովորաբար օգտագործում են հեշ աղյուսակներ՝ իդենտիֆիկատորներ փնտրելու համար^[7]:

Տվյալների կառուցվածքները թույլ են տալիս արդյունավետ կառավարել մեծ ծավալի տվյալների այնպիսի ծրագրեր, ինչպիսիք են տվյալների բազաները և ինտերնետի ինդեքսավորման ծառայությունները: Որպես կանոն, արդյունավետ տվյալների կառուցվածքները արդյունավետ ալգորիթմների նախագծման բանալին են: Որոշ ֆորմալ նախագծման մեթոդներ և ծրագրավորման լեզուներ կարևորում են տվյալների կառուցվածքները, այլ ոչ թե ալգորիթմները՝ որպես ծրագրային ապահովման մշակման հիմնական գործոն: Տվյալների կառուցվածքները կարող են օգտագործվել ինչպես հիմնական, այնպես էլ երկրորդային հիշողության մեջ պահվող տեղեկատվության պահպանման և որոնման կազմակերպման համար^[8]:

Իրականացում

Տվյալների կառուցվածքները կարող են իրականացվել տարբեր ծրագրավորման լեզուների միջոցով, սակայն դրանք բոլորն ունեն տվյալների արդյունավետ կազմակերպման և պահպանման ընդհանուր նպատակ^[9]: Տվյալների կառուցվածքները սովորաբար հենվում են համակարգչի՝ իր հիշողության մեջ տվյալներ ստանալու և պահելու ունակության վրա, որը նշված է ցուցիչով՝ բիթային տող, որը ներկայացնում է հիշողության հասցե, որն ինքնին կարող է պահվել հիշողության մեջ և կառավարվել ծրագրի կողմից: Այսպիսով, զանգվածի և գչառման տվյալների կառուցվածքները հիմնված են տվյալների տարրերի հասցեների հաշվարկման վրա՝ օգտագործելով թվաբանական գործողությունները, մինչդեռ հարակից տվյալների կառուցվածքները հիմնված են տվյալների տարրերի հասցեները հենց կառուցվածքում պահելու վրա: Տվյալների կառուցվածքի այս մոտեցումը խորը հետևանքներ ունի ալգորիթմների արդյունավետության և մասշտաբայնության վրա: Օրինակ, զանգվածներում հարակից հիշողության բաշխումը հեշտացնում է արագ մուտքի և փոփոխման գործողությունները, ինչը հանգեցնում է օպտիմիզացված հաջորդական մշակմանը^[10]:

Հերթի և պահունակի տարբերությունը

Տվյալների կառուցվածքի ներդրումը սովորաբար պահանջում է գրել մի շարք պրոցեդուրաներ, որոնք ստեղծում և շահարկում են այդ կառուցվածքի օրինակները: Տվյալների կառուցվածքի արդյունավետությունը չի կարող վերլուծվել այս գործողություններից առանձին: Այս դիտարկումը դրդում է վերացական տվյալների տիպի տեսական հայեցակարգը՝ տվյալների կառուցվածք, որն անուղղակիորեն որոշվում է դրա վրա կատարվող գործողություններով և այդ գործողությունների մաթեմատիկական հատկություններով (ներառյալ դրանց տարածական և ժամանակային ծախսերը)^[11]:

Օրինակներ

Կան բազմաթիվ տեսակի տվյալների կառուցվածքներ, որոնք սովորաբար կառուցված են ավելի պարզ տվյալների տեսակների վրա: Հայտնի օրինակներն են^[12]՝

• Զանգվածը որոշակի կարգով դասավորված մի քանի տարրեր է՝ սովորաբար նույն տեսակի (կախված լեզվից, առանձին տարրեր կարող են ստիպել լինել նույն տիպի, կամ կարող են լինել գրեթե ցանկացած տեսակի)։ Տարրերը հասանելի են՝ օգտագործելով ամբողջ թվի ինդեքսը, որը ցույց է տալիս, թե որ տարրն է պահանջվում:Զանգվածները կարող են լինել ֆիքսված երկարությամբ կամ փոխվող երկարությամբ:
• Կապակցված ցուցակը (նաև կոչվում է պարզապես ցուցակ) ցանկացած տեսակի տվյալների տարրերի գծային հավաքածու է, այդ հավաքածուի տարրերը կոչվում է հանգույցներ, որտեղ յուրաքանչյուր հանգույց ունի արժեք և հղում որը ցույց է տալիս հաջորդ հանգույցը: Կապակցված ցուցակի հիմնական առավելությունը զանգվածի նկատմամբ այն է, որ արժեքները միշտ կարող են արդյունավետ կերպով տեղադրվել և հեռացվել՝ առանց ցուցակի մնացած մասը տեղափոխելու: Այնուամենայնիվ, որոշ այլ գործողություններ, ինչպիսիք են կոնկրետ տարրի պատահական մուտքը, ավելի դանդաղ են ընթանում ցուցակներում, քան զանգվածներում:
• Հեշ աղյուսակները, որոնք նաև հայտնի են որպես հեշ քարտեզներ, տվյալների կառուցվածքներ են, որոնք ապահովում են արժեքների արագ որոնում՝ հիմնված բանալիների վրա: Նրանք օգտագործում են հեշավորման ֆունկցիա՝ բանալիները զանգվածի ինդեքսներին համապատասխանեցնելու համար: Հեշ աղյուսակները լայնորեն օգտագործվում են բառարաններում, քեշերում և տվյալների բազայի ինդեքսավորման մեջ: Այնուամենայնիվ, հեշ աղյուսակների հետ աշխատելիս կարող են առաջանալ բախումներ, ինչը բացասաբար է անդրադառնում դրանց աշխատանքի վրա: Բախումների դեմ պայքարելու համար օգտագործվում են այնպիսի մեթոդներ, ինչպիսիք են շղթայական կապը և բաց հասցեավորումը:
• Գրաֆները հանգույցների շարք են, որոնք միացված են կողերով, որոնք ներկայացնում են հարաբերությունները սուբյեկտների միջև: Գրաֆները կարող են օգտագործվել սոցիալական ցանցերի, համակարգչային ցանցերի, տրանսպորտային ցանցերի և այլն մոդելավորելու համար: Դրանք բաղկացած են գագաթներից (հանգույցներից) և կողերից(հանգույցների միջև կապեր): Գրաֆները կարող են լինել ուղղորդված կամ չուղղորդված, ունենալ ցիկլեր կամ լինել ացիկլիկ: Գրաֆի անցման ալգորիթմները ներառում են որոնում լայնությամբ և որոնում խորությամբ:
• Պահունակը և հերթերը տվյալների վերացական տեսակներ են, որոնք կարող են իրականացվել զանգվածների կամ կապակցված ցուցակների միջոցով: Պահունակն ունի երկու հիմնական գործողություն՝ push (ավելացնում է տարր կույտի վերին մասում) և pop (հեռացնում է ամենավերին տարրը կույտից), որոնք հետևում են Last In, First Out (LIFO) սկզբունքին: Հերթերն ունեն երկու հիմնական գործողություն՝ հերթում (հերթի վերջում տարր է ավելացնում) և հերթում (հերթի առջևից հեռացնում է տարրը), որոնք հետևում են First In, First Out (FIFO) սկզբունքին:.
• Ծառերը ներկայացնում են տարրերի հիերարխիկ դասավորվածություն: Ծառը բաղկացած է կողերով միացված հանգույցներից, որոնցից մեկը արմատն է, իսկ մյուս բոլոր հանգույցները՝ ենթածառեր: Ծառերը լայնորեն օգտագործվում են տարբեր ալգորիթմների և տվյալների պահպանման համար: Բինար ծառերը (մասնավորապես՝ կույտերը), AVL ծառերը և B-ծառերը ծառերի որոշ հայտնի տեսակներ են: Դրանք ապահովում են տվյալների արդյունավետ և օպտիմալ որոնում, տեսակավորում և հիերարխիկ ներկայացում:

Ծրագրավորման լեզվի կողմից աջակցություն

Ասսեմբլերային լեզուների մեծ մասը և որոշ ցածր մակարդակի լեզուներ, ինչպիսիք են BCPL-ը, չունեն տվյալների կառուցվածքների ներկառուցված աջակցություն: Մյուս կողմից, շատ բարձր մակարդակի ծրագրավորման լեզուներ և որոշ ավելի բարձր մակարդակի ասսեմբլերի լեզուներ, ինչպիսիք են MASM-ը, ունեն հատուկ շարահյուսություն կամ այլ ներկառուցված աջակցություն որոշակի տվյալների կառուցվածքների համար, ինչպիսիք են զանգվածները: Օրինակ, C (BCPL-ի անմիջական ժառանգորդը) և Պասկալ լեզուները համապատասխանաբար աջակցում են կառուցվածքներին, բացի վեկտորներից (միաչափ զանգվածներ) և բազմաչափ զանգվածներից^[13][14]։

Ծրագրավորման լեզուներից շատերն ունեն գրադարանային մեխանիզմ, որը թույլ է տալիս տվյալների կառուցվածքի իրականացումը վերօգտագործել տարբեր ծրագրերի կողմից: Ժամանակակից լեզուները սովորաբար ունեն ստանդարտ գրադարաններ, որոնք իրականացնում են տվյալների ամենատարածված կառուցվածքները: Օրինակներ են C++ Ստանդարտ Կաղապարների գրադարանը(STL), Java Collections Framework-ը և Microsoft .NET Framework-ը:

Ժամանակակից լեզուները նաև ընդհանուր առմամբ աջակցում են մոդուլային ծրագրավորմանը՝ գրադարանային մոդուլի միջերեսի և դրա իրականացման միջև բաժանումը: Ոմանք տրամադրում են տվյալների անթափանց տեսակներ, որոնք թույլ են տալիս հաճախորդներին թաքցնել իրականացման մանրամասները: Օբյեկտ-կողմնորոշված ​​ծրագրավորման լեզուները, ինչպիսիք են C++-ը, Java-ն և Smalltalk-ը, սովորաբար օգտագործում են դասեր այդ նպատակով:

Շատ հայտնի տվյալների կառուցվածքներ ունեն զուգահեռ տարբերակներ, որոնք թույլ են տալիս մի քանի հաշվողական հոսքերին միաժամանակ հասանելություն ունենալ տվյալների կառուցվածքի մեկ կոնկրետ օրինակին ^[15]։

Ծանոթագրություններ

1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press. ISBN 978-0262033848.
2. Black, Paul E. (15 December 2004). «data structure». In Pieterse, Vreda; Black, Paul E. (eds.). Dictionary of Algorithms and Data Structures [online]. National Institute of Standards and Technology. Վերցված է 2018-11-06-ին.
3. «Data structure». Encyclopaedia Britannica. 17 April 2017. Վերցված է 2018-11-06-ին.
4. Wegner, Peter; Reilly, Edwin D. (2003-08-29). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. էջեր 507–512. ISBN 978-0470864128.
5. «Abstract Data Types». Virginia Tech - CS3 Data Structures & Algorithms. Արխիվացված օրիգինալից 2023-02-10-ին. Վերցված է 2023-02-15-ին.
6. Gavin Powell (2006). «Chapter 8: Building Fast-Performing Database Models». Beginning Database Design. Wrox Publishing. ISBN 978-0-7645-7490-0. Արխիվացված օրիգինալից 2007-08-18.{{cite book}}: CS1 սպաս․ unfit URL (link)
7. «1.5 Applications of a Hash Table». University of Regina - CS210 Lab: Hash Table. Արխիվացված է օրիգինալից 2021-04-27-ին. Վերցված է 2018-06-14-ին.
8. «When data is too big to fit into the main memory». Indiana University Bloomington - Data Structures (C343/A594). 2014. Արխիվացված է օրիգինալից 2018-04-10-ին.
9. Vaishnavi, Gunjal; Shraddha, Gavane; Yogeshwari, Joshi (2021-06-21). «Survey Paper on Fine-Grained Facial Expression Recognition using Machine Learning» (PDF). International Journal of Computer Applications. 183 (11): 47–49. doi:10.5120/ijca2021921427.
10. Nievergelt, Jürg; Widmayer, Peter (2000-01-01), Sack, J. -R.; Urrutia, J. (eds.), «Chapter 17 - Spatial Data Structures: Concepts and Design Choices», Handbook of Computational Geometry, Amsterdam: North-Holland, էջեր 725–764, ISBN 978-0-444-82537-7, Վերցված է 2023-11-12-ին
11. Dubey, R. C. (2014). Advanced biotechnology : For B Sc and M Sc students of biotechnology and other biological sciences. New Delhi: S Chand. ISBN 978-81-219-4290-4. OCLC 883695533.
12. Seymour, Lipschutz (2014). Data structures (Revised first ed.). New Delhi, India: McGraw Hill Education. ISBN 9781259029967. OCLC 927793728.
13. «The GNU C Manual». Free Software Foundation. Վերցված է 2014-10-15-ին.
14. Van Canneyt, Michaël (September 2017). «Free Pascal: Reference Guide». Free Pascal.
15. Mark Moir and Nir Shavit. «Concurrent Data Structures» (PDF). cs.tau.ac.il. Արխիվացված է օրիգինալից (PDF) 2011-04-01-ին.

Գրականություն

• Peter Brass, Advanced Data Structures, Cambridge University Press, 2008, 978-0521880374
• Donald Knuth, The Art of Computer Programming, vol. 1. Addison-Wesley, 3rd edition, 1997, 978-0201896831
• Dinesh Mehta and Sartaj Sahni, Handbook of Data Structures and Applications, Chapman and Hall/CRC Press, 2004, 1584884355
• Niklaus Wirth, Algorithms and Data Structures, Prentice Hall, 1985, 978-0130220059

Հետագա ընթերցման համար

• Alfred Aho, John Hopcroft, and Jeffrey Ullman, Data Structures and Algorithms, Addison-Wesley, 1983, 0-201-00023-7
• G. H. Gonnet and R. Baeza-Yates, Handbook of Algorithms and Data Structures - in Pascal and C, second edition, Addison-Wesley, 1991, 0-201-41607-7
• Ellis Horowitz and Sartaj Sahni, Fundamentals of Data Structures in Pascal, Computer Science Press, 1984, 0-914894-94-3

Արտաքին հղումներ

• Descriptions from the Dictionary of Algorithms and Data Structures
• Data structures course
• An Examination of Data Structures from .NET perspective
• Schaffer, C. Data Structures and Algorithm Analysis