Universiteti akt sohasida iqtisodiyot va menejment fakulteti axborot texnologiyalarning dasturiy ta

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALAR

UNIVERSITETI

AKT SOHASIDA IQTISODIYOT VA MENEJMENT FAKULTETI

AXBOROT TEXNOLOGIYALARNING DASTURIY TA’MINOTI

KAFEDRASI:

122-19 GURUH TALABASI:

BAJARDI: BAHODIR MEYLIKOV

TEKSHIRDI:YUSUF BO’RIYEV

MAVZU:QIDIRUV USULLARINI TADQIQ QILISH

IZOH:topshiriq dasturi C++ builderda bajarildi

Nazariy ma’lumotlar:

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. Bunday noyob kalitga boshlang’ich (birinchi) kalit deyiladi. Ikkinchi kalit bir jadvalda takrorlansada u orqali xam qidiruvni amalga oshirish mumkin.

Ma’lumotlar kalitini bir joyga yig’ish (boshqa jadvalga) yoki yozuv sifatida ifodalab bitta maydonga kalitlarni yozish mumkin. Agar kalitlar ma’lumotlar jadvalidan ajratib olinib alohida fayl sifatida saqlansa, u holda bunday kalitlar tashqi kalitlar deyiladi. Aks holda, ya’ni yozuvning bir maydoni sifatida jadvalda saqlansa ichki kalit deyiladi.

Kalitni berilgan argument bilan mosligini aniqlovchi algoritmga berilgan argument bo’yicha qidiruv deb ataladi. Qidiruv algoritmi vazifasi kerakli ma’lumotni jadvalda topish yoki yo’qligi aniqlashdan iboratdir

. Agar kerakli ma’lumot yo’q bo’lsa, u holda ikkita ishni amalga oshirish mumkin:

1. ma’lumot yo’qligini indikasiya (belgilash) qilish

2. jadvalga ma’lumotni qo’yish.

Faraz qilaylik, k – kalitlar massivi. Har bir k(i) uchun r(i) – ma’lumot mavjud. Key – qidiruv argumenti. Unga rec - informasion yozuv mos qo’yiladi. Jadvaldagi ma’lumotlarning tuzilmasiga qarab qidiruvni bir necha turlari mavjud.

1. 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).

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.

3. Ketma-ket qidiruvni samaradorligi

Ixtiѐriy qidiruvning samaradorligi jadvaldagi ma’lumotlarning kalitlari bilan solishtirish soni – S bilan baxolanishi mumkin. Agar taqqoslashlar (solishtirish) soni qancha kichik bo’lsa, qidiruv algoritmi samaradorligi shuncha yaxshi bo’ladi. Massivda ketma-ket qidiruvning samaradorligi quyidagicha bo’ladi: C = 1 n, C = (n + 1)/2. Umuman olganda ro’yxatda xam samaradorlik yuqoridagi kabi bo’ladi. Garchi massivda xam bog’langan ro’yxatda xam qidiruv samaradorligi bir xil bo’lsada, ma’lumotlarni massiv va ro’yxat ko’rinishda tasvirlashning o’ziga xos kamchilik va afzalliklari mavjud.

Qidiruvning maqsadi - quyidagi jaraѐnlarni bajarilishidan iborat:

1) Topilgan ѐzuvni o’qish.

2) Qidirilaѐtgan ѐzuv topilmasa, uni jadvalga qo’yish.

3) Topilgan ѐzuvni o’chirish.

Birinchi jaraѐn (qidiruvning o’zi) massiv uchun ham ro’yxat uchun ham bir xil bo’ladi. Ikkinchi va uchinchi jaraѐnda esa qidiruv ro’yxatli tuzilmada samaraliqroq bo’ladi (sababi massivda elementlarn siljitish lozim). Agar k massivda elementlarni siljitishlar soni bo’lsa, u xolda k = (n + 1)/2 bo’ladi.

4. Indeksli ketma-ket qidiruvni samaradorligi

Agar bo’lishi mumkin barcha xolatlar teng extimolli deb olinsa, u holda qidiruv samaradorligini quyidagicha xisoblash mumkin: Belgilashlar kiritib olamiz: m – indeks o’lchovi; m = n / p; p – qadam o’lchovi Q = (m+1)/2 + (p+1)/2 = (n/p+1)/2 + (p+1)/2 = n/2p+p/2+1 (*) Q ni p bo’yicha differensiallab uni nolga tenglashtiramiz: dQ/dp=(d/dp) (n/2p+p/2+1)= - n / 2 p 2 + 1/2 = 0

Bu yerdan p 2 =n ; n p opt

Transpozisiya usuli

Ushbu usulda topilgan element ro’xatda bitta oldingi element bilan o’rin almashtiriladi. Agarda mazkur elementga ko’p murojaat qilinsa, bittadan oldinga surilib borib natijada ro’yxat boshida bo’ladi.

Chizma. Qo’shni elementlarni o’rnini almashtirish r – ishchi ko’rsatkich q – ѐrdamchi ko’rsatkich, r dan bitta qadam orqada bo’ladi s - ѐrdamchi ko’rsatkich, q dan ikkita qadam orqada bo’ladi.