Muhammad al-Xorazmiy nomidagi Toshkent axborot texnalogiyalari universiteti



Yüklə 71,82 Kb.
Pdf görüntüsü
tarix07.01.2024
ölçüsü71,82 Kb.
#202348
1-mustaqil ish



Muhammad al-Xorazmiy nomidagi
Toshkent axborot texnalogiyalari universiteti
Qarshi filiali “Kompyuter injiniringi” Fakulteti
KI-11-21S guruh talabasi Qudratov Shavkat
Ma’lumotlar tuzilmasi va algoritmlar 
1-MUSTAQIL ISH 


Reja; 
1.
Ma’lumotlar, algoritmlar va ma’lumotlar tuzilmasi 
tushunchalar 
2.
Ma’lumotlarni ifodalash bosqichlari, Ma’lumotlar toifalari. 
3.
Ma'lumotlar tuzilmalarining umumiy ko‘rinishlari. 
Ma’lumotlar tuzilmasi bu xotirada tashkil etiladigan elementlar 
yig’indisi bo’lib, ular ustida dastur yordamida amallar bajariladi.
Ma’lumotlar tuzilmasi – bu bironta toifaga tegishli bo’lgan va 
o’zaro ma’lum munosabatga ega bo’lgan elementlar to’plamiga 
aytiladi.
Ma’lumot – bironta qiymat yoki qiymatlar to’plami 
hisoblanadi.Misol uchun bu bironta eksperiment natijalari, yoki 
talabalarning imtixon ballari bo’lishi mumkin.
Ma’lumotlar tuzilmasi elementi – bu qiymatlar to’plamining bir 
bo’lagi hisoblanadi. Tuzilma elementi – qiymatlar jamlanmasi 
bo’lib, misol uchun talabalarning ismi, sharifi, yoshi har bir 
fandan olgan bahosi va x.k. larni keltirish mumkin.
Elementlar 2 taga bo’linishi mumkin: 
• 


Element sifatida ma’lumotlar guruhi olib qaraladi. Bunda 
e;lementlar yana qism bo’lak;arga bo’linishi mumkin. Masalan, 
ota-onalar maydoni talabalarning ota va onalari xaqida 
ma’lumot saqlaydigan alohida maydonlardan tashkil topadi.
• 
Elementar, ya’ni bo’linmas, bunda element qism bo’laklarga 
ajratilmaydi.
Ob’ekt – bu xususiyatlar va attributlariga ega bo’lgan va bu 
xususiyatlarga qiymat qabul qilishi mumkin bo’lgan tuzilma 
hisoblanadi. Masalan, talaba bu ob’ekt deb qaralishi mumkin 
tuzilma.
Maydon – bu ob’ektlarning attributlari yoki xususiyatlarini 
ifodalovchi tushuncha bo’lib, sonli yoki son bo’lmagan 
qiymatlarni o’zlashtirishi mumkin.
Yozuv – bu bironta ob’ektga tegishli turli toifadagi maydonlar 
to’plamidir.
Fayl- bu bir-biriga bog’liq bo’lgan yozuvlar to’plamidir. Masalan, 
barcha talabalar xaqidagi yozuvlarni o’z ichiga olishi mumkin,
Kalit – bu yozuvdagi maydon bo’lib, aynan shu yozuvni boshqa 
yozuvlardan ajratib turishga xizmat qiladi, uning qiymati boshqa 
yozuvlarda takrorlanmas hisoblanadi. Ba’zida bittadan ko’p 


maydonlar qiymatlari elementlararo betakror bo’lishi mumkin 
va bunga karrali kalit deyiladi. Ko’pincha asosiy kalit 
hisoblanadigan bitta maydon ma’lumoti ishlatiladi va u 
boshlang’ich kalit deyiladi, qolganlari esa alternativ kalit 
deyiladi. Ba’zida esa yozuvlaning yagona qiymatlatli kalit 
maydonni yo’qligi sababli kalit sifatida bir nechta maydonlar 
olinadi va ularga tarkibli kalit deyiladi. Eng yomon holatda, 
ba’zan shunaqa bo’lishi mumkinki, bironta maydon kalit bo’la 
olmasa, xar bit elementga qo’shimcha, qiymati yagona bo’lgan 
kalit maydon kiritiladi.
Axborot.Ko’pincha ma’lumot va axborot tushunchalarini bir xil 
ma’noda ishlatishadi. Lekin aslida esa axborot bu ma’lumotga 
qaraganda kengroq tushunchadir.Axborot bu qayta ishlangan 
ma’lumotdir.Ma’lumot esa qiymatlar yig’indisidir, yani bironta 
yakuniy xulosa bermaydi.Qaror qabul qilishda hali foyda 
bermaydi. Ma’lum qoidalar asosida qayta ishlangach, yangi 
hosil qilingan ma’lumotlar axborotga aylanadi va qaror qabul 
qilishda foydali hisoblanadi.
Ma’lumotlar toifasi – qandaydir qiymatlar yig’indisi bo’lib, ular 
ustida ma’lum amallar o’rinli bo’ladi. Ma’lumotlar toifalari 
dasturda oldindan aniqlangan yoki foydalanuvchi tomonidan 
aniqlangan bo’lishi mumkin va quyidagi aspektlarni nazarda 
tutadi.
1.
Qiymatlar to’plami
2.


Amallar to’plami
Misol uchun int - butun toifalar va ustida bajariladigan arifmetik 
amallar(+,-,*,/).
Ma’lumotlar toifalari 3 turga ajratiladi: 
1.
Primitiv (sozlangan) toifalar (ma’lumotlarning sodda toifalari). 
Oldindan ma’lum bo’ladigan, sozlangan toifalar deb ham 
ataladigan toifalar bo’lib, turli dasturlash tillarida turlicha 
bo’lishi mumkin. Masalan, C++ tilida int (long, short,… ), 
float(double), char,…
2.
Foydalanuvchi tomonidan aniqlanadigan toifalar, qachonki 
mavjud sozlangan toifalar qo’yilgan masalani yechishga yetarli 
bo’lmasa qo’llaniladi.
3.
Abstrakt toifalar. Ma’lumotlar toifalarining mantiqiy 
xususiyatlarini aniqlashda foydali instrument hisoblanadi. 
“Abstrakt toifa” atamasi bazaviy matematik tushunchasiga 
bog’liq. Ushbu toifalardagi ma’lumotlar qisman apparat va 
dasturiy ta’minot yordamida tuzilma sifatida fizik amalga 
oshirilishi mumkin. Biz abstrakt toifalarni matematik tushuncha 
sifatida aniqlaganimizda, muhit va vaqtiy munosabatlarni 
e’tiborga olmaymiz. Bular amalga oshirish masalalari 
hisoblanadi.


Ma’lumotlar tuzilmasi
Ma’lumotlar turli yo’lar asosida tashkil etilishi mumkin, 
mantiqiy yoki matematik modelni tashkil etilishi ma’lumotlar 
tuzilmasi deyiladi. Konkret bir ma’lumotlar tuzilmasini tanlash 
quyidagilarga bog’liq: 
• 
Real voqe’likda elementlararo munosabatni yaqqol ifodalay 
olishi kerak;
• 
U shunday soda tuzilishi kerakki, zarur bo’lganda ustida 
samarali amal bajarish mumkin bo’lsin.
Ma’lumotlar tuzilmasini o’rganish quyidagilardan iborat:
• 
Tuzilmani mantiqiy ifodalash;
• 
Tuzilmani fiizik amalga oshirish;
• 
Tuzilmani sifatiy taxlili, ya’ni elementlarni saqlash uchun qancha 
xotira xajmi sarflanishini aniqlash (xotira sarfi) va qayta 
ishlashga ketadigan vaqtni (vaqt sarfi) xisoblash nazarda 
tutiladi.


Vaqt sarfi.Tuzilma ustida amal bajarish algoritmini bajarilish 
vaqtini hisoblash ko’zda tutiladi.Buni hisoblashda mashxur katta 
“O” notatsiya tushunchasi ishlatiladi.
Xotira sarfi.Kirish ma’lumotlarini inobatga olmagan xolda, 
ishlatilayotgan algoritm uchun xotiradan talab qilinadigan 
qo’shimcha joy sarfi tushuniladi.Bunda xam katta “O” 
notatsiyasi qo‘llaniladi. 
Ma’lumotlar tuzilmasini asosiy ko‘rinishlari (turlari):
1) To‘plam - munosabat to‘plami bo‘sh R=0 bo‘lgan elementlar 
majmuasi. 
2) Ketma-ketlik – shunday abstrakt tuzilmaki, bunda R to‘plam 
faqatgina bitta chiziqli munosabatdan iborat (ya’ni, birinchi va 
ohirgi elementdan tashqari har bir element uchun o‘zidan oldin 
va keyin keladigan element mavjud.
3) Matritsa – shunday tuzilmaki, bunda R munosabatlar 
to‘plami ikkita chiziqli munosabatdan tashkil topgan bo‘ladi. 
4) Daraxt – bunda R to‘plam iyerarxik tartibdagi bitta 
munosabatdan tashkil topgan bo‘ladi.
5)Graf – bunda R munosabatlar to‘plami faqatgina bitta binar 
tartibli munosabatdan tashkil topgan bo‘ladi. 
6) Gipergraf – bu shunday ma’lumotlar tuzilmasiki, bunda R 
to‘plam ikki yoki undan ortiq turli tartibdagi munosabatlardan 
tashkil topgan bo‘ladi.
Foydalanuvchi dasturida va EHM hotirasida MT klassifikatsiya 
qilish 


MT klassifikatsiya qilishda asosiy belgi bu ma’lumotlar 
tuzilmasini dastur ishlashi mobaynida o‘zgarishi hisoblanadi. 
Masalan, agar dastur bajarilishi mobaynida elementlar soni 
va/yoki ular orasidagi munosabatlar o‘zgarsa, u holda bunday 
MT dinamik ma’lumotlar tuzilmasi, aks holda statik ma’lumotlar 
tuzilmasi deyiladi.
D1
D1
Ma’lumotlar tuzilmasiga misollar:
Ma’lumki, matematikada o‘zgaruvchilarni, ularning ba’zi bir 
kerakli tavsiflariga mos ravishda klassifikatsiya qilish qabul 
qilingan. O‘zgaruvchilarga misol sifatida quyidagilarni keltirib 
o‘tish mumkin: haqiqiy o‘zgaruvchilar, kompleks o‘zgaruvchilar, 
mantiqiy o‘zgaruvchilar, bundan tashqari ba’zi bir qiymatlarni 
qabul qiluvchi o‘zgaruvchilar va boshqalar. Ma’lumotlarni qayta 
ishlashda ularni klassifikatsiya qilish ham katta ahamiyatga ega. 
Bu yerda ham klassifikatsiya qilinayotganda har bir konstanta, 
o‘zgaruvchi, ifoda yoki funksiya biror bir toifarga tegishli bo‘ladi, 
degan tamoyilga asoslanadi.


Umuman olganda toifalar o‘zgaruvchi yoki ifoda qabul qilishi 
mumkin bo‘lgan qiymatlar to‘plami orqali tavsiflanadi. 
Ko‘plab dasturlash tillarida ma’lumotlar standart va 
foydalanuvchi tomonidan beriladigan toifalarga ajratiladi.
Ma’lumotlarni standart toifalariga quyidagi 5 ta tur 
o‘zgaruvchilari kiradi:
a) butun (INT);
b) haqiqiy (FLOAT) ;
c) mantiqiy (BOOL);
d) belgili (simvol) (CHAR);
e) ko‘rsatkichli (*).
Foydalanuvchi tomonidan aniqlanadigan toifalar esa:
a) sanaladigan;
b) diapazonli (oraliqli).


Ma’lumotlarning ixtiyoriy toifasi qiymatlar sohasi va ular ustida 
bajarilishi mumkin bo‘lgan amallar orqali tavsiflanadi.
Butun toifa – INT
Mazkur toifa butun sonlar to‘plamini qandaydir qism to‘plami 
bo‘lib, uning o‘lchami mashina, ya’ni EHM konfiguratsiyasiga 
bog‘liq ravishda o‘zgarib turadi. Agar butun sonni mashinada 
tasvirlash uchun p ta razryaddan foydalanilsa (bunda 
qo‘shimcha koddan foydalanilganda), u holda x butun sonning 
qiymat qabul qilish oralig‘i quyidagicha bo‘lishi zarur, ya’ni 
quyidagi shartni qanoatlantirishi lozim: -2 n-1<= x< 2 n-1. 
Butun toifadagi ma’lumotlar ustida bajariladigan barcha amallar 
to‘g‘ri amalga oshiriladi deb hisoblanib, ushbu amallar 
arifmetikada qabul qilgan qoidalariga bo‘ysunadi. Agar ushbu 
toifada amallar bajarilganda natija ruxsat etilgan oraliqdan 
chiqib ketsa, u holda hisoblash to‘xtatiladi. Bunday hol to‘lib 
ketish deb ataladi. 
Statik ma’lumotlar tuzilmasi haqida tushuncha
Ma’lumotlar tuzilamasi (MT) ni dasturda ifodalashning 2 ta usuli 
mavjud:
1.
Statik MT. Bunday tuzilmalar uzunligi (elementlar soni) 
oldindan aniqlangan bo’ladi va dastur bajarilish mobaynida 
o’zgarmas hisoblanadi. Elementlar orasidagi munosabatlar ham 
o‘zgarmas bo’ladi. Bunday tuzilmalar elementlar soni ma’lum va 
o’zgarmas bo’lgan masalalarda yaxshi qo’l keladi. Statik tuzilma 
elementlariga qanday qiymat berilsa berilaveradi, ammo 
tuzilma uchun ajratilgan xotira xajmi o’zgartirilmaydi.


2.
Dinamik MT. Bu tuzilmalar elementlar soni oldindan ma’lum 
bo’lmagan xollarda qo’llaniladi . Bunda elementlar soni dastur 
bajarilishi mobaynida o’zgaruvchan hisoblanadi (YarimStatatik 
MT). Ammo imkoni bo’lsa, dasturchi xotirada ziddiyatlarga duch 
kelmaslik uchun tuzilma o’lchamini oldindan aniqlasa ham 
bo’ladi.
Quyida statik va dinamik tuzilmalar qiyosi keltirilgan.
Dinamik tuzilmalar
Statik tuzilmalar
Elementlar xotirada tarqoq xolda joylashishi mumkin.
Elementlar xotiraja ketma-ket yachseykalarda joylashadi.
Elementlar soni cheklanmagan. Agar xotirada fizik joy mavjud 
bo’lsa, element kiritilishi mumkin.
Elementlar soni cheklangan. Dastur bajarilishi mobaynida 
tuzilma uzunligini o’zgartirib bo’lmaydi.
Tuzilma elementlarida indeks degan tushuncha yo’q. 
Tuzilmaning istalgan joyiga element kiritish va o’chirish amallari 
oson bajariladi. Lekin ba’zi amallar qiyin bajariladi. Chunki 
elementlar orasida qat’iy ketma-ketlik mavjud emas.


Tuzilmada indeks degan tushuncha mavjud. Shu sababli 
saralash amalini bajarish oson. Lekin eng og’ir holatni olib 
qaraydigan bo’lsak, tuzilma boshiga yangi element kiritish va 
o’chirish amalini bajarish noqulay.
Statik MT ga quyidagilarni kiritish mumkin:
1.Тo’plam
2.Massivlar
3.Yozuvlar
4.Jadvallar
1.
Тўплам тушунчаси.
Маълумки, тўплам тушунчаси билан қайсидир маънода 
мактаб даврларидан танишмиз. Тўплам математикада 
бошланғич, фундаментал тушунчалардан бири бўлиб, 
элементлар мажмуасидан ташкил топади.
Таъриф. Тўплам бу бир турга тегишли бўлиб, 
такрорланмайдиган элементлар мажмуасидир.
Тўплам базавий турга тегишли бўлган барча қийматларни 
қабул қилиши мумкин. Шуни эслатиб ўтиш лозимки, 
базавий 256 тадан ортиқ қийматни қабул қилмаслиги 
лозим. Шу сабабли тўпламнинг базавий тури byte, char ва 
улар орқали ҳосил қилинган турлар бўлиши мумкин.
Тўплам тури маълумотлари учун ажратилган байтлар сони:


ByteSize = (max div 8)-(min div 8) + 1, бу ерда max ва min – 
тўплам базавий турининг юқори ва қуйи чегараси.
Аниқ бир Е элементнинг байт рақами қуйидагича 
аниқланади: ByteNumber = (E div 8)-(min div 8).
Тўплам устидаги амаллар:
Қўшиш (тўпламлар йиғиндиси, A+B); Айриш (тўпламлар 
айримаси, A-B); Кўпайтмаси(A*B);
Элементни тўпламга тегишли ёки тегишли эмаслигини 
аниқлаш (a in
A).
Massivlar
Massiv bir toifadagi elementlarning tartibli ketma – ketligi 
hisoblanadi. Massiv bironta nom va undagi elementlar toifasi 
orqali ifodalanadi.
Massivlar:
• 
bir o’lchamli
• 


ikki o’lchamli
• 
ko’p o’lchamli
bo’lishi mumkin. 1 o’lchamli massivlar sodda bo’lib, undagi xar 
bir element xotirada ketma-ket joylashadi. Uning uchun 
xotiradan joy ajratilganda xar bir elementiga massivning 
toifasidan kelib chiqib sarflanadigan xotira xajmi elementlar 
soniga ko’paytiurilib topiladi.
A0
A1
A2

An
Masalan, int a[n] massiv qaraladigan bo’lsa, uning bitta 
elementiga 4 bayt joy ketadigan bo’lsa, massiv uchun 
ajratiladigan xotira sarfi 4*n bayt shaklida hisoblanadi. 
H=
H – bu massivga sarflanadigan xotira xajmi;
h – bu 1ta elementga ajratiladigan xotira xajmi
Ikki o’lchamli massivlarda bir nechta qator va bir nechta 
ustunlar mavjud bo’ladi. Ustun va qatorlar kesishgan joyda 


massivning elementi joylashgan bo’ladi u elementni massivning 
qator va ustun raqami bilan aniqlanadi. Masalan, beshinchi 
qator va uchinchi ustunda turgan B matritsaning elementi 
B[5][3] kabi belgilanadi. Massivlar ustida matematik amallarni 
bajarish mumkin.
Ikki o’lchovli massivlarni matrisalar deb ham atashadi. 
Matrisalar xam statik tuzilma hisoblanadi.
A00
A01
A02

A0m
A10
A11
A12

A1m
A20
A21


A22

A2m





An0
An1
An2

Anm
Chunki uni dasturda ifodalaganda, o’lchamini ko’rsatish kerak. 
Dastur ishga tushishidan oldin matrisaning satr va ustunlar soni 
va toifasini aniqlanishidan kelib chiqib kompyuter uning uchun 
xotiradan joy ajratadi. Matrisa elementlari xotirada ketma-ket 
yacheykalarda joylashtiriladi, garchi uning alohida satr 
elementlari mantiqan quyidagicha keltirilsada, bitta satr 
elementlari xotirada ketma-ket joylashtirilgandan keyin uning 


davomidan ikkinchi qator elementlari joylashtiriladi va uchunchi 
va x.k.
A00
A01
A02

A0m
A10
A11
A12

A1m
A20
A21
A22

A2m
Undan tashqari ma’lumotlar tuzilmasi sifatida massivlar ustida 
boshqa maxsus amallarni ham bajarish mumkin. Dasturda 
massiv ustida ishlash uchun avval uning toifasi va o’lchami e’lon 


qilinadi. Massivni e’lon qilish ikki xil usulda amalga oshirilishi 
mumkin. 
1.
Initsializatsiya qilmasdan e’lon qilish – bu holda massiv toifasi 
va nomi ko’rsatilib kvadrat qavs ichida uning elementlari soni 
ko’rsatiladi: int A[50].
2.
Initsializatsiya qilish orqali e’lon qilish – bu holda massiv toifasi 
ko’rsatilib elementlariga qiymat o’zlashtiriladi. Masalan, 
A[5]={1,2,3,5,4}
Massiv elementlari bir toifaga tegishli bo’lgani uchun ular 
hotiradan bir xil hajmli joyni egallaydi va ular operativ hotirada 
joylashadi. Massiv dasturda foydalanilayotgan o’rniga qarab 
global yoki lokal bo’lishi mumkin. 

Yüklə 71,82 Kb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin