“Ma’lumotlar tuzilmasi va algoritmlar” fanidan 1-hafta laboratoriya ishi bajarishga namuna

“Ma’lumotlar tuzilmasi va algoritmlar” fanidan 5-amaliy ISHnI BAJARISHGA NAMUNA (2-kurslar uchun)

Qidiruv algoritmlari: chiziqli va binar qidiruv
Ma’lumotlarni xeshlash algoritmlari. Xesh jadval va xesh funksiyalari. Ziddiyatlami hal qilish usullari.
Fan o‘qituvchisi: kat.o‘q. Kudratov R.B.

3.1. Qidiruv algoritmlari: chiziqli va binar qidiruv

Rejalashtirildi:

• Qidiruv tushunchasi
• Chiziqli qidirish algoritmi
• Binar qidiruv algoritmi

Qidiruv tushunchasi

Kompyuterda ma’lumotlarni qayta ishlashda qidiruv asosiy amallardan biri bo‘lib hisoblanadi. Uning vazifasi berilgan argument bo‘yicha massiv ma’lumotlari ichidan mazkur argumentga mos ma’lumotlarni topishdan iborat.

Ixtiyoriy ma’lumotlar majmuasi jadval yoki fayl deb ataladi. Ixtiyoriy ma’lumot (yoki tuzilma elementi) boshqa ma’lumotdan biror bir belgisi orqali farq qiladi. Mazkur belgi kalit deb ataladi. Kalit noyob bo‘lishi, ya’ni mazkur kalitga ega ma’lumot jadvalda yagona bo‘lishi mumkin.

Chiziqli qidirish (Линейный поиск, linear search) algoritmi

Berilgan tartiblanmagan massivdagi biror elementni (kalitni) topish uchun chiziqli (ketma-ket) qidirish algoritmi ishlatiladi. U ham tartiblanmagan, ham tartiblangan massivlar bilan ishlaydi, lekin ikkinchisi uchun chiziqli qidiruvdan ko'ra samaraliroq algoritmlar mavjud.

Bu samarasizlik algoritmning oddiy bajarilishi va uni tartiblanmagan ketma -ketlikda qo'llash qobiliyati bilan qoplanadi. Bu yerda, shuningdek, boshqa barcha qidirish algoritmlarini ko'rib chiqayotganda, ma'lum bir qiymat, algoritm bajarilganda, qator elementlarining qiymatlari bilan taqqoslaganda, kalit vazifasini bajaradi, deb taxmin qilamiz.

Chiziqli qidirish (Линейный поиск, linear search) algoritmi

C++ da dastur kodi:

#include "stdafx.h" #include #include using namespace std; int i, N; //chiziqli qidiruv int LineSearch(int A[], int key){ for (i=0; i if (A[i]==key) return i; return -1;} //bosh funksiya void main(){ int key, A[1000]; srand(time(NULL));

cout<<"Massiv o’lchami: > "; cin>>N; cout<<" Qidirilayotgan element > "; cin>>key; cout<<"Massiv elementlari: "; for (i=0; i A[i]=rand()%10; cout< if (LineSearch(A, key)==-1) cout<<"\nElement topilmadi"; else cout<<"\nElement raqami:"< system("pause>>void"); }