Lập trình C

Các kỹ thuật trên mảng một chiều

Các kỹ thuật trên mảng 1 chiều
Được viết bởi Minh Hoàng

Series lập trình C, ngôn ngữ lập trình hệ thống mạnh mẽ.

– Trong nội dung của bài viết này, mình sẽ trình bày một số kỹ thuật quan trọng khi thao tác với mảng 1 chiều trong lập trình C. Vì bài viết có liên quan đến kiến thức của 3 phần bên dưới nên các bạn có thể xem lại nếu cần nhé:

  1. Hàm và cách sử dụng trong lập trình C/C++
  2. Tham trị, tham chiếu trong lập trình C/C++
  3. Mảng một chiều trong lập trình C

– Nội dung gồm các phần như sau:

  1. Nhập, xuất mảng các số nguyên.
  2. Kiểm tra mảng có phải toàn số dương hay không?
  3. Tìm giá trị lớn nhất, nhỏ nhất của mảng.
  4. Sắp xếp mảng tăng dần, giảm dần.
  5. Tách mảng (tách các số âm trong mảng ra một mảng mới)
    ・ Mảng ban đầu: 8, -5, 0, -2, 9
    ・ Tách thành 1 mảng mới: -5, -2
  6. Gộp mảng (gộp mảng vừa tách vào mảng cũ)
    ・ Gộp lại thành: 8, -5, 0, -2, 9, -5, -2
  7. Tìm kiếm một phần tử trong mảng.
  8. Thêm một phần tử vào mảng.
  9. Xóa một phần tử khỏi mảng.
  10. Hàm main thực hiện chương trình.
1. Nhập, xuất mảng các số nguyên.
1. Nhập, xuất mảng các số nguyên.
/*
 * Hàm nhập mảng: tham số là mảng kiểu nguyên, và số phần tử n của mảng sẽ
 * truyền kiểu tham chiếu (vì muốn sau khi ra khỏi hàm nhập thì giá trị n
 * cũng sẽ dc mang theo đến hàm main để dùng thực hiện các chức năng khác)
 */
void NhapMang(int a[], int &n)
{
	// Nhập số phần tử của mảng và kiểm tra tính hợp lệ
	do {
		printf( "\nNhap so luong phan tu cua mang: " );
		scanf_s( "%d", &n );

		if ( n <= 0 || n > MAX ) {
			printf( "So luong phan tu cua mang khong hop le (1 -> %d).\n", MAX );
		}
	} while ( n <= 0 || n > MAX );

	// Nhập giá trị cho mảng
	for ( int ii= 0; ii < n; ii++ )
	{
		printf( "\nNhap a[%d] = ", ii );
		scanf_s( "%d", &a[ii] );
	}
}

/*
 * Hàm xuất mảng: tham số là mảng kiểu nguyên, và số phần tử n của mảng
 * truyền kiểu tham chiếu HAY tham trị đều được (vì đối với hàm xuất không
 * làm thay đổi giá trị của n, nên sẽ truyền n theo kiểu tham trị)
 */
void XuatMang(int a[], int n)
{
	for ( int ii = 0; ii < n; ii++ )
	{
		printf("%d   ", a[ii]);
	}
}
2. Kiểm tra mảng có phải toàn số dương hay không?
2. Kiểm tra mảng có phải toàn số dương hay không?
/*
 * Hàm kiểm tra mảng có phải là toàn số dương hay không
 */
bool KiemtraMang(int a[], int n)
{
	for (int ii = 0; ii < n; ii++)
	{
		if (0 > a[ii]) {
			// Nếu có số âm thì trả về kết quả luôn, không cần kiểm tra nữa.
			return false;
		}
	}

	return true;
}
3. Tìm giá trị lớn nhất, nhỏ nhất của mảng.
3. Tìm giá trị lớn nhất, nhỏ nhất của mảng.
/*
 * Hàm tìm giá trị nhỏ nhất trong mảng
 */
int TimMin(int a[], int n)
{
	// Cho min bằng phần tử đầu tiên của mảng
	int min = a[0];

	// Từ đó check min với phần tử thứ 2 đến hết mảng
	for (int ii = 1; ii < n; ii++)
	{
		if (a[ii] < min) {
			min = a[ii];
		}
	}
	
	return min;
}

/*
 * Hàm tìm giá trị lớn nhất trong mảng
 */
int TimMax(int a[], int n)
{
	int max = a[0];

	for (int ii = 1; ii < n; ii++)
	{
		if (a[ii] > max) {
			max = a[ii];
		}
	}

	return max;
}
4. Sắp xếp mảng tăng dần, giảm dần.
4. Sắp xếp mảng tăng dần, giảm dần.
/*
 * Hàm hoán vị 2 số nguyên
 */
void HoanVi(int &x, int &y)
{
	int tmp = x;
	x = y;
	y = tmp;
}

/*
 * Hàm sắp xếp mảng
 */
void SapXepMang(int a[], int n, bool isTangDan)
{
	// Thực hiện so sánh tuần tự
	for (int ii = 0; ii < n - 1; ii++)
	{
		for (int jj = ii + 1; jj < n; jj++)
		{
			// Nếu là sắp xếp tăng dần
			if (isTangDan)
			{
				if (a[ii] > a[jj])
				{
					HoanVi(a[ii], a[jj]);
				}
			}
			// Nếu là sắp xếp giảm dần
			else
			{
				if (a[ii] < a[jj])
				{
					HoanVi(a[ii], a[jj]);
				}
			}
		}
	}
}
5. Tách mảng (tách các số âm trong mảng ra một mảng mới)
5. Tách mảng (tách các số âm trong mảng ra một mảng mới)
/*
 * Tách mảng (Vì số phần tử của [mảng Temp] sau khi tách sẽ thay đổi,
 * nên sẽ truyền kiểu tham chiếu)
 */
void TachMang(int a[], int n, int Temp[], int &nTemp)
{
	nTemp = 0;

	// Duyệt mảng a để tìm ra các số âm lưu vào mảng Temp
	for (int ii = 0; ii < n; ii++)
	{
		if (0 > a[ii])
		{
			Temp[nTemp++] = a[ii];

			/* Tương đương với cách viết: 
			   Temp[nTemp] = a[ii];
			   nTemp++;					*/
		}
	}
}
6. Gộp mảng (gộp mảng vừa tách vào mảng cũ)
6. Gộp mảng (gộp mảng vừa tách vào mảng cũ)
/*
 * Gộp mảng (Vì số phần tử của [mảng a] sau khi gộp sẽ thay đổi,
 * nên sẽ truyền kiểu tham chiếu)
 */
void GopMang(int a[], int &n, int Temp[], int nTemp)
{
	// Giữ lại số phần tử ban đầu của mảng a
	int m = n;

	// Gộp số lượng phần tử của mảng Temp vào mảng a	
	n += nTemp;

	// Thêm các phần tử của mảng Temp vào mảng a
	for (int ii = (n - nTemp); ii < n; ii++)
	{
		a[ii] = Temp[ii - m];
	}

	/* a	: 1, 2, 3, 4, 5
	   Temp	: 6, 7
	   a[5] = Temp[0]
	   a[6] = Temp[1]	  */
}
7. Tìm kiếm một phần tử trong mảng.
7. Tìm kiếm một phần tử trong mảng.
/*
 * Hàm tìm kiếm xem 1 số có trong mảng hay không
 */
bool Timkiem(int a[], int n, int x) // x là phần tử cần tìm kiếm
{
	// Duyệt từng phần tử trong mảng 
	for (int ii = 0; ii < n; ii++) {	
		// đem so sánh với x
		if (x == a[ii])
		{
			return true;
		}
	}

	return false;
}
8. Thêm một phần tử vào mảng.
8. Thêm một phần tử vào mảng.
/*
 * Hàm thêm 1 phần tử vào 1 vị trí trong mảng
 */
void ThemPhanTu(int a[], int &n, int PhanTuThem, int ViTriThem)
{
	/* Mảng a ban đầu:
	   ・chỉ số:		0 1 2 3 4 5 6 7
	  ・phần tử:	   a b c d e f g h

	  Thêm phần tử X vào vị trí thứ 3 trong mảng.

	  Mảng a sau khi thêm:
	  ・chỉ số:		0 1 2 3 4 5 6 7 8
	  ・phần tử:		a b c X d e f g h

	  VỊ TRÍ SAU = VỊ TRÍ TRƯỚC
			a[4] = a[3]
			a[5] = a[4]
			a[6] = a[5]
			a[7] = a[6]
			a[8] = a[7]

      Nếu for() từ trên xuống thì tất cả giá trị sẽ là của a[3]
	  (vì qua các lần gán kết quả bị ghi đè))
	  Do đó, sẽ thực hiện for() từ <<<dưới lên>>>, rồi thực hiện phép gán giá trị.

	  * Cách 1: Chọn theo VỊ TRÍ SAU, ta thấy:
		・a[4] = (Vị trí Thêm + 1) = 3 + 1
		・a[8] = Tổng sổ phần tử ban đầu của mảng a = 8
		for (int ii = n; ii >= ViTriThem + 1; ii--)
		{
			//SAU = TRƯỚC
			a[ii] = a[ii - 1];
		}

	  * Cách 2: Chọn theo VỊ TRÍ TRƯỚC, ta thấy:
		・a[3] = Vị trí Thêm = 3
		・a[7] = (Tổng sổ phần tử ban đầu của mảng a - 1) = 8 - 1
		for (int ii = n - 1; ii >= ViTriThem; ii--)
		{
			//SAU	  = TRƯỚC
			a[ii + 1] = a[ii];
		}
	*/
	for (int ii = n; ii >= ViTriThem + 1; ii--)
	{
		//SAU = TRƯỚC
		a[ii] = a[ii - 1];
	}

	// Tăng số lượng phần tử của mảng a
	n++;

	a[ViTriThem] = PhanTuThem;
}
9. Xóa một phần tử khỏi mảng.
1. Xóa một phần tử khỏi mảng.
/* 
 * Hàm xóa 1 phần tử tại 1 vị trí trong mảng
 */
void XoaPhanTu(int a[], int &n, int ViTriXoa)
{
	/* Mảng a ban đầu:
	   ・chỉ số:		0 1 2 3 4 5 6 7
	  ・phần tử:	   a b c d e f g h

	  Xóa phần tử X tại vị trí thứ 3 trong mảng.

	  Mảng a sau khi xóa:
	  ・chỉ số:		0 1 2 3 4 5 6
	  ・phần tử:		a b c e f g h

	  VỊ TRÍ SAU = VỊ TRÍ TRƯỚC
			a[3] = a[4]
			a[4] = a[5]
			a[5] = a[6]
			a[6] = a[7]

	  Nếu for() từ dưới lên, thì tất cả giá trị sẽ là của a[7]
	  (vì qua các lần gán kết quả bị ghi đè))
	  Do đó, sẽ thực hiện for() từ <<<trên xuống>>>, rồi thực hiện phép gán giá trị.

	  * Cách 1: Chọn theo VỊ TRÍ SAU, ta thấy:
	  ・a[3] = Vị trí xóa = 3
	  ・a[6] = Ban đầu vị trí cuối mảng là (n - 1), giờ xóa đi 1 phần từ thì vị trí cuối mảng sẽ thành (n - 2)
	  //OR: for (int ii = ViTriXoa; ii < (n - 1); ii++)
	  for (int ii = ViTriXoa; ii <= (n - 2); ii++)
	  {
		  //SAU = TRƯỚC
		  a[ii] = a[ii + 1];
	  }

	  * Cách 2: Chọn theo VỊ TRÍ TRƯỚC, ta thấy:
	  ・a[4] = (Vị trí Thêm + 1) = 3 + 1
	  ・a[7] = (Tổng sổ phần tử ban đầu của mảng a - 1) = 8 - 1
	  // OR for (int ii = ViTriXoa + 1; ii < n; ii++)
	  for (int ii = ViTriXoa + 1; ii <= n - 1; ii++)
	  {
		  //SAU	  = TRƯỚC
		  a[ii - 1] = a[ii];
	  }
	*/
	for (int ii = ViTriXoa + 1; ii <= n - 1; ii++)
	{
		//SAU	  = TRƯỚC
		a[ii - 1] = a[ii];
	}

	// Giảm số lượng phần tử của mảng a
	n--;
}
10. Hàm main thực hiện chương trình
10. Hàm main thực hiện chương trình.
#include <stdio.h>
#include <iostream>

// Định nghĩa số phần tử lớn nhất của mảng
#define MAX 50

// Đặt hàm cần thực hiện chức năng cụ thể vào đây.

int main()
{
	// Khai báo mảng
	int a[MAX];

	// Khai báo số lượng phần tử của mảng
	int n;

	// Nhập
	NhapMang(a, n);

	// Xuất
	printf( "\nMang vua nhap la: " );
	XuatMang(a, n);

	// Kiểm tra
	bool isToanDuong = KiemtraMang(a, n);
	if (isToanDuong) {
		printf( "\nMang toan so duong." );
	}
	else {
		printf( "\nMang co ton tai so am." );
	}

	// Tìm phần tử min, max
	printf( "\nPhan tu nho nhat trong mang la: %d", TimMin(a, n) );
	printf( "\nPhan tu lon nhat trong mang la: %d", TimMax(a, n) );

	// Sắp xếp
	printf( "\nMang sap xep tang dan: " );
	SapXepMang(a, n, true);
	XuatMang(a, n);

	printf( "\nMang sap xep giam dan: " );
	SapXepMang(a, n, false);
	XuatMang(a, n);

	// Tách mảng
	int Temp[MAX], nTemp;
	TachMang(a, n, Temp, nTemp);
	printf( "\nMang duoc tach: " );
	XuatMang(Temp, nTemp);

	// Gộp mảng
	GopMang(a, n, Temp, nTemp);
	printf( "\nMang sau khi gop: " );
	XuatMang(a, n);

	// Tìm kiếm
	int x;
	printf( "\nNhap vao so muon tim kiem: " );
	scanf_s("%d", &x);

	bool isResult = Timkiem(a, n, x);
	if (isResult) {
		printf( "Tim thay so %d trong mang.", x );
	}
	else {
		printf( "Khong tim thay so %d trong mang.", x );
	}

	// Thêm phần tử (Vị trí thêm hợp lệ: 0 -> n)
	int ViTriThem, PhanTuThem;

	do{
		printf( "\nNhap vi tri them (0 -> %d): ", n );
		scanf_s("%d", &ViTriThem);

		if (ViTriThem < 0 || ViTriThem > n)
		{
			printf( "\nVi tri them khong hop le (0 -> %d).", n );
		}
	} while (ViTriThem < 0 || ViTriThem > n);

	printf( "Nhap phan tu them: " );
	scanf_s("%d", &PhanTuThem);

	ThemPhanTu(a, n, PhanTuThem, ViTriThem);
	printf( "Mang sau khi them phan tu %d vao vi tri %d la: ", PhanTuThem, ViTriThem );
	XuatMang(a, n);

	// Xóa phần tử (Vị trí xóa hợp lệ: 0 -> n - 1)
	int ViTriXoa;

	do {
		printf("\nNhap vi tri xoa (0 -> %d): ", n - 1);
		scanf_s("%d", &ViTriXoa);

		if (ViTriXoa < 0 || ViTriXoa > (n - 1))
		{
			printf("\nVi tri xoa khong hop le (0 -> %d).", n - 1);
		}
	} while (ViTriXoa < 0 || ViTriXoa >(n - 1));

	XoaPhanTu(a, n, ViTriXoa);
	printf("Mang sau khi xoa phan tu tai vi tri %d la: ", ViTriXoa);
	XuatMang(a, n);

	system( "pause" );
	return 0;
}
Kết quả chương trình

Kết quả chương trình

Cảm ơn bạn đã theo dõi. Đừng ngần ngại hãy cùng thảo luận với chúng tôi! Minh Hoàng Blog | Nào cùng vui hehe


Giới thiệu

Minh Hoàng

Xin chào, tôi là Hoàng Ngọc Minh, hiện đang làm BrSE, tại công ty Toyota, Nhật Bản. Những gì tôi viết trên blog này là những trải nghiệm thực tế tôi đã đúc rút ra được trong cuộc sống, quá trình học tập và làm việc. Các bài viết được biên tập một cách chi tiết, linh hoạt để giúp người đọc có thể tiếp cận một cách dễ dàng nhất. Hi vọng nó sẽ có ích hoặc mang lại một góc nhìn khác cho bạn[…]

Bình luận của bạn

2 Comments cho bài viết "Các kỹ thuật trên mảng một chiều"

avatar
Sắp xếp theo:   Mới nhất | Cũ nhất | Thích nhiều nhất
trackback

[…] phần như sau các bạn làm thử trước nhé, sau khi làm xong thì theo dõi bài viết Các kỹ thuật trên mảng 1 chiều mà mình đã trình bày. Rồi cùng comment trao đổi cách làm […]

trackback

[…] Ở bài viết các kỹ thuật trên mảng 1 chiều (không sử dụng con trỏ) đã giải thích chi tiết các kỹ thuật thao tác với […]

Chúc bạn có một cuộc sống ngoại hạng!