CS50 - Week 5

Ma'lumot tuzilmalari

Ma'lumot tuzilmalari - xotiradagi ma'lumotlarni tashkil qilish shakllaridir. Xotirada ma'lumotlarni tashkil qilishning ko‘plab usullari mavjud.

Abstrakt ma'lumot tuzilmalari – bu biz konseptual tarzda tasavvur qiladigan tuzilmalardir. Ushbu abstrakt tuzilmalar bilan tanishish kelgusida ma'lumot tuzilmalarini amaliyotda amalga oshirishni osonlashtiradi.

---

Stack va Queue

Queue – bu abstrakt ma'lumot tuzilmalarining bir shakli.
Queue ma'lumot tuzilmasi FIFO (First In First Out, "birinchi qo'shilgan element birinchi chiqadi") qoidasi bo‘yicha ishlaydi.
Buni attraksionda navbatda turgan odamlar misolida tasavvur qilish mumkin: navbatda birinchi bo‘lgan odam birinchi bo‘lib kiradi, oxirgi bo‘lgan esa oxirgi kiradi.

Queue'lar bilan quyidagi operatsiyalarni bajarish mumkin:

• Enqueue: navbatning oxiriga yangi element qo‘shish.
• Dequeue: navbatning boshidan elementni o'chirish.

Stack ma'lumot tuzilmasi esa LIFO (Last In First Out, "oxirgi qo'shilgan element birinchi chiqadi") qoidasi bo‘yicha ishlaydi.
Masalan, oshxonada laganlarni ustma-ust taxlash: eng oxirgi qo‘yilgan lagan birinchi olinadi.

Stack quyidagi operatsiyalarga ega:

• Push: stack'ga yangi element qo‘yish.
• Pop: stack'dan elementni o'chirish.

---

Massiv

Massiv – ma'lumotlarni xotirada ketma-ket saqlash usulidir. Massivni quyidagicha tasavvur qilish mumkin:

Xotirada boshqa dasturlar, funktsiyalar va o'zgaruvchilar tomonidan saqlanadigan boshqa qiymatlar, shuningdek, avval foydalanilib, hozir foydalanilmayotgan keraksiz qiymatlar ham mavjud bo'lishi mumkin:

Agar massivga yangi element – 4ni qo‘shmoqchi bo‘lsak, yangi xotira ajratib, eski massivni unga ko‘chirishimiz kerak bo‘ladi. Ushbu yangi xotira keraksiz qiymatlar (garbage values) bilan to'la bo'lishi mumkin:

Massivga elementlarni ko'chirib, yangi qiymatni qo'shsak, ajratilgan yangi xotiradagi eski kearksiz qiymatlar ustiga yangi qiymatlar yoziladi:

Bu yondashuvning kamchiligi – har bir yangi element qo‘shilganda massivni to‘liq nusxalash kerak bo‘ladi.
Agar biz 4 ni xotirada boshqa joyga joylashtirsakchi? U holda, ta'rifga ko'ra, bu endi massiv bo'lmaydi, chunki 4 xotirada massiv elementlari bilan ketma-ket joylashmaydi.

Ba’zida, dasturchilar kerak bo‘lganidan ko‘proq xotira ajratadilar (masalan, 30 ta element uchun 300 ta joy ajratilishi). Ammo bu yomon dizayn hisoblanadi, chunki tizim resurslari bekor sarflanadi va ko‘p hollarda ortiqcha xotira kerak bo‘lmaydi. Shuning uchun xotirani aniq ehtiyojga mos ravishda ajratish muhimdir.

---

Linked List

Linked List - C dasturlash tilidagi eng kuchli ma’lumot tuzilmalaridan biridir. Ular turli xotira hududlarida joylashgan qiymatlarni bir ro‘yxatda birlashtirish imkonini beradi. Shuningdek, ro‘yxatni xohlaganimizcha dinamik tarzda kengaytirish yoki qisqartirish imkonini ham beradi.

Har bir node o'zida ikki qiymatni saqlaydi:

• qiymat;
• keyingi node'ning xotiradagi manzilini o'zida saqlovchi ko'rsatkich. Oxirgi node esa undan keyin boshqa element yo'qligini ko'rsatish uchun o'zida NULLni saqlaydi.

Linked list birinchi elementinining manzilini bir ko'rsatkich (pointer) ga saqlab qo'yamiz.

C dasturlash tilida node'ni quyidagicha yozishimiz mumkin:

typedef struct node
{
    int number;
    struct node *next;
}
node;

Linked list yaratish jarayonini ko'rib chiqamiz:

• node *listni e'lon qilamiz:

• node uchun xotira ajratamiz:

• nodening qiymatni kiritamiz: n->number = 1:

• nodening next ko'rsatkichini NULLga tenglaymiz: n->next = NULL:

• listni nga tenglaymiz:

• Xuddi shunday tartibda, 2 qiymatiga ega yangi nodeni yaratamiz:

• Ikkala nodelarni bir-biriga bog'lash uchun nning next ko'rsatkichini listga tenglaymiz:

• Va nihoyat, listni nga tenglaymiz. Endi bizda ikkita elementlardan tashkil topgan linked list mavjud:

C dasturlash tilida ushbu jarayonning kodini quyidagicha yozishimiz mumkin:

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
}
node;

int main(int argc, char *argv[])
{
    // Linked list'ni e'lon qilamiz
    node *list = NULL;

    // Har bir buyruq qatori argumenti uchun
    for (int i = 1; i < argc; i++)
    {
        // Argumentni butun songa o‘tkazamiz
        int number = atoi(argv[i]);

        // Yangi element uchun xotira ajratamiz
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = number;
        n->next = NULL;

        // Linked list'ning boshiga node'ni qo‘shamiz
        n->next = list;
        list = n;
    }

    // Linked list elementlarini ekranga chiqaramiz
    node *ptr = list;
    while (ptr != NULL)
    {
        printf("%i\n", ptr->number);
        ptr = ptr->next;
    }

    // Xotirani bo‘shatamiz
    ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
}

Linked list bilan ishlashda bir qancha kamchiliklar mavjud:

• Ko‘proq xotira: har bir element uchun nafaqat elementning o‘z qiymatini, balki keyingi elementga ko‘rsatkichni ham saqlash kerak.
• Elementlarni indeks orqali chaqirish: massivlarda ma’lum bir elementni indeks orqali chaqirishimiz mumkin, lekin linked list'da bu imkonsiz. Ma’lum bir elementning joylashuvini topish uchun birinchi elementdan boshlab barcha elementlarni ketma-ket ko'rib chiqish kerak bo'ladi.

---

Tree

Binary Search Tree (BST) – bu ma’lumotlarni samarali saqlash, qidirish va olish imkonini beruvchi ma’lumot tuzilmasidir.
Bizga saralangan sonlar ketma-ketligi berilgan bo'lsin:

Markazdagi elementni eng yuqoriga, markazdagi elementdan kichik qiymatlarni chap tomonga, katta qiymatlarni esa o‘ng tomonga joylashtiramiz:

Ko‘rsatkichlardan foydalanib har bir elementni bir-biri bilan bog'laymiz:

Quyidagi kod BST ni qanday amalga oshirishni ko‘rsatadi:

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
}
node;

void free_tree(node *root);
void print_tree(node *root);

int main(void)
{
    // Ma'lumot tuzilmasini e'lon qilamiz
    node *tree = NULL;

    // 2 qiymatini qo'shamiz
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    n->number = 2;
    n->left = NULL;
    n->right = NULL;
    tree = n;

    // 1 qiymatini ma'lumot tuzilmasining chap tomoniga qo'shamiz
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        free_tree(tree);
        return 1;
    }
    n->number = 1;
    n->left = NULL;
    n->right = NULL;
    tree->left = n;

    // 3 qiymatini ma'lumot tuzilmasining o'ng tomoniga qo'shamiz
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        free_tree(tree);
        return 1;
    }
    n->number = 3;
    n->left = NULL;
    n->right = NULL;
    tree->right = n;

    // Elementlarni ekranga chiqaramiz
    print_tree(tree);

    // Xotirani bo‘shatamiz
    free_tree(tree);
    return 0;
}

// Xotirani bo‘shatish funksiyasi
void free_tree(node *root)
{
    if (root == NULL)
    {
        return;
    }
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

// Elementlarni ekranga chiqarish funksiyasi
void print_tree(node *root)
{
    if (root == NULL)
    {
        return;
    }
    print_tree(root->left);
    printf("%i\n", root->number);
    print_tree(root->right);
}

Har bir node uchun xotira ajratamiz va uning qiymati numberga saqlanadi, shunindek har bir node - left, va right ko'rsatkichlariga ega. print_tree funksiyasi har bir nodeni chapdan o‘ngga ketma-ket rekursiya orqali chop etadi. free_tree funksiyasi ma'lumot tuzilmasining barcha nodelarini rekursiv ravishda xotiradan bo‘shatadi.

BST ning afzalliklari:

• Dinamizm: elementlarni samarali qo'shishimiz yoki o'chirishimiz mumkin.
• Qidiruv samaradorligi: BST da ma'lum bir elementni qidirishga ketadigan vaqt O(log n) bo‘ladi, chunki har bir qidiruvda daraxtning yarmi qidiruvdan chiqarib tashlanadi.

BST ning kamchiliklari:

• Treening muvozanati buzilgan bo‘lsa (masalan, barcha elementlar ketma-ket joylashsa), qidiruv samaradorligi O(n)ga tushib ketadi.
• Har bir node uchun left va right ko‘rsatkichlarini ham saqlashni talab qiladi, bu kompyuterda xotira iste’molini oshiradi.

---

Dictionary

Dictionary - bu xuddi lug‘at kitoblarlar kabi, unda so‘z va uning ta’rifi bo‘lganidek, uning elementlari kalit (key) va qiymat (value) ga ega.

Dictionary'dan biror bir elementni so'rasak, u elementni bizga O(1) vaqtda qaytaradi. Dictionary'lar xeshlash orqali aynan shu tezlikni ta’minlay oladi.

Xeshlash – kirish massividagi ma'lumotlarni maxsus algoritm yordamida bitlar ketma-ketligiga aylantirish jarayonidir.

Xesh funksiyasi – bu ixtiyoriy uzunlikdagi satrdan aniq uzunlikdagi bitlardan iborat satrni hosil qiladigan algoritmdir.

Hash table – bu massivlar va linked list'larning ajoyib kombinatsiyasidir. Uni quyidagicha tasavvur qilishimiz mumkin:

Kolliziya (Collisions) – bu ikkita har xil kirish ma'lumotidan bir xesh qiymat hosil bo'lib qolishidir. Yuqoridagi rasmda kolliziya bo'lgan elementlar linked list sifatida bog'langan. Xesh funksiyasini yaxshilash orqali kolliziya bo'lish ehtimolini kamashtirish mumkin.

Xesh funksiyasiga oddiy bir misol:

#include <ctype.h>

unsigned int hash(const char *word)
{
    return toupper(word[0]) - 'A';
}

Ushbu maqolada CS50x 2024 manbasidan foydalanilgan.