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.](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_1.png)
![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.](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_2.png)
![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.](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_3.png)
![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))](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_4.png)
![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).](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_5.png)
![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.](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_6.png)
![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](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_7.png)
![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:](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_8.png)
![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 } ;](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_9.png)
![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,](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_10.png)
![ 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.](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_11.png)
![ 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.](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_12.png)
![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.](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_13.png)
![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;](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_14.png)
![}
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)
{](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_15.png)
![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;](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_16.png)
![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](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_17.png)
![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](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_18.png)
![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()](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_19.png)
![{ 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.](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_20.png)
![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()
{](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_21.png)
![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](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_22.png)
![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 ; } ;](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_23.png)
![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](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_24.png)
![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;](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_25.png)
![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](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_26.png)
![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](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_27.png)
![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.](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_28.png)
![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.](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_29.png)
![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](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_30.png)
![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).](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_31.png)
![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](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_32.png)
![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](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_33.png)
![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.](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_34.png)
![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.](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_35.png)
![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 .](/data/documents/f3ed9a44-04d2-459d-a78b-aafacf3bdf1f/page_36.png)
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).