Tài liệu môn ngôn ngữ lập trình C/C++

NGÔN NGỮ LẬP TRÌNH C/C++ Vũ Song Tùng 1 NỘI DUNG Đặc điểm của C/C++ Các thành phần cơ bản Biểu thức và toán tử Hàm, mảng và con trỏ Kiểu dữ liệu trừu tượng Các cấu trúc dữ liệu cơ bản 2 3 5 22 45 77 123 I. Đặc điểm của C/C++ 3 • Ngôn ngữ lập trình hàm • Linh hoạt trong việc sử dụng các kiểu biến • Truy cập trực tiếp bộ nhớ thông qua các con trỏ • Định nghĩa các kiểu biến mới bằng các struct • Có thể chia nhỏ chương trình thành nhiều mô-đun I. Đặc điểm của C/C++ 4 • Kế thừa các đặc điểm của C • Đa hình bằng kỹ thuật xếp chồng (overload) • Hướng đối tượng bằng các lớp (class) • Sử dụng lại các mã bằng kỹ thuật kế thừa (inheritance) II. Các thành phần cơ bản Bộ ký tự Chú thích Định danh Hằng Biến Vào/ra 5 II. Các thành phần cơ bản 6 • Chữ cái thường : a – z • Chữ cái hoa : A – Z • Chữ số : 0 – 9 • Phần lớn các dấu (trừ @ và $) Ví dụ #include void main() { int Arr[] = { 1, 2, 3, 4 }; for (int i = 0; i < 4; i++) std::cout << Arr[i] << '\t'; } II. Các thành phần cơ bản 7 • Dùng để mô tả một hàm hay một đoạn chương trình // Hàm tính x^n // x - số thực, n - số nguyên dương double power(double x, int n) { /* double g = 1; for (int i = 0; i < n; i++) g *= x; return g; */ if (n == 0) return 1; // x^0 = 1 return x * power(x, n - 1); } Mô tả hàm Có thể dùng để bỏ tạm thời một đoạn chương trình Làm rõ nghĩa II. Các thành phần cơ bản 8 • Tên được đặt cho các hàm, các biến, các kiểu dữ liệu v.v • Các quy tắc định danh – Chỉ được dùng các chữ cái, chữ số hoặc dấu gạch nối – Ký tự đầu tiên không là chữ số – Không được phép trùng từ khóa Chú ý. Ngôn ngữ C/C++ phân biệt chữ cái hoa và chữ cái thường Ví dụ void _foo() // đúng quy cách { int so nguyen; // sai vì có chứa dấu cách int soNguyen; // đúng quy cách } II. Các thành phần cơ bản 9 • Các giá trị cụ thể trong chương trình • Có thể là số nguyên, số thực, ký tự hoặc xâu ký tự Ví dụ 5 // số nguyên kiểu int 05 // số nguyên biểu diễn trong hệ 8 0x5 // số nguyên biểu diễn trong hệ 16 5u // U hoặc u – số nguyên kiểu unsigned 5l // L hoặc l – số nguyên kiểu long 5.0 // số nguyên kiểu double '5' // ký tự có giá trị số (mã ASCII) bằng 53 'A' // ký tự có giá trị số (mã ASCII) bằng 65 "5" // xâu ký tự gồm ký tự '5' và ký tự NULL II. Các thành phần cơ bản 10 Bảng 2.1. Các ký tự đặc biệt Ký tự Mô tả \t TAB \n ENTER \’ Nháy đơn \” Nháy kép \\ \ \0 Ký tự NULL (giá trị bằng 0) II. Các thành phần cơ bản 11 • Là một vùng trong bộ nhớ RAM dùng để lưu trữ tạm thời các giá trị được xác định bằng một tên biến • Phân loại • Biến đơn • Biến mảng • Biến con trỏ II. Các thành phần cơ bản 12 • Cần khai báo biến trước khi sử dụng Ví dụ int a, b = 1; // Khai báo biến đơn double A[10]; // Khai báo biến mảng int *pa = &a; // Khai báo biến con trỏ Cú pháp kiểu tên_biến; kiểu tên_biến = biểu_thức_khởi_tạo; II. Các thành phần cơ bản 13 Bảng 2.2. Các kiểu biến Kiểu Kích thước (byte) Vùng giá trị Số n gu yê n char 1 -128 127 short 2 –32,768 32,767 int 4 –2,147,483,648 2,147,483,647 unsigned 4 0 4,294,967,295 long 4 –2,147,483,648 2,147,483,647 long long 8 –9,223,372,036,854,775,808 9,223,372,036,854,775,807 Số t h ự c float 4 ±3.4E±38 double 8 ±1.7E±308 long double 8 ±1.7E±308 II. Các thành phần cơ bản 14 • Một vài chú ý Ví dụ void main() { int x = 10, y; // Các biểu thức for (int i = 0; i < 4; i++) { int x = 5; // Các biểu thức } int y; } error C2086: 'int y' : redefinition Trong một khối ,-, các tên biến phải khác nhau Cùng một tên biến có thể khai báo trong các khối ,- khác nhau II. Các thành phần cơ bản 15 • Một vài chú ý • Kích thước của các kiểu phụ thuộc vào hệ thống mà chương trình được biên dịch • Dùng toán tử sizeof(...) để lấy kích thước của một kiểu, một hằng hay một biến // Chương trình Win32 Console Application int sz; sz = sizeof(sz); // sz = 4 sz = sizeof(long long); // sz = 8 sz = sizeof("12345"); // sz = 6 II. Các thành phần cơ bản 16 • Kiểu liệt kê • Dùng để định danh cho các giá trị kiểu int enum tên_kiểu { danh sách tên }; Ví dụ enum Boolean { False, True }; // False = 0, True = 1 enum Keys { Enter = 13, Escape = 27, A = 65, B, C }; // B = 66, C = 67 II. Các thành phần cơ bản 17 Dùng các chuẩn vào/ra trong thư viện iostream để làm việc với màn hình và bàn phím – Chuẩn vào (cin) sử dụng toán tử luồng vào (>>) – Các chuẩn ra (cout, cerr) sử dụng toán tử luồng ra (<<) Ví dụ double a, b, c; cout << "Nhap a, b, c: "; cin >> a >> b >> c; // Dùng dấu cách, TAB hoặc ENTER để phân biệt các luồng if (a != 0) { cout << "delta = " << b*b - 4*a*c << '\n'; // Các biểu thức } else cerr << "a phai khac 0.\n"; II. Các thành phần cơ bản 18 Yêu cầu bài toán • Nhập các hệ số a, b, c từ bàn phím • Nếu a ≠ 0 thì – Tính  – In kết quả ra màn hình với các trường hợp •  > 0  X1 = , X2 = •  = 0  X1 = X2 = •  < 0  Vo nghiem. II. Các thành phần cơ bản 19 PhuongTrinhBac2.cpp #include // thư viện vào/ra using namespace std; // nơi khai báo các thành phần chuẩn void main() { double a, b, c; cout > a >> b >> c; if (a != 0) { // Đoạn biểu thức giải và biện luận phương trình // } else cerr << "He so a phai khac 0."; cout << endl; // in ký tự xuống dòng system("pause"); // tạm dừng màn hình } II. Các thành phần cơ bản 20 PhuongTrinhBac2.cpp // Giải và biện luận phương trình double d = b*b - 4*a*c; if (d >= 0) { if (d > 0) { cout << "X1 = " << (-b - sqrt(d)) / (2 * a) << ", X2 = " << (b - sqrt(d))/(2 * a); } else cout << "X1 = X2 = " << -b / (2 * a); } // if (d >= 0) else cout << "Vo nghiem."; II. Các thành phần cơ bản 21 • Tạo project PhuongTrinhBac2 trên Visual Studio .NET và kiểm tra với các hệ số: – a = 1, b = 2, c = 1 – a = 1, b = 2, c = 3 – a = 1, b = 3, c = 2 • Tối ưu đoạn mã giải phương trình bậc 2 Gợi ý. Giảm số lượng các biểu thức 2 * a và sqrt(d) III. Biểu thức và toán tử Biểu thức Các toán tử đơn Các toán tử có cấu trúc 22 Ví dụ III. Biểu thức và toán tử 23 • Tập hợp của các toán hạng và toán tử • Kết thúc bằng dấu chấm phảy • Có thể rỗng (-b – sqrt(d)) / (2 * a)  Các toán tử: () - / *  Các toán hạng:  Biến: a, b, d  Hằng: 2  Hàm: sqrt III. Biểu thức và toán tử 24 Bảng 3.1. Phân loại các toán tử đơn Nhóm Các toán tử Ghi chú Gán = Số học + - * / % Có thể kết hợp với = Tăng/Giảm ++ -- So sánh == != > = <= Cho giá trị 0 hoặc 1 Kiểm tra ?: Logic && || ! Cho giá trị 0 hoặc 1 Xử lý bit & | ~ ^ > Có thể kết hợp với = Con trỏ & * new delete Truy cập thành viên :: . -> Các loại khác {} () [] , Thứ tự ưu tiên các toán tử tham khảo tại III. Biểu thức và toán tử 25 • Toán tử gán: a = 5; // gán 5 vào a a = b = c = 5; // tương đương: c = 5; b = c; a = b; a = b + (c = 5); // tương đương: c = 5; a = b + c; Cú pháp lvalue = rvalue lvalue – tên_biến, rvalue – một biểu thức Ví dụ Ví dụ III. Biểu thức và toán tử 26 • Các toán tử số học a = 1 / 5; // a = 0 a = 1.0 / 5; // a = 0.2 a = (double)1 / 5; // a = 0.2 a = 11 % 3; // a = 2 // Kết hợp với toán tử gán a += b; // tương đương: a = a + b; a *= b + 1; // tương đương: a = a * (b + 1); + Cộng / Chia - Trừ hoặc đổi dấu % Chia dư * Nhân Ví dụ III. Biểu thức và toán tử 27 • Các toán tử tăng/giảm ++a; // tương đương: a = a + 1; a++; // tương đương: a = a + 1; a = b++; // tương đương: a = b; b = b + 1; a = ++b; // tương đương: b = b + 1; a = b; ++ Tăng 1 -- Giảm 1 III. Biểu thức và toán tử 28 • Các toán tử so sánh 5 == 3 // cho giá trị 0 5 != 3 // cho giá trị 1 5 > 3 // cho giá trị 1 5 < 3 // cho giá trị 0 5 >= 3 // cho giá trị 1 5 <= 3 // cho giá trị 0 != Khác == Bằng > Lớn hơn >= Lớn hơn hoặc bằng < Nhỏ hơn <= Nhỏ hơn hoặc bằng III. Biểu thức và toán tử 29 • Toán tử kiểm tra: Biểu thức logic? Biểu thức 1: Biểu thức 2 Ví dụ 5 == 3? 5: 3 // cho giá trị 3 5 != 3? 5: 3 // cho giá trị 5 a > b? a: b // cho giá trị lớn nhất của a và b a < 0? –a: a // cho giá trị tuyệt đối của a III. Biểu thức và toán tử 30 • Các toán tử logic Ví dụ !(a == b) // tương đương: a != b x >= a && x <= b // kiểm tra x trong khoảng [a, b] x b // kiểm tra x ngoài khoảng [a, b] && Và || Hoặc ! Phủ định III. Biểu thức và toán tử 31 • Các toán tử logic – Các giá trị khác 0 được coi là 1 – Trong biểu thức A && B, nếu A = 0 thì không cần xác định B – Trong biểu thức A || B, nếu A = 1 thì không cần xác định B !!5 // cho giá trị 1 x >= a && x <= b // kiểm tra x trong khoảng [a, b] x b // kiểm tra x ngoài khoảng [a, b] Ví dụ III. Biểu thức và toán tử 32 • Các toán tử xử lý bit Ví dụ 5 & 0xFE // cho giá trị 4 5 | 2 // cho giá trị 7 5 ^ 4 // cho giá trị 1 ~5 // cho giá trị 0xFFFFFFFA 5 << 1 // cho giá trị 10 5 >> 1 // cho giá trị 2 & AND ~ NOT | OR << SHL (dịch trái) ^ XOR >> SHR (dịch phải) III. Biểu thức và toán tử 33 Bảng 3.2. Một vài phương án sử dụng • Các toán tử xử lý bit Biểu thức Mô tả a &= 0xFE Xóa bit a0 (a thuộc kiểu 1 byte) (a & (1 << n)) Kiểm tra bit an (a & 1) == 0 Kiểm tra tính chia hết cho 2 của a a |= 1 Lập bit a0 a |= (1 << n) Đặt bit an = 1 a ^= 1 Đảo bit a0 a <<= n Nhân a với 2n a >>= 2 Chia a cho 2n III. Biểu thức và toán tử 34 • Toán tử dấu phảy: Dùng để phân biệt hai hay nhiều biểu thức void _foo(int x, int y) // các tham số của hàm { int A[] = { 1, 2, 3, 4 };// các biểu thức khởi tạo mảng int a, b; // các biểu thức khai báo biến a = (b = 3, b + 2); // tương đương: b = 3; a = b+2; _foo(a, b); // các biểu thức truyền cho hàm } III. Biểu thức và toán tử 35 • Toán tử điều kiện: if if (biểu thức logic) khối biểu thức // tìm trị tuyệt đối của x a = x; if (a < 0) a = -x; Ví dụ III. Biểu thức và toán tử 36 • Toán tử điều kiện: if else if (biểu thức logic) khối biểu thức 1 else khối biểu thức 2 // tìm giá trị nhỏ nhất của a và b if (a < b) min = a; else min = b; Ví dụ III. Biểu thức và toán tử 37 • Toán tử lặp: while while (biểu thức logic) khối biểu thức // tìm ước số chung lớn nhất của a và b while (b != 0) { int r = a % b; a = b; b = r; } uscln = a; Ví dụ III. Biểu thức và toán tử 38 • Toán tử lặp: do while do khối biểu thức while (biểu thức logic); // Ví dụ III. Biểu thức và toán tử 39 • Toán tử lặp: for for (bt khởi tạo; bt logic; bt biến đổi) khối biểu thức // tìm N! int gt = 1; for (int i = 2; i <= N; i++) gt *= i; Ví dụ III. Biểu thức và toán tử 40 • Toán tử lựa chọn: switch switch (biểu thức) { case giá_trị_1: các biểu thức #1 break; ... case giá_trị_n: các biểu thức #n break; default: các biểu thức #khác } #k – khi (biểu thức) có giá trị = giá_trị_k #khác – khi giá trị của (biểu thức) khác các giá trị đã liệt kê III. Biểu thức và toán tử 41 • Toán tử lựa chọn: switch // tìm số ngày của tháng month trong năm year switch (month) { case 2: days = (year % 4) == 0? 29: 28; break; case 4: case 6: case 9: case 11: days = 30; break; default: days = 31; } III. Biểu thức và toán tử 42 • Toán tử điều khiển: break và continue • break – đưa con trỏ chương trình ra khỏi các vòng lặp và khối switch • continue – đưa con trỏ chương trình về đầu các vòng lặp // tìm tổng các giá trị chẵn và lẻ // của các số nguyên dương nhập vào từ bàn phím int odd = 0, even = 0, input; while (1) { // vòng lặp vô cùng cin >> input; if (input < 0) continue; if (input == 0) break; if (input & 1) even += input; else odd += input; } Ví dụ III. Biểu thức và toán tử 43 • Viết chương trình in ra màn hình các giá trị từ 1 đến k dưới dạng ma trận mxn với k = mxn, m và n được khởi tạo trong hàm main(). • Viết chương trình xác định dạng tam giác được cho bởi 3 cạnh a, b, c là các số thực. Yêu cầu: – Nhập 3 cạnh của tam giác – In ra màn hình kiểu của tam giác: • Tam giac thuong • Tam giac vuong • Tam giac can • Tam giac vuong can • Tam giac deu – Chương trình chỉ kết thúc khi a, b, c không tạo thành tam giác III. Biểu thức và toán tử 44 • Viết chương trình in ra màn lịch của năm nay theo mẫu của năm 2000: Thang 1 CN T2 T3 T4 T5 T6 T7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Thang 2 CN T2 T3 T4 T5 T6 T7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 IV. Hàm, mảng và con trỏ Mảng Con trỏ và tham chiếu Hàm 45 IV. Hàm, mảng và con trỏ 46 • Khai báo biến mảng kiểu tên_biến[kích thước]; // kích thước phải là hằng số nguyên kiểu tên_biến[kích thước] = { danh sách biểu thức }; // số biểu thức trong danh sách biểu thức phải nhỏ // hơn hoặc bằng kích thước kiểu tên_biến[] = { danh sách biểu thức }; // kích thước của mảng bằng số biểu thức trong // danh sách biểu thức IV. Hàm, mảng và con trỏ 47 • Khai báo biến mảng Ví dụ int A[2]; short B[] = { 10, 256, 1024 }; char S[100] = { 'A', 'B', 'C', 0 }; A A[0] A[1] 0x0A 0x00 0x00 0x01 0x00 0x04 B B[0] B[2] B[1] 0x41 0x42 0x43 0x00 S[0] S[99] S – S[3] IV. Hàm, mảng và con trỏ 48 • Xâu ký tự (string) • Mảng các ký tự, kết thúc bằng ký tự NULL • Biến xâu ký tự được khai báo bằng một mảng kiểu char (biểu thức khởi tạo có thể là một hằng xâu ký tự) Ví dụ // nhập và kiểm tra mật khẩu char pwd[] = "12345678"; char s[100]; cout << "Nhap mat khau: "; cin.getline(s, 100); for (int i = 0; s[i] != 0 || pwd[i] != 0; i++) { if (s[i] != pwd[i]) // khối biểu thức xử lý sai mật khẩu } IV. Hàm, mảng và con trỏ 49 • Thiết kế và cài đặt chương trình thực hiện các thao tác sau: – Khai báo một mảng chứa 1000 số nguyên – Đặt giá trị ngẫu nhiên từ 1 .. 1000 cho các phần tử của mảng (dùng hàm rand()) – Đếm số lượng số chẵn, số lẻ và số chia hết cho 8 của mảng • Viết chương trình thực hiện các thao tác sau: – Nhập giá trị cho xâu ký tự s (chứa được nhiều nhất 49 ký tự khác NULL) – In s ra màn hình với các chữ cái thường (VD. s = “123ABC”  123abc) – Đổi s thành số nguyên và gán cho biến a (VD. s = “123abc”  a = 123) IV. Hàm, mảng và con trỏ 50 • Các khái niệm • Con trỏ là một biến đặc biệt, dùng để chứa địa chỉ của một biến khác • Tham chiếu là một biến đại diện cho duy nhất một biến nào đó Kiểu con trỏ kiểu * Truy cập nội dung con trỏ *tên_biến_con_trỏ Lấy địa chỉ &tên_biến Kiểu tham chiếu kiểu & Bảng 4.1. Các toán tử của con trỏ và tham chiếu IV. Hàm, mảng và con trỏ 51 • Các khái niệm Ví dụ int a; // giả sử a nằm ở địa chỉ 0x000000A0 int b; // giả sử b nằm ở địa chỉ 0x000000B0 int *p = &a; // p trỏ vào a -> p = 0x000000A0 int &r = a; // r là tham chiếu của a r = 10; // -> a = 10 b = *p; // p đang trỏ vào a -> b = 10 p = &b; // p trỏ vào b -> p = 0x000000B0 *p = 5; // -> b = 5 IV. Hàm, mảng và con trỏ 52 • Con trỏ và mảng • Có thể coi biến mảng như một con trỏ trỏ vào phần tử đầu tiên của mảng • Nếu A là một biến mảng thì (A + i) chính là địa chỉ của A[i] Ví dụ double A[10], *p = A; // 3 đoạn mã tương đương for (int i = 0; i < 10; i++) *(A + i) = 0; // A[i] = 0; for (int i = 0; i < 10; i++) *(p + i) = 0; for (int i = 0; i < 10; i++, p++) *p = 0; IV. Hàm, mảng và con trỏ 53 • Cấp phát bộ nhớ động • Cấp bộ nhớ cho một biến theo nhu cầu cụ thể của chương trình • Biến được cấp bộ nhớ phải là con trỏ • Sử dụng toán tử new • Giải phóng bộ nhớ bằng toán tử delete new kiểu new kiểu[kích_thước] delete tên_biến; delete []tên_biến; IV. Hàm, mảng và con trỏ 54 • Cấp phát bộ nhớ động Ví dụ int *p; p = new int; // cấp vùng nhớ 4 byte cho p // . . . delete p; p = new int[10]; // cấp vùng nhớ 40 byte cho p // . . . delete []p; p = new int[5]; // cấp vùng nhớ 20 byte cho p // . . . delete []p; IV. Hàm, mảng và con trỏ 55 • Thiết kế và cài đặt chương trình thực hiện các thao tác sau: – Khai báo một mảng chứa n số nguyên với n được nhập từ bàn phím – Đặt giá trị ngẫu nhiên từ 1 .. 1000 cho các phần tử của mảng (dùng hàm rand()) – Đếm số lượng số chẵn, số lẻ và số chia hết cho 8 của mảng • Debug đoạn biểu thức sau: char s[100] = "1234567890"; short *p = (short *)s; *(p += 2) = 0x41; cout << s; • Viết chương trình thực hiện các thao tác sau: – Nhập giá trị cho xâu ký tự s (chứa được nhiều nhất 49 ký tự khác NULL) – In s ra màn hình với các chữ cái thường (VD. s = “123ABC”  123abc) – Đổi s thành số nguyên và gán cho biến s (VD. s = “123abc”  a = 123) Yêu cầu: Duyệt các ký tự của s bằng con trỏ IV. Hàm, mảng và con trỏ 56 • Cấu trúc của hàm kiểu tên_hàm(danh sách tham số) { các biểu thức } Vi dụ int factorial(int n) { ... } double power(double x, int n) { ... } void main() { ... } IV. Hàm, mảng và con trỏ 57 • prototype của hàm kiểu tên_hàm(danh sách kiểu); Vi dụ int factorial(int ); double power(double, int ); IV. Hàm, mảng và con trỏ 58 Bảng 4.2. Quy tắc tham số Tham số Khai báo Tham trị kiểu tên Mảng kiểu tên*+ Con trỏ kiểu * tên Tham chiếu kiểu & tên Chú ý: • Dùng tham số con trỏ thay cho mảng trong prototype của hàm • VD. int sum(int *, int); • Có thể dùng từ khóa const để cấm thay đổi giá trị các tham số trong hàm • VD. int max(const int, const int); IV. Hàm, mảng và con trỏ 59 • Tham số mặc định • Được đặt sẵn giá trị • Khai báo ở cuối danh sách tham số • Chỉ cần truyền đối số khi giá trị của đối số khác giá trị mặc định Ví dụ double power(double x, int N = 2) { ... } a = power(3); // N = 2 a = power(3, 4); // N = 4 IV. Hàm, mảng và con trỏ 60 • Toán tử return return; // thoát khỏi hàm // dùng cho các hàm kiểu void Vi dụ void main() { // các biểu thức if (a == 0) return; // các biểu thức } IV. Hàm, mảng và con trỏ 61 • Toán tử return return (biểu thức); // thoát khỏi hàm // dùng cho các hàm khác kiểu void // trả về cho hàm giá trị của biểu thức Vi dụ // hàm tính giá trị lớn nhất của a và b int max(int a, int b) { if (a > b) // return a; // return (a > b? a: b); return b; // } IV. Hàm, mảng và con trỏ 62 • Gọi hàm tên_hàm(danh sách đối số) // tên_hàm phải được khai báo trước khi gọi // danh sách đối số phải phù hợp với danh sách tham số // về số lượng và kiểu Vi dụ void main() { int f = Factorial(5); double p = power(2.5, 3); } IV. Hàm, mảng và con trỏ 63 Bảng 4.2. Quy tắc truyền đối số Đối số / Tham số Tham trị Mảng Con trỏ Tham chiếu Hằng giá trị - - - Biến đơn tên - &tên tên Tham chiếu tên - &tên tên Con trỏ *tên tên tên *tên Mảng - tên tên - IV. Hàm, mảng và con trỏ 64 • Quy tắc truyền đối số // hàm tính tổng N phần tử của mảng A int sum(int A[], int N) { int s = 0; for (int i = 0; i < N; i++) s += A[i]; return s; } void main() { int arr[] = { 1, 2, 3, 4 }; int s = sum(arr, 4); } IV. Hàm, mảng và con trỏ 65 • Quy tắc truyền đối số void change1(int a) { a++; } void change2(int *p) { (*p)++; } void change3(int &r) { r++; } void change4(const int &r) { r++; } // báo lỗi void main() { int x = 10; change1(x); // x không thay đổi change2(&x); // x = 11 change3(x); // x = 12 } IV. Hàm, mảng và con trỏ 66 • Các mô hình định nghĩa hàm // 1.cpp void foo(int a) { // không thể gọi goo } void goo(int a, int b) { // có thể gọi foo } // 2.cpp // prototype của foo và goo extern void foo(int); extern void goo(int, int); // 1.cpp // prototype của foo và goo extern void foo(int); extern void goo(int, int); IV. Hàm, mảng và con trỏ 67 • Các mô hình định nghĩa hàm // 1.cpp // prototype của foo và goo void foo(int); void goo(int, int); void foo(int a) { // có thể gọi goo } void goo(int a, int b) { // có thể gọi foo } // 2.cpp // prototype của foo và goo extern void foo(int); extern void goo(int, int); // 3.cpp // prototype của foo và goo extern void foo(int); extern void goo(int, int); IV. Hàm, mảng và con trỏ 68 • Các mô hình định nghĩa hàm // 1.cpp #include "1.h" void foo(int a) { // có thể gọi goo } void goo(int a, int b) { // có thể gọi foo } #include "1.h" // có thể gọi tất cả // các hàm khai báo // trong 1.h // 1.h #pragma once void foo(int); void goo(int, int); IV. Hàm, mảng và con trỏ 69 • Hàm inline • Chương trình dịch thay các biểu thức của hàm inline vào biểu thức gọi hàm • Không nên chứa các vòng lặp Ví dụ inline double modul(double a, double b) { return sqrt(a * a + b * b); } void main() { cout << modul(3, 4); // cout << sqrt(3* 3 + 4 * 4) } IV. Hàm, mảng và con trỏ 70 • Con trỏ hàm Ví dụ int foo(int n) { if (n < 2) return 1; return n * foo(n – 1); } int goo(int a) { return a * a; } int get(int x, int (*f)(int)) { return f(x); } void main() { cout << get(5, &foo) << ' ' << get(4, &goo); } IV. Hàm, mảng và con trỏ 71 • Hàm trả về tham chiếu Ví dụ int & max(int &a, int &b) { return (a > b? a: b); } void main() { int x = 5, y = 10; cout << max(x, y); max(x, y) = 7; cout << x << ' ' << y; } IV. Hàm, mảng và con trỏ 72 • Các hàm xếp chồng (overload) • Các hàm cùng tên • Phân biệt bằng kiểu hoặc danh sách tham số double power(double x) { return x * x; } double power(double x, int N) { if (N == 0) return 1; if (N < 0) return 1/power(x, -N); return x * power(x, N – 1); } double power(double x, double y) { return exp(y * log(x)); } Ví dụ IV. Hàm, mảng và con trỏ 73 • Các hàm xếp chồng (overload) • Chương trình dịch sẽ tự gọi hàm phù hợp dựa vào các đối số truyền cho hàm double a; a = power(2); // gọi hàm: double power(double) a = power(2, 3); // gọi hàm: double power(double, int) a = power(2, 3.0); // gọi hàm: double power(double, double) IV. Hàm, mảng và con trỏ 74 • Hàm mẫu • Dùng để sinh ra các hàm có cấu trúc giống nhau, chỉ phân biệt về kiểu của các tham số Ví dụ template _T abs(_T x) { return (x < 0? –x: x); } void main() { cout << abs(-1) // hàm sinh: int abs(int x) {...} << abs(2.0); // hàm sinh: double abs(double x) {...} } IV. Hàm, mảng và con trỏ 75 • Cài đặt hàm giải phương trình bậc 2 sau: 𝐟𝐮𝐧𝐜𝐭𝐢𝐨𝐧 FindRoot 𝑎, 𝑏, 𝑐 ∶ ℝ; 𝐯𝐚𝐫 𝑥1, 𝑥2 ∶ ℝ ∶ ℕ 𝑑 ≔ 𝑏2 − 4𝑎𝑐 𝐢𝐟 𝑑 < 0 𝐭𝐡𝐞𝐧 𝐫𝐞𝐭𝐮𝐫𝐧 0 𝐢𝐟 𝑑 = 0 𝐭𝐡𝐞𝐧 𝑥1 ≔ 𝑥2 ≔ − 𝑏 2𝑎 ; 𝐫𝐞𝐭𝐮𝐫𝐧 1 𝑥1 ≔ (−𝑏 − √𝑑)/2𝑎; 𝑥2 ≔ (−𝑏 + √𝑑)/2𝑎 𝐫𝐞𝐭𝐮𝐫𝐧 2 • Thiết kế và cài đặt hàm trả về xâu ký tự theo chuẩn họ tên từ xâu đầu vào. v u H A I m i n h \0 V u H a i M i n h \0 IV. Hàm, mảng và con trỏ 76 • Cài đặt hàm sau: 𝐟𝐮𝐧𝐜𝐭𝐢𝐨𝐧 IsSorted 𝑎 ∶ 𝐀𝐫𝐫𝐚𝐲 1. . 𝑛 𝐨𝐟 ℕ; 𝑡 ∶ *0, 1+ ∶ 0, 1 𝐟𝐨𝐫 𝑖 ≔ 1 𝐭𝐨 𝑛 − 1 𝐝𝐨 𝐢𝐟 𝑡 = 1 ∧ 𝑎 𝑖 > 𝑎 𝑖 + 1 𝐭𝐡𝐞𝐧 𝐫𝐞𝐭𝐮𝐫𝐧 0 𝐢𝐟 𝑡 = 0 ∧ 𝑎 𝑖 < 𝑎 𝑖 + 1 𝐭𝐡𝐞𝐧 𝐫𝐞𝐭𝐮𝐫𝐧 0 𝐫𝐞𝐭𝐮𝐫𝐧 1 • Cài đặt các hàm sắp xếp và tìm kiếm • Viết chương trình so sánh các thuật toán sắp xếp với các mảng 100, 1000, 10000 và 100000 phần tử V. Kiểu dữ liệu trừu tượng Các khái niệm Xây dựng ADT Các toán tử Kế thừa 77 V. Kiểu dữ liệu trừu tượng 78 • Kiểu dữ liệu trừu tượng (ADT) – kiểu được định nghĩa để mô tả cho một sự vật Các tính chất • Đóng gói – các biến và các hàm được khai báo trong một khối, cho phép che dấu các thành viên • Kế thừa – ADT (dẫn xuất) được xây dựng trên nền một ADT khác (cơ sở), có thể sử dụng lại các thành phần của ADT cơ sở • Đối tượng – một biến thuộc một ADT V. Kiểu dữ liệu trừu tượng 79 • Ví dụ: • Một hình chữ nhật (Rectangle) được xác định bởi: – tọa độ góc trên bên trái: x1, y1 – tọa độ góc dưới bên phải: x2, y2 – tính diện tích: Area = (y2 – y1) * (x2 – x1) • Một hình ô van (Elipse) nội tiếp trong hình chữ nhật: – tính diện tích: Area = Rectagle::Area *  / 4 V. Kiểu dữ liệu trừu tượng 80 • Ví dụ (struct): struct Rectangle { double x1, y1; double x2, y2; double Area() { return (y2 - y1) * (x2 - x1); } }; struct Elipse : public Rectangle { double Area() { return Rectangle::Area() * 3.14 / 4; } }; V. Kiểu dữ liệu trừu tượng 81 • Ví dụ (class): class Rectangle { public: double x1, y1; double x2, y2; double Area() { return (y2 - y1) * (x2 - x1); } }; class Elipse : public Rectangle { public: double Area() { return s = Rectangle::Area() * 3.14 / 4; } }; V. Kiểu dữ liệu trừu tượng 82 • Ví dụ (các đối tượng): void main() { Rectangle r = { 1, 1, 6, 3 }; Elipse e; e.x1 = 12; e.y1 = 2; e.x2 = 17; e.y2 = 7; cout << r.Area() << ' ' << e.Area(); } V. Kiểu dữ liệu trừu tượng 83 • Các vùng truy cập protected public private V. Kiểu dữ liệu trừu tượng 84 • Cấu trúc của ADT class tên_ADT { private|protected|public: // các biến thành viên (các thuộc tính) private|protected|public: // các hàm tạo public: // hàm hủy private|protected|public: // các hàm thành viên khác (các phương thức) public: // các toán tử thành viên // các hàm và các toán tử friend }; V. Kiểu dữ liệu trừu tượng 85 • Cấu trúc của ADT • Các hàm đơn giản (không chứa các vòng lặp hoặc rất ngắn) có thể định nghĩa inline class tên_ADT { kiểu tên_hàm(danh sách tham số) { // các biểu thức } }; V. Kiểu dữ liệu trừu tượng 86 • Cấu trúc của ADT • Các hàm phức tạp nên định nghĩa ngoài khối khai báo ADT class tên_ADT { kiểu tên_hàm(danh sách tham số); }; kiểu tên_ADT::tên_hàm(danh sách tham số) { // các biểu thức } V. Kiểu dữ liệu trừu tượng 87 • Hàm tạo và hàm hủy Hàm tạo (constructor) • Dùng để thiết lập giá trị cho các biến hoặc cấp phát bộ nhớ cho các mảng động • Được gọi trong các biểu thức khai báo đối tượng hoặc cấp phát bộ nhớ Hàm hủy (destructor) • Dùng để giải phóng bộ nhớ đã cấp phát • Được gọi khi kết thúc khối khai báo đối tượng hoặc trong biểu thức giải phóng bộ nhớ V. Kiểu dữ liệu trừu tượng 88 • Hàm tạo và hàm hủy class tên_ADT { public: tên_ADT(); // hàm tạo mặc định tên_ADT(danh sách tham số); // hàm tạo thiết lập tên_ADT(const tên_kiểu &); // hàm tạo copy ~tên_ADT(); // hàm hủy }; V. Kiểu dữ liệu trừu tượng 89 • Định nghĩa hàm tạo (inline) class tên_ADT { public: tên_ADT(danh sách tham số) : tên_biến(biểu thức) , ... { // các biểu thức } }; V. Kiểu dữ liệu trừu tượng 90 • Ví dụ (class Time) class Time { long ticks; public: Time() { ticks = 0; } Time(long value) : ticks(value) { } Time(const Time & t) : ticks(t.ticks) { } ~Time() { } public: long Seconds() { return ticks / 1000; } long Minutes() { return Seconds() / 60; } long Hours() { return Seconds() / 3600; } }; V. Kiểu dữ liệu trừu tượng 91 • Ví dụ (class Time) void main() { Time *p; Time t1; // gọi Time() Time t2(1000); // gọi Time(long) Time t3 = t2; // gọi Time(const Time &) p = new Time(100); // gọi Time(long) cout << t2.Seconds() << endl; cout Seconds() << endl; delete p; // gọi ~Time() của *p } // gọi ~Time() của t3, t2 và t1 V. Kiểu dữ liệu trừu tượng 92 • Ví dụ (class String) – Các biến thành viên và các hàm static class String { char *data; // Vùng dữ liệu chứa các ký tự int len; // Số ký tự public: // Lấy độ dài xâu src static int GetLength(const char * src); // copy xâu src vào dst static void Copy(char * dst, const char * src); V. Kiểu dữ liệu trừu tượng 93 • Ví dụ (class String) – Các hàm private private: // Hàm tạo đối lượng chứa được n ký tự String(int n) { createData(n); } // copy xâu src vào data void copyData(const char * src) { Copy(data, src); } // Tạo vùng dữ liệu chứa n ký tự void createData(int n) { len = n; data = new char[n + 1]; data[n] = 0; } V. Kiểu dữ liệu trừu tượng 94 • Ví dụ (class String) – Các hàm tạo và hàm hủy public: String() { createData(0); } String(const char * src) { createData(GetLength(src)); copyData(src); } String(const String & src) { createData(src.len); copyData(src.data); } ~String() { delete[] data; } V. Kiểu dữ liệu trừu tượng 95 • Ví dụ (class String) – Các hàm public public: // Lấy số ký tự int Length() { return len; } // So sánh với đối tượng src int Compare(const String & src) const { return Compare(src.data); } // So sánh với xâu src int Compare(const char * src) const; V. Kiểu dữ liệu trừu tượng 96 • Ví dụ (class String) – Các toán tử public: String operator=(const char * src); String operator=(String & src); // Các toán tử khác }; // class String V. Kiểu dữ liệu trừu tượng 97 • Ví dụ (class String) – Định nghĩa các hàm int String::GetLength(const char * src) { register int i = 0; while (src[i]) ++i; return i; } void String::Copy(char *dst, const char * src) { for (register int i = 0; src[i]; i++) dst[i] = src[i]; } V. Kiểu dữ liệu trừu tượng 98 • Ví dụ (class String) – Định nghĩa các hàm int String::Compare(const char *src) const { for (int i = 0; i <= len; i++) { if (data[i] != src[i]) return (data[i] > src[i]? 1: -1); } return 0; } V. Kiểu dữ liệu trừu tượng 99 • Toán tử gán { Time t1, t2; String s1, s2; t1 = t2; s1 = s2; } t1.ticks = t2.ticks s1.len = s2.len s1.data = s2.data delete[] s2.data delete[] s1.data sinh ra lỗi vì s1.data đã bị xóa V. Kiểu dữ liệu trừu tượng 100 • Toán tử gán // Bổ sung toán tử gán cho String String& operator=(const String & right) { delete [] data; // xóa vùng dữ liệu cũ createData(right.len); // tạo vùng dữ liệu mới copyData(right.data); // copy dữ liệu từ src return *this; // trả về bản thân đối tượng } V. Kiểu dữ liệu trừu tượng 101 • Các toán tử số học // Bổ sung toán tử số học cho Time Time operator+(const Time right) { return Time(ticks + right.ticks); } // Bổ sung toán tử số học cho String String operator+(const String & right) { String s(len + right.len); copy(s.data, data); copy(s.data + len, right.data); return s; } (const Time right) (const String & right) Có gì khác nhau ? V. Kiểu dữ liệu trừu tượng 102 • Các toán tử kết hợp // Bổ sung toán tử kết hợp cho Time Time & operator+=(const Time right) { ticks += right.ticks; return *this; } // Bổ sung toán tử kết hợp cho String String operator+=(const String & right) { String s(len + right.len); copy(s.data, data); copy(s.data + len, right.data); len = s.len; char *p = data; data = s.data; s.data = p; return *this; } V. Kiểu dữ liệu trừu tượng 103 • Các toán tử so sánh // Bổ sung toán tử so sánh cho Time int operator==(const Time right) const { return (ticks == right.ticks); } // Bổ sung toán tử so sánh cho String int operator==(const String & right) const { return (Compare(right.data) == 0); } V. Kiểu dữ liệu trừu tượng 104 • Toán tử chỉ số // Bổ sung toán tử chỉ số cho String char & operator[](int index) { return data[index]; } V. Kiểu dữ liệu trừu tượng 105 • Toán tử hàm kiểu operator()(danh sách tham số) { ... } Ví dụ  Lấy giá trị của hàm theo một tập các đối số  Truy cập phần tử của mảng n chiều V. Kiểu dữ liệu trừu tượng 106 • Các toán tử tăng/giảm // Bổ sung toán tử ++ cho Time // Trường hợp toán tử ở bên phải Time & operator++() { ticks++; return *this; } // Trường hợp toán tử ở bên trái friend Time & operator++(Time & right) { right.ticks++; return right; } V. Kiểu dữ liệu trừu tượng 107 • Các toán tử luồng vào/ra // Bổ sung toán tử luồng ra cho Time friend ostream & operator<<(ostream & left, Time & right) { left << right.Hours() << ':' << right.Minutes() % 60 << ':' << right.Seconds() % 60 << '.' << right.ticks % 1000; return left; } // Bổ sung toán tử luồng ra cho String friend ostream & operator<<(ostream & left, Time & right) { return left << right.data; } V. Kiểu dữ liệu trừu tượng 108 • Các toán tử ép kiểu // Bổ sung toán tử ép sang kiểu long cho Time operator long() { return ticks; } // Bổ sung toán tử ép sang kiểu xâu ký tự cho String operator char*() { return data; } V. Kiểu dữ liệu trừu tượng 109 • Xây dựng class PhanSo mô tả kiểu phân số gồm các thành phần sau: – Hai biến a, b chứa tử số và mẫu số – Các hàm tạo – Các toán tử cộng, trừ, nhân, chia và kết hợp – Toán tử luồng ra VD. PhanSo a(2, 4); cout << a + 1;  3/2 • Xây dựng class Complex mô tả kiểu số phức gồm các thành phần sau: – Hai biến r, i chứa phần thực và phần ảo – Các hàm tạo – Các toán tử cộng, trừ, nhân, chia và kết hợp – Toán tử hàm để lấy mô-đun – Toán tử luồng ra VD. Complex z(1, 3); cout << z + 1;  (2, 3i) V. Kiểu dữ liệu trừu tượng 110 • Mô hình class ADT_cơ_sở { protected|public: virtual void foo() { ... } }; class ADT_dẫn_xuất : public|protected|private ADT_cơ_sở { protected|public: void foo() { // phần mở rộng ADT_cơ_sở::foo(); // phần mở rộng } }; ADT_dẫn_xuất : public ADT_cơ_sở V. Kiểu dữ liệu trừu tượng 111 • Các vùng truy cập ADT_cơ_sở protected public private V. Kiểu dữ liệu trừu tượng 112 • Ví dụ về sự kế thừa class B { protected: int x; public: B(int a = 0) : x(a) { } virtual void Print() { cout << x; } void Inc() { x++; } }; class D : public B { int x; public: D(int a, int b) : x(a), B(b) { } void Print() { cout << x << ", "; B::Print(); } }; V. Kiểu dữ liệu trừu tượng 113 • Ví dụ về sự kế thừa void main() { B b(5); D d(1, 2); d.Inc(); B *p = &b; p->Print(); // gọi B::Print() -> 5 p = &d; p->Print(); // gọi D::Print() -> 1, 3 } V. Kiểu dữ liệu trừu tượng 114 • Lớp cơ sở trừu tượng class ADT_cơ_sở { ... virtual void foo() = 0; }; class ADT_dẫn_xuất : public|protected|private ADT_cơ_sở { ... void foo() { // ... } }; V. Kiểu dữ liệu trừu tượng 115 • Lớp cơ sở trừu tượng class Shape { String _name; public: Shape(const char *name) : _name(name) { } void Print() { cout << _name << ": Area = " << Area() << endl; } virtual double Area() = 0; }; V. Kiểu dữ liệu trừu tượng 116 • Kế thừa từ lớp cơ sở trừu tượng class Rectangle : public Shape { int _w, _h; public: Rectangle(int a, int b) : Shape("Rectangle"), _w(a), _h(b) { } double Area() { return _w * _h; } }; V. Kiểu dữ liệu trừu tượng 117 • Kế thừa lớp cơ sở trừu tượng class Triangle : public Shape { int _a, _b, _c; public: Triangle(int a, int b, int c) : Shape("Triangle"), _a(a), _b(b), _c(c) { } double Area() { double s = (_a + _b + _c) / 2; return sqrt(s * (s - _a) * (s - _b) * (s - _c)); } }; V. Kiểu dữ liệu trừu tượng 118 • Ví dụ void main() { Shape *s[2]; s[0] = new Rectangle(2, 5); s[1] = new Triangle(3, 4, 5); for (int i = 0; i < 2; i++) { s[i]->Print(); delete s[i]; } } Rectangle: Area = 10 Triangle: Area = 12 VI. Các cấu trúc dữ liệu cơ bản 119 • ADT mẫu template class Shape { _T edge[n]; // các cạnh public: _T Bound(); }; template _T Shape::Bound() { int c = 0; for (int i = 0; i < n; i++) c += edge[i]; return c; } void main() { Shape tamGiac; // tạo ra class Shape có 3 cạnh kiểu int Shape tuGiac;// tạo ra class Shape có 4 cạnh kiểu double } V. Kiểu dữ liệu trừu tượng 120 • class Matrix mô tả một ma trận được cho dưới đây template class Matrix { _T **data; int rows, cols; // số hàng và số cột void createData(); // tạo vùng dữ liệu từ rows và cols void createData(int m, int n); // tạo vùng dữ liệu m hàng, n cột void deleteData(); // xóa dữ liệu public: Matrix() : data(0) { } Matrix(int m, int n = 0); // tạo ma trận mxn hoặc mxm Matrix(int m, int n, const _T*); // tạo ma trận mxn kiểu ưu tiên // hàng từ mảng 1 chiều Matrix(const Matrix& M); ~Matrix() { deleteData(); } _T& operator()(int i, int j) { return data[i][j]; } }; V. Kiểu dữ liệu trừu tượng 121 • Định nghĩa các hàm của Matrix template void Matrix::createData() { data = new _T *[rows]; for (int i = 0; i < rows; i++) data[i] = new _T[cols]; } template void Matrix::deleteData() { if (data == 0) return; for (int i = 0; i < rows; i++) delete []data[i]; delete data; } V. Kiểu dữ liệu trừu tượng 122 • Các yêu cầu: – Hoàn thành tất cả các hàm của class Matrix – Bổ sung toán tử gán, và cộng ma trận – Xây dựng class Graphic mô tả đồ thị có hướng không trọng số kế thừa từ Matrix và có thể sử dụng trong đoạn biểu thức sau: int M[] = { 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0 }; Graphic g(5, M); g.DFT(2); // in ra màn hình chỉ số các đỉnh // theo chiều sâu bắt đầu từ đỉnh 2 VI. Các cấu trúc dữ liệu cơ bản Array, BoundStack và BoundQueue LinkedList Binary Search Tree 123 Link đến file code đầy đủ: https://docs.google.com/open?id=0B4vBa0QnLWSraGRyVkJKaFUwekE VI. Các cấu trúc dữ liệu cơ bản 124 template class Array { protected: T *data; int size; public: Array(); Array(int length); Array(const Array& a); ~Array(); public: void CopyFrom(T *); int Size(); public: T& operator[](int index); Array& operator=(const Array& a); }; VI. Các cấu trúc dữ liệu cơ bản 125 template class BoundStack : protected Array { int top; public: BoundStack(); BoundStack(int size); public: void Push(T value); T Pop(); T Top(); int IsEmpty(); int IsFull(); int Count(); T operator[](int index); }; VI. Các cấu trúc dữ liệu cơ bản 126 template class BoundQueue : protected Array { int front, rear; int count; void Inc(int &i); public: BoundQueue(); BoundQueue(int size); public: void Enqueue(T value); T Dequeue(); int IsEmpty(); int IsFull(); int Count(); T operator[](int index); }; VI. Các cấu trúc dữ liệu cơ bản 127 • Ứng dụng stack trong QuickSort template class Sort { class Segment { public: int Lb, Ub; Segment() { } Segment(int l, int r) : Lb(l), Ub(r) { } void Swap(T &a, T &b) { T t = a; a = b; b = t; } int DoPart(Array &); // Phân đoạn Array // Sắp xếp Array trong đoạn [Lb, Ub] bằng InsertSort void DoSort(Array &); }; // Segment public: static void DoSort(Array &); }; VI. Các cấu trúc dữ liệu cơ bản 128 • Ứng dụng stack trong QuickSort template void Sort::DoSort(Array &a) { int n0 = 10, len = a.Size(); BoundStack s(len/n0 + 1); s.Push(Segment(0, len - 1)); while (!s.IsEmpty()) { Segment b = s.Pop(); if (b.Ub - b.Lb + 1 > n0) { int j = b.DoPart(a); if (b.Lb < j - 1) s.Push(Part(b.Lb, j - 1)); if (b.Ub > j + 1) s.Push(Part(j + 1, b.Ub)); } else b.DoSort(a); } } VI. Các cấu trúc dữ liệu cơ bản 129 • Sử dụng class Sort #include "stdafx.h" #include "ds.h" #include using namespace std; int main() { int v[] = { 7, 5, 4, 8, 9, 1, 3, 2, 0, 6 }; Array a(10); a.CopyFrom(v); Sort::DoSort(a); for (int i = 0; i < a.Size(); i++) cout << a[i] << ' '; } VI. Các cấu trúc dữ liệu cơ bản 130 • class LinkedList template class LinkedList { protected: // Đoạn định nghĩa các lớp con // baseList h; int n; public: LinkedList() : n(0) { } ~LinkedList() { h.makeEmpty(); } int IsEmpty() { return n == 0; } int Count() { return n; } _Ti PopBegin(); _Ti PopEnd(); void RemoveAll() { h.makeEmpty(); n = 0; } void PushBegin(const _Ti& i); void PushEnd(const _Ti& i) }; VI. Các cấu trúc dữ liệu cơ bản 131 • Các lớp con class baseList { public: baseList *next, *prev; baseList() { next = prev = this; } void insertAfter(const _Ti& info); void remove(); void makeEmpty(); }; class infoList : public baseList { public: _Ti info; infoList(const _Ti& i) : info(i) { } }; VI. Các cấu trúc dữ liệu cơ bản 132 • Ứng dụng – đổi cơ số đếm std::string IntToBin(int x) { std::string s; LinkedList stack; do { char c = (char)((x & 1) + 48); x >>= 1; stack.PushBegin(c); } while (x); while (!stack.IsEmpty()) s += stack.PopBegin(); return s; } VI. Các cấu trúc dữ liệu cơ bản 133 • class cơ sở template class baseBST { public: baseBST() { } virtual baseBST * insert(const _Ti& ) = 0; virtual baseBST * contents(const _Ti& ) { return 0 ; } virtual baseBST * remove(const _Ti& ) { return this; } virtual baseBST * getSuccessor() { return 0; } virtual void makeEmpty() { } virtual _Ti * Info() { return 0; } }; template int _compare(const _Ti& a, const _Ti& b) { return (a b); } VI. Các cấu trúc dữ liệu cơ bản 134 • class BST template class BST { // Đoạn định nghĩa các class con // nullBST nullBST; baseBST * root; public: BST() { root = (baseBST *)&nullBST; } ~BST() { root->makeEmpty(); } void Insert(const _Ti& info) { root = root->insert(info); } void Delete(const _Ti& i) { root = root->remove(i); } bool Contents(const _Ti& i) { return root->contents(i); } }; VI. Các cấu trúc dữ liệu cơ bản 135 • Định nghĩa các class con class nullBST : baseBST { public: baseBST * insert(const _Ti& i) { return new infoBST(i, this); } }; class infoBST : baseBST { _Ti info; baseBST *left, *right; public: infoBST(const _Ti& i, baseBST *nullBST) : info(i) { left = right = nullBST; } void makeEmpty(); baseBST * insert(const _Ti& ); baseBST * contents(const _Ti& ); baseBST * remove(const _Ti& ); baseBST * getSuccessor(); }; VI. Các cấu trúc dữ liệu cơ bản 136 • Ứng dụng – kiểm tra khai báo biến #include "ds.h" #include using namespace std; class VarDef { public: string name; int line; VarDef() { } VarDef(const char* s, int l) : name(s), line(l) { } static int compare(const VarDef& a, const VarDef& b) { return a.name.compare(b.name); } }; VI. Các cấu trúc dữ liệu cơ bản 137 • Ứng dụng – kiểm tra khai báo biến void main() { char vars[][100] = { "x", "y", "a", "b", "x", "k", "i", "k", "m", "n" }; BST bst; BoundQueue e(10); for (int i = 0; i < 10; i++) { VarDef v(vars[i], i + 1); if (!bst.Contents(v)) bst.Insert(v); else e.Enqueue(v); } for (int i = 0; i < e.Count(); i++) { VarDef v(e[i]); cout << "redefinition variable " << v.name.data() << " in line " << v.line << endl; } }