Bạn đã quá quen với việc sử dụng mảng trên C/C++? Có thể nói, mảng với ngôn ngữ lập trình C/C++. Mảng giúp ta quản lý bộ nhớ phục vụ cho việc thao tác khi lập trình thuận tiện, linh động và tiết kiệm thời gian. Chúng ta khi mới học lập trình hay có thói quen tạo ra các mạng có một số lượng phần tử cố định, ví dụ tạo mảng có 1000 phần tử. Vậy có cách nào để không phải tạo ra một mảng với số lượng phần tử bất kỳ ngay lúc chạy chương trình?
Đây là một bài viết tôi viết dành tặng một người bạn sau lời hứa sẽ giúp anh ta quen với việc cấp phát bộ nhớ động, một điều “diệu kỳ” mà một người đã quen với Pascal thấy lạ lẫm. Người bạn này của tôi thì rất giỏi về thuật toán nhưng chưa kinh qua nhiều với C++.
Bài viết này chỉ ớ mức yêu cầu trình độ cơ bản về C/C++ do tôi vẫn còn đang học tập, nghiên nghiên cứu trong lĩnh vực lập trình. Bài viết không khỏi tránh thiếu sót với một người chưa dày dặn kinh nghiêm như tôi. Rất mong nhận sự đóng góp, hồi âm của các bạn gần xa yêu thích bộ môn lập trình.
Bài toán gợi mở
Chúng ta hãy bắt đầu với một bài toán cơ bản gợi mở vấn đề. Yêu cầu bài toán là: Viết chương trình yêu cầu người dùng nhập vào n số nguyên, tìm giá trị lớn nhất trong các số vừa nhập vào.
Để giải quyết bài toán này, ta thường sử dụng mảng và vòng lặp for. Thuật toán cũng khá đơn giản như sau:
#include <iostream> #include <stdlib.h> using namespace std;
int main()
{
int nums[100];
int n;
// yeu cau nguoi dung nhap vao so luong phan tu
cout << "Nhap vao so luong phan tu: ";
cin >> n;
// nhap vao gia tri cho tung phan tu
for(int i=0; i<n; i++)
{
cout << "Nhap vao phan tu thu " << i << ": ";
cin >> nums[i];
}
// thuat toan tim gia tri lon nhat trong mot mang
int maxVal = nums[0];
for(int j=1; j<n; j++)
{
if(maxVal<nums[j])
maxVal = nums[j];
}
// in ket qua ra man hinh
cout << "\nVay gia tri lon nhat la " << maxVal << endl;
system("pause");
return 0;
}
Như ta có thể thấy, chúng ta đã tạo ra mảng “nums” có thể chứa 100 phần tử để giải quyết vấn đề của bài toán. Người dùng sẽ nhập vào giá trị cho n để xác định số lượng phần tử mà bài toán sẽ thực hiện.
Vậy điều gì xảy ra khi người dùng nhập quá 100 phần tử? Chắc chắn chương trình sẽ có một số sai lệch nhất định, và điều này hoàn toàn cấm kị trong lập trình khi không lường trước được người dùng có thể vi phạm điều khoản là “anh không được nhập n quá 100”. Vì vậy ta có thể kiểm tra giá trị n ngay khi người dùng nhập vào:
if(n>100)
{
cout << "Please input again.";
return 0;
}
Câu lệnh trên đảm bảo rằng n không được lớn hơn 100 và vấn đề tránh vượt ngoài vùng quản lý đã được giải quyết.
Giả sử, ta thiết lập số phần tử của nums là 1000 chẳng hạng. Và giả sử nếu trên máy tính của bạn 1 biến int chiếm 4 byte, vậy thì mảng này chiếm khoảng 4.000 byte trên máy tính của bạn. Và người dùng nhập vào n = 10. Tức là thực thể chỉ có 4×10 = 40 byte được sử dụng, và bạn đã bỏ phí tới 3960 byte một cách vô ích.
Chúng ta đều đã biết không thể dùng câu lệnh tạo mảng thông thường để yêu cầu người dùng nhập một mảng có n phần tử bất kỳ.
cout << "nhap vao so luong phan tu: ";
cin >> n;
int a[n] // wrong
Vậy, liệu có cách nào khả dĩ để tạo một mảng có n phần tử bất kỳ ngay trong lúc chương trình đang chạy?
Cấp phát bộ nhớ động
Ta đã biết có 5 vùng nhớ trên RAM:
+ Vùng toàn cục – Global name space
+ Thanh ghi – Registrers
+ Vùng mã – Code space
+ Ngăn xếp – stack
+ Vùng lưu trữ tự do: Heap
Vùng toàn cục chứa các biến toàn cục của chương trình. Còn các biến cục bộ và các tham số của hàm dược chứa trong ngăn xếp theo mô hình “vào sau, ra trước”. Vùng mã chứa các mã thực thi của chương trình và thanh ghi được sử dụng để theo dõi đỉnh của ngăn xếp và con trỏ lệnh.
Vậy vùng lưu trữ tự do để làm gì? Vùng lưu trữ tự do là một vùng nhớ lớn chưa những ô nhớ “tự do” đang chờ bạn gọi yêu cầu sử dụng. Nghĩa là bạn không cần phải khai báo việc sử dụng những ô nhớ này trước khi chương trình chạy như các biến và mảng thông thường. Những ô nhớ “tự do” này sẽ được cấp ngay trong lúc chương trình chạy.
Điểm tối ưu là bạn sẽ cấp phát bộ nhớ linh động ngay trong lúc chương trình chạy cho phù hợp với yêu cầu sử dụng khi đang chạy, và dữ liệu trên vùng lưu trữ này chỉ được xóa khi chương trình kết thúc hoặc dùng lệnh giải phóng bộ nhớ.
Người ta thường gọi kĩ thuật này là “cấp phát bộ nhớ động”. Trong C++, kĩ thuật này sử dụng từ khóa “new” và con trỏ để yêu cầu bộ nhớ trên vùng lưu trữ tự do.
kiểu_dữ_liệu * pPointer = new kiểu_dữ_liệu;
Ví dụ, ta yêu cầu một vùng nhớ 4 byte trên vùng lưu trữ tự do cho kiểu dữ liệu int:
int * pPointer = new int;
Việc sử dụng pPointer hoàn toàn như việc sử dụng con trỏ bình thường khác:
*pPointer = 4; // gan gia tri cho vung nho cout << "Value: " << *pPointer << endl;
Ngoài ra, ta có thể sử dụng từ khóa “delete” để giải phóng bộ nhớ trên vùng này:
delete pPointer;
Nếu không thực hiện việc giải phóng bộ nhớ trước khi tái sử dụng lại con trỏ pPointer như trên có thể gây ra hiện tượng rò rỉ bộ nhớ. Những vấn đề này sẽ được bàn luận ở một bài viết khác.
Sử dụng kĩ thuật “cấp phát bộ nhớ động” cho bài toán đầu đề
Chúng ta có thể tạo một mảng với n phần tử bất kỳ trên vùng lưu trữ tự do bằng câu lệnh sau:
int * nums = new int[n];
Với n là một biến do người dùng nhập vào giá trị trong lúc chạy chương trình. Thử thay đổi mã nguồn ban đầu, ta được chương trình sau:
#include <iostream>
#include <stdlib.h>
using namespace std;
int main()
{
int * nums;
int n;
// yeu cau nguoi dung nhap vao so luong phan tu
cout << "Nhap vao so luong phan tu: ";
cin >> n;
// yeu cau bo nho tren vung luu tru tu do
// nghia la tao mot mang co n phan tu tren vung luu tru tu do
nums = new int[n];
// nhap vao gia tri cho tung phan tu
for(int i=0; i<n; i++)
{
cout << "Nhap vao phan tu thu " << i << ": ";
cin >> nums[i];
}
// thuat toan tim gia tri lon nhat trong mot mang
int maxVal = nums[0];
for(int j=1; j<n; j++)
{
if(maxVal<nums[j])
maxVal = nums[j];
}
// in ket qua ra man hinh
cout << "\nVay gia tri lon nhat la " << maxVal << endl;
// giai phong bo nho tren vung luu tru tu do
delete nums;
system("pause");
return 0;
}
Chúng ta biết rằng có một mảng ví dụ như mangA[100]. Thì bản thân tên mảng là con trỏ chỉ tới phần tử đầu tiên của mảng. Do đó, khi tạo mảng trên vùng lưu trữ tự do, cách sử dụng cũng không khác mảng thông thường. Ví dụ:
cin >> n; int * mangA = new int[n]; mangA[0] = 3;
Bạn hãy chạy thử chương trình và kiểm chứng hoạt động.
Nhược điểm của việc cấp phát bộ nhớ động
Như đã thảo luận ở trên, việc cấp phát bộ nhớ động có thể gây rò rĩ bộ nhớ nếu bạn không giải phóng bộ nhớ trước khi tái sử dụng con trỏ trỏ tên vùng nhớ trên Heap.
Ngoài ra, bộ nhớ máy tính dù thế nào vẫn là “hữu hạn”, việc cấp phát bộ nhớ động vô tội vạ và không suy tính có thể làm crash chương trình và treo máy tính trên những chương trình lớn.
Vì vậy, khi tạo các mảng trên Heap, bạn cũng nên quy định số phần tử tối đa được tạo bằng việc tạo một hằng nào đó, ví dụ”MAX_EL” và dùng câu lệnh if để kiểm tra số lượng phần tử người dùng yêu cầu có vượt quá MAX_EL hay không.
Công Hậu, nvconghau1995@gmail.com
JASON NGUYEN 