Mảng
Các mảng có thể được phân làm hai dạng dựa
vào chiều của mảng: Mảng một chiều và mảng đa chiều. Trong bài này, chúng ta sẽ
tập trung vào cách tạo và sử dụng các mảng.
Sự sắp xếp một mảng một chiều
Mảng một chiều có thể được sử dụng để lưu trữ
một tập các giá trị có cùng kiểu dữ liệu. Xét một tập điểm của sinh viên trong
một môn học. Chúng ta sẽ sắp xếp các điểm này theo thứ tự giảm dần.
Các bước sắp xếp mảng một chiều theo thứ tự
giảm như sau:
Bước 1: Nhập vào số lượng các điểm.
Để thực hiện điều này, một biến phải được
khai báo và giá trị của biến phải được nhập. Mã lệnh như sau:
int n;
printf(“\n
Enter the total number of marks to be
entered : ”);
scanf(“%d”, &n);
Bước 2: Nhập vào tập các điểm.
Để nhập vào tập các giá trị cho một mảng,
mảng phải được khai báo. Mã lệnh như sau,
int num[100];
Số phần tử của mảng được xác định bằng giá
trị đã nhập vào biến n. n phần tử của mảng phải được khởi tạo giá trị. Để nhập
n giá trị, sử dụng vòng lặp for. Một biến nguyên cần được khai báo để sử
dụng như là chỉ số của mảng. Biến này giúp truy xuất từng phần tử của mảng. Sau
đó giá trị của các phần tử mảng được khởi tạo bằng cách nhận các giá trị nhập
vào từ người dùng. Mã lệnh như sau:
int l;
for(l
= 0; l < n; l++)
{
printf(“\n Enter the marks of student
%d : ”, l + 1);
scanf(“%d”, &num[l]);
}
Vì
các chỉ số của mảng luôn bắt đầu từ 0 nên chúng ta cần khởi tạo biến l
là 0. Mỗi khi vòng lặp được thực thi, một giá trị nguyên được gán đến một phần
tử của mảng.
Bước 3: Tạo một bản sao của mảng.
Trước khi sắp xếp mảng, tốt hơn là nên giữ lại mảng
gốc. Vì vậy một mảng khác được khai báo và các phần tử của mảng thứ nhất có thể
được sao chép vào mảng mới này. Các dòng mã lệnh sau được sử dụng để thực hiện
điều này:
int
desnum[100], k;
for(k = 0; k < n; k++)
desnum[k] =
num[k];
Bước 4: Sắp xếp mảng theo thứ tự giảm dần.
Để sắp xếp một mảng, các phần tử trong mảng
cần phải được so sánh với những phần tử còn lại. Cách tốt nhất để sắp xếp một
mảng, theo thứ tự giảm dần, là chọn ra giá trị lớn nhất trong mảng và hoán vị
nó với phần tử đầu tiên. Một khi điều này được thực hiện xong, giá trị lớn thứ
hai trong mảng có thể được hoán vị với phần tử thứ hai của mảng, phần tử đầu
tiên của mảng được bỏ qua vì nó đã là phần tử lớn nhất. Tương tự, các phần tử
của mảng được loại ra tuần tự đến khi phần tử lớn thứ n được tìm thấy. Trong
trường hợp mảng cần sắp xếp theo thứ tự tăng dần giá trị lớn nhất sẽ được hoán
vị với phần tử cuối cùng của mảng.
Quan sát ví dụ một dãy số để hiểu được giải
thuật. Hình 12.1 trình bày một mảng số nguyên cần được sắp xếp.
Để sắp xếp mảng này
theo thứ tự giảm dần,
a.
Chúng
ta cần tìm phần tử lớn nhất và hoán vị nó vào vị trí phần tử đầu tiên. Xem như
đây là lần thực hiện thứ nhất. Để đưa giá trị lớn nhất về vị trí đầu tiên,
chúng ta cần so sánh phần tử thứ nhất với các phần tử còn lại. Khi phần tử đang
được so sánh lớn hơn phần tử đầu tiên thì hai phần tử này cần phải được hoán
vị.
Khởi đầu, ở lần thực hiện đầu tiên, phần tử ở
ví trí thứ nhất được so sánh với phần tử
ở vị trí thứ hai. Hình 12.2 biểu diễn sự hoán vị tại vị trí thứ nhất.
Tiếp đó, phần tử thứ nhất được so sánh với
phần tử thứ ba. Hình 12.3 biểu diễn sự hoán vị giữa phần tử thứ nhất và phần tử
thứ ba.
Quá trình này được lặp lại cho đến khi phần
tử thứ nhất được so sánh với phần tử cuối cùng của mảng. Mảng kết quả sau lần
thực hiện đầu tiên được trình bày trong hình 12.4 bên dưới.
b.
Bỏ
qua phần tử đầu tiên, chúng ta cần tìm phần tử lớn thứ hai và hoán vị nó với
phần tử thứ hai của mảng. Hình 12.5 biểu diễn mảng sau khi được thực hiện lần
hai.
c.
Phần
tử thứ ba phải được hoán vị với phần tử lớn thứ ba của mảng. Hình 12.6 biểu
diễn mảng sau khi hoán vị phần tử lớn thứ ba.
d.
Phần
tử thứ tư phải được hoán vị với phần tử lớn thứ tư của mảng. Hình 12.7 biểu
diễn mảng sau khi hoán vị phần tử lớn thứ tư.
e.
Hình
12.7 cũng biểu diễn mảng đã được sắp xếp.
Để lập trình cho
bài toán này, chúng ta cần hai vòng lặp, một để tìm phần tử lớn nhất trong mảng
và một vòng lặp kia để lặp quá trình thực hiện n lần. Thực chất quá trình phải
lặp n-1 lần cho một phần tử của mảng bởi vì phần tử cuối cùng sẽ không còn phần
tử nào để so sánh với nó. Vì vậy, chúng ta khai báo hai biến i và j để thao tác
với hai vòng lặp for. Vòng lặp for với chỉ số i được dùng để lặp
lại quá trình xác định phần tử lớn nhất trong phần còn lại của mảng. Vòng lặp for
với chỉ số j được dùng để tìm phần tử lớn thứ i của mảng trong các phần tử từ
phần tử thứ i+1 đến phần tử cuối cùng của mảng. Theo cách đó, phần tử lớn thứ
nhất thứ i trong phần còn lại của mảng sẽ được đưa vào vị trí thứ i.
Đoạn mã lệnh khai báo chỉ số và vòng lặp thực
hiện n - 1 lần với i như là chỉ số:
int
i,j;
for(i = 0; i < n - 1; i++)
{
Đoạn mã lệnh cho vòng lặp từ phần tử thứ i +
1 đến phần tử thứ n của mảng:
for(j = i + 1; j < n;
j++)
{
Để
hoán vị hai phần tử trong mảng chúng ta cần sử dụng một biến tạm. Bởi vì đây là
thời điểm một phần tử của mảng được sao chép thành một phần tử khác, giá trị
trong phần tử thứ hai sẽ bị mất. Để tránh mất giá trị của phần tử thứ hai, giá
trị cần phải được lưu lại trong một biến tạm. Đoạn mã lệnh để hoán vị phần tử
thứ i với phần tử lớn nhất trong phần còn lại của mảng là:
if(desnum[i] < desnum[j])
{
temp =
desnum[i];
desnum[i]
= desnum[j];
desnum[j] = temp;
}
}
}
Các
vòng lặp for cần được đóng lại và vì vậy hai dấu ngoặc đóng xuất hiện trong
đoạn mã lệnh trên.
Bước 5: Hiển thị mảng đã được sắp xếp.
Chỉ số i có thể được dùng để hiển thị các giá
trị của mảng như các câu lệnh trình bày bên dưới:
for(i
= 0; i < n; i++)
printf("\n
Number at [%d] is %d", i, desnum[i]);
Theo cách đó các phần tử của một mảng được
sắp xếp. Hãy xem chương trình hoàn thiện dưới đây:
Bước 1: Gọi trình soạn thảo mà bạn có thể viết
chưong trình C.
Bước 2: Tạo một tập Gọi trình soạn thảo mà bạn có
thể viết chưong trình C.
Bước 3: Tạo một tập tin mới.
Bước 4: Đưa vào mã lệnh sau:
void main()
{
int n;
int
num[100];
int l;
int
desnum[100], k;
int i, j,
temp;
printf("\nEnter
the total number of marks to be entered : “);
scanf(“%d”,
&n);
clrscr();
for (l = 0;
l < n; l++)
{
printf(“\n
Enter the marks of student %d : ”, l + 1);
scanf(“%d”, &num[l]);
}
for(k = 0; k < n; k++)
desnum[k] = num[k];
for(i = 0; i < n - 1; i++)
{
for(j = i + 1; j < n; j++)
{
if(desnum[i] <
desnum[j])
{
temp =
desnum[i];
desnum[i]
= desnum[j];
desnum[j]
= temp;
}
}
}
for(i = 0; i < n; i++)
printf("\n Number at [%d]
is %d", i, desnum[i]);
}
Để
xem kết quả, thực hiện theo các bước liệt kê dưới đây:
Bước 1: Lưu tập tin với tên arrayI.C.
Bước 2: Biên dịch
tập tin, arrayI.C.
Bước 3: Thực thi
chương trình, arrayI.C.
Bước 4: Trở về trình
soạn thảo.
Cộng ma trận sử dụng các mảng hai chiều
Các mảng có thể có nhiều chiều. Một ví dụ tiêu biểu
của mảng hai chiều là ma trận. Một ma trận được tạo bởi các dòng và các cột.
Giao điểm của mỗi dòng và cột có một giá trị. Hình 12.10 biểu diễn một ma trận.
Số dòng và cột
trong ma trận khi được biểu diễn dạng (số dòng) x (số cột) được gọi là kích
thước của ma trận. Kích thước của ma trận trong hình 12.10 là 3x3.
Chúng ta hãy xem ví dụ cộng ma trận để hiểu cách sử
dụng của mảng hai chiều. Quan sát hai ma trận A và B trong hình 12.11.
Tổng của hai ma trận này là một ma trận khác. Nó
được tạo từ việc cộng các giá trị tại mỗi dòng và cột tương ứng. Ví dụ. phần tử
đầu tiên C(1,1) trong ma trận C sẽ là tổng của A(1,1) và B(1,1). Phần tử thứ
hai C(1,2) sẽ là tổng của A(1,2) và B(1,2) ... Một qui luật quan trọng trong
việc cộng các ma trận là kích thước của các ma trận phải giống nhau. Nghĩa là,
một ma trận 2x3 chỉ có thể được cộng với một ma trận 2x3. Hình 12.12 Biểu diễn
ma trận A, B và C.
Để lập trình công việc này,
Bước 1: Khai báo hai
mảng. Mã lệnh như sau,
int
A[10][10], B[10][10], C[10][10];
Bước 2: Nhập vào
kích thước của các ma trận. Mã lệnh là,
int
row,col;
printf(“\n
Enter the dimension of the matrix : “);
scanf(“%d %d”,&row,&col);
Bước 3: Nhập các giá
trị cho ma trận A và B.
Các giá trị của ma trận được nhập theo dòng. Trước
tiên các giá trị của dòng thứ nhất được nhập vào. Kế đến các giá trị của dòng
thứ hai được nhập, ... Bên trong một dòng, các giá trị của cột được nhập tuần
tự. Vì vậy cần hai vòng lặp để nhập các giá trị của một ma trận. Vòng lặp thứ
nhất đi qua từng dòng một, trong khi vòng lặp bên trong sẽ đi qua từng cột.
Đoạn mã lệnh
như sau:
printf(“\n
Enter the values of the matrix A and B : \n”);
int i, j;
for(i = 0; i < row; i++)
for(j = 0; j < col; j++)
{
print(“A[%d,%d], B[%d,%d]:“, row, col, row, col);
scanf(“%d
%d”, &A[i][j], &B[i][j]);
}
Bước 4: Cộng hai ma
trận. Hai ma trận có thể được cộng bằng cách sử dụng đoạn mã lệnh sau,
C[i][j] = A[i][j] + B[i][j];
Chú ý, dòng lệnh này cần đặt ở vòng lặp bên trong
của đoạn lệnh đã nói ở trên. Một cách khác, hai vòng lặp có thể được viết lại
để cộng ma trận.
Bước 5: Hiển thị ba
ma trận. Mã lệnh sẽ như sau,
for(i = 0; i < row; i++)
for(j = 0;j
< col; j++)
{
printf(“\nA[%d,%d]=%d, B[%d,%d] = %d, C[%d,%d]=%d \n“,
i, j, A[i][j], i, j, B[i][j], i, j, C[i][j]);
}
Bên dưới là chương trình hoàn chỉnh.
Bước 1: Tạo một tập
tin mới.
Bước 2: Đưa vào mã
lệnh sau:
void main()
{
int A[10][10], B[10][10], C[10][10];
int
row, col;
int
i,j;
printf(“\n
Enter the dimension of the matrix : “);
scanf(“%d
%d”, &row, &col);
printf(“\nEnter
the values of the matrix A and B: \n”); for(i
= 0; i < row; i++)
for(j
= 0; j < col; j++)
{
printf(“\n
A[%d,%d], B[%d,%d]: “, i, j, i, j);
scanf(“%d
%d”, &A[i][j], &B[i][j]);
C[i][j]
= A[i][j] + B[i][j];
}
for(i = 0; i < row; i++)
for(j
= 0; j < col; j++)
{
printf(“\nA[%d,%d]=%d,
B[%d,%d]=%d, C[%d,%d]=%d\n“,
i,
j, A[i][j], i, j, B[i][j], i, j, C[i][j]);
}
}
Bước 3: Lưu tập tin
với tên arrayII.C.
Bước 4: Biên dịch
tập tin, arrayII.C.
Bước 5: Thực thi
chương trình arrayII.C.
Bước 6: Trở về trình
soạn thảo.
Đăng nhận xét