|
Axborot texnologiyalari” kafedrasi “MA’lumotlar tuzilmasi va algoritmlari” fanidan amaliy mashg‘ulotlarini bajarish bo‘yicha
|
| bet | 29/39 | | Sana | 12.06.2024 | | Hajmi | 2,32 Mb. | | #262963 |
Bog'liq uslubiy qo\'llanma 3Nazorat savollar:
Daraxtlarning asosiy dasturlariga qaysilar kiradi?
Ikkilik daraxt boshqa daraxtlar bilan asosan nimasi bilan farq qiladi?
12-Amaliy mashg‘ulot: Heap tree ko‘rinishidagi binary daraxtlar bilan ishlash algoritmlari.
Ishdan maqsad. Ushbu amaliyot ishida talabalar Heap tree ko‘rinishidagi binary daraxtlar bilan ishlash algoritmlari bilan tanishib chiqishlari kerak
Qo‘yilgan masala. Talabalar topshiriq variantiga mos ravishda Heep tree darxtlar ustida berilgan amallar bilan ishlash ko‘nikmasiga ega bo‘lishlari kerak.
Ish tartibi:
Tajriba ishi nazariy ma’lumotlarini o‘rganish;
Berilgan topshiriqning algoritmini ishlab chiqish;
C++ dasturlash muhitida dasturni yaratish;
Natijalarni tekshirish;
Hisobotni tayyorlash va topshirish.
Heap tree(bosh daraxt), qulaylik va tezlik bilan ko‘p miqyosli ma’lumotlarni o‘z ichiga olish uchun ishlatiladi. Quyidagi algoritmlar bosh daraxtlar bilan ishlash uchun bazi asosiy operatsiyalardir:
1. Qo‘shish (Insertion): Yangi elementni bosh daraxtga qo‘shish uchun quyidagi qadamlar bajariladi:
a. Elementni daraxtning oxiriga qo‘shing.
b. Agar yangi element bosh daraxt qoidaga zarar yetkazmasa (ya’ni, bosh daraxtning barcha qoidalariga qarshi holda to‘g‘ri o‘tsa), unda bosh daraxtni tiklash uchun qoida alohida boshqaruvchiga o‘tkazing (masalan, “heapify_up” funksiyasiga).
2. O‘chirish (Deletion): Bosh daraxtning eng yirik elementini (o‘rniga bosh elementni) o‘chirish uchun quyidagi qadamlar bajariladi:
a. Bosh elementni o‘chirib, daraxtning oxiridagi eng kichik elementni bosh elementning o‘rniga ko‘chirish.
b. Agar daraxtning oxiridagi element bosh daraxtning barcha qoidalariga qarshi holda to‘g‘ri o‘tkazmasa, unda daraxtni tiklash uchun “heapify_down” funksiyasiga qarshi holda barcha qoidalarga to‘g‘ri o‘tsa qadamlar bajariladi.
3. Bosh daraxtni tiklash (Heapify): Bosh daraxtning tuzilishi qoidalariga mos keladigan holatga keltirish uchun “heapify” funksiyasi ishlatiladi. Buni ikki turdagi funksiyalar amalga oshiradi:
a. heapify_up: Bu funksiya yangi elementni bosh daraxtga qo‘shishdan so‘ng uning o‘zi bosh daraxtni tiklash uchun ishlatiladi. Element bosh daraxtni ustiga chiqsa, u o‘rniga yo‘qotiladi va uning o‘zi bilan bir o‘rin pastdagi elementni solishtirib olish uchun qoidalar bilan solishtiriladi.
b. heapify_dow: Bu funksiya o‘chirilgan elementning o‘rnini to‘g‘ri olish uchun ishlatiladi. O‘chirilgan element bosh daraxtning oxiri bilan solishtirilib, qoidalarga mos kelishi va barcha qoidalar bilan to‘g‘ri o‘tish qoidalariga amal qilish uchun barcha qoidalarga solishtiriladi.
Heap tree ko‘rinishidagi binary daraxtlar bilan ishlash uchun C++ dasturlash tilida dasturlar yozishni ko‘rsataman. Bu, C++ tilida bosh daraxt (binary heap) yaratish, element qo‘shish, elementni o‘chirish, va daraxtni tiklash uchun muhim algoritmlarni o‘z ichiga oladi.
Quyidagi C++ kodida bosh daraxtni yaratish, element qo‘shish, elementni o‘chirish va daraxtni tiklashni amalga oshirish uchun funksiyalarni o‘z ichiga olgan misolni ko‘rsataman:
#include
#include
class BinaryHeap {
private:
std::vector heap;
void heapify_up(int index) {
if (index == 0) return; // Bosh elementda to‘g‘ri o‘tqazamiz
int parent = (index - 1) / 2;
if (heap[index] > heap[parent]) {
std::swap(heap[index], heap[parent]);
heapify_up(parent);
BinaryHeap() {}
void insert(int value) {
heap.push_back(value);
heapify_up(heap.size() - 1); }
void remove() {
if (heap.empty()) return;
heap[0] = heap.back();
heap.pop_back();
heapify_down(0); }
void print() {
for (int val : heap) {
std::cout << val << " ";
} std::cout << std::endl; }};
int main() {
BinaryHeap heap;
heap.insert(10);
heap.insert(30);
heap.insert(15);
heap.insert(50);
heap.insert(5);
std::cout << "Bosh daraxt: ";
heap.print();
heap.remove();
std::cout << "Bosh daraxt o‘chirilgandan so‘ng: ";
heap.print();
return 0;}
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Axborot texnologiyalari” kafedrasi “MA’lumotlar tuzilmasi va algoritmlari” fanidan amaliy mashg‘ulotlarini bajarish bo‘yicha
|
