Mavzu Ma’lumotlarni qidirish usullari, algoritmlar va ularning samaradorligi. Reja

1. 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<<”Masiv uzunligini kiriting!”<
cin>>N;

cout<<”Massiv elementlarini kiriting!”
cin>>mas[i];
cout<<”Qidiruv elementini kiriting!”<
cin>>key;
P=search(mas,N,key);
if (P==-1) cout<<”Bunday element massivda yoq”;
else cout<<”Bunday element bor”<

getch();

return 0;
}
Massivda ketma-ket qidiruv algoritmi samaradorligini bajarilgan taqqoslashlar soni M bilan aniqlash mumkin. M_min = 1, M_max = n. Agar ma’lumotlar massiv yacheykasida bir hil extimollik bilan taqsimlangan bo’lsa, u holda M_sr » (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.