=
=

Bài 6: Mảng

Nội dung bài học

  1. Giới thiệu kiểu dữ liệu mảng
  2. Mảng 1 chiều
  3. Mảng đa chiều

I. Giới thiệu kiểu dữ liệu mảng

Là tập hợp các phần tử có cùng dữ liệu. Giả sử bạn muốn lưu n số nguyên để tính trung bình, bạn không thể khai báo n biến để lưu n giá trị rồi sau đó tính trung bình. Ví dụ 1 : bạn muốn tính trung bình 10 số nguyên nhập vào từ bàn phím, bạn sẽ khai báo 10 biến: a, b, c, d, e, f, g, h, i, j có kiểu int và lập thao tác nhập cho 10 biến này như sau:

printf("Nhap vao bien a:");
scanf("%d", &a);

10 biến bạn sẽ thực hiện 2 lệnh trên 10 lần, sau đó tính trung bình: (a + b + c + d + e + f + g + h + i + j)/10

Điều này chỉ phù hợp với n nhỏ, còn đối với n lớn thì khó có thể thực hiện được. Vì vậy khái niệm mảng được sử dụng.

II. Mảng 1 chiều

II.1. Cách khai báo mảng
KieuDLptu Tenmang[sopt];
Ví dụ:
int ia[10];

với int là kiểu mảng (KieuDLptu), ia là tên mảng (Tenmang), 10 số phần tử mảng (sopt).

Ý nghĩa: Khai báo một mảng số nguyên gồm 10 phần tử, mỗi phần tử có kiểu int.

Tham chiếu đến từng phần tử mảng

Sau khi mảng được khai báo, mỗi phần tử trong mảng đều có chỉ số để tham chiếu. Chỉ số bắt đầu từ 0 đến n-1 (với n là kích thước mảng). Trong ví dụ trên, ta khai báo mảng 10 phần tử thì chỉ số bắt đầu từ 0 đến 9. 0 1 2 3 4 5 6 7 8 9

Cách tham chiếu: Tên mảng [chỉ số]. Ví dụ ia[0] là phần tử thứ nhất, ia[1] là phần tử thứ hai,...

II.2. Nhập dữ liệu cho mảng

Dữ liệu có thể được gán đến mảng khi khai báo mảng theo cú pháp:

KieuDLptu Tenmang[sopt] = {pt_1, pt_2,...,pt_sopt};

Ví dụ:

int ia[5] = {7, 5, 15, 3, 8};

Có thể dùng vòng lặp để gán dữ liệu đến mảng như ví dụ sau:

for (i = 0; i < 10; i++) //vòng for có giá trị i chạy từ 0 đến 9
{
   printf("Nhap vao phan tu thu %d: ", i + 1);
   scanf("%d", &ia[i]);
}
II.3. Đọc dữ liệu từ mảng

Dữ liệu từ mảng có thể được đọc thông qua cách tham chiếu mảng: Tên mảng [chỉ số]. Ví dụ ia[0] là phần tử thứ nhất, ia[1] là phần tử thứ hai,...

for(i = 0; i > 10; i++)
   printf("%3d ", ia[i]);

Ví dụ: Chương trình tính trung bình cộng của n số nguyên cho trước.

Nhập giá trị n và kế tiếp nhập n số nguyên bất kỳ cách nhau bởi khoảng trắng vào ô Stdin Inputs. Ví dụ nhập 3 1 1 2 nghĩa là n = 3 và các phần tử mảng lần lượt là 1, 1, 2. Nhấn nút Execute màu xanh để xem kết quả.

☛ Bài tập:
  • Từ ví dụ trên, nhấn dòng liên kết Edit this program in JDoodle.com để truy cập trang chủ JDoodle.
  • Thay đổi chương trình trên để hiển thị ra màn hình phần tử có giá trị lớn nhất của mảng.
  • Lưu đến tài khoản cá nhân trên JDoodle.
II.4. Mảng và tham số của hàm

Khi truyền mảng sang hàm, không tạo bản sao mảng mới. Vì vậy mảng truyền sang hàm có dạng tham biến. Nghĩa là giá trị của các phần tử trong mảng sẽ bị ảnh hưởng nếu có sự thay đổi trên chúng.

Ví dụ 1: Chương trình tìm số lớn nhất dùng hàm

Nhập n số nguyên bất kỳ cách nhau bởi khoảng trắng vào ô Stdin Inputs. Ví dụ nhập 3 10 7 2. Nhấn nút Execute màu xanh để xem kết quả.

Chương trình ban đầu hàm max có hai tham số truyền vào và kết quả trả về là giá trị max có kiểu nguyên, một tham số là mảng 1 chiều kiểu int và một tham số có kiểu int. Với chương trình sau khi sửa hàm max chỉ còn một tham số truyền vào nhưng cho kết quả như nhau.

Ví dụ 2: Chương trình tìm số lớn nhất dùng hàm max chỉ có một tham số

Nhập n số nguyên bất kỳ cách nhau bởi khoảng trắng vào ô Stdin Inputs. Ví dụ nhập 3 10 7 2. Nhấn nút Execute màu xanh để xem kết quả.

Do sau khi sửa chương trình mảng ia[MAX] được khai báo lại là biến toàn cục nên hàm max không cần truyền tham số mảng vào cũng có thể sử dụng được. Tuy vậy, khi lập trình bạn nên viết như chương trình theo ví dụ 1 là truyền tham số mảng vào (dạng tổng quát) để hàm max có thể thực hiện được trên nhiều mảng khác nhau. Còn với chương trình sửa lại bạn chỉ sử dụng hàm max được với mảng a mà thôi.

☛ Bài tập:
  • Từ ví dụ 1, nhấn dòng liên kết Edit this program in JDoodle.com để truy cập trang chủ JDoodle.
  • Thay đổi hàm max trả về một vị trí mà giá trị tại vị trí đó là giá trị lớn nhất trong mảng.
  • Lưu đến tài khoản cá nhân trên JDoodle.
II.5. Sắp xếp mảng

Trong thực tế ta thường gặp những công việc cần phải sắp xếp theo một thứ tự nào đó, chẳng hạn danh sách học sinh trong lớp có thể được sắp xếp theo Họ hoặc Điểm trung bình. Việc sắp xếp thứ tự 1 mảng giúp ta dễ dàng tìm kiếm các phần tử của mảng.

Phần dưới đây trình bày hai giải thuật sắp xếp thường được sử dụng nhiều nhất đó là phương pháp nổi bọt (Bubble sort) và sắp xếp nhanh (QuickSort). Chúng ta sẽ gặp lại và tìm hiểu kỹ hơn về các thuật toán này trong môn học Cấu trúc dữ liệu và Giải thuật.

Phương pháp nổi bọt (Bubble sort)

Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy số bằng cách lặp lại công việc đổi chỗ 2 số liên tiếp nhau nếu chúng đứng sai thứ tự (số sau bé hơn số trước với trường hợp sắp xếp tăng dần) cho đến khi dãy số được sắp xếp.

Ví dụ minh họa: Giả sử chúng ta cần sắp xếp dãy số [5 1 4 2 8] này tăng dần.

Lần lặp đầu tiên:

( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ) So sánh hai phần tử đầu tiên, và đổi chỗ cho nhau do 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ) Đổi chỗ do 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ) Đổi chỗ do 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) Hai phần tử đang xét đã đúng thứ tự (8 > 5), vậy ta không cần đổi chỗ.

Lần lặp thứ 2:

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ) Đổi chỗ do 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Bây giờ, dãy số đã được sắp xếp, Nhưng thuật toán của chúng ta không nhận ra điều đó ngay được. Thuật toán sẽ cần thêm một lần lặp nữa để kết luận dãy đã sắp xếp khi và khi khi nó đi từ đầu tới cuối mà không có bất kỳ lần đổi chỗ nào được thực hiện.

Lần lặp thứ 3:

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Ví dụ chương trình sau đây sắp xếp và hiển thị dãy số nguyên cho trước.

Nhấn nút Execute màu xanh để xem kết quả.

Đánh giá độ phức tạp thuật toán thuật toán sắp xếp nổi bọt

Thuật toán QuickSort - Sắp xếp nhanh

Thuật toán sắp xếp QuickSort là một thuật toán chia để trị (Divide and Conquer algorithm). Nó chọn một phần tử trong mảng làm điểm đánh dấu (pivot). Thuật toán sẽ thực hiện chia mảng thành các mảng con dựa vào pivot đã chọn. Việc lựa chọn pivot ảnh hưởng rất nhiều tới tốc độ sắp xếp. Nhưng máy tính lại không thể biết khi nào thì nên chọn theo cách nào. Dưới đây là một số cách để chọn pivot thường được sử dụng:

Tầm quan trọng của phân đoạn trong thuật toán QuickSort

Mấu chốt chính của thuật toán QuickSort là việc phân đoạn dãy số (Xem hàm partition()). Mục tiêu của công việc này là: Cho một mảng và một phần tử x là pivot. Đặt x vào đúng vị trí của mảng đã sắp xếp. Di chuyển tất cả các phần tử của mảng mà nhỏ hơn x sang bên trái vị trí của x, và di chuyển tất cả các phần tử của mảng mà lớn hơn x sang bên phải vị trí của x.

Khi đó ta sẽ có 2 mảng con: mảng bên trai của x và mảng bên phải của x. Tiếp tục công việc với mỗi mảng con (chọn pivot, phân đoạn) cho tới khi mảng được sắp xếp.

Thuật toán phân đoạn

Đặt pivot là phần tử cuối cùng của dãy số arr. Chúng ta bắt đầu từ phần tử trái nhất của dãy số có chỉ số là left, và phần tử phải nhất của dãy số có chỉ số là right -1(bỏ qua phần tử pivot). Chừng nào left < right mà arr[left] > pivot và arr[right] < pivot thì đổi chỗ hai phần tử left và right. Sau cùng, ta đổi chỗ hai phần tử left và pivot cho nhau. Xem hình minh họa phía dưới. Khi đó, phần tử left đã đứng đúng vị trí và chia dãy số làm đôi (bên trái và bên phải)

Code minh họa thuật toán phân đoạn

int partition (int arr[], int low, int high)
{
   int pivot = arr[high]; // pivot
   int left = low;
   int right = high - 1;
   while(true) {
      while(left <= right && arr[left] < pivot) left++; // Tìm phần tử >= arr[pivot]
      while(right >= left && arr[right] > pivot) right--; // Tìm phần tử <= arr[pivot]
      if (left >= right) break; // Đã duyệt xong thì thoát vòng lặp
      swap(&arr[left], &arr[right]); // Nếu chưa xong, đổi chỗ.
      left++; // Vì left hiện tại đã xét, nên cần tăng
      right--; // Vì right hiện tại đã xét, nên cần giảm
   }
   swap(&arr[left], &arr[high]);
   return left; // Trả về chỉ số sẽ dùng để chia đổi mảng
}

Ví dụ cho quá trình phân đoạn

arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes: 0 1 2 3 4 5 6

pivot = 6, left = 0, right = 5

arr[left] = 10 < arr[pivot] = 70 và left <= right, left = 1
arr[left] = 80 > arr[pivot] = 70, tạm dừng

arr[right] = 50 < arr[pivot] = 70, tạm dừng

Do left < right, đổi chỗ arr[left], arr[right]
arr[] = {10, 50, 30, 90, 40, 80, 70}
left = 2, right = 4

arr[left] = 30 < arr[pivot] = 70 và left <= right, left = 3
arr[left] = 90 > arr[pivot] = 70, tạm dừng

arr[right] = 40 < arr[pivot] = 70, tạm dừng

Do left < right, đổi chỗ arr[left], arr[right]
arr[] = {10, 50, 30, 40, 90, 80, 70}
left = 4, right = 3

// Do left >= right
arr[] = {10, 50, 30, 40, 70, 80, 90}. // Đổi chỗ arr[left] và arr[pivot]

Bây giờ, 70 đã nằm đúng vị trí, các phần từ <= 70 nằm phía trước và lớn hơn 70 nằm phía sau.

Quy trình của thuật toán sắp xếp quick sort

Mã hàm quickSort

void quickSort(int arr[], int low, int high)
{
   if (low < high)
   {
      /* pi là chỉ số nơi phần tử này đã đứng đúng vị trí
      và là phần tử chia mảng làm 2 mảng con trái & phải */
      int pi = partition(arr, low, high);
      // Gọi đệ quy sắp xếp 2 mảng con trái và phải
      quickSort(arr, low, pi - 1);
      quickSort(arr, pi + 1, high);
   }
}

Ví dụ chương trình sau đây sắp xếp tăng dần và hiển thị dãy số nguyên cho trước.

Nhấn nút Execute màu xanh để xem kết quả.

II.6. Gán giá trị từ mảng sang mảng

Hai mảng A và B có cùng kiểu thành phần (các phần tử mảng có cùng kiểu dữ liệu) có thể chuyển giá trị cho nhau bằng hàm memmove, cú pháp như sau:

memmove(b, a, sizeof(a))

a: Tên mảng nguồn; b: Tên mảng đích; sizeof(a): Số phần tử chép.

Hàm này thuộc thư viện string.h.

Ví dụ chương trình sau đây chuyển các giá trị từ mảng a cho trước sang mảng b.

Nhấn nút Execute màu xanh để xem kết quả.

III. Mảng đa chiều

Trong lập trình C, bạn có thể tạo một mảng mảng. Các mảng này được gọi là mảng đa chiều. Khai báo tổng quát của một mảng đa chiều:

kieu_du_lieu ten_mang[kichco_1][kichco_2]...[kichco_N];

Ví dụ khai báo mảng 2 chiều:

float x[3][4];

Ở đây, x là một mảng hai chiều (2d). Mảng có thể chứa 12 phần tử. Bạn có thể nghĩ rằng mảng như một bảng có 3 hàng (row) và mỗi hàng có 4 cột (column) như hình ảnh sau:

Tương tự, bạn có thể khai báo một mảng ba chiều (3d). Ví dụ:

float y[2][4][3];

Ở đây, mảng y có thể chứa 24 phần tử.

Nhập xuất mảng đa chiều

Tương tự mảng 1 chiều, mảng đa chiều cũng có thể được nhập trực tiếp hay từ bàn phím (thông qua cấu trúc lặp).

Ví dụ khởi tạo mảng 2 chiều

int c[2][3] = {{1, 3, 0}, {-1, 5, 9}};
int c[][3] = {{1, 3, 0}, {-1, 5, 9}};
int c[2][3] = {1, 3, 0, -1, 5, 9};

Ví dụ khởi tạo mảng 3 chiều

int a[2][3][4] = {
  {{3, 4, 2, 3}, {0, -3, 9, 11}, {23, 12, 23, 2}},
  {{13, 4, 56, 3}, {5, 9, 3, 5}, {3, 1, 4, 9}}};

Ví dụ nhập mảng 2 chiều từ bàn phím và hiển thị ra màn hình

// Chương trình C lưu trữ nhiệt độ (nhietdo) của 2 thành phố (THANHPHO) trong
// 1 tuần (TUAN) và hiển thị theo từng ngày (NGAY) trong tuần.
#include <stdio.h>
const int THANHPHO = 2;
const int TUAN = 7;
int main()
{
  int nhietdo[THANHPHO][TUAN];
  // lưu trữ giá trị trong mảng 2 chiều
  for (int i = 0; i < THANHPHO; ++i)
  {
     for (int j = 0; j < TUAN; ++j)
     {
        printf("Thanh pho %d, Ngay %d: ", i + 1, j + 1);
        scanf("%d", &nhietdo[i][j]);
     }
  }
  printf("\nHien thi cac gia tri: \n\n");
  // Hiển thị các giá trị dùng vòng lặp
  for (int i = 0; i < THANHPHO; ++i)
  {
     for (int j = 0; j < TUAN; ++j)
     {
        printf("Thanh pho %d, Ngay %d = %d\n", i + 1, j + 1, nhietdo[i][j]);
     }
  }
  return 0;
}

Kết quả:

Thanh pho 1, Ngay 1: 33
Thanh pho 1, Ngay 2: 34
Thanh pho 1, Ngay 3: 35
Thanh pho 1, Ngay 4: 33
Thanh pho 1, Ngay 5: 34
Thanh pho 1, Ngay 6: 32
Thanh pho 1, Ngay 7: 31
Thanh pho 2, Ngay 1: 28
Thanh pho 2, Ngay 2: 27
Thanh pho 2, Ngay 3: 22
Thanh pho 2, Ngay 4: 32
Thanh pho 2, Ngay 5: 32
Thanh pho 2, Ngay 6: 33
Thanh pho 2, Ngay 7: 31
Hien thi cac gia tri:
Thanh pho 1, Ngay 1: 33
Thanh pho 1, Ngay 2: 34
Thanh pho 1, Ngay 3: 35
Thanh pho 1, Ngay 4: 33
Thanh pho 1, Ngay 5: 34
Thanh pho 1, Ngay 6: 32
Thanh pho 1, Ngay 7: 31
Thanh pho 2, Ngay 1: 28
Thanh pho 2, Ngay 2: 27
Thanh pho 2, Ngay 3: 22
Thanh pho 2, Ngay 4: 32
Thanh pho 2, Ngay 5: 32
Thanh pho 2, Ngay 6: 33
Thanh pho 2, Ngay 7: 31

Mảng đa chiều trong C là chủ đề phức tạp và đa dạng. Người học có thể tham khảo thêm về chủ đề này từ Nguồn tham khảo.