|
Chiziqli qidiruv yondoshuvi
|
| bet | 14/18 | | Sana | 14.05.2024 | | Hajmi | 91,02 Kb. | | #231246 |
Bog'liq 1. Kompyuter nima hardware, software-fayllar.org12.6.1. Chiziqli qidiruv yondoshuvi.
Chiziqli qidirish yondoshuvi kalit – kalit so`zini massivning har bir elementi blan, ketma-ket solishtirishga ixtisoslashtirilgan. Funksiya bu ishni massiv tarkibidagi elementlardan birontasi kalit ga mos kelgunicha yoki, massiv so`nggiga qadar amalga oshiradi. Agar massiv tarkibida biror element kalit ga mos kelsa, chiziqli qidirish uning indeksini qaytaradi. Aks holda, qidiruv -1 ni qaytaradi. Chiziqli qidirish 12.6-kodli ro`yxatda batafsil yozilgan. 12.6-kodli ro`yxat. ChiziqliQidiruv.cpp
int ChiziqliQidiruv(const int list[], int kalit, int hajm) {
for (int i = 0; i < hajm; i++) {
if (kalit == list[i])
return i; } return -1; }
Bu funksiyani quyidagi ko`rsatma satrlari orqali tekshirib ko`rishimiz mumkin:
intlist[]={1,4,4,2,5,-3, 6, 2}; int i = ChiziqliQidiruv(list,4,8); // Qaytariluvchi1 int j=ChiziqliQidiruv(list, -4,8); //Qaytariluvchi -1
int k = ChiziqliQidiruv(list,
-3,8); // Qaytariluvchi 5
Ikkilik qidiruv yondoshuvi.
Bir qancha qiymatlarni qidirishning eng ko`p tarqalgan yodoshuvlaridan biri – ikkilik qidiruv yondoshuvidir. U massivdagi elementlar avvaldan tartiblangan bo`lishini talab qiladi. Tasavvur qiling, massiv o`sish tartibida. Ikkilik qidiruv birinchi navbatda kalit so`zni massivning markazidagi element bilan solishtiradi. Quyidagi holatlarni ko`rib chiqamiz:
Agar kalit markaziy elementdan kichik bo`lsa, qidirish massivning faqat birinchi yarimtaligida davom ettiriladi;
Agar kalit markaziy elementga mos bo`lsa, qidirish brinchi urinishdayoq to`xtatiladi;
Agar kalit markaziy elementdan katta bo`lsa, qidirish massivning faqat ikkinchi yarimtaligida davom ettiriladi. Bir narsa aniqki, qidiruv funksiyasi har bir solishtirishdan so`ng massivning eng kichik bo`lagini olib tashlaydi. Ba’zida elementlarning yarmi olib tashlaymiz, ba’zida esa, yarmidan bitta ko`pini. Faraz qilaylik, n ta elementdan iborat massiv mavjud. Qulaylik uchun, keling uni 2 ga karrali deb olamiz. Birinchi taqqoslashdan so`ng keyingi qidiruv qismiga o`tish uchun elementlarning n/2 qismi tashlab yuboriladi; ikkinchi taqqoslashdan so`ng esa, keyingi qidiruv qismiga o`tish uchun elementlarning (n/2)/2 qismi tashlab yuboriladi; shunday qilib, k-taqqoslashdan so`ng esa, keyingi qidiruv qismiga o`tish uchun elementlarning n/2k qismi tashlab yuboriladi. k=log2n bo`lganida, massivning bitta elementi tashlab yuboriladi va bu yerda bir martadan ko`p taqqoslashni amalga oshirish kerak bo`ladi. Bu yaxshi holat emas, shuning uchun ikkilik qidiruv yondoshuvi qo`llanilganda log 2 n+1 ta taqqoslashlar amalga oshirilishi zarur.
68.Massivlarni saralash(sorting arrays).
Saralash ham qidirish kabi, kompyuterli dasturlashda ko`p qo`llaniladigan masalalar sirasiga kiradi. Saralashga mo`ljallangan turli xil algoritmlar ishlab chiqilgan. Bu qismda tanlab saralash algoritmi yoritib beriladi.
Faraz qilaylik, biz list nomli massivimizni o`suvchi tartibda saralamoqchimiz. Tanlab saralash algoritmi massivdagi eng kichik sonni topib, uni birinchisi bilan almashtiradi. Undan keyin, birinchi sondan tashqari, yana eng kichik sonni topadi va uni ikkinchi elementga joylashtiradi, bu jarayon toki oxirida bitta son qolmaguncha davom etadi. 12.5-rasmda qanday qilib list{2, 9, 5, 4, 8, 1, 6} massivini tanlab saralash algoritmi yordamida saralash mumkinligi tasvirlangan.
69.C-Stringlar(c-strings va. string type, null terminator).
C-satr nolli chegaraviy birikma (‘\0’) bilan tugallanuvchi belgilar massividir. C++ kutubxonasida C-satrlarni C-satr funksiyalaridan foydalanib qo`llash mumkin.
C-satr xotirada satr chegarasini belgilovchi nolli chegaraviy birikma (‘\0’) bilan tugallanuvchi belgilar massividir.Har bir satrli literal – C-satrdir. Massivni satrli literallar bilan yuklash mumkin. Quyidagi ko`rsatma satri C-satr uchun, 'D', 'a', 'l', 'l', 'a', 's' belgilari va chegaraviy birikma – (‘\0’ dan iborat bo`lgan massivni e’lon qiladi:
char city[7] = "Dallas";
12.6-rasm. Belgili massiv C-satr bilan e’lon qilinishi mumkin.
Bu yerda massivning hajmi 7 ga teng va uning oxirgi belgisi ‘\0’. C-satr va belgilar massivi o`rtasida nozik bir farq mavjud. Masalan, quyidagi ikkita ko`rsatma satrlari bir-biridan farq qiladi:
char city1[] = "Dallas"; // C-satr
char city2[] = {'D', 'a', 'l', 'l', 'a', 's'}; // C-satr emas C-satrlarni kiritish va chiqarish.
C-satrni chiqarish oson. Faraz qilaylik, s C-satrli massiv. Uni konsol oynada chop etish uchun shunchaki
cout << s;
ko`rsatma satridan foydalanish mumkin.
C-satrli massivni klaviaturadan ham osongina kiritishimiz mumkin:
char city[7]; cout<< "Shaharni kiriting:"; cin >> city; // city massivini o`qish
cout<<"Sizkiritganshahar: " << city << endl;
C-satrni kiritishda chegaraviy belgi uchun joy qoldirib ketish kerak. Chunki city ning hajmi 7 ga teng, bizning kiritmoqchi bo`lgan belgilarimiz soni 6 tadan oshmasligi lozim. Bu yondoshuv asosida satrni o`qish oson, lekin bunda bir muammo bor. Kiritilayotgan satr oxirida bitta bo`sh joy bilan o`qiladi. Aytaylik, biz satrni so`nggida qo`shimcha bo`sh joy bilan olmasligimiz kerak. Faraz qilaylik, Nyu York satrini o`qish kerak. Bunday holatlar uchun C++ da satrli massivni o`qishning yana bir alternative variant mavjud. C++ tili iostream kutubxona fayli tarkibida mavjud bo`lgan cin.getline funksiyasini taqdim etadi. Bu funksiyaning sintaksisi quyidagicha:
|
| |
