O`rta maxsus ta’lim vazirligi

Qidiruvning maqsadi - quyidagi jarayonlarning birini bajarilishidan iborat:

• 
  topilgan yozuvni o‘qish;
  
• 
  qidirilayotgan yozuv topilmasa, uni jadvalga qo‘yish;  topilgan yozuvni o‘chirish.
  

Faraz qilaylik, k – kalitlar massivi bo‘lsin. Har bir k(i) uchun r(i) – ma’lumot mavjud. Key – qidiruv argumenti.

Jadvaldagi ma’lumotlarning tuzilmasiga qarab qidiruvni bir necha turlari mavjud.

Ketma-ket qidiruv algoritm

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 tartib raqamini saqlaydi).

Ketma-ket qidiruv algoritmi C++ tilida quyidagicha bo‟ladi:

int qidiruv(int key){ for (int i=0;ireturn search;} search = -1; return search;

}}

Massivda ketma-ket qidiruv algoritmi samaradorligini bajarilgan taqqoslashlar soni M bilan aniqlash mumkin. Mmin = 1, Mmax = n. Agar ma`lumotlar massiv yacheykasida bir xil ehtimollik bilan taqsimlangan bo‟lsa, u holda Mo`rt (n + 1)/2 bo‟ladi. Agar kerakli element jadvalda yo`q bo`lib, uni jadvalga qo‟shish lozim bo`lsa, u holda yuqorida keltirilgan algoritmdagi oxirgi ikkita operator quyidagicha almashtiriladi. n=n+1; k[n-1]:=key; r[n-1]:=rec; search:=n-1; return search;

Agar ma`lumotlar jadvali bir bog`lamli ro`yhat ko`rinishida berilgan bo`lsa u holda ketma-ket qidiruv ro`yhatda amalga oshiriladi.

Chiziqli bir bog‟lamli ro`yhatdan key kalitga mos elementni ketma-ket qidiruv usuli yordamida izlab topish dasturi.

Node *q=NULL; Node *p=lst; while (p !=NULL){ if (p->k == key){ search = p; return search;

} q = p; p = p->nxt; }

Node *s=new Node;; s->k=key; s->r=rec; s->nxt= NULL; if (q == NULL){ s->nxt=lst; lst = s; } else q->nxt = s; search= s; return search;

Ro`yhatli tuzilmaning afzalligi shundan iboratki, ro`yhatga elementni Qo`shish yoki o`chirish tez amalga oshadi, bunda qo`shish yoki o`chirish element soniga bog`liq bo`lmaydi, massivda esa elementni qo`shish yoki o`chirish o`rta hisobda barcha elementlarning yarmini siljitishni talab qiladi. Ro`yhatda qidiruvning samaradorligi taxminan massivniki bilan bir xil bo`ladi.