“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

  Ma’lumotlar tuzilmasiga misol

D1



D2

D3

To’plam



D1

D2

D3



Ketma-ketlik

Daraxt



Graf


D1



D2

D3

D1



D2

D3

Foydalanuvchi dasturida MT turlari  

statik tuzilma;

dinamik tuzilma.

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.

Foydalanuvchi dasturida MT klassifikatsiyasi



Ma’lumotlarni standart turlari

butun

xaqiqiy

belgili

mantiqiy

Ko’rsatkichli

Foydalanuvchi tomonidan aniqlanadigan tur

sanaladigan

oraliqli

massivlar

vektorlar

strukturalar

birlashmalar

klasslar

Butun tur

Qiymatlar oralig’i

Amallar

-2 n-1<= x< 2 n-1 - n -razryad

qo’shish(+);

ayirish(-);

Ko’paytirish(*);

Butun bo’lish(/);

Qoldiqli bo’lish(%);


Тур	Формат
Short	2 байт
Int	4 байт
Long	4 байт (ишорали)
unsigned	modifikator



O’zlashtirish =; ~=

Taqqoslash <; <=; >; >=

Inkrement ++

Dekrement --

Ishora butun son

Xaqiqiy tur

Qiymatlar oralig’i

Amallar

qo’shish(+);

ayirish(-);

Ko’paytirish

Bo’lish(/);

O’zlashtirish =; ~=

Taqqoslash <; <=; >; >=


Тур	Формат
Float	4 байт
Double	8 байт



Mantissa ishorasi mantissa tartib ishorasi tartib

ASCII – kodi

elementlari

Belgili tur

Qiymatlar

Amallar

O’zlashtirish =;

Birlashtirish(Kontekanatsiya)+

<; <=;

>; >=.

Eslatma

Belgili tur apostrov ichida beriladi

Mantiqiy tur

Qiymatlar

Amallar

O’zlashtirish;

taqqoslash(==; <;<=; >; >=);

&& || !


Nomi	False qiymati	True qiymati	Хотира o’lchami
Bool	0	1	1 байт

X	Y	! X	X &&Y	X || Y
false	false	true	false	false
false	true	true	false	true
true	false	false	false	true
true	true	false	true	true



Ko’rsatkichli tur

Amallar

O’zlashtirish;

Adress bo’yicha qiymat olish;

Adresni olish(&);

Qo’shish; ayirish;

inkrement; dekrement.

Ta’rif

Ko’rsatkich (Pointer) – bu shunday tur bo’lib, uningqiymatlar oralig’i xotira yacheykalari manzili va maxsus qiymat (nol manzil) dan iborat.

Izox

Nol ko’rsatkich– shunday maxsus qiymatki, u xech qanday obyektga yo’naltirmaganlikni anglatadi.

C# ва Java – null;

C ва C++ - 0 ёки null макрос;

Pascal – nil.

Mavjud obyekt adresiniko’rsatkichga o’zgartiradi.

int a = 5;

int* p = &a;

Sanaladigan turlar

• 
  Bir qancha qiymatlardan birini qabul qila oladigan o‘zgaruvchiga sanaladigan toifadagi o‘zgaruvchilar deyiladi va bunday o‘zgaruvchilarni e’lon qilishda enum kalit so‘zi va undan keyin toifa nomi hamda figurali qavs ichida vergullar bilan ajratilgan o‘zgarmas qiymatlar ro‘yhati ishlatiladi.
  
• 
  Masalan:
  
• 
  enum Ranglar{oq, qora, qizil, yashil};
  

Ushbu toifada yangi o’zgaruvchi e’lon qilish mumkin.

Ranglar rang;

Bu yerda Ranglar nomli sanoqli toifa yaratildi. Ushbu toifaning 4 ta o‘zgarmas elementlari mavjud va ular dastlab 0 dan boshlab sanaladigan butun sonli qiymatga ega bo‘ladilar.

Foydalanuvchi tomonidan o’zgarmaslarga ixtiyoriy ( sanaladigan ) sonli qiymat ham o’zlashtirilishi mumkin. O’zgarmaslarga qiymatlar o’sish tartibida berilishi kerak. Masalan,

Foydalanuvchi tomonidan o’zgarmaslarga ixtiyoriy ( sanaladigan ) sonli qiymat ham o’zlashtirilishi mumkin. O’zgarmaslarga qiymatlar o’sish tartibida berilishi kerak. Masalan,

enum

Ranglar{oq=100,qora=200,qizil,yashil=400};

Bu yerda qizil o’zgarmasning qiymati 201 ga teng bo’ladi.

Massiv bu bir toifaga mansub elementlar to‘plami bo‘lib, uning 2 xil ko‘rinishi mavjud: 1 o‘lchovli va 2 o‘lchovli massivlar.

1 o‘lchovli massiv - a[0],a[1],…,a[n]

2 o‘lchovli massiv - a[0][0],a[0][1],…,a[0][m]

a[1][0],a[1][1],…,a[1][m]

…

a[n][0],a[n][1],…,a[n][m]



Massivlar va vektorlar

Ma’lumotlarni massivda saqlashda elementlar soni oldindan ma’lum bo‘lishi kerak. Ayrim paytlarda massivga nechta element kiritilishi ma’lum bo‘lmaydi va o‘shanda dinamik dasturlashdan foydalanish kerak bo‘ladi. Shunday hollarda vector dan foydalanish mumkin. Vector klassi o‘zgaruvchan uzunlikdagi massiv yaratishga yordam beradi. Vektor bu elementlari soni oldindan ma’lum bo‘lmagan bir xil toifadagi elementlar ketma-ketligidir(yani dinamik tuzilma). Vektorning massivdan farqi, vector uzunligi oldindan berilmaydi va u dastur bajarilishi mobaynida o‘zgarib turadi. Uni 2 xil usulda e’lon qilish mumkin : vector o‘zgaruvchi_nomi;

Ma’lumotlarni massivda saqlashda elementlar soni oldindan ma’lum bo‘lishi kerak. Ayrim paytlarda massivga nechta element kiritilishi ma’lum bo‘lmaydi va o‘shanda dinamik dasturlashdan foydalanish kerak bo‘ladi. Shunday hollarda vector dan foydalanish mumkin. Vector klassi o‘zgaruvchan uzunlikdagi massiv yaratishga yordam beradi. Vektor bu elementlari soni oldindan ma’lum bo‘lmagan bir xil toifadagi elementlar ketma-ketligidir(yani dinamik tuzilma). Vektorning massivdan farqi, vector uzunligi oldindan berilmaydi va u dastur bajarilishi mobaynida o‘zgarib turadi. Uni 2 xil usulda e’lon qilish mumkin : vector o‘zgaruvchi_nomi;

Massivlar va vektorlar

Vektor yaratish uchun < vector> kutubxonasiga ulanish zarur.

• 
  Vektor yaratish uchun < vector> kutubxonasiga ulanish zarur.
  
• 
  Vektorni eʼlon qilishning 2 xil usuli bor :
  

1) vektor uzunliginii koʼrsatib

2) boʼsh vektor sifatida.

1)vector o‘zgaruvchi_nomi;

1)vector o‘zgaruvchi_nomi;

2) vector o‘zgaruvchi_nomi (o’lcham);

Misol :vector vek;

BU holda vek[0]=123; vek[1]=234; kabi indexga murojaat amallari mumkin emas (2usulda mumkin)

Bu holda vektorga element kiritish quyidagicha amalga oshiriladi:

• 
  vek.push_back(7);//vector oxiriga yangi element 7 ni kiritish
  
• 
  vek.pop_back();// vektor oxirgi elementini o‘chirish funksiyasi
  


Massivlar va vektorlar

vek.push_back(7);//vector oxiriga yangi element 7 ni kiritish

• 
  vek.push_back(7);//vector oxiriga yangi element 7 ni kiritish
  
• 
  vek.push_front(17);//vector boshiga yangi element 17 ni kiritish
  
• 
  vek.pop_back();// vektor oxirgi elementini o„chirish funksiyasi
  
• 
  vek.pop_front();// vektor 1-elementini o„chirish funksiyasi
  

MISOL 1 :

#include

• 
  #include
  
• 
  #include
  
• 
  using namespace std;
  
• 
  int main(){
  
• 
  vector< string > text;
  
• 
  string word;
  
• 
  while(word!="0"){
  
• 
  text.push_back( word );
  
• 
  cin>>word; }
  
• 
  for(int i=0;i
  
• 
  system("pause");
  
• 
  }
  

Misol 2. vector vek (5);

Yaʼni vektor uzunligi oldindan koʼrsatilyapti va berilgan uzunlikka mos barcha elementlarga avtomatik ravishda 0 qiymat beriladi.Vektor elementlariga murojaat (massiv kabi) indekslar orqali amalga oshirdi. Masalan,

vek [0]++;vek [1]=11;

Bu xolda push_back va push_front funktsiyalarning qoʼllanishi uzunlikni oshiradi

Strukturalar turli toifadagi maydonlardan tashkil topgan yozuv hisoblanadi. Strukturalarni e’lon qilish uchun struct kalit so‘zi ishlatiladi. Undan keyin toifaga nom beriladi va {} qavs ichida maydonlar toifalari va nomlari e’lon qilinadi.

• 
  Strukturalar turli toifadagi maydonlardan tashkil topgan yozuv hisoblanadi. Strukturalarni e’lon qilish uchun struct kalit so‘zi ishlatiladi. Undan keyin toifaga nom beriladi va {} qavs ichida maydonlar toifalari va nomlari e’lon qilinadi.
  

struct G{

char ch;

} talaba, talabalar[10];

O’zgaruvchi yoki massiv elementi maydonlariga murojaat:

• 
  Jadval_elementi[indeks].maydon_nomi=qiymat;
  
• 
  Ya’ni, talabalar[i].ch=’a’;
  


Strukturalar

Bu yaratilgan G nomli toifada eʼlon qilingan oʼzgaruvchi talaba -

• 
  yozuv xisoblanadi, massiv talabalar[10] esa jadvalni tashkil etadi.
  

Yozuv va jadval yozuvi maydoniga qiymat berish :

yozuv.maydon _nomi=qiymat;

Masalan, talaba.ch=‘a’

Oʼzgaruvchi yoki massiv elementi maydonlariga murojaat:

Jadval_elementi[indeks].maydon_nomi=qiymat;

Yani

talaba[i].ch=‘a’

Yozuv – Struct (C,C++))

• 
  TА’RIF. Yozuv – maydon deb ataluvchi chekli sondagi maʼlumotlar tuplamidir.
  
• 
  Eslatma. Yozuv ketma-ket kelgan turli tipdagi maydonlar tuplamidan iborat maʼlumotlar tuzilmasini ifodalab, mantiqiy tasvirlanishda ham fizik tasvirlanishda ham tuzilma elementlari ketma-ket joylashgan boʼladi.
  

Izoh: Yozuvning massivdan farqi shundan iboratki, uning elementlari bir necha maydonlarga ega boʼlib, ular turli turlarga tegishli boʼlishi mumkin.

Yozuvda maʼlumot elementlarini koʼpincha yozuv maydonlari deb xam ataladi.

Yozuvni eʼlon kilish : С++da

Yozuvni eʼlon kilish : С++da

struct { } o’zgaruvchilar;

• 
  maydonlar orasiga ; belgisi qoʼyiladi.
  
• 
  С++ da yozuvni eʼlon qilishga oid misol
  

struct BirthDay {

int day;

int month;

long year;} a,b;

int main()

{

a.day=27;

a.month=12;

b.year=1939;

}

Yozuvning ifodalanishi

• 
  Yozuv elementlarini oʼzi xam yozuvdan iborat boʼlishi mumkin. Bu holatda murakkab ierarxik maʼlumotlar tuzilmasi vujudga keladi. Ushbu tuzilma ichma-ich joylashgan yozuv deb ataladi.
  

Yozuv ustidagi asosiy amallar

• 
  Yozuv ustidagi asosiy amallar
  
• 
  Yozuv maydoni maʼlumotlarni oʼqish.
  
• 
  Yozuv maydoniga maʼlumotlar kiritish.
  
• 
  Turga mos keluvchi, yozuv maydoni ustida bajarishi mumkin boʼlgan barcha amallar.
  
• 
  Jadvallar
  

Jadval - bu yozuvning chekli majmuasidir.

Jadval berilayotganda unda ishtirok etadigan yozuvlar soni koʼrsatib oʼtiladi.

Jadval ustida bajariladigan amallar :

Jadval maʼlumotlari elementi yozuv hisoblanadi. Shuning uchun jadval ustida bajariladigan amallar bu yozuv ustida bajariladigan amallardir.

  1. Berilgan kalit boʼyicha yozuvni qidirish.

2. Jadvalga yangi yozuvni kiritish.

• 
  Misol: struct Guruh{
  
• 
  int n;
  
• 
  char fio[30];};
  
• 
  Guruh talaba[5];
  
• 
  for(int i=0;i<5;i++){
  
• 
  talaba[i].n=i+1;
  
• 
  cin>>talaba[i].fio;
  
• 
  }
  

Maʼlumotlarning abstrakt tuzilmasi(MАT)

Chiziqli – roʼyxat, stek, navbat va dek;

Chiziqsiz -toʼplam, daraxt va graf boʼlishi mumkin.

MАT maʼlumotlar tuzilmasining matematik modeli boʼlib, unda mt foydalanuvchi nuqtai nazaridan maʼno jixatidan oʼzini tutishi orqali aniqlanadi, yaʼni uni mumkin boʼlgan qiymatlari, undagi mumkin boʼlgan amallar orqali aniqlanadi. MАTning konkret amalga oshirilishi maʼlumotlar tuzilmasi deyiladi, masalan, roʼyxat yoki stek va b.

Formal ravishda, MAT komponentlar (ushbu ob'ektlarga nisbatan qo'llaniladigan operatsiyalar va ularning xususiyatlari) ro'yxati tomonidan aniqlangan ob'ektlar to'plami sifatida aniqlangan bolishi mumkin. Ushbu turning barcha ichki tuzilishi dasturiy ta'minot ishlab chiqaruvchidan yashiringan - bu abstraktsiyaning mohiyatidir. Ma'lumotlarning abstrakt turi, uning konkret bir turdagi realizatsiyasidan mustaqil bo'lgan funktsiyalar to'plami bolib, ular MATning qiymatlari ustida operatsiyalar bajarish uchun moljallangandir. MAT-larning konkret amalga oshirilishlariga(realizatsiya) ma'lumotlar tuzilmasi deyiladi.

Formal ravishda, MAT komponentlar (ushbu ob'ektlarga nisbatan qo'llaniladigan operatsiyalar va ularning xususiyatlari) ro'yxati tomonidan aniqlangan ob'ektlar to'plami sifatida aniqlangan bolishi mumkin. Ushbu turning barcha ichki tuzilishi dasturiy ta'minot ishlab chiqaruvchidan yashiringan - bu abstraktsiyaning mohiyatidir. Ma'lumotlarning abstrakt turi, uning konkret bir turdagi realizatsiyasidan mustaqil bo'lgan funktsiyalar to'plami bolib, ular MATning qiymatlari ustida operatsiyalar bajarish uchun moljallangandir. MAT-larning konkret amalga oshirilishlariga(realizatsiya) ma'lumotlar tuzilmasi deyiladi.

Dasturlashda MATlar odatda mos turning realizatsiyasini yashiradigan interfeys sifatida taqdim etiladi. Dasturchilar MATlar bilan faqat o'zlarining interfeyslari orqali ishlaydi, chunki kelajakda amalga oshirish o'zgarishi mumkin. Ushbu yondashuv ob'ektga yo'naltirilgan dasturlashda inkapsulasyon printsipiga mos keladi. Ushbu uslubning kuchi aniq bajarilishini yashiradi. Faqatgina interfeys tashqarida ochiq ekan, ma'lumotlar strukturasi ushbu interfeysni qo'llab-quvvatlayotgan ekan, MAT sifatida belgilangan struktura bilan ishlaydigan barcha dasturlar ishlashni davom ettiradi.

• 
  Dasturlashda MATlar odatda mos turning realizatsiyasini yashiradigan interfeys sifatida taqdim etiladi. Dasturchilar MATlar bilan faqat o'zlarining interfeyslari orqali ishlaydi, chunki kelajakda amalga oshirish o'zgarishi mumkin. Ushbu yondashuv ob'ektga yo'naltirilgan dasturlashda inkapsulasyon printsipiga mos keladi. Ushbu uslubning kuchi aniq bajarilishini yashiradi. Faqatgina interfeys tashqarida ochiq ekan, ma'lumotlar strukturasi ushbu interfeysni qo'llab-quvvatlayotgan ekan, MAT sifatida belgilangan struktura bilan ishlaydigan barcha dasturlar ishlashni davom ettiradi.
  
• 
  Ma'lumotlar tuzilmalarini ishlab chiquvchilar tashqi interfeys va funktsiyalar semantikasini o'zgartirmasdan, tezkorlik, ishonchlilik va ishlatilgan xotira nuqtai-nazaridan kelib chiqib algoritmlarini takomillashtirishni bosqichma-bosqich amalga oshirishni aniqlashtirishga harakat qiladalar.
  

Mavzu bo‘yicha nazorat savollari

• 
  Ma’lumotlar tuzilmasi deganda nimani tushunasiz?
  
• 
  Ma’lumotlarni tasvirlash bosqichlarini keltirib o‘ting.
  
• 
  Ma’lumotlar tuzilmasi klassifikatsiyasi qanday amalga oshiriladi?
  
• 
  Ma’lumotlar tuzilmasini foydalanuvchi dasturidagi turlari.
  
• 
  Qanday ma’lumotlar dinamik yoki statik turdagi ma’lumotlar tuzilmasi deyiladi?
  
• 
  МАТ – нима?
  
• 
  MAT dasturda qanday amalga oshiriladi?
  

Mavzu bo‘yicha nazorat savollari

• 
  Ma’lumotlar tuzilmasini asosiy tavsifi nimadan iborat?
  
• 
  Ma’lumotlarning qanday turlarini bilasiz?
  
• 
  Ma’lumotlar ustida qanday amallarni bajarish mumkin?
  
• 
  Belgili turda qanday amallarni bajarish mumkin?
  
• 
  Ko‘rsatkichli tur tushunchasi.
  
• 
  Ma’lumotlarning sanaladigan turi degani nima?
  

http://hozir.org