Chương 4
Mảng & các giải thuật với mảng
Đặt vấn đề

Trong rất nhiều bài toán chúng ta cần thao tác
trên một dãy (hoặc một bảng, ) gồm hữu hạn
các phần tử cùng kiểu. Chẳng hạn:
-
một lớp học: có các phần tử là sinh viên.
-
một ma trận: có các phần tử là số thực.

Khi đó cần có các cấu trúc dữ liệu phù hợp, đó
chính là mảng.

Mảng là dãy hữu hạn, có thứ tự các phần tử
có cùng một kiểu dữ liệu.

Mảng có thể có 1 hoặc nhiều chiều.
Đặt vấn đề (tt)
sv[0] sv[0]
sv[k]
Thông tin về sinh viên được lưu trữ trong một phần tử
dãy sinh viên
2 0 1 4
4 5 10 3
0 9 6 0
ma trận
Khai báo mảng

Ví dụ:


Ví dụ 1: Giả sử có int a[10], b[3][4];
khi đó:
-
để truy xuất đến phần tử thứ i của a ta dùng
cú pháp sau: a[i]
-
tương tự: cú pháp b[i][j] để truy xuất đến phần
tử ở dòng i, cột j của ma trận b.
<tênbiếnmảng>[chỉ số1] [chỉ sốk]
Truy xuất mảng (tt)

Ví d
ụ
2: Hàm sau
đ
ây s
ẽ
nh
ậ
p d
ữ
li
ệ
u cho m
ả
ng n s
ố
nguyên (gi
ả

scanf(“%d”,&a[i]);
}
}
Khai báo hình thức
(không cần chỉ rõ kích thước)
Mảng và con trỏ (tt)

Ví d
ụ
2: hàm in ma tr
ậ
n b, n dòng, m c
ộ
t ra màn hình
(gi
ả
s
ử b đượ
c khai báo s
ố
c
ộ
t là 10).
void inMT(int b[][10], int n, int m)
{
int i,j;
for(i=0;i<n;++i)
{
for(j=0;j<m;++j)printf(“%5d”,a[i][j]);
printf(“\n”);//xu

m
ả
ng.

Ví d
ụ
1:
void nhapDL(int *p, int n)
{
int i;
for(i=0;i<n;++i)
{
printf(“\nphan tu thu %d = “,i);
scanf(“%d”,p+i);
}
}
Mảng và con trỏ (tt)
 Giải thích:
int x[100], n;

lời gọi hàm nhập dữ liệu sẽ có dạng:
nhapDL(x,n);

Suy ra:
p=x=&x[0]
p+i = &x[i]
*(p+i) = x[i]
p[i] = x[i]
Mảng và con trỏ (tt)


Các giải thuật trên mảng (tt)
 Giải thích:
i=0 t=0+a[0]=2
i=1 t=2
i=2 t=2+a[2]=3
i=3 t=3+a[3]=7
i=4 t=7
i=5 t=7+a[5]=9
i=6 t=9
i=7 t=9+a[7]=10
2 0 1 4 -3 2 -8 1
0 1 2 3 4 5 6 7
Các giải thuật trên mảng (tt)
 Tìm max-min:
 Cho mảng a, n số nguyên. Hãy tìm chỉ
số của phần tử lớn nhất.
int max(int *p, int n)
{
int i,m=0;
for(i=1;i<n;++i)
if(p[m]<p[i])m=i;
return m;
}
Các giải thuật trên mảng (tt)
 Giải thích:
2 0 1 4 -3 2 -8 1
0 1 2 3 4 5 6 7
i=0
i=1
i=2

i=0
i=1
i=2
x!=a[0]
x!=a[1]
x=a[2]
x=1
Các giải thuật trên mảng (tt)
 Sắp xếp:
 Cho dãy a, n số nguyên. Yêu cầu sắp
xếp các phần tử của dãy theo thứ tự
tăng dần.
 Ở đây trình bày 2 phương pháp sắp xếp:
- Phương pháp chọn (selection).
- Phương pháp hoán đổi trực tiếp
(interchange).
Phương pháp sắp xếp chọn

Bước 0: Tìm phần tử min trong các phần tử
a[0] -> a[n-1] rồi hoán vị min với a[0].

Bước 1: Tìm phần tử min trong các phần tử
a[1] -> a[n-1] rồi hoán vị min với a[1].



Bước i: Tìm phần tử min trong các phần tử a[i]
-> a[n-1] rồi hoán vị min với a[i].



-8 -3 0 1 1 2 2 4
0 1 2 3 4 5 6 7
trước khi hoán vị sau khi hoán vị
Minh họa:
Phương pháp sắp xếp chọn (tt)
void selection(int a[], int n)
{
int i,j,t,m;
for(i=0;i<n-1;++i)
{
m=i;
for(j=i+1;j<n;++j)
if(a[m]>a[j])m=j;
if(m!=i)
{
t=a[m];
a[m]=a[i];
a[i]=t;
}
}
}
Cài đặt
Phương pháp interchange
 Tư tưởng: tượng tự phương pháp
selection. Nhưng tại mỗi bước thay vì
hoán vị a[i] với phần tử min tìm được thì
a[i] sẽ được hoán vị lần lượt với các
phần tử nhỏ hơn nó để cuối cùng a[i]
chính là min.
Phương pháp interchange (tt)

0 1 2 3 4 5 6 7
Minh họa:
Phương pháp interchange (tt)
void interchange(int a[], int n)
{
int i,j,t;
for(i=0;i<n-1;++i)
for(j=i+1;j<n;++j)
if(a[i]>a[j])
{
t=a[i];
a[j]=a[i];
a[i]=t;
}
}
Cài đặt
Ví dụ về mảng 2 chiều
 Ví dụ 1: Cho ma trận nguyên A, n dòng,
m cột. Hãy viết các hàm:
- Tính tổng các phần tử dương của A.
- Đếm số phần tử trên đường chéo chính
là số nguyên tố.
- Tìm phần tử max của mảng.
Ví dụ về mảng 2 chiều (tt)
//hàm tính tổng các phần tử dương:
int tongDuong(int *p, int n, int m, int M)
{
int i,j,t=0;
for(i=0;i<n;++i)
for(j=0;j<m;++j)

}
return *(p+M*d+c);
}
Hỏi đáp