Giả sử chúng ta chịu trách nhiệm xây dựng một hệ thống thư viện giám sát và truy vấn các hoạt động tại thư viện. Chúng ta hiện được yêu cầu triển khai ba lệnh khác nhau thực hiện như sau:
Dùng lệnh 1, ghi nhận việc thêm sách có y trang tại kệ x.
Dùng lệnh 2, in số trang của quyển sách thứ y tại kệ x.
Dùng lệnh 3, in số lượng sách trên kệ x.
Các lệnh được cho dưới dạng mảng 2D theo định dạng {loại lệnh, x, y}. Nếu không có giá trị y, giá trị sẽ mặc định là 0. Chúng ta in kết quả của các lệnh cho trước.
Ví dụ, nếu đầu vào là số kệ = 4, truy vấn = 4, input_arr = {{1, 3, 23}, {1, 4, 128}, {2, 3, 0}, {3, 4, 0}}; thì đầu ra sẽ là:
23 1
Lệnh 1 chèn sách 23 trang lên kệ 3. Lệnh 2 chèn sách 128 trang lên kệ 4. Lệnh 3 in số trang sách 0 trên kệ 3. Lệnh 4 in số sách trên kệ 3.
Để giải quyết bài toán, ta làm theo các bước sau:
- b := mảng mới kích thước s
- p := mảng mới kích thước s
- khởi tạo i := 0, khi i < s, tăng i lên 1, làm:
- b[i] := 0
- p[i] := mảng mới
- khởi tạo loopCount := 0, khi loopCount < q, tăng loopCount lên 1, làm:
- qtype := q_array[loopCount, 0]
- nếu qtype == 1:
- x := q_array[loopCount, 1]
- y := q_array[loopCount, 2]
- b[x] := b[x] + 1
- p[x] := giải phóng đối tượng p[x] trỏ tới và trả về con trỏ kích thước b[x]
- p[x, b[x] - 1] = y
- ngược lại nếu qtype == 2:
- x := q_array[loopCount, 1]
- y := q_array[loopCount, 2]
- in(p[x, y])
- ngược lại:
- x := q_array[loopCount, 1]
- in(b[x])
- nếu b không null:
- giải phóng bộ nhớ b
- với i từ 0 đến s-1:
- nếu p[i] không null: giải phóng p[i]
- nếu p không null: giải phóng p
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <stdio.h>
#include <stdlib.h>
void solve(int s, int q, int q_array[][3]) {
int* b;
int** p;
b = (int*)malloc(sizeof(int)*s);
p = (int**)malloc(sizeof(int*)*s);
for(int i = 0; i < s; i++) {
b[i] = 0;
p[i] = (int*)malloc(sizeof(int));
}
int loopCount;
for(loopCount = 0; loopCount < q; loopCount++) {
int qtype;
qtype = q_array[loopCount][0];
if (qtype == 1) {
int x, y;
x = q_array[loopCount][1];
y = q_array[loopCount][2];
b[x] += 1;
p[x] = realloc(p[x], b[x]*sizeof(int));
p[x][b[x] - 1] = y;
}
else if (qtype == 2) {
int x, y;
x = q_array[loopCount][1];
y = q_array[loopCount][2];
printf("%d\n", p[x][y]);
}
else {
int x;
x = q_array[loopCount][1];
printf("%d\n", b[x]);
}
}
if (b) free(b);
for (int i = 0; i < s; i++)
if (p[i]) free(p[i]);
if (p) free(p);
}
int main() {
int input_arr[][3] = {{1, 3, 23}, {1, 4, 128}, {2, 3, 0}, {3, 4, 0}};
solve(4, 4, input_arr);
}
Đầu vào
int input_arr[][3] = {{1, 3, 23}, {1, 4, 128}, {2, 3, 0}, {3, 4, 0}}; solve(4, 4, input_arr);
Đầu ra
23 1