Toshkent davlat iqtisodiyot universiteti raqamli iqtisodiyot fakulteti

Abstrakt ma'lumotlar turlari
Ma'lumotlarning aniq ko'rinishini belgilamaydigan har qanday ma'lumotlar turi mavhum ma'lumotlar turi hisoblanadi. Buning o'rniga, uni tavsiflash uchun ma'lumotlar turining operatsiyalariga asoslangan rasmiy spetsifikatsiya qo'llaniladi. Spetsifikatsiyaning har qanday amalga oshirilishi belgilangan qoidalarga javob berishi kerak. Mavhum ma'lumotlar turlari rasmiy semantika va dasturlarni tekshirishda, kamroq qat'iy ravishda dizaynda qo'llaniladi.
Tekshiruvdan tashqari, spetsifikatsiya darhol dasturga aylanishi mumkin. Masalan, OBJ dasturlash tillari oilasi spetsifikatsiya va ularni ishga tushirish uchun qayta yozish uchun tenglamalardan foydalangan holda ushbu variantga asoslanadi. Algebraik spetsifikatsiya taxminan 1980-yillarda CSda tadqiqotning muhim mavzusi bo'lgan va o'sha paytda mavhum ma'lumotlar turlarining deyarli sinonimi edi. U universal algebrada matematik asosga ega. Spetsifikatsiya tilini faqat tenglamalarga emas, balki boshqa formulalarga ruxsat berish orqali yanada ifodali qilish mumkin.Ikkilik daraxt, roʻyxat, sumka va toʻplam maʼlumotlar turlarining Boom ierarxiyasi odatiy misoldir. Ushbu ma'lumotlar turlarining barchasi uchta operatsiya bilan e'lon qilinishi mumkin: bo'sh konteynerni tuzadigan null, bitta elementdan konteyner quradigan va bitta turdagi ikkita konteynerni birlashtirgan qo'shimcha. To'rt turdagi ma'lumotlarning to'liq spetsifikatsiyasi ushbu operatsiyalarga quyidagi qoidalarni ketma-ket qo'shish orqali berilishi mumkin:
- null daraxt uchun chap va o'ng neytral hisoblanadi: append(null,A) = A, append(A,null) = A.
- ro'yxatlar ilovaning assotsiativ ekanligini qo'shadi: append(append(A,B),C) = append(A,append(B,C)).
- sumkalar kommutativlikni qo'shadi: append(B,A) = append(A,B).
- nihoyat, to'plamlar ham idempotentdir: append(A,A) = A.
Ma'lumotlarga kirish uchta operatsiya bo'yicha naqshlarni moslashtirish orqali aniqlanishi mumkin, masalan. Ushbu konteynerlar uchun a'zo funktsiyasi:
- a'zo(X,bit(Y)) = ek(X,Y)
- a'zo (X, null) = noto'g'ri
- a'zo (X, qo'shimcha (A, B)) = yoki (a'zo (X, A), a'zo (X, B))
Funktsiyaning ma'lumotlar turi uchun tegishli qoidalarga muvofiq o'zgarmasligini ta'minlash uchun ehtiyot bo'lish kerak.
Boshqa turlar
Turlar yuqorida bayon qilingan asosiy turlarga asoslanishi yoki ulardan kelib chiqishi mumkin. Ayrim tillarda, masalan, C, funksiyalar t turidan kelib chiqqan turga ega merosxo'rning qaytish qiymati.
Ko'rsatkichlar va havolalar
Asosiy kompozit bo'lmagan, hosila turi - bu ko'rsatkich, ma'lumotlar turi, uning qiymati to'g'ridan-to'g'ri kompyuter xotirasining boshqa joyida saqlanadigan boshqa qiymatga tegishli (yoki "ishora qiladi") manzili yordamida. Bu murojaatning ibtidoiy turi. (Kundalik nuqtai nazardan, kitobdagi sahifa raqami boshqasiga tegishli bo'lgan ma'lumotlar qismi deb hisoblanishi mumkin). Ko'rsatkichlar ko'pincha butun songa o'xshash formatda saqlanadi; ammo qiymati hech qachon haqiqiy xotira manzili bo'lmagan ko'rsatkichni yo'qotish yoki "izlash"ga urinish dasturning ishdan chiqishiga olib keladi. Ushbu potentsial muammoni hal qilish uchun ko'rsatgichlar, hatto asosiy vakillik bir xil bo'lsa ham, ular ko'rsatadigan ma'lumotlar turining alohida turi hisoblanadi.