+3

Bài 14: Cấp phát bộ nhớ động và Danh sách liên kết (Phần 2) - Danh sách liên kết (Linked List)

Đây là bài viết số 2 thuộc bài học Cấp phát bộ nhớ động và Danh sách liên kết của chuyên đề lập trình C++ cơ bản. Để nắm vững bài viết này, trước tiên các bạn hãy tìm đọc lại các bài viết trước đây gồm các kiến thức liên quan:

I. Giới thiệu chung

Đối với những ai học lập trình, bất kể cơ bản hay nâng cao, cấu trúc dữ liệu mảng luôn luôn là một cấu trúc dữ liệu được nghiên cứu đầu tiên, vì nó quá đơn giản và quen thuộc. Giả sử chúng ta cần phải lưu trữ một dãy số và tính trung bình cộng của nó, mảng là sự lựa chọn không thể tuyệt vời hơn. Đặc biệt, sức mạnh của mảng đến từ khả năng truy cập vị trí ngẫu nhiên trên mảng bằng chỉ số chỉ trong O(1)O(1).

Tuy nhiên, không phải mảng không có hạn chế. Một số vấn đề có thể sinh ra khi sử dụng mảng là:

  • Bắt buộc phải biết trước số lượng phần tử của dãy số cần lưu trữ.
  • Do các phần tử của mảng được lưu trữ trên một đoạn vị trí liên tiếp nhau trong bộ nhớ máy tính, nên khi cần tăng kích thước mảng hoặc thêm/xóa một phần tử vào vị trí bất kì trong mảng sẽ cần tới độ phức tạp O(n)O(n).

Để khắc phục những nhược điểm trên, người ta nghĩ ra một cấu trúc dữ liệu là danh sách liên kết.

Về bản chất, danh sách liên kết có chức năng giống như một mảng dùng để lưu trữ một tập các giá trị có cùng kiểu, nhưng nó được thiết kế để lưu trữ dãy số không biết trước số lượng phần tử hoặc các phần tử thường xuyên thay đổi dựa trên các con trỏ trỏ tới các phần tử trong danh sách. Nhờ thế, khi xóa một phần tử trong danh sách liên kết, nếu ta biết trước con trỏ trỏ vào phần tử đó, thì độ phức tạp của thao tác xóa chỉ là O(1)O(1). Ngoài ra, các thao tác chèn phần tử vào đầu/cuối danh sách liên kết cũng có độ phức tạp chỉ là O(1)O(1).

Có ba kiểu danh sách liên kết: Danh sách liên kết đơn, Danh sách liên kết đôiDanh sách liên kết vòng.

Trước khi tìm hiểu về danh sách liên kết, các bạn cần nắm vững kiến thức về con trỏ, bởi vì đây là một cấu trúc dữ liệu hoàn toàn sử dụng con trỏ để cài đặt.

II. Danh sách liên kết đơn

1. Định nghĩa

Danh sách liên kết đơn là một tập hợp các nodes được phân bố ngẫu nhiên trong bộ nhớ, và sắp xếp theo cách sao cho mỗi node chứa một giá trị (data) và một ***con trỏ (next)***. Con trỏ sẽ trỏ đến địa chỉ của phần tử kế tiếp trong danh sách, hoặc trỏ đến địa chỉ NULL nếu như đó là phần tử cuối cùng của danh sách.

Bởi vì mỗi node đều lưu con trỏ tới phần tử tiếp theo trong danh sách, nên chúng ta chỉ cần lưu trữ node đầu tiên là head (cũng là một con trỏ). Nhờ vào node này chúng ta có thể đi tới lần lượt tất cả các node tiếp theo trong danh sách.

Hình ảnh dưới đây mô phỏng một danh sách liên kết đơn gồm 33 phần tử:

2. Các thao tác của Danh sách liên kết đơn

Trong phần cài đặt, tôi sẽ minh họa các thao tác trên danh sách liên kết với kiểu dữ liệu của từng phần tử là int cho đơn giản. Các bạn có thể thay thế kiểu dữ liệu của các node trong danh sách theo ý của mình tùy vào tình huống.

2.1. Khai báo

Trước hết, ta khai báo một cấu trúc cho một node trong danh sách liên kết:

struct Node
{
    int value;
    struct Node* next;
    
    Node()
    {
        value = 0;
        next = NULL;
    }
}

Mỗi node sẽ có trường value\text{value} lưu giá trị và trường next\text{next} là một con trỏ kiểu Node trỏ đến một node tiếp theo trong danh sách liên kết.

Danh sách liên kết đặc biệt ở chỗ, ta không cần phải tạo ra một danh sách thực sự như mảng hay vector, mà chỉ cần lưu trữ phần tử đầu tiên của danh sách thôi. Node head\text{head} sẽ là phần tử đầu tiên đó.

2.2. Tạo mới một node

Sử dụng một hàm để tạo ra một node mới lưu trữ giá trị value\text{value}. Mỗi khi một node được tạo ra, ta sẽ cấp phát bộ nhớ động cho nó rồi cho con trỏ next\text{next} của nó mặc định trỏ tới NULL. Ta sẽ viết hàm này thành một hàm thành viên của cấu trúc NodeNode:

struct Node
{
    int value;
    struct Node* next;

    Node()
    {
        value = 0;
        next = NULL;
    }

    void create_node(int _value)
    {
        value = _value;
        next = NULL;
    }
};

2.3. Thêm node vào danh sách liên kết

Thêm node vào đầu danh sách liên kết

Để thêm một node vào đầu danh sách, ta cần phải cập nhật lại giá trị head\text{head} của danh sách đó. Với một giá trị value\text{value} mới, để thêm nó vào đầu danh sách ta làm như sau:

  • Tạo node mới new_node\text{new\_node}data=value\text{data} = \text{value}.
  • Nếu như head\text{head} đang trỏ tới NULL - nghĩa là danh sách đang rỗng, thì ta đặt luôn node mới là head\text{head}. Ngược lại ta phải thay thế head\text{head} cũ thành node mới, thao tác hai bước:
    • Cho next\text{next} của new_node\text{new\_node} trỏ tới head\text{head} ban đầu.
    • Đặt head=new_node\text{head} = \text{new\_node}.
  • Trả về giá trị head\text{head} mới cho danh sách liên kết.
Node* add_to_front(int value, Node* head)
{
    Node* new_node = create_node(value);
	
    if (head == NULL)
        head = new_node;
    else 
    {
        new_node -> next = head;
        head = new_node;
    }
	
    return head;
}

Thao tác này có độ phức tạp là O(1)O(1).

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

Chúng ta sẽ cần node đầu tiên head\text{head} và giá trị value\text{value} cần thêm. Khi đó, làm các thao tác sau:

  • Tạo node mới new_node\text{new\_node} với data=value\text{data} = \text{value}.
  • Nếu head=\text{head} = NULL nghĩa là danh sách liên kết đang rỗng, ta đặt luôn head=new_node\text{head} = \text{new\_node}.
  • Ngược lại, ta duyệt liên tục từ head\text{head} tới node cuối cùng của danh sách (node có next=\text{next} = NULL) và đặt next\text{next} của node đó trỏ vào new_node\text{new\_node}.
  • Cuối cùng trả về giá trị head\text{head} mới của danh sách liên kết.
Node* add_to_last(int value, Node* head)
{
    // Node mới cần thêm vào.
    Node* new_node = create_node(value);
	
    // Danh sách rỗng thì gán luôn head bằng node mới.
    if (head == NULL)
        head = new_node;
    else
    {
        // Ngược lại, tạo một node p để duyệt tới phần tử cuối của danh sách.
        Node* p = head;
        while (p -> next != NULL)
            p = p -> next;
			
        // Cho next của phần tử cuối trỏ tới node mới.
        p -> next = new_node;
    }
	
    return head;
}

Độ phức tạp của thao tác này là O(n)O(n).

Thêm một node vào giữa danh sách liên kết

Thao tác này sẽ phức tạp hơn một chút. Giả sử cần thêm một giá trị mới vào vị trí xx trên danh sách, ta cần làm như sau:

  • Duyệt từ đầu danh sách tới node đang nằm ở vị trí x1x - 1 của danh sách. Giả sử đó là node QQ và coi như vị trí của các node trên danh sách sẽ bắt đầu từ 00.
  • Cho trường next\text{next} của node mới trỏ tới node mà QQ đang trỏ tới.
  • Cho trường next\text{next} của node QQ trỏ tới node mới.

Các bạn chỉ cần lưu ý trường hợp nếu như x=0x = 0 hoặc danh sách liên kết đang rỗng thì coi như đó chính là thao tác thêm một node vào đầu danh sách. Còn nếu như duyệt hết danh sách mà không thể tìm ra node Q,Q, thì thao tác chèn đó là một thao tác không hợp lệ, hoặc bạn có thể mặc định chèn vào cuối danh sách.

Hình ảnh dưới đây minh họa cho việc chèn một node vào vị trí thứ 22 trong danh sách liên kết:

Node* add_to_position(Node* head, int value, int x)
{
    // Danh sách đang rỗng hoặc x = 0 thì coi như là chèn vào đầu danh sách.
    if (x == 0 || head == NULL) // Hoặc x == 1 tùy vào cách đánh số trên danh sách.
        head = add_to_front(value, head);
    else
    {
        Node* p = head;
        int k = 0; 
        while (p != NULL && k + 1 != x)
        {
            p = p -> next;
            ++k;
        }
		
        // Không tìm được node ở vị trí x - 1.
        if (k + 1 != x)
        {
            // Thông báo vị trí không hợp lệ
            cout << "Invalid position\n";
            // Hoặc có thể coi như chèn vào cuối danh sách.
            // head = add_to_last(value, head);
        }
        // Chèn node mới vào vị trí x.
        else
        {
            Node* new_node = create_node(value);
            new_node -> next = p -> next;
            p -> next = new_node;
        }
    }
	
    return head;
}

Độ phức tạp của thao tác này là O(n)O(n).

2.4. Xóa node khỏi danh sách liên kết

Xóa vị trí đầu

Rất đơn giản, khi xóa vị trí đầu nghĩa là ta thay đổi phần tử head\text{head} thành phần tử nó đang trỏ đến. Nghĩa là gán head=headnext\text{head} = \text{head} \to \text{next}.

Sau đó trả về giá trị mới của head\text{head}. Lưu ý trường hợp danh sách rỗng thì không có gì để xóa cả.

Node* del_front(Node* head)
{
    if (head == NULL)
        cout << "The linked-list is empty!\n";
	
    return (head = head -> next);
}

Thao tác này có độ phức tạp O(1)O(1).

Xóa vị trí cuối

Đồng nghĩa với việc giảm kích thước của danh sách liên kết đi 11 đơn vị. Ta sẽ tìm phần tử áp chót của danh sách liên kết, sau đó cho phần tử đó trỏ tới NULL. Còn nếu như danh sách đang rỗng hoặc chỉ có 11 phần tử thì ta coi như đó là đang xóa phần tử đầu tiên.

Sau đó ta trả về giá trị mới của head\text{head}.

Node* del_last(Node* head)
{
    if (head == NULL || head -> next == NULL)
        return del_front(head);

    Node* p = head;
    while (p -> next -> next != NULL)
        p = p -> next;
	
    p -> next = NULL;
	
    return head;
}

Thao tác này có độ phức tạp O(n)O(n).

Xóa node ở vị trí bất kì

Thao tác này cũng khá giống với thao tác xóa node ở vị trí cuối. Nó đơn giản là ta bỏ qua phần tử ở vị trí đó bằng cách cho next\text{next} của phần tử trước nó trỏ tới phần tử sau nó.

Tuy nhiên, cần lưu ý trường hợp vị trí cần xóa không tồn tại trong danh sách, đó là khi duyệt hết danh sách mà vẫn chưa tới được phần tử ở trước phần tử cần xóa.

Hình ảnh dưới đây minh họa thao tác xóa một phần tử trong danh sách liên kết (phần tử tmp\text{tmp}):

Node* del_at_position(Node* head, int x)
{
    if (x == 0 || head == NULL || head -> next == NULL) // Hoặc x == 1 tùy vào cách đánh số trên danh sách.
        return del_front(head);

    Node* p = head;
    int k = 0;
    while (p -> next -> next != NULL && k != x - 1)
    {
        p = p -> next;
        ++k;
    }

    // Đã duyệt tới phần tử áp chót mà vẫn chưa tới được phần tử liền trước
    // vị trí cần xóa, thì kết luận không tồn tại vị trí cần xóa.
    if (k != x - 1)
        cout << "The position is invalid\n";
    // Đặt p trỏ tới phần tử liền sau phần tử cần xóa.
    else 
        p -> next = p -> next -> next;
	
    return head;
}

Thao tác này có độ phức tạp O(n)O(n). Tuy nhiên, nếu ta biết trước con trỏ trỏ tới phần tử cần xóa thì độ phức tạp sẽ chỉ còn là O(1)O(1).

2.5. Lấy giá trị ở vị trí bất kì

Để lấy giá trị ở vị trí xx bất kì trên danh sách liên kết, không có cách nào khác ngoài việc duyệt từ đầu danh sách cho tới khi tìm được phần tử ở vị trí xx. Các thao tác tìm kiếm trên danh sách cũng hoàn toàn tương tự. Có thể thấy, việc tìm kiếm và truy xuất giá trị không phải là một ưu thế của danh sách liên kết.

Dưới đây là code lấy giá trị ở vị trí xx bất kì trên danh sách liên kết. Đối với thao tác tìm kiếm một phần tử value\text{value} trên danh sách, các bạn cũng làm hoàn toàn tương tự. Ngoài ra, các bạn có thể viết thêm đoạn code kiểm tra vị trí cần truy xuất có hợp lệ hay không.

Node* value_at_index(int x)
{
    int k = 0; // Hoặc int k = 1 tùy vào cách đánh số trên danh sách.
    Node* p = head;
    while (p -> next != NULL && k != x)
    {
        p = p -> next;
        ++k;
    }
	
    return p -> data;
}

Thao tác này có độ phức tạp O(n)O(n).

2.6. Một số thao tác bổ trợ khác

Duyệt danh sách liên kết

Để duyệt và in ra danh sách liên kết, các bạn chỉ cần liên tục gán head=headnext\text{head} = \text{head} \to \text{next} là có thể làm được. Thao tác này có độ phức tạp O(n)O(n).

void print_list(Node* head)
{
    for (Node* p = head; p != NULL; p = p -> next)
        cout << p -> data << ' ';
}

Đếm số phần tử của danh sách liên kết

Cũng giống như duyệt qua danh sách liên kết, nhưng các bạn dùng thêm một biến để đếm số phần tử trong quá trình duyệt.

int get_size(Node* head)
{
    int _size = 0;
    for (Node* p = head; p != NULL; p = p -> next)
        ++_size;
	
    return _size;
}

Nhập danh sách liên kết

Muốn nhập danh sách liên kết, ta chỉ cần nhập từng giá trị và thêm nó vào làm node cuối cùng trong danh sách liên kết. Thao tác này có độ phức tạp O(n)O(n) với nn là số phần tử nhập vào.

Node* input_linked_list()
{
    int n;
    cin >> n;
	
    Node* head = NULL;
    for (int i = 0; i < n; ++i)
    {
        int value;
        cin >> value;
		
        head = add_to_last(value);
    }
	
    return head;
}

Ngoài ra, tất cả các thao tác trên có thể được chỉnh sửa một chút để thu được danh sách liên kết đôidanh sách liên kết vòng. Các bạn chỉ cần hiểu đơn giản như sau:

  • Danh sách liên kết đôi là danh sách mà mỗi node sẽ có thêm một con trỏ prev\text{prev} để trỏ vào phần tử liền trước nó.
  • Danh sách liên kết vòng là danh sách có thêm một liên kết nữa giữa phần tử đầu tiên và phần tử cuối cùng của danh sách để tạo thành vòng tròn.

3. Cài đặt đầy đủ

Do Danh sách liên kết là một cấu trúc dữ liệu cung cấp khá nhiều thao tác đi kèm, nên để thuận tiện khi cài đặt, toàn bộ các thao tác cũng như các trường dữ liệu của nó sẽ được gói gọn trong một struct. Như vậy, các hàm tác động tới con trỏ headhead sẽ có chút thay đổi ở kiểu hàm, các bạn quan sát chương trình mẫu để hiểu rõ hơn.

Dưới đây là chương trình minh họa cài đặt Danh sách liên kết đơn lưu số nguyên:

// Struct thể hiện một node trên danh sách liên kết.
struct Node
{
    int value;
    struct Node* next;

    Node()
    {
        this -> value = 0;
        this -> next = NULL;
    }

    void create_node(int _value)
    {
        value = _value;
        next = NULL;
    }
};

// Struct thể hiện 1 danh sách liên kết, với head là node đại diện.
struct LinkedList
{
    Node* head = new Node();

    LinkedList()
    {
        head = NULL;
    }

    void add_to_front(int value)
    {
        Node* new_node = new Node();
        new_node -> create_node(value);

        if (head == NULL)
            head = new_node;
        else
        {
            new_node -> next = head;
            head = new_node;
        }
    }

    void add_to_last(int value)
    {
        Node* new_node = new Node();
        new_node -> create_node(value);

        // Danh sách rỗng thì gán luôn head bằng node mới.
        if (head == NULL)
            head = new_node;
        else
        {
            // Ngược lại, tạo một node p để duyệt tới phần tử cuối của danh sách.
            Node* p = new Node();
            p = head;
            while (p -> next != NULL)
                p = p -> next;

            // Cho next của phần tử cuối trỏ tới node mới.
            p -> next = new_node;
        }
    }

    void add_to_position(int value, int x)
    {
        // Danh sách đang rỗng hoặc x = 0 thì coi như là chèn vào đầu danh sách.
        if (x == 0 || head == NULL) // Hoặc x == 1 tùy vào cách đánh số trên danh sách.
        {
            add_to_front(value);
            return;
        }
        
        Node* p = new Node();
        p = head;
        int k = 0;
        while (p != NULL && k + 1 != x)
        {
            p = p -> next;
            ++k;
        }

        // Không tìm được node ở vị trí x - 1.
        if (k + 1 != x)
        {
            // Thông báo vị trí không hợp lệ
            cout << "Invalid position\n";
            // Hoặc có thể coi như chèn vào cuối danh sách.
            // add_to_last(value);
        }
        // Chèn node mới vào vị trí x.
        else
        {
            Node* new_node = new Node();
            new_node -> create_node(value);
            new_node -> next = p -> next;
            p -> next = new_node;
        }
    }

    void del_front()
    {
        if (head == NULL)
            cout << "The linked-list is empty!\n";

        head = head -> next;
    }

    void del_last()
    {
        if (head == NULL || head -> next == NULL)
        {
            del_front();
            return;
        }

        Node* p = head;
        while (p -> next -> next != NULL)
            p = p -> next;

        p -> next = NULL;
    }

    void del_at_position(int x)
    {
        if (x == 0 || head == NULL || head -> next == NULL) // Hoặc x == 1 tùy vào cách đánh số trên danh sách.
        {
            del_front();
            return;
        }

        Node* p = head;
        int k = 0;
        while (p -> next -> next != NULL && k != x - 1)
        {
            p = p -> next;
            ++k;
        }

        // Đã duyệt tới phần tử áp chót mà vẫn chưa tới được phần tử liền trước
        // vị trí cần xóa, thì kết luận không tồn tại vị trí cần xóa.
        if (k != x - 1)
            cout << "The position is invalid\n";
        // Đặt p trỏ tới phần tử liền sau phần tử cần xóa.
        else
            p -> next = p -> next -> next;
    }

    void print_list()
    {
        for (Node* p = head; p != NULL; p = p -> next)
            cout << p -> value << ' ';
    }

    int value_at_index(int x)
    {
        int k = 0; // Hoặc k = 1 tùy vào cách đánh số trên danh sách.
        Node* p = head;
        while (p -> next != NULL && k != x)
        {
            p = p -> next;
            ++k;
        }

        return p -> value;
    }

    int get_size()
    {
        int _size = 0;
        for (Node* p = head; p != NULL; p = p -> next)
            ++_size;

        return _size;
    }

    void input_linked_list(int n)
    {
        for (int i = 0; i < n; ++i)
        {
            int value;
            cin >> value;

            add_to_last(value);
        }
    }
};

Các bạn có thể xem thêm cài đặt đầy đủ của Danh sách liên kết đôi tại đây.

III. So sánh giữa mảng và danh sách liên kết

Tổng kết lại, ta có bảng so sánh giữa danh sách liên kết và mảng dưới đây:

Đồng thời độ phức tạp của từng thao tác tôi cũng đã đề cập kĩ ở cài đặt. Tùy vào tình huống mà các bạn có thể lựa chọn sử dụng cấu trúc dữ liệu mảng hay danh sách liên kết cho phù hợp.

IV. Bài tập áp dụng

1. DAQuery

Đề bài

Cho một danh sách liên kết SS ban đầu rỗng, các phần tử trong danh sách sẽ được đánh số từ vị trí 11. Bạn cần thực hiện qq truy vấn có dạng như sau:

  • 1 x1 \ x: Thêm giá trị xx vào đầu SS.
  • 2 x2 \ x: Thêm giá trị xx vào cuối SS.
  • 33: Xóa giá trị đầu tiên của SS. Đảm bảo lúc này dãy SS khác rỗng.
  • 44: Xóa giá trị cuối cùng của SS. Đảm bảo lúc này dãy SS khác rỗng.
  • 5 k5 \ k: In ra giá trị thứ kk của SS. Đảm bảo kSk \le |S|.

Yêu cầu: Hãy thực hiện tất cả các truy vấn cho trước?

Input:

  • Dòng đầu tiên chứa một số nguyên dương qq miêu tả số truy vấn.
  • Trên qq dòng tiếp theo, mỗi dòng biểu diễn một truy vấn.

Ràng buộc:

  • Các số trong Input đều là số nguyên.
  • 1x,q10001 \le x,q \le 1000.

Output:

  • In ra kết quả theo thứ tự xuất hiện của các truy vấn loại 55. Nếu như truy vấn loại 55 nào không tồn tại đáp án thì đưa ra Can't find the kth element.

Sample Input:

8
1 2
2 3
5 1
3
4
1 2
1 3
5 1

Sample Output:

2
3

Ý tưởng

Ta sử dụng các thao tác cơ bản của danh sách liên kết là Thêm, xóa ở đầu - cuối; Đưa ra giá trị ở vị trí cho trước; Đưa ra kích thước danh sách. Tuy nhiên, trong bài toán này các phần tử của danh sách được đánh số từ vị trí 1,1, nên các bạn phải sửa lại hàm get_value_at_index().

Code mẫu

#include <bits/stdc++.h>

using namespace std;

// Struct thể hiện một node trên danh sách liên kết.
struct Node
{
    int value;
    struct Node *next;

    Node()
    {
        this -> value = 0;
        this -> next = NULL;
    }

    void create_node(int _value)
    {
        value = _value;
        next = NULL;
    }
};

// Struct thể hiện 1 danh sách liên kết, với head là node đại diện.
struct LinkedList
{
    Node* head = new Node();

    LinkedList()
    {
        head = NULL;
    }

    void add_to_front(int value)
    {
        Node* new_node = new Node();
        new_node -> create_node(value);

        if (head == NULL)
            head = new_node;
        else
        {
            new_node -> next = head;
            head = new_node;
        }
    }

    void add_to_last(int value)
    {
        Node* new_node = new Node();
        new_node -> create_node(value);

        // Danh sách rỗng thì gán luôn head bằng node mới.
        if (head == NULL)
            head = new_node;
        else
        {
            // Ngược lại, tạo một node p để duyệt tới phần tử cuối của danh sách.
            Node* p = new Node();
            p = head;
            while (p -> next != NULL)
                p = p -> next;

            // Cho next của phần tử cuối trỏ tới node mới.
            p -> next = new_node;
        }
    }

    void del_front()
    {
        if (head == NULL)
            cout << "The linked-list is empty!";

        head = head -> next;
    }

    void del_last()
    {
        // Nếu danh sách chỉ có 1 node thì xóa chính node đó.
        if (head == NULL || head -> next == NULL)
        {
            del_front();
            return;
        }

        Node* p = head;
        while (p -> next -> next != NULL)
            p = p -> next;

        p -> next = NULL;
    }

    int value_at_index(int x)
    {
        int k = 1;
        Node* p = head;
        while (p -> next != NULL && k != x)
        {
            p = p -> next;
            ++k;
        }

        return p -> value;
    }

    int get_size()
    {
        int _size = 0;
        for (Node* p = head; p != NULL; p = p -> next)
            ++_size;

        return _size;
    }
};

int main()
{
    // Tạo một con trỏ đại diện cho Danh sách liên kết.
    LinkedList* ptr_list1 = new LinkedList();

    int q;
    cin >> q;

    while (q--)
    {
        int type, x;
        cin >> type;

        switch (type)
        {
            case 1:
                cin >> x;

                ptr_list1 -> add_to_front(x);
                break;

            case 2:
                cin >> x;

                ptr_list1 -> add_to_last(x);
                break;

            case 3:
                ptr_list1 -> del_front();
                break;

            case 4:
                ptr_list1 -> del_last();
                break;

            case 5:
                cin >> x;

                if (ptr_list1 -> get_size() < x)
                    cout << "Can't find the kth element\n";
                else
                    cout << ptr_list1 -> value_at_index(x) << '\n';
                break;
        }
    }

    return 0;
}

2. Super list

Đề bài

Cho nn danh sách liên kết, danh sách thứ ii được gọi là SiS_i và có độ dài aia_i. Bạn có một danh sách TT ban đầu rỗng và cần làm nn thao tác sau: Thao tác thứ ii được gán bằng ci;c_i; nếu ci=0c_i = 0 bạn cần chèn SiS_i vào đầu của T,T, ngược lại nếu ci=1c_i = 1 bạn cần chèn SiS_i vào cuối của TT.

Yêu cầu: Hãy in ra TT sau nn thao tác trên?

Input:

  • Dòng đầu tiên chứa một số nguyên dương nn miêu tả số danh sách liên kết.
  • Từ dòng thứ hai tới dòng thứ 2n+12n+1 có dạng:
    • Dòng thứ 2i2i miêu tả aia_i.
    • Dòng thứ 2i+12i+1 gồm aia_i số nguyên dương miêu tả SiS_i.
  • Dòng tiếp theo gồm nn số cic_i miêu tả thao tác.

Ràng buộc:

  • Các số trong SiS_i đều là số nguyên trong khoảng [0,109][0,10^9].
  • 1n1001 \le n \le 100.
  • 1ai200;i:1in1 \le a_i \le 200; \forall i: 1 \le i \le n.

Output:

  • Dòng đầu tiên in ra số lượng phần tử của TT.
  • Dòng thứ hai in ra các phần tử của TT.

Sample Input:

4
3
1 4 2
2
1 5
3 
5 2 1
2
2 6
1 0 0 1

Sample Output:

10
5 2 1 1 5 1 4 2 2 6

Ý tưởng

Ta có thể chèn SiS_i vào TT rất nhanh chỉ bằng vài thao tác. Tuy nhiên, để thuận tiện hơn thì ta sẽ biến đổi danh sách liên kết, lưu thêm một con trỏ lastlast để trỏ vào phần tử cuối cùng của danh sách. Như vậy, ta sẽ biến đổi thao tác add_to_last() đi một chút (do bài này chỉ cần sử dụng thao tác này trong việc thêm phần tử vào danh sách):

void add_to_last(int value)
{
    Node* new_node = new Node();
    new_node -> create_node(value);

    // Danh sách rỗng thì gán luôn head và last bằng node mới.
    if (head == NULL)
        head = new_node, last = new_node;
    else
    {
        // Ngược lại, tạo một node p để duyệt tới phần tử cuối của danh sách.
        Node* p = new Node();
        p = head;
        while (p -> next != NULL)
            p = p -> next;

        // Cho next của phần tử cuối trỏ tới node mới.
        // Node cuối cùng của danh sách sẽ là node mới.
        p -> next = new_node;
        last = new_node;
    }
}

Để thuận tiện trong việc quản lý các danh sách Si,S_i, ta dùng một mảng các con trỏptr_s\text{ptr\_s} - với ptr_s[i]\text{ptr\_s}[i] là con trỏ kiểm soát danh sách liên kết S[i]S[i]. Ngoài ra, ta sử dụng con trỏ ptr_t\text{ptr\_t} để kiểm soát danh sách TT.

Nếu cần chèn SiS_i vào đầu T,T, ta sẽ nối phần tử cuối cùng của SiS_i với phần tử đầu tiên của TT. Tức là ta sẽ cho node lastlast của danh sách SiS_i trỏ tới node headhead của danh sách TT (nhưng nếu TT đang rỗng thì gán trực tiếp T=SiT = S_i), sau đó cập nhật lại node headhead của TT thành node lastlast của SiS_i.

Ngược lại nếu cần chèn SiS_i vào cuối T,T, ta nối phần tử cuối cùng của TT với phần tử đầu tiên của SiS_i. Tức là ta sẽ cho node lastlast của TT trỏ tới node headhead của SiS_i (nhưng nếu TT đang rỗng thì gán trực tiếp T=SiT = S_i), sau đó cập nhật lại node lastlast của TT thành node lastlast của SiS_i.

Phép nối được thực hiện thông qua các con trỏ kiểm soát các SiS_i và danh sách TT.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

// Struct thể hiện một node trên danh sách liên kết.
struct Node
{
    int value;
    struct Node* next;

    Node()
    {
        value = 0;
        next = NULL;
    }

    void create_node(int _value)
    {
        value = _value;
        next = NULL;
    }
};

// Struct thể hiện 1 danh sách liên kết, với head là node đầu tiên và last là node cuối cùng.
struct LinkedList
{
    Node* head = new Node();
    Node* last = new Node();

    LinkedList()
    {
        head = NULL;
        last = NULL;
    }

    void add_to_last(int value)
    {
        Node* new_node = new Node();
        new_node -> create_node(value);

        // Danh sách rỗng thì gán luôn head bằng node mới.
        if (head == NULL)
            head = new_node, last = new_node;
        else
        {
            // Ngược lại, tạo một node p để duyệt tới phần tử cuối của danh sách.
            Node* p = new Node();
            p = head;
            while (p -> next != NULL)
                p = p -> next;

            // Cho next của phần tử cuối trỏ tới node mới.
            // Node cuối cùng của danh sách sẽ là node mới.
            p -> next = new_node;
            last = new_node;
        }
    }

    void print_list()
    {
        for (Node* p = head; p != NULL; p = p -> next)
            cout << p -> value << ' ';
    }

    int get_size()
    {
        int _size = 0;
        for (Node* p = head; p != NULL; p = p -> next)
            ++_size;

        return _size;
    }

    void input_linked_list(int n)
    {
        for (int i = 0; i < n; ++i)
        {
            int value;
            cin >> value;

            add_to_last(value);
        }
    }
};

// Tạo một mảng con trỏ đại diện cho các danh sách S.
LinkedList* ptr_s[101];

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        int a;
        cin >> a;

        ptr_s[i] = new LinkedList(); // Cấp phát bộ nhớ cho danh sách S[i].
        ptr_s[i] -> input_linked_list(a);
    }

    LinkedList* ptr_t = new LinkedList();
    for (int i = 1; i <= n; ++i)
    {
        int c;
        cin >> c;

        if (c == 0)
        {
            if (ptr_t -> head == NULL)
                ptr_t = ptr_s[i];
            else
            {
                ptr_s[i] -> last -> next = ptr_t -> head;
                ptr_t -> head = ptr_s[i] -> head;
            }
        }
        else
        {
            if (ptr_t -> head == NULL)
                ptr_t = ptr_s[i];
            else
            {
                ptr_t -> last -> next = ptr_s[i] -> head;
                ptr_t -> last = ptr_s[i] -> last;
            }
        }
    }

    cout << ptr_t -> get_size() << endl;
    ptr_t -> print_list();

    return 0;
}

V. Tài liệu tham khảo


©️ Tác giả: Vũ Quế Lâm từ Viblo


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.