Savol: Matritsani matritsaga ko‘paytiring

Savol: Navbatsiz idish. Navbatdagi asosiy operatsiyalar.
1)Navbatda birinchi elementga teng barcha elementlar o„chirilsin.
#include
#include
using namespace std;
int main()
{
int n,x,b,y;
queue q1,q2,q;
cout<<"Queuetni o'lchamini kiriting:";
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>x;
q1.push(x);
q2.push(x);
}
b=q1.front();
while(!q2.empty())
{
if(b!=q2.front())
{
y=q2.front();
q.push(y);
}
q2.pop();
}
cout<<"Natija...\n";
while(!q.empty())
{
cout<q.pop();
}
}
2)Navbatda oxirgi elementga teng barcha elementlar o„chirilsin.
#include
#include
using namespace std;
int main()
{
int n,x,o,y;
queue q1,q2,q;
cout<<"Queuetni o'lchamini kiriting:";
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>x;
q1.push(x);
q2.push(x);
}
o=q1.back();
while(!q2.empty())
{
if(o!=q2.front())
{
y=q2.front();
q.push(y);
}
q2.pop();
}
cout<<"Natija...\n";
while(!q.empty())
{
cout<q.pop();
}
}
3)Navbat eng katta elementi o„chirilsin.
#include
#include
using namespace std;
int main()
{
int n,x,mx,y;
queue q1,q2,q;
cout<<"Queuega nechta element kiritasiz:";
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>x;
q1.push(x);
q2.push(x);
}
mx=q1.front();
while(!q1.empty())
{
if(mxmx=q1.front();
q1.pop();
}
while(!q2.empty())
{
if(mx!=q2.front())
{
y=q2.front();
q.push(y);
}
q2.pop();
}
cout<<"Natija...\n";
while(!q.empty())
{
cout<q.pop();
}
}

4)Navbat eng kichik elementi topilsin va uning o’rniga 0 joylashtirilsin.

#include
#include
using namespace std;
int main()
{
int n,x,mn,y;
queue q1,q2,q;
cout<<"Queuega nechta element kiritasiz:";
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>x;
q1.push(x);
q2.push(x);
}
mn=q1.front();
while(!q1.empty())
{
if(mn>q1.front())
mn=q1.front();
q1.pop();
}
while(!q2.empty())
{
if(mn!=q2.front())
{
y=q2.front();
q.push(y);
}
else
{
q.push(0);
}
q2.pop();
}
cout<<"Natija...\n";
while(!q.empty())
{
cout<q.pop();
}
5)Dekning har 2 ta elementidan keyin ularning yig„indisini joylang.
#include
#include
using namespace std;
int main()
{
int n,x,s=0,k=0;
cout<<"Nechta son kiritasiz:";
cin>>n;
deque d1,d2;
for(int i=0; i{
cin>>x;
d1.push_back(x);
}
while(!d1.empty())
{
if(!d1.empty())
{
x=d1.front();
d2.push_front(x);
d1.pop_front();
k++;
s+=x;
}
if(!d1.empty())
{
x=d1.front();
d2.push_front(x);
d1.pop_front();
k++;
s+=x;
}
if(k==2)
d2.push_front(s);
s=0;
k=0;
}
cout<<"Natija...\n";
while(!d2.empty())
{
cout<d2.pop_back();
}
}

6)Dekning o„rtasidagi element yoki elementlarni o„chiring.

#include
#include
using namespace std;
int main()
{
int n,x,k1,k2;
cout<<"Deque ga nechta element kiritasiz:";
cin>>n;
deque d1,d2;
for(int i=1; i<=n ;i++)
{
cin>>x;
d1.push_front(x);
}
if(n%2==0)
{
k1=int(n/2);
k2=int(n/2)+1;
}
else
{
k1=int(n/2)+1;
k2=int(n/2)+1;
}
for(int i=1; i<=n; i++)
{
if(i!=k1 and i!=k2)
{
x=d1.front();
d2.push_front(x);
d1.pop_front();
}
else
d1.pop_front();
}
cout<<"Natija...\n";
while(!d2.empty())
{
cout<d2.pop_front();
}
}


7)Dekning juft elementlari yig„indisini hisoblang.
#include
#include
using namespace std;
int main()
{
int n,x,s=0;
cout<<"Deque ga nechta element kiritasiz:";
cin>>n;
deque d;
for(int i=1; i<=n ;i++)
{
cin>>x;
d.push_front(x);
}
while(!d.empty())
{
x=d.front();
if(x%2==0 and x>0)
s+=x;
d.pop_front();
}
cout<<"Natija = "< }

8)Berilgan so’zning unli harflarini dekning chap tomonidan, undoshlarini o’ng tomondan kiriting.

#include
#include
#include
using namespace std;
int main()
{
string s;
cout<<"So'z kiriting:";
cin>>s; char x;
deque d;
for(int i=0; i{
x=s[i];
if(isalpha(x))
{
if(x=='A' or x=='a' or x=='O' or x=='o' or x=='I' or x=='i' or x=='U' or x=='u' or x=='E' or x=='e')
{
d.push_front(x);
}
else
{
d.push_back(x);
}
}
}
cout<<"Natija...\n";
while(!d.empty())
{
cout<d.pop_front();
}
}
5. Dinamik MT.
1)Stek eng kichik elementi o„chirilsin.
#include
#include
using namespace std;
int main()
{
int n,x,mn,y;
stack st1,st2,st;
cout<<"Stackni o'lchamini kiriting:";
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>x;
st1.push(x);
st2.push(x);
}
mn=st1.top();
st1.pop();
while(!st1.empty())
{
if(mn>st1.top())
mn=st1.top();
st1.pop();
}
while(!st2.empty())
{
if(mn!=st2.top())
{
y=st2.top();
st.push(y);
}
st2.pop();
}
cout<<"Natija...\n";
while(!st.empty())
{
cout<st.pop();
}
}

2)Stekda birinchi elementga teng barcha elementlar o„chirilsin.
#include
#include
using namespace std;
int main()
{
int n,x,b,y;
stack st1,st2,st;
cout<<"Stackni o'lchamini kiriting:";
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>x;
st1.push(x);
st2.push(x);
}
b=st1.top();
st1.pop();
while(!st2.empty())
{
if(b!=st2.top())
{
y=st2.top();
st.push(y);
}
st2.pop();
}
cout<<"Natija...\n";
while(!st.empty())
{
cout<st.pop();
}
}

3)Stek oxirgi elementiga teng barcha elementlar o„chirilsin.
#include
#include
using namespace std;
int main()
{
int n,x,o,y;
stack st1,st2,st;
cout<<"Stackni o'lchamini kiriting:";
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>x;
st1.push(x);
st2.push(x);
if(i==n)
o=x;
}
while(!st2.empty())
{
if(o!=st2.top())
{
y=st2.top();
st.push(y);
}
st2.pop();
}
cout<<"Natija...\n";
while(!st.empty())
{
cout<st.pop();
}
}

4)Stek eng katta elementi o„chirilsin.
#include
#include
using namespace std;
int main()
{
int n,x,mx,y;
stack st1,st2,st;
cout<<"Stackni o'lchamini kiriting:";
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>x;
st1.push(x);
st2.push(x);
}
mx=st1.top();
st1.pop();
while(!st1.empty())
{
if(mxmx=st1.top();
st1.pop();
}
while(!st2.empty())
{
if(mx!=st2.top())
{
y=st2.top();
st.push(y);
}
st2.pop();
}
cout<<"Natija...\n";
while(!st.empty())
{
cout<st.pop();
}
}

6. Xalqasimon bog‘langan ro’yhatlar.

Ro’yhat har uchinchi elementi o’chirilsin..

#include

#include
using namespace std;
int main()
{
int n,x,k=0;
cout<<"Ro'yxatga nechta element kiritasiz: ";
cin>>n;
list my,my1;
for(int i=0; i{
cin>>x;
my.push_back(x);
}
for(int i=1; i<=n; i++)
{
k++;
if(k%3!=0)
{
x=my.front();
my1.push_back(x);
my.pop_front();
}
else
my.pop_front();
}
cout<<"Har 3 elementi o'chirilgan ro'yxat..\n";
while(!my1.empty())
{
cout<my1.pop_front();
}
}

7. Chiziqsiz MT.
Grafning qo’shma matritsasini tuzing
#include
using namespace std;
class Graph {
private:
bool** adjMatrix;
int numVertices;
public:

Graph(int numVertices) {

this->numVertices = numVertices;

adjMatrix = new bool*[numVertices];

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

adjMatrix[i] = new bool[numVertices];

for (int j = 0; j < numVertices; j++)

adjMatrix[i][j] = false;}}

void addEdge(int i, int j) {

adjMatrix[i][j] = true;

adjMatrix[j][i] = true;}

void removeEdge(int i, int j) {

adjMatrix[i][j] = false;

adjMatrix[j][i] = false;}

void toString() {

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

cout << i << " : ";

for (int j = 0; j < numVertices; j++)

cout << adjMatrix[i][j] << " ";

cout << "\n";}}

~Graph() {

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

delete[] adjMatrix[i];

delete[] adjMatrix;}};

int main() {

Graph g(4);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.toString(); }

8. Rekursiv algoritmlar va ularning funksiyalari
1) void recurse()
{
... .. ...
recurse();
... .. ...
}


int main()
{
... .. ...
recurse();
... .. ...
}
Quyidagi rasmda o'zini qayta-qayta chaqirish orqali rekursiya qanday ishlashi ko'rsatilgan.
1-misol: Rekursiya yordamida sonning factorial
// Factorial of n = 1*2*3*...*n


#include
using namespace std;


int factorial(int);


int main() {
int n, result;


cout << "Enter a non-negative number: ";
cin >> n;


result = factorial(n);
cout << "Factorial of " << n << " = " << result;
return 0;
}


int factorial(int n) {
if (n > 1) {
return n * factorial(n - 1);
} else {
return 1;
}
}


Enter a non-negative number: 4
Factorial of 4 = 24

Faktorial dasturning ishlashi

Savol: Fibonachi sonini k-hadini topuvchi rekursiv funksiya tuzing.

#include

using namespace std;
long fib(int n)
{
if(n<=2)
return 1;
return fib(n-1)+fib(n-2);
}
int main()
{
long long k;
cout<<"K ni kiriting: ";
cin>>k;
cout<<"Natija: "<}

9. Daraxtsimon MT va ular ustida amallar. Muvozanatli ikki tomonlama daraxtlar
Ikkilik daraxtlar:
Agar har bir tugunning chiqish darajasi 2 dan kichik yoki teng bo'lsa, yo'naltirilgan daraxtda ikkilik daraxt deyiladi. Tugunlardan tashkil topgan daraxt (bo'sh daraxt) ham ikkilik daraxtdir. Ikkilik daraxt shaklda ko'rsatilgan:

Asosiy terminologiya:

Ildiz: Ikkilik daraxtda daraxtning ildizi deb ataladigan noyob tugun mavjud.

Chap bola: Ildizning chap tomonidagi tugun uning chap bolasi deb ataladi.

O'ng bola: ildizning o'ng tomonidagi tugun uning o'ng bolasi deb ataladi.
Videox

Ota-ona: Chap bola yoki o'ng bola yoki ikkalasiga ega bo'lgan tugun tugunlarning ota-onasi deb ataladi.

Birodarlar: bir ota-onaga ega bo'lgan ikkita tugun aka-uka deb ataladi.

Barg: Bolalari bo'lmagan tugunga barg deyiladi. Ikkilik daraxtdagi barglar soni bittadan (minimal) daraxtdagi uchlari sonining (maksimal) yarmigacha o'zgarishi mumkin.

Avlod: Agar tugun tugunning yoki shu tugunning boshqa avlodining farzandi bo'lsa, tugun boshqa tugunning avlodi deb ataladi. Daraxtdagi barcha tugunlar ildizning avlodlaridir.

Chap pastki daraxt: Ildizi ba'zi tugunning chap pastki daraxti bo'lgan pastki daraxt shu tugunning chap pastki daraxti deb ataladi.

Misol: Shaklda ko'rsatilganidek, daraxt uchun:

Qaysi tugun ildiz hisoblanadi?

Qaysi tugunlar barglar hisoblanadi?
Har bir tugunning asosiy tuguniga nom bering
To'liq ikkilik daraxt: To'liq ikkilik daraxt ikkilik daraxtdir, agar u oxirgidan tashqari barcha darajalarda mumkin bo'lgan tugunlarning maksimal soni chap tomonda bo'lsa. n ta tugunga ega bo'lgan to'liq binar daraxtning chuqurligi log2 n+1 ga teng.

Misol: Anjirda ko'rsatilgan daraxt to'liq ikkilik daraxtdir. To'liq ikkilik daraxt: To'liq ikkilik daraxt ikkilik daraxt bo'lib, unda barcha barglar bir xil darajada joylashgan va har bir barg bo'lmagan tugun ikkita bolaga ega.

10. Binar daraxtlar bilan ishlash.
Binar daraxt tasviri
Binar daraxtning tuguni ma'lumotlar qismi va bir xil turdagi boshqa tuzilmalar uchun ikkita ko'rsatgichni o'z ichiga olgan tuzilma bilan ifodalanadi.
struct node
{
int data;
struct node *left;
struct node *right;
};
// Binary Tree in C++


#include


#include


using namespace std;


struct node {
int data;
struct node *left;
struct node *right;
};


// New node creation
struct node *newNode(int data) {
struct node *node = (struct node *)malloc(sizeof(struct node));


node->data = data;


node->left = NULL;
node->right = NULL;
return (node);
}


// Traverse Preorder
void traversePreOrder(struct node *temp) {
if (temp != NULL) {
cout << " " << temp->data;
traversePreOrder(temp->left);
traversePreOrder(temp->right);
}
}


// Traverse Inorder
void traverseInOrder(struct node *temp) {
if (temp != NULL) {
traverseInOrder(temp->left);
cout << " " << temp->data;
traverseInOrder(temp->right);
}
}


// Traverse Postorder
void traversePostOrder(struct node *temp) {
if (temp != NULL) {
traversePostOrder(temp->left);
traversePostOrder(temp->right);
cout << " " << temp->data;
}
}


int main() {
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);


cout << "preorder traversal: ";
traversePreOrder(root);
cout << "\nInorder traversal: ";
traverseInOrder(root);
cout << "\nPostorder traversal: ";
traversePostOrder(root);
}
11. Muvozanatlangan binary daraxtlar
Balanslangan Binar daraxt
Ushbu qo'llanmada siz muvozanatli Binar daraxt va uning turli xil turlari haqida bilib olasiz. Shuningdek, siz C, C++, Java va Python tillarida muvozanatli ikkilik daraxtning ishchi misollarini topasiz.

Muvozanatli Binar daraxt, shuningdek, balandlik bo'yicha muvozanatli Binar daraxt deb ataladi, har qanday tugunning chap va o'ng pastki daraxtining balandligi 1 dan ko'p bo'lmagan farq qiladigan Binar daraxt sifatida aniqlanadi.

Daraxt/tugun balandligi haqida ko'proq ma'lumot olish uchun Tree Data Structure-ga tashrif buyuring. Quyida balandlik muvozanatli Binar daraxt uchun shartlar keltirilgan:

har qanday tugun uchun chap va o'ng pastki daraxt o'rtasidagi farq bittadan ko'p emas

chap pastki daraxt muvozanatli
o'ng pastki daraxt muvozanatli C++ misollari
Quyidagi kod daraxtning balandligi muvozanatlanganligini tekshirish uchun mo'ljallangan. // Checking if a binary tree is height balanced in C++


#include
using namespace std;


#define bool int


class node {
public:
int item;
node *left;
node *right;
};


// Create anew node
node *newNode(int item) {
node *Node = new node();
Node->item = item;
Node->left = NULL;
Node->right = NULL;


return (Node);
}


// Check height balance
bool checkHeightBalance(node *root, int *height) {
// Check for emptiness
int leftHeight = 0, rightHeight = 0;


int l = 0, r = 0;


if (root == NULL) {
*height = 0;
return 1;
}


l = checkHeightBalance(root->left, &leftHeight);
r = checkHeightBalance(root->right, &rightHeight);


*height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;


if (std::abs(leftHeight - rightHeight >= 2))
return 0;


else
return l && r;
}


int main() {
int height = 0;


node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);


if (checkHeightBalance(root, &height))
cout << "The tree is balanced";
else
cout << "The tree is not balanced";
}
12. Yo’naltirilgan va yo‘naltirilmagan binary daraxtlar
Ushbu mavzu bo'yicha ko'plab kitoblar va maqolalar mavjud. Ushbu maqolada men eng asosiy narsani aniq aytib berishga harakat qilaman.

Ikkilik daraxt-bu ma'lumotlarning ierarxik tuzilishi bo'lib, unda har bir tugun qiymatga ega (bu holda kalit ham) va chap va o'ng avlodlarga havolalar mavjud. Eng yuqori darajadagi tugun (hech kimning avlodi emas) ildiz deb ataladi. Avlodlari bo'lmagan tugunlar (ularning ikkala avlodi ham null) barglar deb ataladi.

Shakl. 1 ikkilik daraxt

Ikkilik qidiruv daraxti-bu qo'shimcha xususiyatlarga ega bo'lgan ikkilik daraxt: chap avlodning qiymati ota-onaning qiymatidan kam, o'ng avlodning qiymati esa har bir daraxt tuguni uchun ota-onaning qiymatidan katta. Ya'ni, ikkilik qidiruv daraxtidagi ma'lumotlar saralangan shaklda saqlanadi. Yangi tugunni kiritish yoki mavjud tugunni olib tashlash bo'yicha har bir operatsiya daraxtning tartiblangan tartibini saqlaydi. Elementni qidirishda kerakli qiymat ildiz bilan taqqoslanadi. Agar qidirilayotgan ildizdan kattaroq bo'lsa, unda qidiruv ildizning o'ng avlodida davom etadi, agar kamroq bo'lsa, chap tomonda, agar teng bo'lsa, qiymat topiladi va qidirish to'xtaydi.

Shakl. 2 ikkilik qidiruv daraxti
Balansli ikkilik qidiruv daraxti - bu logaritmik balandlikdagi ikkilik qidiruv daraxti. Ushbu ta'rif qat'iy emas, balki g'oyaviy. Qattiq ta'rif eng chuqur va eng sayoz barg chuqurligining farqi (AVL daraxtlarida) yoki eng chuqur va eng sayoz barg chuqurligining nisbati (qizil-qora daraxtlarda) bilan ishlaydi. Balansli ikkilik qidiruv daraxtida qidirish, kiritish va o'chirish operatsiyalari logaritmik vaqt ichida amalga oshiriladi (chunki ildizdan har qanday bargga yo'l logarifmdan oshmaydi). Balanssiz ikkilik qidiruv daraxtining degenerativ holatida, masalan, bo'sh daraxtga tartiblangan ketma-ketlik kiritilganda, daraxt chiziqli ro'yxatga aylanadi va qidirish, kiritish va o'chirish operatsiyalari chiziqli vaqt ichida amalga oshiriladi. Shuning uchun daraxtni muvozanatlash juda muhimdir. Texnik jihatdan, agar ushbu elementning kiritilishi muvozanat holatini buzgan bo'lsa, yangi element kiritilganda yog'och qismlarini burish orqali muvozanatlashtiriladi.

Shakl. 3 muvozanatli ikkilik qidiruv daraxti

Balansli ikkilik qidiruv daraxti yangi elementlarni kiritish va mavjudlarini o'chirish bilan almashinadigan elementlarni tezda qidirish zarur bo'lganda qo'llaniladi. Agar ma'lumotlar tuzilmasida saqlanadigan elementlar to'plami o'rnatilgan bo'lsa va yangi qo'shimchalar va o'chirishlar bo'lmasa, unda massiv afzalroqdir. Chunki qidirish bir xil logaritmik vaqt uchun ikkilik qidiruv algoritmi bilan amalga oshirilishi mumkin, ammo indekslarni saqlash va ulardan foydalanish uchun qo'shimcha xarajatlar yo'q. Masalan, C++ da set va map assotsiativ konteynerlari muvozanatli ikkilik qidiruv daraxti hisoblanadi.

Shakl. 4 haddan tashqari muvozanatsiz ikkilik qidiruv daraxti

Endi rekursiyani qisqacha muhokama qilamiz. Dasturlashda rekursiya-bu boshqa argumentlar bilan o'z-o'zidan funktsiyani chaqirish. Aslida, rekursiv funktsiya bir xil argumentlar bilan o'zini chaqirishi mumkin, ammo bu holda Stack overflow bilan tugaydigan cheksiz rekursiya tsikli bo'ladi. Har qanday rekursiv funktsiyaning ichida funktsiyadan chiqish, shuningdek, boshqa argumentlar bilan o'zini chaqirish yoki chaqirish sodir bo'ladigan asosiy holat bo'lishi kerak. Argumentlar nafaqat boshqacha bo'lishi kerak, balki funktsiya chaqiruvini asosiy holatga yaqinlashtirishi kerak. Masalan, faktorialni hisoblashning rekursiv funktsiyasi ichidagi qo'ng'iroq kichikroq argument bilan, daraxtni aylanib o'tishning rekursiv funktsiyasi ichidagi qo'ng'iroqlar esa ildizdan uzoqroq, barglarga yaqinroq tugunlar bilan o'tishi kerak. Rekursiya nafaqat to'g'ridan-to'g'ri (o'zini o'zi chaqirish), balki bilvosita ham bo'lishi mumkin. Masalan A sabab bo'ladi B, a B sabab bo'ladi A. rekursiya yordamida takroriy tsiklni, shuningdek ma'lumotlar strukturasining ishlashini taqlid qilish mumkin Stack (LIFO).