Kỹ thuật lập trình - Chương 1: Mở đầu

323 trang phuongnguyen 2500

Download

Bạn đang xem 20 trang mẫu của tài liệu "Kỹ thuật lập trình - Chương 1: Mở đầu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

ky_thuat_lap_trinh_chuong_1_mo_dau.pdf

Nội dung text: Kỹ thuật lập trình - Chương 1: Mở đầu

Kỹ thuật lập trình 1 g n Chương 1: Mở₫ầu 0101010101010101100001 ươ 01010101010101011000010101010101010101100001 StateController010101010010101010010101010101001010101001010101010100101010100101 start() 101001100011001001001010100110001100100100101010011000110010010010 Ch stop() 110010110010001000001011001011001000100000101100101100100010000010 010101010101010110000101010101010101011000010101010101010101100001 010101010010101010010101010101001010101001010101010100101010100101 N 101001100011001001001010100110001100100100101010011000110010010010y = A*x + B*u; Ơ 110010110010001000001011001011001000100000101100101100100010000010x = C*x + d*u; LQGController010101010101010110000101010101010101011000010101010101010101100001 start() 010101010010101010010101010101001010101001010101010100101010100101 stop() 101001100011001001001010100110001100100100101010011000110010010010 110010110010001000001011001011001000100000101100101100100010000010 8/14/2006 2004, HOÀNG MINH S ©
Nộidung bài giảng 1.1 Giới thiệunội dung môn học 1.2 Giới thiệu chung về kỹ thuật lập trình 1.3 Phương pháp luận 1.4 Qui trình phát triển phần mềm 1.5 Sơ lược về ngôn ngữ C/C++ N Ơ 2004, HOÀNG MINH S ương 1: Mởđầu 2 Ch ©
1.1 Nộidung môn học Các kỹ thuậtlập trình cơ bản, thựchiệnminhhoạ trên các ngôn ngữ lập trình C và C++: —Lậptrìnhcócấutrúc(structured programming) —Lậptrìnhhướng ₫ốitượng (object-oriented programming) —Lậptrìnhthờigianthực(real-time programming) —Lậptrìnhtổng quát (generic programming) Tạisaochọn C/C++: — Hai ngôn ngữ lậptrìnhtiêubiểunhất, ₫ủ ₫ể thựchiệncác kỹ thuậtlập trình quan trọng N Ơ — Hai ngôn ngữ lập trình quan trọng nhất ₫ốivớikỹ sư ₫iện/kỹ sư₫iềukhiển 2004, HOÀNG MINH S ương 1: Mởđầu 3 Ch ©
Quan ₫iểmvề môn học Đề cao kiếnthứccơ bản, nềntảng: —Thiênvề tư duy và phương pháp lậptrình —Tạokhả năng dễ thích ứng vớicácứng dụng khác nhau —Tạokhả năng dễ thích ứng với các ngôn ngữ lậptrình khác (Java, Visual Basic, C#, MATLAB ) —Nhấnmạnh tính chuyên nghiệp trong lập trình: hiệu quả + chấtlượng Những nộidung không có trong chương trình: —Lậptrìnhhệ thống (low-level system programming) —Lậptrình₫ồ họa N Ơ —Lậptrìnhgiaotiếpvớicácthiếtbị ngoại vi ( cổng nốitiếp, song song ) —Lậptrìnhcơ sở dữ liệu —Lậptrìnhthànhphần, lập trình phân tán (mạng, Internet) 2004, HOÀNG MINH S ương 1: Mởđầu 4 Ch ©
Phương pháp họctập Cách thứ nhất: Nghe giảng làm thử ₫ọctài liệu thảoluận luyệntập Cách thứ hai: Đọctàiliệu làm thử nghe giảng thảoluận luyệntập Nguyên tắccơ bản: Chủ₫ộng họcthường xuyên! Những ₫iều không nên làm: —Chépnhiềutrênlớp —Họcthuộclòng, họcchay N —Mong₫ợinhiềuvàoôntập Ơ —Dựadẫm vào các bài tậpmẫutrongsách 2004, HOÀNG MINH S ương 1: Mởđầu 5 Ch ©
Công cụ họctập Máy tính PC Môi trường lậptrình: Visual C++ 6.0 (Visual Studio 6.0), Visual C++ .NET, Borland C++ Builder Nền ứng dụng: Win32 Console Application Tài liệuthamkhảo. N Ơ 2004, HOÀNG MINH S ương 1: Mởđầu 6 Ch ©
1.2 Tổng quan về kỹ thuật lập trình Kỹ thuật lập trình là gì: Kỹ thuật thực thi một giải pháp phần mềm (cấu trúc dữ liệu + giải thuật) dựa trên nền tảng một phương pháp luận (methodology) và một hoặc nhiều ngôn ngữ lập trình phù hợp với yêu cầu ₫ặc thù của ứng dụng. Kỹ thuật lập trình = Tư tưởng thiết kế + Kỹ thuật mã hóa = Cấu trúc dữ liệu + Giải thuật + Ngôn ngữ lập trình Kỹ thuật lập trình N Ơ ≠ Phương pháp phân tích & thiết kế (A&D) 2004, HOÀNG MINH S ương 1: Mởđầu 7 Ch ©
Thế nào là lập trình? Viết chương trình tính Viết một hàm tính giai thừacủa 100! giai thừa! Viết chương trình in ra Viết chương trình in ra 100 số nguyên tố N số nguyên tố ₫ầu tiên! ₫ầu tiên! Lập trình giải bài toán: Lập trình giải bài toán: "Vừa gà vừa chó, "Vừa gà vừa chó, ba mươi sáu con, vừa vặn X con, bó lại cho tròn, bó lại cho tròn, N Ơ một trăm chân chẵn" ₫ủ Y chân chẵn" KHÔNG PHẢI LÀ LẬP TRÌNH! ĐÂY LÀ LẬP TRÌNH! 2004, HOÀNG MINH S ương 1: Mởđầu 8 Ch ©
Thế nào là lập trình tốt? Đúng/Chính xác —Thoả mãn ₫úng các nhiệm vụ bài toán lập trình ₫ặt ra, ₫ược khách hàng chấp nhận Ổn ₫ịnh và bền vững —Chương trình chạy ổn ₫ịnh trong cả những trường hợp khắc nghiệt —Chạy ít lỗi (số lượng lỗi ít, cường ₫ộ lỗi thấp) —Mức ₫ộ lỗi nhẹ có thể chấp nhận ₫ược Khả năng chỉnh sửa —Dễ dàng chỉnh sửa trong quá trình sử dụng và phát triển —Dễ dàng thay ₫ổi hoặc nâng cấp ₫ể thích ứng với ₫iều kiện N Ơ bài toán lập trình thay ₫ổi Khả năng tái sử dụng —Cóthể ₫ược sử dụng hoặc ₫ược kế thừa cho các bài toán lập trình khác 2004, HOÀNG MINH S ương 1: Mởđầu 9 Ch ©
Thế nào là lập trình tốt? Độ tương thích —Khả năng thích ứng và chạy tốt trong các ₫iều kiện môi trường khác nhau Hiệusuất —Chương trình nhỏ gọn, sử dụng ít bộ nhớ —Tốc ₫ộ nhanh, sử dụng ít thời gian CPU Hiệu quả: —Thời gian lập trình ngắn, —Khả năng bảo trì dễ dàng N Ơ —Giátrị sử dụng lại lớn —Sử dụng ₫ơn giản, thân thiện —Nhiều chức năng tiện ích 2004, HOÀNG MINH S ương 1: Mởđầu 10 Ch ©
Ví dụ minh họa: Tính giai thừa Viết chương trình hay xây dựng hàm? — Hàm tính giai thừa của một số nguyên int factorial(int N); Giải thuật: — Phương pháp ₫ệ quy (recursive) if (N > 1) return N*factorial(N-1); return 1; — Phương pháp lặp(iterative) N Ơ int kq = 1; while (N > 1) ☺„to iterate is human, kq *= N ; to recurse is device!“ return kq; 2004, HOÀNG MINH S ương 1: Mởđầu 11 Ch ©
Làm thế nào ₫ể lập trình tốt? Học cách tư duy và phương pháp lập trình —Tư duy toán học, tư duy logic, tư duy có cấu trúc, tư duy hướng ₫ối tượng, tư duy tổng quát —Tìm hiểu về cấu trúc dữ liệu và giải thuật Hiểu sâu về máy tính —Tương tác giữa CPU, chương trình và bộ nhớ —Cơ chế quản lý bộ nhớ Nắm vững ngôn ngữ lập trình —Biết rõ các khả năng và hạn chế của ngôn ngữ —Kỹ năng lập trình (₫ọc thông, viết thạo) N Ơ Tự rèn luyện trên máy tính —Hiểu sâu ₫ược các ₫iểm nêu trên —Rèn luyện kỹ năng lập trình —Thúc ₫ẩy sáng tạo 2004, HOÀNG MINH S ương 1: Mởđầu 12 Ch ©
Các nguyên tắc cơ bản Trừutượng hóa Chắtlọcranhững yếutố quan trọng, bỏ qua những chi tiếtkémquantrọng Đóng gói Che giấuvàbảovệ các dữ liệuquantrọng qua mộtgiao diệncókiểmsoát Module hóa Chia nhỏ₫ốitượng/vấn ₫ề thành nhiềumodule nhỏ₫ểdễ can thiệpvàgiảiquyết N Ơ Phân cấp Phân hạng hoặcsắpxếptrậttự₫ốitượng theo các quan hệ trên dưới 2004, HOÀNG MINH S ương 1: Mởđầu 13 Ch ©
Nguyên tắc tốicao „Keep it simple: as simple as possible, but no simpler!“ (Albert Einstein) N Ơ 2004, HOÀNG MINH S ương 1: Mởđầu 14 Ch ©
Các bài toán lập trình cho kỹ sư ₫iện Lập trình phần mềm ₫iều khiển (µC, PC, PLC, DCS) Lập trình phần mềm thu thập/quản lý dữ liệu quá trình Lập trình phần mềm giao diện người-máy (₫ồ họa) Lập trình phần mềm tích hợp hệ thống (COM, OPC, ) Lập trình phần mềm tính toán, thiết kế Lập trình phần mềm mô phỏng N Ơ Lập trình phần mềm tối ưu hóa 2004, HOÀNG MINH S ương 1: Mởđầu 15 Ch ©
1.3 Phương pháp luận Phương pháp: Cách thứctiếnhànhmộtcôngviệc ₫ể có hiệu quả cao Phương pháp luận: Mộttậphợp các phương pháp ₫ượcsử dụng hoặcbộ môn khoa họcnghiêncứu các phương pháp ₫ó Phương pháp luận phục vụ: —Phân tích hệ thống —Thiết kế hệ thống —Thực hiện —Thử nghiệm N Ơ — 2004, HOÀNG MINH S ương 1: Mởđầu 16 Ch ©
Lập trình tuần tự (Sequential Programming) Phương pháp cổ₫iểnnhất, bằng cách liệtkêcáclệnh kế tiếp, mứctrừutượng thấp Kiểmsoátdòngmạch thựchiệnchương trình bằng các lệnh rẽ nhánh, lệnh nhảy, lệnh gọichương trình con (subroutines) Ví dụ ngôn ngữ ₫ặc thù: —Ngônngữ máy, — ASSEMBLY N — BASIC Ơ — IL (Instruction List), STL (Statement List) — LD, LAD (Ladder Diagram) 2004, HOÀNG MINH S ương 1: Mởđầu 17 Ch ©
Lập trình tuần tự: Ví dụ tính giai thừa 1: MOV AX, n 2: DEC n 3: CMP n, 1 4: JMPI 5: MUL AX, n 6: JMP 2 7: MOV n, AX N Ơ 8: RET 2004, HOÀNG MINH S ương 1: Mởđầu 18 Ch ©
Lập trình tuần tự: Ưu ₫iểm và nhược ₫iểm Ưu ₫iểm: —Tư duy ₫ơn giản —Lậptrìnhở mứctrừutượng thấp, nên dễ kiểmsoátsử dụng tài nguyên —Cóthể có hiệusuấtcao —Cóthể thích hợp với bài toán nhỏ, lập trình nhúng, lập trình hệ thống Nhược ₫iểm: —Chương trình khó theo dõi -> dễ mắclỗi N —Khósử dụng lại Ơ —Hiệu quả lập trình thấp — Không thích hợp với ứng dụng qui mô lớn 2004, HOÀNG MINH S ương 1: Mởđầu 19 Ch ©
Lập trình có cấu trúc (structured programming) Cấu trúc hóa dữ liệu(xâydựng kiểudữ liệu) và cấu trúc hóa chương trình ₫ể tránh các lệnh nhảy. Phân tích và thiếtkế theo cách từ trên xuống (top- down) Thựchiệntừ dưới lên (bottom-up) Yêu cầu của chương trình có cấu trúc: chỉ sử dụng các cấutrúc₫iềukhiểntuầntự, tuyểnchọn ( if then else), lặp(while) vàthoátra(exit). N Ví dụ các ngôn ngữ ₫ặc thù: Ơ — PASCAL, ALGO, FORTRAN, C, — SFC (Sequential Funtion Charts) — ST (Structured Text) 2004, HOÀNG MINH S ương 1: Mởđầu 20 Ch ©
Lập trình có cấu trúc: Ví dụ tính giai thừa (PASCAL) FUNCTION Factorial(n: INTEGER) : INTEGER VAR X: INTERGER; BEGIN X := n; WHILE (n > 1) DO BEGIN DEC(n); X := X * n; END N Ơ Factorial := X; END END; 2004, HOÀNG MINH S ương 1: Mởđầu 21 Ch ©
Lập trình có cấu trúc: Ví dụ quản lý sinh viên struct Date { int Day, Month, Year; }; struct Student { string name; Date dob; int code; }; typedef Student* Students; // cấu trúc mảng Students create(int max_items, int item_size ); void destroy(Students lop); N void add(Students lop, Student sv); Ơ void delete(Students lop, Student sv); Student find(Students lop, int code); 2004, HOÀNG MINH S ương 1: Mởđầu 22 Ch ©
Lập trình module (modular programming) Lập trình module là mộtdạng cải tiếncủalập trình có cấu trúc. Chương trình ₫ượccấutrúcnghiêmngặthơn, dùng ₫ơn vị cấu trúc là module. Module: —Một ₫ơn vị cấutrúc₫ộclập, ₫ượcchuẩn hóa dùng ₫ể tạolập mộthệ thống. —Mỗi module bao gồm phần giao diện(mở) và phầnthựchiện (che giấu) — Các module giao tiếpvới nhau thông qua các giao diện ₫ược N ₫ặctả rấtchínhxác. Ơ Ví dụ ngôn ngữ tiêu biểu: — Modula-2, xây dựng trên cơ sở PASCAL, do Niclaus Wirth thiếtkế năm 1977. 2004, HOÀNG MINH S ương 1: Mởđầu 23 Ch ©
Lập trình hướng ₫ối tượng (Object-Oriented Programming) Xây dựng chương trình ứng dụng theo quan ₫iểm dựa trên các cấu trúc dữ liệu trừu tượng (lớp), các thể nghiệm của các cấu trúc ₫ó (₫ối tượng) và quan hệ giữa chúng (quan hệ lớp, quan hệ ₫ối tượng). Nguyên lý cơ bản: —Trừu tượng (abstraction) — Đóng gói dữ liệu (data encapsulation) —Dẫn xuất/thừa kế (subtyping/inheritance) — Đa hình/₫a xạ (polymorphism) N Ơ Ví dụ ngôn ngữ hỗ trợ tiêu biểu: — C++, C# — Java, —ADA, Ch2004, HOÀNG MINH S ương 1: Mởđầu 24 — ©
Ví dụ minh họa: Quản lý sinh viên (C++) class Date { int Day, Month, Year; public: void setDate(int, int, int); }; class Student { string name; Date dob; int code; public: Student(string n, Date d, int c); }; N class StudentList { Ơ Student* list; public: void addStudent(Student*); }; 2004, HOÀNG MINH S ương 1: Mởđầu 25 Ch ©
Ví dụ minh họa: Tính toán kiểu MATLAB Vector a(10, 1.0), b(10, 0.5); Vector c = a + b; Vector d = a - b + 2*c; Matrix A(4,4), B(4,2), C(2,4), D(2,2); Vector x(4),u(2),y(2); while (true) { // đọc đầu vào u y = C*x + D*u; x = A*x + B*u; N // đưa đầu ra y Ơ } CTFMatrix G = ss2tf(A,B,C,D); 2004, HOÀNG MINH S ương 1: Mởđầu 26 Ch ©
Lập trình tổng quát (generic programming) Một tư duy lập trình mở, trên quan ₫iểm tổng quát hóa tất cả những gì có thể nhằm ₫ưa ra một khuôn mẫu giải pháp cho nhiều bài toán lập trình cụ thể. Ưu ₫iểm: —Giảm tối ₫a lượng mã nguồn —Tăng nhiều lần giá trị sử dụng lại của phần mềm —Cóthể kết hợp tùy ý với các phương pháp luận khác —Tính khả chuyển cao Các hình thức tổng quát hóa: N Ơ —Kiểu dữ liệu — Phép toán cơ bản —Cấu trúc dữ liệu —Quản lý bộ nhớ, 2004, HOÀNG MINH S ương 1: Mởđầu 27 Ch ©
Ví dụ minh họa: Các cấu trúc toán học typedef TMatrix Matrix; typedef TMatrix > ComplexMatrix; Matrix a(4,4), b(4,4); Matrix c = a*b; ComplexMatrix a1(4,4), b1(4,4); ComplexMatrix c1 = a1*b1; typedef TPoly Poly; typedef TMatrix PolyMatrix; typedef TPoly ComplexMatrixPoly; N Ơ TRational IntRational; TRational PolyRational; 2004, HOÀNG MINH S ương 1: Mởđầu 28 Ch ©
Lập trình thành phần (component-based programming) Phương pháp xây dựng phần mềm dựa trên các thành phần "IC" có sẵn, hoặc tạo ra các IC ₫ó. Tiến hóa từ lập trình hướng ₫ối tượng Hầu hết các ứng dụng Windows và ứng dụng Internet ngày nay ₫ược xây dựng theo phương pháp luận này Các ngôn ngữ tiêu biểu —C/C++, C# — Delphi, Visual Basic N — Script, HMTL, XML, Ơ —FBD 2004, HOÀNG MINH S ương 1: Mởđầu 29 Ch ©
Lập trình thời gian thực (real-time programming) Xây dựng phầnmềm ₫áp ứng tính năng thờigian thực của hệ thống, ví dụ các hệ thống ₫iềukhiển Đặc thù: —Lập trình cạnh tranh (₫a nhiệm, ₫a luồng) —Cơ chế xử lý sự kiện —Cơ chế₫ịnh thời — Đồng bộ hóa quá trình —Hiệusuấtcao Ngôn ngữ lập trình: ASM, C/C++, ADA, N Ơ Cần sự hỗ trợ của nền cài ₫ặt —Hệ₫iềuhành —Nền phầncứng —Mạng truyềnthông 2004, HOÀNG MINH S ương 1: Mởđầu 30 Ch ©
1.4 Qui trình phát triển phầnmềm BÀI TOÁN ? GIẢI PHÁP THẾ GIỚI THỰC Phân tích Mã hóa Thử nghiệm THẾ GIỚI MÔ HÌNH MÔ HÌNH THIẾT KẾ N PHÂN TÍCH THIẾT KẾ Ơ Thiếtkế 2004, HOÀNG MINH S ương 1: Mởđầu 31 Ch ©
Tậphợp và phân tích yêu cầu Bởi vì: Khách hàng thường biết ₫ược là họ muốngì, nhưng không biết lập hoạch các yêu cầu Cho nên: Cầnphảicùng với khách hàng phân hoạch và làm rõ những yêu cầuvề phạm vi chứcnăng của bài toán Kếtquả: Mô hình ₫ặctả (Specification Model) ấn ₫ịnh và chỉ rõ yêu cầu của bài toán một cách tường minh theo một ngôn ngữ mô hình hóa rõ ràng, dễ hiểu ₫ể nhóm phân tích thiết kế lập trình thực hiện N Ơ Trả lời câu hỏi: Khách hàng cần những gì và nên làm gì? 2004, HOÀNG MINH S ương 1: Mởđầu 32 Ch ©
Phân tích hệ thống (System analysis) Phân tích mốiliên hệ của hệ thống vớimôi trường xung quanh Tìm ra cấutrúchệ thống và các thành phầnquan trọng Định nghĩachứcnăng cụ thể của các thành phần Nhận biết các ₫ặc ₫iểm của từng thành phần Phân loại các thành phần, tổng quát hóa, ₫ặc biệt hóa Nhận biếtmốiliên hệ giữacácthànhphần N Ơ Kết quả: Mô hình hệ thống (System model) Cần một ngôn ngữ mô hình hóa ₫ể trao ₫ổi giữa các thành viên trong nhóm phân tích và với nhóm thiết kế Trả lời câu hỏi: Những gì sẽ phải làm? 2004, HOÀNG MINH S ương 1: Mởđầu 33 Ch ©
Thiếtkế hệ thống (System Design) Dựa trên mô hình hệ thống, xây dựng các mô hình chi tiết phục vụ sẵn sàng mã hóa/cài ₫ặt Bao gồm: —Thiếtkế cấutrúc(structured design): chương trình, kiểu dữ liệu, ₫ối tượng, quan hệ cấu trúc giữa các ₫ối tượng và kiểu) —Thiết kế tương tác (interaction design): quan hệ tương tác giữa các ₫ối tượng —Thiếtkế hành vi (behaviour design): sự kiện, trạng thái, phép toán, phản ứng —Thiếtkế chứcnăng (funtional design): tiến trình hành ₫ộng, N Ơ hàm, thủ tục) Kếtquả: Mô hình thiếtkế (các bảnvẽ và lờivăn mô tả) Trả lờicâu hỏi: Làm như thế nào? 2004, HOÀNG MINH S ương 1: Mởđầu 34 Ch ©
Các bướckhác Mã hóa/cài ₫ặt (Coding/Implementation): Thể hiện mô hình thiếtkế với một ngôn ngữ lập trình cụ thể Thử nghiệm (Testing, Verification): Chạy thử, phân tích và kiểm chứng: —Thử ₫ơn vị (Unit Test) —Thử tích hợp (Integration Test) Gỡ rối (Debugging): Tìm ra và sửa các lỗi chương trình chạy (các lỗi logic) Xây dựng tài liệu (Documenting): Xây dựng tài liệu phát N Ơ triển, tài liệu hướng dẫn sử dụng Đào tạo, chuyển giao Bảo trì, bảo dưỡng 2004, HOÀNG MINH S ương 1: Mởđầu 35 Ch ©
Chu trình cổ₫iển: “Waterfall Model” NghiênNghiên ccứứuu khkhảảthithi PhânPhân tíchtích yêuyêu ccầầuu ThiThiếếtt kkếế MãMãhóahóa ThThửửnghinghiệệmm đơđơnn vvịị ThThửửnghinghiệệmm tíchtíchhhợợpp ĐĐàoàottạạoo N Ơ ChuChuyyểểngngiaiaoo BBảảototrrìì 2004, HOÀNG MINH S ương 1: Mởđầu 36 Ch ©
Lập trình là gì, nằm ở₫âu? Lập trình > Mã hóa Lập trình ≈ Tư tưởng thiếtkế + Mã hóa + Thử nghiệm + Gỡ rối N Ơ 2004, HOÀNG MINH S ương 1: Mởđầu 38 Ch ©
Các bướcpháttriển chương trình Mã nguồn Biên dịch Mã đích Liên kết Thư viện N Ơ CT chạy được Nạp và chạy 2004, HOÀNG MINH S ương 1: Mởđầu 39 Ch ©
Môi trường/công cụ phát triển IDE (Integrated Development Environment) —Hỗ trợ toàn bộ các bướcpháttriểnchương trình —Vídụ: MS Visual C++, Borland C++ (Builder), Keil-C Các công cụ tiêu biểu —Trìnhsoạnthảo(Editor) —Trìnhbiêndịch (Compiler) —Trìnhliênkết(Linker) —Trìnhnạp (Loader) —Trìnhgỡ rối (Debugger) N —Trìnhquảnlýdự án (Project Manager) Ơ 2004, HOÀNG MINH S ương 1: Mởđầu 40 Ch ©
1.5 Sơ lượcvề C/C++ Lượcsử ngôn ngữ C Tiến hóa từ hai ngôn ngữ lậptrình — BCPL và B: Các ngôn ngữ “phi kiểu” Dennis Ritchie (Bell Laboratories, AT&T) —Bổ sung kiểuhóadữ liệuvàcácyếutố khác Ngôn ngữ phát triểnhệ₫iềuhànhUNIX Không phụ thuộcphầncứng —Tínhkhả chuyển N Ơ 1989: ANSI chuẩn hóa (ANSI-C) 1990: Công bố chuẩn ANSI và ISO — ANSI/ISO 9899: 1990 2004, HOÀNG MINH S ương 1: Mởđầu 42 Ch ©
Lượcsử ngôn ngữ C++ Mở rộng, tiến hóa từ C Bjarne Stroustrup (Bell Laboratories) — Đầunhững năm 1980: “C with classes” — 1984: Tên C++ — 1987: “The C++ Programming Language” 1st Edition — 1997: “The C++ Programming Language” 3rd Edition —Chuẩnhóaquốctế: ANSI/ISO 1996 Bổ sung các ₫ặctínhhỗ trợ: —Lậptrìnhhướng ₫ốitượng N Ơ —Lậptrìnhtổng quát —Lậptrìnhtoánhọc, Ngôn ngữ “lai” 2004, HOÀNG MINH S ương 1: Mởđầu 43 Ch ©
Tạisao chọnC/C++ Đáp ứng các yêu cầu: —Gầngũivớiphầncứng —Hiệu suất cao —Tương ₫ối thân thiện vớingườilập trình —Khả chuyển —Chuẩn hóa quốc tế (tương lai vững chắc) Thế mạnh tuyệt ₫ối của ANSI-C: —Phổ biến cho hầu hết các nền vi xử lý, vi ₫iều khiển, DSP —Phổ biến cho “mỗi người lập trình” trên thế giới N Ơ Thế mạnh tuyệt ₫ối của ANSI/ISO C++: —Lập trình hướng ₫ối tượng —Lập trình tổng quát (template) —Lập trình toán học (dữ liệutrừutượng và nạp chồng toán tử) 2004, HOÀNG MINH S ương 1: Mởđầu 44 Ch ©
Visual C++, .NET & C# Visual C++: —Môitrường/công cụ lậptrìnhC++ củaMicrosoft —Mở rộng mộtsố yếutố —Thư việnlập trình Windows: Microsoft Foundation Classes (MFC), Active Template Library (ATL) —Cácthư viện chung: GUI, graphics, networking, multithreading, .NET (“dot net”) —Kiếntrúcnềntảng phầnmềmlập trình phân tán —Hướng tớicácứng dụng Web, phân tán trên nhiềuchủng N Ơ loạithiếtbị khác nhau —Cácứng dụng trên nhiềungônngữ khác nhau có thể giao tiếpmộtcách₫ơngiảntrênmộtnền chung —Phương pháp luận: Lậptrìnhthànhphần 2004, HOÀNG MINH S ương 1: Mởđầu 45 Ch ©
Visual C++, .NET & C# C# — Anders Hejlsberg và Scott Wiltamuth (Microsoft) —Thiếtkế riêng cho nền.NET —Nguồngốctừ C, C++ và Java — Điều khiểntheosự kiện, hoàn toàn hướng ₫ốitượng, ngôn ngữ lập trình hiểnthị — Integrated Development Environment (IDE) —Tương tác giữa các ngôn ngữ N Ơ 2004, HOÀNG MINH S ương 1: Mởđầu 46 Ch ©
Chúng ta ₫ãhọc ₫ượcnhững gì? Biết ₫ượcnhững gì sẽ phảihọc, học ₫ể làm gì và phảihọcnhư thế nào Hàng loạtkháiniệmmới xung quanh kỹ thuậtlập trình và qui trình công nghệ phầnmềm Tổng quan về các kỹ thuậtlậptrình Lượcsử ngôn ngữ C/C++, thế mạnh của chúng so N với các ngôn ngữ khác Ơ 2004, HOÀNG MINH S ương 1: Mởđầu 47 Ch ©
Chủ₫ềtiếptheo:C/C++ cơ sở Tổ chứcchương trình/bộ nhớ Dữ liệuvàbiến Toán tử, biểuthứcvàcâulệnh Điềukhiểnchương trình: vòng lặp, rẽ nhánh Mảng và con trỏ Cấutrúc N Ơ 2004, HOÀNG MINH S ương 1: Mởđầu 48 Ch ©
Kỹ thuật lập trình 1 g n Chương 2: Các yếutố cơ bản ươ 010101010101010110000101010101010101011000010101010101010101100001 StateController010101010010101010010101010101001010101001010101010100101010100101 start() 101001100011001001001010100110001100100100101010011000110010010010 Ch củaC vàC++ stop() 110010110010001000001011001011001000100000101100101100100010000010 010101010101010110000101010101010101011000010101010101010101100001 N Ơ 010101010010101010010101010101001010101001010101010100101010100101 101001100011001001001010100110001100100100101010011000110010010010y = A*x + B*u; 110010110010001000001011001011001000100000101100101100100010000010x = C*x + d*u; LQGController010101010101010110000101010101010101011000010101010101010101100001 start() 010101010010101010010101010101001010101001010101010100101010100101 stop() 101001100011001001001010100110001100100100101010011000110010010010 110010110010001000001011001011001000100000101100101100100010000010 8/19/2006 2004, HOÀNG MINH S ©
Nộidung chương 2 2.1 Tổ chứcchương trình C/C++ 2.2 Biếnvàcáckiểudữ liệucơ bản 2.3 Các kiểudữ liệudẫnxuấttrựctiếp 2.4 Định nghĩakiểudữ liệumới 2.5 Điềukhiểnchương trình: phân nhánh 2.6 Điềukhiểnchương trình: vòng lặp 2.7 Mộtsố lệnh ₫iềukhiểnchương trình khác N Ơ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 2 Ch ©
2.1 Tổ chức chương trình C/C++ Cấutrúcvàcácphầntử cơ bảncủamộtchương trình viếttrênC/C++ Qui trình tạoramộtchương trình chạy ₫ược: —Vấn ₫ề tạodự án —Qui tắcsoạnthảomãnguồn —Biêndịch từng phầnvàsửacácloạilỗibiêndịch —Liênkếtvàsử dụng thư viện, sửalỗiliênkết —Chạythử và gỡ rối(Debug) Sơ lượcvề tổ chứcbộ nhớ N Ơ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 3 Ch ©
2.1 Tổ chức chương trình C/C++ # Tiền xử lý Khai báo thư viện và macro Khai báo biến, hàm Khai báo hàm ₫ược sử dụng trong CT chính void main() { Chương trình (CT) Chương trình chính Thân hàm chính N Ơ } Định nghĩa thân hàm ₫ã Định nghĩa hàm (thân hàm) khai báo 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 4 Ch ©
Chương trình tính giai thừa: Phiên bảnC #include #include int factorial(int); void main() { char c = 'N'; int N = 1; int kq; do { printf(“\nEnter a number > 0:"); /* writing on the screen */ scanf("%d",&N); /* reading from keyboard to N */ kq = factorial(N); /* calling function with argument N */ printf(“\nFactorial of %d is %d", N, kq); /*write result on screen */ printf(“\nPress 'Y' to continue or any other key to stop"); c = getch(); /* reading a character from keyboard*/ } while (c=='y' || c=='Y'); /* checking loop condition */ N }Ơ int factorial(int n) { int kq = 1; while (n > 1) kq *= n ; return kq; } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 5 Ch ©
Chương trình tính giai thừa: Phiên bảnC++ #include #include int factorial(int); void main() { char c = 'N'; int N = 1; do { cout 0:“ // writing on the screen cin >> N; // reading from keyboard to N int kq = factorial(N); // calling function with argument cout 1) kq *= n ; return kq; } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 6 Ch ©
Bổ sung file mã nguồn 5 và soạnthảo Các công cụ biên dịch và liên kết Cửasổ soạnthảo Cửasổ bàn làm việc/ dự án N Ơ Cửasổ thông báo kếtquả (biên dịch, ) 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 8 Ch ©
Qui tắcsoạnthảomãnguồn 1. Tên biến, tên hàm, tên kiểumới: Tránh sử dụng các từ khóa và tên kiểucơ sở Các ký tự dùng ₫ược: ‘A’ ’Z’, ‘a’ ’z’, ‘0’ ’9’, ‘_’ Phân biệtgiữachữ hoavàchữ thường: n khác N Ngắnnhưng ₫ủ khả năng phân biệt, gợinhớ₫ểnhậnbiết Sử dụng tiếng Anh hoặctiếng Việt không dấu(kể cả dòng chú thích) 2. Sau mỗicâulệnh có chấmphảy; 3. Đoạn{ } ₫ược coi là nhóm lệnh, không có dấu chấmphảysau₫ó, trừ trường hợp khai báo kiểu N 4.Ơ Cấutrúcmãnguồntheokiểuphâncấp => dễ₫ọc 5. Bổ sung chú thích ₫ầy ₫ủ, hợp lý (/* */ hoặc //) 6. Chia mộtfile lớn thành nhiềufile nhỏ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 9 Ch ©
Các từ khóa trong C auto double int struct break else long switch case enum register typedef char extern return union const float short unsigned continue for signed void default goto sizeof volatile do if static while N Ơ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 10 Ch ©
Từ khóa trong C++ asm auto bool break case catch char class const const_cast continue default delete else extern do enum false double explicit float dynamic_cast export for friend goto if inline int long mutable namespace new operator private protected public register reinterpret_cast return short signed sizeof static static_cast struct switch template N thisƠ throw true try typedef typeid typename union unsigned using virtual void volatile wchar_t while 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 11 Ch ©
Biên dịch (compile) Biên dịch từng file nguồnriêngbiệt (*.c: C compiler, *.cpp: C++ compiler), kếtquả => *.obj Trong Visual C++: Gọi Compile (Ctrl + F7) ₫ể biên dịch riêng rẽ hoặc Build (F7) ₫ể kếthợpbiêndịch và liên kếtchotoànbộ dự án Các kiểulỗibiêndịch (compile error): —Lỗicúpháp: Sử dụng tên sai qui ₫ịnh hoặcchưa khai báo, thiếu dấuchấmphảy ;, dấu ₫óng } —Lỗikiểu: Các số hạng trong biểuthứckhôngtương thích kiểu, gọi hàm vớithamsố sai kiểu — N Ơ Các kiểucảnh báo biên dịch (warning): —Tự₫ộng chuyển ₫ổikiểulàmmất chính xác — Hàm khai báo có kiểutrả về nhưng không trả về —Sử dụng dấu = trong trường hợpnghivấnlàso sánh== — 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 12 Ch ©
Liên kết (link) MyProg.obj MyLib1.obj MyLib2.obj xx.obj yy.lib MyProg.exe Liên kết là quá trình ghép nhiềufile ₫ích (*.obj, *.lib) ₫ể tạora chương trình chạycuối cùng *.exe Trong Visual C++: Gọi Build (F7) Lỗi liên kếtcóthể là do: N —Sử dụng hàm nhưng không có ₫ịnh nghĩahàm Ơ —Biếnhoặchàm₫ược ₫ịnh nghĩa nhiềulần — 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 13 Ch ©
Chạythử và gỡ rối (debug) Chạythử trong Visual C++: Execute hoặc Ctrl+F5 Tìm lỗi: —Lỗi khi chạylàlỗithuộcvề phương pháp, tư duy, thuậttoán, không phảivề cú pháp —Lỗi khi chạybìnhthường không ₫ược báo —Lỗi khi chạyrất khó phát hiện, vì thế trong ₫asố trường hợp cầntiếnhànhdebug. Chạy Debug trong Visual C++: —Chạytớichỗ₫ặt cursor: Ctrl+F10 —Chạytừng dòng lệnh: F10 N Ơ —Chạyvàotronghàm: F11 —Chạytiếpbìnhthường: F5 —Xemkếtquả dướicửasổ Output hoặcgọiQuickWatch 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 14 Ch ©
Tổ chứcbộ nhớ Hệđiều hành Các CT khác Mã chương trình Đỉnh ngănxếp SP Dữ liệu toàn cục n Matran_A Vùng nhớ tự do f Ngănxếp k N Ơ (tham biến, biến i cụcbộ) count a Vùng nhớ tự do 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 15 Ch ©
2.2 Biếnvàdữ liệu Biểuthức= dữ liệu + phép toán + Biểudiễndữ liệu: Thông qua biến hoặc hằng số, kèm theo kiểu Nội dung trong phầnnày: —Cáckiểudữ liệucơ bản — Các phép toán áp dụng —Tương thích và chuyển ₫ổikiểu — Khai báo biến, phân loạibiến N Ơ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 16 Ch ©
2.2.1 Các kiểudữ liệu cơ bảncủaC/C++ KiểuKíchcỡ thông dụng Phạmvi tốithiểu (tính bằng bit) char 8 −127 to 127 signed char 8 −127 127 unsigned char 8 0 255 int 16/32 −32767 32767 signed int 16/32 -nt- unsigned int 16/32 0 65535 short 16 −32767 32767 signed short 16 nt unsigned short 16 0 65535 long 32 −2147483647 2147483647 signed long 32 - nt- unsignedN long 32 0 4294967295 floatƠ 32 Độ chính xác 6 chữ số double 64 Độ chính xác 15 chữ số long double 80 Độ chính xác 17 chữ số bool (C++) - - wchar_t (C++) 16 −32767 32767 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 17 Ch ©
Các phép toán cơ bản Phép toán Ký hiệuKiểu nguyên Kiểusố thựcKiểu bool Gán = XXX Số học +, -, *, /, XXx +=, -=, *=, /= %, %= Xx ++, Xx So sánh >, =, >, >= Xx Lựachọn ? : XXX Lũythừa? Không có! 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 18 Ch ©
Tương thích và chuyển ₫ổikiểu Tương thích kiểu=> Tự₫ộng chuyển ₫ổikiểu —Giữacáckiểusố nguyên vớinhau(lưuý phạm vi giá trị) —Giữacáckiểusố thựcvớinhau(lưuý ₫ộ chính xác) —Giữacáckiểusố nguyên và số thực(lưuý phạm vi giá trị và ₫ộ chính xác) —Kiểu bool sang số nguyên, số thực: true => 1, false => 0 —Số nguyên, số thựcsang kiểu bool: ≠ 0 => true, 0 => false Nếucólỗihoặccảnh báo => khắcphụcbằng cách ép chuyển ₫ổikiểu: —VD: N Ơ i = int(2.2) % 2; j = (int)2.2 + 2; // C++ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 19 Ch ©
Nhìn nhận về chuyển ₫ổikiểu long long double int double short float char bool N Ơ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 20 Ch ©
Nhìn nhận về chuyển ₫ổikiểu long long double double int short float N Ơ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 21 Ch ©
2.2.2 Khai báo biến char c = 'N'; Khai báo và khởitạogiátrị bool b = true; int kq; Chỉ khai báo, giá trị bất ₫ịnh double d; long count, i=0; Khai báo kếthợp, chỉ i=0 unsigned vhexa=0x00fa; Đặtgiátrị₫ầu hexa unsigned voctal=082; Đặtgiátrị₫ầu octal -> 66 chứ không phải 82 C: Toàn bộ biếnphải khai báo ngay ₫ầuthânhàm C++: Có thể khai báo tạichỗ nào cần, trước khi sử dụng Phân loạibiến: —Biếntoàncục: Khai báo ngoài hàm, lưugiữ trong vùng nhớ dữ liệu N Ơ chương trình —Biếncụcbộ: Khai báo trong thân hàm, lưugiữ trong ngănxếp —Thambiến: Khai báo trên danh sách tham số củahàm, lưugiữ trong ngănxếp 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 22 Ch ©
Ví dụ khai báo các loạibiến Biếntoàncục int N = 1; void main() { char c = 'N'; do { printf(“\nEnter a number > 0:"); scanf("%d",&N); Biếncụcbộ int kq = factorial(N); // C++ only! } while (c == 'y' || c == 'Y') Hai biếncụcbộ } cùng tên ở hai phạm int factorial(int n) { vi khác nhau, int kq = 1; khôngliênquangì while (n > 1) ₫ếnnN hau! kq *= n ; Ơ return kq; } Tham biến 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 23 Ch ©
Đặctínhlưugiữ Biến extern: Khai báo sử dụng biếntoàncục ₫ã ₫ược ₫ịnh nghĩavàgángiátrị trong mộttập tin khác /* file1.c */ /* file2.c */ int x, y; extern int x, y; char ch; extern char ch; void main() void func22() { { /* */ x = y / 10; } } void func1(void) void func23() { { x = 123; y = 10; } } N Ơ Biến static: ₫ượclưutrữ trong bộ nhớ dữ liệuCT —Biếnstatic cụcbộ: hạnchế truy nhậptừ bên ngoài hàm —Biến static toàn cục: hạnchế truy nhậptừ file khác 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 24 Ch ©
2.2.3 Hằng số (trựckiện) KiểuVídụ int 1 123 21000 −234 0x0A 081 long int 35000L −34l −234L 0x0AL 081L unsigned int 10000U 987u 40000u float 123.23F 4.34e−3f .1f double 123.23 1.0 −0.9876324 .1e−10 long double 1001.2L char ‘A’ ‘B’ ‘ ‘ ‘a’ ‘\n’ ‘\t’ ‘\b’ bool true false N Ơ wchar_t L’A’ L’B’ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 25 Ch ©
2.3 Các kiểudữ liệu dẫnxuấttrựctiếp Kiểuliệtkê Kiểuhằng Kiểucon trỏ Kiểumảng Kiểuthamchiếu (C++) N Ơ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 26 Ch ©
2.3.1 Kiểuliệtkê(enum) Mục ₫ích sử dụng: — Định nghĩamộtkiểulàtậpcáchằng số nguyên kí hiệu —Sử dụng thuậntiệnbằng tên => hằng số nguyên Ví dụ enum Color {Red, Green, Blue}; enum WeekDay { Mon = 2, Tue, Wed, Thu, Fri, Sat, Sun = 1 }; enum { DI_MOTOR1_STARTED = 0x01, DI_MOTOR1_RUNNING = 0x02, DI_MOTOR2_STARTED = 0x04, N Ơ DI_MOTOR2_RUNNING = 0x08, DI_PUMP1_STARTED = 0x10, DI_PUMP1_RUNNING = 0x20, DI_OVERLOADED = 0x40, DI_VALVE1_OPENED = 0x80 }; 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 27 Ch ©
Sử dụng kiểuliệtkê /* C version */ void main() { enum Color c = Red; /* c = 0 */ C: enum WeekDay d = Tue; /* d = 3 */ Như mộtkiểusố int i=c, j=d; /* j=0, i=3 */ enum Color c2 = i+1; /* c2 = 1 */ nguyên 8 bit int di1 = 0x01; /* OK, but */ int di2 = DI_MOTOR1_STARTED;/* this is better */ ++c; /* c = 1 */ } // C++ version */ void main() { C++ enum Color c = Red; // c = Red Không còn như WeekDay d = Tue; // OK, d = Tue mộtkiểusố int i=c, j=d; // i=0, j=3 N nguyên! Ơ Color c2 = i+1; // Error! Color c3 = Color(i+1); // OK, c3 = Green int di1 = 0x01; // OK, but int di2 = DI_MOTOR1_STARTED;// this is better ++c; // Error! } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 28 Ch ©
2.3.2 Kiểuhằng (const) Cho phép khai báo như biếnsố, nhưng ₫ượcgángiá trị cố₫ịnh bằng mộthằng số và không thể₫ượcthay ₫ổi => khai báo hằng số void main() { const double pi = 3.1412; // initializing is OK! const int ci = 1; // initializing is OK! ci = 2; // error! ci = 1; // error, too! int i = ci; // const int is a subset of int N const Color cc = Red; Ơ cc = Green; // error const double d; // potential error } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 29 Ch ©
2.3.3 Kiểucon trỏ Con trỏ thựcchấtlàmộtbiếnchứa ₫ịachỉ củamột ₫ốitượng có thể là mộtbiếnhoặcmộthàm. int v = 2; int* p = &v; // p holds the address of v Con trỏ p Vùng nhớ chứa biến CT 0x000127c3 p: &v v: 2 N Ơ chứa ₫ịa chỉ của biến v 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 30 Ch ©
2.3.3 Kiểucon trỏ int i = 1; int* p = &i;// p holds the address of i *p = 2; // i = 2 int j; p = &j; // now p holds the address of j *p = 3; // j = 3, i remains 2 N Ơ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 31 Ch ©
Ví dụ sử dụng kiểucon trỏ void main() { int i = 0; int* p = &i; // p refers to the addesss of i int j = *p; // j = 0 *p = 2; // now i = 2 p = &j; // now p contains the addess of j *p = 3; // now j = 3, i remains 2 double d = i; // OK, int is compatible to double p = &d; // error, int* isn’t compatible to double* p = (*int)&d; // no compile error, but dangerous, // meaningles type conversion! double* pd=0; // p contains the address 0 *pd = 0; // no compile error, but fatal error pd = &d; // OK N Ơ double* pd2; // p refers to an uncertain address *pd2 = 0; // fatal error pd2 = &d; // OK, pd and pd2 refer to the same addr. } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 32 Ch ©
Tóm tắtsơ bộ về con trỏ Con trỏ là mộtbiếnchứa ₫ịachỉ byte ₫ầucủamộtbiếndữ liệu, ₫ượcsử dụng ₫ể truy cậpgiántiếpdữ liệu ₫ó Sau khi khai báo mà không khởitạo, mặc ₫ịnh con trỏ mang một ₫ịachỉ bất ₫ịnh Địachỉ con trỏ mang có thể thay ₫ổi ₫ược => con trỏ có thể mỗi lúc ₫ạidiệnchomộtbiếndữ liệu khác Toán tử lấy ₫ịachỉ củamộtbiến(&) trả về con trỏ vào kiểucủa biến=> thường gán cho biếncon trỏ Toán tử truy nhậpnộidung (*) ápdụng cho con trỏ trả về biến mà con trỏ mang ₫ịachỉ => có thể₫ọchoặcthay₫ổi giá trị của biến ₫ó N Ơ Không bao giờ sử dụng toán tử truy nhậpnội dung, nếucon trỏ chưamangmột ₫ịachỉ ô nhớ mà chương trình có quyềnkiểm soát 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 33 Ch ©
2.3.4 Kiểumảng Chỉ số 012 N-1 ₫ịachỉ₫ầu ₫ịachỉ cuối ₫ịachỉ₫ầu-₫ịachỉ cuối = N * kích cỡ mộtphầntử Cấutrúcdữ liệuvới: —Số lượng các phầntử cố₫ịnh —Cácphầntử có cùng kiểu N Ơ —Cácphầntử₫ượcsắpxếpkế tiếptrongbộ nhớ —Cóthể truy nhậptừng phầntử mộtcáchtự do theo chỉ số hoặc theo ₫ịachỉ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 34 Ch ©
Khai báo mảng Số phầntử củamảng phảilàhằng số nguyên (trong C phảilàmộttrựckiện, trong C++ có thể là kiểu const ) Khai báo không khởitạo: int a[3]; enum {index = 5}; double b[index]; const int N = 2; char c[N]; // C++ only Khai báo vớisố phầntử và khởitạo giá trị các phầntử N Ơ int d[3]= {1, 2, 3}; double e[5]= {1, 2, 3}; char f[4]= {0}; 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 35 Ch ©
Khai báo mảng (tiếp) Khai báo và khởitạogiátrị các phần tử, số phầntử₫ượctự₫ộng xác ₫ịnh int a[]= {1, 2, 3, 4, 5}; double b[]= {1, 2, 3}; double c[]= {0}; char s[]= {‘a’}; Khai báo mảng nhiềuchiều double M[2][3]; int X[2][]={{1,2},{3,4},{5,6}}; short T[2][2]={1,2,3,4,5,6}; N Ơ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 36 Ch ©
Ví dụ sử dụng kiểumảng void main() { int a[5]; // a has 5 elements with uncertain values int b[5]= {1,3,5,7,9}; // 5 elements with initial values double c[]; // error, unspecified size double x = 1.0, y = 2.0; double d[]= {x,y,3.0}; // 3 elements with initial values short n = 10; double v[n]; // error, array size must be a constant! const int m=10; // C++ OK double v2[m]; // C++ OK a[0] = 1; int i= 1; a[i] = 2; a[5] = 6; // no compile error, but fatal error int k = a[5]; // no compile error, but fatal error N a = {1,2,3,4,5}; // error Ơ a = b; // error, cannot assign array int M[2][3]; M[0][1] = 0; M[0][2] = 1; } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 37 Ch ©
Mảng ₫ặcbiệt: Chuỗikýtự Trong C/C++, chuỗikýtự không phảilà kiểucơ bản, mà thựcchấtlàmộtmảng Phân biệtchuỗikýtự thường và chuỗiký tự kết0 char city1[]= {'H','A','N',' ','O','I‘}; char city2[]= "HA NOI"; wchar_t city3[]= L"HÀ NOI"; city2[] = “HANOI”; // error Đasố các hàm trong thư việnC làmviệc N Ơ vớichuỗikýtự kết0 Với C++, chuỗikýtự₫ược ₫ịnh nghĩabằng lớp string trong thư việnchuẩn, không sử dụng byte kết0 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 38 Ch ©
Mảng và con trỏ void main() { int a[5]; // a has 5 elements with // uncertain values int* p; p = a; // p refers to a[0] p = &a[0]; // the same as above *p = 1; // a[0]=1 ++p; // now p points to a[1] *p = 2; // a[1]=2 p++; // now p points to a[2] *p = 3; // a[2]=3 p += 2; // now p points to a[4] *p = 5; // a[4] = 5 N Ơ ++p; // OK, no problem until we dereference it *p = 6; // Now is a BIG BIG problem! a = p; // error, a is like a constant pointer } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 39 Ch ©
Mảng và con trỏ (tiếp) void main() { int a[5]; // a has 5 elements with // uncertain values int* p = a; // p points to a[0] p[0] = 1; // a[0]=1 p[1] = 2; // a[1]=2 p+= 2; // now p points to a[2] p[0] = 3; // a[2]=3 p[1] = 4; // a[3]=4 p[3] = 6; // a[5]=6, Now is a BIG BIG problem! } N Ơ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 40 Ch ©
Tóm lượcvề mảng Mảng là mộttậphợpcácdữ liệu cùng kiểu, sắpxếpliềnkề trong bộ nhớ => các phầntử củamảng Có thể truy cập các phầntử mảng vớibiếnmảng kèm theo chỉ số hoặcvớibiếncon trỏ (theo ₫ịachỉ củatừng phầntử) Số phầntử củamảng là cố₫ịnh (khi khai báo phảilàhằng số), không bao giờ thay ₫ổi ₫ược Biếnmảng (tĩnh) thựcchấtlàmộtcon trỏ hằng, mang ₫ịachỉ củaphầntử₫ầutiên Có thể₫ặt giá trị₫ầuchocácphầntử củamảng qua danh sách khởitạo, không bao giờ gán ₫ượcmảng cho nhau. Nếucầnsao chép hai mảng thì phảisử dụng hàm Không bao giờ₫ượcphéptruynhậpvớichỉ số nằm ngoài phạm N vi, nếuN làsố phầntử thì phạm vi cho phép là từ 0 N-1 Ơ Con trỏ không bao giờ là mộtmảng, nó chỉ có thể mang ₫ịachỉ củamộtmảng và sử dụng ₫ể quảnlýmảng (dù là ₫ộng hay tĩnh) 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 41 Ch ©
2.3.5 Kiểu tham chiếu (C++) Một biếnthamchiếulàmột biến ₫ạidiện trực tiếpcho một biến khác (thay cho con trỏ) Ýnghĩasử dụng chủ yếuvề sau trong truyềnthamsố cho hàm void main() { double d = 2.0; double& r = d; // r represents d double *p1 = &d, *p2 = &r; r = 1.0; // OK, d = 1.0 double& r2; // error, r has to be assigned to a var. N Ơ double& r3 = 0; // error, too double d2 = 0; r = d2; // r = 0, d=0 r = 1.0; // r = d = 1, d2 =0 } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 42 Ch ©
2.3.6 Typedef Từ khóa typedef tạoramột tên mớichomộtkiểucó sẵn, không ₫ịnh nghĩamộtkiểumới Ý nghĩa: ₫ưa tên mớidễ nhớ, phù hợpvới ứng dụng cụ thể, dễ thay ₫ổivề sau typedef float REAL; typedef int AnalogValue; typedef int Vector[10]; typedef AnalogValue AnalogModule[8]; typedef int* IPointer; N AnalogValue av1 = 4500; Ơ Vector x = {1,2,3,4,5,6,7,8,9,10}; AnalogModule am1 = {0}; IPointer p = &av1; 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 43 Ch ©
2.4 Định nghĩa kiểudữ liệumới Cấutrúc(struct): Tậphợpnhững dữ liệuhỗnhợp, truy nhập theo tên (biếnthànhviên). Thôngdụng nhất trong C, ý nghĩa ₫ượcmở rộng trong C++ Hợpnhất(union): Mộttênkiểu chung cho nhiềudữ liệu khác nhau (chiếmcùngchỗ trong bộ nhớ). Ít thông dụng trong cả C và C++ Lớp(class): Chỉ có trong C++, mở rộng struct cũ thêm những hàm thành viên. N Ơ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 44 Ch ©
2.4.1 Cấutrúc(struct) Định nghĩacấutrúc(bêntronghoặc ngoài các hàm) struct Time Tên kiểumới { (không trùng lặp) int hour; // gio int minute; // phut int second; // giay }; Các biến thành viên, struct Date { khai báo ₫ộclập int day, month, year; hoặc chung kiểu }; N Các biến thành viên Ơ struct Student { char name[32]; có thể cùng kiểu struct Date birthday; hoặc khác kiểu C++ int id_number; }; 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 45 Ch ©
Khai báo biếncấutrúc void main() { Time classTime = {6,45,0}; Time lunchTime = {12}; Date myBirthday, yourBirthday = {30,4,1975}; Student I = {"Nguyen Van A", {2,9,1975}}; // N Ơ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 46 Ch ©
Sử dụng biếncấutrúc / void main() { Time classTime = {6,45,0}; Time lunchTime = {12}; Date myBirthday, yourBirthday = {30,4,1975}; Student I = {"Nguyen Van A", {2,9,1975}}; lunchTime.minute = 15; lunchTime.hour = classTime.hour + 6; Student U = I; // in C++ also possible: Student U(I); U.name[11] = 'B'; // "Nguyen Van B" U.id_number++; // 1 N Ơ U.birthday.day = 30; // 30-9-1975 U.birthday.month = 4; // 30-4-1975 U.birthday = yourBirthday; // structs can be assigned } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 47 Ch ©
Phảnvídụ: khaibáovàsử dụng cấutrúc struct Time { int hour = 0; // error, initialization not allowed int minute, // error, use semicolon (;) instead int second // error, missing semicolon (;) } // error, missing semicolon (;) // void main() { Date d; d = {11,9,2001}; // error, { } is an initialization // list,not a structure Date.hour = 0; // error, Date is a type, not a var. N Ơ struct Date2 { int day, month, year; }; Date2 d2 = d; // error, Date is not compatible to Date2 } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 48 Ch ©
Mảng, con trỏ và cấutrúc Kếthợpmảng, con trỏ và cấutrúcchophépxâydựng và sử dụng các cấutrúcdữ liệuphứctạpmộtcáchrất linh hoạt void main() { // Date victoryDays[]= {{19,8,1945},{7,5,1954},{30,4,1975}}; Date saigonVictory= victoryDays[2]; Date *p=&saigonVictory; (*p).year += 30; // good p->year -=30; // better Student studentList[45]; for (int i=0; i id_number += 4800; ++pList; } } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 49 Ch ©
Tóm lượcvề cấutrúc(struct) Cấu trúc (struct) ₫ượcsử dụng ₫ể nhóm các dữ liệuliênquan mô tả một ₫ốitượng, các dữ liệucóthể cùng hoặc khác kiểu Định nghĩakiểucấutrúcbằng cách khai báo tên các biến thành viên. Định nghĩakiểucấutrúcchưaphảilà₫ịnh nghĩa các biếncụ thể, vì thế không ₫ược ₫ặt giá trị₫ầuchocácbiến Kích cỡ củacấutrúc>= tổng kích cỡ các thành viên Truy cậpmộtbiếncấu trúc thông qua tên biến, toán tử (.) và tên biến thành viên Các kiểucấutrúccóthể lồng vào nhau, trong cấutrúccóthể sử dụng mảng, mộtmảng có thể có các phầntử là cấu trúc, v.v Các biến có cùng kiểucấutrúccóthể gán cho nhau, có thể sử N dụng ₫ể khởitạo cho nhau (khác hẳnvớimảng) Ơ Có thể sử dụng con trỏ₫ểtruy nhậpdữ liệucấu trúc thông qua toán tử (*.) và toán tử (->) Hai kiểucấu trúc có khai báo giốngnhauhoàntoànvẫnlàhai kiểucấu trúc khác nhau 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 50 Ch ©
2.4.2 Hợpnhất enum SignalType {BINARY_8, BINARY_16, ANALOG_1, ANALOG_2}; union SignalValue { unsigned short word; unsigned char byte; float real; double lreal; }; struct Signal { SignalType type; SignalValue value; }; void main() { SignalValue B,W; B.byte = 0x01; W.word = 0x0101; unsigned char b = W.byte; // OK, the lower byte N float f = W.real; // meaningless Ơ Signal DI1 = {BINARY_8, 0x11}; Signal AI1 = {ANALOG_1,{0}}; Signal AI2; AI2.type = ANALOG_2; AI2.value.lreal = 145.67; } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 51 Ch ©
Tóm lượcvề hợpnhất Hợpnhất (union) là mộttậphợp (không có cấutrúcchặtchẽ) chứa các biếnsử dụng chung ô nhớ, ở mỗingữ cảnh chỉ sử dụng mộtbiếnriêngbiệt Union thường ₫ượcsử dụng khi dữ liệu ₫ầuvàocóthể có kiểu khác nhau Các thành viên củamột union không liên quan ₫ến nhau, không cùng nhau tạothànhmộtthựcthể thống nhất Kích cỡ củaunion bằng kích cỡ củabiếnlớnnhất Khai báo kiểuunion tương tự như khai báo struct, nhưng ý nghĩa khác hẳn Truy nhậpbiến thành viên cũng tương tự như struct, có thể qua N Ơ biếntrựctiếphoặcqua biếncon trỏ. Union có thể chứa struct, struct có thể chứa union, union có thể chứamảng, các phầntử củamảng có thể là union. 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 52 Ch ©
2.5 ĐiềukhiểnCT: phân nhánh Các kiểu phân nhánh – if else: Phân nhánh lựachọnmộthoặchaitrường hợp – switch case: Phân nhánh lựachọnnhiềutrường hợp – break: Lệnh nhảykết thúc (sớm) mộtphạmvi – return: Lệnh nhảyvàkếtthúc(sớm) mộthàm – goto: Lệnh nhảytớimột nhãn (không nên dùng!) N Ơ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 53 Ch ©
2.5.1 Cấutrúcif else Lựachọnmộttrường hợp: sử dụng if if (npoints >= 60) cout = 80 && npoints = 90) cout = 80) cout = 70) N cout = 60) cout << ‘D’; else cout << ‘F’; 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 54 Ch ©
Ví dụ: Hàm max() int max1(int a, int b) { int max4(int a, int b) { int c; if (a > b) if (a > b) return a; c = a; else else return b; c = b; } return c; int max5(int a, int b) { } if (a > b) int max2(int a, int b) { return a; int c = a; return b; if (a b)? a: b; } } intN max3(int a, int b) { Ơ if (a < b) a = b; return a; } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 55 Ch ©
2.5.2 Cấutrúcswitch case Signal input; int i = 0; while (i++ < 8) { input = readInput(i); // read from input module i switch (input.type) { case BINARY_8: cout << input.value.byte; break; case BINARY_16: cout << input.value.word; break; case ANALOG_1: cout << input.value.real; break; case ANALOG_2: N cout << input.value.lreal; break; Ơ default: cout << "Unknown signal type"; } } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 56 Ch ©
2.6 ĐiềukhiểnCT: vòng lặp Các kiểuvònglặp trong C/C++ – while (condition) { } – do { } while (condition) – for (init;condition;post_action) { } Vòng lặpcóthể thựchiệnvới if else + goto, song không bao giờ nên như vậy Ứng dụng vòng lặpchủ yếutronglàmviệcvớimảng và các cấutrúcdữ liệutổng quát khác => truy nhập qua biếnmảng + chỉ số, qua con trỏ hoặcqua N Ơ iterator (sẽ₫ềcậpsaunày) 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 57 Ch ©
2.6.1 Cấutrúcwhile #include void main() { char input[32]; cout > i; } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 58 Ch ©
Cấutrúcwhile: Biểuthức ₫iềukiện #include void main() { char input[32], family_name[16]={0}; cout > i; }N Ơ 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 59 Ch ©
2.6.2 Cấutrúcdo while #include void main() { char input[32], family_name[16]={0}; short i; do { cout > i; } while (i == ‘Y’ || i == ‘N’) } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 60 Ch ©
2.6.3 Cấutrúcfor short i =0; for (short i=0;input[i]!=0; ++i) while (input[i]!= 0) { { if (input[i] == ' ') if (input[i]==' ') ++nSpaces; ++nSpaces; else else ++nLetters; ++nLetters; } ++i; } short i=0; short i=0; for (;input[i]!= 0;) for (;input[i]!=0; ++i) { { if (input[i]==' ') if (input[i] == ' ') N Ơ ++nSpaces; ++nSpaces; else else ++nLetters; ++nLetters; ++i; } } 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 61 Ch ©
Tóm lượccáccấutrúcvònglặp Các cấutrúcvònglặp while và for tương tự như nhau, thựcratachỉ cầnmộttronghai Cấutrúcdo while tuy có ý nghĩakhácmột chút, song cũng có thể chuyểnvề cấutrúcwhile hoặc for Các cấutrúccóthể lồng vào nhau tương ₫ốitự do, tuy nhiên tránh lồng quá nhiều ₫ể còn dễ bao quát, khi cầncóthể phân hoạch lại thành hàm Điềukhiểnvònglặpcóthể nằmtrựctiếptrên₫iều kiện, hoặccóthể kếthợp bên trong vòng lặpvớicác N Ơ lệnh if else và break, return Thậntrọng trong kiểmtra₫iềukiệnvònglặp(chỉ số mảng, con trỏ, ) 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 62 Ch ©
Luyệntập ở nhà theo sườn bài giảng Tậptạodự án mớivớiVisual C++ Tậpviếtmộtchương trình bằng C (₫ặt ₫uôi *.c): —tập khai báo các loạibiến, sử dụng các kiểudữ liệucơ bản —tậpsử dụng các phép toán ₫ãhọc —sử dụng toán tử sizeof ₫ể tìm kích cỡ các kiểudữ liệu, in kết quả ra màn hình —biêndịch, chạythử và tìm lỗi —tậpsử dụng công cụ debugger — ₫ổi ₫uôi file thành *.cpp và thử lại Tậpviếtmộtchương trình bằng C/C++ khác ₫ể tìm N Ơ hiểu: — Cách khai báo và sử dụng kiểuhằng, kiểuliệtkê, kiểucon trỏ, kiểumảng, kiểu tham chiếu(C++), kiểucấutrúc —bảnchấtcủacon trỏ và quan hệ vớikiểumảng 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 63 Ch ©
Bài tậpvề nhà cho chương 2 1. Viếtmộtchương trình bằng C, thựchiệnlầnlượtcácchứcnăng sau ₫ây: —yêucầungườisử dụng nhậpmộtsố nguyên lớnhơn0 — phântíchsố nguyên ₫ó thành hàng ₫ơnvị, hàng chục, hàm trăm, v.v và in kếtquả lầnlượt ra màn hình. —hỏingườisử dụng có yêu cầutiếptục hay không, nếucóyêu cầuthìlặplại 2. Chuyểnchương trình thành C++ và ₫ơngiảnhóacáccâulệnh vào-ra bằng cách sử dụng thư viện 3. Dựavàokiểu Date trong bài giảng, viếtmộtchương trình cho phép ngườisử dụng nhậpsố liệuchomột ngày, và sau ₫ó: a) Kiểm tra các số liệungày, thángvànămcóhợplệ hay không N Ơ b) Kiểm tra xem ngày ₫ócóphảilàmộtngàylễ trong nămhay không c) Xác ₫ịnh ngày tiếptheolàngàynào d) In các kếtquả thông báo ra màn hình 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 64 Ch ©
Bài tậplớn1 (tuần1-6: Lậptrìnhcấutrúc) 1. Xây dựng mộtchương trình có chứcnăng tạotínhiệutheoyêu cầungườisử dụng về dạng tín hiệu(bậc thang, tín hiệudốc, xung vuông, hình sin hoặc ồntrắng), tham số củatínhiệu(tùy theo dạng tín hiệuchọnnhư biên ₫ộ, tầnsố, ₫ộ dốc, ₫ộ rộng xung, ). Yêu cầungườisử dụng nhập khoảng thời gian cầntạo giá trị tín hiệu cùng thời gian trích mẫu, sau ₫ó ghi các giá trị gián ₫oạncủatínhiệuramột file vớitêndo ngườisử dụng nhập. Gợiý: sử dụng thư viện choviệcthaotácvớifile. 2. Xây dựng mộtchương trình ₫ể tính tích phân củatínhiệu(hay tính diệntíchdưới ₫ường cong) bằng phương pháp xấpxỉ hình N thang vớicácgiátrị gián ₫oạncủatínhiệu ₫ưavàotừ file tạo Ơ ra theo chương trình 1. 3. Suy nghĩ phân hoạch chương trình 1 và 2 thành các hàm ₫ưa vào thư viện. Viếtlạicácchương trình ₫ótheothiếtkế mới. 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 65 Ch ©
Chỉ dẫnvề thựchiệnbàitậplớn Bài tậplớncóthể thựchiện riêng hoặc theo nhóm tự chọn(tối ₫a3 người/nhóm) Bài tậplớn1 nộpvàocuốituần7, baogồm: —Môtả theo mẫutrênítnhất1 tranggiấyvề các tư tưởng phân tích, thiếtkế và thựcthi. —Toànbộ thư mụcdự án (file dự án, mã nguồnvàchương trình chạy) cầnnénlạidướidạng *.zip và gửivề₫ịachỉ email của giáo viên: luuhongviet@gmail.com. Qui ₫ịnh tên file zip: bắt ₫ầubằng “P1_”, tiếptheolàtên₫ầy ₫ủ của người ₫ạidiện nhóm, ví dụ “P1_NguyenVanA.zip”. Lưuý trước khi nén cầnxóatấtcả các file phụ trong thư mục N “Debug”, chỉ trừ file *.exe. Ơ Hoàn thành bài tậplớn không những là ₫iềukiệndự thi họckỳ, mà ₫iểm bài tậplớncòn₫ượctínhvào₫iểmcuốihọckỳ theo một hệ số thích hợp 2004, HOÀNG MINH S ương 2: Các yếutố cơ bảncủaC vàC++ 66 Ch ©
Kỹ thuật lập trình Phần II: Lập trình có cấu trúc 1 g n 0101010101010101100001 ươ Chương3: Hàmv01010101010101011000010101010101010101100001àthư viện StateController010101010010101010010101010101001010101001010101010100101010100101 start() 101001100011001001001010100110001100100100101010011000110010010010 Ch stop() 110010110010001000001011001011001000100000101100101100100010000010 010101010101010110000101010101010101011000010101010101010101100001 010101010010101010010101010101001010101001010101010100101010100101 N 101001100011001001001010100110001100100100101010011000110010010010y = A*x + B*u; Ơ 110010110010001000001011001011001000100000101100101100100010000010x = C*x + d*u; LQGController010101010101010110000101010101010101011000010101010101010101100001 start() 010101010010101010010101010101001010101001010101010100101010100101 stop() 101001100011001001001010100110001100100100101010011000110010010010 110010110010001000001011001011001000100000101100101100100010000010 8/31/2006 2004, HOÀNG MINH S ©
Nộidung chương 3 3.1 Hàm và lậptrìnhhướng hàm 3.2 Khai báo, ₫ịnh nghĩahàm 3.3 Truyềnthamsố và trả về kếtquả 3.4 Thiếtkế hàm và thư viện 3.5 Thư việnchuẩnANSI-C 3.6 Làm việcvớitệptin sử dụng thư việnC++ 3.7 Nạpchồng tên hàm C++ N Ơ 3.8 Hàm inline trong C++ 2004, HOÀNG MINH S ương 3: Hàm và thư viện 2 Ch ©
3.1 Hàm và lậptrìnhhướng hàm Lậptrìnhcócấutrúccóthể dựatrênmộttronghaiphương pháp: Lậptrìnhhướng hàm (function-oriented), còn gọilàhướng nhiệm vụ (task-oriented), hướng thủ tục(procedure-oriented) NV 1 NV 1a NV 1b Nhiệmvụ NV 2 NV 2a NV 2b NV 2c NV 3 NV 3 Lậptrìnhhướng dữ liệu(data-oriented) N Ơ DL 1 DL 1 DL 2 DL 2 DL 3 DL 3 2004, HOÀNG MINH S ương 3: Hàm và thư viện 3 Ch ©
Hàm là gì? Tiếng Anh: function -> hàm, chứcnăng Một ₫ơnvị tổ chứcchương trình, một ₫oạnmã chương trình có cấutrúc₫ể thựchiệnmột chức năng nhất ₫ịnh, có giá trị sử dụng lại Các hàm có quan hệ với nhau thông qua lờigọi, các biếnthamsố (₫ầuvào, ₫ầu ra) và giá trị trả về Cách thựchiệncụ thể mộthàmphụ thuộcnhiềuvào dữ kiện(thamsố, ₫ốisố củahàm): — Thông thường, kếtquả thựchiệnhàmmỗilần ₫ềugiống N nhau nếu các tham số₫ầuvàonhư nhau Ơ —Một hàm không có tham số thì giá trị sử dụng lạirấtthấp Trong C/C++: Không phân biệtgiữathủ tụcvàhàm, cả₫oạnmãchương trình chính cũng là hàm 2004, HOÀNG MINH S ương 3: Hàm và thư viện 4 Ch ©
Ví dụ phân tích Yêu cầu bài toán: Tính tổng mộtdãysố nguyên (liên tục) trong phạmvi do ngườisử dụng nhập. In kếtquả ra màn hình. Các nhiệmvụ: —Nhậpsố nguyên thứ nhất: z Yêu cầungườisử dụng nhập z Nhậpsố vào mộtbiến —Nhậpsố nguyên thứ hai z Yêu cầungườisử dụng nhập z Nhậpsố vào mộtbiến N Ơ —Tínhtổng vớivònglặp —Hiểnthị kếtquả ra màn hình 2004, HOÀNG MINH S ương 3: Hàm và thư viện 5 Ch ©
Phương án 4 trong 1 #include void main() { int a, b; char c; do { cout > a; cout > b; int Total = 0; for (int i = a; i > c; } while (c == 'y' || c == 'Y'); } 2004, HOÀNG MINH S ương 3: Hàm và thư viện 6 Ch ©
Phương án phân hoạch hàm (1) #include int ReadInt(); int SumInt(int,int); void WriteResult(int a, int b, int kq); void main() { char c; do { int a = ReadInt(); int b = ReadInt(); int T = SumInt(a,b); WriteResult(a,b,T); N cout > c; } while (c == 'y' || c == 'Y'); } 2004, HOÀNG MINH S ương 3: Hàm và thư viện 7 Ch ©
Phương án phân hoạch hàm (1) int ReadInt() { Không có tham số, cout > N; return N; } OK, Không thể tốthơn! int SumInt(int a, int b) { int Total = 0; for (int i = a; i <= b; ++i) Total += i; Quá nhiềuthamsố, return Total; Hiệunăng? } N Ơ void WriteResult(int a, int b, int kq) { cout << "The sum from " << a << " to " << b << " is " << kq << endl; } 2004, HOÀNG MINH S ương 3: Hàm và thư viện 8 Ch ©
Phương án phân hoạch hàm (1) Chương trình dễ₫ọchơn => dễ phát hiệnlỗi Chương trình dễ mở rộng hơn HàmSumIntcóthể sử dụng lạitốt Mã nguồndàihơn Mã chạylớnhơn Chạychậmhơn Â Không phảicứ phân hoạch thành nhiềuhàmlàtốt, N Ơ mà vấn ₫ề nằm ở cách phân hoạch và thiếtkế hàm làm sao cho tối ưu! 2004, HOÀNG MINH S ương 3: Hàm và thư viện 9 Ch ©
Phương án phân hoạch hàm (2) #include int ReadInt(const char*); int SumInt(int,int); void main() { char c; do { int a = ReadInt("Enter the first integer number :"); int b = ReadInt("Enter the second integer number:"); cout > c; } while (c == 'y' || c == 'Y'); } 2004, HOÀNG MINH S ương 3: Hàm và thư viện 10 Ch ©
Phương án phân hoạch hàm (2) int ReadInt(const char* userPrompt) { cout > N; return N; OK, } Đãtốthơn! int SumInt(int a, int b) { int Total = 0; for (int i = a; i <= b; ++i) Total += i; return Total; N }Ơ 2004, HOÀNG MINH S ương 3: Hàm và thư viện 11 Ch ©
3.2 Khai báo và ₫ịnh nghĩahàm Định nghĩahàm: tạomãthựcthihàm Kiểutrả về Tên hàm Tham biến (hình thức) int SumInt(int a, int b) { int Total = 0; for (int i = a; i <= b; ++i) Total += i; return Total; } Khai báo hàm thuần túy: không tạomãhàm int SumInt(int a, int b); N Ơ Kiểutrả về Tên hàm Kiểuthambiến Tại sao và khi nào cần khai báo hàm? 2004, HOÀNG MINH S ương 3: Hàm và thư viện 12 Ch ©
Khai báo hàm và lờigọihàm Ý nghĩacủa khai báo hàm: —Khicầnsử dụng hàm (gọihàm) —Trìnhbiêndịch cầnlờikhaibáohàm₫ể kiểmtralờigọihàm ₫úng hay sai về cú pháp, về số lượng các tham số, kiểucác tham số và cách sử dụng giá trị trả về. int SumInt(int a, int b); —Cóthể khai báo hàm ₫ộclậpvớiviệc ₫ịnh nghĩahàm(tất nhiên phải ₫ảmbảonhất quán) Gọihàm: yêucầuthựcthimãhàmvớithamsố thực tế (tham trị) N Khi biên dịch chưacần Ơ int x = 5; phảicó₫ịnh nghĩa int k = SumInt(x, 10); hàm, nhưng phảicó Tên hàm Tham số (gọihàm) khai báo hàm! 2004, HOÀNG MINH S ương 3: Hàm và thư viện 13 Ch ©
Khai báo hàm C/C++ ở₫âu? Ở phạmvi toàncục(ngoàibấtcứ hàm nào) Mộthàmphải ₫ượckhaibáotrướclờigọi ₫ầutiên trong mộttệptin mãnguồn Nếusử dụng nhiềuhàmthìsẽ cầnrấtnhiều dòng mã khai báo (mất công viết, dễ saivàmãchương trình lớnlên?): —Nếungườixâydựng hàm (₫ịnh nghĩahàm) ₫ưasẵntấtcả phần khai báo vào trong mộttệptin => Header file (*.h, *.hx, ) thì ngườisử dụng chỉ cầnbổ sung dòng lệnh N #include Ơ —Mãchương trình không lớnlên, bởi khai báo không sinh mã! Mộthàmcóthể khai báo nhiềulầntùyý! 2004, HOÀNG MINH S ương 3: Hàm và thư viện 14 Ch ©
Định nghĩahàmở₫âu? Ở phạm vi toàn cục(ngoàibấtcứ hàm nào) Có thể₫ịnh nghĩa trong cùng tệptin vớimãchương trình chính, hoặctáchramộttệp tin riêng. Trong Visual C++: *.c => C compiler, *.cpp => C++ compiler Mộthàm₫ãcólờigọithìphải ₫ược ₫ịnh nghĩa chính xác 1 lần trong toàn bộ (dự án) chương trình, trướckhigọitrìnhliênkết (lệnh Build trong Visual C++) Đưatệptin mãnguồnvàodự án, không nên: #include “xxx.cpp” Mộthàmcó₫ược ₫ịnh nghĩabằng C, C++, hợpngữ hoặcbằng mộtngônngữ khác và dùng trong C/C++ => Sử dụng hàm N Ơ không cầnmãnguồn! Mộtthư viện cho C/C++ bao gồm: — Header file (thường ₫uôi *.h, *.hxx, , nhưng không bắtbuộc) —Tệptin mãnguồn(*.c, *.cpp, *.cxx, ) hoặcmã₫ích (*.obj, *.o, *.lib, *.dll, ) 2004, HOÀNG MINH S ương 3: Hàm và thư viện 15 Ch ©
3.3 Truyềnthamsố và trả về kếtquả Truyềnthamsố và trả về kếtquả là phương pháp cơ bản ₫ể tổ chứcquanhệ giữacáchàm(giữacácchứcnăng trong hệ thống) Hàm A Hàm B a d Tham số Giá trị trả Tham số Giá trị trả (₫ầu vào) b về hoặc (₫ầu vào) về hoặc ee c tham số ra tham số ra Ngoài ra, còn có các cách khác: —Sử dụng biếntoàncục: nói chung là không nên! —Sử dụng các tệp tin, streams: dù sao vẫnphảisử dụng tham số₫ể nói rõ tệp tin nào, streams nào N —Cáccơ chế giao tiếphệ thống khác (phụ thuộcvàohệ₫iều hành, Ơ nềntảng và giao thứctruyền thông) => nói chung vẫncần các tham số bổ sung Truyềnthamsố & trả về kếtquả là mộtvấn ₫ề cốtlõitrongxây dựng và sử dụng hàm, mộttrongnhững yếutốảnh hưởng quyết ₫ịnh tớichấtlượng phầnmềm! 2004, HOÀNG MINH S ương 3: Hàm và thư viện 16 Ch ©
Tham biến hình thức và tham số thựctế int SumInt(int a, int b) { } Tham biến (hình thức) int x = 5; int k = SumInt(x, 10); Tham số Kếtquả trả về (thựctế) (không tên) SumInt x a int a = 2; k N Ơ k = SumInt(a,x); 5 b Biến ₫ượcgán kếtquả trả về Tham biến 2004, HOÀNG MINH S ương 3: Hàm và thư viện 17 Ch ©
3.3.1 Truyềngiátrị int SumInt(int, int); // Function call void main() { int x = 5; SP int k = SumInt(x, 10); b = 10 a = 5 SP } k =k 45 x = 5 // Function definition Ngănxếp int SumInt(int a, int b) { N Ơ } 2004, HOÀNG MINH S ương 3: Hàm và thư viện 18 Ch ©
Thử ví dụ₫ọctừ bàn phím #include void ReadInt(const char* userPrompt, int N) { cout > N; } void main() { int x = 5; ReadInt("Input an integer number:", x); cout << "Now x is " << x; N }Ơ Kếtquả: x không hề thay ₫ổisau₫ó. 2004, HOÀNG MINH S ương 3: Hàm và thư viện 19 Ch ©
Truyềngiátrị Truyềngiátrị là cách thông thường trong C Tham biếnchỉ nhận ₫ượcbảnsaocủabiến ₫ầuvào (tham số thựctế) Thay ₫ổithambiếnchỉ làm thay ₫ổivùngnhớ cụcbộ, không làm thay ₫ổibiến ₫ầuvào Tham biếnchỉ có thể mang tham số₫ầu vào, không chứa ₫ượckếtquả (tham số ra) Truyềngiátrị khá an toàn, tránh ₫ượcmộtsố hiệu N ứng phụ Ơ Truyềngiátrị trong nhiềutrường hợpkémhiệuquả do mất công sao chép dữ liệu 2004, HOÀNG MINH S ương 3: Hàm và thư viện 20 Ch ©
3.3.2 Truyền ₫ịachỉ int SumInt(int* p, int N); // Function call void main() { SP int a[] = {1, 2, 3, 4}; k =k 45 int k = SumInt(a,4); N=4 p=00A0 SP } k =k 45 a[3]=4 a[2]=3 // Function definition a[1]=2 int SumInt(int* p, int N) { a[0]=1 N int *p2 = p + N, k = 0; 00A0 Ơ while (p < p2) k += *p++; return k; } 2004, HOÀNG MINH S ương 3: Hàm và thư viện 21 Ch ©
Truyềnmảng tham số? int SumInt(int p[4], int N); // Function call void main() { int a[] = {1, 2, 3, 4}; Bảnchấtnhư int k = SumInt(a,4); trongvídụ trước: Truyền ₫ịachỉ! } // Function definition int SumInt(int p[4], int N) { N int *p2 = p + N, k = 0; Ơ while (p < p2) k += *p++; return k; } 2004, HOÀNG MINH S ương 3: Hàm và thư viện 22 Ch ©
Thử lạivídụ₫ọctừ bàn phím #include void ReadInt(const char* userPrompt, int* pN) { cout > *pN; } void main() { int x = 5; ReadInt("Input an integer number:", &x); cout << "Now x is " << x; N Ơ } Kếtquả: x thay ₫ổigiátrị sau ₫ó(cũng là lý do tạisaohàm scanf() lạiyêucầukiểuthambiếnlàcon trỏ!) 2004, HOÀNG MINH S ương 3: Hàm và thư viện 23 Ch ©
Khi nào sử dụng truyền ₫ịachỉ? Khi cầnthay₫ổi"biến ₫ầuvào" (truynhậptrựctiếp vào ô nhớ, không qua bảnsao) Khi kích cỡ kiểudữ liệulớn=> tránhsaochépdữ liệu vào ngănxếp Truyềnthamsố là mộtmảng => bắtbuộctruyền ₫ịa chỉ Lưuý: Sử dụng con trỏ₫ểtruyền ₫ịachỉ của vùng N nhớ dữ liệu ₫ầuvào. Bảnthâncon trỏ có thể thay ₫ổi Ơ ₫ược trong hàm nhưng ₫ịachỉ vùng nhớ không thay ₫ổi(nội dung của vùng nhớ₫óthay₫ổi ₫ược): xem ví dụ biến p trong hàm SumInt trang 21. 2004, HOÀNG MINH S ương 3: Hàm và thư viện 24 Ch ©
3.3.3 Truyền tham chiếu (C++) #include void ReadInt(const char* userPrompt, int& N) { cout > N; } void main() { int x = 5; ReadInt("Input an integer number:", x); cout << "Now x is " << x; N Ơ } Kếtquả: x thay ₫ổigiátrị sau ₫ó 2004, HOÀNG MINH S ương 3: Hàm và thư viện 25 Ch ©
Thử ví dụ hàm swap #include void swap(int& a, int& b) { int temp = a; a = b; b = temp; } void main() { int x = 5, y = 10; swap(x,y); N Ơ cout << "Now x is " << x << ", y is " << y; } 2004, HOÀNG MINH S ương 3: Hàm và thư viện 26 Ch ©
Khi nào sử dụng truyền tham chiếu? Chỉ trong C++ Khi cầnthay₫ổi"biến ₫ầuvào" (truynhậptrựctiếp vào ô nhớ, không qua bảnsao) Mộtthambiếnthamchiếucóthể₫óng vai trò là ₫ầu ra (chứakếtquả), hoặccóthể vừalà₫ầuvàovà₫ầu ra Khi kích cỡ kiểudữ liệulớn=> tránhsaochépdữ liệu vào ngănxếp, ví dụ: void copyData(const Student& sv1, Student& sv2) { N Ơ sv2.birthday = sv1.birthday; } 2004, HOÀNG MINH S ương 3: Hàm và thư viện 27 Ch ©
3.3.4 Kiểutrả về Kiểutrả về: gầnnhư tùy ý, chỉ không thể trả về trực tiếpmộtmảng Về nguyên tắc, có thể trả về kiểu: —Giátrị —Con trỏ —Thamchiếu Tuy nhiên, cầnrấtthậntrọng vớitrả về₫ịachỉ hoặc tham chiếu: — Không bao giờ trả về con trỏ hoặc tham chiếu vào biếncục bộ N Ơ — Không bao giờ trả về con trỏ hoặc tham chiếu vào tham biếntruyềnqua giátrị Vớingườilập trình ít có kinh nghiệm: chỉ nên trả về kiểugiátrị 2004, HOÀNG MINH S ương 3: Hàm và thư viện 28 Ch ©
Cơ chế trả về int SumInt(int a, int b) { int k = 0; for (int i=a; i 45 } b = 10 a = 5 SP void main() { k k = =045 int x = 5, k = 0; x = 5 k = SumInt(x,10); Ngănxếp N Ơ } 45 2004, HOÀNG MINH S ương 3: Hàm và thư viện 29 Ch ©
Trả về con trỏ Viếthàmtrả về₫ịachỉ củaphầntử lớnnhấttrongmộtmảng: int* FindMax(int* p, int n) { int *pMax = p; int *p2 = p + n; while (p *pMax) pMax = p; ++p; } return pMax; } N voidƠ main() { int s[5] = { 1, 2, 3, 4, 5}; int *p = FindMax(s,5); } 2004, HOÀNG MINH S ương 3: Hàm và thư viện 30 Ch ©
Lý do trả về con trỏ hoặc tham chiếu Tương tự như lý do truyền ₫ịachỉ hoặctruyềntham chiếu: —Tránhsaochépdữ liệulớnkhôngcầnthiết — Để có thể truy cậptrựctiếpvàthay₫ổigiátrị₫ầura Có thể trả về con trỏ hoặcthamchiếuvào₫âu? — Vào biếntoàncục — Vào tham số truyền cho hàm qua ₫ịachỉ hoặcqua tham chiếu — Nói chung: vào vùng nhớ mà còn tiếptụctồntại sau khi kết N Ơ thúc hàm Con trỏ lạiphứctạpthêmmột chút? 2004, HOÀNG MINH S ương 3: Hàm và thư viện 31 Ch ©
Phảnvídụ: trả về con trỏ int* f(int* p, int n) { int Max = *p; int *p2 = p + n; while (p Max) Max = *p; ++p; } return &Max; } N void main() { Ơ int s[5] = { 1, 2, 3, 4, 5}; int *p = FindMax(s,5); // get invalid address } 2004, HOÀNG MINH S ương 3: Hàm và thư viện 32 Ch ©
Các ví dụ nghiên cứu: Đúng / sai? int* f1(int a) { int f5(int *pa) { return &a; return *pa; } } int& f2(int &a) { int& f6(int *pa) { return a; return *pa; } } int f3(int &a) { int& f7(int a) { return a; return a; } } N int*Ơ f4(int *pa) { int *pa; int* f8() { return pa; } return pa; } 2004, HOÀNG MINH S ương 3: Hàm và thư viện 33 Ch ©
3.4 Thiếtkế hàm và thư viện Viếtmộtchương trình chạytốt ₫ãkhó, viếtmộtthư việnhàmtốtcònkhóhơn! Mộtthư việnhàm₫ịnh nghĩa: —mộttậphợp các hàm (có liên quan theo mộtchủ₫ềchức năng) —những kiểudữ liệusử dụng trong các hàm —mộtsố biếntoàncục(rấthạnchế) Mộtthư việnhàmtốtcầnphải: —Thựchiệnnhững chứcnăng hữuích N Ơ — Đơngiản, dễ sử dụng —Hiệusuấtvà₫ộ tin cậycao —Trọnvẹn, nhấtquánvà₫ồng bộ 2004, HOÀNG MINH S ương 3: Hàm và thư viện 34 Ch ©
Thiếtkế hàm Phân tích yêu cầu: — Làm rõ các dữ kiện(₫ầuvào) vàkếtquả (₫ầura) — Tìm ra các chứcnăng cầnthựchiện Đặt tên hàm: ngắngọn, ý nghĩaxác₫áng, tự miêu tả —Hàmchỉ hành ₫ộng: Chọntênhàmlàmột ₫ộng từ kếthợpvớikiểu ₫ốitượng chủ thể, ví dụ printVector, displayMatrix, addComplex, sortEventQueue, filterAnalogSignal, — Hàm truy nhậpthuộc tính: Có thể chọnlà₫ộng từ hoặcdanhtừ kết hợpkiểu ₫ốitượng chủ thể, ví dụ length, size, numberOfColums, getMatrixElem, putShapeColor — Trong C++ nhiềuhàmcóthể giống tên (nạpchồng tên hàm), có thể N chọntênngắn, ví dụ sort, print, display, add, putColor, getColor => Ơ nguyên tắc ₫a hình/₫axạ theo quan ₫iểmhướng ₫ốitượng — Trong C++ còn có thể₫ịnh nghĩa hàm toán tử₫ểcó thể sử dụng các ký hiệutoántử₫ịnh nghĩasẵnnhư *, /, +, - thay cho lờigọihàm. 2004, HOÀNG MINH S ương 3: Hàm và thư viện 35 Ch ©
Chọnthamsố₫ầu vào (=> tham biến) — Đặctả ý nghĩa: Thể hiệnrõvaitròthamsố — Đặt tên: Ngắngọn, tự mô tả —Chọnkiểu: Kiểunhỏ nhấtmà₫ủ biểudiễn —Chọncáchtruyềnthamsố: cân nhắcgiữatruyềngiátrị hay truyền ₫ịachỉ/tham chiếuvàokiểuhằng Chọnthamsố₫ầura(=> thambiếntruyềnqua ₫ịachỉ/qua tham chiếuhoặcsử dụng giá trị trả về) — Đặctả ý nghĩa, ₫ặttên, chọnkiểutương tự như tham số₫ầuvào Định nghĩabổ sung các kiểudữ liệumớinhư cầnthiết Mô tả rõ tiềntrạng (pre-condition): ₫iềukiệnbiênchocáctham số₫ầuvàovàcác₫iềukiệnngoạicảnh cho việcgọihàm Mô tả rõ hậutrạng (post-condition): tác ₫ộng củaviệcsử dụng N Ơ hàm tớingoạicảnh, các thao tác bắtbuộc sau này, Thiếtkế thân hàm dựavàocácchứcnăng ₫ã phân tích, sử dụng lưu ₫ồ thuậttoánvớicáccấutrúc₫iềukiện/rẽ nhánh (kể cả vòng lặp) => có thể phân chia thành các hàm con nếucần 2004, HOÀNG MINH S ương 3: Hàm và thư viện 36 Ch ©
Ví dụ minh họa: Tìm số nguyên tố Bài toán: Xây dựng hàm tìm N số nguyên tố₫ầutiên! Phân tích: —Dữ kiện: N - số số nguyên tố₫ầutiêncầntìm —Kếtquả: Một dãy N số nguyên tố₫ầutiên —Cácchứcnăng cầnthựchiện: z Nhậpdữ liệu? KHÔNG! z Kiểmtradữ kiện vào (N)? Có/không (NếukiểmtramàN nhỏ hơn0 thìhàmlàmgì?) z Cho biếtk số nguyên tố₫ầutiên, xác₫ịnh số nguyên tố tiếp theo N z Lưutrữ kếtquả mỗilầntìmravàomộtcấutrúcdữ liệuphù Ơ hợp(dãysố cầntìm) z In kếtquả ra màn hình? KHÔNG! 2004, HOÀNG MINH S ương 3: Hàm và thư viện 37 Ch ©
Đặt tên hàm: findPrimeSequence Tham số vào: 1 —Ý nghĩa: số các số nguyên tố cầntìm —Tên: N —Kiểu: số nguyên ₫ủ lớn(int/long) —Truyềnthamsố: qua giá trị Tham số ra: 1 —Ý nghĩa: dãy N số nguyên tố₫ầu tiên tính từ 1 —Giátrị trả về hay tham biến? Tham biến! —Tên: primes —Kiểu: mảng số nguyên (của int/long) —Truyềnthamsố: qua ₫ịachỉ (int* hoặc long*) Tiềntrạng: N Ơ —Thamsố N phảilàsố không âm (có nên chọnkiểu unsigned?) – primes phảimang₫ịachỉ củamảng số nguyên có ít nhấtN phầntử Hậutrạng: không có gì ₫ặcbiệt 2004, HOÀNG MINH S ương 3: Hàm và thư viện 38 Ch ©
Khai báo hàm: void findPrimeSequence(int N, int* primes); Thiếtkế thân hàm Start —Lưu ₫ồ thuậttoánnhư hình vẽ false N>0 —Phânchia, bổ sung một hàm mới: findNextPrime true primes[0]=1 Lặplạiqui trìnhthiếtkế k=1 hàm cho findNextPrime (Bài tậpvề nhà!) false k<N N true Ơ primes[k]=findNextPrime ++k Stop 2004, HOÀNG MINH S ương 3: Hàm và thư viện 39 Ch ©
3.5 Thư việnchuẩn ANSI-C Thư việnvào/ra(nhập/xuất) Xử lý ký tự và chuỗikýtự , Thư viện hàm toán , Thời gian, ngày tháng , Cấpphátbộ nhớ₫ộng Các hàm ký tự rộng , Các hàm khác , N Ơ 2004, HOÀNG MINH S ương 3: Hàm và thư viện 40 Ch ©
3.6 Làm việcvớitệptin trong C++ #include #include Khai báo mộtbiến: ifstream fin; // input ofstream fout; // output fstream fio; // input and output Mở/tạomộttệptin: fin.open("file1.txt"); fout.open("file2.dat"); fio.open("file3.inf"); N Ơ Kếthợp khai báo biếnvàmở/tạomộttệptin ifstream fin("file1.txt"); // input ofstream fout("file2.inf");// output fstream fio("file3.dat"); // input and output 2004, HOÀNG MINH S ương 3: Hàm và thư viện 41 Ch ©
Ghi dữ liệuratệptin —Tương tự như sử dụng cout —Tệptin cóthể chứadữ liệukiểuhỗnhợp, ví dụ: fout > age >> married; Đóng mộttệptin: —Tự₫ộng khi kết thúc phạm vi { }, N Ơ —Hoặcgọi hàm thành viên close(): fin.close(); fout.close(); fio.close(); 2004, HOÀNG MINH S ương 3: Hàm và thư viện 42 Ch ©
Ví dụ: làm việcvớitệptin #include #include void main() { { ofstream fout("file1.dat");// output fout > age >> married; cout > c; } 2004, HOÀNG MINH S ương 3: Hàm và thư viện 43 Ch ©
3.7 Nạpchồng tên hàm trong C++ Trong C++ có thể xây dựng nhiều hàm có cùng tên, ví dụ: int max(int a, int b); double max(double a, double b); double max(double a, double b, double c); double max(double *seq, int n); Mục ₫ích của nạpchồng tên hàm là: — Đơngiảnhóachongườixâydựng hàm trong việcchọntên (thay vì maxInt, maxDouble, maxDouble3, N maxDoubleSequence, ) Ơ — Đơngiảnhóachongườisử dụng hàm, chỉ cầnnhớ 1 tên quen thuộc thay cho nhiềutênphứctạp 2004, HOÀNG MINH S ương 3: Hàm và thư viện 44 Ch ©
Ví dụ: ₫ịnh nghĩa các hàm max() int max(int a, int b) { // (1) return (a > b)? a : b; } double max(double a, double b) { // (2) return (a > b)? a : b; } double max(double a, double b, double c); { // (3) if (a < b) a = b; if (a < c) a = c; return a; } double max(double *seq, int n) { // (4) int i = 0, kq = seq[0]; while (i < n) { N Ơ if (kq < seq[i])kq = seq[i]; ++i; } return kq; } 2004, HOÀNG MINH S ương 3: Hàm và thư viện 45 Ch ©
Ví dụ: sử dụng các hàm max() int max(int a, int b); // (1) double max(double a, double b); // (2) double max(double a, double b, double c); // (3) double max(double *seq, int n); // (4) void main() { int k = max(5,7); // call (1) double d = max(5.0,7.0); // call (2) double a[] = {1,2,3,4,5,6}; d = max(d, a[1], a[2]); // call (3) d = max(a, 5); // call (4) d = max(5,7); // ? d = max(d, 5); // ? N }Ơ Â Đẩy trách nhiệmkiểmtravàtìmhàmphùhợpcho compiler! 2004, HOÀNG MINH S ương 3: Hàm và thư viện 46 Ch ©
Mộtsố qui tắcvề nạpchồng tên hàm Các hàm cùng tên ₫ược ₫ịnh nghĩacùngtrong mộtfile/ trongmộtthư viện hoặc sử dụng trong cùng mộtchương trình phảikhácnhauítnhấtvề: —Số lượng các tham số, hoặc —Kiểucủaítnhấtmộtthamsố (int khác short, const int khác int, int khác int&, ) Â Không thể chỉ khác nhau ở kiểutrả về Tạisaovậy? — Compiler cầncócơ sở₫ểquyết ₫ịnh gọihàmnào N —Dựa vào cú pháp trong lờigọi(số lượng và kiểucácthamsố Ơ thựctế) compiler sẽ chọn hàm có cú pháp phù hợpnhất —Khicần compiler có thể tự₫ộng chuyển ₫ổikiểu theo chiều hướng hợplýnhất (vd short=>int, int => double) 2004, HOÀNG MINH S ương 3: Hàm và thư viện 47 Ch ©
3.8 Hàm inline trong C++ Vấn ₫ề: Hàm tiệndụng, nhưng nhiều khi hiệusuất không cao, ₫ặcbiệt khi mã thựcthihàmngắn —Cácthủ tụcnhư nhớ lạitrạng thái chương trình, cấpphátbộ nhớ ngănxếp, sao chép tham số, sao chép giá trị trả về, khôi phụctrạng thái chương trình mấtnhiềuthờigian —Nếumãthực thi hàm ngắnthìsự tiệndụng không bõ so vớisự lãng phí thờigian GiảipháptrongC: Sử dụng macro, ví dụ #define max(a,b) a>b?a:b —Vấn ₫ề: Macro do tiềnxử lý chạy (preprocessor), không có kiểmtra kiểu, không có phân biệtngữ cảnh => gây ra các hiệu ứng phụ không mong muốn N Ơ Ví dụ dòng lệnh l=max(k*5-2,l); sẽ₫ượcthaythế bằng l=k*5-2>k?k*5-2:l; // OOPS! —Những cách giảiquyếtnhư thêm dấungoặcchỉ làm mã khó ₫ọc, không khắcphụctriệt ₫ể các nhược ₫iểm 2004, HOÀNG MINH S ương 3: Hàm và thư viện 48 Ch ©
Giảipháphàm inline trong C++ Điều duy nhấtcần làm là thêm từ khóa inline vào ₫ầudòngkhaibáovà₫ịnh nghĩahàm inline int max(int a, int b) { return (a > b)? a : b; } Hàm inline khác gì hàm bình thường: — "Hàm inline" thựcchất không phảilàmộthàm! —Khigọihàmthìlờigọihàm₫ược thay thế một cách thông minh bởimãnguồn ₫ịnh nghĩahàm, không thựchiện các thủ tụcgọihàm N Ví dụ: Ơ l=max(k*5-2,l); Đượcthaythế bằng các dòng lệnh kiểunhư: int x=k*5-2; // biếntạm trung gian l=(x>l)?x:l; // OK 2004, HOÀNG MINH S ương 3: Hàm và thư viện 49 Ch ©
Khi nào nên dùng hàm inline Ưu ₫iểmcủahàminline: —Tiệndụng như hàm bình thường —Hiệusuấtnhư viếtthẳng mã, không gọihàm —Tin cậy, an toàn hơnnhiềuso vớisử dụng Macro Nhược ₫iểmcủa hàm inline: —Nếugọi hàm nhiềulầntrongchương trình, mã chương trình có thể lớnlênnhiều(mãthựchiệnhàmxuấthiệnnhiềulần trong chương trình) —Mã₫ịnh nghĩahàmphải ₫ể mở => ₫ưa trong header file Lựachọnxâydựng và sử dụng hàm inline khi: N Ơ —Mã₫ịnh nghĩahàmnhỏ (một vài dòng lệnh, không chứa vòng lặp) —Yêucầuvề tốc ₫ộ ₫ặtratrước dung lượng bộ nhớ 2004, HOÀNG MINH S ương 3: Hàm và thư viện 50 Ch ©
Bài tậpvề nhà Xây dựng hàm tìm N số nguyên tố₫ầutiên —Hoànthiệnthiếtkế hàm — Định nghĩahàm Viếtchương trình minh họacáchsử dụng N Ơ 2004, HOÀNG MINH S ương 3: Hàm và thư viện 51 Ch ©
Kỹ thuật lập trình 1 g n 0101010101010101100001 ươ Chương 4: Khái01010101010101011000010101010101010101100001quát về cấu StateController010101010010101010010101010101001010101001010101010100101010100101 start() 101001100011001001001010100110001100100100101010011000110010010010 Ch stop()trúc110010110010001000001011001011001000100000101100101100100010000010dữ liệu 010101010101010110000101010101010101011000010101010101010101100001 010101010010101010010101010101001010101001010101010100101010100101 N 101001100011001001001010100110001100100100101010011000110010010010y = A*x + B*u; Ơ 110010110010001000001011001011001000100000101100101100100010000010x = C*x + d*u; LQGController010101010101010110000101010101010101011000010101010101010101100001 start() 010101010010101010010101010101001010101001010101010100101010100101 stop() 101001100011001001001010100110001100100100101010011000110010010010 110010110010001000001011001011001000100000101100101100100010000010 9/8/2006 2004, HOÀNG MINH S ©
Nộidung chương 4 4.1 Cấutrúcdữ liệulàgì? 4.2 Mảng và quảnlýbộ nhớ₫ộng 4.2 Xây dựng cấu trúc Vector 4.3 Xây dựng cấutrúcList N Ơ 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 2 Ch ©
4.1 Giớithiệuchung Phầnlớn các bài toán trong thựctế liên quan tớicác dữ liệuphứchợp, những kiểudữ liệucơ bảntrong ngôn ngữ lập trình không ₫ủ biểudiễn Ví dụ: —Dữ liệu sinh viên: Họ tên, ngày sinh, quê quán, mã số SV, —Môhìnhhàmtruyền: Đathứctử số, ₫athứcmẫusố —Môhìnhtrạng thái: Các ma trận A, B, C, D —Dữ liệuquátrình: Tên₫ạilượng, dải ₫o, giá trị, ₫ơnvị, thời gian, cấpsaisố, ngưỡng giá trị, N — Đốitượng ₫ồ họa: Kích thước, màu sắc, ₫ường nét, phông Ơ chữ, Phương pháp biểudiễndữ liệu: ₫ịnh nghĩakiểudữ liệumớisử dụng cấu trúc (struct, class, union, ) 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 3 Ch ©
Vấn ₫ề: Biểudiễntậphợpdữ liệu Đasố những dữ liệuthuộcmột ứng dụng có liên quan với nhau => cầnbiểudiễntrongmộttậphợpcócấu trúc, ví dụ: — Danhsáchsinhviên: Cácdữ liệu sinh viên ₫ượcsắpxếptheo thứ tự Alphabet —Mộ hình tổng thể cho hệ thống ₫iều khiển: Bao gồm nhiều thành phầntương tác —Dữ liệuquátrình: Mộttậpdữ liệucóthể mang giá trị của một ₫ạilượng vào các thời ₫iểmgián₫oạn, các dữ liệu ₫ầu vào liên quan tớidữ liệu ₫ầura — Đốitượng ₫ồ họa: Mộtcửasổ bao gồm nhiều ₫ốitượng ₫ồ N họa, mộtbảnvẽ cũng bao gồm nhiều ₫ốitượng ₫ồ họa Ơ Thông thường, các dữ liệutrongmộttậphợpcócùng kiểu, hoặcítralàtương thích kiểuvớinhau Kiểumảng không phải bao giờ cũng phù hợp! 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 4 Ch ©
Vấn ₫ề: Quảnlý(tậphợp) dữ liệu Sử dụng kếthợpmộtcáchkhéoléokiểucấutrúcvà kiểumảng ₫ủ ₫ể biểudiễncáctậphợpdữ liệubấtkỳ Các giảithuật (hàm) thao tác vớidữ liệu, nhằmquản lý dữ liệumộtcáchhiệuquả: —Bổ sung mộtmụcdữ liệumớivàomột danh sách, mộtbảng, mộttậphợp, —Xóamộtmụcdữ liệutrongmột danh sách, bảng, tậphợp, —Tìmmộtmụcdữ liệutrongmột danh sách, bảng tậphợp, theo mộttiêuchuẩncụ thể —Sắpxếpmột danh sách theo mộttiêuchuẩnnào₫ó N Ơ — 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 5 Ch ©
QuảnlýDL thế nàolàhiệuquả? Tiếtkiệmbộ nhớ: Phần "overhead" không ₫áng kể so vớiphầndữ liệuthực Truy nhập nhanh, thuậntiện: Thờigiancầnchobổ sung, tìm kiếm và xóa bỏ các mụcdữ liệuphảingắn Linh hoạt: Số lượng các mụcdữ liệu không (hoặcít) bị hạnchế cố₫ịnh, không cầnbiếttrướckhitạocấu trúc, phù hợpvớicả bài toán nhỏ và lớn Hiệuquả quảnlýdữ liệuphụ thuộcvào —Cấutrúcdữ liệu ₫ượcsử dụng N —Giảithuật ₫ượcápdụng cho bổ sung, tìm kiếm, sắpxếp, xóa Ơ bỏ 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 6 Ch ©
Các cấutrúcdữ liệu thông dụng Mảng (nghĩarộng): Tậphợpcácdữ liệucóthể truy nhậptùyý theochỉ số Danh sách (list): Tậphợpcácdữ liệu ₫ược móc nối ₫ôi mộtvớinhauvàcóthể truy nhậptuầntự Cây (tree): Tậphợpcácdữ liệu ₫ược móc nốivới nhau theo cấutrúccây, cóthể truy nhậptuầntự từ gốc —Nếumỗi nút có tối ₫a hai nhánh: cây nhị phân (binary tree) Bìa, bảng (map): Tậphợpcácdữ liệucósắpxếp, có thể truy nhậprất nhanh theo mã khóa (key) N Ơ Hàng ₫ợi (queue): Tậphợpcácdữ liệucósắpxếp tuầntự, chỉ bổ sung vào từ một ₫ầuvàlấyratừ₫ầu còn lại 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 7 Ch ©
Các cấutrúcdữ liệu thông dụng (tiếp) Tậphợp(set): Tậphợpcácdữ liệu ₫ượcsắpxếptùyý nhưng có thể truy nhậpmộtcáchhiệuquả Ngănxếp (stack): Tậphợpcácdữ liệu ₫ượcsắpxếp tuầntự, chỉ truy nhập ₫ượctừ một ₫ầu Bảng hash (hash table): Tậphợpcácdữ liệu ₫ượcsắp xếpdựatheomộtmãsố nguyên tạoratừ mộthàm ₫ặcbiệt Bộ nhớ vòng (ring buffer): Tương tự như hàng ₫ợi, nhưng dung lượng có hạn, nếuhếtchỗ sẽ₫ượcghi N Ơ quay vòng Trong toán họcvàtrong₫iềukhiển: vector, ma trận, ₫athức, phân thức, hàm truyền, 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 8 Ch ©
4.2 Mảng và quảnlýbộ nhớ₫ộng Mảng cho phép biểudiễnvàquảnlýdữ liệumộtcách khá hiệuquả: — Đọcvàghidữ liệurất nhanh qua chỉ số hoặcqua ₫ịachỉ —Tiếtkiệmbộ nhớ Các vấn ₫ề củamảng tĩnh: VD: Student student_list[100]; —Số phầntử phảilàhằng số (biếttrước khi biên dịch, ngườisử dụng không thể nhậpsố phầntử, không thể cho số phầntừ là mộtbiến) => kém linh hoạt N Ơ —Chiếmchỗ cứng trong ngănxếp(₫ốivớibiếncụcbộ) hoặc trong bộ nhớ dữ liệuchương trình (₫ốivớibiếntoàncục) => sử dụng bộ nhớ kém hiệuquả, kém linh hoạt 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 9 Ch ©
Mảng ₫ộng Mảng ₫ộng là mộtmảng ₫ượccấpphátbộ nhớ theo yêu cầu, trong khi chương trình chạy #include /* C */ int n = 50; float* p1= (float*) malloc(n*sizeof(float)); /* C */ double* p2= new double[n]; // C++ Sử dụng con trỏ₫ểquảnlýmảng ₫ộng: Cách sử dụng không khác so vớimảng tĩnh p1[0] = 1.0f; N p2[0] = 2.0; Ơ Sau khi sử dụng xong => giải phóng bộ nhớ: free(p1); /* C */ delete [] p2; // C++ 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 10 Ch ©
Cấpphátvàgiải phóng bộ nhớ₫ộng C: —Hàmmalloc() yêu cầuthamsố là số byte, trả về con trỏ không kiểu(void*) mang ₫ịachỉ vùng nhớ mới ₫ượccấp phát (nằm trong heap), trả về 0 nếu không thành công. —Hàmfree() yêu cầuthamsố là con trỏ không kiểu(void*), giải phóng vùng nhớ có ₫ịachỉ₫ưavào C++: —Toántử new chấpnhậnkiểudữ liệuphầntử kèm theo số lượng phầntử củamảng cầncấpphátbộ nhớ (trong vùng heap), trả về con trỏ có kiểu, trả về 0 nếu không thành công. N Ơ —Toántử delete[] yêu cầuthamsố là con trỏ có kiểu. —Toántử new và delete còn có thể áp dụng cho cấpphátvà giải phóng bộ nhớ cho mộtbiến ₫ơn, một ₫ốitượng chứ không nhấtthiếtphảimộtmảng. 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 11 Ch ©
Mộtsố₫iềucầnlưuý Con trỏ có vai trò quảnlýmảng (₫ộng), chứ con trỏ không phải là mảng (₫ộng) Cấpphátbộ nhớ và giải phóng bộ nhớ chứ không phảicấpphát con trỏ và giải phóng con trỏ Chỉ giải phóng bộ nhớ mộtlần int* p; p[0] = 1; // never do it new(p); // access violation! p = new int[100]; // OK p[0] = 1; // OK int* p2=p; // OK delete[] p2; // OK N Ơ p[0] = 1; // access violation! delete[] p; // very bad! p = new int[50]; // OK, new array 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 12 Ch ©
Cấpphátbộ nhớ₫ộng cho biến ₫ơn Ý nghĩa: Các ₫ốitượng có thể₫ượctạora₫ộng, trong khi chương trình chạy(bổ sung sinh viên vào danh sách, vẽ thêm mộthìnhtrongbảnvẽ, bổ sung mộtkhâutronghệ thống, ) Cú pháp int* p = new int; *p = 1; p[0]= 2; // the same as above p[1]= 1; // access violation! int* p2 = new int(1); // with initialization delete p; delete p2; N Student* ps = new Student; Ơ ps->code = 1000; delete ps; Mộtbiến ₫ơn khác vớimảng mộtphầntử! 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 13 Ch ©
Ý nghĩacủasử dụng bộ nhớ₫ộng Hiệusuất: —Bộ nhớ₫ượccấpphát₫ủ dung lượng theo yêu cầuvàkhi ₫ượcyêucầutrongkhichương trình ₫ãchạy —Bộ nhớ₫ượccấpphátnằm trong vùng nhớ tự do còn lạicủa máy tính (heap), chỉ phụ thuộc vào dung lượng bộ nhớ của máy tính —Bộ nhớ có thể₫ượcgiải phóng khi không sử dụng tiếp. Linh hoạt: —Thờigian"sống" củabộ nhớ₫ượccấpphát₫ộng có thể kéo dài hơnthời gian "sống" củathựcthể cấpphátnó. —Cóthể mộthàmgọilệnh cấpphátbộ nhớ, nhưng mộthàm N Ơ khác giải phóng bộ nhớ. —Sự linh hoạtcũng dễ dẫn ₫ếnnhững lỗi"ròrỉ bộ nhớ". 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 14 Ch ©
Ví dụ sử dụng bộ nhớ₫ộng trong hàm Date* createDateList(int n) { Date* p = new Date[n]; return p; } void main() { int n; cout > n; Date* date_list = createDateList(n); for (int i=0; i < n; ++i) { N } Ơ for ( ) { cout << } delete [] date_list; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 15 Ch ©
Tham số₫ầuralàcon trỏ? void createDateList(int n, Date* p) { p = new Date[n]; } void main() { int n; cout > n; Date* date_list; createDateList(n, date_list); for (int i=0; i < n; ++i) { N } Ơ for ( ) { cout << } delete [] date_list; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 16 Ch ©
4.3 Xây dựng cấutrúcVector Vấn ₫ề: Biểudiễnmột vector toán họctrongC/C++? Giải pháp chân phương: mảng ₫ộng thông thường, nhưng —Sử dụng không thuậntiện: Ngườisử dụng tự gọicáclệnh cấpphát và giải phóng bộ nhớ, trong các hàm luôn phải ₫ưathamsố là số chiều. —Sử dụng không an toàn: Nhầmlẫnnhỏ dẫn ₫ếnhậuquả nghiêm trọng int n = 10; double *v1,*v2, d; v1 = (double*) malloc(n*sizeof(double)); v2 = (double*) malloc(n*sizeof(double)); N Ơ d = scalarProd(v1,v2,n); // scalar_prod đãcó d = v1 * v2; // OOPS! v1.data[10] = 0; // OOPS! free(v1); free(v2); 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 17 Ch ©
Định nghĩacấutrúcVector Tên file: vector.h Cấutrúcdữ liệu: struct Vector { double *data; int nelem; }; Khai báo các hàm cơ bản: Vector createVector(int n, double init); void destroyVector(Vector); double getElem(Vector, int i); void putElem(Vector, int i, double d); N Vector addVector(Vector, Vector); Ơ Vector subVector(Vector, Vector); double scalarProd(Vector, Vector); 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 18 Ch ©
Định nghĩacáchàmcơ bản Tên file: vector.cpp #include #include "vector.h" Vector createVector(int n, double init) { Vector v; v.nelem = n; v.data = (double*) malloc(n*sizeof(double)); while (n ) v.data[n] = init; return v; } void destroyVector(Vector v) { free(v.data); }N doubleƠ getElem(Vector v, int i) { if (i = 0) return v.data[i]; return 0; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 19 Ch ©
void putElem(Vector v, int i, double d) { if (i >=0 && i < v.nelem) v.data[i] = d; } Vector addVector(Vector a, Vector b) { Vector c = {0,0}; if (a.nelem == b.nelem) { c = createVector(a.nelem,0.0); for (int i=0; i < a.nelem; ++i) c.data[i] = a.data[i] + b.data[i]; } return c; } Vector subVector(Vector a, Vector b) { N Vector c = {0,0}; Ơ return c; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 20 Ch ©
Ví dụ sử dụng #include "vector.h" void main() { int n = 10; Vector a,b,c; a = createVector(10,1.0); b = createVector(10,2.0); c = addVector(a,b); // destroyVector(a); N Ơ destroyVector(b); destroyVector(c); } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 21 Ch ©
4.4 Xây dựng cấutrúcList Vấn ₫ề: Xây dựng mộtcấutrúc₫ể quảnlýmộtcách hiệuquả và linh hoạtcácdữ liệu ₫ộng, ví dụ: —Hộpthư₫iệntử — Danh sách những việccầnlàm —Các₫ốitượng ₫ồ họatrênhìnhvẽ — Các khâu ₫ộng họctrongsơ₫ồmô phỏng hệ thống (tương tự trong SIMULINK) Các yêu cầu ₫ặc thù: —Số lượng mụcdữ liệutrongdanhsáchcóthể thay ₫ổithường N Ơ xuyên — Các thao tác bổ sung hoặcxóadữ liệucần ₫ượcthựchiện nhanh, ₫ơngiản —Sử dụng tiếtkiệmbộ nhớ 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 22 Ch ©
Sử dụng kiểumảng? Số phầntử trong mộtmảng thựcchất không bao giờ thay ₫ổi ₫ược. Dung lượng bộ nhớ vào thời ₫iểmcấp phát phảibiếttrước, không thựcsự co giãn ₫ược. Nếu không thựcsự sử dụng hết dung lượng ₫ãcấp phát => lãng phí bộ nhớ Nếu ₫ãsử dụng hếtdung lượng và muốnbổ sung phầntử thì phảicấpphátlại và sao chép toàn bộ dữ liệusang mảng mới=> cần nhiềuthờigiannếusố phầntử lớn N Ơ Nếumuốnchènmộtphầntử/xóa mộtphầntửở₫ầu hoặcgiữamảng thì phải sao chép và dịch toàn bộ phầndữ liệucònlại => rấtmấtthờigian 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 23 Ch ©
Danh sách móc nối (linked list) pHead Item A Dữ liệuA Item B Dữ liệuB Item C Dữ liệuC Item X Dữ liệuX N Ơ Item Y 0x00 Dữ liệuY 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 24 Ch ©
Bổ sung dữ liệu pHead pHead pHead Dữ liệuT Dữ liệuA Dữ liệuA Dữ liệuB Dữ liệuB Dữ liệuT Dữ liệuC Dữ liệuC N Dữ liệuX Dữ liệuX Ơ 0x00 Dữ liệuY 0x00 Dữ liệuY Bổ sung vào ₫ầudanhsách Bổ sung vào giữa danh sách 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 25 Ch ©
Xóa bớtdữ liệu pHead pHead Dữ liệuA Dữ liệuA Dữ liệuB Dữ liệuB Dữ liệuC Dữ liệuC Dữ liệuX Dữ liệuX N Ơ 0x00 Dữ liệuY 0x00 Dữ liệuY Xóa dữ liệu ₫ầudanhsách Xóa dữ liệugiữadanhsách 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 26 Ch ©
Các ₫ặc ₫iểm chính Ưu ₫iểm: —Sử dụng rấtlinhhoạt, cấpphátbộ nhớ khi cần và xóa khi không cần —Bổ sung và xóa bỏ mộtdữ liệu ₫ượcthựchiện thông qua chuyểncon trỏ, thờigianthựchiệnlàhằng số, không phụ thuộcvàochiều dài và vị trí —Cóthể truy nhậpvàduyệtcácphầntử theo kiểutuầntự Nhược ₫iểm: —Mỗidữ liệubổ sung mới ₫ềuphải ₫ượccấpphátbộ nhớ₫ộng —Mỗidữ liệuxóabỏ₫i ₫ềuphải ₫ượcgiải phóng bộ nhớ tương N Ơ ứng —Nếukiểudữ liệu không lớnthìphần overhead chiếmtỉ lệ lớn —Tìmkiếmdữ liệutheokiểutuyến tính, mấtthờigian 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 27 Ch ©
Ví dụ: Danh sách thông báo (hộpthư) #include using namespace std; struct MessageItem { string subject; string content; MessageItem* pNext; }; struct MessageList { MessageItem* pHead; }; void initMessageList(MessageList& l); void addMessage(MessageList&, const string& sj, N Ơ const string& ct); bool removeMessageBySubject(MessageList& l, const string& sj); void removeAllMessages(MessageList&); 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 28 Ch ©
#include "List.h" void initMessageList(MessageList& l) { l.pHead = 0; } void addMessage(MessageList& l, const string& sj, const string& ct) { MessageItem* pItem = new MessageItem; pItem->content = ct; pItem->subject = sj; pItem->pNext = l.pHead; l.pHead = pItem; } void removeAllMessages(MessageList& l) { MessageItem *pItem = l.pHead; while (pItem != 0) { MessageItem* pItemNext = pItem->pNext; N Ơ delete pItem; pItem = pItemNext; } l.pHead = 0; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 29 Ch ©
bool removeMessageBySubject(MessageList& l, const string& sj) { MessageItem* pItem = l.pHead; MessageItem* pItemBefore; while (pItem != 0 && pItem->subject != sj) { pItemBefore = pItem; pItem = pItem->pNext; } if (pItem != 0) { if (pItem == l.pHead) l.pHead = 0; else pItemBefore->pNext = pItem->pNext; delete pItem; } N Ơ return pItem != 0; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 30 Ch ©
Chương trình minh họa #include #include "list.h" using namespace std; void main() { MessageList myMailBox; initMessageList(myMailBox); addMessage(myMailBox,"Hi","Welcome, my friend!"); addMessage(myMailBox,"Test","Test my mailbox"); addMessage(myMailBox,"Lecture Notes","Programming Techniques"); removeMessageBySubject(myMailBox,"Test"); MessageItem* pItem = myMailBox.pHead; while (pItem != 0) { cout subject content pNext; N Ơ } char c; cin >> c; removeAllMessages(myMailBox); } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 31 Ch ©
Bài tậpvề nhà Xây dựng kiểu danh sách móc nốichứacácngàylễ trong nămvàý nghĩacủamỗi ngày (string), cho phép: —Bổ sung mộtngàylễ vào ₫ầudanhsách —Tìmý nghĩacủamộtngày(₫ưa ngày tháng là tham số) —Xóabỏ₫imộtngàylễở₫ầu danh sách —Xóabỏ₫imộtngàylễởgiữadanhsách(₫ưa ngày tháng là tham số) —Xóabỏ₫itoànbộ danh sách Viếtchương trình minh họacáchsử dụng N Ơ 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 32 Ch ©
Kỹ thuật lập trình Phần III: Lập trình hướng ₫ối tượng ng 1 0101010101010101100001 ươ 01010101010101011000010101010101010101100001 Chương 5: LớStateControllerpv010101010010101010010101010101001010101001010101010100101010100101à₫ốitượng start() 101001100011001001001010100110001100100100101010011000110010010010 Ch stop() 110010110010001000001011001011001000100000101100101100100010000010 010101010101010110000101010101010101011000010101010101010101100001 N Ơ 010101010010101010010101010101001010101001010101010100101010100101 101001100011001001001010100110001100100100101010011000110010010010y = A*x + B*u; 110010110010001000001011001011001000100000101100101100100010000010x = C*x + d*u; LQGController010101010101010110000101010101010101011000010101010101010101100001 start() 010101010010101010010101010101001010101001010101010100101010100101 stop() 101001100011001001001010100110001100100100101010011000110010010010 110010110010001000001011001011001000100000101100101100100010000010 9/15/2006 2004, HOÀNG MINH S 2004, HOÀNG MINH ©
Nộidung chương 5 5.1 Khái niệm 5.2 Từ cấutrúcsang lớp 5.3 Biếnthànhviên 5.4 Hàm thành viên 5.5 Kiểmsoáttruynhập N Ơ Ch2004, HOÀNG MINH S ương 5: Lớpvàđốitượng 2 © 2005 - HMS ©
5.1 Khái niệm Đối tượng là gì? Thực thể phần mềm Mô hình/₫ại diện của một ₫ốitượng vật lý: — Tank, Heater, Furnace — Motor, Pump, Valve — Sensor, Thermometer, Flowmeter — Control Loop, Control System Hoặc một ₫ốitượng logic ("conceptual object): — Trend, Report, Button, Window N — Matrix, Vector, Polynomial Ơ Ch2004, HOÀNG MINH S ương 5: Lớpvàđốitượng 3 © 2005 - HMS ©
Một ₫ối tượng có Hành vi Â Các thuộc tính (attributes) sủa, cắn, chạy chạy khi gặp nguy hiểm Â Trạng thái (state) •Dữ liệu Trạng thái • Quan hệ tư thế Â Hành vi (behavior) sức khỏe • Các phép toán Thuộc tính • Đặc tính phản ứng Căn cước màu lông: vàng Tên: Rex N Â Căn cước (identity) giống: Berge Ơ Â Ngữ nghĩa/trách nhiệm ID: 007 (semantic/responsibilities) Ngữ nghĩa Chó giữ nhà Ch2004, HOÀNG MINH S ương 5: Lớpvàđốitượng 4 © 2005 - HMS ©
Lớplàgì? Mộtlớplàthựcthicủacác₫ốitượng có chung —Ngữ nghĩa —Thuộctính —Quanhệ —Hànhvi Lớp= Đóng gói [Cấutrúcdữ liệu + hàm thao tác] —Lớp các vector, lớp các ma trận(dữ liệuphầntử + các phép truy nhậpvàphéptoáncơ bản) —Lớp các hình chữ nhật(cácdữ liệutọa ₫ộ + phép vẽ, xóa, ) —Lớp các mô hình hàm truyền(cáchệ số₫athứctử/mẫu, các phép toán xác ₫ịnh tính ổn ₫ịnh, xác ₫ịnh các ₫iểmcực, ) N Các dữ liệucủamộtlớp=> biến thành viên Ơ Các hàm củamộtlớp => hàm thành viên Các biếncủamộtlớp=> một ₫ốitượng, mộtthể nghiệm Ch2004, HOÀNG MINH S ương 5: Lớpvàđốitượng 5 © 2005 - HMS ©
Lập trình hướng ₫ối tượng (object-oriented programming, OOP) Trừu tượng hóa (abstraction): giúp ₫ơn giản hóa vấn ₫ề, dễ sử dụng lại Đóng gói dữ liệu/che dấu thông tin (data encapsulation/ information hiding): nâng cao giá trị sử dụng lại và ₫ộ tin cậy của phần mềm Dẫn xuất/thừa kế (subtyping/inheritance): giúp dễ sử dụng lại mã phần mềm và thiết kế Đa hình/₫a xạ (polymorphism): giúp phản ánh trung thực thế giới thực và nâng cao tính linh hoạt của phần mềm N Ơ Phương pháp luậnhướng ₫ốitượng cho phép tư duy ở mức trừutượng cao nhưng gầnvớithế giớithực! Ch2004, HOÀNG MINH S ương 5: Lớpvàđốitượng 6 © 2005 - HMS ©
5.2 Từ cấutrúcsang lớp struct Time { void addSec(Time& t, int s) { int hour; // gio t.sec += s; int min; // phut if (t.sec > 59) { int sec; // giay addMin(t, t.sec/60); }; t.sec %= 60; void addHour(Time& t, int h) { } t.hour += h; else if (t.sec 59) { } t.hour += t.min/60; } t.min %= 60; void main() { N } Time t = {1, 0, 0}; Ơ else if (t.min < 0) { addMin(t,60); t.hour += (t.min/60 - 1); addMin(t,-5); t.min = (t.min % 60) + 60; addSec(t,25); } } } Ch2004, HOÀNG MINH S ương 5: Lớpvàđốitượng 7 © 2005 - HMS ©