CS- Minggu 5

Struktur data

Struktur maklumat ialah bentuk penyusunan maklumat dalam ingatan. Terdapat banyak cara untuk menyusun data dalam ingatan.

Struktur data abstrak ialah struktur yang kami bayangkan secara konsep. Kebiasaan dengan struktur abstrak ini memudahkan untuk melaksanakan struktur data dalam amalan pada masa hadapan.

---

Timbunan dan Baris Gilir

Barisan ialah satu bentuk struktur data abstrak.
Struktur data Queue berfungsi mengikut peraturan FIFO (Dulu Masuk Dulu, "elemen tambah pertama keluar dahulu") peraturan.
Ia boleh dibayangkan sebagai contoh orang yang berdiri dalam barisan di tempat tarikan: orang pertama dalam barisan masuk dahulu, dan yang terakhir masuk terakhir.

Operasi berikut boleh dilakukan dengan

Baris Gilir:

• Enqueue: tambah elemen baharu pada penghujung baris gilir.
• Dequeue: alih keluar elemen dari permulaan baris gilir.

Tindanan struktur data berfungsi mengikut peraturan LIFO (Masuk Dahulu Terakhir, "elemen yang ditambahkan terakhir keluar dahulu") peraturan
Contohnya, susun pinggan di dapur: pinggan terakhir diambil dahulu.

Timbunan mempunyai operasi berikut:

• Tekan: letakkan elemen baharu pada tindanan.
• Pop: alih keluar elemen daripada tindanan.

---

Susunan

Array ialah kaedah menyimpan data secara berurutan dalam ingatan. Tatasusunan boleh digambarkan sebagai:

Memori mungkin mengandungi nilai lain yang disimpan oleh atur cara, fungsi dan pembolehubah lain, serta nilai berlebihan yang digunakan sebelum ini dan tidak lagi digunakan:

Jika kita ingin menambah elemen baharu - 4 - pada tatasusunan, kita perlu memperuntukkan memori baharu dan memindahkan tatasusunan lama ke dalamnya. Memori baru ini mungkin penuh dengan nilai sampah:

Jika kita mengalihkan elemen ke tatasusunan dan menambah nilai baharu, nilai baharu akan ditulis di atas nilai lama yang tidak diperlukan dalam memori baharu yang diperuntukkan:

Kelemahan pendekatan ini ialah keseluruhan tatasusunan perlu disalin setiap kali elemen baharu ditambahkan.
Bagaimana jika kita meletakkan 4 di tempat lain dalam ingatan? Kemudian, mengikut definisi, ini bukan lagi tatasusunan, kerana 4 tidak bersebelahan dengan elemen tatasusunan dalam ingatan.

Kadangkala, pengaturcara memperuntukkan lebih banyak memori daripada yang diperlukan (cth 300 untuk 30 elemen). Tetapi ini adalah reka bentuk yang buruk kerana ia membazirkan sumber sistem dan dalam kebanyakan kes memori tambahan tidak diperlukan. Oleh itu, adalah penting untuk memperuntukkan ingatan mengikut keperluan khusus.

---

Senarai Terpaut

Senarai Terpaut ialah salah satu struktur data yang paling berkuasa dalam bahasa pengaturcaraan C. Mereka membenarkan menggabungkan nilai yang terletak di kawasan memori yang berbeza ke dalam satu senarai. Ia juga membolehkan kami mengembangkan atau mengecilkan senarai secara dinamik mengikut kehendak kami.

Setiap nod menyimpan dua nilai:

• nilai;
• ialah penunjuk yang memegang alamat memori nod seterusnya. Dan nod terakhir mengandungi NULL untuk menunjukkan bahawa tiada unsur lain selepasnya.

Kami menyimpan alamat elemen pertama senarai terpaut ke penuding (penunjuk).

Dalam bahasa pengaturcaraan C, kita boleh menulis nod sebagai:

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

Mari kita lihat proses mencipta

Senarai terpaut:

• Kami mengisytiharkan nod *senarai:

• peruntukkan memori untuk nod:

• masukkan nilai nod: n->nombor = 1:

• Kami menetapkan indeks seterusnya nod kepada NULL: n->next = NULL:

• mari samakan senarai dengan:

• Dalam susunan yang sama, kami mencipta nod baharu dengan nilai 2:

• Untuk menyambung kedua-dua nod, kami menetapkan indeks seterusnya n kepada senarai:

• Dan akhirnya, kami menetapkan senarai kepada n. Kini kami mempunyai senarai terpaut yang terdiri daripada dua elemen:

Dalam bahasa pengaturcaraan C, kita boleh menulis kod proses ini seperti berikut:

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

Terdapat beberapa kelemahan apabila bekerja dengan senarai terpaut:

• Lebih banyak ingatan: untuk setiap elemen, anda perlu menyimpan bukan sahaja nilai elemen itu sendiri, tetapi juga penunjuk kepada elemen seterusnya.
• Memanggil elemen mengikut indeks: dalam tatasusunan kita boleh memanggil elemen tertentu mengikut indeks, tetapi dalam senarai terpaut adalah mustahil. Untuk mencari kedudukan elemen tertentu, perlu melalui semua elemen dalam urutan, bermula dengan elemen pertama.

---

pokok

Pokok Carian Perduaan (BST) ialah struktur maklumat yang membolehkan penyimpanan, carian dan pengambilan data yang cekap.
Marilah kita diberikan urutan nombor yang disusun:

Kami meletakkan elemen di tengah di bahagian atas, nilai lebih kecil daripada elemen di tengah di sebelah kiri, dan nilai yang lebih besar di sebelah kanan:

Kami menyambung setiap elemen antara satu sama lain menggunakan penunjuk:

Kod berikut menunjukkan cara melaksanakan BST:

#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;
    }
}

Kami memperuntukkan memori untuk setiap nod dan nilainya disimpan dalam nombor, jadi setiap nod mempunyai penunjuk kiri dan kanan. Fungsi print_tree mencetak setiap nod dalam rekursi berurutan dari kiri ke kanan. Fungsi free_tree secara rekursif membebaskan semua nod struktur data daripada memori.

Kelebihan

BST:

• Dinamisme: kita boleh menambah atau mengalih keluar elemen dengan cekap.
• Kecekapan Carian: Masa yang diambil untuk mencari elemen tertentu dalam BST ialah O(log n), kerana separuh daripada pokok dikecualikan daripada carian dalam setiap carian.

Kelemahan

BST:

• Jika baki pokok itu rosak (contohnya, jika semua elemen diletakkan dalam satu baris), kecekapan carian turun kepada O(n).
• Memerlukan untuk menyimpan kedua-dua penunjuk kiri dan kanan untuk setiap nod, yang meningkatkan penggunaan memori pada komputer.

---

Kamus

Kamus adalah seperti buku kamus, ia mengandungi perkataan dan definisinya, elemennya kunci (kunci) dan nilai mempunyai (nilai).

Jika kita menanyakan

Kamus untuk elemen, ia mengembalikan elemen itu kepada kita dalam masa O(1). Kamus boleh memberikan kelajuan ini dengan tepat melalui pencincangan.

Hashing ialah proses menukar data dalam tatasusunan input kepada jujukan bit menggunakan algoritma khas.

Fungsi cincang ialah algoritma yang menghasilkan rentetan bit panjang tetap daripada rentetan panjang arbitrari.

Jadual cincang ialah gabungan tatasusunan dan senarai terpaut yang hebat. Kita boleh bayangkan seperti berikut:

Perlanggaran (Perlanggaran) ialah apabila dua input berbeza menghasilkan satu nilai cincang. Dalam imej di atas, elemen yang berlanggar disambungkan sebagai senarai terpaut. Dengan menambah baik fungsi cincang, kebarangkalian perlanggaran dapat dikurangkan.

Contoh mudah fungsi cincang ialah:

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

Artikel ini menggunakan sumber CS50x 2024.

Atas ialah kandungan terperinci CS- Minggu 5. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!