logo

DINAMIK DASTURLASH METODLARINI OPTIMALLASHTIRISH USULLARI

Yuklangan vaqt:

08.08.2023

Ko'chirishlar soni:

0

Hajmi:

2546.396484375 KB
                  
                  
“ALGORITM VA MA’LUMOTLAR STRUKTURASI” FANIDAN
       “ DINAMIK DASTURLASH METODLARINI 
OPTIMALLASHTIRISH USULLARI ” MAVZUSIDA            
                                       TAYYORLAGAN
 
SAMARQAND – 2021
1KU
RS 
IS
HI Mundarija
I Kirish
II Asosiy qism ……..………………………………………………..4
2.1. Dinamik dasturlash haqida umumiy tushunchalar……….…......4
2.2.Dinamik dasturlashda optimallik tamoyili……………………....8
2.3. C++ dasturlash tilida dinamik dasturlar yaratish…….…..……..17  
2.4. C++ dasaturlash tilida dinamik ma’lumotlar tuzilmasi……..….24
III Xulosa………………………………………………...…………39
IV Foydalanilgan adabiyotlar………………………………….……40
2               Kirish
Vatanimizda,   erkin   va   farovon   hayot   barpo   etish,   rivojlangan   mamlakatlar
qatoridan   o’rin   olish,   demokratik   jamiyat   qurish   kabi   ezgu   maqsadlarni   qo’yildi.
Bu   esa   kelajagimizni   yaqqol   tasavvur   etish,   jamiyatimizning   ijtimoiy-ma‘naviy
poydevorini   mustahkamlash   ehtiyojini   tug’diradi.   Demak,   galdagi   eng   asosiy
vazifa:   yosh   avlodni   vatan   ravnaqi,   yurt   tinchligi,   xalq   farovonligi   kabi   olijanob
tuyg’ular   ruhida   tarbiyalash,   yuksak   fazilatlarga   ega,   ezgu   g’oyalar   bilan
qurollangan   komil   insonlarni   voyaga   etkazish,   jahon   andozalariga   mos,   kuchli
bilimli,   raqobatbardosh   kadrlar   tayyorlashdir.   O’zbekistonning   iqtisodiy   va
ijtimoiy   sohalarda   yuqori   natijalarga   erishishi,   jahon   iqtisodiy   tizimida   to’laqonli
sheriklik o’rnini egallay borishi, inson faoliyatining barcha jabhalarida zamonaviy
axborot   texnologiyalaridan   yuqori   darajada   foydalanishning   ko’lamlari   qanday
bo’lishiga   hamda   bu   texnologiyalar   ijtimoiy   mehnat   samaradorligini   oshishida
qanday   rol   o’ynashiga   bog’liq.   Keyingi   yillarda   mamlakatimiz   ilm-fani   ham
axborotlashtirishning   nazariy   asoslariga   katta   hissa   qo‗shib   kelmoqda,   shu   bilan
birgalikda,   hodisalar,   jarayonlarni   yagona   axborot   asosida   tadqiq   etishning   ilmiy
yo’nalishlarini  tahlil  va sintez  qilish natijasi  bo’lgan fan-informatikaning vujudga
kelishiga   boshlang’ich   poydevor   qo’yildi.   Axborot,   energiya,   vazn,   bo’shliq   va
vaqtni   bir   butun   holda   batafsil   o’rganish   hozirgi   vaqtda   inson   hayotining   barcha
jabhalarida muhim axamiyatga ega bo’lib qolmoqda.
3 Dinamik dasturlash haqida umumiy tushunchalar
Dinamik   dasturlash   tushunchasi   juda   keng   qamrovli   tushuncha   bolib,Bu
tushunchao’z ichiga ko’plab yo’nalishlar va sohalarni qamrab oladi.
  Dasturchilar   butunlay   boshqacha   vazifalarga   ega   bo'lishi   mumkin.   Bir   holatda,
biror   narsani   chizish   uchun   faqat   belgilash   tilidan   foydalanishingiz   kerak,
ikkinchisida protsessor samarali ishlashi uchun assembler orqali ko'rsatmalar yozis
kerak.Ammo   bu   assotsiatsiya   barcha   odamlar   uchun   ishlaydi   -   dasturchilar
algoritmlarni ishlab chiqadilar.
  Tasavvur qilaylik, bizga yangi vazifa qo’yildi, uning maqsadi va cheklovlari bor.
Har   qanday  vazifada  bo'lgani  kabi,  u  ham   ma'lumotlar  tuzilmalarini   va  tizimning
boshqa qismlariga bog'liqlikni o'z ichiga oladi
za   bir   vaqtning   o'zida   siz   ushbu   vazifa   uchun   ishlash   muhim.     Bunidarhol
tushunish mumkin. Masalan, avval  muammoni hal qilgandan  keyin yechim sekin
ekanligini   payqashimiz   mumkin   .Bunday   holatda   hisob-kitob   natijalari   kamroq
vaqt ichida olinishi uchun muammoni qanday hal qilishni kerak.
Dasturlash   nuqtayi   nazaridan   dinamik   dasturlash   atamasi   biz   yaratayotgan
dasturmizga ma’lumotlarni kirtganimizdak keyin vaqt o’tishi bilan avvalgi kiritgan
ma’lumotlarimizning bizga keragi bo’lmasligi mumkin.Shunda bizga malumotlarni
kiritish va chiqarish jarayonida eski ma’lumotlarni o’chirish kerak bo’ladi.
Dinamik dasturga misol
C++ dasturlash tilida
#include<iostream>
using namespace std;
int main(){
int  m;
cout << "m="; cin >> m; //massiv elementlari soni;
float *b = new float[m]; //Element haqiqiy sonlar bo'lgan m ta elementli dinamik 
massiv;
4 for (int j = 0; j < m; j++)
cin >> b[j]; // bir o'lchamli Massivni to'ldirish
cout<<"     bir o'lchamli dinamik massiv"<<endl;
for (int j = 0; j < m; j++)
cout<<b[j]<<" ";
delete [] b;//xotira bo'shatildi
cout<<"\n xotira bo'shatildi";
return 0;
}
Dinamik dastur
Java dasturlash tilida
class Array {
private int arr[];
private int count;
public Array(int length) { arr = new int[length]; }
public void printArray()
{
for (int i = 0; i < count; i++) {
// Print the elements of an array
System.out.print(arr[i] + " ");
}
}
public void insert(int element)
{
5 if (arr.length == count) {
int newArr[] = new int[2 * count];
for (int i = 0; i < count; i++) {
newArr[i] = arr[i];
}
arr = newArr;
}
arr[count++] = element;
}
}
public class GFG {
public static void main(String[] args)
{
Array numbers = new Array(3);
numbers.insert(10);
numbers.insert(30);
numbers.insert(40);
numbers.insert(50);
numbers.printArray();
}
}
6 Ammo kirish ma'lumotlarining soni va  qiymatining oshishi bilan yechim vaqti 
sezilarli darajada oshib borishini tushunishimiz mukin.Bunda bizga Dinamik 
dasturlash haqida o’ylashimiz kerak bo’ladi.
Algoritmni tavsiflashdan oldin ikkita tushunchani kiritamiz - xotira va jadval.
7 Dinamik dasturlashda optimallik tamoyili
  Dinamik   dasturlash     ham   matematematik   optimallashtrish   usuli   va
kompyuter   dasturlash   usuli.   Usul   Richard   Bellman   tomonidan   ishlab
chiqilgan     1950   yillarda   ,   aerokosmik   muhandislik   ga   iqtisodiyot   va   ko'plab
sohalarda dasturiy yechimlarni yaratdi.
Ikkala   kontekstda   u   murakkab   muammoni     oddiy   kichik   muammolarga   ajratish
orqali   soddalashtirishga   ishora   qiladi   rekursiv   uslubi.   Qaror   bilan   bog'liq   ba'zi
muammolarni shu tarzda ajratib bo'lmaydigan bo'lsa-da, bir necha vaqtni o'z ichiga
olgan   qarorlar   ko'pincha   rekursiv   ravishda   ajralib   chiqadi.   Xuddi   shu   tarzda,
informatika   fanida,   agar   muammoni   kichik   muammolarga   ajratib,   so'ngra   kichik
muammolarning optimal echimlarini rekursiv ravishda topish orqali optimal tarzda
echimlarni olish mumkin bo’ladi. 
Agar   kichik   masalalarni   rekursiv   ravishda   kattaroq   masalalar   ichiga   joylashtirish
mumkin   bo'lsa,   shuning   uchun   dinamik   dasturlash   usullari   qo'llanilishi   mumkin
bo'lsa,  unda kattaroq masalaning qiymati  bilan kichik muammolarning qiymatlari
o'rtasida   bog'liqlik   mavjud. [1]
  Optimallashtirish   bo'yicha   adabiyotda   bu
munosabatlar Bellman tenglamalarida keltrilgan. 
Kompyuter dasturlash usuli
Dinamik   dasturlash   uchun   muammo   yuzaga   kelishi   kerak   bo'lgan   ikkita   asosiy
xususiyat   mavjud:   maqbul     tuzulish   muammolar   va   bir   birini   qoplaydigan   kichik
jarayonlar.   Agar   muammoni   optimal   echimlarni   birlashtirib   hal   qilish   mumkin
bo'lsa   bir-birining   ustiga   chiqmaydigan   kichik   muammolar,   strategiya   "deb
nomlangan   “bo’lib   tashla   va   hukumronlik   qil”o'rniga.Shuning   uchun   birlashtrish
va teskor tartiblash   dinamik dasturlash muammolari deb tasniflanmagan.
Optimal pastki tuzilish   ma'lum bir optimallashtirish muammosining echimini uning
quyi   masalalariga   optimal   echimlarni   birlashtirish   orqali   olish   mumkinligini
anglatadi.   Bunday   maqbul   pastki   tuzilmalar   odatda   rekursiya .   Masalan,   grafik
berilgan   G = (V, E) , eng qisqa yo'l   p   tepadan   siz   tepaga   v   maqbul pastki  tuzilishni
namoyish   etadi:   har   qanday   oraliq   tepalikni   oling   w   bu   eng   qisqa   yo'lda   p .
8 Agar   p   haqiqatan   ham   eng   qisqa   yo'l,   keyin   uni   pastki   yo'llarga   bo'lish
mumkin   p
1   dan   siz   ga   w   va   p
2   dan   w   ga   v   Shunday   qilib,   bular,   albatta,   mos
keladigan   tepalar   orasidagi   eng   qisqa   yo'llardir   (tasvirlangan   oddiy   va   kesilgan
argument  bo'yicha)Algoritmlarga kirish. Shunday qilib, rekursiv usulda eng qisqa
yo'llarni   topish   uchun   echimni   osongina   shakllantirish   mumkin,   bu   esa   Bellman-
Ford algoritmi   yoki Froyd-Uorshall algoritmi   qiladi.
  Kichik masalalar kichik masalalar maydoni kichik bo'lishi kerakligini anglatadi, 
ya'ni har qanday rekursiv algoritm yangi kichik muammolarni yaratishdan ko'ra bir
 quyidagi ikki usuldan biri bilan erishish mumkin.
Yuqoridan pastga yondashish. Bu har qanday muammoning rekursiv formulasidan 
to'g'ridan-to'g'ri tushish. Agar biron-bir muammoning echimi uning kichik 
muammolari echimi yordamida rekursiv tarzda tuzilishi mumkin bo'lsa va agar 
uning pastki muammolari bir-birining ustiga chiqsa, unda osonlikcha xotirada 
saqlab qolish   yoki pastki muammolarning echimlarini jadvalda saqlash mumkin. 
Har doim yangi kichik masalani echishga urinayotganimizda, avval jadvalni 
allaqachon echilganligini tekshirib ko'ramiz. Agar echim yozib olingan bo'lsa, biz 
uni to'g'ridan-to'g'ri ishlatishimiz mumkin, aks holda kichik masalani echamiz va 
uning echimini jadvalga qo'shamiz.
Pastdan yuqoriga qarab yondashuv. Agar muammoning echimini uning pastki 
muammolari nuqtai nazaridan retsursiv ravishda tuzgan bo'lsak, biz muammoni 
pastdan yuqoriga qarab qayta isloh qilishimiz mumkin: avval kichik muammolarni 
echishga urinib ko'ring va ularning echimlaridan foydalanish uchun kattaroq kichik
muammolarni hal qilish. Bu, odatda, jadval shaklida, kichik kichik muammolarga 
echimlardan foydalangan holda, katta va kattaroq kichik muammolarga echimlarni 
yaratish orqali amalga oshiriladi. Masalan,  F
41   va   F
40 , ning qiymatlarini allaqachon 
bilsak    biz  F
42   ning qiymatini to'g'ridan-to'g'ri qiymatini hisoblashimiz mumkin   .
Dinamik dasturlashda optimal  quyi tuzilma asl  masalani  yechish uchun kichikroq
kichik   muammolarning   optimal   yechimidan   foydalanish   mumkinligini   bildiradi.
Masalan,   grafikdagi   eng   qisqa   yo‘lni   bir   cho‘qqidan   (s   ni   belgilang)   ikkinchi
cho‘qqiga (tni belgilang) quyidagicha topish mumkin: avval s ga tutashgan barcha
9 cho‘qqilardan   t   gacha   bo‘lgan   eng   qisqa   yo‘lni   hisoblaymiz,   so‘ngra   ni   hisobga
olgan holda eng qisqa yo‘lni hisoblaymiz. s ni qo'shni cho'qqilar bilan bog'laydigan
qirralarning   og'irliklari,   t   ga   eng   yaxshi   yo'lni   tanlang   (qaysi   cho'qqidan   o'tish
yaxshiroq).   Umuman   olganda,   biz   quyidagi   uchta   qadamni   bajarib,   optimal   quyi
tuzilma bilan muammoni hal qilishimiz mumkin.
Vazifani   kichikroq   kichik   vazifalarga   bo'lish.Xuddi   shu   uch   bosqichli   algoritmga
amal   qilgan   holda   rekursiv   usulda   kichik   muammolarning   optimal   yechimini
topish.
Olingan   kichik   masalalar   yechimidan   foydalanib,   dastlabki   masala   yechimini
qurish.
Voqealarning   bunday   rivojiga   yo'l   qo'ymaslik   uchun   biz   allaqachon   hal   qilgan
kichik   muammolarning   echimlarini   saqlab   qo'yamiz   va   bizga   yana   kichik
muammoning   echimi   kerak   bo'lganda,   uni   qayta   hisoblash   o'rniga,   biz   uni
shunchaki xotiradan olib tashlaymiz. Bunday yondashuv memoizatsiya deb ataladi.
Qo'shimcha   optimallashtirishlar   amalga   oshirilishi   mumkin   -   masalan,   agar   biz
quyi vazifaga yechim kerak emasligiga ishonchimiz komil bo'lsa, biz uni xotiradan
chiqarib   tashlashimiz,   boshqa   ehtiyojlar   uchun   bo'shatishimiz   yoki   protsessor
ishlamayotgan bo'lsa va biz bu yechimni bilamiz. Ba'zi hali hisoblanmagan kichik
vazifalardan keyin bizga kerak bo'ladi, biz ularni oldindan hal qilishimiz mumkin.
Yuqoridagilarni umumlashtirib, shuni aytishimiz mumkinki, dinamik dasturlash 
muammoning quyidagi xususiyatlaridan foydalanadi:bir-biriga moskeladigan 
kichik vazifalar;optimal quyi tuzilma;tez-tez duch keladigan kichik vazifalarning 
echimlarini yodlash qobiliyati.
Dinamik dasturlash odatda muammolarni hal qilishda ikkita yondashuvni qo'llaydi:
Yuqoridan   pastga   dinamik   dasturlash:   muammo   kichikroq   kichik   muammolarga
bo'linadi, ular hal qilinadi va keyin asl muammoni hal qilish uchun birlashtiriladi.
Yodlash allaqachon hal qilingan kichik vazifalarni hal qilish uchun ishlatiladi.
Pastdan yuqoriga dinamik dasturlash: asl muammoni hal qilish uchun keyinchalik
zarur   bo'lgan   barcha   kichik   vazifalar   oldindan   hisoblab   chiqiladi   va   keyin   asl
muammoning   echimini   yaratish   uchun   ishlatiladi.   Bu   usul   kerakli   stekning
10 o'lchami   va   funksiya   chaqiruvlari   soni   bo'yicha   yuqoridan   pastga   dasturlashdan
ko'ra   yaxshiroqdir,   lekin   ba'zida   kelajakda   qaysi   kichik   muammolarni   hal
qilishimiz kerakligini oldindan aniqlash oson emas.
 dinamik dasturlash muammolari uchun bosqichma-bosqich algoritm
bizda Z funksiyaning natijasidir.
Jami Z (x) = y, bu erda x - kirish parametrlari, y - kirish parametrlari x bo'yicha 
masala yechimi.
2. X ning kichik va izchil qiymatlari uchun muammoning yechimi qanday 
ishlashini ko'ring. Ya'ni, hisoblash miqdori kichik bo'lgan hollarda.
"Qarang" deganda men tom ma'noda aytmoqchiman - barcha natijalarni (va ular 
qanday paydo bo'lganligini) yozing va barcha echimlarni o'z ko'zingiz bilan ko'rib 
chiqing.
Misol uchun, agar siz x ning natural sonlarning qiymatlarini olishi mumkinligini 
bilsangiz, funktsiya natijalarini olamiz:
Z (1) = y_1
Z (2) = y_2
Z (3) = y_3
Z (4) = y_4
Z (5) = y_5
Agar x qandaydir massiv bo'lsa, u holda Z funksiyasi turli xil kichik massivlar 
bilan orasidagi bog’liqlikni tekshiramiz:
Z ([1, 2, 3]) = y1
Z ([4, 5]) = y2
Z ([1, 5, 4]) = y3
Bu erda massiv elementlari  talablarga javob berishi kerak (masalan, tabiiy yoki 
ijobiy va oqilona sizning aniq vazifangizga bog'liq).
Va bu juda muhim, hisoblash natijalarida bog’liqlik mavjudligini tekshiramiz. 
Ya'ni, y_5 y_4 yoki y_2 ga bog'liq bo'lishi mumkin. Yoki y_3 ni hisoblashda 
11 olingan ma'lumotlardan y_5 ni hisoblashda foydalanish mumkin. Masalan, 
Fibonachchi raqamlarida F (5) F (3) va F (4) ga bog'liq.
Turli xil hisob-kitoblarning natijalari o'rtasida to'g'ridan-to'g'ri bog'liqlik bo'lmagan
holatlar mavjud. 
Agar   biz   Fibonachchi   raqamlari   bilan   misol   olsak,   bu   ba'zi   qiymatlarni   echish
jarayonida xotirada saqlash  osonroq bo'ladi  va har safar qayta hisoblanmaydi. Va
bu shunchaki xotira bo'ladi.
N   +   1   uchun   muammoning   echimini   N   uchun   yechimdan   olish   mumkin   bo'lgan
misollarda,   echimni   olish   paytida   o'zgaruvchilarning   holati   (indekslar,
ko'rsatkichlar) xotirada saqlanishi kerak bo'ladi. N.
Oddiy misol qatorni Fibonachchi raqamlari bilan tsikl orqali to'ldirishdir.
(arr [i] = arr [[i-1] + arr [i-2]. arr [i] ni hisoblash vaqtida bizda arr [i-1] va arr [i-2]
uchun to'g'ri echimlar mavjud edi. ].)
Bir o'lchovli muammo uchun u quyidagicha ko'rinishi mumkin:
2-rasm Bir o'lchovli massivning saqlangan holatini tasvirlash
Dinamik dasturlash   asosan oddiy rekursiya bilan solishtirganda 
optimallashtirishdir.   Asosiy g'oya - asl savolni takrorlanadigan naqshlarga bo'lish 
va keyin   natijalarni ko'p sub-javoblarni saqlash   .   Shuning uchun,   kerak bo'lganda   , 
biz   bosqichdan oldingi javoblarni keyinroq   qayta hisoblashimiz shart   emas   .   Katta 
O nuqtai nazaridan, ushbu optimallashtirish usuli odatda vaqt murakkabligini 
eksponensialdan polinomga qisqartiradi.
12 1. Rekursiya ham, dinamik dasturlash ham boshlang'ichni ishga tushiradigan asosiy 
holatdan boshlanadi.
2. Asosiy holatni yozganimizdan so'ng, muammoning mantiqiy oqimidan keyin 
har qanday naqshlarni topishga harakat qilamiz.   Uni topganimizdan so'ng, biz 
asosan tugatdik.
3. Asosiy farq shundaki, rekursiya uchun biz   hech qanday oraliq qiymatlarni  
saqlamaymiz   , dinamik dasturlash esa undan foydalanadi.
 Fibonachchi raqami python dasturlash tilida ko’rib chiqaylik
3-rasm fibonachchi sonlarining  dynamik dasturlashdagi rekursiv algoritmi
Rekursiya   uchun   vaqt   murakkabligi   O(2^n)   bo'ladi,   chunki   har   bir   tugun   ikkita
kichik   tarmoqqa   bo'linadi   va   fazoning   murakkabligi   O   (N)   bo'ladi,   chunki
13 daraxtning   chuqurligi   n   o'lchamiga   mutanosib   bo'ladi.Dinamik   dasturlash   uchun
vaqt   murakkabligi   O(n)   bo'ladi,   chunki   biz   uni   faqat   bir   marta
aylantiramiz.   Dinamik   dasturlash   protsedurasi   diagrammasida   ko'rib
turganingizdek, u chiziqli.Va kosmik murakkablik O(N) bo'ladi, chunki biz barcha
oraliq   qiymatlarni   dp_listimizga   saqlashimiz   kerak.   Shunday   qilib,   bizga   kerak
bo'lgan joy n berilgan bilan bir xil.
Dinamik dasturlash yondashuvi
 Rekursiya kodi
# DP time
complexit
y 
O(n),Spac
e O(n)
class   Solution (object):
     def   fib (self, n):
#int parameter sifatida qabul qiladi va int qaytarishi kerak
         """
        :type n: int
        :rtype: int
        """
         # base case
         if  n  ==   0 :
             return ( 0 )
         if  n  ==   1 :
             return ( 1 )
         #  bo’sh bo’lgan massiv yaratildi
        dp  =  [ 0 ]  *  (n  +   1 )
         # find patterns
        dp[ 0 ]  =   0
        dp[ 1 ]  =   1
        
         print ( "oldindan yaratilgan dinamik massiv= " , dp)
         # dp[2] = dp[1] + dp[0]
         # dp[i] = dp[i-1] + dp[i-2]
        
         for  i  in   range ( 2 ,n +1 ):
14              dp[i]  =  dp[i -1 ]  +  dp[i -2 ]
        
         print ( "to’ldrilgandan keyin dinamk massiv yaratiladi= 
" , dp)
        
         return (dp[n])
        
        
out  =   Solution (). fib (n)
rekursiya   bilan   alohida   dinamik   dasturlashning   asosiy
farqidir.   Rekursiyada   biz   dinamik   dasturlashda   oraliq
natijalarni   saqlamaymiz,   biz   barcha   oraliq   bosqichlarni
saqlaymiz.
F[4] ni hisoblash uchun biz avval F[2], F[3] ni hisoblab chiqamiz
va   ularning qiymatin i   oldindan tuzilgan   DP ro'yxatiga joylashtiramiz   .
Dinamik  dast urlash prot sedurasi sy ujet i
15 C++ dasturlash tilida dinamik dasturlar yaratish
C   ++   tilining   eng   katta   afzalliklaridan   biri   shundaki,   u   mashina   darajasidan
abstraktlash   paytida   yuqori   darajadagi   dasturlarni   yozish,   shu   bilan   birga   kerak
bo'lganda apparatga yaqin ishlash  imkoniyatini  ham beradi.   C ++ ilova ishlashini
bayt   va   bit   darajasida   sozlash   imkonini   beradi.   Ko'rsatkichlarning   qanday
ishlashini   tushunish   tizim   resurslaridan   samarali   foydalanadigan   dasturlarni
yozishni o'rganish bosqichlaridan biridir.
Ko’rsatkichlar.   Ko’rsatkich   –   bu   maydon   manzilini   xotirada   saqlaydigan
o'zgaruvchidir.   int   o'zgaruvchisi   butun   qiymatni   saqlash   uchun   ishlatilgandek,
ko'rsatgich   o'zgaruvchisi   xotira   maydoni   manzilini   saqlash   uchun   ishlatiladi   (1-
rasm).
  
Shunday qilib,  ko'rsatkich  o'zgaruvchidir va barcha  o'zgaruvchilar  singari u
ham xotiradan joy egallaydi (1-rasmda 0x101 manzilda). Ko'rsatkichlarni  maxsus
ko’rinishga   keltiradigan   xususiyat   shundaki,   ular   tarkibidagi   qiymatlar   (bu   holda,
160x101 manzilidagi 
ko'rsatkich 0x558 
qiymatini o'z ichiga 
oladi Xotiradagi 
ma'lumotlar 0x558 
manzilida 0x558) xotira maydonlarining manzillari sifatida talqin etiladi. Demak, ko'rsatkich
- bu xotiradagi maydonni ko'rsatadigan maxsus o'zgaruvchidir.
 
Ko'rsatkich boshqa barcha o'zgaruvchilar singari e'lon qilinishi kerak:
Tip_nomi * Ko’rsatkich nomi;
& adres olish amali.   O'zgaruvchilar - bu til tomonidan xotirada ma'lumotlar
bilan ishlashni ta'minlaydigan imkoniyat.
Agar   varName   o'zgaruvchi   bo'lsa,   &varName   uning   qiymati   saqlanadigan
xotira adres o’rnini qaytaradi. Shunday qilib, agar sintaksisdan foydalangan holda
butun o'zgaruvchini e'lon qilgan bo'lsangiz, sizga tanish bo'lgan
int age = 30;
u   holda   &age   ifodasi   belgilangan   qiymat   30   joylashtirilgan   xotira
maydonining manzilini qaytaradi.
#include <iostream>
using namespace std;
int main()
{
    int age = 30;
    const double Pi =3.1416;
int *a=&age;
const double *b-&Pi;
    cout <<"age manzili: "<<&age<<endl;
    cout<<”age qiymat=”<<*a<<endl;
    cout <<"Pi manzili: "<<&Pi<<endl;
   cout<<”Pi qiymati=”<<*b;
    return 0;
}
17 Statik ma’lumotlar bilan ishlasha quyidagi muammolar kelib chiqadi .
int Numbers[100]; //100 ta butun son uchun statik massiv.
1-muammo:  Bu   yerda   dasturimizning   imkoniyatlarini   chegaralaymiz,  chunki
u 100 dan ortiq raqamni saqlay olmaydi.
2-muammo:   Masalan,   faqat   1   ta   raqamni   saqlash   kerak   bo'lganda   va   100   ta
raqam uchun xotira ajratilganda resurslardan samarasiz foydalanyapmiz.
Ushbu   muammolarning   asosiy   sababi   kompilyator   tomonidan   massiv   uchun
statik bo’lgan, doimiy xotirani ajratishdir.
Dastur   foydalanuvchidan   o'ziga   xos   ehtiyojlariga   qarab   xotiradan   maqbul
foydalanishi   uchun   xotirani   dinamik   taqsimotidan   foydalanish   zarur.   Bu   sizga
kerak  bo'lganda   ko'proq   xotira   ajratish   va   kerak  bo'lmaganda   bo'shatish   imkonini
beradi.   C++   dasturida   xotiradan   foydalanishni   boshqarish   imkonini   beradigan
ikkita   operator,   new   va   delete   mavjud.   Xotira   manzillarini   saqlaydigan
ko'rsatkichlar   xotirani   samarali   dinamik   ravishda   taqsimlashda   hal   qiluvchi   rol
o'ynaydi.
Xotirani   ajratish   va   bo'shatish   uchun   new   va   delete   operatorlaridan
foydalanish
new   operatori   yangi   xotira   bloklarini   ajratish   uchun   ishlatiladi.   new
operatorining   eng   ko'p   ishlatiladigan   versiyasi,   u   muvaffaqiyat   haqida   so'ralgan
18 xotira   maydoniga   ko'rsatkichni   qaytaradi   va   aks   holda   istisno   qiladi.   new
operatoridan   foydalanishda   siz   xotira   ajratiladigan   ma'lumotlar   turini
ko'rsatishingiz kerak:
Tip* Ko’rsatkich  = new  Tip ; //Xotiraga bitta element uchun so’rov
Shuningdek, siz xotirani ajratmoqchi bo'lgan elementlar sonini belgilashingiz
mumkin (agar siz elementlar qatori uchun xotira ajratishingiz kerak bo'lsa):
Tip*   Ko’rsatkich   =   new   Tip   [Miqdor]   //   Belgilangan   elementlar   soni   uchun
xotirani so'rash
Shunday   qilib,   xotirada   butun   sonlarni   joylashtirish   kerak   bo'lsa,   quyidagi
koddan foydalanishimiz mumkin:
int* pointToAnInt = new int; //Butun songa ko’rsatkich
int*   pointToNums   =   new   int[10];   //10   ta   butun   sondan   iborat   massivga
ko’rsatkich
new operatori bilan ajratilgan har bir xotira maydoni tegishli delete operatori
tomonidan bo'shatilishi kerak: 
Tip *  Ko’rsatkich  = new  Tip ; 
Delete  Ko’rsatkich;
 
Bu   bir   nechta   element   uchun   xotira   ajratilganda   ham   shu   usul   yordamida
o’chirish mumkin:
Tip *  Ko’rsatkich  = new  Tip[Miqdor] ; 
19 Delete []  Ko’rsatkich;
Agar   siz   ajratilgan   xotirani   tugatgandan   so'ng   bo'shatmasangiz,   u   ajratilgan
bo'lib   qoladi   va   keyinchalik   sizning   yoki   boshqa   ilovalaringizga   ajratish   uchun
mavjud   bo'lmaydi.   Xotiraning   bunday   sarflanishi   hatto   dastur   yoki   umuman
kompyuter   ishini   sekinlashtirishi   mumkin   va   bunga   har   qanday   holatda   yo'l
qo'ymaslik kerak.
Quyidagi dasturda xotirani dinamik ajratish va taqsimlash ko'rsatilgan.
#include <iostream>
using namespace std;
int main()
{
   //int tipi uchun xotira ajratish
   int* pointsToAnAge = new int;
   //Ajratilgan xotiradan foydalanish
   cout<<"Yoshni kiriting: ";
   cin>> *pointsToAnAge;
   //* Ajratish operatorini qo'llash
      cout<<"Yosh   "<<   *pointsToAnAge<<"   "   <<hex<<pointsToAnAge<<"
adresida saqlanadi"<<endl;
   delete pointsToAnAge; //Xotirani bo'shatish
   
    return 0;
}
20 E'tibor   bering,   new   []   operatoridan   foydalangan   holda   bir   qator   elementlar
uchun xotirani ajratganda, quyidagi dasturda ko'rsatilgandek, uni delete [] operatori
yordamida bo'shatish kerak.
Statik   massivla r ning   kamchiliklari   shundaki ,   ularn i ng   o’lchamlari
oldindan   ma’lum   bo’lishi   ker ak ,   bundan   tashqari   bu   o’lchamlar
berilgan l arga   ajratilgan   xotira   se g mentining   o’lchami   bilan
chegaralangan .   I kkinchi   tomondan ,   yet a rlicha   katta   o’l cham d agi   massiv
e’lon   qilib ,   konkret   masala   yechilishida   ajrati l gan   xotira   to’liq
i sh latil m asli g i   mumkin .   Bu   kamchiliklar   dinamik   m a ssiv l ar - dan
foyda l anish   orqali   bartaraf   etiladi ,   chunki   ular   programma   ishla sh i
jarayonida   kerak   bo’lgan   o’lchamdagi   massi v larni   yaratish   va   zarurat
qolmag a nda   yo’qotish   imkoniyatini   beradi .
Dinam i k   m a ssivla r ga   xotira   ajratish   uchun   mall o c(),   calloc()
funksiyalaridan   yoki   n ew   operatoridan   foydala n ish   mumkin .   Dina - mik
obyektga   ajr a tilgan   xotirani   bo’shatish   uchun   free()   f unksi ya si   yoki
delete  operatori   ishlatiladi .
Yuqorida   qayd   q i li n gan   funksiyal a r   «allo c .h»   kutubxonasida
joylashgan .
mal l oc()  funk s iyasining   sintaksisi
void   *   ma l loc ( siz e _t   s ize ) ;
ko’rinishida   bo’lib ,   u   xotiraning   uyum   qismidan   size   bayt
o’lchamidagi   uzluksiz   sohani   ajratadi .   Agar   xotira   ajratish
muvaffaqiyatli   bo’lsa ,   malloc()   fun k siyasi   ajratilgan   sohaning   boshla n ish
ad re sini   qaytaradi .   T alab   qil i ngan   xotirani   ajratish   muvaffaqiyatsiz   bo’lsa ,
funksiya  NULL  qiymatini   qaytaradi .
Sintaksisdan   ko’rinib   turibdiki ,   f un k siya   void   t u ridagi   qiymat
q aytaradi .   Amalda   esa   konkret   tur d agi   obye k t   uchun   xotira   ajratish
zarur   bo’lad i .   Buning   uchun   void   turi n i   konkret   t u rga   keltirish
21 texnologiyasidan   foydalaniladi .   Mas a lan ,   butun   turdagi   uzunligi   3   ga
teng   massivga   joy   ajr a tishni   quyidagicha   amal g a   oshir i sh   mumkin :
int   *   pIn t =(i n t*) m al l oc( 3 *si z eof ( int ) );
call o c()   funksiyasi   mal l oc()   f u nksiya s idan   farqli   ravishda
massiv   u chun   j o y   ajratishdan   t ashqari   massiv   elementlari n i   0
qiymati   bilan   inisializasiya   qiladi .  B u   funks i ya   sintaksisi
void   *   ca l loc ( siz e _t   n um,   s ize _ t   s i ze);
ko’rinishda   bo’lib ,   num   parametri   ajratilgan   sohada   nechta   e le ment
borligini ,   size  har   bir   element   o’lchamini   bildira d i .
free ( )   xo t irani   bo’sh a tish   funksiyasi   o’chiriladigan   xotira   bo’la - gi g a
ko’rsatk i ch   bo’l g an   yag o na   parametrga   ega   bo’ladi :
Quyidagi   programmada     butun   sondan   iborat   dinamik   massiv   yaratish,   unga
qiymat berish va o’chirish amallari bajarilgan.
#include<iostream>
using namespace std;
int main(){
int  m;
cout << "m="; cin >> m; //massiv elementlari soni;
float *b = new float[m]; //Element haqiqiy sonlar bo'lgan m ta elementli dinamik massiv;
for (int j = 0; j < m; j++)
cin >> b[j]; // bir o'lchamli Massivni to'ldirish
cout<<"     bir o'lchamli dinamik massiv"<<endl;
for (int j = 0; j < m; j++)
cout<<b[j]<<" ";
delete [] b;//xotira bo'shatildi
cout<<"\n xotira bo'shatildi";
return 0;
}
Dastur natijasi
22 Dinamik ma’lumotlar tuzilmasi 
Statik ma’lumotlar tuzilmasi  vaqt o’tishi bilan o’z o’lchamini o’zgartirmaydi. Biz
har doim dastur kodidagi statik ma’lumotlar tuzilmasiga qarab ularning olchamini
bilishimiz   mumkin.   Bunday   ma’lumotlarga   teskari   ravishda   dinamik   ma’lumotlar
tuzilmasi   mavjud   bo’lib,   bunda   dastur   bajarilishi   davomida   dinamik   ma’lumotlar
tuzilmasi   o’lchamini   o’zgartirishi   mumkin.   Dinamik   ma’lumotlar   tuzilmasi   –   bu
qandaydir   bir   qonuniyatga   asoslanib   shakllangan,   lekin   elementlari   soni,   o’zaro
joylashuvi   va   o’zaro   aloqasi   dastur   bajarilishi   davomida   shu   qonuniyat   asosida
dinamik o’zgaruvchan bo’lgan ma’lumotlar tuzilmasidir.
Malumotlar   tuzilmasi   dasturlarda   ma’lumotlar   ajratish   usuli   bo’yicha
staticdinamikaga   bo’linadi.Statik   ma’lumotlar   tuzilmasi-bu   kompyuterning
xotirasida   joylashishi   va   elementlarning   o’zaro   aloqalari   ular   tomondan   amalga
oshiriladigan   soha   dasturini   bajarish   paytida   o’zgarishsiz   qoladigan
ma’lumotlardir.Statik strukturaning ma’lumotlariga dasturda elon qilingan asosiy
va   mahalliy   hamda   global   darajadagi   o’zgaruvchilar   kiradi.Dinamik   ma’lumotlar
tuzilmasi-bu   kompyuterning   xotirasiga   joylashtrilishi   va   NEW   va   DELETE   kabi
tizm protseduralari yordamida dasturni bajarishda xotiradan o’chirilishi mumkin
23 bo’lgan ma’lumotlar.
Dinamik ma’lumotlar tuzilmasi   o’zichiga malumotlar strukturasini   hosil qilishda
kerak bo’ladigan barcha tuzilma va texnologiyalarni qamrab oladi.
Bularga c++ dasturlash tilidagi STL(Standart template library),classlar,structuralar
Emun xizmachi so’zi bilan hosil qilingan malumot tuzilmalari,union( birlashmalar)
Ko’rsatkichlar va boshqalarni o’z ichiga oladi.
Dinamik ma’lumotlar tuzilmasi quyidagicha  klassifikatsiyalanadi.(3.1-rasm)
24 Dasturlarda dinamik ma’lumotlar tuzilmasidan kopincha chiziqli royhatlar, steklar,
navbatlar va binar daraxtlar ishlatiladi. Bu tuzilmalar bir-biridan elementlarning 
bog’lanish usuli va ular ustida bajarilishi mumkin bo’lgan amallari bilan 
farqlanadi. Dinamik tuzilmalar massiv va yozuvdan farqli ravishda operativ 
xotirada ketma-ket sohalarda joylashmaydi. Ixtiyoriy dinamik tuzilma elementi 2 
ta maydondan tashkil topadi: tuzilma tashkil etilishiga sabab bo’layotgan
informatsion maydon va elementlarning o’zaro aloqasini ta’minlovchi ko‘rsatkichli
maydon. Chiziqli ro’yhatlarda har bir element o’zidan keyingisi yoki oldingisi 
bilan ham bog’langan bo’lishi mumkin. Birinchi holatda, ya’ni elementlar o’zidan 
25 keyingi element bilan bog’langan bo’lsa, bunday ro’yhatga bir bog‘lamli ro‘yhat 
deyiladi. Agar har bir element o’zidan oldingi va o’zidan keyingi element bilan 
bog’langan bo’lsa, u holda bunday ro’yhatlarga 2 bog‘lamli ro‘yhatlar deyiladi. 
Agar oxirgi element birinchi element ko’rsatkichi bilan bog’langan bo’lsa, bunday 
ro’yhatga halqasimon ro‘yhat deyiladi. Ro’yhatning har bir elementi shu elementni
identifikatsiyalash uchun kalitga ega bo’ladi. Kalit odatda butun son yoki satr 
ko’rinishida ma’lumotlar maydonining bir qismi sifatida mavjud bo’ladi. 
Ro’yhatlar ustida quyidagi amallarni bajarish mumkin.
 - ro’yhatni shakllantirish (birinchi elementini yaratish); 
- ro’yhat oxiriga yangi element qo’shish;
 - berilgan kalitga mos elementni o’qish;
 - ro’yhatning ko’rsatilgan joyiga element qo’shish (berilgan kalitga mos 
elementdan oldin yoki keyin) 
- berilgan kalitga mos elementni o’chirish;
 - kalit bo’yicha ro’yhat elementlarini tartibga keltirish. 
Ro’yhatlar bilan ishlashda dasturda boshlang’ich elementni ko’rsatuvchi 
ko’rsatkich talab etiladi. Chiziqli bir bog’lamli ro’yhatlar ustida turli amallar 
bajarish algoritmlari va dasturlarini ko’rib chiqamiz.
Chiziqli bir tomonlama bog’langan ro’yhatlar
3.2-rasm. Chiziqli bir bog’lamli ro’yhatlar
Bir bog„lamli ro’yhat deb elementlarning shunday tartiblangan ketma-ketligiga 
aytiladiki, har bir element 2 ta maydonga: informatsion maydon info va ko’rsatkich
maydoni ptr ga ega bo’ladi (3.2-rasm). Mazkur ko’rinishdagi ro’yhat elementi 
ko’rsatkichining o’ziga xosligi shundan iboratki, u faqatgina ro’yhatning 
26 navbatdagi (o’zidan keyin keluvchi) elementi adresini ko’rsatadi. Bir tomonlama 
yo’naltirilgan ro’yhatda eng so’ngi element ko’rsatkichi bo’sh, ya’ni NULL 
bo’ladi. Lst – ro’yhat boshi ko’rsatkichi. U ro’yhatni yagona bir butun sifatida 
ifodalaydi. Ba’zan ro’yhat bo’sh bo’lishi ham mumkin, ya’ni ro’yhatda bitta ham 
element bo’lmasligi mumkin. Bu holda lst = NULL bo’ladi. Hozir chiziqli bir 
bog’lamli ro’yhat hosil qilish dasturini ko’rib chiqsak. Buning uchun biz 
foydalanuvchi tomonidan yaratiladigan nostandart toifa yaratib olishimiz kerak. 
Buning bir qancha usullari mavjud, ya’ni klasslar yoki strukturalar bilan amalga 
oshirish mumkin. 
Masalan:
class Node{
 public://klass ma’lumotlariga tashqaridan bo‘ladigan murojaatga ruxsat berish 
int info; // informatsion maydon
 Node* next;// ko‘rsatkichli maydon 
};
 Bu yerda biz Node nomli toifa yaratdik va ro’yhatimiz butun sonlardan iborat. 
Endi ro’yhat elementlarini shu toifa orqali e’lon qilsak bo’ladi, ya’ni 
Node *lst = NULL;// ro‘yhat boshi ko‘rsatkichi
 Node *last = NULL;// ro‘yhatga oxirgi kelib tushgan elementning ko‘rsatkichi 
Endi shu belgilashlar orqali ro„yhat hosil qilamiz. 
Node * p = new Node; 
int numb = -1;
 cout<<"son kiriting: "; cin>>numb
p->info = numb; 
p->next = NULL; 
27 if (lst == NULL) {
 lst = p; last = p;
 } else{
 last->next = p; last = p;
 } Bu dasturda yangi element ro’yhat oxiridan kelib qo’shiladi.
Bir bog’lamli ro’yhatlar ustida amallar bajarish algoritmlari
1. Bir bog’lamli ro’yhat boshiga element qo’yish
3.3-rasm. Bir bog’lamli chiziqli ro’yhat tuzilishi 3.3-rasmdagi ro’yhat 
boshiga informatsion maydoni D o’zgaruvchi bolgan element qo’yamiz. 
Ushbu ishni amalga oshirish uchun quyidagi amallarni bajarish lozim 
bo’ladi: 
a) p ko’rsatkich murojaat qiladigan, bo’sh element yaratish (3.4-rasm).
          
b) Yaratilgan element informatsion maydoniga D o’zgaruvchi qiymatini 
o’zlashtirish (3.5-rasm)
28 c) Yangi elementni ro’yhat bilan bog’lash: p->ptr=lst; (shu holatda yangi element 
va lst – ro’yhat boshini ko’rsatyapti) 
d) lst ko’rsatkichni ro’yhat boshiga ko’chirish (3.6-rasm). lst=p; 
Va nihoyat:
Endi shu algoritmni C++ tilidagi realizatsiyasini ko’rib chiqamiz. 
Node * p = new Node;
 int numb = -1; 
cout<<"son kiriting: "; cin>>numb; 
p->info = numb; 
if (lst ==NULL){ 
p->next = NULL;
 lst = p;
 } else{ 
p->next = lst; lst = p;
}
2. Bir bog’lamli ro’yhat boshidan elementni o’chirish
 Ro’yhatda birinchi element info informatsion maydonidagi ma’lumotni esda
saqlab qolib uni ro’yhatdan o’chiramiz (3.7-rasm)
29 Yuqorida aytilganlarni amalga oshirish uchun quyidagi ishlarni bajarish 
lozim:
 a) o’chirilayotgan elementni ko’rsatuvchi p ko’rsatkich kiritish: p=lst; 
b) p ko’rsatkich ko’rsatayotgan element info maydonini qandaydir x 
o’zgaruvchida saqlash: x=p->info; 
c) lst ko’rsatkichni yangi ro’yhat boshiga ko„chirish: lst=p->ptr;
 d) p ko’rsatkich ko’rsatayotgan elementni o’chirish: delete(p); 
Natijada 3.8-rasmdagi ko’rinishga ega bo’lamiz.
Endi shu algoritmni C++ tilidagi realizatsiyasini ko’rib chiqsak.
 Node* p = new Node; 
if (lst == NULL){
 cout<<"ro'yhat bo'sh"; 
system("pause"); 
system("CLS"); } else { 
p = lst; lst = p->next ; delete(p);
 }
30 3. Elementni ro’yhatga qo’shish 
Berilgan ro’yhatda p ko’rsatkich ko’rsatayotgan elementdan keyin 
informatsion maydoni x bo’lgan elementni qo’yamiz (3.9-rasm).
          
Aytilganlarni amalga oshirish uchun quyidagi amallarni bajarish lozim: 
a) q ko’rsatkich ko’rsatuvchi bo’sh elementni yaratish: Node *q=new Node;
 b) Yaratilgan element informatsion maydoniga x ni kiritish: q->info=x; 
c) q elementni p elementdan keyingi element bilan bog’lash. q->ptr=p->ptr – 
yaratilgan element ko’rsatkichiga p element ko’rsatkichini o’zlashtirish. 
d) p element bilan q elementni bog„lash. p->ptr=q – bu amal p elementdan keyingi 
element q ko’rsatkich murojaat qilgan element bo’lishini anglatadi. Natijada 
quyidagi rasmdagidek ko’rinishga ega bo’lamiz.
Endi shu algoritmni C++ tilidagi realizatsiyasini ko’rib chiqsak.
 Node * p = lst;
 Node * q = new Node; 
31 int numb = -1; 
cout<<"son kiriting: "; cin>>numb; 
q->number = numb;
 int k;
 cout<<"nechta elementdan keyin kiritasiz k=";cin>>k;
for(int i=0;i<k-1;i++)
p=p->next;
q->next=p->next;
p->next=q;
4. Bir bog’lamli ro’yhatdan elementni o’chirish 
Ro’yhatda p ko’rsatkich ko’rsatayotgan elementdan keyingi elementni 
o’chiramiz (3.11-rasm).
Buni bajarish uchun quyidagi ishlarni amalga oshirish lozim:
 a) O’chirilayotgan elementni ko’rsatuvchi q ko’rsatkichni kiritish. q=p->ptr; 
b) p elementni q elementdan keyingi element bilan bog’lash. p->ptr=q->ptr;
 c) O’chirilayotgan element info maydonidagi informatsiyani yodda saqlash 
(agar zarur bo’lsa) k=q->info;
 d) q ko’rsatkich ko’rsatayotgan elementni o’chirish. delete(q) 
Natijada ro’yhat quyidagi ko’rinishga ega bo’ladi:
32 Shu algoritm dasturi
Node* p = lst;
 Node* q = new Node;
 int k; 
cout<<"k=";cin>>k; 
for(int i=0;i<k-1;i++)
p=p->next;q = p->next; 
p->next = q->next;
 delete(q); 
Dastur quyidagicha ishlaydi
1. Ekranga menyu chiqaramiz: 
1 - element qo’shish;
 2 - ro’yhatni ko’rish;
 3 - ro’yhat maksimalini topish;
 0 - chiqish;
 tanlash uchun tanla o’zgaruvchisiga qiymat so’raymiz.
 2-qadamga o’tish.
2. Agar tanlang=1 bo’lsa,
 3-qadamga, 2 ga teng bo’lsa, 4-qadamga, 3 tanlansa, 6-qadamga o’tish, 0 
tanlansa dasturni yakunlash. 
3. Navbatdagi elementni yaratish p; (p ning info maydoniga qiymat so’rab 
olib yozish va ptr maydoniga NULL yozish) Agar ro’yhat boshi ko’rsatkichi
33 lst=NULL bo lsa, lst=p va last=p; aks holda last – ro’yhat oxirgi elementi ‟
ptr maydoniga p ni yozib, p elementni last qilib belgilaymiz. 
1-qadamga o’tamiz. 
Agar lst NULL ga teng bo’lsa, ro’yhat bo’shligini ekranga chiqarib, 
1-qadamga o’tish. Aks holda, p=lst va 5-qadamga o’tish. 
Agar p ning ptr maydoni NULL bo’lmasa, p ning info maydonini ekranga 
chiqaramiz va keyingi elementga o’tamiz, ya’ni p=p->ptr, 
5-qadamga o’tamiz, aks holda, 1-qadamga o’tamiz. 
5. max=lst->info, ya’ni max o zgaruvchisiga ro’yhat 1-elementi info maydoni 	
‟
qiymatini o’zlashtiramiz. p=lst va 7-qadamga o’tish.
6. Agar p NULL ga teng bo’lmasa, 8-qadamga o’tamiz, aks holda max ni 
ekranga chiqaramiz va 1-qadamga o’tamiz. 8. Agar max< p->info bo’lsa, 
max=p->info. Keyingi elementga o’tamiz, ya’ni p=p->ptr. 7-qadamga 
o’tamiz.
                      Dasturning umumiy ko’rinishi
#include <iostream>
using namespace std;
class Node{
public: int number;
 Node* next;
};
int main()
{ Node* head = NULL;
 Node* lastPtr = NULL;
34  short action = -1;
 cout<<"                          Dinamik ro'yhat ustida bajariladigan 
amallar"<<endl;
 while (1)
 { 
 cout<<"1. ruyhatga element qo'shish\n";
 cout<<"2. ro'yhatni ko'rish\n";
 cout<<"3. royhatdan maksimalini topish\n";
 cout<<"0. chiqish\n\n";
 cout<<"tanlang: ";
 cin>>action;
 if (action == 0) {
 system("CLS");
 break;}
 if (action == 1)
 { system("CLS");
 Node* ptr = new Node;
 int numb = -1;
 cout<<"son kiriting: ";
 cin>>numb;
 ptr->number = numb;
 ptr->next = NULL;
 if (head == 0)
35  { head = ptr;
 lastPtr = ptr;
 system("CLS");
 continue;
 }
 lastPtr->next = ptr;
 lastPtr = ptr;
 system("CLS");
 continue;
 }
 if (action == 2){
 Node* ptr = NULL;
 system("CLS");
 if (head == 0)
 { cout<<"\t!!! ro’yhat bo’sh !!!\n\n";
 system("PAUSE");
 system("CLS");
 continue;
 }
 cout<<"* * * * * ruyhat * * * * *\n\n";
 ptr = head;
 while (1) {
36  cout<<ptr->number<<" ";
 if (ptr->next == 0) break;
 
ptr = ptr->next;
 }
 cout<<"\n\n";
 system("PAUSE");
 system("CLS");
 continue;
 }
 if (action == 3)
 {
 system("CLS");
 Node* p = head;
 Node* q = new Node;
 Node* last = new Node;
 int max=p->number; q=head;
 while(p){
 if(max<p->number){ max=p->number;}
 p=p->next;
 }
 system("CLS");
 cout<<"max="<<max<<endl;
37  system("pause");
 continue;
 }
}}
Dastur bosh oynasi
1-menuni 6 marta tanlab qiymatlarni kiritib quyidagi natijalarni olamiz
2.Ro’yhatni ko’rish bo’limi
3.maksimal elementini topish
 Xulosa
38 Dinamik   dasturlash   Ikkala   kontekstda   u   murakkab   muammoni     oddiy   kichik
muammolarga ajratish orqali soddalashtirishga ishora qiladi   rekursiv   uslubi. Qaror
bilan   bog'liq   ba'zi   muammolarni   shu   tarzda   ajratib   bo'lmaydigan   bo'lsa-da,   bir
necha vaqtni o'z ichiga olgan qarorlar ko'pincha rekursiv ravishda ajralib chiqadi.
Xuddi   shu   tarzda,   informatika   fanida,   agar   muammoni   kichik   muammolarga
ajratib,   so'ngra   kichik   muammolarning   optimal   echimlarini   rekursiv   ravishda
topish orqali optimal tarzda echimlarni olish mumkin bo’ladi. 
Agar   kichik   masalalarni   rekursiv   ravishda   kattaroq   masalalar   ichiga   joylashtirish
mumkin   bo'lsa,   shuning   uchun   dinamik   dasturlash   usullari   qo'llanilishi   mumkin
bo'lsa,  unda kattaroq masalaning qiymati  bilan kichik muammolarning qiymatlari
o'rtasida   bog'liqlik   mavjud. [1]
  Optimallashtirish   bo ' yicha   adabiyotda   bu
munosabatlar   muhim   o ’ rin   tutadi .
Dinamik   dasturlasning   ahamiyati   shundan   iboratki   biz   faqat   bir   xil   ma ’ lumotlar
bilan   emas   balki   vaqt   o ’ tishi   bilan   yangilanib   turadigan   ma ’ lumotlar   bilan
ishlashda   kata   ahamiyatga   egadi . Ushbu   kurs   ishimda   dinamik   dasturlashning
umumiy   tushunchalari   , dinamik   dasturlashning   tamoyillar , dinamik   dasturlashning
ma ’ lumotlar   tuzilmasdagi   o ’ rni , c ++   dasturlash   tilida   dinamik   dasturlashning
qo ’ llanilishi   haqida   ma ’ lumotlar   keltirganman .
Bu   kurs   ishidan   akademik   litseylarda,kollejlarda,oliy   ta’lim   muassasalarida
alogritmlar   va   ma’lumotlar   strukturasi   fanidan   qo’llanma   sifatida   foydalansa
bo’ladi.
39 Foydalanilgan adabiyolar
1. M.O‘. ASHUROV, SH.A.SATTAROVA, SH.U.USMONQULOV,  
“ALGORITMLAR” ,  «Fan va texnologiya» nashriyoti, 2018.
2. H.To’rayev,“Kombinatorika va graflar nazariyasi”, “Ilm ziyo”, 2009 ,
3. Akbaraliyev B.B., Yusupova Z.Dj.  ,  “MA LUMOTLAR TUZILMASI VA ‟
ALGORITMLAR”, Toshkent 2013
4. Toirov Sh.A., Raximov R.T., Karimov M.M ,” “ALGORITMGA KIRISH” 
fanidan laboratoriya ishlarini bajarish bo’yicha USLUBIY KO’RSATMA”, 
Samarqand 2015,
5. Xayitmatov O’.T., Inogomjonov E.E., Sharipov B.A., Ro’zmetova N., 
Rahimboboeva D,” MA'LUMOTLAR TUZILMASI VA 
ALGORITMLARI”, Toshkent – 2011
6. Л.И.Домнин, “ЭЛИМЕНТЫ ТЕОРИИ ГРАФОВ” ,  “ Пенза Издательство 
Пензенского государственного университета“ ,2007
7. Никлаус Вирт ,”Алгоритмы и структуры данных Новая версия для 
Оберона + CD “,  Москва, 2010.
Foydalanilgan internet saytlar:
1) https://kursovik.com/programming/320372.html   
2) http://aliev.me/runestone/Graphs/PrimsSpanningTreeAlgorithm.html   
3) http://www.hpcc.unn.ru/?dir=836   
4) https://brestprog.by/topics/mst/   
5) wikipedia   
6) https://evileg.com/ru/post/524/   
7) http://www.mkurnosov.net/   
8) www.fayllar .org   
40 41

“ALGORITM VA MA’LUMOTLAR STRUKTURASI” FANIDAN “ DINAMIK DASTURLASH METODLARINI OPTIMALLASHTIRISH USULLARI ” MAVZUSIDA TAYYORLAGAN SAMARQAND – 2021 1KU RS IS HI

Mundarija I Kirish II Asosiy qism ……..………………………………………………..4 2.1. Dinamik dasturlash haqida umumiy tushunchalar……….…......4 2.2.Dinamik dasturlashda optimallik tamoyili……………………....8 2.3. C++ dasturlash tilida dinamik dasturlar yaratish…….…..……..17 2.4. C++ dasaturlash tilida dinamik ma’lumotlar tuzilmasi……..….24 III Xulosa………………………………………………...…………39 IV Foydalanilgan adabiyotlar………………………………….……40 2

Kirish Vatanimizda, erkin va farovon hayot barpo etish, rivojlangan mamlakatlar qatoridan o’rin olish, demokratik jamiyat qurish kabi ezgu maqsadlarni qo’yildi. Bu esa kelajagimizni yaqqol tasavvur etish, jamiyatimizning ijtimoiy-ma‘naviy poydevorini mustahkamlash ehtiyojini tug’diradi. Demak, galdagi eng asosiy vazifa: yosh avlodni vatan ravnaqi, yurt tinchligi, xalq farovonligi kabi olijanob tuyg’ular ruhida tarbiyalash, yuksak fazilatlarga ega, ezgu g’oyalar bilan qurollangan komil insonlarni voyaga etkazish, jahon andozalariga mos, kuchli bilimli, raqobatbardosh kadrlar tayyorlashdir. O’zbekistonning iqtisodiy va ijtimoiy sohalarda yuqori natijalarga erishishi, jahon iqtisodiy tizimida to’laqonli sheriklik o’rnini egallay borishi, inson faoliyatining barcha jabhalarida zamonaviy axborot texnologiyalaridan yuqori darajada foydalanishning ko’lamlari qanday bo’lishiga hamda bu texnologiyalar ijtimoiy mehnat samaradorligini oshishida qanday rol o’ynashiga bog’liq. Keyingi yillarda mamlakatimiz ilm-fani ham axborotlashtirishning nazariy asoslariga katta hissa qo‗shib kelmoqda, shu bilan birgalikda, hodisalar, jarayonlarni yagona axborot asosida tadqiq etishning ilmiy yo’nalishlarini tahlil va sintez qilish natijasi bo’lgan fan-informatikaning vujudga kelishiga boshlang’ich poydevor qo’yildi. Axborot, energiya, vazn, bo’shliq va vaqtni bir butun holda batafsil o’rganish hozirgi vaqtda inson hayotining barcha jabhalarida muhim axamiyatga ega bo’lib qolmoqda. 3

Dinamik dasturlash haqida umumiy tushunchalar Dinamik dasturlash tushunchasi juda keng qamrovli tushuncha bolib,Bu tushunchao’z ichiga ko’plab yo’nalishlar va sohalarni qamrab oladi. Dasturchilar butunlay boshqacha vazifalarga ega bo'lishi mumkin. Bir holatda, biror narsani chizish uchun faqat belgilash tilidan foydalanishingiz kerak, ikkinchisida protsessor samarali ishlashi uchun assembler orqali ko'rsatmalar yozis kerak.Ammo bu assotsiatsiya barcha odamlar uchun ishlaydi - dasturchilar algoritmlarni ishlab chiqadilar. Tasavvur qilaylik, bizga yangi vazifa qo’yildi, uning maqsadi va cheklovlari bor. Har qanday vazifada bo'lgani kabi, u ham ma'lumotlar tuzilmalarini va tizimning boshqa qismlariga bog'liqlikni o'z ichiga oladi za bir vaqtning o'zida siz ushbu vazifa uchun ishlash muhim. Bunidarhol tushunish mumkin. Masalan, avval muammoni hal qilgandan keyin yechim sekin ekanligini payqashimiz mumkin .Bunday holatda hisob-kitob natijalari kamroq vaqt ichida olinishi uchun muammoni qanday hal qilishni kerak. Dasturlash nuqtayi nazaridan dinamik dasturlash atamasi biz yaratayotgan dasturmizga ma’lumotlarni kirtganimizdak keyin vaqt o’tishi bilan avvalgi kiritgan ma’lumotlarimizning bizga keragi bo’lmasligi mumkin.Shunda bizga malumotlarni kiritish va chiqarish jarayonida eski ma’lumotlarni o’chirish kerak bo’ladi. Dinamik dasturga misol C++ dasturlash tilida #include<iostream> using namespace std; int main(){ int m; cout << "m="; cin >> m; //massiv elementlari soni; float *b = new float[m]; //Element haqiqiy sonlar bo'lgan m ta elementli dinamik massiv; 4

for (int j = 0; j < m; j++) cin >> b[j]; // bir o'lchamli Massivni to'ldirish cout<<" bir o'lchamli dinamik massiv"<<endl; for (int j = 0; j < m; j++) cout<<b[j]<<" "; delete [] b;//xotira bo'shatildi cout<<"\n xotira bo'shatildi"; return 0; } Dinamik dastur Java dasturlash tilida class Array { private int arr[]; private int count; public Array(int length) { arr = new int[length]; } public void printArray() { for (int i = 0; i < count; i++) { // Print the elements of an array System.out.print(arr[i] + " "); } } public void insert(int element) { 5