2-Amaliy ishi. Qidiruv usullarini tadqiq qilish



Yüklə 239,5 Kb.
səhifə6/7
tarix21.10.2022
ölçüsü239,5 Kb.
#65743
1   2   3   4   5   6   7
Algoritm

  1. Jadvalga n ta talaba FIO va adreslarini kiritamiz.

  2. Binar qidiruvni jadvalning birorta maydonida amalga oshirish uchun jadvalni shu maydoni bo‘yicha tartiblab olish kerak. Shuning uchun masalaning qo‘yilishida adresi TTJ bo‘lgan talabalarni topish kerakligi sababli jadval ma’lumotlarini adres maydoni bo‘yicha saralab olamiz. Masalani yechishda to‘g‘ridan-to‘g‘ri tanlash orqali saralashdan foydalanilgan.

  3. key kalitga mos elementni izlash chegaralarini aniqlab olamiz. Dastlab u [0,n] oralig‘ida, ya’ni low=0,hi=n.

  4. Agar low<=hi bo‘lsa, oraliq o‘rtasini hisoblaymiz. mid=(low+hi)/2

  5. Agar mid o‘rnida turgan talaba adresi TTJ bo‘lsa, element topildi, search=mid va 7-qadamga o‘tiladi, aks holda keyingi qadamga o‘tiladi.

  6. Agar “TTJ” so‘zi alifbo bo‘yicha mid o‘rnida turgan talaba adresi qiymatidan kichik bo‘lsa, izlash quyi chegarasi o‘zgaradi, ya’ni mid o‘rnida turgan elementdan bitta oldingi elementgacha olinadi, ya’ni hi=mid-1. Aks holda, yuqori chegara o‘zgaradi – mid dan keyingi elementdan to oxirgi elementlar oralig‘i olinadi, ya’ni low=mid+1. 4-qadamga o‘tiladi.

  7. Agar topilgan elementdan oldin turgan elementning (mid-1) ham adres maydoni TTJ bo‘lsa, search--, ya’ni bitta oldingi elementga o‘tamiz va shu qadamni boshidan bajaramiz. Aks holda keyingi qadamga o‘tiladi.

  8. Joriy (search ko‘rsatayotgan) elementdan boshlab adresi “TTJ” ga teng bo‘lgan talaba ma’lumotlarini ekranga chiqaramiz. Agar adresi “TTJ” dan farq qiladigan talaba chiqib qolsa, algoritm tugallanadi.

Dastur kodi
#include
using namespace std;
int main(){
int n;cout<<"n=";cin>>n;
struct Guruh{
string fio,adres;
}talaba[n];
for(int i=0;i
cout<
cout<
int low = 0,hi = n-1,search=-1,q=0;
string key="TTJ";
while(low<=hi){
int mid = (low + hi) / 2;
q++;
if (key == talaba[mid].adres){
search = mid;
break;
}
if (key < talaba[mid].adres)
hi = mid - 1;
else low = mid + 1;
}
if(search!=-1) cout<<"qidirilayotgan el "<
else {cout<
system("PAUSE");
return EXIT_SUCCESS;
}
while(talaba[search-1].adres==key) search--;
while(talaba[search].adres==key) {
cout<
search++; }
system("pause");
}

Yüklə 239,5 Kb.

Dostları ilə paylaş:
1   2   3   4   5   6   7




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin