logo

DOIMIY MA’LUMOTLAR SUTRUKTURASI

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

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

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