Navbatni dasturda e'lon qilish quyidagicha

23. Navbat bu shunday tuzilmaki, u elementlar qo'shilishi bilan kengayib boradi va elementlarni faqatgina bir tomondan qabul qiladi. Stekdan farqli holda, navbat tuzilmasi har ikkala tomondan ham ochiq hisoblanadi, lekin element kiritish bir tomondan, chiqarish esa ikkinchi tomonidan amalga oshiriladi. Navbat FIFO(first in first out – birinchi kelgan birinchi ketadi) ko'rinishidagi tuzilmadir. Navbatda ham xuddi stekdagi kabi C++ da alohida kutubxona mavjud:
#include
Navbatni dasturda e'lon qilish quyidagicha:
Queue nav1;
Navbat ustida quyidagi amallar bajariladi:
- Clear() - navbatni tozalash.
- isEmpty() – navbatni bo'shlikka tekshirish
- enqueue(el)—el elementni navbatga joylashtirish
- dequeue() —navbatdan birinchi elementni olish
- firstEl() — navbatning birinchi elementini uni o'chirmasdan qaytaradi
Navbatda bajariladigan enqueue va dequeue amallari 7 rasmda keltirilgan. Steklardan farqli ravishda navbatlarda o'zgarishlar uning oxirida va boshida bo'lishi nazorat qilinishi lozim. Elementlar navbatga oxiridan joylashtiriladi, olish esa boshidan amalga oshiriladi.

24. Dek so'zi (DEQ - Double Ended Queue) ingliz tilidan olingan bo'lib 2 ta chetga ega navbat degan ma'noni bildiradi. Dekning o'ziga xos xususiyati shundan iboratki, elementlarni yozish va o'qishni har ikkala chetidan ham amalga oshirish mumkin. Dekni quyi chegaralari birlashtirilgan ikkita stek ko'rinishda qarash mumkin. Deklar bilan ishlash uchun ham C++ da alohida kutubxona mavjud:

#include Deque
dek1;
Dek ustida bajariladigan amallar:
· boshidan element kiritish. Push_front()
· Oxiridan element kiritish. Push_back()
▪ boshidan element chiqarish. pop_front()
▪ oxiridan element chiqarish. Pop_back()
▪ Empty() – bo'shlikka tekshirish
Dekka misol keltiramiz:
#include <iostream>
#include <deque>
int main (){
std::deque<int> mydeque (2,100);
mydeque.push_front (200);
mydeque.push_front (300);
std::cout << "mydeque contains:";
for (std::deque<int>::iterator it =
mydeque.begin(); it != mydeque.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
25. Tuzilmani tashkil etuvchi elementlar qat'iy tartiblanmagan bo'lsa, u holda bunday tuzilmaga chiziqsiz ma'lumotlar tuzilmasi deyiladi. Chiziqsiz ma'lumotlar tuzilmasida elementlar orasidagi munosabatlar ixtiyoriy bo'lishi mumkin. Chiziqsiz tuzilmani 3 ta farqli belgisini ajratish mumkin:
Tuzilmani xar bir elementi boshqa ixtiyoriy elementga murojaat qilish mumkin;
Tuzilmani berilgan elementiga mazkur tuzilmaning ixtiyoriy sondagi elementi murojaat qilishi mumkin;
Murojaatlar og'irlikga, hamda ierarxik ko'rinishga ega bo'lishi mumkin.
Chiziqsiz ma'lumotlar tuzilmasi klassifikatsiyasi:
Ro'yxatlar: chiziqsiz ikki bog'lamli, ko'p bog'lamli; Daraxtlar: binar daraxtlar, ko'po'lchamli daraxtlar; Graflar: yo'naltirilgan graf (orgraf), yo'naltirilmagan graf (graf), gipergraf. Umuman olganda daraxt ham yo'naltirilgan graf bo'ladi.

=
26. Ro'yhatlarning kamchiligi bor: elementlarni qidirishda qat'iy ketma-ketlik mavjud. Qidirish davom ettiriladi toki element topilguncha yoki ro'yhat oxiriga yetguncha, agar element topilmasa. Shu masalani hal qilish uchun yuqorida aytilgan skip listlardan foydalaniladi. Bunda elementni qidirishda yoki unga murojaat qilishda ungacha bo'lgan xar bir element ko'rib chiqilmaydi. n ta elementdan iborat skip list berilgan bo'lsin. Unda xar bir 1 ≤ k ≤ [lg n] va 1 ≤ i ≤ [n/2^(k–1)]–1 shartni qanoatlantiruvchi k va i uchun 2^(k-1)*i o'rinda turgan tugun 2^(k-1)*(i+1) o'rinda turgan tugunni ko'rsatadi. Bu degani, xar bir 2 tugun 2 tugun keyin turgan elementga murojaat qiladi va xar bir 4-element o'zidan 4 ta keyin turgan elementga murojaat qiladi va h.k.

Ushbu rasmdagi kabi skip listdan elementni qidirish algoritmi quyidagicha: (bizga ma'lumki, skip list tartiblangan) qidiruv eng yuqori ko'rsatkich bilan boshlanadi
• Agar oldinda el elementdan qiymat jixatidan kichik elementlar chiqsa, qidiruv davom ettiriladi, toki el dan katta element chiqqunga qadar.
• Agar oldinda el dan katta element chiqadigan bo'lsa, bitta oldingi elementga qaytiladi va qidiruv bitta past darajadagi ko'rsdatkich bilan davom ettiriladi.
• Qidiruv element topilguncha davom ettiriladi yoki eng pastki darajadagi ko'rsatkich bilan oraliqdagi elementlarning xammasi tekshirilib chiqqanda to'xtatiladi.

27.