Menu
CoddyTech

Luyện tập #4

Bài học 13 trên 14 trong khóa học Danh sách liên kết, loạt bài về cấu trúc dữ liệu #5 của Coddy.

challenge icon

Thử thách

Dễ

Cho hai mảng số nguyên đã sắp xếp a và b (các giá trị của hai danh sách liên kết đã sắp xếp), hãy viết hàm mergeSorted trả về một mảng đã sắp xếp duy nhất chứa tất cả giá trị từ cả hai đầu vào.

Hãy dùng danh sách liên kết để giải bài toán này! Duyệt song song cả hai danh sách, liên tục lấy phần tử đầu nhỏ hơn đưa vào kết quả.

Bạn phải dùng lớp LinkedList (được cung cấp trong linkedlist.<ext> cùng với node.<ext>) — không dùng các chức năng có sẵn của ngôn ngữ như đảo ngược mảng, cắt lát hoặc các thao tác danh sách trong thư viện chuẩn để tính kết quả.

Tự làm thử

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"

int main() {
    char line1[8192];
    char line2[8192];
    if (!fgets(line1, sizeof(line1), stdin)) line1[0] = '\0';
    if (!fgets(line2, sizeof(line2), stdin)) line2[0] = '\0';
    int a[4096];
    int alen = 0;
    char* tok = strtok(line1, " \t\r\n");
    while (tok) { a[alen++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
    int b[4096];
    int blen = 0;
    tok = strtok(line2, " \t\r\n");
    while (tok) { b[blen++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
    int rs = 0;
    int* r = mergeSorted(a, alen, b, blen, &rs);
    for (int idx = 0; idx < rs; idx++) {
        if (idx > 0) printf(" ");
        printf("%d", r[idx]);
    }
    printf("\n");
    return 0;
}

Tất cả bài học trong Danh sách liên kết, loạt bài về cấu trúc dữ liệu #5

Tự luyện tập: Trình biên dịch C online