Laboratoriya ishi -19 Mavzu: Navbat tuzilmasi. Ro’yxatlar yordamida navbatni amalga oshirish. Ishdan maqsad

#include

using namespace std;

int main() da boshlab

{

deque dq;

dq.push_back(1);

dq.push_back(10);

dq.push_back(100);

dq.push_back(50);

dq.push_back(40);

dq.push_back(23);

dq.push_back(6);

cout << "Dek elementlari: ";

for (auto it = dq.begin(); it != dq.end(); it++)

cout << *it << " ";

cout << "\Dekning maksimal qiymati: " << dq.max_size();

return 0;

}

Natija quyidagicha:



Misol uchun: Deque dan foydalanib ikkita c1 va c2 navbat elon qiling c1 navbatga 6 ta elemantni qo'shing, d1 o'zgaruvchi elon qiling uni ro'yhatga bog'lang va natijada bizga d1 ro'yhat elemetlarini o'zlashtirsin, c1 boshidagi 3 ta c1 elementlarini o'zlashtirsin, c1 oxirgi 2 ta elementlarini, c1 istalgan 4 sonini 7 marta doskaga chiqarib bersin.

#include

#include

#include

int main()

{

using namespace std;

deque c1, c2;

deque ::const_iterator cIter;

c1.push_back(10);

c1.push_back(20);

c1.push_back(30);

c2.push_back(40);

c2.push_back(50);

c2.push_back(60);

deque d1{ 1, 2, 3, 4 };

initializer_list iList{ 5, 6, 7, 8 };

d1.assign(iList);

cout << "d1 = ";

for (int i : d1)

cout << i;

cout << endl;

cout << "c1 =";

for (int i : c1)

cout << i;

cout << endl;

c1.assign(++c2.begin(), c2.end());

cout << "c1 =";

for (int i : c1)

cout << i;

cout << endl;

c1.assign(7, 4);

cout << "c1 =";

for (int i : c1)

cout << i;

cout << endl;

}

Labarotoriya ishlari uchun topshiriqlar.

19. “Kalit” nomli dek e’lon qilinsin hamda ushbu dekda “Salom” so’zi ekranga chiqarilishi uchun kerakli tip va qiymatlar qo’llanilsin.

Kod qismi:

#include

using namespace std;

int main()

{

deque dq;

dq.push_back(5);

dq.push_back(25);

dq.push_back(18);

dq.push_back(33);

cout << "\ngquiz.pop_back() : ";

dq.pop_back();
cout << "Dek elementlari: ";

for (auto it = dq.begin(); it < dq.end(); it++)

cout << *it << " ";
return 0;

}

Natija:

LABORATORIYA ISHI - 21

Dastur kodi:

#include

#include

#include

using namespace std;

int main(int argc, char *argv[])

{

string uzb[]={"ruchka","kitob","qalam","sumka"};

string rus[]={"ruchka","kniga","karandash","rugzag"};

string eng[]={"pen","book","pencil","bag"};

string soz,til;

string massiv[4];

cout<<"TILNI KIRITING: "; cin>>til;

if (til=="uzb")

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

{ massiv[i]=uzb[i]; } }

if (til=="rus")

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

{ massiv[i]=rus[i]; }}

if (til=="eng")

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

{ massiv[i]=eng[i]; }}

int s;

cout<<"so'zni kiriting: "; cin>>soz;

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

{ if (soz!=massiv[i])

{ cout<<"xxxxxxxxxxx"<

else

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

{ if (soz==massiv[i])

{ s=i; } }

if (til=="uzb")

{cout<<"RUS: "<

if (til=="rus")

{cout<<"UZB: "<

if (til=="eng")

{cout<<"RUS: "<

}}

system("PAUSE");

return EXIT_SUCCESS;}

Dastur natijasi:



LABORATORIYA ISHI -22

Mavzu: Binar daraxtlar. Daraxt balandligi va ko’ruv.
Ishdan maqsad. Ushbu laboratoriya ishida talabalar Binar daraxtlar tushunchasi bilan tanishib chiqishi hamda daraxt balandligi va ko’ruvni ishlashni o’rganishlari kerak.

Qo’yilgan masala. Talabalar topshiriq variantiga mos ravishda binar darxtlar ustida berilgan amallar bilan ishlash ko’nikmasiga ega bo’lishlari kerak.

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.
  

Daraxtlarni aks ettirish uchun ikkita usul mavjud: massivni ishlatadigan ketma-ket tasvirlangan bog'langan ro'yxatni ishlatadigan dinamik tugunni namoyish etish.

Bu erda biz ikkitomonlama daraxtlarni massivli tasvirlash haqida gaplashamiz. Buning uchun biz BT tugunlarini raqamlashimiz kerak. Ushbu raqamlash 0 dan (n-1) yoki 1 dan n gacha boshlanishi mumkin.

Massivdagi tugunlar va ularning ota-ona va bola tugunlarining pozitsiyalarini chiqaramiz.

Biz 0 indeksiga asoslangan ketma-ketlikni qo'llaganimizda,

Faraz qilaylik, ota tugun - bu p indeks.

Keyin, left_child tuguni (2 * p) + 1 indeksida.

Right_child tuguni (2 * p) + 2 indeksida.

Ildiz tuguni 0 indeksida.

left_child 1-indeksda.

Right_child 2-indeksda.

Biz 1 indeksga asoslangan ketma-ketlikni ishlatganimizda, deylik, ota tugun p indeksda, Right_node indeksda (2 * p).

Left_node (2 * p) +1 indeksida.

Ildiz tuguni indeks 1da.

left_child indeks 2da.

Right_child 3-indeksda.

19-topshiriq.

Quyidagi maydonlardan STUDENT nomi bilan yozuv hosil qiling:

• 
  Familiya va ismi;
  
• 
  Gurux raqami;
  
• 
  Fakultet;
  
• 
  Bahosi;
  
• 
  Manzili;
  

Navbatdagi amallarni bajaruvchi dasturni tuzing:

• 
  6 ta STUDENT toifasidagi yozuv klaviatura orqali massiv ma’lumotlarini kiriting;
  
• 
  Farg’onalik talabalar ro’yxati ekranga chiqarilsin.
  
• 
  Agar bunday bahoga ega talabalar bo’lmasa, u xolda ekranga “Farg’onalik talabalar topilmadi” xabari matni chiqarilsin.
  

Kod qismi:

tree = [None] * 10

def root(key):

if tree[0] != None:

print("Tree already had root")

else:

tree[0] = key

def set_left(key, parent):

if tree[parent] == None:

print("Can't set child at", (parent * 2) + 1, ", no parent found")

else:

tree[(parent * 2) + 1] = key

def set_right(key, parent):

if tree[parent] == None:

print("Can't set child at", (parent * 2) + 2, ", no parent found")

else:

tree[(parent * 2) + 2] = key

def print_tree():

for i in range(10):

if tree[i] != None:

print(tree[i], end="")

else:

print("-", end="")

print()

# Driver Code

root('K')

set_right('L', 0)

set_left('P', 1)

set_right('M',2)

set_right('N', 1)

set_right('O', 2)

set_left('S',3)

set_left('A',3)

set_right('D',3)

set_left('B',4)

set_right('v',4)

set_left('I',4)

print_tree()
Natija:


LABORATORIYA ISHI - 23

Mavzu: Muvozanatlangan binar daraxtlar.
Ishdan maqsad. Ushbu laboratoriya ishida talabalar binar daraxtlar tushunchasi bilan tanishib chiqishi va inorder preorder hamda postorder ko’rinishdagi tartiblar bilan tanishib chiqishlari kerak

Qo’yilgan masala. Talabalar topshiriq variantiga mos ravishda binar darxtlar ustida berilgan amallar bilan ishlash ko’nikmasiga ega bo’lishlari kerak.

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.
  

Ularnibosibo'tishningfaqatbittamantiqiyusulibo'lganchiziqlima'lumotlartuzilmalaridan (Array, bog'langanro'yxat, navbat, stekvaboshqalar) farqlio'laroq, daraxtlarturliyo'llarbilano'tishimumkin. Quyida daraxtlardan o'tishning odatda foydalaniladigan usullari keltirilgan.

Chuqurlikdagi birinchi o'tish joylari:

(a) Inorder (chap, ildiz, o'ng): 4 2 5 1 3

(b) Oldindan buyurtma berish (Ildiz, chap, o'ng): 1 2 4 5 3

(c) Postorder (chap, o'ng, ildiz): 4 5 2 3 1

Birinchi yoki darajadagi buyurtmaning kengligi: 1 2 3 4 5

Inorder-dan foydalanish

Ikkilik qidiruv daraxtlari (BST) bo'lsa, Inorder traversal tugunlarni kamaymaydigan tartibda beradi. BST tugunlarini ko'payib bormaydigan tartibda olish uchun Inorder traversal s teskari yo'naltirilgan Inorder traversalining o'zgarishi mumkin.

Masalan: Yuqorida keltirilgan rasm uchun inorder o'tish 4 2 5 1 3 ga teng.
Preorder-dan foydalanish

Daraxtning nusxasini yaratish uchun oldindan buyurtma o'tish. Oldindan buyurtma o'tish, shuningdek, ifoda daraxtining prefiksini olish uchun ishlatiladi. Iltimos, prefiks iboralari nima uchun foydali ekanligini bilish uchun http://en.wikipedia.org/wiki/Polish_notation ga qarang.

Masalan: Yuqoridagi rasm uchun oldindan buyurtma o'tish 1 2 4 5 3.
Postorder dan foydalanish

Postorder traversal daraxtni yo'q qilish uchun ishlatiladi. Tafsilotlar uchun daraxtni yo'q qilish uchun savolga qarang. Postorder traversal, shuningdek, ifoda daraxtining postfix ifodasini olish uchun foydalidir. Iltimos, postfiks ifodasini ishlatish uchun http://en.wikipedia.org/wiki/Reverse_Polish_notation ga qarang.

Misol: Yuqoridagi rasm uchun postorder o'tish 4 5 2 3 1 ga teng.

Binary daraxt ishlab chiqilsin ildizi birga chap tuguni 2 ga o'ng tuguni 3 ga va hakazo shu daraxtni muvazanatlanganmi yoki muvozanatlanmaganmi shuni ekranga chiqarib beruvchi dasturni yozing

#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 << "bu daraxt muvozanatlangan";

else

cout << "bu daraxt muvozanatlanmagan";

}

Labarotoriya ishlari uchun topshiriqlar.

19.Binar daraxt tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga Muvozanatlangan yoki Muvozanatlanmagan chiqarilsin.

Kod qismi:

from binarytree import Node

root = Node(3)

root.left = Node(2)

root.left.left=Node(7)

root.left.right=Node(8)

root.left.left.left=Node(4)

root.left.left.right=Node(6)

root.right = Node(5)

root.right.left=Node(9)

root.right.right.right=Node(12);print(root)

Natija:



LABORATORIYA ISHI - 24

Mavzu: Graf tushunchasi.Tasvirlash usullari
Ishdan maqsad. Ushbu laboratoriya ishida talabalar Graf tushunchasi bilan tanishib chiqishi kerak

Qo’yilgan masala. Talabalar topshiriq variantiga mos ravishda graf ustida berilgan amallar asosan bog’langan ro’yhatlar bilan ishlash ko’nikmasiga ega bo’lishlari kerak.

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.
Graf - bu ba'zi bir juft ob'ektlar havolalar orqali bog'langan ob'ektlar to'plamining tasviriy tasviri. O'zaro bog'langan ob'ektlar tepaliklar deb nomlangan nuqtalar bilan ifodalanadi va tepaliklarni bog'laydigan bog'lanishlar qirralar deb nomlanadi.

Rasmiy ravishda, grafik - bu juftlik to'plami (V, E), bu erda V - tepaliklar to'plami va E - qirralarning to'plami, tepalik juftlarini bir-biriga bog'lab turadi. Quyidagi grafaga qarang

Yuqoridagi grafikada,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

Grafik ma'lumotlar tuzilishi

Matematik grafikalar ma'lumotlar tarkibida aks ettirilishi mumkin. Biz tepaliklar massivi va qirralarning ikki o'lchovli massivi yordamida grafani namoyish eta olamiz. Davom etishdan oldin, keling, ba'zi muhim shartlar bilan tanishib chiqamiz -

Vertex - Grafikning har bir tuguni vertex sifatida ifodalanadi. Quyidagi misolda belgilangan doira tepaliklarni aks ettiradi. Shunday qilib, A dan G gacha cho'qqilar. Biz ularni quyidagi rasmda ko'rsatilgandek massiv yordamida namoyish etishimiz mumkin. Bu erda A indeksni 0 bilan aniqlash mumkin, B 1 indeks yordamida va boshqalarni aniqlash mumkin.

Edge - Edge ikki tepalik orasidagi yo'lni yoki ikkita tepalik orasidagi chiziqni anglatadi. Quyidagi misolda A dan B gacha, B dan C gacha va hokazo chiziqlar qirralarni bildiradi. Quyidagi rasmda ko'rsatilgandek massivni ko'rsatish uchun biz ikki o'lchovli massivdan foydalanishimiz mumkin. Bu erda AB 0 qatorda 1, ustun 1da, BC 1 qatorda 1da, 2-ustunda va hokazolarda, boshqa kombinatsiyalarni 0 shaklida ushlab turilishi mumkin.

Yaqinlik - Ikkala tugun yoki tepaliklar bir-biriga chekka orqali ulangan bo'lsa, qo'shni. Quyidagi misolda B A bilan, C B bilan qo'shni va hokazo.

Yo'l - yo'l ikki tepalik orasidagi qirralarning ketma-ketligini anglatadi. Quyidagi misolda ABCD A dan D gacha bo'lgan yo'lni aks ettiradi.

Asosiy operatsiyalar

Quyida grafikaning asosiy asosiy operatsiyalari keltirilgan :

Vertex qo'shish - Grafikka vertex qo'shadi.

Edge qo'shish - Grafikning ikkita tepasi orasidagi chekka qo'shiladi.

Display Vertex - Grafika tepaligini namoyish etadi.

Grafika haqida ko'proq bilish uchun, iltimos, Grafik nazariyasi qo'llanmasini o'qing. Grafani bosib o'tish haqida kelgusi boblarda bilib olamiz.

Grafik - bu quyidagi ikki komponentdan iborat ma'lumotlar tuzilishi.

1. Tugunlar deb ham ataladigan cheklangan tepaliklar to'plami.

2. Shaklning tartiblangan juftligining cheklangan to'plami (u, v) chekka deb nomlanadi. Juftlik buyurtma qilingan, chunki (u, v) yo'naltirilgan grafik (di-grafik) holatida (v, u) bilan bir xil emas. Shaklning juftligi (u, v) u vertikaldan v tepaga qadar bir chekka borligini bildiradi, qirralarning vazni / qiymati / narxi bo'lishi mumkin.

Grafikalar hayotdagi ko'plab dasturlarni namoyish qilish uchun ishlatiladi: Grafikalar tarmoqlarni aks ettirish uchun ishlatiladi. Tarmoqlar shahar yoki telefon tarmog'idagi yoki elektron tarmoqdagi yo'llarni o'z ichiga olishi mumkin. Graflar, shuningdek, LinkIn, Facebook kabi ijtimoiy tarmoqlarda qo'llaniladi. Masalan, Facebook-da har bir odam vertex (yoki tugun) bilan ifodalanadi. Har bir tugun tuzilishga ega va shaxs identifikatori, ismi, jinsi va joyi kabi ma'lumotlarni o'z ichiga oladi. Grafikning ko'proq ilovalari uchun buni ko'ring.

Quyida 5 ta tepalikka ega bo'lgan yo'naltirilmagan grafikaga misol keltirilgan.

Quyidagi ikkitasi grafikaning eng ko'p ishlatiladigan tasvirlari.

1. Yaqinlik matritsasi

2. Yaqinlik ro'yxati

Shuningdek, boshqa hodisalar ham mavjud, "Intsident Matrix" va "Incident List". Grafik tasvirini tanlash vaziyatga xosdir. Bu butunlay bajariladigan operatsiyalar turiga va ulardan foydalanish qulayligiga bog'liq.

Yaqinlik ro'yxati:

Bir qator ro'yxatlar ishlatiladi. Massivning kattaligi tepalar soniga teng. Massiv bir qator bo'lsin []. Kirish massivi [i] ith vertexga qo'shni bo'lgan tepalar ro'yxatini aks ettiradi. Ushbu tasvir vaznli grafikani ko'rsatish uchun ham ishlatilishi mumkin. Qirralarning og'irliklari juftliklar ro'yxati sifatida ifodalanishi mumkin. Yuqorida keltirilgan grafikning qo'shni ro'yxati ko'rsatilgan.


Labarotoriya ishlari uchun topshiriqlar.
Labarotoriya ishlari uchun topshiriqlar.

19.Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.

Nazorat savollar:

1. 
   Graf haqida tushuncha va uning turlari?
   
2. 
   Graflarni tasvirlab tushintirib bering?
   
3. 
   Vertex qanday usulda foydalaniladi va unga misol keltiring?
   
4. 
   Vertex va egde o`rtasidagi farqni misollarlar yordamida tushuntiring?