Mảng là một phần cơ bản khi bắt đầu nghiên cứu về Cấu Trúc Dữ Liệu. Đồng thời mảng là kiểu dữ liệu mà chúng ta gặp được ở trong mọi ngôn ngữ lập trình.Trong bài viết này sẽ giúp bạn làm quen và có góc tiếp cận dễ dàng với mảng được ví dụ qua C++.
Trong bài viết có liên quan tới con trỏ trong C++, nếu bạn chưa thực sự rành về con trỏ, hãy giành ít phút đọc qua nhé!
Cấu trúc dữ liệu mảng hay là mảng là một cấu trúc dữ liệu bao gồm 1 nhóm các phần tử giá trị, mỗi phần tử được xác định bằng 1 chỉ số (index) hoăc khóa (key).
Tham khảo: Mảng – Wikipedia
Mảng là một trong những cấu trúc dữ liệu cơ bản, lâu đời và phổ biến nhất, thường được sử dụng nhiều trong lập trình.
Mảng có các loại như là:
+ Mảng một chiều
+ Mảng nhiều chiều (2, 3, … n chiều)
+ Ngoài ra còn có mảng động, tuy nhiên trong phạm trù seri bài cấu trúc dữ liệu cơ bản sẽ không đề cập đến mảng động này.
+ Các phần tử trong 1 mảng phải cùng 1 kiểu dữ liệu. Kiểu dữ liệu ở đây có thể là 1 mảng. Khi đó chúng ta có khái niệm mảng của mảng (hay mảng 2 chiều)
+ Mảng sẽ được khai báo trước với kích thước cố định.
+ Các phần tử trong mảng được lưu vào các ô nhớ liên tiếp nhau trên bộ nhớ.
Ưu điểm:
+ Do bản chất việc mảng là các ô nhớ có địa chỉ liên tiếp nhau do vậy sẽ có những lợi ích trong việc truy vấn phần tử rất nhanh với độ phức tạp là O(1).
+ Tính cục bộ về bộ nhớ, bộ nhớ không bị phân mảnh
Nhược điểm
+ Không thể thay đổi kích thước của mảng khi chương trình đang thực hiện.
Chú ý: Với những thông tin trong bài viết này có thể không đúng chính xác với toàn bộ các ngôn ngữ lập trình. Ví dụ như PHP thì mảng sẽ khác một chút so với những điều đã nói. Hiểu rằng trong phạm vi seri bài viết sẽ lấy C++ làm cơ sở của các vấn đề.
Mảng thường được thực hiện các vector, các ma trận, stack, queue, bảng băm…
Ngoài ra còn nhiều ứng dụng khác bạn có thể tham khảo trên wikipedia.
Thông thường đối với 1 mảng sẽ có các hàm thông dụng:
element (p): Trả về phần tử tại vị trí p
insert(p,x): chèn phần tử x vào vị trí p, các phần tử sau p sẽ lùi về sau 1 vị trí
delete(p) Xóa phần tử tại vị trí p, các phần tử sau p sẽ dịch lên 1 vị trí
int arr[100];
Trong đó:
int : kiểu dữ liệu của các phần tử lưu trong mảng
Arr: tên biến
100: Kích thước của mảng
Ngoài ra còn có thể khai báo như sau
int arr[] = {1,2,3,4}
Đây là cách khai báo khi biết rõ trong mảng có những phần tử nào
Tham khảo đoạn mã dưới đây
#include "stdafx.h"
#include ;
#define MAX 100
using namespace std;
// Khai báo mảng với MAX phần tử
int arr[MAX];
// Số phần tử sẽ sử dụng trong mảng
int n;
void input() {
// in ra thông báo nhập số lượng phần tử trong mảng
// endl để báo kết thúc dòng và xuống dòng
cout << "Nhap so phan tu cua mang" <<endl; // Lấy giá trị nhập vào gán vào biến n cin >> n;
for (int i = 0; i < n; i++)
{
cout << "Nhap gia tri phan tu arr[" << i << "]" << endl; cin >> arr[i];
}
}
void printArray(int a[]) {
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
int main()
{
input();
printArray(arr);
system("pause");
return 0;
}
Kết quả nhận được sẽ là
Để truyền mảng dưới dạng là 1 tham số của hàm ta có thể làm như sau
void printArray(int arr[]) {
}
Như đã nói trên đầu bài viết, mảng là 1 cấu trúc dữ liệu liên tục trên các ô nhớ. Do vậy để truy xuất vào dữ liệu của mảng chúng ta cũng có thể chỉ cần địa chỉ ô nhớ đầu tiên mà thôi.
Mặc định khi lấy địa chỉ của 1 mảng, con trỏ đang trỏ về ô nhớ đầu tiên.
Khi đó sẽ truyền mảng vào hàm như sau
void printArray(int* arr) {
}
Cách làm
B1. Lấy giá trị vị trí positon, giá trị value của phần tử cần truyền từ bàn phím.
B2. Kiểm tra vị trí chèn có phù hợp. Nếu < 0 thì thông báo không hợp lệ, Nếu > n thì thêm vào sau vị trí cuối cùng của mảng.
B3. Dịch chuyển toàn bộ các phần tử trong mảng về sau 1 đơn vị
B4. Gán giá trị value vào vị trí position.
B5. Tăng thêm n 1 đơn vị (biến lưu kích thước của mảng)
Dưới đây là đoạn C++ đã thực hiện
void insert(int* arr, int position,int value){
if (position < 0) {
cout << "Vi tri nhap vao khong hop le!";
return;
}
if (position >= n) {
cout << "Vi tri nhap vao lon hon kich thuoc mang, them vao cuoi mang!";
arr[n] = value;
n++; // cập nhật kích thước mảng
return;
}
for (int i = n; i > position ; i--)
{
// Dịch chuyển mảng về phía cuối 1 đơn vị
arr[i] = arr[i-1];
}
arr[position] = value;
n++; //Cập nhật lại kích thước mảng
}
Chú ý tham số đầu hàm truyền vào có : địa chỉ của biến arr, position và value
Cách làm
B1. Kiểm tra tính hợp lệ của vị trí position truyền vào
B2. Dịch mảng về phái trước 1 đơn vị
B3. Giảm giá trị n (biến lưu kích thước mảng) đi 1 đơn vị
void remove(int* arr, int position) {
if (position < 0 || position >= n) {
cout << "Vi tri nhap vao khong hop le!"<<endl;
return;
}
for (int i = position; i < n; i++)
{
arr[i] = arr[i + 1];
}
n--;
}
Kết quả:
Nhap so phan tu cua mang 3 Nhap gia tri phan tu arr[0] 1 Nhap gia tri phan tu arr[1] 4 Nhap gia tri phan tu arr[2] 6 1 4 6 Nhap gia tri can them vao mang: 100 Nhap vi tri can them trong mang 2 1 4 100 6 Nhap vi tri can xoa 2 1 4 6 Press any key to continue . . .
Mã nguồn đầy đủ của chương trình như sau
Mã nguồn được viết trên visual studio nhé
#include "stdafx.h"
#include <iostream>;
#define MAX 100
using namespace std;
// Khai báo mảng với MAX phần tử
int arr[MAX];
// Số phần tử sẽ sử dụng trong mảng
int n;
void input() {
// in ra thông báo nhập số lượng phần tử trong mảng
// endl để báo kết thúc dòng và xuống dòng
cout << "Nhap so phan tu cua mang" <<endl;
// Lấy giá trị nhập vào gán vào biến n
cin >> n;
for (int i = 0; i < n; i++)
{
cout << "Nhap gia tri phan tu arr[" << i << "]" << endl;
cin >> arr[i];
}
}
void printArray(int a[]) {
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
// Hàm chèn dữ liệu giá trị value ở vị trí position
void insert(int* arr, int position,int value){
if (position < 0) {
cout << "Vi tri nhap vao khong hop le!";
return;
}
if (position >= n) {
cout << "Vi tri nhap vao lon hon kich thuoc mang, them vao cuoi mang!"<<endl;
arr[n] = value;
n++; // cập nhật kích thước mảng
return;
}
for (int i = n; i > position ; i--)
{
// Dịch chuyển mảng về phía cuối 1 đơn vị
arr[i] = arr[i-1];
}
arr[position] = value;
n++; //Cập nhật lại kích thước mảng
}
void remove(int* arr, int position) {
if (position < 0 || position >= n) {
cout << "Vi tri nhap vao khong hop le!"<<endl;
return;
}
for (int i = position; i < n; i++)
{
arr[i] = arr[i + 1];
}
n--;
}
int get(int* arr,int position) {
for (int i = 0; i < n; i++)
{
if (i == position) {
return arr[i];
}
}
return -1;
}
int main()
{
input();
printArray(arr);
int position;
int value;
cout << "Nhap gia tri can them vao mang:" << endl;
cin >> value;
cout << "Nhap vi tri can them trong mang" << endl;
cin >> position;
insert(arr, position, value);
printArray(arr);
cout << "Nhap vi tri can xoa" << endl;
cin >> position;
remove(arr, position);
printArray(arr);
cout << "Ban muon tim phan tu vi tri nao?" << endl;
cin >> position;
cout << get(arr, position) << endl;
system("pause");
return 0;
}
Hi vọng với bài viết trên đây bạn đã hiểu được mảng là gì? và cách hoạt động của mảng. Nếu có bất kì thắc mắc nào đừng quên đặt câu hỏi xuống dưới để cùng thảo luận bạn nhé!
Bình luận: