Ketma-ket qidiruv usuli va uning algoritmining tushuntirib bering. Bu qidiruv usuli qanday tuzilmalar uchun samarali deb hisoblaysiz?

• Mazkur ko’rinishdagi qidiruv agar ma’lumotlar tartibsiz yoki ular tuzilishi noaniq bo’lganda qo’llaniladi.

  
  

• Bunda ma’lumotlar tuzilmasi butun jadval bo’ylab tezkor xotirada kichik adresdan boshlab, to katta adresgacha ketma-ket qarab chiqiladi.

  
  

• Bunda yordamchi search o’zgaruvchisi topilgan element kalitini saqlaydi

  
  

• Massivda ketma-ket qidiruv algoritmining samaradorligini bajarilgan taqqoslashlar soni M bilan aniqlash mumkin.

  
  

Misol: C++ da ketma-ket qidiruv usuli:

Misol:

• 
  
  //ro’yxat
  
• 
  
  struct TNode { int value;
  
• 
  
  TNode* pnext;
  
• 
  
  TNode(int val): pnext(0), value(val) {} };
  
• 
  
  //qidirish funksiyasi
  
• 
  
  TNode* Find(TNode *phead, int x)
  
• 
  
  {
  
• 
  
  TNode *p=phead;
  
• 
  
  while(p)
  
• 
  
  if (p->value==x) return p;
  
• 
  
  else p = p->pnext;
  
• 
  
  return 0;
  
• 
  
  }
  
  16.Indeksli ketma-ket qidiruv usuli, uning ishlash printsiplari, algoritmni misollar yordamida tushuntirib bering.
  Bu qidiruv amalga oshirilayotganda ikkita jadval tashkil qilinadi: o’z kalitiga ega ma’lumotlar jadvali (o’sish tartibida tartiblangan) va indekslar jadvali.
  Bu yerda birinchi berilgan argument bo’yicha indekslar jadvalidan ketma-ketlikda qidirish amalga oshiriladi. Kalitlarni ko’rib chiqishda berilgan kalitdan kichigi topilsa, u holda ushbu kichik kalitni asosiy jadvaldagi qidirishning eng quyi chegarasi – low ga joylashtiramiz, xuddi shunday berilgan kalitdan katta deb topilgan kalitni (kind > key) yuqori hi ga joylashtiramiz.
  

  • Misol uchun, key = 101 bo’lsin. U holda qidiruv butun jadval bo’yicha emas, balki low dan hi gacha amalga oshiriladi.

    
    
  • 
    
    
    
    Download 5,63 Mb.