* Khái niệm mảng (Array)
- Mảng là một kiểu dữ liệu có cấu trúc do người lập trình định nghĩa.
- Biểu diễn một dãy các biến có cùng kiểu dữ liệu.
Ví dụ: dãy số nguyên, dãy số thực, dãy ký tự...
- Kích thước mảng được xác định ngay khi khai báo và không thay đổi (mảng tĩnh).
Mục tiêu:
- Hiểu cách khai báo và sử dụng mảng.
- Thực hiện chèn, xóa phần tử tại vị trí xác định.
- Tìm kiếm phần tử trong mảng.
Kiến thức:
- Cú pháp khai báo mảng:
kieu_du_lieu ten_mang[so_phan_tu];
- Chỉ số của mảng bắt đầu từ 0 đến n - 1 (với n là số phần tử).
- Công thức tính bộ nhớ sử dụng:
Bo nho = so_phan_tu * sizeof(kieu_du_lieu);
Ví dụ:
int a[5]; // Mảng 5 số nguyên
// Chỉ số: a[0], a[1], a[2], a[3], a[4]
Ghi nhớ:
- Mảng lưu trữ các phần tử cùng kiểu.
- Truy cập phần tử bằng chỉ số.
- Kích thước mảng không thay đổi sau khi khai báo.
* Các cách khởi tạo mảng
- Cách 1: Khởi tạo đầy đủ các phần tử
int array1[4];
int array2[4] = {5, 8, 2, 7};
- Cách 2: Khởi tạo một số phần tử đầu (các phần tử còn lại = 0)
int array1[4] = {5, 8}; // 5 8 0 0
- Cách 3: Khởi tạo toàn bộ phần tử bằng 0
int array1[4] = {};
- Cách 4: Tự động xác định số phần tử
int array1[] = {5, 8, 2, 7};
- Cách 5 (C++11): Khởi tạo đồng nhất
int array1[4]{5, 8, 2, 7}; // 5 8 2 7
int array2[4]{5, 8}; // 5 8 0 0
int array3[4]{}; // 0 0 0 0
int array4[]{5, 8, 2, 7}; // 5 8 2 7
Gán và truy cập phần tử
- Gán giá trị:
ten_mang[chi_so] = gia_tri;
- Truy cập phần tử:
ten_mang[chi_so];
Ví dụ: Nhập và xuất từng phần tử
#include <bits/stdc++.h>
using namespace std;
const int sopt = 200;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int a[sopt];
int n = 5;
cout << "a[0] = "; cin >> a[0];
cout << "a[1] = "; cin >> a[1];
cout << "a[2] = "; cin >> a[2];
cout << "a[3] = "; cin >> a[3];
cout << "a[4] = "; cin >> a[4];
cout << a[0] << "\n";
cout << a[3] << "\n";
return 0;
}
Ví dụ: Nhập, xuất bằng vòng lặp
#include <bits/stdc++.h>
using namespace std;
const int sopt = 200;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int a[sopt], n;
cout << "Nhap so phan tu, n = ";
cin >> n;
for(int i = 0; i < n; i++)
{
cout << "a[" << i << "] = ";
cin >> a[i];
}
for(int i = 0; i < n; i++)
{
cout << a[i] << "\n";
}
return 0;
}
Ví dụ: Tách hàm nhập và xuất
#include <bits/stdc++.h>
using namespace std;
void Nhap(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << "a[" << i << "] = ";
cin >> a[i];
}
}
void Xuat(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
const int sophantu = 100;
int a[sophantu], n;
cout << "Nhap so phan tu, n = ";
cin >> n;
Nhap(a, n);
Xuat(a, n);
return 0;
}
Ghi nhớ:
- Có nhiều cách khởi tạo mảng linh hoạt.
- Nên dùng vòng lặp để nhập/xuất thay vì viết tay từng phần tử.
- Có thể tách chương trình thành các hàm để dễ quản lý.
* Sắp xếp mảng (Array Sorting)
- Sắp xếp mảng là thao tác thay đổi vị trí các phần tử theo thứ tự mong muốn.
- Có hai dạng phổ biến:
- Sắp xếp tăng dần (từ nhỏ → lớn).
- Sắp xếp giảm dần (từ lớn → nhỏ).
Ý tưởng:
- So sánh từng cặp phần tử.
- Nếu sai thứ tự thì hoán đổi (swap).
Ví dụ chương trình sắp xếp mảng
#include <bits/stdc++.h>
using namespace std;
void Nhap(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << "a[" << i << "] = ";
cin >> a[i];
}
}
void Xuat(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
}
void Sapxeptang(int a[], int n)
{
for(int i = 0; i < n - 1; i++)
{
for(int j = i + 1; j < n; j++)
{
if(a[i] > a[j])
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
void Sapxepgiam(int a[], int n)
{
for(int i = 0; i < n - 1; i++)
{
for(int j = i + 1; j < n; j++)
{
if(a[i] < a[j])
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
const int sophantu = 100;
int a[sophantu], n;
cout << "Nhap so phan tu, n = ";
cin >> n;
Nhap(a, n);
Sapxeptang(a, n);
cout << "Mang tang dan: ";
Xuat(a, n);
cout << "\n";
Sapxepgiam(a, n);
cout << "Mang giam dan: ";
Xuat(a, n);
return 0;
}
Kết quả:
Input: 5 2 9 1 7
Tang dan: 1 2 5 7 9
Giam dan: 9 7 5 2 1
Ghi nhớ:
- Dùng vòng lặp lồng nhau để sắp xếp.
- Đổi chỗ hai phần tử khi sai thứ tự.
- Có thể dùng sort() trong thư viện để tối ưu hơn.
* Sắp xếp chọn (Selection Sort)
- Đây là thuật toán sắp xếp đơn giản và dễ hiểu.
- Ý tưởng: mỗi bước chọn phần tử nhỏ nhất (hoặc lớn nhất) đưa về đúng vị trí.
Nguyên lý hoạt động:
- Duyệt từng vị trí i trong mảng.
- Tìm phần tử nhỏ nhất (hoặc lớn nhất) từ i → n-1.
- Đổi chỗ phần tử đó với a[i].
Ví dụ chương trình
#include <bits/stdc++.h>
using namespace std;
void Nhap(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << "a[" << i << "] = ";
cin >> a[i];
}
}
void Xuat(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
}
void Sapxeptang(int a[], int n)
{
for(int i = 0; i < n - 1; i++)
{
int minindex = i;
for(int j = i + 1; j < n; j++)
{
if(a[minindex] > a[j])
{
minindex = j;
}
}
if(minindex != i)
{
int temp = a[minindex];
a[minindex] = a[i];
a[i] = temp;
}
}
}
void Sapxepgiam(int a[], int n)
{
for(int i = 0; i < n - 1; i++)
{
int maxindex = i;
for(int j = i + 1; j < n; j++)
{
if(a[maxindex] < a[j])
{
maxindex = j;
}
}
if(maxindex != i)
{
int temp = a[maxindex];
a[maxindex] = a[i];
a[i] = temp;
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
const int sophantu = 100;
int a[sophantu], n;
cout << "Nhap so phan tu, n = ";
cin >> n;
Nhap(a, n);
Sapxeptang(a, n);
cout << "Tang dan: ";
Xuat(a, n);
cout << "\n";
Sapxepgiam(a, n);
cout << "Giam dan: ";
Xuat(a, n);
return 0;
}
Ghi nhớ:
- Mỗi vòng lặp sẽ đưa đúng 1 phần tử về vị trí chuẩn.
- Không cần đổi chỗ nhiều lần như bubble sort.
- Độ phức tạp: O(n²).
* Sử dụng hàm sort() để sắp xếp mảng
- C++ cung cấp sẵn hàm sort() trong thư viện <algorithm>.
- Giúp sắp xếp nhanh và tối ưu hơn so với tự viết thuật toán.
Cú pháp:
- Sắp xếp tăng dần toàn bộ mảng:
sort(a, a + n);
- Sắp xếp tăng dần một đoạn từ chỉ số x đến y:
sort(a + x, a + y + 1);
- Sắp xếp giảm dần:
sort(a, a + n, greater<int>());
Ví dụ chương trình
#include <bits/stdc++.h>
using namespace std;
void Nhap(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << "a[" << i << "] = ";
cin >> a[i];
}
}
void Xuat(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
}
void SapxeptangSort(int a[], int n)
{
sort(a, a + n);
}
void SapxepgiamSort(int a[], int n)
{
sort(a, a + n, greater<int>());
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
const int sophantu = 100;
int a[sophantu], n;
cout << "Nhap so phan tu, n = ";
cin >> n;
Nhap(a, n);
SapxeptangSort(a, n);
cout << "Tang dan: ";
Xuat(a, n);
cout << "\n";
SapxepgiamSort(a, n);
cout << "Giam dan: ";
Xuat(a, n);
return 0;
}
Ghi nhớ:
- sort() nhanh hơn các thuật toán tự viết (O(n log n)).
- Có thể sắp xếp toàn bộ hoặc một phần mảng.
- Dùng greater<int>() để sắp xếp giảm dần.
* Comparator trong sort()
- Comparator là một hàm (hoặc đối tượng hàm) trả về giá trị bool.
- Được dùng để xác định cách so sánh giữa hai phần tử khi sắp xếp.
Nguyên tắc:
- Nếu comp(a, b) trả về true → a đứng trước b.
- Nếu comp(a, b) trả về false → b có thể đứng trước a.
- Nếu không truyền comparator → sort() mặc định dùng toán tử <.
Ghi nhớ quan trọng:
- comp(a, b) = true ⇒ thứ tự hiện tại là đúng.
- comp(a, b) = false ⇒ có thể cần đổi chỗ.
Comparator cơ bản:
// Tăng dần
bool comp(int a, int b) {
return a < b;
}
// Giảm dần
bool comp(int a, int b) {
return a > b;
}
Ví dụ 1: Sắp xếp tăng dần
#include <bits/stdc++.h>
using namespace std;
bool comp(int a, int b)
{
return a < b;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int a[10] = {6, 3, 7, 1, 2, 6, 4, 8, 45, 8};
sort(a, a + 10, comp);
cout << "Mang tang dan: ";
for(int i = 0; i < 10; i++)
{
cout << a[i] << " ";
}
return 0;
}
Ví dụ 2: Sắp xếp tùy chỉnh
- Số lẻ đứng trước (tăng dần).
- Số chẵn đứng sau (giảm dần).
#include <bits/stdc++.h>
using namespace std;
bool comp(int a, int b)
{
// Cả hai là số lẻ → tăng dần
if(a % 2 != 0 && b % 2 != 0)
return a < b;
// Cả hai là số chẵn → giảm dần
if(a % 2 == 0 && b % 2 == 0)
return a > b;
// Số lẻ đứng trước số chẵn
return a % 2 != 0;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int a[100];
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
sort(a, a + n, comp);
cout << "Mang sau sap xep: ";
for(int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
return 0;
}
Ghi nhớ:
- Comparator quyết định toàn bộ thứ tự sắp xếp.
- Có thể dùng để giải các bài toán nâng cao (chẵn/lẻ, khoảng cách, cấu trúc...).
- Hiểu đúng comp(a, b) là chìa khóa quan trọng.
* Tìm kiếm phần tử trong mảng (Linear Search)
- Tìm kiếm tuyến tính là phương pháp duyệt lần lượt từng phần tử trong mảng.
- So sánh từng phần tử với giá trị cần tìm.
Ý tưởng:
- Duyệt từ đầu đến cuối mảng.
- Nếu phần tử bằng X → ghi nhận vị trí và tăng số lần xuất hiện.
Ví dụ chương trình
#include <bits/stdc++.h>
using namespace std;
void Nhap(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << "a[" << i << "] = ";
cin >> a[i];
}
}
void Tim(int a[], int n, int X)
{
int solan = 0;
int vitri[100];
int vt = 0;
for(int i = 0; i < n; i++)
{
if(a[i] == X)
{
vitri[vt] = i;
vt++;
solan++;
}
}
if(solan > 0)
{
cout << "Gia tri " << X << " xuat hien " << solan << " lan. Tai vi tri: ";
for(int i = 0; i < solan; i++)
{
cout << vitri[i] << " ";
}
}
else
{
cout << "Gia tri " << X << " khong xuat hien trong mang";
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
const int sophantu = 100;
int a[sophantu], n, X;
cout << "Nhap so phan tu, n = ";
cin >> n;
Nhap(a, n);
cout << "Nhap gia tri can tim, X = ";
cin >> X;
Tim(a, n, X);
return 0;
}
Kết quả:
Mang: 2 5 3 5 7
X = 5
→ Xuat hien 2 lan tai vi tri: 1 3
Ghi nhớ:
- Không cần mảng đã sắp xếp.
- Dễ cài đặt, phù hợp với mảng nhỏ.
- Độ phức tạp: O(n).
* Chèn phần tử vào mảng
- Chèn là đưa một phần tử mới vào mảng tại vị trí xác định.
- Cần dời các phần tử phía sau sang phải để tạo chỗ trống.
Ý tưởng:
- Duyệt từ cuối mảng về vị trí cần chèn.
- Dịch các phần tử sang phải.
- Gán giá trị mới vào vị trí cần chèn.
Ví dụ: Chèn tại vị trí bất kỳ
#include <bits/stdc++.h>
using namespace std;
void Nhap(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << "a[" << i << "] = ";
cin >> a[i];
}
}
void Xuat(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
}
void Chentaivitri(int a[], int &n, int vitri, int giatri)
{
for(int i = n; i > vitri; i--)
{
a[i] = a[i - 1];
}
a[vitri] = giatri;
n++;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
const int sophantu = 100;
int a[sophantu], n, vitri, giatri;
cout << "Nhap so phan tu, n = ";
cin >> n;
Nhap(a, n);
cout << "Nhap vi tri chen: ";
cin >> vitri;
cout << "Nhap gia tri chen: ";
cin >> giatri;
Chentaivitri(a, n, vitri, giatri);
cout << "Mang sau khi chen: ";
Xuat(a, n);
return 0;
}
Ví dụ: Chèn vào mảng đã sắp xếp
- Mục tiêu: sau khi chèn vẫn giữ đúng thứ tự (tăng hoặc giảm).
#include <bits/stdc++.h>
using namespace std;
void Nhap(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
}
void Xuat(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << "\n";
}
void Chentaivitri(int a[], int &n, int vitri, int giatri)
{
for(int i = n; i > vitri; i--)
{
a[i] = a[i - 1];
}
a[vitri] = giatri;
n++;
}
void Sapxep(int a[], int n, bool tangdan)
{
if(tangdan)
sort(a, a + n);
else
sort(a, a + n, greater<int>());
Xuat(a, n);
}
void Chendasapxep(int a[], int &n, int giatri, bool tangdan)
{
int vitri = n;
for(int i = 0; i < n; i++)
{
if((tangdan && a[i] > giatri) || (!tangdan && a[i] < giatri))
{
vitri = i;
break;
}
}
Chentaivitri(a, n, vitri, giatri);
cout << "Mang sau khi chen: ";
Xuat(a, n);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
const int sophantu = 100;
int a[sophantu], n, giatri;
bool tangdan = true;
cout << "Nhap n: ";
cin >> n;
Nhap(a, n);
cout << "Sap xep tang dan (1) / giam dan (0): ";
cin >> tangdan;
Sapxep(a, n, tangdan);
cout << "Nhap gia tri can chen: ";
cin >> giatri;
Chendasapxep(a, n, giatri, tangdan);
return 0;
}
Ghi nhớ:
- Luôn kiểm tra mảng còn chỗ trống trước khi chèn.
- Phải dịch phần tử từ cuối về để tránh mất dữ liệu.
- Với mảng đã sắp xếp, cần tìm đúng vị trí chèn để giữ thứ tự.
* Xóa phần tử trong mảng
- Xóa là loại bỏ một phần tử khỏi mảng.
- Cần dời các phần tử phía sau sang trái để lấp chỗ trống.
Ý tưởng:
- Từ vị trí cần xóa, dịch các phần tử bên phải sang trái.
- Giảm số phần tử của mảng (n--).
Ví dụ: Xóa tại vị trí bất kỳ
#include <bits/stdc++.h>
using namespace std;
void Nhap(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << "a[" << i << "] = ";
cin >> a[i];
}
}
void Xuat(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
}
void Xoataivitri(int a[], int &n, int vitri)
{
for(int i = vitri; i < n - 1; i++)
{
a[i] = a[i + 1];
}
n--;
cout << "Mang sau khi xoa: ";
Xuat(a, n);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
const int sophantu = 100;
int a[sophantu], n, vitri;
cout << "Nhap so phan tu, n = ";
cin >> n;
Nhap(a, n);
do
{
cout << "Nhap vi tri xoa: ";
cin >> vitri;
}
while(vitri < 0 || vitri >= n);
Xoataivitri(a, n, vitri);
return 0;
}
Ví dụ: Xóa các phần tử trùng lặp
- Sau khi xóa, mỗi phần tử chỉ xuất hiện 1 lần.
#include <bits/stdc++.h>
using namespace std;
void Nhap(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
}
void Xuat(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
}
void Xoatrunglap(int a[], int &n)
{
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n;)
{
if(a[i] == a[j])
{
for(int k = j; k < n - 1; k++)
{
a[k] = a[k + 1];
}
n--;
}
else
{
j++;
}
}
}
cout << "Mang sau khi xoa trung lap: ";
Xuat(a, n);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
const int sophantu = 100;
int a[sophantu], n;
cout << "Nhap n: ";
cin >> n;
Nhap(a, n);
Xoatrunglap(a, n);
return 0;
}
Ghi nhớ:
- Xóa phần tử phải dịch mảng sang trái.
- Sau khi xóa cần giảm n.
- Bài xóa trùng lặp thường xuất hiện trong đề thi.
* Kiểm tra mảng đối xứng (Palindrome Array)
- Mảng đối xứng là mảng có các phần tử đọc từ trái sang phải giống như từ phải sang trái.
- Ví dụ: 1 2 3 2 1 là mảng đối xứng.
Ý tưởng:
- So sánh phần tử đầu với phần tử cuối.
- So sánh tiếp tục vào trong (a[1] với a[n-2], ...).
- Nếu tất cả đều bằng nhau → mảng đối xứng.
Ví dụ chương trình
#include <bits/stdc++.h>
using namespace std;
void Nhap(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout << "a[" << i << "] = ";
cin >> a[i];
}
}
bool Checkdoixung(int a[], int n)
{
for(int i = 0; i < n / 2; i++)
{
if(a[i] != a[n - i - 1])
{
return false;
}
}
return true;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
const int sophantu = 100;
int a[sophantu], n;
cout << "Nhap so phan tu, n = ";
cin >> n;
Nhap(a, n);
if(Checkdoixung(a, n))
{
cout << "La mang doi xung\n";
}
else
{
cout << "Khong phai mang doi xung\n";
}
return 0;
}
Ví dụ:
Input: 1 2 3 2 1 → La mang doi xung
Input: 1 2 3 4 5 → Khong doi xung
Ghi nhớ:
- Chỉ cần duyệt đến n/2 là đủ.
- Nếu có 1 cặp không bằng nhau → kết luận ngay.
- Độ phức tạp: O(n).