|
Chiziqli (Ketma-ket) qidiruv
|
| bet | 2/5 | | Sana | 06.10.2024 | | Hajmi | 29,86 Kb. | | #273785 |
Bog'liq Ma\'lumotlar tuzilmasi va algoritmlar Mardonov M1. Chiziqli (Ketma-ket) qidiruv
Mazkur ko’rinishdagi qidiruv agar ma’lumotlar tartibsiz yoki ular tuzilishi noaniq bo’lganda qo’llaniladi. Bunda ma’lumotlar butun jadval bo’yicha operativ xotirada kichik adresdan boshlab, to katta adresgacha ketma-ket qarab chiqiladi.
Massivda ketma-ket qidiruv (search o’zgaruvchi topilgan element raqamini saqlaydi).
Psevdokodi :
For i:=1 to n
If k(i)=key then
Search= i
return
EndIf
Next i
Search= 0
return
Search o’zgaruvchi topilgan elementning nomerini saqlaydi.
C++ tilida dastur quyidagicha bo’ladi:
#include
#include
int search(int a[], int N, int key)
{
int i=0;
while (i!=N)
if (a[i]==key) return i;
else i++;
return -1;
}
main ()
{
int i, N, mas[1000], key, P;
cout<<
cin>>N;
cout<<
for (i=0; i
cin>>mas[i];
cout<<cin>>key;
P=search(mas,N,key);
if (P==-1) cout<
else cout<<
getch();
return 0;
}
Massivda ketma-ket qidiruv algoritmi samaradorligini bajarilgan taqqoslashlar soni M bilan aniqlash mumkin. Mmin = 1, Mmax = n. Agar ma’lumotlar massiv yacheykasida bir hil extimollik bilan taqsimlangan bo’lsa, u holda Msr » (n + 1)/2 bo’ladi.
Agar kerakli element jadvalda bo’lmasa va mazkur elementni jadvalga qo’shish lozim bo’lsa, u holda yuqoridagi dasturdagi oxirgi ikkita operator quyidagiga almashtiriladi:
Paskalda
n:=n+1;
k[n]:=key;
r[n]:=rec;
search:=n;
exit;
Umuman olganda ketma-ket qidiruv samaradorligini oshirish mumkin.
2. Indeksli ketma-ket qidiruv
Mazkur ko’rinishdagi qidiruv amalga oshirilayotganda ikkita jadval tashkil qilinadi: o’z kalitiga ega ma’lumotlar jadvali (o’sish tartibida tartiblangan) va indekslar jadvali, bu xam ma’lumotlar kalitidan iborat-u, lekin bu kalitlar asosiy jadvaldan aniq bir interval orqali olingan. (2-chizma).
Boshida berilgan argument bo’yicha ketma-ket qidiruv indekslar jadvalida amalga oshiriladi. Qachonki, biz berilgan kalitdan kichik kalitni aniqlaganimizda, asosiy jadvalda qidiruvni quyi chegarasini o’rnatamiz - low, keyin esa yuqori chegarani - hi, ya’ni ( kind > key ).
Masalan, key = 101.
Qidiruv to’la jadval bo’yicha emas, balki low dan hi gacha davom etadi.
|
| |
