Bài 12: Mảng [Thực Hành]
Mục tiêu:
Kết thúc bài học này, bạn có thể:
Ø Sử dụng mảng một chiều
Ø Sử dụng mảng hai chiều.
Các bước trong bài học này được trình bày chi tiết, rõ ràng và cẩn
thận. Điều này giúp ta hiểu rõ về công cụ lập trình. Thực hiện theo các bước
sau thật cẩn thận.
Phần I – Trong thời gian 1 giờ 30 phút đầu:
12.1 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.
12.1.1 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:
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);
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[n];
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.
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];
4. Sắp xếp mảng theo thứ tự
giảm dần.
Để sắp xếp một mảng, có rất nhiều thuật toán khác nhau như: Sắp xếp nổi bọt, sắp xếp chèn, sắp xếp chọn, sắp xếp trộn, sắp xếp vun đống, sắp xếp nhanh... mỗi thuận toán đều có ưu điểm riêng, trong đó thuật toán sắp xếp chọn là một phương pháp khá đơn giản, dễ hiểu, ta sẽ sử dụng thuật toán này để sắp xếp.
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:
Hình 12.1: Mảng num với chỉ số i (5 phần tử)
Để 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.
Hình 12.2: Đảo vị trí phần tử thứ nhất với phần tử thứ hai
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.
Hình 12.3 Đảo vị trí phần tử thứ nhất với 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.
Hình 12.4: Mảng sau lần thực hiện đầu tiên
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.
Hình 12.5: Mảng sau lần thực hiện thứ 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.
Hình 12.6: Mảng sau lần thực hiệ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ư.
Hình 12.7: Mảng sau lần thực hiệ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.
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.
1. Gọi
trình soạn thảo C.
2. Tạo
một tập tin mới.
3. Đưa vào mã lệnh sau:
#include<stdio.h>
#include<conio.h>
main()
{
int n;
int
num[100];
int l;
int
desnum[100], k;
int i, j,
temp;
printf("Enter
the total number of marks to be entered : ");
scanf("%d",
&n);
for (l = 0;
l < n; l++)
{
printf("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]);
getch();
}
4. Biên
dịch và thực thi chương trình.
Một ví dụ về kết quả thực thi
của chương trình:
12.1.2 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.8
biểu diễn một ma trận.
Hình 12.8 : Ma trận A
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.9.
Hình 12.9 : Ma trận A và B
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.10 Biểu diễn ma trận A, B và C.
Hình 12.10 : Ma trận A, B và C
Để lập trình công việc này:
1. Khai báo hai mảng. Mã lệnh
như sau:
int A[10][10], B[10][10], C[10][10];
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);
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]);
}
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.
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.
1. Tạo một tập tin mới.
2. Đưa vào mã lệnh sau:
#include<stdio.h>
#include<conio.h>
main()
{
int A[10][10], B[10][10], C[10][10];
int row, col;
int i,j;
printf("Enter the dimension of the
matrix : ");
scanf("%d %d", &row, &col);
printf("Enter the values of the matrix
A and B: \n"); for(i = 0; i < row; i++)
for(j = 0; j < col; j++)
{
printf(" 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("A[%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]);
}
getch();
}
3. Biên
dịch và thực thi chương trình.
Một ví dụ về kết quả thực
thi của chương trình:
Phần II – Trong thời gian 30 phút kế tiếp:
1. Viết một chương trình C nhập
một tập hợp số vào trong một mảng và đảo ngược mảng.
Để thực hiện điều này:
a. Khai báo hai mảng.
b. Nhập các giá trị vào một
mảng.
c. Thực hiện vòng lặp
theo thứ tự ngược trên mảng này để sao chép các giá trị vào mảng thứ hai. Dùng
một chỉ số khác cho mảng thứ hai, chỉ số này chạy từ 0.
Bài tập tự làm
1. Viết một chương trình C để
tìm giá trị nhỏ nhất và giá trị lớn nhất trong một mảng.
2. Viết một chương trình để đếm
số lượng nguyên âm và phụ âm trong một từ.
0 nhận xét:
Đăng nhận xét