Dasturlash asoslari

9.1.1.2. Ma’lumotlar tarkibini sinflash

Mohiyati va murakkabligiga bog‘liq bo‘lmagan holda ixtiyoriy ma’lumotlar EHM xotirasida ikkilik razryadlari yoki bitlari ketma-ketligi shaklida tasvirlanadi, ularning qiymatlari esa mos ravishda ikkilik sonlari bo‘ladi. Ketma-ket bitlar ko‘rinishda qaralayotgan ma’lumotlar juda sodda ko‘rinishga ega bo‘ladi yoki boshqacha aytganda kuchsiz tarkiblangan bo‘ladi. Qandaydir murakkab ma’lumotlarni bitlar ketma-ketligi terminlarida yoritish va tadqiq qilish odam uchun juda ham noqulay. Bitlarga nisbatan yanada yirik va mohiyatli ya’ni “qurilish blokli” tiplar esa “ma’lumotlarning tarkibi” tushunchasi asosida olinadi.

Ta’rif. Umumiy holda ma’lumotlar tarkibi deganda ma’lumotlar elementlari to‘plami ular orasidagi aloqalar to‘plami tushuniladi.
Bu ta’rif ma’lumotlar tarkiblashtirishdagi mumkin bo‘lgan barcha yo‘llarni qamrab oladi, lekin har bir aniq masala uchun u yoki bu aspektlar ishlatiladi. Shuning uchun ham ularni har xil aspektlarda qarashga mosligi bo‘yicha qo‘shimcha ravishda ma’lumotlar sinflarga ajratiladi. Ma’lumotlar aniq birini o‘rganishdan avval, ularga mos bir qancha belgilar bo‘yicha umumiy sinflarga bo‘lamiz.
“Ma’lumotlarni fizik tarkibi” tushunchasi mashinada ma’lumotlarni mashina xotirasida fizik tasvirlash usulini ifodalaydi va saqlash tarkibi, ichki tartib yoki xotira tarkibi deb ham ataladi.
Ma’lumotlarni mashina xotirasida tasvirlashni hisobga olmay qaralishi esa ularni abstrakt yoki mantiqiy tarkibi deyiladi. Umuman olganda mantiqiy va unga mos fizik tarkibi o‘rtasida farq mavjud. Bu erda ma’lumotlarni akslantirilishi bo‘yicha farqlanish darajasi tarkibning o‘ziga ko‘ra va mazkur muhit xususiyatiga bog‘liq bo‘ladi. Bu farqlanishga ko‘ra mantiqiy tarkibni fizik tarkibga va aksincha fizik tarkibni mantiqiy tarkibga tasvirlash protseduralari mavjud. Bundan tashqari mazkur protseduralar ular ustida har xil amallarni bajarishni ta’minlaydi. Bunda har bir amal mantiqiy va fizik ma’lumotlar tarkibiga qo‘llanish nuqtai nazaridan qaraladi.
Ma’lumotlar tarkibi sodda (tayanch, primitiv) va integrallashgan (tarkiblashtirilgan, kompozit, murakkab) kabilarga bo‘linadi. Shunday ma’lumotlar tarkibi sodda deyiladiki, bunda ular bundan katta bo‘lmagan boshqa qo‘shimcha bo‘laklarga bo‘linmaydi. Fizik tarkib nuqtai nazaridan bunday mashina arxitekturasida, ushbu dasturiy tizimda biz har doim sodda tipning o‘lchovi va uni xotiraga joylashtirish tarkibi qandayligini avvaldan turib aytib berishimiz muhim ahamiyatga ega. Mantiqiy nuqtai nazardan esa sodda ma]lumotlar bo‘linmas birlikdir. qo‘shma qismlari o‘z navbatida boshqa tiplar, ya’ni sodda yoki yana integrallashgan tiplardan tashkil topgan ma’lumotlar tarkibi integrallashgan ma’lumotlar tarkibi deyiladi.
Integrallashgan ma’lumotlar tarkibi dasturchi tomonidan dasturlash tili imkoni bo‘yicha ma’lumotlarni integratsiyasini vositalari ishlatish orqali yaratiladi.
Element orasida oshkor aloqa yo‘q yoki mavjudligiga ko‘ra bog‘lanmagan tarkiblar (vektorlar, massivlar, qatorlar, steklar, navbatlar) va bog‘langan tarkiblarga (bog‘langan ro‘yxatlar) bo‘linadi.
Ma’lumotlar tarkibini o‘ta muhim xususiyatiga uni o‘zgarib turishi, elementlar sonini o‘zgarishi va elementlari tarkibi orasidagi aloqalar soni o‘zgarib turishi kiradi. Tarkibning o‘zgaruvchilik ta’rifiga ma’lumotlar elementlari qiymatini o‘zgarish fakti hisobga olinmagan, vaholanki bu holda barcha ma’lumotlar tarkibi o‘zgaruvchanlik xususiyatiga ega bo‘ladi. O‘zgaruvchanlik belgisi bo‘yicha tarkiblar statik, yarimstatik va dinamik bo‘laklarga bo‘linadi. O‘zgaruvchanlik belgisi bo‘yicha ma’lumotlar tarkibini sinflarga bo‘linishi quyidagi chizmada keltirilgan.

Ma’lumotlar tarkibi



Sodda tayanch tarkibi

Faylli tarkiblar (fayllar)

Dinamik tarkiblar

Yarim statik tarkiblar

Statik tarkiblar

Sonli Vectorlar Ketma-ketliklar

Simvolli Massivlar Steklar To‘ridan-to‘g‘ri kirish
Mantiqiy To‘plamlar Navbatlar Kombinatsiyalashgan
Sanaladigan Yozuv Deklar kirish
Intervally Jadvallar Qatorlar Bo‘limlar orqali tashkil
Ko‘rsatkichlar etish


Chiziqli bog‘langan ro‘yxatlar
Tarmoqlashga bog‘langan ro‘yxatlar
Graflar
Daraxtlar

Ma’lumotlar tarkibini sinflash

Statik, yarimstatik va dinamik tayanch ma’lumotlar tarkibi operativ xotira uchun xarakterlidir va ko‘p hollarda ular operativli xotira deb ataladi.

Ma’lumotlarni muhim belgisi bu uning elementlarini tartiblashtirilgan xarakterligidadir. Shuning uchun tarkiblar belgisini chiziqli va chiziqsiz tarkiblarga bo‘lish mumkin.
Elementlarini operativ xotirada o‘zaro joylashish xarakteriga nisbatan chiziqli tuzilmalarni (tarkiblarni) ikkiga bo‘lish mumkin: xotirada elementlari taqsimlanganligi ketma-ketliklikda bo‘lgan tuzilmlar (tarkiblar) (vektorlar, qatorlar, massivlar, steklar, navbatlar) va xotirada elementlarning taqsimoti ixtiyoriy bog‘liqlikda bo‘lgan tuzilmlar (tarkiblar) (bir bog‘lamli, ikki bog‘lamli ro‘yxatlar). Chiziqsiz tarkiblarga ko‘p bog‘lamli ro‘yxatlar, daraxtlar va graflarni misol qilib keltirish mumkin.
Dasturlash tillarida “Ma’lumotlar tarkibi” tushunchasi “Ma’lumotlar tipi” tushunchasi bilan o‘zaro chambarchas bog‘langan. Ixtiyoriy ma’lumotlar, ya’ni konstantalar, o‘zgaruvchilar, funktsiyaning qiymatlari yoki ifodalar o‘zlarini tiplari bilan xarakterlanadilar.
Axborot har bir tip bo‘yicha quyidagilarga asosan bir qiymatli aniqlanadilar:
1) Ma’lumotlarning tipni saqlash tarkibi, deganda bir tomondan uning uchun xotira ajratilishi va ma’lumotlar unda tasvirlnishi, ikkinchi tomondan esa ikkilik tasvirlanishini interpretatsiyani amalgam oshirish tushuniladi.
2) E’lon qilinayotgan tipning u yoki bu ob’ekti mumkin bo‘lgan ruxsat etilgan qiymatlari to‘plami.
3) E’lon qilinayotgan ob’ektga qo‘llanilayotgan ruxsat etilgan amallar to‘plami.
Biz quyida yuqorida keltirilgan ma’lumotlar tarkibiga mos ularning ba’zi bir tiplari to‘g‘risidagi ma’lumotlarni qisqacha Pascal tili vositasida bayon etamiz.
Eng sodda ma’lumotlar tiplari.
Ixtiyoriy yangi sodda tiplar unga kiruvchi turli qiymatlarni sanab chiqish orqali aniqlanadi. Bunday tiplar sanaladigan tiplar deyiladi.
Uning aniqlanishi quyidagi ko‘rinishda bo‘ladi.
type T = (C₁, C₂,…C_n),
bu yerda T – yangi tip identifikatori, C_i (i = ) – yangi konstantalar identifikatorlari.
T - to‘plamning quvvati (elementlar soni) quyidagicha aniqlanadi:
Card (T) = n.
Misollar:
Type color = (red, yellow, green);
Type weekday = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday),
Type structure = (array, record, set, sequence)
Type meva = (olma, uzum, behi, shaftoli, nok)
Type object = (constant, type, variable, procedure, module)
Yuqorida keltirilgan tipli o‘zgaruvchilar quyidagicha e’lon qilinadi:
Var S: color;
W: weekday;
M: meva;
O: object;
Bu holda quyidagi o‘zlashtirish operatorlarini yozish mumkin:
S: = red;
M: = behi;
W: = Sunday;
O: = module;
Informativ shaklda bularni quyidagicha yozish mumkin:
S: = 1;
M: = 3;
W: = 7;
O: = 5;
Buni quyidagicha tushuntirish mumkin. S, M, W, O o‘zgaruvchilar butun son kabi aniqlanadi, kontaktlar esa ularni sanash tartibida natural songa akslantiradi. Misol uchun S o‘zgaruvchiga red o‘zlashtirilgan bo‘lsin, color tipidan ko‘rinib turibdiki u 1-o‘rinda turibdi, shuning uchun ham S o‘zgaruvchi 1 qiymatni qabul qiladi.
Eng sodda standart tiplar.
Bunday tiplar ko‘pchilik hisoblash mashina mavjud bo‘lgan tiplar hisoblanadi. Bularga butun sonlar, mantiqiy rostlik qiymatlari va chop qilinadigan simvollar to‘plami kiradi. Bundan tashqari ko‘pgina mashinalardan standart arifmetik amallarga mos kasr sonlar ham mavjud. Biz bu tiplarni quyidagicha belgilaymiz:
INTEGER, CARDINAL, REAL, BOOLEAN, CHAR
Bu yerda INTEGER tipi butun sonlarning qandaydir to‘plam osti bo‘lib, uning o‘lchami mashinaga mos o‘zgarib turadi. Agar butun sonlarni mashinada tasvirlash uchun n ta razryad ishlatilsin, va bu yerda qo‘shimcha kod ishlatilsa, u holda mumkin bo‘lgan son shartni qanoatlantiradi. Ushbu oraliqda mazkur tipli ma’lumotlar ustida barcha amallar arifmetikaning oddiy qoidalarga ko‘ra bajariladi. Arifmetik amallar bajarilishi natijasida bu oraliqdan tashqariga chiqilsa, hisoblash to‘xtatiladi va bu hodisa to‘lib (chiqib) ketish deb ataladi. To‘rtta arifmetik amallar - qo‘shish (+), ayirish (-), ko‘paytirish (*) va bo‘lish (/, div) standart arifmetik amallar deyiladi.
Biz bu yerda butun Eyler arifmetikasi va modulliy arifmetikani farqini ko‘rsatib o‘tamiz. Birinchi tur bo‘lish qiyshiq to‘g‘ri chiziq (/) bilan belgilanadi, qoldiq esa – Rem bilan belgilanadi. Faraz qilaylik q = m/n bo‘linmaning qoldig‘i r = m/n bo‘lsin. U holda