Ma’lumotlar tuzilmasi va algoritmlar

If (Lst==NULL){ p->ptr=NULL; Lst=p}
Lst

4. 
   Aks xolda, ya’ni ro’yhat bo’sh bo’lmasa, yangi yaratilayotgan element ptr maydoniga ro’yhatning 1-element adresini yozamiz :
   

p->ptr=Lst;

5. Ro’yhat boshi ko’rsatkichini yangi elementga to’girlaymiz:

Lst=p;

Stekka yangi element kiritish dastur kodini keltiramiz:

class Node{

public: int info;
Node* ptr; };
int main()
{ Node* Lst = NULL;
Node* p = new Node;
int numb; cout<<"son kiriting: ";
cin>>numb;
p->info = numb;
p->ptr = Lst;
Lst = p;

Stekdan element chiqarish amali ham huddi shu tomondan amalga oshiriladi:

Dastur kodini keltiramiz:

Node* p = new Node;

if (Lst == NULL)
cout<<"ro'yhat bo'sh";
else { p = lst;
lst = p->next ;
delete(p);

1. 
   rasm. Stekning bog’langan ro’yxatda amalga oshirilishi
   

B- rasm. Navbatni bog’langan ro’yxatda amalga oshirilish dasturi
NAZORAT SAVOLLARI

1.Stek qanday tuzilma

2.Navbat qanday tuzilma
3. Stekni massiv ko’rinishida e’lon siling
4. Navbatni massiv ko’rinishida e’lon siling
5. Navbatni ro/yxat ko’rinishida e’lon siling
6. Stekni ro/yxat ko’rinishida e’lon siling
7. Stekka yangi element kiritish algoritmini ayting
8. Navbatga yangi element kiritish algoritmini ayting
9 Stekdan yangi element chiqarish algoritmini ayting
10. Navbatdan yangi element chiqarish algoritmini ayting


Adabiyotlar


Asosiy:
1. Adam Drozdek. Data structures and algorithms in C++. Fourth edition. Cengage Learning. 2013 y.
2. Кормен Т., Лейзерсон Ч., Ривест Р. «Алгоритмы. Построение и анализ», 2013 г.


Qo’shimcha:

1. 
   Г.Шилтд Самоучитель С++. 5-е издание. “БХВ Петербург” 2010 г.
   
2. 
   Вирт Н. Алгоритмы и структуры программы//М., Оберон, 2010 г.
   
3. 
   Род Хаггарти «Дискретная математика для программистов» 2012 г.
   
4. 
   Томас Х.Кормен «Алгоритмы. Вводный курс» 2014 г.
   

11- MAVZU
Qidiruv binar daraxti. Qidiruv binar daraxtini qurish. Tugunlar qo‘shish va o‘chirish .
REJA

1. 
   Qidiruv binar daraxti tushunchasi
   
2. 
   Qidiruv binar daraxtini qurish.
   
3. 
   Binar daraxtda qidiruv, tugunlar qo‘shish va o‘chirish
   

Agar ajratib olingan elementlar qandaydir o’zgarmas to’plamni tashkil qilishsa, kelgusi qidiruvlar samaraliroq bo’lishi uchun ularni binar daraxt ko’rinishida ifodalash maqsadga muvofiq bo’lishi mumkin.

Quyida keltirilgan daraxtlarda binar qidiruvni ko’rib chiqaylik ( a)va b) chizma). Ikkala daraxt xam uchtadan elementga ega - k1, k2, k3 bo’lib, bu yerda k1. k3 elementni qidirish a) chizmada ikkita taqqoslashni talab qilsa, b) chizmada esa bitta ( bunda u ildizning kaliti).

Chizma a) Chizma b)

Biror bir yozuvni ajratib olish uchun zarur bo’lgan kalitlarni taqqoslashlar soni binar qidiruv daraxtidagi ushbu yozuv bosqichiga birni qo’shganiga teng.

Faraz qilaylik:
qidiruv argumenti key = k1 bo’lishi extimolligi - p1,
qidiruv argumenti key = k2 bo’lishi extimolligi – p3,
qidiruv argumenti key = k3 bo’lishi extimolligi – p3,
key < k1 bo’lishi extimolligi – q0,
k2 > key > k1 bo’lishi extimolligi – q1,
k3 > key > k2 bo’lishi extimolligi – q2,
key > k3 bo’lishi extimolligi – q3,
C1 - a) chizmadagi taqqoslashlar soni,
C2 - b) chizmadagi taqqoslashlar soni.

U holda r1+r2+r3+q0+q1+q2+q3 = 1

Biror bir qidiruvda kutilayotgan taqqoslashlar soni quyidagicha bo’ladi:
C1 = 2r1+1r2+2r3+2q0+2q1+2q2+2q3
C2 = 2r1+3r2+1r3+2q0+3q1+3q2+1q3
Biror bir berilgan kalitlar va extimolliklar to’plamida kutilayotgan taqqoslashlar sonini minimallashtiruvchi binar qidiruv daraxti mukammal deyiladi. Garchi daraxt yaratish algoritmi ancha sermashaqqat ish bo’lsada, biroq u yaratgan daraxtda qidiruvni amalga oshirish ancha samarali bo’ladi. Afsuski, ko’pincha, qidiruv argumenti extimolligi oldindan aniq bo’lmaydi.