Algoritm va ma’lumotlar strukturasi
![{cout<<" bu mukammal y son emas"<<endl;} }
3-Misol. Alifbo xarflarini chiqaring va kiritilgan so’zning xarflarini o’sish tartibida
saralang.
#include <stdio.h>
#include <iostream>
using namespace std;
int main(void)
{ for(char c='a';c<='z';c++) cout<<c<<(char)(c-32)<<" ";
char s[34];
cout<<endl<<"so'z kiriting ";
cin>>s;
for(int i=0;i<strlen(s)-1;i++)
for(int j=i+1;j<strlen(s);j++) if(s[i]>s[j]) swap(s[i],s[j]);
cout<<s; return 0; }
4-misol. Ikki son berilgan. Ularning musbat ekanligini tekshiring.
#include <iostream>
#include <cmath>
using namespace std;
int main()
{ bool x; int a,b;
cin>>a>>b;
x=a>0&&b>0;
cout<<x;
return 0; }
5-misol. Kiritilgan belgining nimaligini aniqlovchi programma tuzilsin. Agar belgi
raqam bo’lsa –“digit”, lotincha harf bo’lsa-“lotin” yozuvi chiqarilsin. Boshqa
holatlarda nol chiqarilsin.
#include <iostream>
#include <ctype.h>
using namespase std;
int main()
{char a; bool x,y;
cin>>a;
x=isdigit(a);
y=isalpha(a);
if (x==true) cout<<”digit”;
if (y==true) cout<<”lotin”;
else cout<<0;
return 0;}](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_7.png?v=1)
![3-mustaqil ish
Mavzu: Ma’lumotlar tuzilmasida satrli va belgili turlarni dasturlashtirish
Reja:
1 Satrlarni e’lon qilish
2 Satr uzunligini aniqlash
3 Satrlarni nusxalash
C++ dasturlash tilida bir nechta turlardan foydalanish va ular ustida amallar bajarish
mimkin, dasturlash muhitida boshqa turlar kabi belgili turlar ham mavjud. C++ dasturlash
tilida belgili turlar char turiga mansub bo‘lgan yagona elementli tur hisoblanadi. C++
dasturlash tilida satrlar uchun alohida maxsus turlar ham mavjud, lekin satrlarni belgilar
massivi sifatida ishlatish ham mumkin.
Ta’rif: Alohida nom bilan saqlanuvchi bir nechta belgilardan tashkil topgan belgilar
majmuasi satr deyiladi.
Satrlarni belgilar massivi sifatida qarab ular ustida amallar bajarish mumkin. C++
dasturlash tilida satrlar nol(‘\0’) terminatori bilan tugaydi. Nol terminatori bilan
tugaydigan satrlar ASCIIZ –satrlari deyiladi.
Satrlardan foydalanish va ular ustida amallar bajarish uchun albatta oldin ularni e’lon
qilish kerak. Satr turiga mansub bo‘lgan o‘zgaruvchilarni char xizmatchi so‘zi orqali e’lon
qilinadi. Satrlarni e’lon qilish uchun quyidagi dasturlarga etibor bering.
#include <iostream.h>
#include <string.h>
using namespace std;
int main()
{ char s[10]; // s satrli o‘zgaruvchini e’lon qilish
return 0;
}
Yuqoridagi dastur tarkibida s[10] satr o‘zgaruvchisi 9 ta elementga va bitta nol
terminatoriga mo‘ljallangan. Satrlarni boshlang’ich qiymatlarini berish jarayonida uning
elementlar sonini berish shart emas. Agar satrlarni elementlar soni berilmasa dastur
avtomatik ravishda uning elementlar soniga boshlang’ich qiymatdagi elementlar sonidan
bitta ortiq qilib ta’minlaydi, chunki oxiriga bitta nol terminatorini hisobga oladi. Doim
satrlarni kiritishda uning elementlar soni e’lon qilinganidan oshib ketmasligi kerak aks
holda faqat e’lon qilingan elementlar soniga teng elementlarni saqlab qolinib qolganlari
olinmaydi.
Satrlarni kiritish jarayonida >> oqim bo‘yicha kiritishdan foydalanmasdan getline()
funksiyasidan foydalanish maqsadga muvofiq bo‘ladi. Agar oqim bo‘yicha kiritishdan
foydalanilsa unda probellar inkor qilinib satrni ikkinchi qismlari qabul qilinmaydi.
getline(s,n) funksiyasi ikkita parametrni o‘z ichiga oladi, birinchisi s satr o‘zgaruvchisi
ikkinchisi n satr elementlar soni. Getline funksiyasi satr elementlaridan ortiq qiymatlarni
ham kiritish imkoniyatini yaratadi, natijada satr elementlari ortadi. Yuqoridagi dastur
tarkibidagi s satrli o‘zgaruvchi faqat 9 ta elementni qbul qiladi, agar 9 tadan ortiq bo‘lsa
natija qaytarmaydi.](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_8.png?v=1)
![C++ dasturlash tilida strncat() funksiyasi yordamida satrlarni bir biriga faqat n ta
elementini ulash imkoniyati mavjud, strncat() funksiyasining umumiy ko‘rinishi
quyidagicha ko‘rinishda bo‘ladi.
strncat(satr1, satr2,n);
C++ dasturlash tilida strncat(satr1, satr2, n) funksiyasi satr2 ni n ta boshlang’ich
elementlarini satr1ni oxiriga ulaydi.
Misollardan namunalar:
1-Misol: Berilgan satrni ekranga chiqaring
#include <iostream.h>
#include <string.h>
using namespace std;
int main()
{ char s[10];
cin.getline(s,10);
cout<<s;
return 0;
}
2- Misol: Berilgan satr tarkibidagi elementlar sonini aniqlang.
#include <iostream.h>
#include <string.h>
using namespace std;
int main()
{ char s[10];
cin.getline(s,10);
x=sizeof(s);
cout<<x;
return 0;
}
3- Misol: Berilgan s satr elementlarini p satrga nusxalang.
#include <iostream.h>
#include <string.h>
using namespace std;
int main()
{ char s[100];
cin.getline(s,10);
char p[10];
strcpy(p,s);
cout<<p;
return 0;
}
4-Misol: Berilgan s satrni teskari tartiblang.
#include <iostream.h>
#include <string.h>
using namespace std;
int main()](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_10.png?v=1)
![{ char s[100];
cin.getline(s,10);
cout<<strrev(s);
return 0;
}
5-Misol: Berilgan s satrdan p belgini qidiring.
#include <iostream.h>
#include <string.h>
using namespace std;
int main()
{ char s[100];
cin.getline(s,10);
char p; cin>>p;
cout<<strchr(s,p);
return 0;
}](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_11.png?v=1)
![5-mustaqil ish
Mavzu: Murakkab turlarni algoritmlashtirish va dasturlash. Vektorlar va massiv
ma’lumotlarini algoritmlashtirish
Reja:
1. Bir o‘lchovli massivlar
2. Rand funksiyasi
3. Ikki o‘lchovli massivlar
Massivlar holatiga ko‘ra ikki turga bo‘linadi.
- Bir o‘lchovli massivlar;
- Ikki o‘lchovli massivlar;
Bir o‘lchovli massivlar ma’lumotlarni bir satrli ko‘rinishda saqlansa, ikki o‘lchovli
massivlar esa ma’lumotlarni satrlar satri ko‘rinishida saqlaydi.
Bir o‘lchovli massivlar
Odatda massivlar zarurat, katta hajmdagi tartiblangan, lekin chekli elementlarga oid
masalalarni hal etishda yuzaga keladi. Dastur ishlatilishi davomida massivlar aniq nomga
ega bo‘lishi va uning elementlari ma’lum bir turda bo‘lishi kerak. Bir o‘lchovli massivlar
kompyuter xotirasiga quyidagi shaklda saqlanadi.
o‘zgaruvchi qiymatlar
Yuqoridagi holat bo‘yicha massivlar kompyuter xotirasiga saqlanadi, bunda massivning
ixtiyoriy elementiga murojat qilish uchun uning indeks nomeri bo‘yicha murojat qilinadi.
Bir o‘lchovli massivlarni C++ dasturlash tilida bir nechta usullarda e’lon qilish mumkin.
Bir o‘lchovli massivlarni boshlang’ich qiymatlari berilmasdan C++ dasturlash tilida
quyidagicha e’lon qilinadi.
<tur> <massiv o‘zgaruvchisi>[<element soni>];
Massivni C++ dasturlash tilida e’lon qilish uchun, albatta, elementlar soni yoki massiv
elementlarining boshlang’ich qiymatlari berilishi kerak.
C++ dasturlash tilida bir o‘lchovli massivni e’lon qilish.
#include <iostream.h>
int main()
{ int a[10]; //butun turli 10ta elementli massiv
double b[10]; //haqiqiy turli 10ta elementli massiv
return 0;
}
Massivni umumiy ko‘rinishida birinchi o‘zgaruvchi turi, massiv o‘zgaruvchisi va massiv
elementlari soni yoziladi. Massiv elementlari soni, albatta, butun sondan iborat bo‘lishi
kerak, chunki elementlar soni, albatta, butun bo’lishi kerak. Massiv elementlari soni
biror bir ifoda yoki yagona o‘zgaruvchi bo‘lishi mumkin, bitta o‘zgaruvchi orqali
massivning umumiy indekslarini ifodalash mumkin. Massiv elementlarini tashkil qilish va
massiv elementlari ustida amallar bajarishni quyidagi masala orqali qaraymiz. Massiv
elementlarini tartib nomeri doimo 0 dan boshlanadi. C++ dasturlash tilida massiv
elementlari boshlang’ich qiymatlari berilgan holatlarda e’lon qilish quyidagicha.
<tur> <massiv o‘zgaruvchisi>[<element soni>]={boshlang’ich qiymatlar};
Bunda massiv elementlari oldindan berilgan holatlarda ishlatilishi mumkin.
Rand funksiyasi a a[1]
a[2]
a[3] a[4]
a[5]](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_17.png?v=1)
![Massiv elementlarini ixtiyoriy tasodifiy sonlar bilan to‘ldirish uchun C++ dasturlash tilida
imkoniyat yaratilgan. Agar massiv elementlarini tasodifiy sonlar bilan to‘ldirish kerak
bo‘lsa, tasodifiy sonlar bilan ishlash funksiyasiga murojat qilish kerak. C++ dasturlash
tilida tasodifiy sonlarni hosil qilish rand() funksiyasining umumiy ko‘rinishi quyidagicha
bo‘ladi.
Rand();
rand() funksiyasining vazifasi biror bir o‘zgaruvchiga yoki massiv elementlariga tasodifiy
sonni o‘zlashtirish uchun xizmat qiladi. Rand() funksiyasi foydalanuvchi tomonidan dastur
tarkibiga massiv elementlarini kiritishdan ozod qiladi.
Ikki o‘lchovli massivlar
C++ dasturlash tilida ba’zi hollarda bir nechta o‘lchamlari va turi bir xil bo‘lgan bir
o‘lchovli massivlardan foydalanishga to‘g’ri keladi. Bir nechta bir o‘lchovli massivlarni
birlashtirish natijasida ikki o‘lchovli massivlarni hosil qilish mumkin. Ikki o‘lchovli
massivlarni tarkibida ma’lumotlar satrlarning satri ko‘rinishida tasvirlanadi. Ikki o‘lchovli
massivlarning tarkibi ham bir o‘lchovli massivlar kabi tartiblangan bir turga mansub
bo‘lishi kerak. Ikki o‘lchovli massivlarga matematikadagi matritsalar misol bo‘lishi
mumkin. Ikki o‘lchovli massivlar tarkibidagi elementlar xuddi matritsani elementlari kabi
tasvirlanadi.
Ta’rif: Bir turga mansub bo‘lgan yagona nom bilan saqlangan matritsa ko‘rinishdagi
tartiblangan ma’lumotlar majmuasi ikki o‘lchovli massivlar deyiladi.
Ikki o‘lchovli massivning barcha elementlari aniq turga mansub bo‘ladi va uning
elementlari bir nechta satrlar ko‘rinishda bo‘ladi. Ikki o‘lchovli massivlar quyidagi
shaklda bo‘ladi.(
a
11 a
12 … a
1 n
a
21 a
22 … a
2 n
. . .
a
n 1 a
n 2 … a
nn )
Yuqoridagi shakldan ko‘rinib turibdiki ikki o‘lchovli massiv bir o‘lchovli
massivlarning bir nechtasi yoki matritsa ko‘rinishida tasvirlanar ekan. Ikki o‘lchovli
massivlarning kompyuter xotirasiga har bir satr uchun alohida tartib nomer bilan
saqlanadi. Ikki o‘lchovli massivlarning har bir elementiga o’zining indeksi bo‘yicha
murojat qilinadi.
Ikki o‘lchovli massivlarni C++ dasturlash tilida e’lon qilish va uning umumiy
ko‘rinishi quyidagicha.
<tur> <massivO‘zgaruvchisi>[<element1 soni>][<element2 soni>];
Quyidagi ikki o‘lchovli massiv berilgan bo‘lsin.
a =
( 1 2 3
4 5 6
7 8 9 )
a(3,3) massivning elementlariga C++ dasturlash tilida murojat qilish quyidagicha
ko‘rinishda bo‘ladi. a[1][1]=1, a[2][1]=2, a[3][1]=3, a[1][2]=4, a[2][2]=5, a[3]
[2]=6, a[1][3]=7, a[2][3]=8, a[3][3]=9.
C++ dasturlash tilida ikki o‘lchovli massivlarning elementlarini boshlang’ich qiymatlarini
quyidagi tartibda berilishi mumkin.
#include <iostream.h>
int main()](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_18.png?v=1)
![{ int a[][]={{1,2,3}{4,5,6}{7,8,9}};
return 0;
}
Misollardan namunalar:
1-Misol: 10 ta elementdan tashkil topgan massiv elementlarini hosil qilib, elementlarini
ikkiga ko‘paytirib ekranga chiqaring.
#include <iostream.h>
using namespace std;
int main()
{ int a[10];
for(int i=0;i<=9;i++)
cin>>a[i];
for(int i=0;i<=9;i++)
cout<<a[i]*2<<” ”;
return 0;
}
2-Misol: Butun sonlardan iborat a[8] massiv berilgan uning juft elementlarini 2ga
ko‘paytirib toq elementlarini 3 ga ko‘paytirib ekranga chiqaring.
#include <iostream.h>
using namespace std;
int main()
{ int a[8];
for(int i=0;i<=7;i++)
cin>>a[i];
for(int i=0;i<=7;i++)
if(a[i]%2==0) {cout<<a[i]*2<<” ”;}
else cout<<a[i]*3<<” ”;
return 0; }
3-Misol: n natural son va n ta elementdan tashkil topgan massiv berilgan uning eng katta
elementini aniqlang.
#include <iostream.h>
using namespace std;
int main()
{ int a[10];
for(int i=0;i<=9;i++)
cin>>a[i];
int max=a[0];
for(int i=0;i<=9;i++)
if(a[i]>max) max=a[i];
cout<<max;
return 0; }
4-Misol: A(n) massiv elementlarini tasodifiy sonlar yordamida hosil qilib uning juft
elementlarini ikkiga ko‘paytirib ekranga chiqaring
#include <iostream.h>
using namespace std;](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_19.png?v=1)
![int main()
{ int a[10];
for(int i=0;i<=9;i++)
a[i]=rand();
for(int i=0;i<=9;i++)
if(a[i]%2==0)
cout<<a[i]*2<<” “;
return 0; }
5-Misol: A(2,3) massiv berilgan uning elementlarini ikkiga ko‘paytirib ekranga chiqaring
#include <iostream.h>
int main()
{ int a[3][2];
for(int i=0;i<=2;i++)
for(int j=0;j<=1;j++)
cin>>a[j][i];
for(int i=0;i<=2;i++)
{
for(int j=0;j<=1;j++)
cout<<2*a[j][i]<<” ”;
cout<<”\n”; }
return 0; }](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_20.png?v=1)
![Misollardan namunalar:
1-Misol: Talabalar(familyasi, ismi, telefoni, reytingi, tug’ilgan yili) haqida ma’lumotlarga
asosan c++ dasturlash tilida struktura hosil qiling.
#include <iostream.h>
using namespace std;
struct talaba
{
char[20] fam; //familyani saqlovchi maydon
char[20] ism; //ismni saqlovchi maydon
char[20] tel; //telefonni saqlovchi maydon
int reyting; //reyting balini saqlovchi maydon
int tugy; //tug’ilgan vaqtini saqlovchi maydon
};
int main()
{
return 0;
}
2-Misol:
#include <iostream>
using namespace std;
struct MT
{ char Univernomi[10];
int Tbsoni;
int Kafedrasoni;
};
int main(void) {
struct MT p;
cout<<"Universitet nomini kiriting";
cin.get(p.Univernomi,10);
cout<<"Talabalar soni";
cin>>p.Tbsoni;
p.Kafedrasoni = 30;
cout << "Talabalar soni: " << p.Tbsoni << endl;
cout << "Kafedralar soni: " << p.Kafedrasoni << endl;
cout<<"Universitet nomi:"<<p.Univernomi;
return 0;}
3-Misol:
#include <iostream>
using namespace std;
struct Person
{
char name[50];
int age;
float salary;
};](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_23.png?v=1)
![int main()
{
Person p1;
cout << "Enter Full name: ";
cin.get(p1.name, 50);
cout << "Enter age: ";
cin >> p1.age;
cout << "Enter salary: ";
cin >> p1.salary;
cout << "\nDisplaying Information." << endl;
cout << "Name: " << p1.name << endl;
cout <<"Age: " << p1.age << endl;
cout << "Salary: " << p1.salary;
return 0;
}
4-Misol:
#include <iostream>
using namespace std;
struct Person
{
char fakultet[50];
char yonalish[50];
int guruh;
int ID;
};
int main()
{
Person p1;
cout << "Fakultetingiz: ";
cin.get(p1.fakultet, 50);
cout << "Yo'nalishingiz: ";
cin >> p1.yonalish;
cout << "Guruhingiz: ";
cin >> p1.guruh;
cout<<"Id ingiz:";
cin>> p1.ID;
cout << "\nDisplaying Information." << endl;
cout << "fakultet: " << p1.fakultet << endl;
cout <<"yunalish: " << p1.yonalish<< endl;
cout << "guruh: " << p1.guruh;
cout<<"Id:"<<p1.ID;
return 0;
}
5-Misol: Stekning juft o’rinda turgan elementlari o’chirilsin.
*- coding: utf-8 -*-](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_24.png?v=1)
!["""
Created on Sat May 14 10:32:29 2022
@author: admin
"""
class Steck:
"""Steck degan malimot turi"""
def init(self):
self.steck=[]
def Push(self,data):
"""Ruyhatga elimentlar qushish"""
# self.data=data
self.steck.append(data)
return f"Malimot qushildi"
def isEmpty(self):
"""Element bush emasligini tekshirish"""
return len(self.steck)==0
def Pop(self):
"""Ruyhatdan eliment sug'irib olish"""
if self.isEmpty():
return f"Malimot bosh"
else:
self.steck.pop()
def Peek(self):
"""Eng yuqoridagi qiymat elimentini kurish"""
if self.isEmpty():
return f"Tuplam ichida eliment yuq"
else:
return self.steck[-1]
def malimot(self):
"""toq urinda turgan malimotlardi chiqarish"""
return self.steck[1:10:2]
# def uchirish(self):
# """Juft urinda turgan malimotlardi uchirish."""
# # if m%2==0:
# for n in self.steck:
# n%2==0
# return self.steck.pop()
steck=Steck()](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_25.png?v=1)
![Reja:
1. Qo’yish tartiblash usuli (Insertion Sort)
2. Sheyker tartiblash usuli
3. Shell tartiblash usuli
Tartiblash – bu berilgan obyektlar to plamini muayyan tartibda qayta tartibga solishʻ
jarayoni. Saralashning maqsadi elementlarni topishni osonlashtirishdir.
Saralash algoritmi – bu ro yxatdagi elementlarni saralash algoritmi. Agar ro yxat
ʻ ʻ
elementida bir nechta maydon bo lsa, saralash amalga oshiriladigan maydon
ʻ saralash
kaliti deb ataladi. Amalda raqam ko pincha kalit sifatida ishlatiladi va ba’zi ma’lumotlar
ʻ
algoritm ishlashiga hech qanday ta’sir ko rsatmaydigan qolgan maydonlarda saqlanadi.
ʻ
1. Qo’yish tartiblash usuli (Insertion Sort)
Qo’yish tartiblash usuli (Insertion Sort) – bu sodda tartiblash algoritmi. Algo-ritmning har
bir qadamida massiv elementlaridan biri olinadi, qo’yish uchun joyi aniqlanadi va
qo’yiladi. Ta'kidlash kerakki, 1 ta elementdan iborat massiv tartiblangan hisoblanadi.
Algoritmning so’zli tavsifi murakkab ifodalanadi, lekin amalga oshirish juda ham sodda.
Har biri kishi, faoliyati davomida saralash algoritmidan foydalanadi. Masalan,
kupyuralarni tartiblashda, 100 so’mlik kupyurani olib, 10, 50 va 500 so’mlik kupyuralar
ketma-ket kelgan bo’lsin. Bunda faqat 50 dan 500 so’mlik kupyurani orasiga 100 so’mlik
kupyurani qo’yamiz. Amalga oshirish .Amalga oshirishni davom ettirishdan oldin, kirish
ma'lumot-larining formatini aniqlaymiz - masalan, bu butun (int) qiymatlar massivi
bo'lsin. Massiv elementlarini nomerlash 0 dan boshlanadi va n-1 bilan tugaydi. Algoritmni
C++ tilida amalga oshirish misolida qarab chiqamiz.
Algoritmning asosiy sikl 0-elementdan emas, balki 1-elementdan boshlanadi, chunki 1-
elementgacha bo'lgan element tartiblangan ketma-ketlik bo'ladi (bitta elementdan iborat
massiv tartiblangan hisoblanadi) va bu elementga nisbatan 0 nomerli bilan biz boshqasini
kiritamiz. Aslida kod:
for(int i=1;i<n;i++)
for(int j=i;j>0 && x[j-1]>x[j];j--) // toki j>0 va elementlarda j-1 > j
swap(x[j-1],x[j]); // massivning j va j-1 elementlari almashtiriladi
Tartiblashni amalga oshirish juda oddiy, faqat 3 qatordan iborat. swap funksiyasi x[j-1] va
x[j] elementlarini almashtiradi. Ichma-ich sikl elementni qo’yish uchun joyni aniqlaydi.
Algoritm tahlili
Qo’yish tartiblash usuli n2 murakkablik tartibiga ega, taqqoslashlar soni n*(n-1)/2
formulasi bo'yicha hisoblanadi. Bunga quyidagi kod bilan ishonch xosil qilish mumkin:
void Sort(int* arr,int n){
int counter=0;
for(int i=1;i<n;i++){
for(int j=i; j>0 && arr[j-1]>arr[j];j--){
counter++;
int tmp=arr[j-1];
arr[j-1]=arr[j];
arr[j]=tmp;
}
}
cout<<counter<<endl;
}](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_27.png?v=1)
![Samaradorlik
Agar massivning qismi tartiblangan va massiv elementlar soni ko‘p bo‘lmasa, ushbu
tartiblash eng samarali hisoblanadi. Agar elementlar 10 dan ko’p bo'lmasa, ushbu algoritm
eng yaxshi hisoblanadi.
2. Sheyker tartiblash usuli
Pufakchali tartiblash usuli ma'lum darajada yaxshilanishi va uning vaqt xarak-teristikasini
yaxshilashi mumkin. Masalan, tartiblashning bitta o'ziga xos xususi-yatini ko'rish
mumkin: massiv oxiridagi o’z o’rnida joylashmagan element bir o'tishda o'z joyiga
joylashadi va massiv boshida joylashgan element esa o'z joyiga joylashishi juda sekin
amalga oshiriladi. Barcha qarab chiqishlarni bir yo'nalishda olib borish shart emas. Buning
o'rniga, har bir keyingi qarab chiqishni teskari yo'nalishda amalga oshirilishi va
tartiblanmagan qismning quyi va yuqori chegaralarini belgilash mumkin, ya’ni qarab
chiqishning massivning oxirigacha emas, balki oldingi qarab chiqilgandagi oxirgi
almashtirishgacha tartiblash maqsadga muvofiq bo’ladi. Bunday holda, o'z joyidan uzoqda
bo'lgan elementlar tezda tegishli joyga o'tadi. Quyida massivlarning tartiblashning Sheyker
tartiblash usuli deb nomlangan pufakchali tartiblashning takomillashtirilgan versiyasi
keltirilgan:
left = 1 // tartiblanmagan qismning chap chegarasi
right = N // tartiblanmagan qismning o’ng chegarasi
tartib = false // true, agar massiv tartiblangan bo’lsa
toki emas tartib
tartib = true
i = left
//Massivning boshidan oxirigacha o’tish:
toki i < right
agar A[i] > A[i + 1] u holda
almashtir (А, i, i+1)
tartib = false
hal bo’ldi // (agar)
i = i + 1
sikl oxiri
// >=1 element o’ngdan o’zining joyiga qo’yildi
right = right – 1
agar emas tartib u holda
tartib = true
i = right
toki i > left
agar A[i] < A[i – 1] u holda
almashtir (A, i, i–1)
tartib = false
hal bo’ldi
i = i – 1
sikl oxiri
hal bo’ldi // (agar)
// >= 1 element chapdan o’zining joyiga qo’yildi
left = left + 1](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_28.png?v=1)
![sikl oxiri // emas tartib
Dasturi :
void shaker_sort (struct KeyData A [], int N)
{
int left = 0, right = N-1;
int sorted = 0;
while (!sorted && left < right) {
int i;
sorted = 1;
for (i = left; i < right; ++i) {
if (A[i+1] < A[i]) {
struct KeyData x = A[i+1];
A[i+1] = A[i];
A[i] = x;
sorted = 0;
}
}
right -= 1;
if (!sorted) for (i = left+1; i<=right; i++) {
if (A[i-1] > A[i]) {
struct KeyData x = A [i-1];
A[i-1] = A[i];
A[i] = x;
}
}
left += 1;
} // while
} // shaker sort
3. Shell tartiblash usuli
Bu tartiblash usuli 1959 yilda D. Shell tomonidan taklif qilgan. U xotiradan minimal
foydalanadi va tartiblashda yuqori tezligini ko'rsatadi. Shell usuli qo'-shish usuliga
o'xshash elementlarni taqqoslash va almashtirishlardan foydala-nadi, ammo
taqqoslanadigan elementlarning tartibi butunlay boshqacha tar-tibda bo’ladi. Shell
tartiblash usulining g’oyasi bir-biridan ma'lum step qadam masofada joylashgan
elementlarni tartiblashdan iboratdir. Keyin tartiblash step kichik qiymatlarida takrorlanadi
va Shell tartiblash jarayoni step = 1 bo’lganga tugaydi Tartiblash step qadamini tanlash
masalasi muhokamasi davom etmoqda. Shell quyidagi ketma-ketlikni taklif qildi: N/2,
N/4, N/8 ..., bu erda N - massivdagi tartiblanadigan elementlar soni. Shell tartiblash N
uzunlikdagi ketma-ketlikni tartiblash uchun log2N ga yaqin o'tishni talab qiladi
Misollardan namunalar
1-Misol: Butun sonlardan iborat navbatning juft elementlarini o’chirish dasturini
keltiramiz.
#include <iostream>
using namespace std;](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_29.png?v=1)
![int a[10],R=0,n;//bu yerda n navbatga kiritilishi kerak bo'lgan elementlar soni.
int kiritish(int s){
a[R]=s; R++;
}
int chiqarish(){ int
t=a[0];
for(int i=0;i<R-1;i++)
a[i]=a[i+1];
R--;
return t;
}
bool isEmpty(){
if(R==0) return true; else return false;
}
bool isFull(){
if(R>=10)return true;else return false;
}
int print(){ int i;
while(i<R){
int k=chiqarish();i++; cout<<k<<" ";
kiritish(k);}
}
int main(){ int n,s;
cout<<"n=";cin>>n; for(int
i=0;i<n;i++){ if(!isFull()){cin>>s;
kiritish(s);}
else{cout<<"navbat to'ldi"; n=i;break;}
}
cout<<"\nnavbat elementlari: "; print();
for(int i=0;i<n;i++){ s=chiqarish(); if(s%2!
=0)kiritish(s);](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_30.png?v=1)
![}
cout<<"\nnatijaviy navbat elementlari: "; print();
system("PAUSE");
}
Dasturning bajarilishi natijasi:
n=5 6
7
9
8
11
navbat elementlari: 6 7 9 8 11
natijaviy navbat elementlari: 7 9 11
2-Misol:
Dastur kodi
#include <iostream> using
namespace std;
int a[10],R=0,n;//bu yerda n stekka kiritilishi kerak bo'lgan elementlar soni. int
kiritish(int s){
a[R]=s; R++;
}
int chiqarish(){](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_31.png?v=1)
![R--;
return a[R];
}
bool isEmpty(){ if(R==0)
return true;
else return false;
}
bool isFull(){
if(R>=10) return true;else return false;
}
int print(){
int i=0,c[n]; while(!isEmpty()){
c[i]=chiqarish(); cout<<c[i]<<" ";i++;}
for(int j=i-1;j>=0;j--) kiritish(c[j]);
}
int main(){ int n,s;
cout<<"n=";cin>>n; for(int
i=0;i<n;i++){
if(!isFull()){ cin>>s;
kiritish(s);}
else{cout<<"stek to'ldi"; n=i;break;}
}
cout<<"\nstek elementlari: "; print();
int b[n],k=0;
for(int i=0;i<n;i++){ s=chiqarish();
if(s%2!=0) b[k++]=s;
}
for(int i=k-1;i>=0;i--) kiritish(b[i]);
cout<<"\nnatijaviy stek elementlari: "; print();
system("PAUSE");](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_32.png?v=1)
![}
Dasturning bajarilishi natijasi:
n =5
6
7
9
8
11
stek elementlari: 11 8 9 7 6
natijaviy stek elementlari: 11 9 7
3-Misol:
Dastur kodi
#include <cstdlib>
#include <iostream> using namespace std; int a[10],n,R=0; bool isEmpty(){
if(R==0) return true; else return false;
}
bool isFull(){
if(R>=10) return true; else return false;
}
int kirit_left(int s){
if(isFull()){cout<<"\ndek to'ldi";n=R;return EXIT_SUCCESS;} for(int i=R;i>0;i--)
a[i]=a[i-1];
a[0]=s;R++;
cout<<"\nnatijaviy stek elementlari: "; print();
system("PAUSE");
}
Dasturning bajarilishi natijasi:
n =5
6
7
9
8
11
stek elementlari: 11 8 9 7 6
natijaviy stek elementlari: 11 9 7](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_33.png?v=1)
![3-Misol:
Dastur kodi
#include <cstdlib>
#include <iostream> using
namespace std; int
a[10],n,R=0; bool
isEmpty(){
if(R==0) return true; else return false;}
bool isFull(){
if(R>=10) return true; else return false;
}
int kirit_left(int s){
if(isFull()){cout<<"\ndek to'ldi";n=R;return EXIT_SUCCESS;} for(int
i=R;i>0;i--)
a[i]=a[i-1];
a[0]=s;R++;
}
int olish_left(){
if(isEmpty()){cout<<"\ndek bo'sh";return EXIT_SUCCESS;} int t=a[0];
for(int i=0;i<R-1;i++) a[i]=a[i+1];
R--;
return t;
}
int kirit_right(int s){
if(isFull()){cout<<"\ndek to'ldi";n=R;return EXIT_SUCCESS;} a[R]=s;R++;
}
int olish_right(){
if(isEmpty()){cout<<"\ndek bo'sh";return EXIT_SUCCESS;} R--;](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_34.png?v=1)
![return a[R];
}
int print(){
cout<<endl<<"dek ele-tlari=";
for(int i=0;i<R;i++)cout<<a[i]<<" "; cout<<endl;
}
int main(int argc, char *argv[])
{ int n,s;cout<<"n="; cin>>n;
for(int i=0;i<n;i++){
if(!isFull()){ cout<<"kirit=";cin>>s;
if(i>=n/2) kirit_right(s); else
kirit_left(s);}
else {cout<<"dek to'ldi\n";break;}
}
print();
int b[n/2],k=0,c[n/2],p=0;
while(!isEmpty()){
int q=olish_left(); if(q%2==0)
b[k++]=q; if(isEmpty()) break;
int p=olish_right(); if(p%2==0) b[k+
+]=p;
}
int i=0; while(i<k){
kirit_right(b[i]); i++;
}
print(); system("PAUSE"); return
EXIT_SUCCESS;
}
Dastur natijasi](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_35.png?v=1)
![Daraxtlar va zanjirlar . Bog ʻ langan graflarda minimal miqdordagi qirralar mavjud bo ʻ lsa , (|
EG | = n − 1
) ular daraxtlar sinfini tashkil etadi . Yuqorida rasmda bu G
6 va G7 daraxtga to ʻ g ʻ ri
keladi . Daraxtlar haqida keyingi mavzuda batafsil to ʻ xtalamiz . Bu y erda biz 16-rasmda P 4
sifatida belgilangan G 7 grafini qayd etamiz , bu daraxtning alohida holati va oddiy zanjir deb
ataladi .
Grafni tasvirlash usullari
Grafni tasvirlash uchun bir nechta usullardan foydalaniladi. Graflardan o tish uchun siz
ʻ
o zingizning muammoingizni eng samarali hal qiladiganlardan foydalanishingiz kerak.
ʻ
Ko pincha, tanlov qo shnilik matritsasi va qo shnilik ro yxati o rtasida bo ladi (quyidagi
ʻ ʻ ʻ ʻ ʻ ʻ
jadval ikkala yondashuvning samaradorligini taqqoslaydi). Shu bilan birga, o rnatilgan C-
ʻ
massivga tayanib, o zingizning ma’lumotlar tuzilmalaringizni modellashtirishingiz va STD-
ʻ
da mavjud bo lgan turli xil konteynerlardan foydalanishingiz mumkin.
ʻ
Qo shnilik matritsasi.
ʻ Qo shnilik matritsasini n-tartibli ʻ A=[ai,aj] nosimmetrik kvadrat
matritsa sifatida aniqlaymiz, unda a
i , j elementlar 1 ga teng, agar grafda {
vi,V j } qirrasi bo lsa, ʻ
ya’ni
vi va vj qo shni bo lsa, 0 ga teng, agar bunday qirra mavjud bo lmasa. ʻ ʻ ʻ
Ta’rifdan kelib chiqadiki, har qanday i uchun
∑
j = 1n
a
i , j = d ( v
i )
, har qanday j uchun
∑i=1
n
ai,j=d(vj)
va
∑
i = 1n
∑
j = 1n
a
i , j = 2 m
, ya’ni qo shnilik matritsasining har qanday qatori yoki ʻ
ustunidagi birlar soni grafning tegishli vertikal darajasiga teng va ularning umumiy soni
uning qirralarining ikki baravariga teng.
Misol sifatida –rasmda berilgan G
grafning A qo shnilik matritsasini
ʻ deg v
i darajalar
ketma-ketligini yozamiz.
Yo naltirilmagan grafda qo shnilik matritsasi
ʻ ʻ](https://docx.uz/documents/cb1658a4-b0d0-4eb0-9be0-e60e5d56db3e/page_44.png?v=1)
Algoritm va ma’lumotlar strukturasi