Bài giảng Giới thiệu lập trình - Cấu trúc mảng - Lê Nguyên Khôi

Giới Thiệu Lập Trình
Cấu Trúc Mảng
TS. Lê Nguyên Khôi
Trường Đại học Công nghệ, ĐHQGHN
Nội Dung
1

 Khái niệm chung

 Truyền mảng vào hàm

 Lập trình với mảng
Giới Thiệu Lập Trình
Đặt Vấn Đề
2

 Kiến thức về kiểu và biến không đủ để biểu 
diễn, xử lý những kiểu dữ liệu phức tạp, ví dụ:

 Danh sách điểm thi của một sinh viên

 Danh sách sinh viên của lớp học

 Cần lưu trữ và xử lý một chuỗi dữ liệu cùng kiểu

 Sắp xếp, tìm kiếm, tính toán trên chuỗi dữ liệu

 Ngôn ngữ lập trình (C++) cung cấp các kiểu dữ 
liệu có cấu trúc để xử lý các vấn đề trên

 Trong đó mảng là cấu trúc dữ liệu thông dụng nhất

 Mảng dùng để lưu trữ dữ liệu cùng kiểu
Giới Thiệu Lập Trình
Khái Niệm Chung
3

 Mảng một chiều là chuỗi dữ liệu có cùng kiểu

 Đặt tại các ô nhớ liên tiếp trong bộ nhớ

 Mỗi phần tử mảng có một chỉ số riêng biệt

 Sử dụng chỉ số để định vị & truy cập phần tử

 Ví dụ: điểm thi 5 môn của sinh viên lưu trữ 
trong mảng có 5 phần tử (mảng diemSo)

 Mảng trên có 5 phần tử, lưu dữ liệu kiểu int, 
chỉ số bắt đầu từ 0 đến 4
Giới Thiệu Lập Trình
Chỉ số 0 1 2 3 4
Dữ liệu 45 60 77 72 83
Khái Niệm Chung
4

 Các phần tử của mảng có thể coi là biến số tên 
diemSo[0], diemSo[1], diemSo[2], diemSo[3], 
diemSo[4], có kiểu dữ liệu int

 Chỉ số phần tử đặt trong ngoặc vuông ([])

 Truy cập phần tử mảng, sử dụng:

 Tên mảng (diemSo)

 Và chỉ số phần tử là một giá trị nguyên hay biểu thức 
giá trị nguyên
Giới Thiệu Lập Trình
Chỉ số 0 1 2 3 4
Dữ liệu 45 60 77 72 83
Truy Cập Mảng
5

 Sử dụng tên mảng và chỉ số phần tử
Giới Thiệu Lập Trình
Chỉ số 0 1 2 3 4
Dữ liệu 45 60 77 72 83
diemSo[2] = 74; // 77 -> 74
// với i=1, câu lệnh sau -> diemSo[3] = 75
diemSo[i+2] = 75; // 72 -> 75
// thực hiện tính toán
tb = (diemSo[2] + diemSo[3]) / 2;
//in ra 45 và 83
cout << diemSo[0] << " " << diemSo[4];
Khai Báo
6

 Mảng phải được khai báo trước khi sử dụng

 Khi khai báo phải quy định số phần tử mảng

 Cú pháp:
KiểuDL TênMảng [SốPhầnTử];

 Ví dụ:
int diemSo[5];

 Khai báo một mảng có tên diemSo, có 5 phần tử, 
lưu trữ giá trị kiểu int

 Lưu ý:

 Số phần tử của mảng không được thay đổi
Giới Thiệu Lập Trình
Nhập Dữ Liệu
7

 Mảng sau khi khai báo, có thể được nhập dữ 
liệu, và thực tiện tính toán trên dữ liệu mảng
Giới Thiệu Lập Trình
const int SO_MON_HOC = 5;
int main()
{
int diemSo[SO_MON_HOC];
double tongDiem = 0.0;
for (int i = 0; i < SO_MON_HOC; i++) {
cin >> diemSo[i];
tongDiem += diemSo[i];
}
cout << "diem trung binh: "
<< tongDiem / SO_MON_HOC;
}
Khởi Tạo
8

 Mảng có thể được khởi tạo như sau:
int diemSo[5] = {45, 60, 77, 72, 83};

 Lưu ý: số giá trị trong danh sách khởi tạo (trong {}) 
không được vượt quá kích thước mảng (trong [])

 Mảng cũng có thể được khởi tạo như sau:
int diemSo[] = {45, 60, 77, 72, 83};

 C++ sẽ tự xác định độ dài của mảng dựa trên độ dài 
của danh sách khởi tạo

 Mảng không được khởi tạo, phần tử mảng có 
giá trị không xác định (giống biến)
Giới Thiệu Lập Trình
Ứng Dụng
9

 Thống kê số lần ra mặt giá trị từ 1 đến 6, sau 
6000 lần tung xúc xắc
Giới Thiệu Lập Trình
int main(){
const int SO_MAT = 6;
int dem[SO_MAT + 1] = { 0 };
for (int t = 0; t < 6000; t++) {
int mat = 1 + rand() % SO_MAT;
dem[mat]++;
}
for (int m = 1; m <= SO_MAT; m++) {
cout << m << "\t" << dem[m] << "\n";
}
return 0;
}
Quản Lý Chỉ Số Phần Tử
10

 Khai báo mảng có kích thước SốPhầnTử, chỉ 
số các phần tử từ 0 đến SốPhầnTử - 1 

 Tất cả các chỉ số khác không hợp lệ

 Truy cập vào các chỉ số không hợp lệ, ví dụ 
diemSo[-1], diemSo[SO_MON_HOC]:

 Truy cập ra vùng bộ nhớ ngoài mảng

 Không gây lỗi cú pháp (lỗi dịch)

 Có thể gây lỗi khi chạy chương trình

 Chương trình chạy sai

 Dừng đột ngột

 Lập trình viên có trách nhiệm kiểm soát giá trị chỉ số
Giới Thiệu Lập Trình
Truyền Mảng Cho Hàm
11

 Dùng tên mảng làm tham số truyền cho hàm

 Mảng được truyền theo kiểu tham chiếu, nhưng không 
sử dụng toán tử &

 Hàm thay đổi giá trị trong mảng, kết thúc hàm, mảng 
thay đổi
Giới Thiệu Lập Trình
void nhapMang(int diemSo[]) {
for (int i = 0; i < SO_MON_HOC; i++)
cin >> diemSo[i];
}
int main() {
int diemSo[SO_MON_HOC];
nhapMang(diemSo);
return 0;
}
Truyền Mảng Cho Hàm
12

 Nếu không muốn hàm thay đổi giá trị trong mảng, sử 
dụng khai báo hằng số trong chữ ký hàm đối với mảng

 Thay đổi giá trị phần tử mảng (gán, nhập) gây lỗi dịch
Giới Thiệu Lập Trình
double dtb(const int diemSo[], int soPT) {
double tong = 0.0; 
for (int i = 0; i < soPT; i++)
tong += diemSo[i];
return (tong / soPT);
}
int main() {
int diemSo[SO_MON_HOC];
nhapMang(diemSo);
cout << "dtb: << dtb(diemSo, SO_MON_HOC);
return 0;
}
Xâu Ký Tự
13

 Kiểu dữ liệu xâu ký (thư viện string của C++)

 Xâu ký tự là một chuỗi các ký tự, kết thúc '\0'
Giới Thiệu Lập Trình
int main()
{
char ten1[20] = {'L','e',' ','B','e','\0'};
char ten2[20] = "Le Be";
cout << ten2;
cin >> ten1;
cin.getline(ten2, 15, '\n');
return 0;
}
Lập Trình Với Mảng
14

 Nhập & in dữ liệu

 Tìm kiếm dữ liệu

 Sắp xếp dữ liệu

 Thêm & loại dữ liệu
Giới Thiệu Lập Trình
Nhập & In
15Giới Thiệu Lập Trình
void nhapMang(int a[], int soPhanTu){
for (int i = 0; i < soPhanTu; i++)
cin >> a[i];
}
void inMang(const int a[], int soPhanTu){
for (int i = 0; i < soPhanTu; i++)
cout << a[i] << endl;
}
int main() {
const int SO_MON_HOC = 10;
int diemSo[SO_MON_HOC];
nhapMang(diemSo, SO_MON_HOC);
inMang(diemSo, 5);
return 0;
}
Tìm Kiếm
16

 Tìm kiếm giá trị có khóa k trong mảng

 Bắt đầu từ đầu (hoặc cuối), duyệt từng phần tử

 Có phần tử giá trị bằng khóa trả về đúng (tìm thấy)

 Hết mảng, không có, trả về sai (không tìm thấy)
Giới Thiệu Lập Trình
bool timKiemBF{const int a[], int soPT, int k) {
for (int i = 0; i < soPT; i++)
if (a[i] == k) return true;
return false;
}
bool timKiemBW{const int a[], int soPT, int k) {
int i = soPT - 1;
while (i >= 0 && a[i] != k) i--;
return (i >= 0);
}
Tìm Kiếm
17

 Tìm kiếm giá trị có khóa k trong mảng

 Bắt đầu từ đầu (hoặc cuối), duyệt từng phần tử

 Có phần tử giá trị bằng khóa trả về chỉ số phần tử

 Hết mảng, không có, trả về -1 (ngoài khoảng mảng)
Giới Thiệu Lập Trình
int timKiemIF{const int a[], int soPT, int k) {
for (int i = 0; i < soPT; i++)
if (a[i] == k) return i;
return -1;
}
int timKiemIW{const int a[], int soPT, int k) {
int i = soPT - 1;
while (i >= 0 && a[i] != k) i--;
return i;
}
Sắp Xếp Lựa Chọn
18

 Lần lặp 1:

 Tìm phần tử nhỏ nhất của mảng

 Đổi chỗ với phần tử đầu tiên

 Lần lặp 2:

 Tìm phần tử nhỏ thứ 2 của mảng

 Đổi chỗ với phần tử thứ 2

 Lần lặp 3:

 Tìm phần tử nhỏ thứ 3 của mảng

 Đổi chỗ với phần tử thứ 3
Giới Thiệu Lập Trình
Sắp Xếp Lựa Chọn
19

 Coi mảng là 2 phần:

 Phần đầu: các phần tử đã được sắp xếp đúng chỗ

 Phần sau: các phần tử còn lại cần được sắp xếp

 Một giá trị chỉ số để xác định điểm phân cách 2 mảng

 Lặp

 Tìm phần tử nhỏ nhất trong mảng chưa sắp xếp

 Đổi chỗ lên đầu mảng chưa sắp xếp

 Tăng giá trị chỉ số lên 1
Giới Thiệu Lập Trình
Sắp Xếp Lựa Chọn
20Giới Thiệu Lập Trình
void sapXepLuaChon(int a[], int soPT) {
for (int i = 0; i < soPT – 1; i++) {
// tìm chỉ số phần tử có giá trị nhỏ nhất
int minI = i;
for (int j = i + 1; j < soPT; j++)
if (a[j] < a[minI]) minI = j;
// đổi chỗ lên đầu mảng chưa sắp xếp
int tmp = a[i];
a[i] = a[minI];
a[minI] = tmp;
}
}
Thêm & Loại Dữ Liệu
21

 Đặt vấn đề:

 Sinh viên đăng ký lớp môn học

 Sinh viên lần lượt đăng ký (thêm vào danh sách)

 Sinh viên rút khỏi lớp môn học (loại khỏi danh sách)

 Kích thước của danh sách lớp môn học ban đầu

 Số lượng sinh viên thực sự của lớp môn học
Giới Thiệu Lập Trình
Thêm & Loại Dữ Liệu
22

 Thêm hay loại dữ liệu trong mảng làm thay đổi 
số phần tử mảng, không thay đổi kích thước

 Biến số quản lý số phần tử thực sự của mảng

 Biến số này trong khoảng chỉ số hợp lệ của mảng

 Chương trình phải quản lý biến số này

 Thêm dữ liệu

 Tăng số phần tử mảng

 Phải kiểm tra mảng có đầy hay không

 Loại dữ liệu

 Giảm số phần tử mảng

 Phải kiểm tra phần tử có trong mảng hay không
Giới Thiệu Lập Trình
Thêm Dữ Liệu
23

 Mảng chưa sắp xếp

 Thêm vào cuối cùng, sau phần tử cuối cùng

 Sử dụng biến số quản lý số phần tử thực sự

 Nếu mảng chưa đầy, thêm được, trả về đúng
Giới Thiệu Lập Trình
bool them(int a[], int & soPT, int k) {
if (soPT < SO_SINH_VIEN) {
a[soPT] = k;
soPT++;
return true;
}
else {
return false;
}
}
Loại Dữ Liệu
24

 Mảng chưa sắp xếp

 Phần tử bị loại có chỉ số là i (cần phải tìm trước)

 Đổi chỗ phần tử này với phần tử cuối cùng

 Sử dụng biến số quản lý số phần tử thực sự
Giới Thiệu Lập Trình
bool loai(int a[], int & soPT, int i) {
if (soPT = soPT) {
return false;
}
else {
// đảo chỗ a[i] và a[soPT-1]   
soPT--;
return false;
}
}
Thêm Dữ Liệu
25

 Mảng đã sắp xếp

 Sau khi thêm mảng vẫn phải được sắp xếp

 Tìm vị trí để thêm khóa k

 Bắt đầu từ vị trí đó lùi các phần tự ra sau một chỉ số
Giới Thiệu Lập Trình
bool them(int a[], int & soPT, int k) {
if (soPT < SO_SINH_VIEN) {
// tìm vị trí để thêm k (index)
// lùi các phần tử ra sau, sau đó
dsmssv[index] = k;
soPT++;
return true;
}
return false;
}
Loại Dữ Liệu
26

 Mảng đã sắp xếp

 Sau khi loại mảng vẫn phải được sắp xếp

 Tìm vị trí để loại khóa k

 Bắt đầu vị trí đó tiến các phần tự lên trước một chỉ số
Giới Thiệu Lập Trình
bool loai(int a[], int & soPT, int k) {
if (soPT < 0)
return false;
// tìm vị trí để thêm k (index) 
// tiến các phần tử ra trước
soPT--;
return true;
}
Mảng Nhiều Chiều
27

 Trò chơi cờ ca rô

 Xem mã nguồn
Giới Thiệu Lập Trình
Tham Khảo
28

 Đọc sách:

 Chương 5, Lập Trình Cơ Bản C++
Giới Thiệu Lập Trình