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