Algoritmlarni loyihalashtirish fanidan 4 – Laboratoriya ishi Mavzu: Ustuvor navbatlar ustida bajariladigan amallar. Ishdan maqsad

Algoritmlarni loyihalashtirish fanidan

4 – Laboratoriya ishi

Mavzu: Ustuvor navbatlar ustida bajariladigan amallar.

Ishdan maqsad: Ustuvor navbatlarni o’rganib chiqish va ularni ustida amallar ishlab chiqish.

Masalaning qo’yilishi: Talaba variant bo’yicha berilgan misollarni ixtiyoriy dasturlash tilida ishlab chiqadi.

Ma’lumotlar tuzilmalari.

Queue (Navbat) - Queue ham Stack singari chiziqli ma’lumot tuzilmasi bo’lib, hayotdagi oddiy navbat singari ishlaydi. Shu sababli Stackdan farqli o’laroq Queueda eng oxirgi qo’shilgan elementga emas birinchi qo’shilgan elementga birinchi bo’lib “xizmat ko’rsatiladi”. Operatsiyalarni bunday ko’rinishda amalga oshirilishi esa FIFO (First In First Out) deb ataladi. Queueni tasavvur etish uchun quyidagi rasmning o’zi yetarli deb o’ylayman.

Queuega dasturiy misollar sifatida printerga narsalarni chop qilishni uzatishni, yoki protsessor operatsiyalarni amalga oshirish jarayonini misol keltirish mumkin (protsessor ishlashi har doim ham FIFO ga asoslanmaydi). Yanayam qiziqrog’i hammamiz yoshligimizda (yoki hozir ham) o’ynashni yaxshi ko’rgan iloncha o’yinini Queuega misol qilish mumkin.

Queueda biz ikkita tugun adresini xotirada saqlashimiz kerak bo’ladi. Navbat boshida turgan element uchun front, eng oxirgi element uchun rear yoki back.

Queue ustidagi asosiy amallar

• 
  Elementni navbat oxiriga qo’shish (Enqueue)
  
• 
  Elementni navbat boshidan chiqarib olish. Element o’chiriladi (Dequeue)
  
• 
  Navbat boshidagi elementni ko’rish. Element o’chirilmaydi (Peek)
  
• 
  Navbatni bo’shlikka tekshirish (isEmpty)
  

Priority Queue – Bu oddiy queue ga o’xshash lekin unda ozroq farq qiladi.

Oddiy Queue da First-In-First-Served prinsipi amal qilsa Ustuvor navbatlarda esa har bir massiv elementida ustuvorlikni ofidalovchi yana bir qiymat mavjud bo’ladi. Va aynan shu element queue ni elementlarini ifodalab beradi.

Priority Queue ni asosiy amallari:

• 
  insert / enqueue - navbatning orqa tomoniga element qo'shing.
  
• 
  Remove / dequeue - navbatning old qismidan biror narsani olib tashlang.
  

Bu strukturada massivga element qo’shish va ularni o’chirish quyidagi ko’rinishda amalga oshiriladi:

Ustuvor navbatlar asosida ishlovchi massivda element qo’shish java dasturlash tilida quyidagicha ifodalanadi:

void insert(int data){

int i = 0;

if(!isFull()){

// agar navbat bo’sh yoki to’lmagan bo’lsa

if(itemCount == 0){

intArray[itemCount++] = data;

}else{

//

for(i = itemCount - 1; i >= 0; i-- ){

//

if(data > intArray[i]){

intArray[i+1] = intArray[i];

}else{

break;

}

}

//

intArray[i+1] = data;

itemCount++;

}

}

}
int removeData(){

return intArray[--itemCount];

}
int main() {

/* */

insert(3);

insert(5);

insert(9);

insert(1);

insert(12);
// ------------------

// index : 0 1 2 3 4

// ------------------

// queue : 12 9 5 3 1

insert(15);
// ---------------------

// index : 0 1 2 3 4 5

// ---------------------

// queue : 15 12 9 5 3 1

if(isFull()){

printf("Queue to’lgan!\n");

}
//

int num = removeData();

printf("Element o’chirildi: %d\n",num);

// ---------------------

// index : 0 1 2 3 4

// ---------------------

// queue : 15 12 9 5 3
//

insert(16);

// ----------------------

// index : 0 1 2 3 4 5

// ----------------------

// queue : 16 15 12 9 5 3

//

insert(17);

insert(18);
// ----------------------

// index : 0 1 2 3 4 5

// ----------------------

// queue : 16 15 12 9 5 3

printf("Eng boshidagi element %d\n - ",peek());
printf("----------------------\n");

printf("index : 5 4 3 2 1 0\n");

printf("----------------------\n");

printf("Queue: ");

while(!isEmpty()){

int n = removeData();

printf("%d ",n);

}

}
Natija:

Queue to’lgan!

Element o’chirildi: 1

Eng boshidagi element: 3

----------------------

index : 5 4 3 2 1 0

----------------------

Queue: 3 5 9 12 15 16

4 – Laboratoriya ishi bo’yicha variant javobi.

Talabalar ism-sharifi va tartib raqamidan iborat jadvalni quicksort algritmi bilan saralash va nechta o’rinlashtirish amalga oshirilganini aniqlash dasturi.

#include

#include

using namespace std;

struct table{

int t;

string FIO; };

int q=0;

void qs(table *a,int first,int last){

int i = first, j = last;table x =a[(first + last) / 2];

do {

while (a[i].FIO < x.FIO) i++;

while (a[j].FIO > x.FIO) j--;

if(i <= j) {

if (i < j){ swap(a[i], a[j]);q++;}

i++;

j--;

}

} while (i <= j);

if (i < last)

qs(a,i,last);

if (first < j)

qs(a,first,j);

}

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

{ int n;cout<<"n=";cin>>n;

table talaba[n];

for(int i=0;i

talaba[i].t=i+1;

cin>>talaba[i].FIO;

}

qs(talaba,0,n-1);

for(int i=0;i

cout<

cout<<"quicksort algoritmi "<

saraladi\n"; system("PAUSE");

}

Dastur natijasi:

talabalar sonini kiriting=5

5 ta talabalar FIO sini kiriting

Farhod

Asror

Sobir

Bobur

Vali

| 2 | Asror |

| 4 | Bobur |

| 1 | Farhod |

| 3 | Sobir |

| 5 | Vali | bu algoritm jadvalni 3 ta o‘rinlashtirishda saraladi.