Thuật toán chèn phần tử vào một mảng bằng code c++

Bài viết hôm nay mình sẽ hướng dẫn các bạn cách chèn phần tử vào mảng một chiều sử dụng code c++.

Giới thiệu cách chèn phần tử vào mảng

Giả sử mảng của chúng ta có n phần tử: a0, a1, a2, a3, …, a(k-1), ak, …,a(n-1). Bây giờ bạn muốn chèn vào một phần tử có giá trị là b tại vị trí k trong mảng ( 0 ≤k≤n).

Khi đó mảng của chúng ta sẽ là: a0, a1, a2, a3, …,a(k-1), b, ak, …,a(n-1). Tại phần tử b bây giờ sẽ có chỉ số là k tức là giá trị a[k] = b.

Ta có chỉ số của mảng trước khi bị chèn sẽ là: 0, 1, 2, …, k-1, k, .., n-2, n-1

Chỉ số của mảng sau khi bị chèn sẽ là: 0, 1, 2, …, k’-1, k’, …, n’-2, n’-1. Với k’ chính là chỉ số của phần tử vừa chèn.

Ta nhận thấy như sau:

• a[k’-1] = a[k-1]
• a[k’] = b
• a[k’+1] = a[k]
• a[k’+2] = a[k+1]
• …
• a[n’-1] = a[n-1]

Với n' = n+1

Cách chèn phần tử vào mảng một chiều bằng cách dùng mảng phụ

Ta nhận thấy như sau:

• Các phần tử trước vị trí k sẽ không thay đổi. Từ đây ta copy các phần tử của mảng cần chèn (giả sử mảng a) sang một mảng phụ b.
• Ta sẽ gán giá trị a[k] = value ( tức là giá trị cần chèn)
• Sau đó ta tiến hành copy các phần tử từ a[k] trở đi của mảng a sang mảng b.
• Vậy là mảng b chính là mảng mà chúng ta đang cần. Ta chỉ cần cấp phát động lại mảng a và tiến hành copy tất cả các giá trị của mảng b sang là đã xong bài toán.

Mô phỏng bằng tay:

a = { 1, 2 , 4}
*Chèn giá trị 2 vào vị trí thứ 3 (Tức là a[2] vì mảng bắt đầu từ 0 mà )
*Các bước thực hiện:
b = { 1, 2 }
b = { 1, 2, 3}
b = { 1, 2, 3, 4}
*Copy mảng b sang a
a = { 1, 2, 3, 4}

Code tham khảo:

#include <iostream>
using namespace std;
void nhap(int *a, int n) {
	for (int i = 0; i < n; i++) {
		cout << "Nhap a[" << i << "]: ";
		cin >> a[i];
	}
}
void xuat(int *a, int n) {
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << endl;
}
int main()
{
	int n,k,ak;
	/*Khai báo mảng a*/
	int *a;
	cout << "Nhap vao so phan tu: ";
	cin >> n;
	/*Cấp phát bộ nhớ*/
	a = new int[n];
	nhap(a, n);
	xuat(a, n);
	cout << "Vi tri can chen: ";
	cin >> k; k--;
	cout << "Nhap phan tu can chen: ";
	cin >> ak;
	/*Copy từ đầu đến a[k-1]*/
	int *b = new int[n + 1];
	for (int i = 0; i < k; i++)
		b[i] = a[i];
	b[k] = ak;
	for (int i = k+1; i < n+1; i++)
		b[i] = a[i-1];
	/*Tiến hành cấp phát động lại a*/
	delete a;
	n++;
	a = new int[n ];
	for (int i = 0; i < n; i++)
		a[i] = b[i];
	xuat(a, n);
}

Nhap vao so phan tu: 3
Nhap a[0]: 1
Nhap a[1]: 2
Nhap a[2]: 4
1 2 4
Vi tri can chen: 3
Nhap phan tu can chen: 3
1 2 3 4

Cách chèn phần tử vào mảng tối ưu hơn.

Như các bạn có thể thấy sau khi chèn vào vị trí k thì các phần tử a[k’+1] = a[k]. Từ đây ta chỉ cần dịch các giá trị a[i] (i chạy từ k đến n-1) về phía sau và sau đó gán phần tử a[k] = ak.

Để dịch được thì các bạn dùng một vòng for chạy từ n-1 đến k. Ta sẽ lấy giá trị a[i] = a[i-1].

Mô phỏng bằng tay:

a = { 1, 2 , 4}
*Chèn giá trị 2 vào vị trí thứ 3 (Tức là a[2] vì mảng bắt đầu từ 0 mà )
*Các bước thực hiện:
a = { 1, 2, 2, 4}
a = { 1, 2, 3, 4}

Code tham khảo:

#include <iostream>
using namespace std;
void nhap(int *a, int n) {
	for (int i = 0; i < n; i++) {
		cout << "Nhap a[" << i << "]: ";
		cin >> a[i];
	}
}
void xuat(int *a, int n) {
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << endl;
}
int main()
{
	int n,k,ak;
	/*Khai báo mảng a*/
	int *a;
	cout << "Nhap vao so phan tu: ";
	cin >> n;
	/*Cấp phát bộ nhớ*/
	a = new int[n];
	nhap(a, n);
	xuat(a, n);
	cout << "Vi tri can chen: ";
	cin >> k; k--;
	cout << "Nhap phan tu can chen: ";
	cin >> ak;
	/*Copy từ đầu đến a[k-1]*/
	n++;
	int *b = new int[n];
	for (int i = 0; i < n-1; i++)
		b[i] = a[i];
	for (int i = n - 1; i > k; i--)
		b[i] = b[i - 1];
	b[k] = ak;
	/*Tiến hành cấp phát động lại a*/
	delete a;
	a = new int[n ];
	for (int i = 0; i < n; i++)
		a[i] = b[i];
	xuat(a, n);
}

Nhap vao so phan tu: 3
Nhap a[0]: 1
Nhap a[1]: 2
Nhap a[2]: 4
1 2 4
Vi tri can chen: 3
Nhap phan tu can chen: 3
1 2 3 4

Bài viết mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !