Bài giảng Giới thiệu lập trình - Cấu trúc mảng - Lê Nguyên Khôi
Tóm tắt Bài giảng Giới thiệu lập trình - Cấu trúc mảng - Lê Nguyên 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 ma...[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 ...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...
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
File đính kèm:
- bai_giang_gioi_thieu_lap_trinh_cau_truc_mang_le_nguyen_khoi.pdf