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

Massiv - bu ma’lumotlarni ketma-ket taqdim etishdan foydalanib amalga oshiriladigan qat’iy belgilangan o’lchamdagi ma’lumotlarning chiziqli tuzilmasidir. Ma’lumotlar tuzilmasi sifatida massiv tushunchasi AAT tomonidan qayta ishlanadigan ma’lumotlar majmuasini aniqlovchi axborot massivi tushunchasi bilan aynan bir xil emas. Buning sababi quyidagicha.

Massivning har bir elementi bir yoki bir necha indekslar bilan identifikatsiya qilinadi. Indeks - bu qiymati tegishli elementning massivdagi joyini aniqlaydigan butun sondir va u ushbu elementdan erkin foydalanish uchun ishlatiladi. Massivning alohida elementlari o’zgarishi mumkin (ya’ni yozuvlar modifikatsiya qilinishi mumkin), lekin massiv elementlarining umumiy soni hamisha o’zgarmas bo’lib qoladi, demak, massivlar uchun qo’shish va o’chirish operatsiyalari mavjud emas.

Massivning har bir elementini identifikatsiya qiladigan indekslar soniga qarab bir o’lchamli va ko’p o’lchamli massivlar farqlanadi.

Bir o’lchamli massiv vektor deb ataladi. A = {A(1) A(2)... A(I)... A(N)} vektori - bu xotiraning yonma-yon uyalarida joylashgan elementlar (yozuvlar)ning ketma-ketligidir. Vektorning birlik indeksi har bir elementning ketma-ketlikdagi joyini ko’rsatadi. Vektorning birinchi elementi uchun ajratilgan birinchi baytning manzili vektor bazasining manzili deyiladi. Vektor umuman olganda bazaning manzili, elementlar o’lchami va ularning soni yoki elementlar o’lchami va indeks o’zgarishining diapazoni bilan aniqlanadi. Agar L0 - vektorni saqlash uchun ajratilgan xotira blokidagi birinchi baytning manzili, s - har bir elementni saqlash uchun ajratilgan baytlar soni bo’lsa, ixtiyoriy i-elementning manzili quyidagicha bo’ladi:

loc (Ai) = L0 + c (i - 1),

(1os inglizcha 1osation - joylashgan joyini aniqlash).

L0 bazasining manzili dasturni translyatsiya qilish jarayonida translyator tomonidan aniqlanadi. Shu vaqtning o’zida vektor uchun deklaratsiyada aniqlangan uning o’lchamiga muvofiq xotira zahiraga olinadi. Translyatsiya jarayonida xotira manzillarning ketma-ket oshib borishi tartibida taqsimlanadi.

Manzillarning kamayib borishi tarafiga xotiraning taqsimlanishi ham bo’lishi mumkin. Ushbu vaziyatda s (i - 1) qiymat L0 dan ayirib tashlanadi

Vektorni xotirada taqdim etish ular dasturlash tilida qanday

ta’riflanganligiga bog’liq emas. Istalgan ta’rifda ushbu taqdim etish bir xil bo’ladi. Ikki o’lchamli massiv matritsa deb ataladi. Matritsaning har bir elementi ikki indeks bilan aniqlangan. Umumiy holatda matritsa ixtiyoriy o’lchamga ega bo’lishi, ya’ni ko’p o’lchamli bo’lishi mumkin. Ko’p o’lchamli massiv bir o’lchamli ekvivalent massiv bilan taqdim etilgan bo’lishi mumkin. Masalan, matritsaga elementlari o’z navbatida vektor hisoblanadigan vektor sifatida qarash mumkin. Bunda matritsa kompyuter xotiradsida «qatorlar qatori» va «ustunlar qatori» sifatida ko’rilishi va saqlanishi mumkin. Birinchi holatda

A(1,1) A(1,2) A(1,3) A(2,1) A(2,2) A(2,3)

A(3,1) A(3,2) A(3,3)

matritsasi quyidagi vektor ko’rinishida taqdim etiladi:

A(1,1) A(1,2) A(1,3) A(2,1) A(2,2) A(2,3) A(3,1) A(3,2) A(3,3).

Matritsa elementlarini shunday ketma-ketlikda saqlash qatorlar bo’yicha joylashtirish deyiladi.

Boshqa holatda, matritsa «ustunlar qatori» sifatida ko’rilsa, uning elementlari xotirada ustunlar bo’yicha quyidagi tartibda joylashadi:

A(1,1) A(2,1) A(3,1) A(1,2) A(2,2) A(3,2) A(1,3) A(2,3) A(3,3).

Qatorlar bo’yicha joylashtirilganda A(ij) matritsa elementining manzili quyidagi ifoda bilan aniqlanadi:

loc (Ai,j) = L₀ + s(i - 1) + s(j - 1), bunda m - ustunlar soni.

Umumiy holatda massiv ixtiyoriy o’lchamga ega bo’lishi mumkin. n- o’lchamli massiv uchun o’lchamlar soni, shuningdek indekslar o’zgarishi diapazonining yuqori va pastki chegaralari ko’rsatiladi.

Bir qator vaziyatlarda bir massivda turli tipdagi ma’lumotlarni saqlashga to’g’ri kelib qoladi. Bunday massiv har xil turdagi massiv deyiladi. Masalan, talabaning shaxsiy kartochkasini saqlashda familiya, yosh, manzil, o’rtacha ball va boshqalar massiv elementlari hisoblanadi. Ushbu bir talaba to’g’risidagi ma’lumotlar xotirada qat’iy belgilangan uzunlikdagi bir o’lchamli turli turdagi massiv sifatida saqlanishi mumkin. shunday massiv elementlaridan erkin foydalanish belgi shaklida taqdim qilingan indeks bo’yicha amalga oshirilishi mumkin. Masalan, massivning birinchi elementidan erkin foydalanish uchun

NAME indeksi bo’yicha, ikkinchi elementga esa AGE indeksini ishlatish mumkin va h.k.

Bir o’lchamli turli turdagi massivlardan ko’p o’lchamli turli turdagi massivlar, masalan, guruhning barcha talabalarini ta’riflovchi massivni tashkil etilishi mumkin.

Avtomatlashtirilgan axborot tizimlari haqiqiy olamdagi obyektlar to’g’risidagi axborotni saqlaydi va ishlov beradi. Katta obyektlarni, ularning tabiiy murakkabligini hisobga olgan holda, kompozitsiya tamoyillaridan foydalanib alohida agregat va bo’g’inlarga bo’lish qabul qilingan. Muayyan obyekt yoki uning bir qismini ta’riflovchi axborotning muayyan majmuini mantiqiy yozuv yoki oddiygina qilib yozuv deb ataladi. Muayyan sinfga oid ko’plab obyektlarni ta’riflovchi yozuvlar to’plamini axborot massivlari deb ataladi.

Haqiqiy olamda obyektlar va ularning alohida agregatlari o’rtasida turli darajadagi murakkablikka ega bo’lgan muayyan munosabatlar va o’zaro aloqalar mavjud bo’ladi. Axborotga ishlov berish va saqlash tizimlarini ishlab chiqish jarayonida bu munosabatlar aniqlanadi va yozuvlar hamda axborot massivlarini tuzilmalash yo’li bilan aks ettiriladi. Ma’lumotlar o’rtasidagi aloqa va munosabatlarni aniqlab berishni ta’minlaydigan axborot massivlarini tashkiliy shakli ma’lumotlar tuzilmasi deb ataladi. Ma’lumotlarga kompyuter da ishlov berish jarayonida ularning axborot to’liqligi yo’qolmasligi, haqiqiy olamda obyektlar o’rtasidagi mavjud munosabatlarning ma’nosi buzilmasligi uchun tuzilmalarni doimiy kuzatib borish zarur, ya’ni ishlov berish jarayonidagi har qanday operatsiyalar ma’lumotlar tuzilmasini buzmasligi kerak. Tuzilmada ta’riflanayotgan obyektning xususiyatlari aks ettirilgan, shuning uchun tuzilmaning buzilishi uning xususiyatlari yo’qolishiga va oqibatda obyektning nomuvofiq ta’riflanishiga olib keladi. Mantiqiy darajada obyektlar va ularning tavsiflari o’rtasidagi mavjud haqiqiy munosabatlarni aks ettiruvchi ma’lumotlarning mantiqiy tuzilmalari bilan ishlanadi, bu tavsiflarma’lumotlar tizimdan foydalanuvchiga qanday shaklda taqdim etilishini ko’rsatib beradi.

Ma’lumotlarning mantiqiy tuzilmalarini ishlab chiqishda tizimdan foydalanuvchilarning axborotga ehtiyoji va bu axborot hal qilishi mo’ljallanayotgan vazifalar xarakteri ham hisobga olinadi. Bu darajada axborot birligi mantiqiy yozuv hisoblanadi, tegishli mantiqiy yozuv bilan tavsiflanadigan obyekt muayyan belgilari -xususiyatlari bilan xarakterlanadi, ular yozuv atributlari shaklida ifodalanadi. Mantiqiy darajada tizimning ishlab chiquvchisi ta’riflanadigan obyektlar sinfini to’liq xarakterlovchi belgilar ro’yxatini belgilaydi. Belgilarning majmui va ularning o’zaro aloqasi mantiqiy yozuvning ichki tuzilmasini belgilaydi.

Ma’lumotlarning mantiqiy tuzilmasi ma’lumotlarga ishlov berilayotgan obyektlarni to’liq ta’riflab berishi, obyektlar va ularning tavsiflari o’rtasidagi haqiqiy munosabatlarni mos ravishda aks ettirishi, tizimdan foydalanuvchilarning axborotga ehtiyojini qondirishni va ilovalarning topshiriqlarini hal qilishni ta’minlashi zarur. Obyektning qaysi hususiyatlari yozuv atributlarida aks ettirilishi zarurligini tizim ishlab chiquvchisi yetarlilik tamoyillaridan kelib chiqqan holda hal qiladi.

Ma’lumotlarni taqdim etishning mantiqiy darajasida tizimning texnik va matematik ta’minoti (kompyuter turi, XQ turi, dasturlashtirish tili, operatsion tizim) hisobga olinmaydi.

Saqlash darajasida saqlanadigan tuzilmalar - kompyuterlar xotirasidagi ma’lumotlarning mantiqiy tuzilmalari bilan operatsiyalar bajariladi. Saqlash tuzilmasi to’lalig’icha ma’lumotlarning mantiqiy tuzilmasini aks ettirishi va uni AAT (avtomatlashtirilgan axborot tizimlari) ishlash jarayonida qo’llab turishi zarur. Bu darajada ham axborot birligi mantiqiy yozuv hisoblanadi. Dastur hech qanday buzilishga yo’l qo’ymay mantiqiy darajani saqlash darajasiga o’tkazishi kerak.