1-laboratoriya mashg’uloti Statik ma'lumotlar tuzilmalarini o'rganish

1-laboratoriya mashg’uloti

Statik ma'lumotlar tuzilmalarini o'rganish

Ishdan maqsad: Statik ma’lumotlar tuzilmasini o‘rganish va ularni tadqiq qilish.

Qo‘yilgan masala: C++ tilida statik toifadagi ma’lumotlar tuzilmalarini yaratish va ularga doir misollarning dasturini ishlab chiqish.

Ish tartibi:

• 
  Tajriba ishi nazariy ma’lumotlarini o‘rganish;
  
• 
  Berilgan topshiriqning algoritmini ishlab chiqish;
  
• 
  C++ dasturlash muhitida dasturni yaratish;
  
• 
  Natijalarni tekshirish;
  
• 
  Hisobotni tayyorlash va topshirish.
  

Nazariy qism.

Ma’lumotlar tuzilmasi (MT)ni quyidagicha tasniflash mumkin.

Statik tuzilma deb dastur bajarilishi mobaynida elementlari soni yoki ular orasidagi bog’liqliklari o’zgaruvchan bo’lgan tuzilmaga aytiladi.Statik tuzilmalarni ko’rib chiqamiz.

Massivlar.Massiv bu bir xil toifadagi elementlarning tartibli ketma-ketligidir. Massiv bir yoki ikki o’lchovli bo’lishi mumkin. Bir o’lchovli massivlar C++ da quyidagicha e’lon qilinadi:

[elementlar_soni];

Masalan, int a[12];

Ikki o’lchovli massivlar esa quyidagicha ifodalanadi:

[qatorlar_soni][ustunlar_soni];

Masalan, int a[2][3];

1-misol. Massivni elyemyentlarini yig’indisini toping. Misolni yechilishi quyidagicha:

#include using std::cout; #include main() { float s,j; int i; s=0; float a[5]={2,3,4,-1,-5}; for (i=0; i<5; ++i) s = s + a[i]; cout<<"\n s = "< getch(); return 0; }

Natija: S = 3

2-misol. Bir o’lchamli n ta elyemyentdan iborat massiv byerilgan. Quyidagilarni bajaring:

a) manfiy elyemyentlarning yig’indisini;

b) maksimal va minimal qiymatli elyemyentlar orasida joylashgan elyemyentlardan yangi massiv tuzing;

v) massiv elyemyentlarini o’sish tartibida joylashtiring.

Misolni dasturi:

#include

using namespace std;

int main()

{

int x,y,n,h,a[1000],min,max;

cin >> n;

for(int i=0;i

cin >> a[i];

int s=0;

for(int i=0;i

if(s!=0){ cout << "Manfiy elementlar yigindisi:";

cout << endl; cout << s; cout << endl; }

else

{ cout << "Manfiy elementlari yoq;";cout << endl; }

min=a[0];x=0;

for(int i=0;i

if(a[i]

x=i; }

max=a[0];y=0;

for(int i=0;i

if(a[i]>max)

y=i;

}

cout << "maksimal va minimal elementlar orasidagi sonlar:";

if(y>x){

for(int i=x+1;i

cout << endl;

cout << a[i]; } }

else

{

for(int i=y+1;i

cout << endl;

cout << a[i];}

}

cout << endl;

min=a[0];int m=1;

for(int j=0;j

{ for(int i=m;i

if(min>=a[i]){

h=min;

min=a[i];a[i]=h;

} }

a[j]=min;

min=a[j+1];

m++;cout <

}

return 0;

}

Vektorlar. Vektor bu bir xil toifadagi elementlarning tartibli ketma ketligi bo’lib, massivdan farqi uning o’lchami dastur bajarilishi davomida o’zgarishi mumkin,yani vektor bu dinamik massiv hisoblanadi.

Vektorlarni turlicha initsializatsiyalash usullari mavjud:

vector vec0; // bo’sh vektor

const int size = 8;

const int value = 1024;

vector vec1(size);//8 ta elementga ega, elementlar qiymatlari 0 ga teng

vectorvec2(size,value);//8 ta elementga ega, elementlar qiymatlari 1024 ga teng

inta[4] = { 0, 1, 1, 2 };

vector vec3(a,a+4);//4 ta elementga ega, elementlar qiymatlari a massivinikiga teng

vector vec4(vec2);//vec2 ning nusxasi

Vektorlarning massivga nisbatan qulayligi haqida quyidagilarni bayon qilmoqchimiz:

• 
  Vektorlar bilan ishlash uchun standart kutubxona funksiyalari mavjud bo’lib, ular yordamida turli amallarni siklsiz, bir qator kod yordamida bajarish mumkin. Ulardan ayrimlarini keltirib o’tamiz:
  

• 
  test.at(i) - test[i] kabi yozuv bilan bir xil, faqat bunda agar i-element mavjud bo’lmasa, dastur hatolik ko’rsatmaydi;
  
• 
  test.asign(n,m)–vektorga n ta elementni m qiymat bilan yozadi;
  
• 
  test.asign(start,end)–boshqa vektorning boshi va oxirini ko’rsatuvchi iteratorlar startdan end gacha bo’lgan elementlarni ushbu vektorga kiritadi;
  
• 
  test.front()–1-elementga murojaat;
  
• 
  test.back() –oxirgi elementga murojaat;
  
• 
  test.begin()–vektor 1-elementi iteratori;
  
• 
  test.end()–vektor oxiri iteratori(oxirgi elementidan keying adresni ko’rsatadi);
  
• 
  test.clear()–vektorni tozalash;
  
• 
  test.erase(i)yokitest.erase(start,end)–i-iterator elementini yoki start va end oralig’idagi elementlarni o’chiradi;
  
• 
  test.size()–vektordagi elementlar sonini aniqlaydi;
  
• 
  test.swap(test2) - test va test2 vektorlar elementlarini almashtiradi;
  
• 
  test.insert(a,b) - test vektoriga iterator ko’rsatayotgan a elementdan oldin b elementni kiritadi, bunda iterator kiritilgan elementni ko’rsatadi;
  
• 
  test.insert(a,n,b)– b elementdan n ta kiritadi;
  
• 
  test.insert(a,start,end) - start va end iteratorlari oralig’idagi elementlarni a dan oldin kiritadi.
  

• 
  begin() va end() iteratorlari mos ravishdaxotirada vektorning birinchi elementini va oxirgi elementidan keyingi adresni ko‘rsatadi.Shu o‘rinda iterator nimaligiga aniqlik kiritsak. Iterator bi birorta o‘zgaruvchiga ko‘rsatkich hisoblanadi. Iterator bizga kerak qiymatlarni qayerdaligini biladi va uning qiymatini bizga chiqarib beradi. Itaratorlar asosan konteynerlar bilan ishlashda qo‘llaniladi. Iterator yaratish uchun quyidagini yozish kerak:
  

iterator_nomi::iterator nomi;

Masalan:vector ::iterator begin=vec.begin();

string::iterator end,cur;

Satrlar ham konteyner hisoblanadi. Endi iterator ko‘rsatayotgan element quyidagicha olinadi.

cout<<*cur<

Bu erda tushunarliki, * belgisi cur iteratorni emas, u ko‘rsatayotgan qiymatni ko‘rsatadi.

cur++; // keying elementga o‘tish

cur+=10; // <=>cur=cur+10 10 ta elementdan keyinga o‘tish

Vektor elementlarinni iterator bilan ekranga chiqarishni ko‘ramiz:

vector test;

string buffer = "";

//elementlarni kiritilsh

do {

getline(cin, buffer);

if (buffer.size() > 0) test.push_back(buffer);

} while (buffer != "");

vector::iterator cur;

for (cur=test.begin();cur

cout<<*cur<

• 
  2ta uzunligi teng bo‘lgan vektorni siklsiz solishtirish mumkin. Bunda ularning mos elementlari qiymatlari solishtiriladi. Masalan:
  

#include

#include

using namespace std;

int main()

{

vector array1(3);

array1[0] = 4;

array1[1] = 2;

array1[2] = 1;

vector array2(3);

array2[0] = 4;

array2[1] = 2;

array2[2] = 1;

// vektorlarni solishtirish

if (array1 == array2) {

cout << "array1 == array2" << endl;

}

return 0;

}

• 
  Vektor elementlarini siklsiz ekranga chiqarish mumkin:
  

#include

#include

#include

using namespace std;

int main()

{

vector array1;

array1.insert(array1.end(), 4);

array1.insert(array1.end(), 3);

array1.insert(array1.end(), 1);

copy( array1.begin(), // vektor boshi iteratori

array1.end(), // vektor oxiri iteratori

ostream_iterator(cout," ") //chiqarish potoki iteratori

);

return 0;

}

• 
  Vectorlar yordamida ikki o‘lchovli massivlarni ham yaratish mumkin. Masalan:
  

#include

#include

using namespace std;

int main ()

{

const int row=10;

const int col=2;

vector> tab(row);

for(int i=0; i

{

tab[i].resize(col);

for(int j=0; j

cout<<'\n';

}

cout<

system("pause");

}

1-misol. Vektor va vektorlar ustida amal bajarish dasturi.

#include

#include

using namespace std;

int main()

{

vector q;

q.push_back(10); q.push_back(11); q.push_back(12);

vector v;

for(int i=0; i<5; ++i){

v.push_back(i);

}

// v vektori elementlari 0 1 2 3 4

std::vector::iterator it = v.begin() + 1;

// 2-el.dan oldin 33 ni kiritish:

it = v.insert(it, 33);

// v vektori elementlari 0 33 1 2 3 4

//q vektor elementlarini v vector 2-el.dan oldin kiritish:

v.insert(it, q.begin(), q.end());

// v vektori elementlari 0 10 11 12 33 1 2 3 4

it = v.begin() + 3;

// it v vektorning 4-el.ni ko‘rsatyapti

// 4-el.dan oldin 3 marta -1ni kiritamiz:

v.insert(it, 3, -1);

// v vektor el.lari 0 10 11 -1 -1 -1 12 33 1 2 3 4

// v vektorning 5 – el-tini o‘chiramiz

it = v.begin() + 4;

v.erase(it);

// v vektor el.lari 0 10 11 -1 -1 12 33 1 2 3 4

v.clear();//v vektorni o‘chirish

return 0;

}

To‘plamlar. To‘plam bu bir xil toifadagi elementlarning tartibsiz majmuasidir va unda elementlar takrorlanmas bo‘ladi. To‘plam ustida bajariladigan amallar quyidagilar: element kiritish, o‘chirish, elementlar sonini aniqlash, bo‘shlikka tekshirish. To‘plamni C++ da quyidagicha e’lon qilinadi:

set s;

for(int i = 1; i <= 100; i++) {

s.insert(i); // to‘plamga element kiritish

}

s.insert(42); // 42 to‘plamda avjudligi sababli hech nima yuz bermaydi

for(int i = 2; i <= 100; i += 2) {

s.remove(i); // juft sonlarni o‘chiramiz

}

// set::size() funksiyasi unsigned int toifasida qiymat qaytargani uchun uni int toifasiga o‘giramiz

int N = int(s.size()); // N=50

To‘plamda push_back() funksiyasi yo‘q. Chunki unda elementlar tartibsiz va indeks degan tushuncha yo‘q. Shu sababli to‘plam elementlarini iterator bilan chiqarish mumkin.

set S;

...

// S to‘plam elementlari yig‘indisini hisoblaymiz

intr = 0;

for(set::const_iterator it = S.begin(); it != S.end(); it++)

r+=(*it);

To‘plam bilan ishlashning afzalligi tezlikdir.Ayniqsa, qidiruvda.Set::find() funksiyasi 1 ta argumentga ega va uning qaytaradigan qiymati yoki topilgan elementni ko‘rsatadi, yoki end() iteratoriga teng bo‘ladi.

set s;

...

if(s.find(42) != s.end()) {

// 42 mavjud

}

else {

// 42 mavjud emas

}

To‘plamdan elementni o‘chirish uchun erase() funksiyasidan foydalaniladi.

set s;

...

s.insert(54);

...

s.erase(29);

s.erase(s.find(57));

Bu funksiyaning oraliqli ko‘rinishi ham mavjud:

set s;

...

set::iterator it1, it2;

it1 = s.find(10);

it2 = s.find(100);

if(...) {

s.erase(it1, it2); // 10 dan 100 gacha bo‘lgan elementlar //o‘chiriladi(10,100 o‘chirilmaydi)

}

else {

// it2 iteratorni bitta element keying suramiz

// set::iterator uchun += operatori qo‘llanilmaydi, lekin ++ va – //ishlatilishi mumkin

it2++;

s.erase(it1, it2);

}

To‘plamni e’lon qilishning huddi vektordagi kabi oraliqli konstruktori ham mavjud:

int data[5] = { 5, 1, 4, 2, 3 };

set S(data, data+5);

Misol.Matn faylida berilgan so‘zlardan to‘plam xosil qiling.To‘plamdan bironta satrni izlash dasturini tuzing.

#include

#include

#include

#include

#include

using namespace std;

int main()

{

set s;

ifstream f("bas.txt");

copy(

istream_iterator(f),

istream_iterator(),

inserter(s, s.end())

);

copy(

s.begin(),

s.end(),

ostream_iterator(cout, "\n")

);

string a="";

cin>>a;

if(s.find(a)!=s.end()) cout<<"bor";

else cout<<"yo‘q";

system("pause");

}

Misol.Satrdagi belgilarning to‘plamga tegishli yoki yo‘qligini aniqlash dasturi.

#include

#include

#include

using namespace std;

int main()

{

set cs;

for(int i='A';i<='Z';i++) cs.insert(i);

string str="A1bZzh2;";

for(int i=0;i

if(cs.find(str[i])!=cs.end())

cout<

else cout<
system("pause");

return 0;

}

Yozuv va jadvallar. Yozuv bu turli toifadagi ma’lumotlarning tartibli ketma-ketligidir.Yozuv maydonlardan tashkil topadi. Har bir maydon o‘z nomi va o‘z toifasiga ega bolib, ular xotirada ketma-ket joylashadi. Yozuv uchun ajratiladigan xotira hajmi uning maydonlariga ajratilgan xotira hajmlari yig‘indisidan kelib chiqadi. Yozuvlar C++ da quyidagicha e’lon qilinadi.

struct Guruh{

int t_r;

char fio[30];

float bali;

} talaba1, talaba2;

Bu erda Guruh nomli nostandart toifa yaratilib, bu toifaga tegishli 2 ta yozuv e’lon qildik. Shu yozuvlarga tegishli maydonlarga murojaat quyidagicha amalga oshiriladi:

talaba1.fio=”Ahmad”;

talaba2.bali=1.5;

Bu erda ko‘rib turganingizdek,Guruh toifasida 2 ta yozuv yaratildi. Agar bu toifaga tegishli massiv yaratiladgan bo‘lsa, yani yozuvlar massividan jadval xosil bo‘ladi. 2 ta yozuvni solishtirishva o‘zlashtirish mumkin, bunda ulaning mos maydonlari solishtiriladi yoki o‘zlashtiriladi va maydonlarni alohida yozib ko‘rsatish shart emas.

Misol. 2 ta ishchilar ma’lumotlaridan iborat jadval berilgan.Har ikkala jadvalda ismlari takrorlangan ishchilardan yangi jadval hosil qiling.

# include

using namespace std;

int main(){

struct employer{

char fio[30];

char lavozim;

} ;

int n,m;

cout<<"1-bo‘lim ishchilar soni n=";cin>>n;

cout<<"2-bo‘lim ishchilar soni m=";cin>>m;

employer bir_bolim[n],ikki_bolim[m];

employer yangi[n+m];

for(int i=0;i

cin>>bir_bolim[i].fio>>bir_bolim[i].lavozim;

}

for(int j=0;j

cin>>ikki_bolim[j].fio>>ikki_bolim[j].lavozim;

}

int k=0;cout<<"------------mana-------------"<

for(int i=0;i

string s,s1;

s=bir_bolim[i].fio;

for(int j=0;j

s1=ikki_bolim[j].fio;

if(s==s1){yangi[k++]=bir_bolim[i];yangi[k++]=ikki_bolim[j];}

}}

for(int i=0;i

cout<<"|"<

}

Ishni bajarishga namuna

Berilgan topshiriq variantlariga o‘xshash bo‘lgan bitta masalani bajarib ko‘ramiz. Quyidagicha masala qo‘yilgan: Berilgan familiyalardan imlo qoidasiga mos ravishda ismlar hosil qiling.

Algoritm

1. 
   Familiya kiritilishini so‘rash.
   
2. 
   Kiritilgan familiya uzunligini o‘lchash.
   
3. 
   Familiya oxirgi va oxiridan 1 ta oldingi simvolini tekshirish, ya’ni familiya oxiri “ev” bilan tugasa, satrning oxirgi 3 ta simvolini o‘chirish va 7-qadamga o‘tish, aks holda 4-qadamga o‘tish.
   
4. 
   Familiya oxirgi va oxiridan 1 ta oldingi simvolini tekshirish, ya’ni familiya oxiri “ov” bilan tugasa, satrning oxirgi 2 ta simvolini o‘chirish va 7-qadamga o‘tish, aks holda 5-qadamga o‘tish.
   
5. 
   Familiya oxirgi va oxiridan 2 ta oldingi simvolini tekshirish, ya’ni familiya oxiri “eva” bilan tugasa, satrning oxirgi 4 ta simvolini o‘chirish va 7-qadamga o‘tish, aks holda 6 qadamga o‘tish.
   
6. 
   Familiya oxirgi va oxiridan 2 ta oldingi simvolini tekshirish, ya’ni familiya oxiri “ova” bilan tugasa, satrning oxirgi 3 ta simvolini o‘chirish va 7-qadamga o‘tish.
   
7. 
   Hosil bo‘lgan ismni ekranga chiqarish.
   

Talabalar algoritmni so‘z bilan yoki blok-sxema ko‘rinishida ifodalashlari mumkin.

Dastur kodi:

#include

#include

using namespace std;

int main(){

int l;

char a[100];

cout << " Familiyani kiriting: ";

gets(a);

l=strlen(a);

if(a[l-1] ==‘v' && a[l-2] ==‘e'){ l = l-3; }
if(a[l-1] ==‘v' && a[l-2] ==‘o‘){ l = l-2; }

if(a[l-1] ==‘a' && a[l-3] ==‘e'){ l = l-4; }

if(a[l-1] ==‘a' && a[l-3] ==‘o‘){ l = l-3; }

cout << "\n Natija: \n ";

for(int i = 0; i < l; i++)

cout<

getch();

}

Nazorat savollari

1. 
   Statik malumotlar tuzilmalari qanday tuzilmalar?
   
2. 
   Statik ma’lumotlar tuzilmalariga qanday tuzilmalar kiradi?
   
3. 
   Struct va vector toifalarini tushuntiring.
   
4. 
   Class va massivlar qanday e’lon qilinadi?
   
5. 
   To‘plamlar qanday tuzilma?
   

Topshiriqlar.

Variantlar:

1. 
   Berilgan sonlar ketma-ketligidagi maksimal va minimal elementlarning o‘rnini almashtiring.
   
2. 
   Berilgan sonlar ketma-ketligidagi har bir elementni o‘zi, o‘zidan oldingi va o‘zidan keyingi element bilan yig‘indisiga almashtiring.
   
3. 
   k-darajagacha bo‘lgan Nyuton binomi sonlaridan vektor hosil qiling. Nyuton binomi sonlari quyidagicha aniqlanadi.
   

1 1

1 2 1 2

1 3 3 1 3

1 4 6 4 1 …

1 5 10 10 5 1 k

4. 
   nxn matritsaning yuqori chap uchburchagidagi elementlaridan vektor hosil qiling
   
5. 
   nxn matritsaning yuqori o‘ng uchburchagidagi elementlaridan vektor hosil qiling
   
6. 
   nxn matritsaning pastki o‘ng uchburchagidagi elementlaridan vektor hosil qiling
   
7. 
   nxn matritsaning pastki chap uchburchagidagi elementlaridan vektor hosil qiling
   
8. 
   Matritsani matritsaga ko‘paytiring
   
9. 
   Jadval hosil qiling va unga ma’lumotlarni kiriting, ekranga chiqaring.
   
10. 
    Talabalar ism-familiyasi, yoshi va ballaridan iborat jadval yarating va talabalarni ism-familiyasini alfavit bo‘yicha tartibga keltiring.
    
11. 
    10-variantdagi jadvaldan bali bo‘yicha eng katta va eng kichik talabalarning o‘rnini almashtiring
    
12. 
    2 ta bir xil tipdagi jadval berilgan. Ikkala jadvalni o‘zaro solishtiring va aynan bir xil bo‘lgan yozuvlarni o‘chiring.
    
13. 
    Birlashma tipidagi (tipda 2 ta element e’lon qiling) 2 ta o‘zgaruvchini bir-biridan farqli elementlariga qiymat bering va ularning yig‘indisini ikkala o‘zgaruvchining qiymat berilmagan elementlariga o‘zlashtiring. Har ikkala o‘zgaruvchining barcha elementlarini ekranga chiqaring va natijani tushuntiring.
    
14. 
    Avtomobil nomli klass yarating va unda turli o‘zgaruvchi va funksiyalar yarating. Ushbu klassdan foydalanib, turli markali avtomobillar uchun o‘zgaruvchilarni yaratib, ular haqida ma’lumotlar kiritib, ekranga chiqaring.
    
15. 
    Berilgan matnli fayldan simvollarni o‘qib, ekranga chiqaring va raqamlarni ajratib ko‘rsating.
    
16. 
    Berilgan matnli faylda a harfi necha marta qatnashganini sanang.
    
17. 
    Berilgan matnli fayldagi satrlar sonini aniqlang.
    
18. 
    Talabalar ism-familiyasi, yoshi va ballari maydonidan iborat klass yarating va talabalar ro‘yhatini tuzing. So‘ralayotgan talaba ro‘yhatda bor yo‘qligini aniqlang.
    
19. 
    Oy nomlaridan iborat sanaladigan toifa yarating. So‘ralayotgan oy qaysi faslga tegishliligini aniqlang.
    
20. 
    Mahsulot nomlaridan iborat elementlar va ularning qiymati sifatida narxlari kiritilgan sanaladigan toifa yarating. So‘ralayotgan narxda qanday mahsulot yoki mahsulotlar to‘plamini xarid qilsa bo‘ladi, shuni aniqlash dasturini tuzing.
    
21. 
    Kiritilgan ismning harflarini alfavit bo‘yicha tartibga keltiring.
    
22. 
    Satrli toifadagi vektor berilgan. Bir xil qiymatdagi elementlarni aniqlang, ekranga chiqaring.
    
23. 
    Berilgan ismlardan imlo qoidasiga mos ravishda familiyalar hosil qiling.
    
24. 
    Berilgan satrda nechta undosh harflar borligini aniqlang.
    
25. 
    Berilgan satrdagi sonlar yig‘indisini aniqlang.
    
26. 
    F faylda berilgan satr necha marta uchrashini aniqlang.
    
27. 
    G fayldan nusxa ko‘chiring.
    
28. 
    F fayldan matritsa hosil qiling, ya’ni fayldagi har bir qator matritsaning satri va qatordagi’#’ belgisi bilan ajratilgan satrlar ustunlar qilib belgilansin.
    
29. 
    Matritsaning juft va toq elementlaridan 2 ta vektor hosil qiling.
    
30. 
    Massivdagi tub sonlarni va indekslarini ekranga chiqaring.