DOIMIY MA’LUMOTLAR SUTRUKTURASI


DOIMIY MA’LUMOTLAR SUTRUKTURASI Mundarija: 1KIRISH. 2ASOSIY QISM. 1 . Maʼlumotlar tuzilmasi 1.1. Ma’lumot elementlari 2.Ma’lumot turlari. 2.1Fundamental ma’lumot turlari 2.2Murakkab ma’lumot turlari 3.Ma’lumot strukturalari 3.1Statik ma’lumot strukturalari 3.2Dinamik ma’lumot strukturalari 4. Ma'lumotlar tuzilmalarini doimiyga o'tkazish usullari 3Xulosa. 1. Doimiy ma’lumotlar tuzilmasi. 4Foydalanilgan adabiyotlat ro’yhati.
Kirish Ushbu inshoda biz Doimiy ma'lumotlar tuzilmalari dunyosini batafsil ko'rib chiqamiz va uni amalga oshirish asoslarini hamda ularni amalda qayerdan topishimiz mumkinligini ko'rib chiqamiz. Ushbu insho mavzuga to'liq kirish vazifasini o'taydi va kelgusi insholarda biz har bir ma'lumotlar strukturasining o'ziga xos xususiyatlariga chuqurroq kirib boramiz. Ushbu insho 1986 yilda nashr etilgan Jeyms R. Driskoll, Nil Sarnak, Daniel D. Sleator va Robert E. Tarjan tomonidan "Ma'lumotlar tuzilmalarini barqaror qilish" nomli mashhur maqolaga asoslanadi. Doimiy ma'lumotlar tuzilmalari o'zlarining oldingi versiyalarini saqlab qoladi, bu bizga har qanday tarixiy versiyani qayta ko'rib chiqish va tekshirish imkonini beradi. Oldingi versiyalarda ruxsat etilgan operatsiyalarga qarab, qat'iylik uch toifaga bo'linadi Qisman doimiy ma'lumotlar tuzilmalari barcha tarixiy versiyalarga kirish imkonini beradi, lekin faqat eng yangisiga o'zgartirish imkonini beradi. Bu odatda ma'lumotlar strukturasining tarixiy versiyalarini o'zgarmas qiladi (faqat o'qish uchun). To'liq doimiy ma'lumotlar tuzilmalari barcha tarixiy versiyalarga kirish va o'zgartirish imkonini beradi. U hech qanday o'zgarishlarni cheklamaydi. Bu shuni anglatadiki, biz odatda har qanday tarixiy versiyani qayta ko'rib chiqishimiz va uni o'zgartirishimiz va shu bilan yangi filialni ajratishimiz mumkin. Confluently Persistent Data Structures tarixiy versiyalarga o zgartirishlarʻ kiritishga imkon beradi, shu bilan birga ularni oldingi ikki versiyadan yangi versiya yaratish uchun mavjudlari bilan birlashtirishga imkon beradi. Doimiy ma'lumotlar tuzilmalari o'zlarining ilovalarini kompyuter fanining butun spektrini qamrab oladi, lekin ular bilan cheklanmagan - Funktsional dasturlash tillari, hisoblash geometriyasi, matn muharrirlari va boshqalar.
Funktsional dasturlash tillari Funktsional dasturlash tillari doimiy ma'lumotlar tuzilmalarini o'z ichiga olish uchun ideal nomzodlardir, chunki ular asosiy tuzilmalarning o'zgarishini taqiqlaydi, ba'zilari esa, o'zgarmaydi. Bu tillar funktsiyalar doirasidagi shtatlarni aylanib o'tadi va ular mavjudni yangilamaydi, balki yangi holatni qaytaradi. Haskell, Clojure, Elm, Javascript, Scala kabi dasturlash tillarida ro yxatlar,ʻ xaritalar, to plamlar va daraxtlar kabi ma lumotlar tuzilmalarining doimiy tatbiq ʻ ʼ etilishi mavjud. Hisoblash geometriyasi Hisoblash geometriyasining asosiy muammolaridan biri bu so'rov nuqtasi joylashgan hududni aniqlash bilan shug'ullanadigan nuqta joylashuvi muammosi. Masala bayonining soddaroq varianti nuqta berilgan ko‘pburchak ichida yoki tashqarisida joylashganligini aniqlashdir. Nuqtaning joylashuvi muammosi bayonotining yechimini aniqlash uchun mashhur yechim doimiy qizil-qora daraxtlardan foydalanadi. Matn va fayllarni tahrirlash Har qanday matn yoki faylni tahrirlash vositasi tomonidan talab qilinadigan eng keng tarqalgan operatsiya bu Bekor qilish va Qayta tiklash bo'lib, doimiy ma'lumotlar tuzilmasi orqali barcha tarixiy versiyalarni saqlab qolish ushbu tez-tez bajariladigan operatsiyalarni juda samarali va oson qiladi. Qisman qat'iylikni amalga oshirish Qisman qat'iylikni amalga oshirishda yordam beradigan bir nechta umumiy usullar mavjud. Qayta takrorlash uchun, qisman qat'iylik barcha tarixiy versiyalarga kirish imkonini beradi, lekin ma'lumotlarning yangilangan nusxasini yaratish uchun faqat eng yangisiga o'zgartirish imkonini beradi.
Doimiy ma'lumotlar strukturasi - bu o'zgartirilganda o'zining oldingi versiyasini saqlaydigan ma'lumotlar tuzilmasi. Bunday ma'lumotlar tuzilmalari uchun yangilash operatsiyalari strukturani joyida yangilamaydi, lekin har doim yangi yangilangan tuzilmani beradi. Har bir yangilangan versiyaga kirish mumkin bo'lsa, ma'lumotlar tuzilmasi doimiy hisoblanadi. Agar biz faqat oxirgi versiyani yangilashimiz mumkin bo'lsa, ma'lumotlar strukturasi qisman doimiy hisoblanadi, to'liq doimiy ma'lumotlar tuzilmasida esa uning har bir versiyasini o'zgartirishimiz mumkin. Doimiy ma'lumotlar tuzilmalariga misollar: • Bog'langan ro'yxatlar Bog'langan ro'yxatni ko'rib chiqing Agar biz bog'langan ro'yxatning boshiga yangi tugun qo'shmoqchi bo'lsak, biz yangi tugun yaratishimiz va uni bog'langan ro'yxatning joriy boshiga yo'naltirishimiz mumkin. K qo'shish amallaridan keyin qisman doimiy bog'langan ro'yxat uchun bog'langan ro'yxat bo'ladi • Ikkilik daraxtlar Ikkilik daraxtini ko'rib chiqing: Doimiy ikkilik daraxtga yangi qiymat kiritish yangi daraxtni yaratadi, unda ildizdan yangi tugungacha bo'lgan yo'lda tugunlar yana yaratiladi va qolgan tugunlar asl va yangilangan versiyalar o'rtasida taqsimlanadi. • Doimiy segmentli daraxtlar 1 dan N gacha etiketlangan N tugunli daraxtni ko'rib chiqing. Biz har bir tugun uchun segment daraxtlarini yaratishni talab qiladigan so'rovlarni bajarishimiz kerak. N ta shunday segment daraxtini qurish uchun bizga O(n^2) vaqt va xotira kerak bo'ladi. Faraz qilaylik, A tugun uchun segment daraxti yaratilgan. A ning har qanday V bolasi uchun B segment daraxti O(log(N))