Bài giảng Giới thiệu lập trình - Bài 1: Giới thiệu - Lê Nguyên Khôi

(dem < 4) { std::cin >> soND; if (soND <= 0) { continue; } tong = tong + soND; dem = dem + 1; } std::cout << tong; Mệnh Lệnh break & continue – Ví Dụ 29
Nhập vào 4 số nguyên dương, và tính tổng. Dừng khi nhập số âm, in ra số lượng các số Giới Thiệu Lập Trình int soND, tong = 0, dem = 0; while (dem < 4) { std::cin >> soND; if (soND <= 0) { break; } tong = tong + soND; dem = dem + 1; } std::cout << tong << " " << dem; 6Mệnh Lệnh break & continue – Ví Dụ 30
Nhập vào 4 số nguyên dương, và tính tổng. Nếu nhập vào số âm dừng, in số các số Giới Thiệu Lập Trình int soND, tong = 0, dem = 0; while (dem < 4) { std::cin >> soND; if (soND > 0) { tong = tong + soND; dem = dem + 1; } else { // ? } } std::cout << tong << " " << dem; Tham Khảo 31
Đọc sách:
Chương 3, Lập Trình Cơ Bản C++ Giới Thiệu Lập Trình 1Giới Thiệu Lập Trình Hàm – Cơ Bản TS. Lê Nguyên Khôi Trường Đại học Công nghệ, ĐHQGHN Nội Dung 1
Khái niệm chung
Định nghĩa hàm
Sử dụng hàm
Truyền tham số
Phạm vi biến Giới Thiệu Lập Trình Khái Niệm Chung 2
Giải quyết một bài toán phức tạp
Chia nhỏ bài toán ban đầu thành bài toán nhỏ hơn, đơn lẻ, dễ giải quyết
Xử lý từng bài toán nhỏ lần lượt
Kết hợp lại để giải bài toán ban đầu
Ngôn ngữ lập trình bậc cao
Cung cấp công cụ để phân tách và xử lý bài toán nhỏ (khối lắp ghép - mô-đun hóa chương trình)
Lợi ích
Tái sử dụng mã, dễ quản lý
Tránh các đoạn mã giống nhau lặp đi lặp lại
Tìm lỗi, gỡ lỗi dễ dàng, nhanh chóng Giới Thiệu Lập Trình Khái Niệm Chung 3
Chia nhỏ bài toán, ví du:
Cho độ dài 3 đoạn thẳng, 3 đoạn thẳng này tạo thành tam giác gì?
3 đoạn thẳng có tạo thành tam giác?
3 đoạn thẳng này có tạo thành tam giác đều?
3 đoạn thẳng này có tạo thành tam giác cân?
3 đoạn thẳng này có tạo thành tam vuông?

3 đoạn thẳng này có tạo thành tam giác vuông cân? Giới Thiệu Lập Trình Khái Niệm Chung 4
Tái sử dụng mã, ví du:
Tính ước chung lớn nhất của 2 số nguyên dương
Kiểm tra 2 số nguyên tố cùng nhau
Tối giản phân số
Kiểm tra 2 số có chia hết cho nhau Giới Thiệu Lập Trình Hàm (Phương Thức) 5
Hàm (phương thức) là một khối các câu lênh (phải) được đặt tên, để thực hiện thao tác đã được xác định trước
Hàm là một cách hữu hiệu để cấu trúc chương trình và xử lý:
Đoạn mã được dùng lại nhiều lần
Hàm đã sử dụng
Hàm tính căn bậc 2 (sqrt(x))
Hàm tính số mũ (pow(x,y))
Hàm tạo số ngẫu nhiên (rand()) Giới Thiệu Lập Trình 2Hàm – Đặc Điểm 6
Thực hiện một số thao tác và cung cấp kết quả
Ví dụ: căn bậc 2 (sqrt(x))
Dữ liệu đầu vào: một số
Thao tác: tính căn bậc hai
Dữ liệu trả về: căn bậc hai của số đố
Dạng chung
Có thể cần dữ liệu đầu vào
Thực hiện một số thao tác
Có thể trả về dữ liệu sau xử lý
Để thuận tiện, các thao tác được đặt tên, tên hàm Giới Thiệu Lập Trình Hàm – Tính
 7
Dữ liệu đầu vào
2 số (int, double, ) đặt tên x, y
Dữ liệu trả về
1 số (int, double, ) đặt tên ketQua
Thao tác
Thực hiện phép nhân lặp đi lặp lại
Ví dụ: 2 = 16 = 2 ∗ 2 ∗ 2 ∗ 2
Tên hàm
power Giới Thiệu Lập Trình Định Nghĩa Hàm Trong C++ 8
Cú pháp: KiểuDLTrảVề TênHàm (DanhSáchDLĐầuVào) { // danh sách các mệnh lệnh // thân hàm }
Kiểu của dữ liệu trả về (KiểuDLTrảVề)
int, double, char,
Nếu hàm không trả về gì, kiểu dữ liệu trả về void
Tên hàm (TênHàm): phải có
Danh sách dữ liệu đầu vào (DanhSáchDLĐầuVào)
Danh sách tham số (tham số cũng có kiểu) Giới Thiệu Lập Trình Định Nghĩa Hàm Trong C++ 9
Sử dụng câu lệnh return để trả về kết quả của hàm
Thực hiện câu lệnh return trả về kết quả của hàm, kết thúc các thao tác của hàm
Thông thường return là câu lệnh cuối cùng trong thân hàm (định nghĩa của hàm)
Kiểu dữ liệu trả về khi sử dụng câu lệnh return phải giống với kiểu dữ liệu trả về của hàm (KiểuDLTrảVề) Giới Thiệu Lập Trình int main() { return 0; } Hàm – Tính
 10
Ví dụ: power(2,4) trả về kết quả 16 Giới Thiệu Lập Trình int power(int x, int y) { int ketQua = 1; if (y == 0) return 1; while (y > 0) { ketQua = ketQua * x; y = y – 1; } return ketQua; } Vị Trí Đặt Định Nghĩa Hàm 11
Hàm phải được định nghĩa trước khi sử dụng
Thông thường định nghĩa hàm đặt trước (ở trên và ở ngoài) int main() để có thể sử dụng trong int main() Giới Thiệu Lập Trình int power( ) { } int main() { = power( ); return 0; } 3Sử Dụng Hàm 12
Hàm sau khi đã được định nghĩa có thể được sử dụng bất kỳ đâu miễn sao dữ liệu trả về của hàm phù hợp (về cú pháp và kiểu dữ liệu) với mục đích sử dụng
Không thể cin >> power(a, b); Giới Thiệu Lập Trình int power(int x, int y) { } int main() { int a, b; cin >> a >> b; int kq = power(a, b); cout << kq; cout << power(a, b); return 0; } Sử Dụng Hàm 13
Đặt định nghĩa hàm nào trước A hay B
Lưu ý: định nghĩa hàm A có sử dụng (gọi) hàm B, ngược lại, định nghĩa hàm B có sử dụng (gọi) A hàm Giới Thiệu Lập Trình int A() { B(); } int B() { A(); } int main() { return 0; } Khai Báo – Định Nghĩa Hàm 14
C++ cho phép khai báo hàm trước khi sử dụng
Sau khi khai báo hàm, định nghĩa hàm có thể đặt bất kỳ ở đâu, trước/sau int main()
Nên sử dụng cách này Giới Thiệu Lập Trình // khai báo hàm trước int main() int A(); int B(); int main() { return 0; } // định nghĩa hàm sau int main() int A() { B(); } int B() { A(); } Chữ Ký Hàm 15
Bỏ đi phần { } của định nghĩa hàm
Bỏ đi ; của khai báo hàm
Phần còn lại (kiểu trả về, tên, danh sách tham số) của hàm giống hệt nhau ở cả định nghĩa và khai báo Giới Thiệu Lập Trình // khai báo hàm trước int main() int A(); int B(); int main() { return 0; } // định nghĩa hàm sau int main() int A() { B(); } int B() { A(); } Hàm – Tính Nhân (Trả Về int) chỉ sử dụng phép cộng 16Giới Thiệu Lập Trình int multiply(int x, int y) { int ketQua = 0; for (int i = x; i > 0; i--) ketQua = ketQua + y; return ketQua; } int main() { int a, b; cin >> a >> b; cout << "tich 2 so la: " << multiply(a,b); return 0; } Hàm – Tính Nhân (Trả Về void) chỉ sử dụng phép cộng 17Giới Thiệu Lập Trình void multiply(int x, int y) { int ketQua = 0; for (int i = x; i > 0; i--) ketQua = ketQua + y; cout << "tich 2 so la: " << ketQua; } int main() { int a, b; cin >> a >> b; multiply(a,b); return 0; } 4Hàm – Không Có Tham Số 18Giới Thiệu Lập Trình void square() { for (int i = 3; i > 0; i--) { for (int j = 3; j > 0; j--) cout << "*"; cout << endl; } cout << endl; } int main() { int soLuong; cin >> soLuong; for (int i = soLuong; i > 0; i--) square(); return 0; } Hàm – Có Tham Số 19Giới Thiệu Lập Trình void square(char c) { for (int i = 3; i > 0; i--) { for (int j = 3; j > 0; j--) cout << c; cout << endl; } cout << endl; } int main() { int soLuong; cin >> soLuong; char c; cin >> c; for (int i = soLuong; i > 0; i--) square(c); return 0; } Hàm – Nhiều Tham Số 20Giới Thiệu Lập Trình void square(char c, int n) { for (int i = n; i > 0; i--) { for (int j = 3; j > 0; j--) cout << c; cout << ""; } cout << endl; } int main() { const int hang = 3; int cot; cin >> cot; char c; cin >> c; for (int i = hang; i > 0; i--) square(c,cot); return 0; } Xác Định Loại Tam Giác 21
Cho độ dài 3 đoạn thẳng, 3 đoạn thẳng này tạo thành tam giác gì?
3 đoạn thẳng có tạo thành tam giác?
3 đoạn thẳng này có tạo thành tam giác đều?
3 đoạn thẳng này có tạo thành tam giác cân?
3 đoạn thẳng này có tạo thành tam vuông?

3 đoạn thẳng này có tạo thành tam giác vuông cân? Giới Thiệu Lập Trình Xác Định Loại Tam Giác tạo thành tam giác 22Giới Thiệu Lập Trình bool laTamGiac(double a, double b, double c) { return (a < b + c && b < c + a && c < a + b); } int main() { return 0; } Xác Định Loại Tam Giác tạo thành tam giác đều 23Giới Thiệu Lập Trình bool laTamGiacD(double a, double b, double c) { return (a == b && b == c); } int main() { return 0; } 5Xác Định Loại Tam Giác tạo thành tam giác cân 24Giới Thiệu Lập Trình bool laTamGiacC(double a, double b, double c) { return (a == b || b == c || c == a); } int main() { return 0; } Xác Định Loại Tam Giác tạo thành tam giác vuông 25Giới Thiệu Lập Trình bool laTamGiacV(double a, double b, double c) { double sqrCanhA = a * a; double sqrCanhB = b * b; double sqrCanhC = c * c; return (sqrCanhA == sqrCanhB + sqrCanhC || sqrCanhB == sqrCanhC + sqrCanhA || sqrCanhC == sqrCanhA + sqrCanhB); } int main() { return 0; } Xác Định Loại Tam Giác tạo thành tam giác vuông cân 26Giới Thiệu Lập Trình bool laTamGiacVC(double a, double b, double c) { return (laTamGiacV(a, b, c) && laTamGiacC(a, b, c)); } int main() { return 0; } Xác Định Loại Tam Giác 27
Cho độ dài 3 đoạn thẳng, 3 đoạn thẳng này tạo thành tam giác gì?
3 đoạn thẳng có tạo thành tam giác?
3 đoạn thẳng này có tạo thành tam giác đều?
3 đoạn thẳng này có tạo thành tam giác cân?
3 đoạn thẳng này có tạo thành tam vuông?
3 đoạn thẳng này có tạo thành tam giác vuông cân?
Suy luận lô-gic:
Có cần kiểm tra là tam giác trước khi xác định loại của tam giác không? Giới Thiệu Lập Trình Nhập 2 Số Nguyên Dương 28Giới Thiệu Lập Trình int main() { int a, b; do { cin >> a; } while (a <= 0); do { cin >> b; } while (b <= 0); return 0; } Nhập 2 Số Nguyên Dương 29
Chương trình chạy không đúng, giá trị nhập vào không được gán cho biến, các biến chưa được nhập dữ liệu
Do cách truyền tham số chưa đúng Giới Thiệu Lập Trình void nhapSoND(int soND) { do { cin >> soND; } while (soND <= 0); } int main() { int a, b; nhapSoND(a); nhapSoND(b); return 0; } 6Truyền Tham Số Cho Hàm 30
Truyền giá trị:
Bản sao giá trị của biến được truyền vào hàm
Hàm xử lý dữ liệu trên bản sao này
Không làm thay đổi giá trị của biến truyền vào hàm
Dùng trong trường hợp tính toán
Truyền tham chiếu
Hàm xử lý dữ liệu của chính biến truyền vào hàm
Có thể thay đổi giá trị của biến
Dùng trong trường hợp cẩn chuyển dữ liệu sau khi đã xử lý ra ngoài hàm, cho các hàm khác sử dụng Giới Thiệu Lập Trình Truyền Tham Số Cho Hàm truyền giá trị 31
Bản sao giá trị của biến a được tạo ra và truyền
Vào trong hàm nhapSoND, giá trị này được gán cho biến soND
Thay đổi giá trị biến soND trong hàm nhapSoND,
Kết thúc hàm nhapSoND, giá trị của biến soND thay đổi
Nhưng giá trị biến a không thay đổi Giới Thiệu Lập Trình void nhapSoND(int soND) { do { cin >> soND; } while (soND <= 0); } int main() { int a; nhapSoND(a); return 0; } Truyền Tham Số Cho Hàm truyền tham chiếu 32
Chính biến a được truyền vào trong hàm nhapSoND
Nhưng được lưu dưới một tên khác (soND) trong hàm nhapSoND
Thay đổi giá trị biến soND trong hàm nhapSoND
Sẽ làm thay đổi giá trị biến a ở trong hàm main
Do thực chất là một biến, với tên khác nhau, trong hàm main là a, trong hàm nhapSoND là soND Giới Thiệu Lập Trình void nhapSoND(int & soND) { do { cin >> soND; } while (soND <= 0); } int main() { int a; nhapSoND(a); return 0; } Hàm – Tính Nhân (Trả Về void) sử dụng truyền tham chiếu tich 33Giới Thiệu Lập Trình void multiply(int x, int y, int & ketQua) { ketQua = 0; for (int i = x; i > 0; i--) ketQua = ketQua + y; } int main() { int a, b, tich; cin >> a >> b; multiply(a, b, tich); cout << "tich 2 so la: " << tich; return 0; } Một Số Nguyên Tắc 34
Tất cả các hàm trong C++ đều ngang cấp
Hàm không được khai báo lồng với nhau
Thứ tự khai báo không quan trọng
Hàm có thể nhận và xử lý nhiều tham số hoặc không có tham số nào
Hàm có thể trả về một (hoặc không ) giá trị
Phải truyền đầy đủ số lượng tham số và đúng kiểu khi gọi hàm, nếu không sẽ lỗi dịch
Biến khai báo trong hàm nào chỉ có phạm vi trong hàm đó, không sử dụng được những biến này trong các hàm khác Giới Thiệu Lập Trình Quy Tắc Phạm Vi 35
Phạm vi được xác định bắt đầu từ { đến }
Được áp dụng ở hàm (định nghĩa hàm), các cấu trúc điều khiển (thân cấu trúc) và các khối lệnh { }
Biến được khai báo trong phạm vi nào chỉ có thể được sử dụng trong phạm vi đó
Kết thúc một phạm vi (}), tất cả các biến vừa được khai báo trong phạm vi đó sẽ bị xóa
Có thể khai báo các biến cùng tên trong các phạm vi khác nhau
Các biến này là biến cục bộ
Duy trì điều khiển trong nội bộ phạm vi Giới Thiệu Lập Trình 7Quy Tắc Phạm Vi 36
Phạm vi toàn cục
Biến được khai báo ở bên ngoài main, và ngoài tất cả các hàm
Biến này sẽ được hiểu và có thể dùng ở mọi nơi trong chương trình
Hạn chế dùng, dễ gây lỗi không đáng có khi thay đổi giá trị biến không cẩn thẩn
Thường khai báo hằng số có phạm vi toàn cục để mọi hàm đều hiểu Giới Thiệu Lập Trình Tham Khảo 37
Đọc sách:
Chương 4, Lập Trình Cơ Bản C++ Giới Thiệu Lập Trình 1Giớ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]; 2Khai 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; } 3Truyề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; } 4Sắ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; } } 5Loạ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 1Giới Thiệu Lập Trình Xâu Ký Tự TS. Lê Nguyên Khôi Trường Đại học Công nghệ, ĐHQGHN Nội Dung 1
Mảng ký tự (thư viện cstring)
Lớp string Giới Thiệu Lập Trình Xâu Ký Tự cstring 2
Mảng dữ liệu kiểu char
Mỗi ký tự là một phần tử trong mảng
Thêm 1 ký tự cuối cùng: '\0' (ký tự null)
Đánh dấu kết thúc xâu
Ví dụ:
Xâu "hello" lưu dưới dạng cstring
Khai báo char s[10];, s lưu 9 ký tự và '\0'
Lưu xâu sử dụng mảng không đầy:
Khai báo một mảng “đủ lớn” để lưu xâu
Ký tự null ('\0') đánh dấu kết thúc xâu Giới Thiệu Lập Trình Xâu Ký Tự cstring – Ví Dụ 3
Khai báo char s[10];
Dùng s để lưu "hi you", s trông như sau
Khởi tạo char s[10] = "hi you";
s lưu "hi you", s trông như sau
Khởi tạo char s[] = "hi you";
s lưu "hi you", s trông như sau Giới Thiệu Lập Trình s[0] s[1] s[2] s[3] s[4] s[5] s[6] s[7] s[8] s[9] 'h' 'i' ' ' 'y' 'o' 'u' '\0' ? ? ? s[0] s[1] s[2] s[3] s[4] s[5] s[6] s[7] s[8] s[9] 'h' 'i' ' ' 'y' 'o' 'u' '\0' '\0' '\0' '\0' s[0] s[1] s[2] s[3] s[4] s[5] s[6] 'h' 'i' ' ' 'y' 'o' 'u' '\0' Xâu Ký Tự cstring – Ví Dụ 4
Khởi tạo char s[6] = "hi you";
Mảng s có 6 phần tử, dùng để lưu xâu có 6 ký tự, thêm ký tự kết thúc xâu, 7 ký tự
Lỗi dịch: mảng s không đủ bộ nhớ để lưu xâu
Khởi tạo char s[] = "hi you";
s lưu "hi you", s trông như sau
Nếu gán s[6]='!';, s không có ký tự kết thúc xâu
Nếu gán s[2]='\0';, s có 2 ký tự kết thúc xâu Giới Thiệu Lập Trình s[0] s[1] s[2] s[3] s[4] s[5] s[6] 'h' 'i' ' ' 'y' 'o' 'u' '\0' Xâu Ký Tự cstring – Xuất 5
Có thể dùng cout để in ra xâu ký tự như các biến thuộc kiểu dữ liệu cơ bản
In ra đến khi nào gặp ký tự kết thúc xâu đầu tiên
Nếu không có ký tự kết thúc xâu
In hết các phần tử của mảng
Tiếp tục in ký tự ở các ô nhớ tiếp theo
Đến khi nào gặp ký tự kết thúc xâu (giá trị 0 kiểu int) cout << s;
In ra "hi" cout << s;
In ra "hi you? " Giới Thiệu Lập Trình s[0] s[1] s[2] s[3] s[4] s[5] s[6] 'h' 'i' '\0' 'y' 'o' 'u' '\0' s[0] s[1] s[2] s[3] s[4] s[5] s[6] 'h' 'i' ' ' 'y' 'o' 'u' '?' 2Xâu Ký Tự cstring – Nhập 6
Có thể dùng cin để nhập dữ liệu cho xâu ký tự, đến khi gặp dấu cách thì dừng
Sử dụng getline để đọc cả ký tự dấu cách char s[80]; cin.getline(s, 80); Giới Thiệu Lập Trình Xâu Ký Tự cstring – Gán & So Sánh 7
Không thể sử dụng toán tử gán (=) và toán tử so sánh với xâu ký tự kiểu mảng (==)
Sử dụng hàm sao chép xâu strcpy strcpy(s, "Hello");
Sử dụng hàm sao so sánh xâu strcmp strcmp(s1, s2)
Tải thư viện cstring để sử dụng các hàm làm việc với xâu ký tự kiểu mảng Giới Thiệu Lập Trình Xâu Ký Tự cstring – Các Hàm Khác 8
Trả về độ dài của xâu strlen strlen("Hello") trả về 5
Ghép xâu strcat strcat(s1, "Hello") thêm "Hello" vào cuối s1 Giới Thiệu Lập Trình Lớp string 9
Tải thư viên string
Các thao tác trên xâu kiểu string giống như trên các kiểu dữ liệu cơ bản string s1, s2, s3; cin >> s1; cin >> s2; s3 = s1 + s2; cout << s3; s3 = "Hello Mom!" getline(cin, s3); Giới Thiệu Lập Trình Lớp string – Xâu Ký Tự cstring 10
Chuyển đổi kiểu dữ liệu
Từ cstring sang đối tượng string (hợp lệ) char aCString[] = "My C-string"; string stringVar; stringVar = aCstring;
Từ đối tượng string sang cstring (không hợp lệ) aCstring = stringVar;
Không tự động chuyển sang cstring
Phải tự chuyển sử dụng hàm sao chép strcpy strcpy(aCString, stringVar.c_str()); Giới Thiệu Lập Trình Tham Khảo 11
Tìm hiểu các hàm thao tác với xâu ký tự kiểu mảng char trong thư viện cstring
Tìm hiểu các hàm thao tác với xâu ký tự kiểu đối tượng string trong thư viện string Giới Thiệu Lập Trình 1Giới Thiệu Lập Trình Luồng Dữ Liệu & Tệp TS. Lê Nguyên Khôi Trường Đại học Công nghệ, ĐHQGHN Nội Dung 1
Luồng Nhập/Xuất
Tệp Nhập/Xuất
Ký Tự Nhập/Xuất
Công cụ cho Luồng Nhập/Xuất
Sử dụng tên tệp cho dữ liệu vào
Định dạng dữ liệu ra, cài đặt cờ
Tệp truy cập ngẫu nhiên Giới Thiệu Lập Trình Giới Thiệu 2
Luồng dữ liệu (stream)
Đối tượng đặc biệt
Dùng nhập/xuất dữ liệu của chương trình
Tệp Nhập/Xuất dùng:
Nhập dữ liệu từ tệp vào chương trình
Xuất dữ liệu từ chương trình ra tệp Giới Thiệu Lập Trình Luồng Dữ Liệu 3
Chuỗi các ký tự
Luồng vào (input stream)
Nhập vào chương trình
Từ bàn phím
Từ tệp
Luồng ra (output stream)
Xuất ra khỏi chương trình
Ra màn hình
Ra tệp Giới Thiệu Lập Trình Sử Dụng Luồng Dữ Liệu 4
Chúng ta đã sử dụng luồng
cin
Đối tượng luồng nhập kết nối với bàn phím
cout
Đối tượng luồng xuất kết nối với màn hình
Định nghĩa các luồng khác
Để nhập/xuất cho tệp
Sử dụng tương tự cin, cout Giới Thiệu Lập Trình Tệp Văn Bản 5
Đọc từ tệp
Khi nhập dữ liệu cho chương trình
Ghi vào tệp
Khi chương trình xuất dữ liệu
Bắt đầu từ đầu đến cuối tệp
Có nhiều cách thức (đọc/ghi) khác
Truy cập tệp văn bản đơn giản Giới Thiệu Lập Trình 2Kết Nối Tệp Với Chương Trình 6
Phải kết nối tệp với đối tượng luồng
Với nhập dữ liệu:
Tệp là đối tượng ifstream
Với xuất dữ liệu:
Tệp là đối tượng ofstream
Các lớp ifstream và ofstream
Được định nghĩa trong thư viện fstream
Có trong không gian tên std Giới Thiệu Lập Trình Thư Viện Tệp Nhập/Xuất 7
Cho phép nhập/xuất dữ liệu từ/ra tệp: #include using namespace std; hoặc #include using std::ifstream; using std::ofstream; Giới Thiệu Lập Trình Khai Báo Luồng 8
Khai báo luồng giống như bất cứ biến nào: ifstream inStream; ofstream outStream;
Sau đó kết nối với tệp: inStream.open("infile.txt");
Thực hiện thao tác mở tệp
Sử dụng hàm thành viên open
Có thể chỉ định đường dẫn hoàn chỉnh Giới Thiệu Lập Trình Sử Dụng Luồng Dữ Liệu 9
Sau khi khai báo sử dụng như cin ifstream inStream; inStream.open("infile.txt"); int soThuNhat, soThuHai; inStream >> soThuNhat; inStream >> soThuHai;
Tương tự luồng xuất (giống cout) ofstream outStream; outStream.open("outfile.txt"); outStream << "soThuNhat = " << soThuNhat; outStream << " soThuHai = " << soThuHai;
Ghi dữ liệu ra tệp Giới Thiệu Lập Trình Tên Tệp 10
Đối với chương trình, tệp có 2 tên:
Tên tệp ngoại vi
Tên tệp trên ổ cứng, đôi khi được gọi tên tệp thực
Sử dụng một lần trong chương trình (khi mở tệp)
Ví dụ: infile.txt, outfile.txt
Tên luồng
Tên tệp trong chương trình
Sử dụng tên này cho tất cả các hoạt động đọc/ghi
Ví dụ: inStream, outStream Giới Thiệu Lập Trình Đóng Tệp 11
Tệp nên được đóng lại
Khi chương trình hoàn tất đọc/ghi dữ liệu
Đóng kết nối giữa luồng & tệp
Ví dụ: inStream.close(); outStream.close();
Không có tham số
Tệp tự động đóng khi kết thúc chương trình Giới Thiệu Lập Trình 3Nhập/Xuất Dữ Liệu Sử Dụng Tệp 12 ifstream inStream; ofstream outStream; inStream.open("infile.txt"); outStream.open("outfile.txt"); int so1, so2, so3; inStream >> so1 >> so2 >> so3; outStream << "Tong 3 so dau la " << (so1 + so2 + so3) << endl; inStream.close(); outStream.close(); Giới Thiệu Lập Trình Ghi Dữ Liệu Vào Tệp 13
Thường một tệp được mở là một tệp rỗng
Nếu tệp tồn tại, toàn bộ dữ liệu bị xóa
Mở tệp để chèn vào cuối tệp (sử dụng cờ): ofstream outStream; outStream.open("outfile.txt", ios::app);
Nếu tệp không tồn tại, tạo tệp mới
Nếu tệp tồn tại, chèn vào cuối tệp
Tham số thứ 2 là hằng trong lớp ios
Trong thư viện iostream
Không gian tên std Giới Thiệu Lập Trình Kiểm Tra Mở Tệp Thành Công 14
Có thể gặp lỗi khi mở tệp
Khi tệp không tồn tại (để đọc dữ liệu)
Không có quyền ghi vào tệp
Sử dụng hàm thành viên fail()
Gọi hàm thành viên fail() để kiểm tra mở luồng thành công không inStream.open("infile.txt"); if (inStream.fail()) { cout << "Loi mo file.\n"; exit(1); } Giới Thiệu Lập Trình Kiểm Tra Kết Thúc Tệp 15
Dùng vòng lặp để xử lý với tệp đến khi hết tệp
Sử dụng hàm thành viên eof() inStream.get(next); while (!inStream.eof()) { cout << next; inStream.get(next); }
Đọc từng ký tự cho đến khi hết dữ liệu trong tệp
Hàm thành viên eof() trả về kiểu bool Giới Thiệu Lập Trình Nhập Tên Tệp Khi Chạy Chương Trình 16
Tham số cho open() là kiểu xâu ký tự
Tên cụ thể hoặc biến char tenTep[16]; cout << "Nhap ten tep: "; cin >> tenTep; ifstream inStream; inStream.open(tenTep);
Linh hoạt hơn đối với tên tệp là biến được nhập từ bàn phím khi chạy chương trình Giới Thiệu Lập Trình Định Dạng Dữ Liệu Xuất 17
Xuất dữ liệu dưới dạng 2 số thập phân: cout.setf(ios::fixed); cout.setf(ios::showpoint); cout.precision(2);
In ra màn hình (12.50)
Hàm thành viên precision(x)
Phần thập phân dưới dạng "x" số sau dấu “.”
Hàm thành viên setf()
Cho cài đặt nhiều định dạng
Có thể sử dụng cho bất cứ luồng xuất nào
Đối với luồng cho tệp, hàm thành viên giống đối tượng cout Giới Thiệu Lập Trình 4Tham Khảo 18
Đọc sách:
Chương 8, Lập Trình Cơ Bản C++
Tìm hiểu thư viện iomanip
Các định dạng xuất dữ liệu
Tìm hiểu thao tác với tệp truy cập ngẫu nhiên
Hiểu quả cho cơ sở dữ liệu lớn Giới Thiệu Lập Trình 1Giới Thiệu Lập Trình Con Trỏ TS. Lê Nguyên Khôi Trường Đại học Công nghệ, ĐHQGHN Nội Dung 1
Con trỏ
Biến kiểu con trỏ
Quản lý vùng nhớ
Toán tử con trỏ
Mảng động
Khai báo & sử dụng
Các phép toán với con trỏ Giới Thiệu Lập Trình Giới Thiệu 2
Định nghĩa:
Địa chỉ vùng nhớ máy tính của một biến
Vùng nhớ máy tính
Chia nhỏ thành các byte
Đánh số thứ tự lần lượt (hệ 16)
Địa chỉ được sử dụng làm tên cho biến
Con trỏ đã sử dụng
Truyền tham số theo kiểu tham chiếu
Địa chỉ của tham số được truyền Giới Thiệu Lập Trình Biến Con Trỏ 3
Con trỏ là “kiểu dữ liệu”
Kiểu địa chỉ vùng nhớ
Có thể dùng biến để lưu giá trị kiểu con trỏ
Không phải kiểu int, double
Địa chỉ của vùng nhớ dùng lưu dữ liệu kiểu int, double
Ví dụ: double * p;
Khai báo p là biến kiểu con trỏ double
Lưu địa chỉ vùng nhớ kiểu double Giới Thiệu Lập Trình Biến Con Trỏ – Khai Báo 4
Khai báo con trỏ giống biến kiểu dữ liệu khác
Thêm * vào trước tên biến
Ký hiệu * phải đặt trước mỗi biến con trỏ
Ví dụ: int *p1, *p2, v1, v2;
p1, p2 biến kiểu con trỏ int
v1, v2 biến kiểu int
Sử dụng p1, p2 lưu địa chỉ các biến kiểu int
Sử dụng p1, p2 lưu địa chỉ của v1, v2 Giới Thiệu Lập Trình Địa Chỉ & Số Nguyên 5
Con trỏ là địa chỉ
Địa chỉ là số nguyên
Con trỏ KHÔNG là số nguyên
C++ ép con trỏ phải được sử dụng như địa chỉ
Không thể được sử dụng như số nguyên
Mặc dù đó là số nguyên!!! Giới Thiệu Lập Trình 2Toán Tử & 6
Toán tử & trả về địa chỉ của biến
Dòng 4: đặt biến con trỏ p chỉ tới biến v1
p bằng địa chỉ của v1
Dòng 5: đặt biến con trỏ p chỉ tới biến v2
p chỉ tới v1 Giới Thiệu Lập Trình 1 { 2 int *p, v1, v2; 3 v1 = 10; v2 = 20; 4 p = &v1; 5 p = &v2; 6 } 0x22ff32 p 20 v2 0x22ff32 0x44ab12 p 10 v1 0x44ab12 Toán Tử * 7
Toán tử * truy xuất giá trị của vùng nhớ được quản lý (lưu) bởi con trỏ
Dòng 4: in ra 10 (giá trị biến v1, mà p chỉ tới)
Dòng 6: in ra 20 (giá trị biến v2, mà p chỉ tới) Giới Thiệu Lập Trình 1 { 2 int *p, v1, v2; 3 v1 = 10; p = &v1; 4 cout << *p; 5 v2 = 20; p = &v2; 6 cout << *p; 7 } 0x22ff32 p 20 v2 0x22ff32 0x44ab12 p 10 v1 0x44ab12 Toán Tử = 8
Gán giá trị
Dòng 3, 4: p chỉ tới v1, q chỉ tới v2
Dòng 5: sử dụng toán tử * truy cập vùng tới nhớ con trỏ quản lý
*p là v1, *q là v2, dòng 5 tương đương v1 = v2; Giới Thiệu Lập Trình 1 { 2 int v1 = 10, v2 = 20; 3 int *p = &v1; 4 int *p = &v2; 5 *p = *q; 6 } 0x22ff32 q 20 v2 0x22ff32 0x44ab12 p 10 20 v1 0x44ab12 Toán Tử = 9
Gán con trỏ
Dòng 3, 4: p chỉ tới v1, q chỉ tới v2
Dòng 5: gán p bằng q
p không quản lý v1
p và q cùng quản lý v2 Giới Thiệu Lập Trình 1 { 2 int v1 = 10, v2 = 20; 3 int *p = &v1; 4 int *p = &v2; 5 p = q; 6 } 0x22ff32 q 20 v2 0x22ff32 0x44ab12 p 10 v1 0x44ab12 0x22ff32 Bài Tập 10Giới Thiệu Lập Trình 1 { 2 int i = 10, j = 20, k; 3 int *p = &i; 4 int *q = &j; 5 *p += 1; 6 p = &k; 7 *p = *q; 8 p = q; 9 *p = i; 0 } j 0x7756 p 0x64cc p 0x16aa k 0x9948 i 0x2232 Toán Tử new 11
Sử dụng toán tử new để tạo một vùng nhớ mới cho con trỏ, vùng nhớ này không có tên int * p = new int;
Khởi tạo một vùng nhớ mới cho con trỏ p, giá trị tại vùng nhớ này không biết int * p = new int(10);
Khởi tạo một vùng nhớ mới cho con trỏ p, giá trị tại vùng nhớ này được khởi tạo là 10 Giới Thiệu Lập Trình 3Bài Tập 12Giới Thiệu Lập Trình 1 { 2 int *p1, *p2; 3 p1 = new int; 4 *p1 = 10; 5 p2 = p1; 6 *p2 = 20; 7 p1 = new int; 8 *p1 = 30; 9 } ?p1 ?p2 p1 ?p2 ? p1 ?p2 10 p1 p2 10 p1 p2 20 p1 p2 20 ? p1 p2 20 30 Toán Tử delete 13
Sử dụng toán tử delete để giải phóng vùng nhớ động được tạo ra bởi toán tử new
Lưu ý: chỉ giải phóng vùng nhớ được tạo ra bởi new, không phải xóa biến con trỏ p Giới Thiệu Lập Trình { int * p = new int; delete p; } Toán Tử delete 14
Vùng nhớ động có thể được trả về bởi hàm
Vùng nhớ động chỉ được giải phóng khi sử dụng delete, do đó vùng nhớ động tạo ra trong hàm không bị xóa sau khi kết thúc hàm
Chỉ các biến khai báo trong hàm bị xóa, trong đó có biến con trỏ p Giới Thiệu Lập Trình int * f(int * q) { int * p = new int; return p; } Mảng Động 15
Biến mảng thực chất là biến con trỏ
Mảng thông thường (int a[10])
Độ dài mảng cố định
Không thể thay đổi độ dài sau khi khai báo
Có thể coi là con trỏ hằng (con trỏ tĩnh)
Mảng động (int * a = new int[10])
Độ dài mảng có thể thay đổi sau khi khai báo
Sử dụng lại toán tử new int * a = new int[10]; a = new int[50]; Giới Thiệu Lập Trình Mảng Động – Mảng Tĩnh 16 int * a = new int[10]; int * p;
a và p đều là biến con trỏ, nhưng a là hằng
Có thể gán (được phép) p = a;
p chỉ tới địa chỉ mà a đang chỉ tới
Nhưng không được phép (lỗi dịch) a = p;
a là hằng, không thay đổi giá trị của a Giới Thiệu Lập Trình Nhắc Lại: cstring & Lớp string 17 char aCString[]; string stringVar;
Chuyển cstring sang string (hợp lệ) stringVar = aCString;
Chuyển string sang cstring (không hợp lệ) aCString = stringVar; Giới Thiệu Lập Trình 4Mảng Động 18
Hạn chế của mảng thông thường:
Phải khai báo độ dài trước
Độ dài mảng có thể không biết tới khi chạy chương trình
Phải ước lượng độ dài lớn nhất
Lãng phí bộ nhớ
Mảng động
Có thể tăng và giảm khi cần thiết Giới Thiệu Lập Trình Giải Phóng Mảng Động 19
Cũng được thực hiện khi chạy d = new double[10]; // thao tác với d delete [] d;
Giải phóng tất cả bộ nhớ cho mảng động
[] thông báo giải phóng bộ nhớ cho mảng
Vẫn chỉ tới vùng nhớ đó
Nên gán d = NULL; Giới Thiệu Lập Trình Bài Tập 20Giới Thiệu Lập Trình int a[10] = {2,3,5,1,4,7,0}; int *p = a; cout << a[0] << *p << "\n"; p++; cout << *p << p[2] << "\n"; p++; a[2] = 0; cout << p[1] << *p << "\n"; p -= 2; cout << p[3] << p[1] << "\n"; 2 2 3 1 1 9 1 3 Hàm Trả Về Mảng 21
Kiểu mảng không được phép là kiểu trả về
Không hợp lệ int[] someFunction();
Phải trả về kiểu con trỏ int * someFunction(); Giới Thiệu Lập Trình Con Trỏ Trong C++ 22
Con trỏ là khối kiến thức đặc biệt quan trọng trong C++
Phải nắm vững khái niệm con trỏ cũng như thao tác với con trỏ
Con trỏ sẽ được sử dụng trong các kiểu dữ liệu phức tạp
INT 2203 Cấu trúc Dữ liệu & Giải thuật Giới Thiệu Lập Trình 1Giới Thiệu Lập Trình Cấu Trúc struct TS. Lê Nguyên Khôi Trường Đại học Công nghệ, ĐHQGHN Nội Dung 1
Cấu trúc struct
Kiểu dữ liệu nhóm
Định nghĩa
Khai báo / Khởi tạo
Sử dụng
Truyền biến cho hàm Giới Thiệu Lập Trình Kiểu Dữ Liệu Nhóm 2
Kiểu Mảng:
Tập hợp dữ liệu cùng kiểu
Khai báo sau đó sử dụng như biến đơn lẻ
Truyền cho hàm: truyền địa chỉ
Kiểu cấu trúc struct:
Tập hợp dữ liệu có thể khác kiểu
Phải định nghĩa trước khi sử dụng
Khai báo sau đó sử dụng như biến đơn lẻ
Truyền cho hàm: giống biến đơn lẻ Giới Thiệu Lập Trình Kiểu DL Cấu Trúc struct 3
Tập hợp dữ liệu, có thể khác kiểu, được nhóm
Mỗi dữ liệu được lưu trong một biến (trường)
Mỗi dữ liệu có kiểu dữ liệu cụ thể
Hỗ trợ tổ chức dữ liệu phức tạp vào cùng một đối tượng
Hỗ trợ làm việc giữa các dữ liệu trên đối tượng Giới Thiệu Lập Trình Kiểu DL Cấu Trúc struct – Ví Dụ 4 Tên Trường Kiểu Dữ Liệu Dữ Liệu MSSV string 12345678 HoTen string Trach Van Doanh NgaySinh string 01/01/1999 GioiTinh bool true Giới Thiệu Lập Trình Kiểu DL Cấu Trúc struct – Định Nghĩa 5
Định nghĩa bởi từ khóa struct
Định nghĩa toàn cục
Ngoài và trước int main()
Tất cả các hàm đều hiểu
Không được cấp phát bộ nhớ
Chỉ có mục đích miêu tả cấu trúc
Chỉ cấp phát bộ nhớ
Khi khai báo biến kiểu cấu trúc
Miêu tả:
Các thành phần (trường) và kiểu của chúng Giới Thiệu Lập Trình 2struct sinhvien – Định Nghĩa 6 struct sinhvien { string MSSV; string HoTen; string NgaySinh; bool GioiTinh; } ; Giới Thiệu Lập Trình Tên Trường Kiểu Dữ Liệu Dữ Liệu MSSV string 12345678 HoTen string Trach Van Doanh NgaySinh string 01/01/1999 GioiTinh bool true struct sinhvien – Khai Báo/Khởi Tạo 7 struct sinhvien { string MSSV; string HoTen; string NgaySinh; bool GioiTinh; } ; int main() { struct sinhvien sv1; struct sinhvien sv2 = { "12345678" , "Trach Van Doanh" , "01/01/1999" , true } ; } Giới Thiệu Lập Trình Truy Cập Thành Phần struct 8
Sử dụng toán tử chấm (.) sv1 . MSSV sv1 . HoTen sv1 . NgaySinh sv1 . GioiTinh
Gọi tên là “biến thành phần”
Các thành phần của biến kiểu cấu trúc
Kiểu cấu trúc struct khác nhau có thể có cùng tên biến thành phần
Biến thành phần là biến cục bộ Giới Thiệu Lập Trình Truy Cập Thành Phần struct – Ví Dụ 9 struct sinhvien { string MSSV; string HoTen; string NgaySinh; bool GioiTinh; } ; int main() { struct sinhvien sv1; sv1.MSSV = "12345678"; sv1.HoTen = "Trach Van Doanh"; sv1.NgaySinh = "01/01/1999"; sv1.GioiTinh = true; } Giới Thiệu Lập Trình struct ngaythangnam 10 struct ngaythangnam { int ngay; int thang; int nam; } ; int main() { struct ngaythangnam homNay = {1, 4, 2000}; struct ngaythangnam ngayMai; ngayMai.ngay = homNay.ngay + 1; ngayMai.thang = homNay.thang; ngayMai.nam = homNay.nam; } Giới Thiệu Lập Trình Cấu Trúc struct – Phép Gán 11
Với cấu trúc struct ngaythangnam
Khai báo 2 biến cấu trúc struct ngaythangnam homQua, homNay;
Cả 2 biến đều kiểu struct ngaythangnam
Thực hiện phép gán đơn giản hợp lệ homQua = homNay;
Sao chép giá trị biến thành phần homNay của cho các biến thành phần của homQua, tương đương homQua.ngay = homNay.ngay; homQua.thang = homNay.thang; homQua.nam = homNay.nam; Giới Thiệu Lập Trình 3Cấu Trúc struct – Phép Toán Khác 12
Các phép toán khác không được định nghĩa cho kiểu cấu trúc struct
So sánh bằng/khác (==, !=) (homQua == homNay biểu thức không hợp lệ)
So sánh thứ tự (, ...) (homQua < homNay biểu thức không hợp lệ)
Các phép toán (homQua + homNay biểu thức không hợp lệ)
Nhập & in (cin & cout không hợp lệ) Giới Thiệu Lập Trình Truyền Biến Cấu Trúc struct Cho Hàm 13 struct toado { int x, y; } ; typedef struct toado ToaDo; void _nhapToaDo(ToaDo & td) { cin >> td.x >> td.y; } void _inToaDo(const ToaDo & td) { cout << "(" << td.x << "," << td.y << ")"; } Giới Thiệu Lập Trình Truyền Biến Cấu Trúc struct Cho Hàm 14 struct toado { int x , y ; } ; typedef struct toado ToaDo; void _nhapToaDo ( ToaDo & td ) ; void _inToaDo ( const ToaDo & td ) ; int main ( ) { ToaDo td1; _nhapToaDo ( td1 ) ; _inToaDo ( td1 ) ; ToaDo td2; _nhapToaDo ( td2 ) ; _inToaDo ( td2 ) ; } Giới Thiệu Lập Trình Truyền Biến Cấu Trúc struct Cho Hàm 15 void _trungDiem ( const ToaDo & td1 , const ToaDo & td2 , ToaDo & trungDiem ) { trungDiem.x = ( td1.x + td2.x ) / 2; trungDiem.y = ( td1.y + td2.y ) / 2; } ToaDo * _trungDiem ( const ToaDo & td1 , const ToaDo & td2 ) { ToaDo * trungDiem = new ToaDo; (*trungDiem).x = ( td1.x + td2.x ) / 2; (*trungDiem).y = ( td1.y + td2.y ) / 2; return trungDiem; } Giới Thiệu Lập Trình Truyền Biến Cấu Trúc struct Cho Hàm 16 int main ( ) { ToaDo td1 ; _nhapToaDo ( td1 ) ; ToaDo td2 ; _nhapToaDo ( td2 ) ; ToaDo tdTrgD1 ; _trungDiem ( td1 , td2 , tdTrgD1 ) ; ToaDo * tdTrgD2 = new ToaDo; tdTrgD2 = _trungDiem ( td1 , td2 ) ; _inToaDo ( tdTrgD1 ) ; _inToaDo ( *tdTrgD2 ) ; } Giới Thiệu Lập Trình Cấu Trúc struct & Con Trỏ 17
Giống các kiểu dữ liệu khác:
struct toado * là con trỏ tới struct toado
Toán tử & trả về địa chỉ của biến cấu trúc
Theo thứ tự ưu tiên: “.” được ưu tiên trước “*”
Nếu td là con trỏ tới cấu trúc struct toado:
*p.x tương đương *(p.x) không hợp lệ
Phải sử dụng (*p).x
Để thuận tiện, có thể dùng toán tử ->:
kết hợp con trỏ (*) với truy cập trường (.)
p->a tương đương (*p).a Giới Thiệu Lập Trình 4struct thoigian 18Giới Thiệu Lập Trình struct thoigian 19Giới Thiệu Lập Trình struct sohuuti 20Giới Thiệu Lập Trình struct sohuuti 21Giới Thiệu Lập Trình struct dathuc 22Giới Thiệu Lập Trình struct dathuc 23Giới Thiệu Lập Trình 1Giới Thiệu Lập Trình Hàm – Nâng Cao TS. Lê Nguyên Khôi Trường Đại học Công nghệ, ĐHQGHN Nội Dung 1
Nhắc lại Hàm – Cơ Bản
Nạp chồng hàm
Nạp chồng toán tử Giới Thiệu Lập Trình Hàm – Cơ Bản 2
Khai báo hàm int bin ( int , int ) ;
Định nghĩa hàm int bin ( int so1 , int so2 ) { // thân hàm miêu tả định nghĩa // không khai báo lại so1 , so2 }
Chữ ký hàm int bin ( int , int )
Lời gọi hàm int a = bin ( so1 , so2 ) ;
Sử dụng tên hàm, tên tham số, không có kiểu Giới Thiệu Lập Trình Hàm – Cơ Bản – Truyền Tham Số 3
Truyền giá trị int bin ( int , int ) ;
Tạo và truyền một bản sao > tốn chi phí
Thay đổi bản sao , bản gốc ngoài hàm không đổi
Xóa bản sao khi kết thúc hàm
Truyền tham chiếu int bin ( int & , int & ) ;
Chính bản gốc được truyền (địa chỉ bản gốc)
Thay đổi trong hàm, bản gốc thay đổi
Không xóa bản gốc khi kết thúc hàm Giới Thiệu Lập Trình Hàm – Cơ Bản – Sử Dụng const 4
Truyền tham chiếu int bin ( int & , int & ) ;
Thay đổi trong hàm, bản gốc thay đổi
Không muốn hàm thay đổi, sử dụng từ khóa const
Bảo vệ dữ liệu, không cho thay đổi, dữ liệu “chỉ-đọc” int bin ( const int & , const int & ) ;
Quy ước:
Luôn truyền tham chiếu
Dữ liệu không thay đổi, dùng const
Dữ liệu thay đổi, không dùng const Giới Thiệu Lập Trình Hàm Nạp Chồng (Function Overloading) 5
Các hàm thực hiện công việc tương tự
Trùng tên, nhưng khác nhau về tham số
Số lượng tham số
Kiểu tham số
Xác định hàm nào được gọi:
Sử dụng thông tin về tham số
Số lượng & kiểu tham số
Kiểu của hàm Giới Thiệu Lập Trình 2Hàm Nạp Chồng – Ví Dụ 6 void _trungDiem ( const ToaDo & td1 , const ToaDo & td2 , ToaDo & trungDiem ) { trungDiem.x = ( td1.x + td2.x ) / 2; trungDiem.y = ( td1.y + td2.y ) / 2; } ToaDo * _trungDiem ( const ToaDo & td1 , const ToaDo & td2 ) { ToaDo * trungDiem = new ToaDo; (*trungDiem).x = ( td1.x + td2.x ) / 2; (*trungDiem).y = ( td1.y + td2.y ) / 2; return trungDiem; } Giới Thiệu Lập Trình Hàm Nạp Chồng 7
Khác số lượng tham số
Hàm tính tổng các số truyền vào
Tính tổng 3 số nguyên int _tong ( int , int , int ) ;
Tính tổng 2 số nguyên int _tong ( int , int ) ;
Tính tổng 1 số nguyên int _tong ( int ) ;
Dựa trên số lượng tham số để gọi hàm tương ứng Giới Thiệu Lập Trình Hàm Nạp Chồng 8
Tham số mặc định int _tong(int so1, int so2 = 0, int so3 = 0) { return so1 + so2 + so3; }
Có thể gọi _tong ( 1 , 2 , 3 ) _tong ( 1 , 2 ) _tong ( 1 )
Có định nghĩa hàm int _tong ( int , int )
_tong ( 1 , 2 ) gọi hàm nào Giới Thiệu Lập Trình Hàm Nạp Chồng 9
Khác kiểu tham số
Hàm tính tổng 2 số truyền vào int _tong ( int , int ) ; double _tong ( double , double ) ;
Dựa trên kiểu tham số để gọi hàm tương ứng
Tại sao không sử dụng chuyển đổi kiểu tự động
Kiểu trả về không đúng
Nguy hiểm
_tong(1,2) gọi int _tong(int, int);
_tong(1.0,2.0) gọi double _tong(double, double); Giới Thiệu Lập Trình Hàm Nạp Chồng 10
Khác kiểu tham số
Hàm tính tổng 2 số truyền vào double _tong ( int , double ) ; double _tong ( double , int ) ;
Dựa trên kiểu tham số để gọi hàm tương ứng
Sử dụng chuyển đổi kiểu tự động _tong ( 3 , 3 ) hoặc _tong ( 3.5 , 3.5 )
Gọi hàm nào
Thêm đầy đủ int _tong ( int , int ) ; double _tong ( double , double ) ; Giới Thiệu Lập Trình Toán Tử 11
Toán tử thực chất là hàm
Sử dụng toán tử giống lời gọi hàm
Viết theo một cách khác
Ví dụ: so sánh bằng
1 == 2 thực chất == ( 1 , 2 ) Giới Thiệu Lập Trình 3Toán Tử Nạp Chồng 12
Giống như hàm, toán tử cũng có thể nạp chồng
Định nghĩa toán tử cho kiểu dữ liệu mới
Nạp chồng toán tử so sánh cho kiểu cấu trúc struct PS { int ts , ms ; } ; bool operator == ( const PS & ps1 , const PS & ps2 ) { return ( ps1.ts * ps2.ms == ps2.ts * ps1.ms ) ; } bool operator != ( const PS & , const PS & ) ; Giới Thiệu Lập Trình Toán Tử Nạp Chồng 13 struct PS { int ts , ms ; } ; bool operator == ( const PS & , const PS & ) ; bool operator != ( const PS & , const PS & ) ; int main() { PS ps1 , ps2 ; // nhập dữ liệu if ( ps1 == ps2 ) if ( ps1 != ps2 ) } Giới Thiệu Lập Trình Toán Tử Nạp Chồng 14 struct PS { int ts , ms ; } ; PS operator + ( const PS & ps1 , const PS & ps2 ) { PS tongPS; // cập nhật tongPS return tongPS; } int main() { PS ps1 , ps2 , tongPS ; tongPS = ps1 + ps2 ; } Giới Thiệu Lập Trình Toán Tử Nạp Chồng 15 struct PS { int ts , ms ; } ; PS operator + ( const PS & ps , const int & i ) { PS tongPS; // cập nhật tongPS return tongPS; } int main() { PS ps , tongPS ; tongPS = ps + 1 ; } Giới Thiệu Lập Trình Toán Tử Nạp Chồng 16 ostream & operator << ( ostream & outStream , const PS & ps ) { outStream << ps.ts << "/" << ps.ms ; return outStream; } int main() { PS ps , tongPS ; tongPS = ps + 1 ; cout << tongPS; } Giới Thiệu Lập Trình Template – Giới Thiệu 17 int _getMax(int so1 , int so2) { if (so1 < so2) return so2; return so1; } double _getMax(double so1 , double so2) { if (so1 < so2) return so2; return so1; } PS _getMax(PS so1 , PS so2) { if (so1 < so2) return so2; return so1; } Giới Thiệu Lập Trình 4Template – Giới Thiệu 18 template T _getMax ( T so1 , T so2 ) { if ( so1 < so2 ) return so2; return so1; } int main() { PS ps1 , ps2 , psMax; psMax = _getMax ( ps1 , ps2 ) ; } Giới Thiệu Lập Trình