Cấu trúc dữ liệu mảng – Cấu trúc dữ liệu và giải thuật cơ bản

27/09/2020 - lượt xem
Chia sẻ
 
Rate this post

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é!

Mảng là gì?

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.

Những điều cần biết khi nói về mảng

+ 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, nhược điểm của mảng

Ư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 đề.

Ứng dụng của mảng

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.

Các hàm thông dụng của mạng

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í

Ví dụ với mảng trong C++

Khai báo mảng trong C++

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

Nhập dữ liệu vào mảng

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à

Nhập giá trị vào mảng C++
Nhập giá trị vào mảng C++

Truyền hàm là 1 tham số của hàm

Để 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) {
}

Chèn 1 phần từ vào trong mảng

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

Xóa 1 phần tử trong mảng

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é!

    Liên hệ với chúng tôi

    Để lại thông tin để nhận được các bài viết khác

    Rate this post

    Xem thêm nhiều bài tin mới nhất về Cấu trúc dữ liệu và giải thuật

    Xem thêm