Bài giảng Giới thiệu lập trình - Bài 6: Cấu trúc mảng

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