Xóa 1 dòng trong mảng 2 chiều cấp phát động
Đề bài
Cho mảng 2 chiều các số nguyên được cấp phát động gồm dong dòng, cot cột. Hãy viết hàm xóa 1 dòng có chỉ số viTriXoa ra khỏi mảng (các dòng phía sau dồn lên), rồi in ra mảng sau khi xóa.
Dữ liệu vào và kết quả (mình bổ sung để các bạn chạy thử): đề gốc chỉ là một bài tập về con trỏ nên không có định dạng nhập/xuất. Để tiện kiểm tra, trong bài này mình quy ước như sau:
- Dòng đầu gồm 2 số nguyên
dong,cot$(2 \le dong \le 1000,\ 1 \le cot \le 1000)$. dongdòng tiếp theo, mỗi dòng gồmcotsố nguyên (giá trị tuyệt đối không quá $10^9$) là các phần tử của mảng.- Dòng cuối là số nguyên
viTriXoa$(0 \le viTriXoa \lt dong)$: chỉ số dòng cần xóa (đánh số từ 0). - Kết quả: in ra mảng sau khi xóa gồm
dong − 1dòng, mỗi dòng là các phần tử cách nhau một khoảng trắng.
3 3
1 2 3
4 5 6
7 8 9
04 5 6
7 8 95 3
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
11 1 1
3 3 3
4 4 4
5 5 5Lời mở đầu
Bài này là một đoạn hỏi đáp giữa mình với một em học viên đang học tới phần con trỏ. Em ấy viết hàm xóa dòng thì "lúc chạy kết quả ra đúng, nhưng khi tắt chương trình đi thì lại hiện lỗi" 😥. Mình thấy đây là ví dụ cực kỳ hay để thấy được sức mạnh của con trỏ 💪, đồng thời cũng là cái bẫy mà rất nhiều bạn mới học con trỏ hay dính, nên viết lại thành bài để nhiều bạn cùng tham khảo. Hy vọng giúp ích được cho các bạn 😇.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJTrước hết, mảng 2 chiều động là gì? Bản chất mảng 2 chiều động chính là mảng 1 chiều mà mỗi phần tử trong mảng 1 chiều đó là 1 mảng 1 chiều. Ví dụ mảng 2 chiều a có 5 dòng, 10 cột:
- Đầu tiên là khai báo ra con trỏ cấp 2
a, sẽ new ra 5 (số dòng) con trỏ cấp 1:int **a = new int*[5]; - Sau đó với mỗi con trỏ cấp 1, sẽ đi new ra 10 (cột) ô nhớ:
for(int i = 0; i < 5; i++) a[i] = new int[10];
Bên C thì thay new bằng malloc như code trong bài này. Tức là mỗi a[i] là 1 con trỏ, đại diện cho cả 1 dòng.
Xóa 1 dòng thì làm sao? Nó cũng giống quy tắc xóa 1 phần tử trong mảng 1 chiều vậy đó: toàn bộ các ô nhớ từ sau vị trí cần xóa sẽ nhích lên phía trước hết, sau đó ta giải phóng phần dư ra ở cuối. Ví dụ mảng có 5 dòng, xóa dòng 1 nghĩa là dòng 2 sẽ phải nhích lên đứng ở dòng 1, dòng 3 nhích lên đứng ở dòng 2, dòng 4 nhích lên đứng ở dòng 3. Câu hỏi là: nhích bằng cách nào?
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Copy từng ô nhớ của dòng sau lên dòng trước – O(dong · cot)
Cách đầu tiên ai cũng nghĩ tới: đi copy từng ô nhớ của dòng 2 lên từng ô nhớ tương ứng của dòng 1, rồi dòng 3 lên dòng 2... Copy xong thì dòng cuối cùng thành dư, ta free nó đi và giảm dong xuống 1.
Với mảng 1 chiều cấp phát động thì đây là cách duy nhất: cái cần xóa là ô nhớ sau cùng thì phải dùng cơ chế realloc để nó giảm bớt ô nhớ, chứ không có chuyện delete a[n-1]; được, vì lúc này a[n-1] không phải là con trỏ mà delete được, a[n-1] chỉ đang là 1 ô nhớ thuộc dãy ô nhớ quản lý bởi duy nhất 1 con trỏ a.
#include <iostream>
#include <cstdlib>
using namespace std;
void xoaDong(int**& a, int& dong, int cot, int viTriXoa)
{
// dời từng ô của các dòng phía sau lên trên 1 dòng
for (int i = viTriXoa; i < dong - 1; i++)
for (int j = 0; j < cot; j++)
a[i][j] = a[i + 1][j];
free(a[dong - 1]); // dòng cuối giờ dư ra, giải phóng nó
dong--;
}
int main()
{
int dong, cot;
cin >> dong >> cot;
int** a = (int**)malloc(dong * sizeof(int*));
for (int i = 0; i < dong; i++)
{
a[i] = (int*)malloc(cot * sizeof(int));
for (int j = 0; j < cot; j++)
cin >> a[i][j];
}
int viTriXoa;
cin >> viTriXoa;
xoaDong(a, dong, cot, viTriXoa);
for (int i = 0; i < dong; i++)
{
for (int j = 0; j < cot; j++)
cout << a[i][j] << " ";
cout << "\n";
}
for (int i = 0; i < dong; i++)
free(a[i]);
free(a);
return 0;
}import sys
def xoa_dong(a, dong, cot, vi_tri_xoa):
# dời từng ô của các dòng phía sau lên trên 1 dòng
for i in range(vi_tri_xoa, dong - 1):
for j in range(cot):
a[i][j] = a[i + 1][j]
a.pop() # dòng cuối giờ dư ra, bỏ nó đi
return dong - 1
data = sys.stdin.buffer.read().split()
dong, cot = int(data[0]), int(data[1])
pos = 2
a = []
for i in range(dong):
a.append([int(x) for x in data[pos:pos + cot]])
pos += cot
vi_tri_xoa = int(data[pos])
dong = xoa_dong(a, dong, cot, vi_tri_xoa)
out = []
for i in range(dong):
out.append(' '.join(map(str, a[i])) + ' ')
sys.stdout.write('\n'.join(out) + '\n')Đánh giá độ phức tạp của cách làm này:
- Không gian: không dùng thêm bộ nhớ: $O(1)$.
- Thời gian: mỗi dòng phía sau phải copy đủ
cotô, tổng cộng $(dong - 1 - viTriXoa) \cdot cot$ phép gán, xấu nhất cỡ $O(dong \cdot cot)$. Ví dụ 1000 dòng, 1000 cột mà xóa dòng 0 thì phải gán gần $10^6$ lần.
Chạy thì đúng, nhưng như mình nói với em học viên: đừng làm thế 😄, làm thế là trình độ con trỏ chưa tốt. Bản chất từng dòng là 1 con trỏ, và con trỏ thì có thể trỏ đi được!
Cách 2Chỉ nhảy con trỏ a[i] = a[i + 1], có temp giữ nhà – O(dong)
Vì thế nên ta cho a[1] là con trỏ quản lý dòng 1, sẽ nhảy đến a[2] là con trỏ quản lý dòng 2. Như thế thì khi gọi duyệt a[1] là nó sẽ duyệt các ô nhớ thuộc dòng 2, nói cách khác cũng như việc toàn bộ dòng 2 copy lên dòng 1. Nhưng thay vì phải làm từng ô nhớ (giả sử có 1000 ô tức là có 1000 cột thì phải chạy vòng lặp làm 1000 lần) thì giờ chỉ làm 1 lần cho con trỏ a[1] = a[2]; thế là xong ^^. Đây là sức mạnh của con trỏ nhé 😃:
a[1] = a[2];
a[2] = a[3];
a[3] = a[4];Nhích xong rồi, nếu mình free(a[4]) (giải phóng "dòng cuối dư ra" như cách 1) thì lúc này đâu được! Vì lần cuối cùng: a[3] = a[4], tụi nó đang ở cùng địa chỉ của nhau. Nếu giải phóng con trỏ a[4] nghĩa là giải phóng vùng nhớ mà nó quản lý, thì hiện tại a[3] cũng đang ở đó mà 🙂. Thấy vấn đề không?
Chưa hết: dòng mình cần xóa là dòng index 1, và nó đang được quản lý bởi con trỏ a[1]. Nếu cho a[1] = a[2] tức là a[1] nhảy tới địa chỉ con trỏ a[2], thì như thế mình đã mất kết nối với địa chỉ a[1] ban đầu rồi. Nó có nhà của nó, mà giờ nó bỏ qua nhà khác, vậy nhà của nó bị vô chủ rồi ⇒ rò rỉ bộ nhớ.
Đây chính là lý do code của em học viên chạy ra kết quả đúng nhưng tắt chương trình thì lỗi: đến cuối chương trình, vòng lặp giải phóng bộ nhớ sẽ free lại vùng nhớ đã bị free trước đó (double free).
Vậy nên mình phải cho 1 con trỏ temp giữ nhà giùm nó: int *temp = a[viTriXoa]; là cho con trỏ temp quản lý địa chỉ của a[1] đó (đang muốn xóa dòng index 1). Rồi thì thằng a[1] mới trỏ tới a[2], a[2] trỏ a[3], a[3] trỏ a[4], rồi thì ta free(temp).
Tưởng tượng thế này đi hen. Giả sử mảng a có 5 dòng, địa chỉ lần lượt của con trỏ đầu mỗi dòng sẽ là 0x001, 0x002, 0x003, 0x004, 0x005 (chỗ này là mình tượng trưng địa chỉ cho dễ hình dung chứ thực tế các địa chỉ đầu mỗi dòng không có liền kề sát nhau như vậy đâu nha, đừng anh em nào bắt bẻ mình chỗ này nhé hihi ^_^).
- Giờ cần xóa dòng index 1: tức là địa chỉ
0x002, hiện tại nó đang được quản lý địa chỉ bởi con trỏa[1]. - Ta cho
temp = a[1], tức làtempsẽ quản lý địa chỉ0x002. - Sau đó
a[1]sẽ nhảy tớia[2]tức làa[1]sẽ là0x003;a[2]nhảy tớia[3]tức là0x004;a[3]nhảy tớia[4]tức là0x005. - Vậy giờ đây mảng 2 chiều đang quản lý các con trỏ cấp 1 từ
a[0]đếna[3]sẽ là các địa chỉ0x001,0x003,0x004,0x005. - Còn lúc này đây, địa chỉ
0x002đang là con trỏtempquản lý, tafree(temp)giải phóng nó đi 🙂.
temp → nhích các con trỏ a[i] = a[i + 1] với $i$ từ $k$ đến $dong - 2$ → free(temp) → dong--. Nhờ con trỏ mà chỉ nhảy phát là cả dòng đi theo, không phải đụng tới ô nhớ nào bên trong.Cái này nói bằng lời thì hơi "hack não" 😅, nhưng cứ kẻ hình mảng 2 chiều ra giấy, đánh dấu các con trỏ đầu mỗi dòng, rồi nhìn vào sẽ rõ hơn. Hoặc dùng khung minh hoạ dưới đây: chọn cách làm rồi bấm Tiếp. Các bạn chọn thử "Quên temp, free(a[dong − 1])" để thấy tận mắt cái lỗi của em học viên nhé:
Code cuối cùng mình sửa lại cho em học viên chạy ngon lành (cả bản Python cũng làm y hệt ý tưởng, vì trong Python mỗi phần tử của list chính là một tham chiếu tới list con, giống con trỏ cấp 1):
#include <iostream>
#include <cstdlib>
using namespace std;
void xoaDong(int**& a, int& dong, int cot, int viTriXoa)
{
int* temp = a[viTriXoa]; // giữ nhà giùm dòng cần xóa
for (int i = viTriXoa; i < dong - 1; i++)
{
a[i] = a[i + 1]; // chỉ nhảy con trỏ, cả dòng đi theo
}
free(temp);
dong--;
}
int main()
{
int dong, cot;
cin >> dong >> cot;
int** a = (int**)malloc(dong * sizeof(int*));
for (int i = 0; i < dong; i++)
{
a[i] = (int*)malloc(cot * sizeof(int));
for (int j = 0; j < cot; j++)
cin >> a[i][j];
}
int viTriXoa;
cin >> viTriXoa;
xoaDong(a, dong, cot, viTriXoa);
for (int i = 0; i < dong; i++)
{
for (int j = 0; j < cot; j++)
cout << a[i][j] << " ";
cout << "\n";
}
for (int i = 0; i < dong; i++)
free(a[i]);
free(a);
return 0;
}import sys
def xoa_dong(a, dong, vi_tri_xoa):
temp = a[vi_tri_xoa] # giữ dòng cần xóa
for i in range(vi_tri_xoa, dong - 1):
a[i] = a[i + 1] # chỉ đổi "con trỏ" (tham chiếu), cả dòng đi theo
a.pop() # bỏ ô tham chiếu cuối đang bị trùng
del temp # giải phóng dòng cũ
return dong - 1
data = sys.stdin.buffer.read().split()
dong, cot = int(data[0]), int(data[1])
pos = 2
a = []
for i in range(dong):
a.append([int(x) for x in data[pos:pos + cot]])
pos += cot
vi_tri_xoa = int(data[pos])
dong = xoa_dong(a, dong, vi_tri_xoa)
out = []
for i in range(dong):
out.append(' '.join(map(str, a[i])) + ' ')
sys.stdout.write('\n'.join(out) + '\n')free(temp), còn bên C++ nếu cấp phát bằng new thì em hoàn toàn có thể delete[] temp; nhé (phải có [] vì nó đang là con trỏ cấp 1 quản lý nhiều ô nhớ nên phải delete[]). Lúc này chả cần dùng realloc gì cả, vì mỗi a[i] là 1 con trỏ, đại diện cho cả 1 dòng.realloc cho các con trỏ cấp 1 ở từng dòng để bớt đi 1 ô.Khung chạy tay dưới đây chạy đúng từng dòng của code C++ ở trên. Phần đầu là cấp phát và nhập mảng, các bạn có thể bấm Tiếp nhanh qua phần đó để tới hàm xoaDong (dòng 5 – 14):
Đánh giá độ phức tạp của cách làm này:
- Không gian: chỉ thêm 1 con trỏ
temp: $O(1)$. - Thời gian: chỉ có $dong - 1 - viTriXoa$ phép gán con trỏ, không phụ thuộc số cột: $O(dong)$.
Thay vì phải đi vào từng ô cột tương ứng trong từng dòng mà hoán vị tụi nó với nhau, thì giờ nhờ con trỏ mà chỉ nhảy phát là cả dòng đi theo, ngon phết nhở 😁. Suy ngẫm đi nhé, kẻ ra giấy sẽ nhìn rõ :)).
xoaDong: cách 1 gán gần $10^6$ ô, cách 2 chỉ gán 999 con trỏ.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét