Mavzu: Ma’lumotlarning nochiziqiy tuzilmasi kirish 2 I. Ma’lumotlar tuzilmalari va algoritmlari

1.2 Ma’lumotlar tuzilmalarining klassifikatsiyasi.

O’zining mazmuni va murakkabligidan qat’iy nazar barcha ma’lumotlar kompyuter xotirasida ikkilik razryadlari yoki bitlar ketmaketligida tasvirlanadi, demak ularni olgan qiymatlari ham mos ravishda ikkilik sonlardan iborat bo’ladi. Bitlar ketma-ketligi shaklidagi ma’lumotlar juda oddiy tashkil qilingan yoki boshqacha aytganda kuchsiz tuzilmalashtirilgan bo’ladi. Murakkab ma’lumotlarni bitlar ketma-ketligi terminlarida talqin qilish juda noqulaydir. Ixtiyoriy ma’lumotlarni tashkil qilish uchun bit sonog’iga ko’ra ma’noli va yirikroq bo’lgan “qurilish bloklari”- “ma’lumotlar tuzilmalari” tushunchasi asosida hosil qilinadi. Ma’lumotlar tuzilmalari deb umumiy xolda ma’lumotlar elementlarini to’plami va ular orasidagi bog’lanishlar to’plamiga aytiladi. Ma’lumotlar tuzilmalarining bunday ta’rifi ma’lumotlar tuzilmalariga barcha mumkin bo’lgan kirib borishlarni qamrab oladi, ammo har bir aniq masala uchun u yoki bu aspektlar qo’llaniladi.

Shu maqsadda ma’lumotlar tuzilmalariga qo’shimcha klassifikatsiya kiritilgan bo’lib, yo’nalishlariga ko’ra ularni ko’rib chiqishning turli aspektlariga mos keladi. Aniq bir ma’lumotlar tuzilmalarini o’rganishdan avval, ularga bir necha xususiyatlariga ko’ra umumiy klassifikatsiya beramiz.

“Ma’lumotlarning fizik tuzilmalari” tushunchasi mashina xotirasida ma’lumotlarni fizik tasvirlash usullarini aks ettiradi va yana saqlash tuzilmasi, ichki tuzilma yoki xotira tuzilmasi deb ataladi.

Ma’lumotlar tuzilmalarini mashina xotirasidan tashqari tasvirlash abstrakt yoki mantiqiy tuzilma deb ataladi. Umumiy xolda mantiqiy tuzilma va unga mos ravishdagi fizik tuzilma orasida farqlanish mavjud bo’lib, uning darajasi tuzilmaning o’zidan va u aniqlanishi kerak bo’lgan muhitga bog’liq bo’ladi. Hozirda mantiqiy tuzilmalar fizik tuzilma ko’rinishida va aksincha fizik tuzilmani mantiqiy ko’rinishda tasvirlovchi protseduralar mavjud. Ushbu protseduralar yordamida fizik tuzilmalarga kirib bori shva ular ustida amallar bajarish mumkin.

Tuzilmalar oddiy (bazaviy, primitiv) va integrallashgan(struk- turlashgan, murakkab, yig’ma) tuzilmalarga bo’linadi. Oddiy tuzilmalar deb bit tarkibiy qismlargacha bo’lina oladigan tuzilmalarga aytiladi. Ma’lumotlarning fizik tuzilmalari nuqtai nazari bilan qaralsa, berilgan odddiy tuzilmalarning o’lchovi va uni xotiraga joylashtirish tuzilmasi ushbu mashina arxitekturasida yoki dasturlash tizimida qanday bo’lishini oldindanayta olish mumkin. Ma’lumotlar tuzilmalarini mantiqiy nuqtai nazariga ko’ra oddiy tuzilmalar bo’linmas birliklar hisoblanadilar. Integrallashgan tuzilmalar deb tarkibiy qismlari oddiy yoki o’z navbatida integrallashgan ma’lumotlar tuzilmalariga aytiladi. Integrallashtirilgan ma’lumotlar tuzilmalari dasturchi tomonidan dastur tillaridagi ma’lumotlarni integratsiya vositalarini qo’llagan xolda quriladi.

Ma’lumotlar elementlari orasidagi bog’lanishlarni yaqqol mavjudligi yoki ularni yo’qligiga qarab ma’lumotlar tuzilmalari bog’lanmagan (vektorlar, massivlar, satrlar, steklar, navbatlar) va bog’langan (bog’langan ro’yxatlar) ko’rinishida bo’ladilar.

Ma’lumotlar tuzilmalarining muhim belgisi - uning o’zgaruvchanligi- elementlar sonini va ular orasidagi bog’lanishlarni o’zgarib turishidir. O’zgaruvchanlik belgisiga ko’ra ma’lumotlar tuzilmalari statistik, yarimstatistik va dinamik tuzilmalarga bo’linadilar. 1.1. chizmada ma’lumotlar tuzilmalari o’zgaruvchanligi belgisiga ko’ra klassifikatsiyasi keltirilgan. Ma’lumotlar tuzilmalarining bazaviy, statistik, yarimstatistik va dinamik ko’rinishlari tezkor xotiraga xos bo’ladi va ularni tezkor tuzilmalar deb ataydilar. Fayl tuzilmalari esa tashqi xotira ma’lumotlari tuzilmalariga mos keladilar.

Ma’lumotlar tuzilmalarining muhim belgisi - uning elementlarini tartiblana olishi xossasidir. Ushbu belgiga ko’ra tuzilmalarni chiziqli va chiziqli bo’lmagan tuzilmalarga ajratish mumkin. Chiziqli tuzilmalar elementlarini xotirada o’zaro yaqin joylashishi xossasiga ko’ra ularni xotirada ketma-ket joylashgan (vektorlar, satrlar, massivlar, steklar, navbatlar) va ixtiyoriy bog’lanib taqsimlangan (bir bog’lamli, ikki bog’lamli ro’yxatlar) tuzilmalarga ajratish mumkin. Chiziqli bo’lmagan tuzilmalarga misol tariqasida ko’p bog’langan ro’yxatlar, daraxtlar, grafalarni keltirish mumkin.

Dasturlash tillarida «ma’lumotlar tuzilmalari” tushinchasi “ma’lumotlar turi” tushinchasi bilan chambarchas bog’langandir. Barcha ma’lumotlar - konstantalar, o’zgaruvchilar, funktsiya qiymatlari yoki ifodalar o’zlarining turlari bilan tavsiflanadilar. Har bir tur bo’yicha axborot bir ma’noda aniqlanadi:

Ko’rsatilgan turning ma’lumotlarini saqlash tuzilmasi, ya’ni unga xotirani ajratish va ma’lumotlarni unda bir tomondan tasvirlansa, ikkinchi tomondan uni ikkilik ko’rinishini tushuntirib beradi;

Tur tomonidan tasvirlangan u yoki bu obyektning qabul qilishi mumkin bo’lgan qiymatlari to’plami;

Tur tomonidan tasvirlanayotgan obyektga qo’llanilishi mumkin bo’lgan amallar to’plami.

Har qanday ma’lumotlar tuzilmalari ustida umumiy bo’lgan to’rt amalni bajarish mumkin: yaratish, yo’q qilish, tanlash (kirib borish), yangilash.

Ma’lumotlar tuzilmalari yaratish amali deganda ma’lumotlar tuzilmalariga xotirada joy ajratilishi tushiniladi. Xotira dastur bajarilishi jarayonida yoki kompilyatsiya bosqichida ajratilishi mumkin. Bir qator tillarda (masalan C da) dasturchi tomonidan strukturlashtirilgan ma’lumotlar uchun yaratish amali o’z ichiga tuzilma tomonidan hosil qilinadigan parametrlarni boshlang’ich qiymatlarini o’rnatishni ham o’z ichiga oladi. Masalan, PL/1 da DECLARE N FIXED DECIMAL e’loni N o’zgaruvchi uchun manzil kengligini ajratishga olib keladi. FORTRANda (Integer I), PASCALda (I:Integer), C da (Int I) tur e’loni natijasida ushbu o’zgaruvchilar uchun mos xotira ajratiladi. Dasturda e’lon qilingan ma’lumotlar tuzilmalari uchun xotira avtomatik ravishda Dasturlash tizimi vositalari orqalikopilyatsiya bosqichida , yoyinki mos o’zgaruvchilar e’lon qilinadigan protsedura blokini aktivlashgan vaqtida ajratiladi. Dasturlash tizimida mavjud ajratish-ozod qilish prqedura (funktsiya)ni qo’llagan xolda dasturchining o’zi ham ma’lumotlar tuzilmalari uchun xotirani ajratishi mumkin. Obyektga- mo’ljallangan Dasturlash tillarida yangi obyektlar tuzilayotganida obyekt uchun yaratish va yo’q qilish protseduralari aniqlangan bo’lishi kerak. Muhimi bunda, dasturlash tilidan qat’iy nazar, dasturdagi mavjud ma’lumotlar tuzilmalari “hech qayerdan” paydo bo’lmay balki bilvosita yoki bevosita tuzilmalarni tuzish operatorlari yordamida e’lon qilinadidar. Buning natijasida dasturdagi barcha tuzilma nusxalariga ularni joylashtirish uchun xotira ajratiladi.

Ma’lumotlar tuzilmalarini xotiradan o’chirish amallari ularni yaratish amallariga nisbatan qarama-qarshi yo’nalishda olib boriladi. Ba’zi bir BASIC,

FORTRAN kabi tillar dasturchiga ma’lumotlar tuzilmalarini o’chirishni imkonini bermaydi. PL/1, Pascal tillarida blok ichida joylashgan ma’lumotlar tuzilmalari ushbu blok tashqarisiga chiqqanidan so’ng dastur bajarilishi jarayonida o’chiriladi.

O’chirish amali xotiradan samarali foydalanish uchun qo’llaniladi.

Tanlash amallari dasturchilar tomonidan tuzilmalar ichida joylashgan ma’lumotlarga kirib borishni amaliy shakli murojaat qilinayotgan ma’lumotlar tuzilmalari turiga bog’liqdir. Kirish usuli - tuzilmalarning muhim xususiyatlaridan biri bo’lib, bu xususiyat aniq ma’lumotlar tuzilmalarini tanlashda bevosita rol o’ynaydi.

Yangilash amali ma’lumotlar tuzilmalarida ma’lumotlar qiymatlarini o’zgartirishga imkon beradi. Masalan: qiymat berish, yoki yanada murakkab shakli parametrlarni uzatish.

Yuqorida keltirilgan to’rt amal barcha tuzilmalar va turlar uchun majburiy bajariladigan amallar hisoblanadi. Bu umumiy amallardan tashqari har bir ma’lumotlar tuzilmalari uchun maxsus o’ziga xos faqat ushbu ma’lumotlar turi

(ma’lumotlar tuzilmalari) bilan ish olib boruvchi amallar aniqlangan bo’lishi mumkin.

1.2.1 Ma’lumotlarning chiziqli tuzilmalari.