Week 5 Cấu trúc dữ liệu

Chào mừng các bạn!

• Tất cả những tuần trước đã cung cấp cho bạn những khối kiến thức nền tảng của lập trình.

• Tất cả những gì bạn đã học trong C sẽ cho phép bạn triển khai các khối kiến thức này trong các ngôn ngữ lập trình cấp cao hơn như Python.

• Mỗi tuần, các khái niệm ngày càng trở nên thử thách hơn, giống như một con dốc ngày càng dốc. Tuần này, thử thách sẽ dần ổn định khi chúng ta khám phá về cấu trúc dữ liệu.

• Cho đến nay, bạn đã học về cách một mảng có thể tổ chức dữ liệu trong bộ nhớ.

• Hôm nay, chúng ta sẽ nói về việc tổ chức dữ liệu trong bộ nhớ và các khả năng thiết kế nảy sinh từ kiến thức ngày càng tăng của bạn.

Cấu trúc dữ liệu (Data Structures)

Cấu trúc dữ liệu về cơ bản là các hình thức tổ chức trong bộ nhớ.

• Có nhiều cách để tổ chức dữ liệu trong bộ nhớ.

Kiểu dữ liệu trừu tượng (Abstract data types) là những kiểu dữ liệu mà chúng ta có thể tưởng tượng về mặt khái niệm. Khi học về khoa học máy tính, việc bắt đầu với những cấu trúc dữ liệu khái niệm này thường rất hữu ích. Việc học chúng sẽ giúp bạn dễ dàng hiểu cách triển khai các cấu trúc dữ liệu cụ thể sau này.

Hàng đợi (Queues)

Hàng đợi là một dạng cấu trúc dữ liệu trừu tượng.

• Hàng đợi có các thuộc tính cụ thể. Cụ thể, chúng tuân theo cơ chế FIFO hoặc “vào trước ra trước” (first in first out). Bạn có thể tưởng tượng mình đang đứng xếp hàng chờ chơi một trò chơi ở công viên giải trí. Người đầu tiên đứng vào hàng sẽ được chơi trước. Người cuối cùng đứng vào hàng sẽ được chơi cuối cùng.

• Hàng đợi có các hành động cụ thể đi kèm. Ví dụ, một mục có thể được enqueued (thêm vào hàng đợi); tức là mục đó gia nhập vào hàng hoặc hàng đợi. Hơn nữa, một mục có thể được dequeued (lấy ra khỏi hàng đợi) hoặc rời khỏi hàng đợi khi nó đã lên đến đầu hàng.

Trong mã nguồn, bạn có thể hình dung một hàng đợi như sau:

const int CAPACITY = 50;

typedef struct
{
    person people[CAPACITY];
    int size;
}
queue;

Lưu ý rằng một mảng có tên people có kiểu dữ liệu là person. CAPACITY là giới hạn tối đa của hàng đợi. Số nguyên size cho biết hàng đợi thực sự đang chứa bao nhiêu người, bất kể nó có thể chứa được bao nhiêu.

Ngăn xếp (Stacks)

• Hàng đợi tương phản với ngăn xếp. Về cơ bản, các thuộc tính của ngăn xếp khác với hàng đợi. Cụ thể, nó tuân theo cơ chế LIFO hoặc “vào sau ra trước” (last in first out). Giống như việc xếp các khay trong nhà ăn, chiếc khay được đặt vào chồng cuối cùng sẽ là chiếc khay đầu tiên được lấy ra.

• Ngăn xếp có các hành động cụ thể đi kèm. Ví dụ, push đặt một cái gì đó lên trên cùng của ngăn xếp. Pop là lấy một cái gì đó ra khỏi đỉnh ngăn xếp.

Trong mã nguồn, bạn có thể hình dung một ngăn xếp như sau:

const int CAPACITY = 50;

typedef struct
{
    person people[CAPACITY];
    int size;
}
stack;

Lưu ý rằng một mảng có tên people có kiểu dữ liệu là person. CAPACITY là giới hạn tối đa của ngăn xếp. Số nguyên size cho biết ngăn xếp thực sự đang chứa bao nhiêu mục, bất kể nó có thể chứa được bao nhiêu. Lưu ý rằng mã này giống với mã của hàng đợi.

• Bạn có thể nhận thấy rằng mã trên có một hạn chế. Vì dung lượng của mảng luôn được xác định trước trong mã này. Do đó, ngăn xếp có thể luôn bị dư thừa kích thước. Bạn có thể tưởng tượng chỉ sử dụng một vị trí trong ngăn xếp trong số 5000 vị trí có sẵn.

• Sẽ rất tốt nếu ngăn xếp của chúng ta có tính động – có khả năng mở rộng khi các mục được thêm vào nó.

Jack Learns the Facts

• Chúng ta đã xem một video có tên Jack Learns the Facts của Giáo sư Shannon Duvall thuộc Đại học Elon.

Thay đổi kích thước mảng (Resizing Arrays)

• Quay lại Tuần 2, chúng tôi đã giới thiệu cho bạn cấu trúc dữ liệu đầu tiên.

• Một mảng là một khối bộ nhớ liền kề.

Bạn có thể hình dung một mảng như sau:

Trong bộ nhớ, có các giá trị khác đang được lưu trữ bởi các chương trình, hàm và biến khác. Nhiều giá trị trong số này có thể là các giá trị rác không được sử dụng, vốn đã được sử dụng tại một thời điểm nào đó nhưng hiện tại đã có sẵn để sử dụng.

Hãy tưởng tượng bạn muốn lưu trữ giá trị thứ tư 4 trong mảng của mình. Điều cần thiết là cấp phát một vùng bộ nhớ mới và chuyển mảng cũ sang mảng mới? Ban đầu, vùng bộ nhớ mới này sẽ được lấp đầy bằng các giá trị rác.

Khi các giá trị được thêm vào vùng bộ nhớ mới này, các giá trị rác cũ sẽ bị ghi đè.

Cuối cùng, tất cả các giá trị rác cũ sẽ bị ghi đè bằng dữ liệu mới của chúng ta.

• Một trong những nhược điểm của cách tiếp cận này là thiết kế kém: Mỗi khi chúng ta thêm một số, chúng ta phải sao chép từng mục của mảng.

Mảng (Arrays)

• Sẽ thật tuyệt nếu chúng ta có thể đặt số 4 ở một nơi khác trong bộ nhớ? Theo định nghĩa, đây sẽ không còn là một mảng nữa vì 4 sẽ không còn nằm trong bộ nhớ liền kề. Làm thế nào chúng ta có thể kết nối các vị trí khác nhau trong bộ nhớ?

Trong terminal của bạn, gõ code list.c và viết mã như sau:

// Triển khai danh sách các số với mảng có kích thước cố định

#include <stdio.h>

int main(void)
{
    // Danh sách kích thước 3
    int list[3];

    // Khởi tạo danh sách với các số
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    // In danh sách
    for (int i = 0; i < 3; i++)
    {
        printf("%i\n", list[i]);
    }
}

Lưu ý rằng đoạn mã trên rất giống với những gì chúng ta đã học trước đây trong khóa học này. Bộ nhớ được cấp phát trước cho ba mục.

Dựa trên kiến thức thu được gần đây hơn, chúng ta có thể tận dụng hiểu biết về con trỏ để tạo ra một thiết kế tốt hơn trong mã này. Sửa đổi mã của bạn như sau:

// Triển khai danh sách các số với mảng có kích thước động

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

int main(void)
{
    // Danh sách kích thước 3
    int *list = malloc(3 * sizeof(int));
    if (list == NULL)
    {
        return 1;
    }

    // Khởi tạo danh sách kích thước 3 với các số
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    // Danh sách kích thước 4
    int *tmp = malloc(4 * sizeof(int));
    if (tmp == NULL)
    {
        free(list);
        return 1;
    }

    // Sao chép danh sách kích thước 3 sang danh sách kích thước 4
    for (int i = 0; i < 3; i++)
    {
        tmp[i] = list[i];
    }

    // Thêm số vào danh sách kích thước 4
    tmp[3] = 4;

    // Giải phóng danh sách kích thước 3
    free(list);

    // Ghi nhớ danh sách kích thước 4
    list = tmp;

    // In danh sách
    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }

    // Giải phóng danh sách
    free(list);
    return 0;
}

Lưu ý rằng một danh sách gồm ba số nguyên đã được tạo ra. Sau đó, ba địa chỉ bộ nhớ có thể được gán các giá trị 1, 2 và 3. Tiếp theo, một danh sách có kích thước bốn được tạo ra. Sau đó, danh sách được sao chép từ danh sách thứ nhất sang danh sách thứ hai. Giá trị 4 được thêm vào danh sách tmp. Vì khối bộ nhớ mà list trỏ đến không còn được sử dụng, nó được giải phóng bằng lệnh free(list). Cuối cùng, trình biên dịch được yêu cầu trỏ con trỏ list ngay bây giờ đến khối bộ nhớ mà tmp trỏ đến. Nội dung của list được in ra và sau đó được giải phóng. Ngoài ra, hãy lưu ý việc bao gồm thư viện stdlib.h.

• Sẽ rất hữu ích nếu coi cả list và tmp đều là những biển báo trỏ đến một khối bộ nhớ. Như trong ví dụ trên, tại một thời điểm list đã trỏ đến một mảng có kích thước 3. Cuối cùng, list được yêu cầu trỏ đến một khối bộ nhớ có kích thước 4. Về mặt kỹ thuật, ở cuối đoạn mã trên, cả tmp và list đều trỏ đến cùng một khối bộ nhớ.

Một cách để chúng ta có thể sao chép mảng mà không cần vòng lặp for là sử dụng realloc:

// Triển khai danh sách các số với mảng có kích thước động sử dụng realloc

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

int main(void)
{
    // Danh sách kích thước 3
    int *list = malloc(3 * sizeof(int));
    if (list == NULL)
    {
        return 1;
    }

    // Khởi tạo danh sách kích thước 3 với các số
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    // Thay đổi kích thước danh sách thành 4
    int *tmp = realloc(list, 4 * sizeof(int));
    if (tmp == NULL)
    {
        free(list);
        return 1;
    }
    list = tmp;

    // Thêm số vào danh sách
    list[3] = 4;

    // In danh sách
    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }

    // Giải phóng danh sách
    free(list);
    return 0;
}

Lưu ý rằng danh sách được cấp phát lại thành một mảng mới thông qua realloc.

• Người ta có thể bị cám dỗ để cấp phát nhiều bộ nhớ hơn mức cần thiết cho danh sách, chẳng hạn như 30 mục thay vì 3 hoặc 4 mục cần thiết. Tuy nhiên, đây là một thiết kế kém vì nó tiêu tốn tài nguyên hệ thống khi chúng có thể không cần thiết. Hơn nữa, có rất ít sự đảm bảo rằng bộ nhớ cho hơn 30 mục cuối cùng sẽ được cần đến.

Danh sách liên kết (Linked Lists)

• Trong những tuần gần đây, bạn đã học về ba thành phần cơ bản hữu ích. Một struct là một kiểu dữ liệu mà bạn có thể tự định nghĩa. Dấu . trong ký hiệu dấu chấm (dot notation) cho phép bạn truy cập các biến bên trong cấu trúc đó. Toán tử * được sử dụng để khai báo một con trỏ hoặc truy xuất giá trị của một biến (dereference).

• Hôm nay, bạn được giới thiệu toán tử ->. Nó là một mũi tên. Toán tử này đi đến một địa chỉ và nhìn vào bên trong một cấu trúc.

• Danh sách liên kết là một trong những cấu trúc dữ liệu mạnh mẽ nhất trong C. Danh sách liên kết cho phép bạn bao gồm các giá trị nằm ở các vùng bộ nhớ khác nhau. Hơn nữa, chúng cho phép bạn tăng và giảm danh sách một cách linh hoạt theo ý muốn.

Bạn có thể hình dung ba giá trị được lưu trữ trong ba vùng bộ nhớ khác nhau như sau:

• Làm thế nào người ta có thể liên kết các giá trị này lại với nhau trong một danh sách?

Chúng ta có thể hình dung dữ liệu được mô tả ở trên như sau:

Chúng ta có thể sử dụng thêm bộ nhớ để theo dõi xem mục tiếp theo ở đâu bằng cách sử dụng một con trỏ.

Lưu ý rằng NULL được sử dụng để chỉ ra rằng không còn gì tiếp theo (next) trong danh sách.

Theo quy ước, chúng ta sẽ giữ thêm một phần tử nữa trong bộ nhớ, một con trỏ, để theo dõi mục đầu tiên trong danh sách, được gọi là head (đầu) của danh sách.

Bỏ qua các địa chỉ bộ nhớ, danh sách sẽ xuất hiện như sau:

Những ô này được gọi là node (nút). Một node chứa cả một item (mục dữ liệu) và một con trỏ gọi là next. Trong mã nguồn, bạn có thể hình dung một node như sau:

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

Lưu ý rằng mục chứa trong node này là một số nguyên có tên là number. Thứ hai, một con trỏ đến một node có tên là next được bao gồm, nó sẽ trỏ đến một node khác ở đâu đó trong bộ nhớ.

Chúng ta có thể tạo lại list.c để sử dụng danh sách liên kết:

// Bắt đầu xây dựng danh sách liên kết bằng cách thêm các node vào đầu

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

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

int main(void)
{
    // Bộ nhớ cho các số
    node *list = NULL;

    // Xây dựng danh sách
    for (int i = 0; i < 3; i++)
    {
        // Cấp phát node cho số
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = get_int("Number: ");
        n->next = NULL;

        // Thêm node vào đầu danh sách
        n->next = list;
        list = n;
    }
    return 0;
}

Đầu tiên, một node được định nghĩa là một struct. Đối với mỗi phần tử của danh sách, bộ nhớ cho một node được cấp phát thông qua malloc với kích thước của một node. n->number (hoặc trường number của n) được gán một số nguyên. n->next (hoặc trường next của n) được gán null. Sau đó, node được đặt ở đầu danh sách tại vị trí bộ nhớ list.

Về mặt khái niệm, chúng ta có thể tưởng tượng quá trình tạo một danh sách liên kết. Đầu tiên, node *list được khai báo, nhưng nó mang một giá trị rác.

Tiếp theo, một node có tên là n được cấp phát trong bộ nhớ.

Tiếp theo, trường number của node được gán giá trị 1.

Tiếp theo, trường next của node được gán NULL.

Tiếp theo, list được trỏ đến vị trí bộ nhớ mà n trỏ đến. n và list bây giờ cùng trỏ đến một chỗ.

Một node mới sau đó được tạo ra. Cả trường number và next đều được lấp đầy bằng các giá trị rác.

Giá trị number của node n (node mới) được cập nhật thành 2.

Ngoài ra, trường next cũng được cập nhật.

Quan trọng nhất, chúng ta không muốn mất kết nối với bất kỳ node nào trong số này kẻo chúng bị mất vĩnh viễn. Theo đó, trường next của n được trỏ đến cùng một vị trí bộ nhớ với list.

Cuối cùng, list được cập nhật để trỏ vào n. Bây giờ chúng ta có một danh sách liên kết gồm hai mục.

• Nhìn vào sơ đồ danh sách của chúng ta, chúng ta có thể thấy rằng số cuối cùng được thêm vào là số đầu tiên xuất hiện trong danh sách. Theo đó, nếu chúng ta in danh sách theo thứ tự, bắt đầu từ node đầu tiên, danh sách sẽ xuất hiện không đúng thứ tự ban đầu.

Chúng ta có thể in danh sách theo đúng thứ tự như sau:

// In các node trong danh sách liên kết bằng vòng lặp while

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

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

int main(void)
{
    // Bộ nhớ cho các số
    node *list = NULL;

    // Xây dựng danh sách
    for (int i = 0; i < 3; i++)
    {
        // Cấp phát node cho số
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = get_int("Number: ");
        n->next = NULL;

        // Thêm node vào đầu danh sách
        n->next = list;
        list = n;
    }

    // In các số
    node *ptr = list;
    while (ptr != NULL)
    {
        printf("%i\n", ptr->number);
        ptr = ptr->next;
    }
    return 0;
}

Lưu ý rằng node *ptr = list tạo ra một biến tạm thời trỏ cùng vào điểm mà list đang trỏ đến. Vòng lặp while in ra những gì tại node mà ptr trỏ đến, sau đó cập nhật ptr để trỏ đến node next (tiếp theo) trong danh sách.

• Trong ví dụ này, việc chèn vào danh sách luôn theo thứ tự \(O(1)\), vì chỉ mất một số lượng bước rất nhỏ để chèn vào đầu danh sách.

• Xem xét lượng thời gian cần thiết để tìm kiếm trong danh sách này, nó theo thứ tự \(O(n)\), vì trong trường hợp xấu nhất, toàn bộ danh sách phải luôn được tìm kiếm để tìm thấy một mục. Độ phức tạp thời gian để thêm một phần tử mới vào danh sách sẽ phụ thuộc vào vị trí phần tử đó được thêm vào. Điều này được minh họa trong các ví dụ dưới đây.

• Danh sách liên kết không được lưu trữ trong một khối bộ nhớ liền kề. Chúng có thể mở rộng bao nhiêu tùy thích, miễn là có đủ tài nguyên hệ thống. Tuy nhiên, nhược điểm là cần nhiều bộ nhớ hơn để theo dõi danh sách so với mảng. Đối với mỗi phần tử, bạn không chỉ phải lưu trữ giá trị của phần tử đó mà còn phải lưu trữ một con trỏ tới node tiếp theo. Hơn nữa, danh sách liên kết không thể được truy cập bằng chỉ số (index) như mảng vì chúng ta cần đi qua \(n - 1\) phần tử đầu tiên để tìm vị trí của phần tử thứ \(n\). Do đó, danh sách được mô tả ở trên phải được tìm kiếm tuyến tính. Vì vậy, tìm kiếm nhị phân không khả thi trong một danh sách được xây dựng như trên.

Hơn nữa, bạn có thể đặt các số vào cuối danh sách như được minh họa trong đoạn mã này:

// Thêm các số vào cuối danh sách liên kết

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

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

int main(void)
{
    // Bộ nhớ cho các số
    node *list = NULL;

    // Xây dựng danh sách
    for (int i = 0; i < 3; i++)
    {
        // Cấp phát node cho số
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = get_int("Number: ");
        n->next = NULL;

        // Nếu danh sách trống
        if (list == NULL)
        {
            // Node này là toàn bộ danh sách
            list = n;
        }

        // Nếu danh sách đã có số
        else
        {
            // Duyệt qua các node trong danh sách
            for (node *ptr = list; ptr != NULL; ptr = ptr->next)
            {
                // Nếu ở cuối danh sách
                if (ptr->next == NULL)
                {
                    // Thêm node vào cuối
                    ptr->next = n;
                    break;
                }
            }
        }
    }

    // In các số
    for (node *ptr = list; ptr != NULL; ptr = ptr->next)
    {
        printf("%i\n", ptr->number);
    }

    // Giải phóng bộ nhớ
    node *ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
    return 0;
}

Lưu ý cách mã này duyệt dọc danh sách này để tìm điểm kết thúc. Khi nối thêm một phần tử (thêm vào cuối danh sách), mã của chúng ta sẽ chạy trong \(O(n)\), vì chúng ta phải đi qua toàn bộ danh sách trước khi có thể thêm phần tử cuối cùng. Hơn nữa, hãy lưu ý rằng một biến tạm thời có tên next được sử dụng để theo dõi ptr->next.

Hơn nữa, bạn có thể sắp xếp danh sách của mình khi các mục được thêm vào:

// Triển khai danh sách liên kết các số đã được sắp xếp

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

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

int main(void)
{
    // Bộ nhớ cho các số
    node *list = NULL;

    // Xây dựng danh sách
    for (int i = 0; i < 3; i++)
    {
        // Cấp phát node cho số
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = get_int("Number: ");
        n->next = NULL;

        // Nếu danh sách trống
        if (list == NULL)
        {
            list = n;
        }

        // Nếu số thuộc về đầu danh sách
        else if (n->number < list->number)
        {
            n->next = list;
            list = n;
        }

        // Nếu số thuộc về vị trí sau trong danh sách
        else
        {
            // Duyệt qua các node trong danh sách
            for (node *ptr = list; ptr != NULL; ptr = ptr->next)
            {
                // Nếu ở cuối danh sách
                if (ptr->next == NULL)
                {
                    // Thêm node vào cuối
                    ptr->next = n;
                    break;
                }

                // Nếu ở giữa danh sách
                if (n->number < ptr->next->number)
                {
                    n->next = ptr->next;
                    ptr->next = n;
                    break;
                }
            }
        }
    }

    // In các số
    for (node *ptr = list; ptr != NULL; ptr = ptr->next)
    {
        printf("%i\n", ptr->number);
    }

    // Giải phóng bộ nhớ
    node *ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
    return 0;
}

Lưu ý cách danh sách này được sắp xếp khi nó được xây dựng. Để chèn một phần tử theo thứ tự cụ thể này, mã của chúng ta vẫn sẽ chạy trong \(O(n)\) cho mỗi lần chèn, vì trong trường hợp xấu nhất, chúng ta sẽ phải xem qua tất cả các phần tử hiện có.

• Mã này có vẻ phức tạp. Tuy nhiên, lưu ý rằng với con trỏ và cú pháp ở trên, chúng ta có thể liên kết dữ liệu với nhau ở những vị trí khác nhau trong bộ nhớ.

Cây (Trees)

• Mảng cung cấp bộ nhớ liền kề có thể được tìm kiếm nhanh chóng. Mảng cũng mang lại cơ hội để thực hiện tìm kiếm nhị phân.

• Liệu chúng ta có thể kết hợp những gì tốt nhất của cả mảng và danh sách liên kết không?

Cây tìm kiếm nhị phân (Binary search trees) là một cấu trúc dữ liệu khác có thể được sử dụng để lưu trữ dữ liệu hiệu quả hơn để có thể tìm kiếm và truy xuất.

Bạn có thể hình dung một dãy số đã được sắp xếp.

Hãy tưởng tượng sau đó giá trị trung tâm trở thành đỉnh của một cái cây. Những giá trị nhỏ hơn giá trị này được đặt sang bên trái. Những giá trị lớn hơn giá trị này ở bên phải.

Con trỏ sau đó có thể được sử dụng để trỏ đến vị trí chính xác của từng vùng bộ nhớ sao cho mỗi node này có thể được kết nối với nhau.

Trong mã nguồn, điều này có thể được triển khai như sau.

// Triển khai danh sách các số dưới dạng cây tìm kiếm nhị phân

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

// Đại diện cho một node
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)
{
    // Cây kích thước 0
    node *tree = NULL;

    // Thêm số vào danh sách
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    n->number = 2;
    n->left = NULL;
    n->right = NULL;
    tree = n;

    // Thêm số vào danh sách
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        free_tree(tree);
        return 1;
    }
    n->number = 1;
    n->left = NULL;
    n->right = NULL;
    tree->left = n;

    // Thêm số vào danh sách
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        free_tree(tree);
        return 1;
    }
    n->number = 3;
    n->left = NULL;
    n->right = NULL;
    tree->right = n;

    // In cây
    print_tree(tree);

    // Giải phóng cây
    free_tree(tree);
    return 0;
}

void free_tree(node *root)
{
    if (root == NULL)
    {
        return;
    }
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

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

Lưu ý hàm tìm kiếm này bắt đầu bằng cách đi đến vị trí của tree. Sau đó, nó sử dụng đệ quy để tìm kiếm number. Hàm free_tree giải phóng cây một cách đệ quy. print_tree in cây một cách đệ quy.

• Một cái cây như trên cung cấp tính năng động mà mảng không có. Nó có thể to ra hoặc nhỏ lại theo ý muốn của chúng ta.

• Hơn nữa, cấu trúc này cung cấp thời gian tìm kiếm là \(O(log n)\) khi cây được cân bằng.

Từ điển (Dictionaries)

Từ điển là một cấu trúc dữ liệu khác.

• Từ điển, giống như từ điển dạng sách thực tế có một từ và một định nghĩa, có một key (khóa) và một value (giá trị).

Chén thánh của độ phức tạp thời gian thuật toán là \(O(1)\) hoặc thời gian hằng số. Nghĩa là, mục tiêu cuối cùng là việc truy cập diễn ra tức thì.

• Từ điển có thể cung cấp tốc độ truy cập này thông qua kỹ thuật băm (hashing).

Băm và Bảng băm (Hashing and Hash Tables)

Băm (Hashing) là ý tưởng lấy một giá trị và có thể xuất ra một giá trị khác đóng vai trò như một phím tắt để dẫn đến nó sau này.

• Ví dụ, băm apple có thể cho ra giá trị là 1, và berry có thể được băm thành 2. Do đó, việc tìm apple dễ dàng như việc hỏi thuật toán băm xem apple được lưu trữ ở đâu. Mặc dù không lý tưởng về mặt thiết kế, nhưng cuối cùng, việc đặt tất cả những từ bắt đầu bằng chữ a vào một cái xô và chữ b vào một cái xô khác, khái niệm chia xô (bucketizing) các giá trị đã băm này minh họa cách bạn có thể sử dụng khái niệm này: một giá trị băm có thể được sử dụng làm phím tắt để tìm một giá trị như vậy.

• Một hàm băm (hash function) là một thuật toán rút gọn một giá trị lớn thành một thứ gì đó nhỏ và có thể dự đoán được. Nói chung, hàm này nhận vào một mục bạn muốn thêm vào bảng băm và trả về một số nguyên đại diện cho chỉ số mảng mà mục đó nên được đặt vào.

• Một bảng băm (hash table) là sự kết hợp tuyệt vời giữa cả mảng và danh sách liên kết. Khi được triển khai trong mã nguồn, bảng băm là một mảng chứa các con trỏ dẫn đến các node.

Một bảng băm có thể được hình dung như sau:

Lưu ý rằng đây là một mảng được gán cho mỗi giá trị của bảng chữ cái.

Sau đó, tại mỗi vị trí của mảng, một danh sách liên kết được sử dụng để theo dõi từng giá trị được lưu trữ ở đó:

Xung đột (Collisions) là khi bạn thêm các giá trị vào bảng băm và một giá trị đã tồn tại tại vị trí đã băm đó. Trong ví dụ trên, các giá trị xung đột chỉ đơn giản được thêm vào cuối danh sách.

Xung đột có thể được giảm bớt bằng cách lập trình bảng băm và thuật toán băm tốt hơn. Bạn có thể hình dung một sự cải tiến so với cách trên như sau:

Hãy xem xét ví dụ sau về thuật toán băm:

Điều này có thể được triển khai trong mã như sau:

#include <ctype.h>

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

Lưu ý cách hàm băm trả về giá trị của toupper(word[0]) - 'A'.

• Bạn, với tư cách là lập trình viên, phải đưa ra quyết định về lợi thế của việc sử dụng nhiều bộ nhớ hơn để có một bảng băm lớn và có khả năng giảm thời gian tìm kiếm hoặc sử dụng ít bộ nhớ hơn và có khả năng làm tăng thời gian tìm kiếm.

• Cấu trúc này cung cấp thời gian tìm kiếm là \(O(n)\).

Trie

Trie là một dạng cấu trúc dữ liệu khác. Trie là cây của các mảng.

Trie luôn có thể tìm kiếm được trong thời gian hằng số.

• Một nhược điểm của Trie là chúng có xu hướng chiếm một lượng bộ nhớ lớn. Lưu ý rằng chúng ta cần \(26 \times 4 = 104\) node chỉ để lưu trữ từ Toad!

Từ Toad sẽ được lưu trữ như sau:

Từ Tom sau đó sẽ được lưu trữ như sau:

• Cấu trúc này cung cấp thời gian tìm kiếm là \(O(1)\).

• Nhược điểm của cấu trúc này là cần bao nhiêu tài nguyên để sử dụng nó.

Tổng kết

Trong bài học này, bạn đã học về việc sử dụng con trỏ để xây dựng các cấu trúc dữ liệu mới. Cụ thể, chúng ta đã đi sâu vào…

• Cấu trúc dữ liệu

• Ngăn xếp và hàng đợi

• Thay đổi kích thước mảng

• Danh sách liên kết

• Từ điển

• Trie

Hẹn gặp lại các bạn lần sau!