logo
Русский O'zbekcha
  1. Главная страница
  2. Дипломные работы
  3. Общий
  4. DOIMIY MA’LUMOTLAR SUTRUKTURASI

DOIMIY MA’LUMOTLAR SUTRUKTURASI

Загружено в:

12.08.2023

Скачано:

1

Размер:

550.0 KB
Условия скачивания
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)) tugunlaridan tashqari A ning segment daraxtiga deyarli o'xshash bo'ladi. Biz A segment daraxtining qolgan tugunlarini qayta ishlatishimiz va ushbu O(log N) tugunlari uchun xotirani ajratishimiz mumkin. Daraxtning har bir tuguniga O(log(N)) tugunlari uchun xotira ajratamiz. Xotira va vaqt murakkabligi O(N*log(N)) ga kamayadi. Bolalar uchun yangi daraxtlar ota-onalarning segment daraxtlaridan O (log (N)) tugunlari bilan farqlanadi. Ushbu xususiyatdan foydalanib, biz barcha tugunlar uchun segment daraxtlarini qurish uchun zarur bo'lgan vaqtni O(N*log(N)) ga qisqartirishimiz mumkin. O'zgartirilganda har doim o'zining oldingi versiyasini saqlaydigan ma'lumotlar strukturasi Hisoblashda doimiy ma'lumotlar strukturasi bo'lib, u o'zgarganda har doim o'zining oldingi versiyasini saqlab qoladi. Bunday ma'lumotlar tuzilmalari tabiatan o'zgarmasdir, chunki ularning operatsiyalari (vizual) tuzilmani joyida yangilamaydi, balki har doim yangilangan yangi tuzilmani yaratadi. Bu atama 1986 yilda Driscoll, Sarnak, Sleator va Tarjans tomonidan yozilgan maqolada kiritilgan. Agar barcha versiyalar mavjud bo'lsa, ma'lumotlar strukturasi qisman doimiy bo'ladi, lekin faqat eng yangi versiyasini o'zgartirish mumkin. Har bir versiyaga kirish va o'zgartirish mumkin bo'lsa, ma'lumotlar strukturasi to'liq barqaror bo'ladi. Agar oldingi ikkita versiyadan yangi versiyani yaratishi mumkin bo'lgan birlashtirish yoki birlashtirish operatsiyasi mavjud bo'lsa, ma'lumotlar strukturasi doimiy ravishda doimiy deb aytiladi. Doimiy bo'lmagan tuzilmalar efemer deyiladi. Ushbu turdagi ma'lumotlar tuzilmalari, ayniqsa, mantiqiy va funktsional dasturlashda keng tarqalgan, chunki bu paradigmalardagi tillar o'zgaruvchan ma'lumotlardan foydalanishni oldini oladi (yoki butunlay taqiqlaydi). ASOSIY QISM. Ma lumotlar tuzilmasiʼ Informatika sohasida ma lumotlar tuzilmasi ʼ — samarali kirish va o zgartirishga ʻ imkon beradigan ma lumotlarni tashkil qilish, managment va saqlash formati. ʼ [1] [2] [3] Aniqrog i, ma lumotlar tuzilmasi ma lumotlar qiymatlari, ular orasidagi ʻ ʼ ʼ munosabatlar va ma lumotlarga qo llanilishi mumkin bo lgan funksiyalar yoki ʼ ʻ ʻ operatsiyalar to plami hisoblanadi. ʻ [4] Kompyuter xotirasida saqlanadigan ma'lumotlar nol va birliklar (bitlar) yig'indisidir. Bitlar ketma-ketlikda birlashtiriladi: baytlar, so'zlar va boshqalar. Operativ xotiraning bir bayt yoki so'zni sig'dira oladigan har bir qismiga tartib raqami (manzil) beriladi. Ma'lumotlarning ma'nosi nima, ular qanday belgilar bilan ifodalangan - alifbo yoki raqamli, u yoki bu raqam nimani anglatadi - bularning barchasi ishlov berish dasturi bilan belgilanadi. Amaliy muammolarni hal qilish uchun zarur bo'lgan barcha ma'lumotlar bir necha xil turlarga va kontseptsiyaga bo'linadi turi nafaqat ma'lumotlarning manzillar maydonida ko'rinishi bilan, balki bilan ham aloqa qiladi ularni qayta ishlash usuli . Har qanday ma'lumotlarni ikki turdan biriga bo'lish mumkin: asosiy (oddiy), shakli kompyuter arxitekturasi tomonidan belgilanadigan yoki foydalanuvchi tomonidan muayyan muammolarni hal qilish uchun ishlab chiqilgan murakkab. Oddiy ma'lumotlar turlari - bu belgilar, raqamlar va boshqalar. elementlar, ularni keyingi maydalash mantiqiy emas. Elementar ma'lumotlardan ma'lumotlar tuzilmalari (murakkab tiplar) tuziladi. Ma’lumotlar tuzilmalari o’zi nima? Barcha dastur yoki dasturiy mahsulotning asosida ikkita birlik yotadi: ma’lumotlar va ular ustida qandaydir amallar bajaradigan algoritmlar. Algoritmlar ma’lumotlarni biz yoki dastur uchun foydali bo’lgan axborot ko’rinishiga keltirib beradi. Algoritmlar shu ma’lumotlar ustida amallarni (o’qish, yozish, yangilash, o’chirish) samarali va tez bajara olishi uchun biz shu ma’lumotlarni ma’lum bir strukturaga solgan holda saqlashimiz kerak bo’ladi. Demak shunday qilib, Ma’lumotlar tuzilmasi — bu ma’lumotlarni samarali o’qish va o’zgartirish imkonini beruvchi, ma’lumotlarni saqlash va boshqarishning bir formatga solingan shaklidir. Soddaroq qilib aytganda, ma’lumotlar tuzilmasi — bu ma’lumotlarning ma’lum bir strukturaga solingan, ular o’rtasida ma’lum bir bog’lanishlar yaratilgan va ular ustida ma’lum amallar bajaruvchi funksiyalardan tashkil topgan guruh. Eng sodda ma’lumotlar tuzilmasiga misol qilib massiv (array) ni ko’rsatishimiz mumkin. Ma’lumot turlari. C++ da ma’lumot turlari ikki kategoriyaga bo’linadi: fundamental va murakkab ma’lumot turlari. Quyidagi ma’lumot turlari fundamental turlar hisoblanadi: void . Bu tur tugallanmaydigan (ya’ni, bu tur bilan obyekt, massiv va adres (reference, ссылка ) lar e’lon qilinmaydi va aniqlanmaydi) ma’lumot turi hisoblanib hech qanday qiymat qabul qilmaydi. Lekin bu tur bilan ko’rsatgichlar e’lon qilinishi va aniqlanishi mumkin. Bundan tashqari bu tur qiymat hosil qilmaydigan funksiyalarni e’lon qilish va aniqlashda foydalanilishi mumkin. Masalan, quyidagilar to’g’ri hisoblanadi: void * Ptr ; // istalgan turdagi obyekt uchun ko’rsatgich void DoSomething () { } // funksiya std::nullptr_t ( C++ 11 dan boshlab ). Bu tur nol ko’rsatgich nullptr ning turi hisoblanadi, ya’ni nullptr std::nullptr_t ma’lumot turiga ega. 0 yoki nullptr qiymatlarini qabul qiladi. Hajmi sizeof ( void *) ga teng. Misol: int * IntPtr = nullptr ; // IntPtr ning qiymati 0 bool . Mantiqiy ma’lumotlar, o’zgaruvchilar turi. Faqat true va false qiymatlarini qabul qiladi. Hajmi kompillyatorga bo’g’liq, lekin kamida 1 bayt. Misol: bool BoolningHajmiBirgaTeng = sizeof ( bool ) == 1 ; char , signed char , unsigned char . Bular belgilar turlari bo’lib, uchchalasi alohida turlar hisoblanadi. Uchchalasi bir xil hajmga ega va 1 baytga teng. char asosan belgilar to’plami, satrlar hosil qilishda foydalaniladi. U kompillyatorga bog’liq ravishda signed char yoki unsigned char bilan aynan bir xil bo’ladi. Shuning uchun -128 dan 127 gacha yoki 0 dan 255 gacha bo’lgan qiymatlarni qabul qiladi. signed char kichik hajmli, ishorali butun sonlar talab qilinganda foydalanilishi mumkin va -128 dan 127 gacha bo’lgan qiymatlarni qabul qiladi. unsigned char kichik hajmli, ishorasiz butun sonlar talab qilinganda foydalanilishi mumkin va 0 dan 255 gacha bo’lgan qiymatlarni qabul qiladi. Misol: char Harf = ‘A’ ; char DT [] = “C ++ ” ; const signed char N = - 90 ; unsigned char IP [ 4 ] = { 192, 168, 1, 1 } ; char16_t ( C++ 11 dan boshlab ). Unicode formatidagi belgilar uchun ishlatiladi. Qiymatlari uchun UTF-16 belgilar to’plami foydalaniladi. Hajmi kompillyatorga bog’liq, lekin kamida 2 bayt. Misol: char16_t Harf = u‘A’ ; char16_t DT [] = u“C ++ ” ; char32_t ( C++ 11 dan boshlab ). Unicode formatidagi belgilar uchun ishlatiladi va UTF-32 belgilar to’plami foydalaniladi. Hajmi kompillyatorga bog’liq, lekin kamida 4 bayt. Misol: char32_t Harf = U‘A’ ; char32_t DT [] = U“C ++ ” ; wchar_t . Unicode formatidagi belgilar uchun ishlatiladi va UTF-16 yoki UTF-32 belgilar to’plami foydalaniladi. Hajmi kompillyatorga, ya’ni foydalanilgan belgilar to’plamiga bo’g’liq. Misol: wchar_t Harf = L‘A’ ; wchar_t DT [] = L“C ++ ” ; int . Butun sonlarning asosiy ( базовый ) turi hisoblanadi. Uning hajmi kamida 2 baytga teng. Lekin 32/64 bit arxitekturali tizimlarda uning hajmi kamida 4 bayt. Bu tur o’zgartirgich ( модификатор ) lar bilan birga ishlatilishi mumkin. Quyidagi o’zgartirgichlar mavjud: signed, unsigned (ishorasini belgilaydi) va short, long, long long (hajmini belgilaydi). Demak,  short , short int , signed short , signed short int lar aynan bir xil bo’lib, ishorali butun sonlar turi hisoblanadi. Hajmi kamida 2 bayt va -32768 dan 32767 gacha bo’lgan sonlarni qabul qiladi.  unsigned short , unsigned short int lar aynan bir xil bo’lib, ishorasiz butun sonlar turi hisoblanadi. Hajmi kamida 2 bayt va 0 dan 65535 gacha bo’lgan sonlarni qabul qiladi.  signed , signed int , int lar aynan bir xil bo’lib, ishorali butun sonlar turi hisoblanadi. Hajmi kamida 4 bayt va -2147483648 dan 2147483647 gacha bo’lgan sonlarni qabul qiladi. Ba’zi 16 bitli tizimlarda uning hajmi 2 bayt ( short variantidek).  unsigned , unsigned int lar aynan bir xil bo’lib, ishorasiz butun sonlar turi hisoblanadi. Hajmi kamida 4 bayt va 0 dan 4294967295 gacha bo’lgan sonlarni qabul qiladi. Ba’zi 16 bitli tizimlarda uning hajmi 2 bayt ( short variantidek).  long , long int , signed long , signed long int lar aynan bir xil bo’lib, ishorali butun sonlar turi hisoblanadi. Hajmi kamida 4 bayt va -2147483648 dan 2147483647 gacha bo’lgan sonlarni qabul qiladi. Ba’zi 64 bitli tizimlarda uning hajmi kamida 8 bayt va -9223372036854775808 dan 9223372036854775807 gacha bo’lgan sonlarni qabul qiladi.  unsigned long , unsigned long int lar aynan bir xil bo’lib, ishorasiz butun sonlar turi hisoblanadi. Hajmi kamida 4 bayt va 0 dan 4294967295 gacha bo’lgan sonlarni qabul qiladi. Ba’zi 64 bitli tizimlarda buning hajmi kamida 8 bayt va 0 dan 18446744073709551615 gacha bo’lgan sonlarni qabul qiladi.  long long , long long int , signed long long , signed long long int lar aynan bir xil bo’lib, ishorali butun sonlar turi hisoblanadi. Hajmi kamida 8 bayt va - 9223372036854775808 dan 9223372036854775807 gacha bo’lgan sonlarni qabul qiladi.  unsigned long long , unsigned long long int lar aynan bir xil bo’lib, ishorasiz butun sonlar turi hisoblanadi. Hajmi kamida 8 bayt va 0 dan 18446744073709551615 gacha bo’lgan sonlarni qabul qiladi. float . Yagona aniqlikga ega bo’lgan haqiqiy sonlar turi hisoblanadi. Bunday aniqlikga ega sonlar odatda 4 bayt hajmga ega va 1.17E-38 dan 3.4E38 gacha bo’lgan sonlarni qabul qiladi. double . float ga nisbatan ikki karra yuqori aniqlikga ega bo’lgan haqiqiy sonlar turi va odatda 8 bayt hajmga ega. 2.23E-308 dan 1.79E308 gacha bo’lgan sonlarni qabul qiladi. long double . Kengaytirilgan aniqlikga ega bo’lgan haqiqiy sonlar turi va odatda 10 yoki 16 bayt (kompillyatorga bog’liq) hajmga ega. 3.36E-4932 dan 1.18E4932 gacha bo’lgan sonlarni qabul qiladi. Quyidagilar murakkab turlar hisoblanadi: Massiv . Agar struktura bir hil kattalikdagi tiplardan tuzilgan bo'lsa, uning nomi massiv (array) deyiladi. Massivlar dasturlashda eng ko'p qo'laniladigan ma'lumot tiplaridir. Bundan tashqari strukturalar bir necha farqli tipdagi o'zgaruvchilardan tashkil topgan bo'lishi mumkin. Buni biz klas (Pascalda record) deymiz. Masalan bunday strukturamiz ichida odam ismi va yoshi bo'lishi mumkin. Bu bo'limda biz massivlar bilan yaqindan tanishib o'tamiz. Bu bo'limdagi massivlarimiz C uslubidagi, pointerlarga (ko'rsatkichlarga) asoslan strukturalardir. Massivlarning boshqa ko'rinishlarini keyingi qismlarda o'tamiz. Massivlar hotirada ketma-ket joylashgan, bir tipdagi o'zgaruvchilar guruhidir. Dasturda ikki asosiy tur ma'lumot strukturalari mavjuddir. Birinchisi statik, ikkinchisi dinamikdir. Statik deganimizda hotirada egallagan joyi o'zgarmas, dastur boshida beriladigan strukturalarni nazarda tutamiz. Dinamik ma'lumot tiplari dastur davomida o'z hajmini, egallagan hotirasini o'zgartirishi mumkin. Alohida bir o'zgaruvchini ko'rsatish uchun massiv nomi va kerakli o'zgaruvchi indeksini yozamiz. C++ dagi massivlardagi elementlar indeksi har doim noldan boshlanadi. Massiv bir o`lchamli deyiladi, agar uning elementiga bir indeks orqali murojaat qilish mumkin bo`lsa. Bir o`lchamli massivni e`lon qilish quyidagicha bo`ladi: 1) float a[5]; 2) int m[6]; 3) bool b[10]; 1) a elementlari haqiqiy sonlardan iborat bo`lgan, 5 ta elementdan tashkil topgan massiv. Indekslari esa 0 dan 4 gacha bo`lgan sonlar float a[5]; Massiv a[0] a[1] a[2] a[3] a[4] elementilari qiymati 4 -7 15 5.5 3 2) m elementlari butun sonlardan iborat bo`lgan, 6 ta elementdan tashkil topgan massiv. Indekslari esa 0 dan 5 gacha bo`lgan sonlar. int m[6]; Massiv m[0] m[1] m[2] m[3] mas2[4] mas2[5] elementilari qiymati 2 -17 6 7 13 -3 3) b elementlari mantiqiy qiymatlardan (true, false ) iborat bo`lgan 10 ta elementdan tashkil topgan massiv. Indekslari esa 0 dan 9 gacha bo`lgan sonlar. Massiv elementlariga murojaat qilish oddiy o`zgaruvchilarga murojaat qilishdan biroz farq qiladi. Massiv elementiga murojaat qilish uning indeksi orqali bo`ladi. a[1] = 10; a massivining 1 – elementi 10 qiymat o’ zlashtirsin; cin >> a[2]; a massivining 2 – elementi kirtilsin; cout << a[3]; a massivining 3 – elementi ekranga chiqarilsin; Massivni e'lon qilishda uning elementlariga boshlang'ich qiymat berish mumkin va buning bir nechta usuli mavjud. 1) O'lchami ko'rsatilgan massivni to'liq initsializatsiyalash. int k[5] = { 2, 3, 7, 8, 6}; Bu yerda 5 ta elementdan iborat bo'lgan k massivi e'lon qilingan va massivning barcha elemantlariga boshlang'ich qiymat berilgan. 2) O'lchami ko'rsatilgan massivni to'liqmas initsializatsiyalash. int k[5] = { 2, 3, 7 }; Bu yerda 5 ta elementdan iborat bo'lgan k massivi e'lon qilingan va massivning dastlabki 3 ta elemantlariga boshlang'ich qiymat berilgan. 3) O'lchami ko'rsatilmagan massivni to'liq initsializatsiyalash. int k[] = { 2, 3, 7, 8, 6}; Shuni takidlash lozimki, agar massiv o'lchami ko'rsatilmasa, uni to'liq initsializatsiyalash shart. Bu xolda massiv o'lchami kompilyatsiya jarayonida massiv elementlari soniga qarab aniqlanadi. Bu yerda massiv o'lchami 5 ga teng. 4) O'lchami ko'rsatilgan massivning barcha elementlariga boshlang'ich qiymat 0 berish: int k[5] = { 0 }; O'lchami ko'rsatilgan massivning barcha elementlariga boshlang'ich qiymat 0 berish #include <iostream.h> int main() { int a[10] = { 0 }; for (int i = 0; i < 10; i++) cout << "a[" << i << "]=" << a[i] << endl; return 0; } Berilgan massiv elimentlarini yig`indisini topish dasturini tuzing #include <iostream.h> int main() { int s=0; int a[10] ; for (int i = 0; i < 10; i++) { cout << "a[" << i << "]="; cin >> a[i]; s=s+a[i]; } cout << "Massivning yig`indisi=" <<s<< endl; return 0; } Funksiyalar . C++ da dasturlashning asosiy bloklaridan biri funksiyalardir. Funksiyalar dasturchi ishini juda yengillashtiradi. Funksiyalar yordamida programma modullashadi, qismlarga bo'linadi. Bu esa keyinchalik dasturni rivojlantirishni osonlashtiradi. Bunda dasturchi yozgan funksiyalar C++ ning standart kutubhonasi va boshqa kutubhonalar ichidagi funksiyalar bilan birlashtiriladi. Bu esa ishni osonlashtiradi. Ko'p holda dasturda takroran bajariladigan amalni funksiya sifatida yozish va kerakli joyda ushbu funksiyani chaqirish mumkin. Dastur yozilish davrida hatolarni topishni yengillashtiradi. Bir misolda funksiyaning asosiy qismlarini ko'rib chiqaylik: int foo(int k, int t) { int result; result = k * t; return (result); } Yuqoridagi foo funksiyamizning ismi, () qavslar ichidagi parametrlar – int tipidagi k va t lar kirish argumentlaridir , ular faqat ushbu funksiya ichida ko'rinadi va qo'llaniladi. Bunday o'zgaruvchilar lokal (local - mahalliy) deyiladi. result foo() ning ichida e’lon qilinganligi uchun u ham lokaldir. Demak biz funksiya ichida o'zgaruvchilarni va sinflarni (class) e’lon qilishimiz mumkin ekan. Lekin funksiya ichida boshqa funksiyani e’lon qilib bo'lmaydi. foo() funksiyamiz qiymat ham qaytaradi. Qaytish qiymatining tipi foo() ning e’lonida eng boshida kelgan - int tipiga ega. Biz funksiyadan qaytarmoqchi bo'lgan qiymatning tipi ham funksiya e’lon qilgan qaytish qiymati tipiga mos kelishi kerak - ayni o'sha tipda bo'lishi yoki o'sha tipga keltirilishi mumkin bo'lgan tipga ega bo'lishi shart. Funksiyadan qiymatni return ifodasi bilan qaytaramiz. Agar funksiya hech narsa qaytarmasa e’londa void tipini yozamiz. Ya’ni: void funk() { int g = 10; cout << g; return; } Bu funksiya void (bo’sh, hech narsasiz) tipidagi qiymatni qaytaradi. Boshqacha qilib aytganda qaytargan qiymati bo’sh to’plamdir. Lekin funksiya hech narsa qaytarmaydi deya olmaymiz. Chunki hech narsa qaytarmaydigan mahsus funksiyalar ham bor. Ularning qaytish qiymati belgilanadigan joyga hech narsa yozilmaydi. Biz unday funksiyalarni keyinroq ko’rib chiqamiz. Bu yerda bir nuqta shuki, agar funksiya mahsus bo’lmasa, lekin oldida qaytish qiymati tipi ko’rsatilmagan bo'lsa, qaytish qiymati int tipiga ega deb qabul qilinadi. void qaytish tipli funksiyalardan chiqish uchun return; deb yozsak yetarlidir. Yoki return ni qoldirib ketsak ham bo’ladi. Funksiyaning qismlari bajaradan vazifasiga ko’ra turlicha nomlanadi. Yuqorida korib chiqqanimiz funksiya aniqlanishi (function definition) deyiladi , chunki biz bunda funksiyaning bajaradigan amallarini funksiya nomidan keyin, {} qavslar ichida aniqlab yozib chiqyapmiz. Funksiya aniqlanishida {} qavslardan oldin nuqta-vergul (;) qo'yish hatodir. Bundan tashqari funksiya e’loni, prototipi yoki deklaratsiyasi (function prototype) tushunchasi qo'llaniladi. Bunda funksiyaning nomidan keyin hamon nuqta-vergul qo'yiladi, funksiya tanasi esa berilmaydi. C++ da funksiya qo’llanilishidan oldin uning aniqlanishi yoki hech bo'lmaganda e’loni kompilyatorga uchragan bo'lishi kerak. Agar funksiya e’loni boshqa funksiyalar aniqlanishidan tashqarida berilgan bo'lsa, uning kuchi ushbu fayl ohirigacha boradi. Biror bir funksiya ichida berilgan bo'lsa kuchi faqat o'cha funksiya ichida tarqaladi. E’lon fayllarda aynan shu funksiya e’lonlari berilgan bo’ladi. Funksiya e’loni va funksiya aniqlanishi bir-biriga mos tushishi kerak. Funksiya e’loniga misol: double square(char, bool); float average(int a, int b, int c); Funksiya e’lonlarda kirish parametrlarining faqat tipi yozish kifoya, huddi square() funksiyasidek. Yoki kiruvchi parametrlarning nomi ham berilishi mumkin , bu nomlar kompilyator tarafidan etiborga olinmaydi, biroq dasturning o'qilishini ancha osonlashtiradi. Bulardan tashqari C++ da funksiya imzosi (function signature) tushunchasi bor. Funksiya imzosiga funksiya nomi, kiruvchi parametrlar tipi , soni, ketma-ketligi kiradi. Funksiyadan qaytuvchi qiymat tipi imzoga kirmaydi. int foo(); //No1 int foo(char, int); //No2 double foo(); //No3 - No1 funksiya bilan imzolari ayni. void foo(int, char); //No4 - No2 bilan imzolari farqli. char foo(char, int); //No5 - No2 bilan imzolari ayni. int foo(void); //No6 - No1 va No3 bilan imzolari ayni, Yuqoridagi misolda kirish parametrlari bo'lmasa biz () qavsning ichiga void deb yozishimiz mumkin (No6 ga qarang). Yoki () qavslarning quruq o’zini yozaversak ham bo’ladi (No1 ga qarang). 64 Yana bir tushuncha - funksiya chaqirig'idir. Dasturda funksiyani chaqirib, qo'llashimiz uchun uning chaqiriq ko'rinishini ishlatamiz. () qavslari funksiya chaqirig'ida qo'llaniladi. Agar funksiyaning kirish argumentlari bo’lmasa, () qavslar bo’sh holda qo’llaniladi. Ma’lumki, funksiyalarni aniqlashda ulaming qaytarishi lozim bo‘lgan qiymatlar tipi va funksiya uchun zarur bo‘lgan parametrlar tipini ko'rsatish lozim edi. Faraz qilaylik , ikkita butun sonni qo‘shish uchun funksiya qurilgan bo‘lsin. Agar uchta butun sonni qo‘shish talab qilingan bo‘lsa, ular uchun boshqa nomdagi funksiyani qurish talab qilinadi. Ikkita haqiqiy sonni qo‘shish uchun esa boshqa funksiya qurish lozim bo'ladi. Bunday hollarda bir xil funksiyani takror va takror yozishning o'miga, C++ tili bir xil nomdagi funksiyalarni qurish imkonini beradi. Dastumi kompilatsiya qilish jarayonida C++ funksiyalaming har biridagi argumentlar miqdori e’tiborga olinadi va aynan kerak bo'lgan funksiyani chaqiradi. Kompilyatorga bir nechta funksiyalar orasidan kcragini tanlash imkoniyati funksiyalarni qayta yuklash deb ataladi. Funksiyalami qayta yuklash amali bir xil nomdagi parametrlami har xil tipga mansub bo‘lgan turli funksiyalar uchun qo‘llashga ruxsat beradi. Masalan, quyidagi dastur add_values nomli ikkita funksiyani qayta yuklash uchun xizmat qiladi: #include using namespace std; int add_values (int a, int b) { return(a + b); } int add_values (int a, int b, int c) { return(a + b + c); } int main() { cout « “200 + 801 = “ « add_values(200, 801) « endl; cout « “100 + 201 + 700 = “ « add_values(100, 201, 700) « endl;} Dastur natijasi quyidagicha aks etadi: Ko‘rinib turibdiki , dasturda ikkita bir xil nomdagi, ammo parametrlari soni har xil bo‘lgan add_values funksiyasi aniqlangan. Bu holda kompilyator parametrlar soniga ko‘ra qaysi funksiyani qo‘llash haqida mustaqil ravishda xulosa qiladi. Agar funksiya o‘zidan yordamchi funksiya sifatida foydalanadigan bo‘lsa, bunday funksiyalar rekursiv deyiladi. Rekursiv funksiyalar ikki turga bo‘linadi: a) to‘g‘ri rekursiya. Bunda dastur o‘ziga-o‘zi murojaat qiladi. b) yondosh rekursiya. Bunda A funksiya B ga, B funksiya A ga murojaat qiladi. Rekursiv funksiya yozish uchun avvalo : 1) rekkurent munosabat ; 2) shu munosabat uchun boshlang‘ich holatlar aniqlangan bo‘lishi shart. Rekkurent munosabat deganda qaralayotgan jarayonga doir muayyan bosqichlami avvalgi bosqichlar bilan bog‘lovchi munosabatlar tushuniladi. Masalan, N! =N*(N—1) formulani N! uchun rekurent munosabat deb qarash mumkin. Boshlang‘ich holat sifatida esa 1!=1 olinadi. Keltirilgan ma’lumotlami hisobga olsak, faktorialni hisoblash masalasi uchun rekkurent va boshlang‘ich munosabatlar quyidagicha bo'ladi: Ko‘rinib turibdiki, N! ni hisoblash uchun (N-1)! ma’lum bo‘lishi kerak. Lekin, (N-1)!=(N-1)*(N-2)! bo‘lgani uchun o‘z navbatida (N-2)! ni inpish talab qilinadi. (N-2)! esa (N-3)!*(N-2) ga teng va hokazo. Bu yerda N! ni hisoblash algoritmi o ‘zining ichiga o ‘zi “cho‘kib” borishi hodisasi ro‘y bermoqda. Cho‘kish jarayoni boshlang‘ich holat sodir bo‘lgunga qadar, ya’ni 1! gacha davom etadi. Shundan keyin , “cho‘- kish” jarayoni to‘xtaydi, 1!=1 ekanligi haqida ko‘rsatma olgan kompyuter yuqoriga qarab “suzib” chiqish bosqichini boshlaydi. Ya’ni, 2!=1, 2!=l- 2=2, 3 !=2!-3=6 va hokazo. Bu holat to N! hisoblanmaguncha davom etaveradi. Yuqorida keltirilgan masala dasturi quyidagicha bo’ladi: #include using namespace std; long fak(int m) { long f; if (m==1) f=1; else f=fak(m-1)*m; return f; } int main() { int n; cout<<"Butun sonni kiriting: "; cin>>n; cout< } Dastur natijasi quyidaicha bo’ladi: Funksiyalarning e’lon qilinishi ularning nomi va turini ko’rsatib beradi. Funksiyalarning aniqlanishi esa ularning nomi, turi va “tanasi” ni ko’rsatib beradi. Misol: void Funksiya1 ( int ) ; // funksiya e’lon qilinyapti int Funksiya2 () { //... } // funksiya aniqlanyapti void , obyekt yoki funksiyalar uchun ko’rsatgichlar (sinflarning statik a’zolari uchun ham). Misol: void * Ptr ; // istalgan turdagi obyekt uchun ko’rsatgich int * IntPtr ; // butun son uchun ko’rsatgich int ( * FuncPtr )() ; // funksiya uchun ko’rsatgich Obyekt yoki funksiyalar uchun adreslar (reference, ссылка ). Ikki turdagi adreslar mavjud: l-ifoda adreslari va r-ifoda adreslari. r-ifoda adres tushunchasi C+ + 11 dan boshlab kiritilgan. Misol: int Butun ; int & AButun = Butun ; // bu yerda AButun l-ifoda adres int Funksiya1 ( X && v ) ; // bu yerda v r-ifoda adres, X biror sinf int Funksiya2 () { //... } int ( & AFunksiya2 )() = Funksiya2 ; // bu yerda AFunksiya2 l-ifoda adres Sinf ( struct , class ) Uyushma ( union ) Sanoq ( enumeration ) Sinflarning statik bo’lmagan a’zolari uchun ko’rsatgichlar. Misol: struct X { int IntMem ; } ; int X :: * IntMemPtr = & X :: IntMem ; // bu yerda IntMemPtr – ko’rsatgich X x ; // x obyektini yaratamiz x. * IntMemPtr = 100 ; // x ning IntMem a’zosini o’zgartiramiz Yuqoridagi standart turlardan tashqari, kompillyatorlar qo’shimcha turlarga ega bo’lishlari ham mumkin. Masalan, ko’p kompillyatorlar __int8 , __int16 , __int32 , __int64 (ishorali va ishorasiz) butun sonlar turlariga ega Ma’lumot strukturalari Ma'lumotlar strukturasi nima? Ma'lumotlar strukturasi - bu ma'lum bir sxemada ma'lumotlarni saqlaydigan konteyner. Ushbu "tartib" ma'lumotlar tuzilmasini ba'zi operatsiyalarda samarali, boshqalarida esa samarasiz bo'lishiga imkon beradi. Chiziqli, elementlar ketma-ketlik yoki chiziqli ro'yxatni tashkil qiladi, tugunlarning o'tishi chiziqli. Misollar: massivlar. Bog'langan ro'yxat, steklar va navbatlar. Agar tugunlarning o'tishi chiziqli bo'lmasa va ma'lumotlar ketma-ket bo'lmasa, chiziqli emas. Misol: grafik va daraxtlar. Ma'lumotlarning asosiy tuzilmalari. 1. Massivlar 2. Stacks 3. Navbatlar 4. Bog'langan ro'yxatlar 5. Grafiklar 6. Daraxtlar 7. Prefiksli daraxtlar 8. Xesh-jadvallar Massiv – Massivlar hotirada ketma-ket joylashgan, bir tipdagi o'zgaruvchilar guruhidir. Alohida bir o'zgaruvchini ko'rsatish uchun massiv nomi va kerakli o'zgaruvchi indeksini yozamiz. C/C++ dagi massivlardagi elementlar indeksi har doim noldan boshlanadi. Bizda char tipidagi m nomli massiv bor bo'lsin. Va uning 4 dona elementi mavjud bo'lsin. Shemada bunday ko'rsataylik: m[0] -> 4 m[1] -> -44 m[2] -> 109 m[3] -> 23 Ko'rib turganimizdek, elementga murojaat qilish uchun massiv nomi va [] qavslar ichida element indeksi yoziladi. Bu yerda birinchi element qiymati 4, ikkinchi element - 1 nomerli indeksda -44 qiymatlari bor ekan. Ohirgi element indeksi n-1 bo'ladi (n - massiv elementlari soni). [] qavslar ichidagi indeks butun son yoki butun songa olib keluvchi ifoda bo'lmog'i lozim. Masalan: ... int k = 4, l = 2; m[ k-l ] = 77; // m[2] = 77 m[3] *= 2; // m[3] = 46 double d = m[0] * 6; // d = 24 cout << m[1]; // Ekranda: -44 ... Massivlarni ishlatish uchun ularni e'lon qilish va kerak bo'lsa massiv elementlarini initsalizatsiya qilish kerak. Massiv e'lon qilinganda kompilyator elementlar soniga teng hajmda hotira ajratadi. Masalan yuqorida qo'llanilgan char tipidagi m massivini e'lon qilaylik. char m[4]; Bu yerdagi 4 soni massivdagi elementlar miqdorini bildiradi. Bir necha massivni e'londa bersak ham bo'ladi: int m1[4], m2[99], k, l = 0; Massiv elementlari dastur davomida initsalizatsiya qilishimiz mumkin, yoki boshlang'ich qiymatlarni e'lon vaqtida, {} qavslar ichida ham bersak bo'ladi. {} qavslardagagi qiymatlar massiv initsalizaytsiya ro'yhati deyiladi. int n[5] = {3, 5, -33, 5, 90}; Yuqorida birinchi elementning qiymati 3, ikkinchiniki 5 ... ohirgi beshinchi element qiymati esa 90 bo'ldi. Boshqa misol: double array[10] = {0.0, 0.4, 3.55}; Bu yerdagi massiv tipi double bo'ldi. Ushbu massiv 10 ta elementdan iboratdir. {} qavslar ichida esa faqat boshlangich uchta element qiymatlari berildi. Bunday holda, qolgan elementlar avtomatik tarzda nolga tenglashtiriladi. Bu yerda aytib o'tishimiz kerakki, {} qavslar ichida berilgan boshlangish qiymatlar soni massivdagi elementlar sonidan katta bo'lsa, sintaksis hatosi vujudga keladi. Masalan: char k[3] = {3, 4, 6, -66, 34, 90}; // Hato! Uch elementdan iborat massivga 6 dona boshlangich qiymat berilyapti, bu hatodir. Boshqa misolni ko'rib chiqaylik: int w[] = {3, 7, 90, 78}; w nomli massiv e'lon qilindi, lekin [] qavslar ichida massivdagi elementlar soni berilmadi. Bunday holda necha elementga joy ajratishni kompilyator {} qavslar ichidagi boshlangich qiymatlar miqdoriga qarab biladi. Demak, yuqoridagi misolda w massivimiz 4 dona elementdan iborat bo'ladi. Stackga misol sifatida vertikal ravishda joylashtirilgan kitoblar to'plami bo'lishi mumkin. O'rtada joylashgan kitobni olish uchun undagi barcha kitoblarni o'chirishingiz kerak bo'ladi. Navbatlar - steklar singari, navbat ham elementni ketma-ket saqlaydi. Stackdan sezilarli farq LIFO o'rniga FIFO (First in First Out) dan foydalanishdir. (inglizcha " birinchi kelgan - birinchi ketadi"). Navbatga misol qilib odamlarning navbatini keltirish mumkin. Oxirgisi oxirgisini oldi va siz bo'lasiz va birinchisi uni birinchi bo'lib tark etadi. To'rt elementda (1, 2, 3 va 4) navbat tasviri, bu erda 1 element tepada joylashgan va avval olib tashlanadi. Keyin 2element olib tashlanadi navbati bn 3- va 4- element olib tashlanadi. Bog'langan ro'yxat massiv bo'lib, unda har bir element alohida ob'ekt bo'lib, ikkita elementdan - ma'lumotlar va keyingi tugunga havoladan iborat. Massivning asosiy ustunligi uning strukturaviy moslashuvchanligidir: bog'langan ro'yxat elementlarining tartibi kompyuter xotirasidagi ma'lumotlar elementlarining tartibiga to'g'ri kelmasligi mumkin va ro'yxat bo'ylab harakatlanish tartibi har doim uning ichki havolalari bilan aniq belgilanadi. . Ikki tomonlama, har bir tugun bilan bog'langan ikkita havolalardan biri keyingi tugunga va biri oldingi tugunga ishora qiladi. Grafik bir-biri bilan chekkalar (yoylar) orqali tarmoq shaklida bog'langan tugunlar (cho'qqilar) yig'indisidir. Yo'naltirilgan - qirralari yo'naltirilgan, ya'ni ikkita bog'langan cho'qqilar o'rtasida faqat bitta yo'nalish mavjud. Yo'naltirilmagan - qirralarning har biri ikkala yo'nalishda ham o'tkazilishi mumkin. Daraxt - bu tugunlardan (cho'qqilar) va qirralardan (yoylardan) tashkil topgan ierarxik ma'lumotlar strukturasi. Daraxtlar, asosan, halqasiz bog'langan grafiklardir. Daraxt turlari: • N daraxt • Muvozanatli daraxt • Ikkilik daraxt • Ikkilik qidiruv daraxti • AVL daraxti • 2-3-4 daraxt Ikkilik daraxti - bu ierarxik ma'lumotlar strukturasi bo'lib, unda har bir tugun o'z qiymatiga ega. Daraxtdan o'tishning uchta usuli • To'g'ridan-to'g'ri tartibda (yuqoridan pastga) - prefiks shakli. • Simmetrik tartibda (chapdan o'ngga) - infiks shakli. • Teskari tartibda (pastdan yuqoriga) - postfiks shakli. Xeshlash - bu ob'ektlarni noyob tarzda aniqlash va har bir ob'ektni oldindan hisoblangan noyob indeksda (kalit) saqlash uchun ishlatiladigan jarayon. Ob'ekt kalit-qiymat juftligi sifatida saqlanadi va bunday elementlarning to'plami lug'at deb ataladi. Ushbu kalit yordamida har bir ob'ektni topish mumkin. Ma'lumotlar strukturasi tushunchasi shunchalik fundamentalki, unga oddiy ta'rif berish qiyin. Agar siz ushbu kontseptsiyani ma'lumotlar turlari va o'zgaruvchilari bilan bog'liq holda shakllantirishga harakat qilsangiz, vazifa soddalashtiriladi. Ma’lumki, dastur algoritm (protseduralar, funksiyalar) va ular tomonidan qayta ishlanadigan ma’lumotlarning birligidir. Ma'lumotlar, o'z navbatida, asosiy va olingan ma'lumotlar turlari bilan belgilanadi - ular va ularning tarkibiy qismlari ustida ma'lum operatsiyalar to'plami bilan belgilangan o'lchamdagi o'zgaruvchilarning "ideal" tasvirlari. O'zgaruvchilar - bu tuzilgan ma'lumotlar turlari "xaritalangan" xotira sohalari. Dasturda siz har doim bilvosita bog'langan (bir xil protsedura va funktsiyalarda ma'lumotlardan foydalanish orqali) va to'g'ridan-to'g'ri bog'liq (ko'rsatkichlar orqali aloqalar mavjudligi bilan) o'zgaruvchilar guruhlarini ajrata olasiz. Birinchi taxmin sifatida ularni ma'lumotlar tuzilmalari deb hisoblash mumkin. ODDIY (asosiy, ibtidoiy) ma'lumotlar tuzilmalari (turlari) va INTEGRATED (strukturali, kompozit, murakkab) o'rtasida farqlang. Oddiy ma'lumotlar tuzilmalari - bu bitdan kattaroq qismlarga bo'linib bo'lmaydigan tuzilmalar. Jismoniy tuzilma nuqtai nazaridan, ma'lum bir mashina arxitekturasida, ma'lum dasturlash tizimida biz har doim berilgan oddiy tipning o'lchami qanday bo'lishini va uni joylashtirish strukturasi qanday bo'lishini oldindan aytishimiz muhimdir. xotira. Mantiqiy nuqtai nazardan, oddiy ma'lumotlar bo'linmas birlikdir. Integratsiyalashgan ma'lumotlar tuzilmalari - tarkibiy qismlari boshqa ma'lumotlar tuzilmalari bo'lganlar - oddiy yoki o'z navbatida integratsiyalashgan. Integratsiyalashgan ma'lumotlar tuzilmalari dasturchi tomonidan dasturlash tillari tomonidan taqdim etilgan ma'lumotlar integratsiya vositalaridan foydalangan holda tuziladi. Ma'lumotlar elementlari o'rtasida aniq belgilangan munosabatlarning yo'qligi yoki mavjudligiga qarab, BO'LGAN BO'LMAGAN tuzilmalar (vektorlar, massivlar, satrlar, steklar, navbatlar) va BOG'LANGAN tuzilmalar (bog'langan ro'yxatlar) o'rtasida farqlash kerak. Ma'lumotlar strukturasining juda muhim xususiyati uning o'zgaruvchanligi - elementlar sonining o'zgarishi va (yoki) strukturaning elementlari orasidagi bog'lanishdir. Tuzilishning o'zgaruvchanligi ta'rifi ma'lumotlar elementlarining qiymatlari o'zgarganligini aks ettirmaydi, chunki bu holda barcha ma'lumotlar tuzilmalari o'zgaruvchanlik xususiyatiga ega bo'ladi. O'zgaruvchanlik asosida tuzilmalar ajralib turadi: STATIK, YARIM-STATIK, DINAMIK. O'zgaruvchanlikka asoslangan ma'lumotlar tuzilmalarining tasnifi rasmda ko'rsatilgan. Statik, yarim statik va dinamik ma'lumotlarning asosiy tuzilmalari RAMga xos bo'lib, ko'pincha onlayn tuzilmalar deb ataladi. Fayl tuzilmalari tashqi xotira uchun ma'lumotlar tuzilmalariga mos keladi. Statik deganimizda hotirada egallagan joyi o'zgarmas, dastur boshida beriladigan strukturalarni nazarda tutamiz. Dinamik ma'lumot tiplari dastur davomida o'z hajmini, egallagan hotirasini o'zgartirishi mumkin Ma'lumotlar tuzilmalarini doimiyga o'tkazish usullari Har qanday tuzilmani barqaror qilishning bir necha yo'li mavjud:  to'liq zaxira nusxasi (inglizcha to'liq nusxasi ) har qanday o'zgartirish operatsiyasi uchun ma'lumotlar strukturasi to'liq nusxalanganda, natijada yangi nusxa o'zgartiriladi,  yuqoriga yo'l (ingliz. yo'ldan nusxa ko'chirish ),  yog 'tugun usuli . Qisman qat'iyat bilan boshlaylik. Aniqlik uchun ma'lumotlar tuzilmalarining turli versiyalarini raqamlaymiz. Ma'lumotlar strukturasidagi o'zgarishlar tarixi chiziqli bo'lib, istalgan vaqtda ma'lumotlar strukturasining istalgan versiyasiga murojaat qilishingiz mumkin, lekin faqat oxirgi versiyasini o'zgartirish mumkin (rasmda u ko'k rang bilan ta'kidlangan). Keling, ma'lumotlar strukturasi nima ekanligini aniqlaylik. Bizning tushunchamizga ko'ra, ma'lumotlar strukturasi ba'zi ma'lumotlarni saqlaydigan tugunlar to'plami deb ataladi va bu tugunlar havolalar bilan bog'lanadi. Ma'lumotlar strukturasiga misol daraxtdir . Keling, yo'lni nusxalash orqali daraxtni qanday qilib barqaror qilishni ko'rib chiqaylik. To'liq doimiy ma'lumotlar tuzilmalari uchun yuqorida tavsiflangan transformatsiya usuli ishlamaydi, chunki versiyalar tarixi chiziqli emas va qisman doimiy ma'lumotlar tuzilmalarida bo'lgani kabi o'zgarishlarni versiya bo'yicha saralab bo'lmaydi. Faraz qilaylik, biz versiya o'zgarishlari tarixini daraxt shaklida saqlaymiz. Keling, bu daraxtni chuqurroq sayr qilaylik . Ushbu vaqtinchalik hal qilish tartibida biz har bir versiyaga qachon kirishimiz va qachon chiqishimizni yozamiz. Ushbu harakatlar ketma-ketligi daraxtni to'liq belgilaydi, keling, undan ro'yxat tuzamiz. Ba'zi versiyadan keyin (quyidagi rasmda bu versiya ) ma'lumotlar strukturasining yangi versiyasi qo'shilganda (rasmda versiya ), biz ro'yxatga ikkita elementni kiritamiz (rasmda u va 66sakkiz8+ 8+8- 8−8 ) tizimga kirgandan so'ng, lekin o'zgarish sodir bo'lgan versiyadan chiqishdan oldin (ya'ni, elementlar va ). Birinchi element o'zgarishlarni amalga oshiradi, ikkinchisi esa avvalgi versiya qiymatiga qaytadi. Shunday qilib, har bir operatsiya ikkiga bo'linadi: birinchisi o'zgarishlarni amalga oshiradi, ikkinchisi esa uni orqaga qaytaradi. + 6+6- 6−6 Oldingi paragrafda tavsiflangan ma'lumotlar tuzilmalarini to'liq barqarorlikka o'tkazish usulini amalga oshirish uchun bizga operatsiyalarni qo'llab- quvvatlaydigan ro'yxat kerak . Agar oldin yolg'on bo'lsa va boshqacha tarzda qaytariladi . Bu ro'yxat tartibini saqlash so'rovini qo'llab-quvvatlaydigan ro'yxat bo'lib, u ikkala operatsiyani ham bajaradi . i n s e r t A ft e r ( p , q)insertAfter(p,q)qqppo r d e r ( p , q)order(p,q)ppq qo r d e r ( p , q)order(p,q)bitta1ppqq00O ( 1 )O(1) O'zgartirish jurnali «qalin» birligi endi ikki hodisalarni kiritish bo'ladi: biri tegishli versiyada o'zgarishlar, uning bekor boshqa ko'rsatadi. Voqealar o'zgartirish jurnaliga versiya raqami bo'yicha emas, balki Ro'yxat tartibini saqlash ro'yxatidagi tartibi bo'yicha qo'shiladi . Agar versiyaga so'rov bo'lsa, siz versiyalar ro'yxatidan birini topishingiz kerak, qaysi birini kiritganingizdan so'ng, lekin qaysi versiyadan chiqishdan oldin so'rovning versiyasi mavjud va ular orasida maksimal. Misol uchun, agar so'rov yuqoridagi rasmdagi versiyaga kelsa , u holda biz kiritilgandan keyin versiyalar ro'yxatida ekanligini ko'ramiz, lekin versiyada chiqarilishidan oldin , va . Ularning eng kattasini topish kerak. Ro'yxat ro'yxati Buyurtmani saqlash operatsiyadan foydalanish uchun buni amalga oshirishga imkon beradi . Misolda, bu versiya . Yildan o'zgartirish log har bir tugunni doimiy hajmini ega, zarur versiyasi uchun qidiruv uni uchraydi yilda . 66bitta12244O ( 1 )O(1)o r d e r ( p , q)order(p,q)44O ( 1 )O(1) Bir nuqtada , yog 'tugunining o'zgarish jurnali to'lib ketadi. Keyin ushbu tugunni klonlashingiz va o'zgarishlarning pastki yarmini klonlangan tugunning o'zgarishlar jurnaliga o'tkazishingiz kerak . O'zgarishlarning birinchi yarmini tugunning asl versiyasiga qo'llang va uni asl nusxa sifatida klonlangan tugunga saqlang. Ikki tugun bo'ladi: birinchisi oxirgi o'zgartirish operatsiyasidan oldin versiyalar segmenti uchun javob beradi, ikkinchisi esa undan keyin. Keyingi protsedura qisman doimiy ma'lumotlar tuzilmalarini qurishning umumiy usulida qo'llaniladiganga o'xshaydi. Keling, ushbu algoritmning amortizatsiya vaqtini hisoblaylik. To'liq tugunlar soniga teng potentsial funktsiyani kiritamiz. Tugun ikkiga bo'linganda, potentsialning funktsiyasi bittaga kamayadi, keyin biz bog'lanishlarni qayta joylashtiramiz, potentsial ga ortadi , ya'ni ishning amortizatsiya vaqti . PPPPO ( 1 )O(1) Xulosa. Foydalanilgan adabiyotlat ro’yhati. 1. Nazarov Fayzullo Maxmadiyarovich, “Algoritimlar va ma’lumotlar strukturasi”. Samarqand – 2019. 2. Boboxo’jayeva N.M “Algoritimlar nazariyasi”. 3. B.B.Akbaraliyev. “Ma’lumotlar tuzilmasi va algoritimlar”. Toshkent – 2011. 4. A.R.Azamatov, “Algoritimlash va dasturlash asoslari”. Cho 'lpon nomidagi nashriyot-matbaa ijodiy uyi Toshkent — 2013 . 5. Sh. I. Razzoqov, M. J. Yunusova. Dasturlash: Kasb-hunar kollejlari uchun o quv qo llanma. T. : “Ilm Ziyo”, 2011y. ʻ ʻ 6. T. X. Holmatov, N. I. Tayloqov . Amaliy matematika, dasturlash va kompyuterning dasturiy ta`minoti. O quv qo llanma ʻ ʻ . T :. “Me h nat”, 2000 y. 7. Sattorov A. Informatika va axborot texnologiyalari. Darslik. Т. : , “ O qituvchi ʻ ” , 20 11 y .

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))

Загрузите документ, чтобы увидеть его полностью.

Похожие

DOIMIY MA’LUMOTLAR STRUKTURALARI
DOIMIY MA’LUMOTLAR STRUKTURASI
Doimiy (stasionar) parazitizm
Doimiy ustuvor navbatb algoritmi.
Ma’lumotlar bazalari. Ma’lumotlar bazasi xaqida