Bài giảng môn học Lập trình nâng cao - Nguyễn Hải Minh

Nội dung text: Bài giảng môn học Lập trình nâng cao - Nguyễn Hải Minh

1. TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG KHOA CÔNG NGHỆ THÔNG TIN o0o BÀI GIẢNG MÔN HỌC LẬP TRÌNH NÂNG CAO Tên môn học: Lập trình nâng cao Số tin chỉ/ĐVHT: 3TC (2LT: 1TH) Hệ đào tạo: Đại học Ngành: Các ngành Số tín chỉ thực hành: 1 TC Giảng viên biên soạn: 1. Nguyễn Hải Minh 2. Nguyễn Tuấn Anh 3. Hà Mạnh Hùng 4. Nguyễn Quang Hiệp 5. Trần Lâm Bộ môn: Công nghệ lập trình và Ứng dụng Thái Nguyên - 2016
2. TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG KHOA CÔNG NGHỆ THÔNG TIN o0o BÀI GIẢNG MÔN HỌC LẬP TRÌNH NÂNG CAO KHOA PHÊ DUYỆT BỘ MÔN PHÊ DUYỆT GIÁO VIÊN PHỤ TRÁCH Thái nguyên, Năm 2016
3. MỤC LỤC CHƯƠNG 1: CON TRỎ 4 1.1 KHÁI NIỆM CON TRỎ 4 1.1.1 Khai báo con trỏ 4 1.1.2 Sử dụng con trỏ 4 1.2 CON TRỎ VÀ MẢNG 7 1.2.1 Con trỏ và mảng ộm t chiều 7 1.2.2 Con trỏ và mảng nhiều chiều 10 1.3. CON TRỎ HÀM 11 1.4 CẤP PHÁT ỘB NHỚ ỘĐ NG 14 1.4.1 Cấp phát bộ nhớ động cho biến 14 1.4.2 Cấp phát bộ nhớ cho mảng động một chiều 15 1.4.3 Cấp phát bộ nhớ cho mảng động nhiều chiều 17 CHƯƠNG 2: CÁC DÒNG NHẬP XUẤT VÀ TỆP TIN 23 2.1. NHẬP/XUẤT VỚI CIN/COUT 24 2.1.1. Toán tử nhập >> 24 2.1.2. Các hàm nhập kí tự và xâu kí tự 25 2.1.3. Toán tử xuất << 28 2.2. ĐỊNH DẠNG 28 2.2.1.Các phương thức định dạng 28 2.2.2. Các cờ định dạng 29 2.2.3. Các bộ và hàm định dạng 31 2.3. IN RA MÁY IN 32 2.4. LÀM VIỆC VỚI FILE 33 2.4.1. Tạo đối tượng gắn với file 33 2.4.2 Đóng file và giải phóng đối tượng 34 2.4.3. Kiểm tra sự tồn tại của file, kiểm tra hết file 37 2.4.4. Đọc ghi đồng thời trên file 38 2.4.5. Di chuyển con trỏ file 39 1
4. 2.5. NHẬP/XUẤT NHỊ PHÂN 41 2.5.1. Khái niệm về 2 loại file: văn bản và nhị phân 41 2.5.2.Đọc, ghi kí tự 41 2.5.3. Đọc, ghi dãy kí tự 42 2.5.4. Đọc ghi đồng thời 43 CHƯƠNG 3: DỮ LIỆU KIỂU CẤU TRÚC VÀ HỢP 48 3.1. KIỂU CẤU TRÚC 48 3.1.1. Khai báo, khởi tạo 48 3.1.2.Truy nhập các thành phần kiểu cấu trúc 50 3.1.3. Phép toán gán cấu trúc 52 3.1.4. Các ví dụ minh hoạ 53 3.1.5.Hàm với cấu trúc 56 3.1.6.Cấu trúc với thành phần kiểu bit 67 3.1.7.Câu lệnh typedef 68 3.1.8.Hàm sizeof() 69 3.2. CẤU TRÚC TỰ TRỎ VÀ DANH SÁCH LIÊN KẾT 69 3.2.1.Cấu trúc tự trỏ 70 3.2.2. Khái niệm danh sách liên kết 72 3.2.3. Các phép toán trên danh sách liên kết 73 3.3. KIỂU HỢP 79 3.3.1. Khai báo 79 3.3.2. Truy cập 79 3.4. KIỂU LIỆT KÊ 80 CHƯƠNG 4: XỬ LÝ NGOẠI LỆ 86 4.1. Xử lý ngoại lệ 86 4.2. Ném Exception trong C++ 87 4.3. Bắt Exception trong C++ 87 4.4.Chuẩn Exception trong C++ 88 4.5. Định nghĩa Exception mới trong C++ 90 2
5. CHƯƠNG 5: MỘT SỐ VẤN ĐỀ 92 5.1. Một số quy tắc trong lập trình C++ 92 5.1.1. Tổ chức chương trình 92 5.1.2. Chuẩn tài liệu 93 5.1.3. Tên 93 5.1.4. Định dạng 95 5.1.5. Thiết kế 96 5.1.6. Code 97 5.2. Namespaces 103 5.1.1. Using namespace 104 5.1.2. Định nghĩa bí danh 106 5.1.3. Namespace std 106 Tài liệu tham khảo 108 3
6. CHƯƠNG 1: CON TRỎ 1.1 KHÁI NIỆM CON TRỎ 1.1.1 Khai báo con trỏ Con trỏ là ộm t biến đặc biệt chứa địa chỉ của một biến khác. Con trỏ có cùng kiểu dữ liệu với kiểu dữ liệu của biến mà nó trỏ tới. Cú pháp khai báo một con trỏ như sau: * ; Trong đó: Kiểu dữ liệu: Có thể là các kiểu dữ liệu cơ bản của C++, hoặc là kiểu dữ liệu có cấu trúc, hoặc là kiểu đối tượng do người dùng tự định nghĩa. Tên con trỏ: Tuân theo qui tắc đặt tên biến của C++: - Chỉ được bắt đầu bằng ộm t kí tự (chữ), hoặc dấu gạch dưới “_”. - Bắt đầu từ kí tự thứ hai, có thể có kiểu kí tự số. - Không có dấu trống (space bar) trong tên biến. - Có phân biệt chữ hoa và chữ thường. - Không giới hạn độ dài tên biến. Ví dụ, để khai báo ộm t biến con trỏ có kiểu là int và tên là pointerInt, ta viết như sau: int *pointerInt; Lưu ý Có thể viết dấu con trỏ “*” ngay sau kiểu dữ liệu, nghĩa là hai cách khai báo sau là tương đương: int *pointerInt; int* pointerInt; Các cách khai báo con trỏ như sau là sai cú pháp: *int pointerInt; // Khai báo sai con trỏ int pointer int*; // Khai báo sai con trỏ 1.1.2 Sử dụng con trỏ Con trỏ được sử dụng theo hai cách: Dùng con trỏ để lưu địa chỉ của biến để thao tác Lấy giá trị của biến do con trỏ trỏ đến để thao tác 4
7. Dùng con trỏ để lưu địa chỉ của biến Bản thân con trỏ sẽ được trỏ vào địa chỉ của một biến có cùng kiểu dữ liệu với nó. Cú pháp của phép gán như sau: = & ; Lưu ý Trong phép toán này, tên con trỏ không có dấu “*”. Ví dụ: int x, *px; px = &x; sẽ cho con trỏ px có kiểu int trỏ vào địa chỉ của biến x có kiểu nguyên. Phép toán & sẽ cho địa chỉ của biến tương ứng. Lấy giá trị của biến do con trỏ trỏ đến Phép lấy giá trị của biến do con trỏ trỏ đến được thực hiện bằng cách gọi tên: * ; Lưu ý Trong phép toán này, phải có dấu con trỏ “*”. Nếu không có dấu con trỏ, sẽ trở thành phép lấy địa chỉ của biến do con trỏ trỏ tới. Ví dụ: int x = 12, y, *px; px = &y; *px = x; Quá trình diễn ra như sau: int x = 12, y, *px; //x=12, y=0, px null px = &y; //x=12, y=0  px px = x; // x=12, y=x=12  px con trỏ px vẫn trỏ tới địa chỉ biến y và giá trị của biến y sẽ là 12. Phép gán giữa các con trỏ Các con trỏ cùng kiểu có thể gán cho nhau thông qua phép gán và lấy địa chỉ con trỏ: = ; Lưu ý Trong phép gán giữa các con trỏ, bắt buộc phải dùng phép lấy địa chỉ của biến do con trỏ trỏ tới (không có dấu “*” trong tên con trỏ) mà không được dùng phép lấy giá trị của biến do con trỏ trỏ tới. 5
8. Hai con trỏ phải cùng kiểu. Trong trường hợp hai con trỏ khác kiểu, phải sử dụng các phương thức ép kiểu tương tự như trong phép gán các biến thông thường có kiểu khác nhau. Ví dụ: int x = 12, *px, *py; px = &x; py = px; int x = 12, *px, *py; //x=12, px null, py null px = &x; // x=12  px, py null py = px; // x=12 px, py x=12 con trỏ py cũng trỏ vào địa chỉ của biến x như con trỏ px. Khi đó *py cũng có giá trị 12 giống như *px và là giá trị của biến x. Chương trình 1.1 minh hoạ việc dùng con trỏ giữa các biến của một chương trình C++ Chương trình 1.1 #include #include void main(void){ int x = 12, *px, *py; cout << ”x = ” << x << endl; px = &x; // Con trỏ px trỏ tới địa chỉ của x cout << ”px = &x, *px = ” << *px << endl; *px=*px+20; //Nộidungcủapxlà32 cout << ”*px = *px+20, x = ” << x << endl; py = px; // Cho py trỏ tới chỗ mà px trỏ: địa chỉ của x *py += 15; // Nội dung của py là 47 cout<<”py=px,*py+=15,x= ”<<x<<endl; } Trong chương trình 1.1, ban đầu biến x có giá trị 12. Sau đó, con trỏ px trỏ vào địa chỉ của biến x nên con trỏ px cũng có giá trị 12. Tiếp theo, ta tăng giá trị của con trỏ px thêm 20, giá trị của con trỏ px là 32. Vì px đang trỏ đến địa chỉ của x nên x cũng có giá trị là 32. Sau đó, ta cho con trỏ py trỏ đến vị trí mà px đang trỏ tới (địa chỉ của biến x) nên py cũng có giá trị 32. Cuối cùng, ta tăng giá trị của con trỏ py thêm 15, py sẽ có giá trị 37. Vì py cũng đang trỏ đến địa chỉ của x nên x cũng có giá trị 37. Do đó, ví dụ 1.1 sẽ in ra kết quả như sau: 6
9. x = 12 px = &x, *px = 12 *px = *px + 20, x = 32 py = px, *py += 15, x = 47 1.2 CON TRỎ VÀ MẢNG 1.2.1 Con trỏ và mảng một chiều Mảng một chiều Trong C++, tên một mảng được coi là một kiểu con trỏ hằng, được định vị tại một vùng nhớ xác định và địa chỉ của tên mảng trùng với địa chỉ của phần tử đầu tiên của mảng. Ví dụ khai báo: int A[5]; thì địa chỉ của mảng A (cũng viết là A) sẽ trùng với địa chỉ phần tử đầu tiên của mảng A (là &A[0]) nghĩa là: A = &A[0]; Quan hệ giữa con trỏ và mảng Vì tên của mảng được coi như một con trỏ hằng, nên nó có thể được gán cho một con trỏ có cùng kiểu. Ví dụ khai báo: int A[5] = {5, 10, 15, 20, 25}; int *pa = A; int A[5] = {5, 10, 15, 20, 25}; int *pa = A; thì con trỏ pa sẽ trỏ đến mảng A, tức là trỏ đến địa chỉ của phần tử A[0], cho nên hai khai báo sau là tương đương: pa = A; pa = &A[0]; Với khai báo này, thì địa chỉ trỏ tới của con trỏ pa là địa chỉ của phần tử A[0] và giá trị của con trỏ pa là giá trị của phần tử A[0], tức là *pa = 5; Phép toán trên con trỏ và mảng Khi một con trỏ trỏ đến mảng, thì các phép toán tăng hay giảm trên con trỏ 7
10. sẽ tương ứng với phép dịch chuyển trên mảng. Ví dụ khai báo: int A[5] = {5, 10, 15, 20, 25}; int *pa = &A[2]; thì con trỏ pa sẽ trỏ đến địa chỉ của phần tử A[2] và giá trị của pa là: *pa = A[2] = 15. Khi đó, phép toán: pa = pa + 1; sẽ đưa con trỏ pa trỏ đến địa chỉ của phần tử tiếp theo của mảng A, đó là địa chỉ của A[3]. Sau đó, phép toán: pa = pa – 2; sẽ đưa con trỏ pa trỏ đến địa chỉ của phần tử A[1] int A[5] = {5, 10, 15, 20, 25}; int *pa = &A[2]; pa = pa + 1; pa = pa - 2; Lưu ý: • Hai phép toán pa++ và *pa++ có tác dụng hoàn toàn khác nhau trên mảng, pa++ là thao tác trên con trỏ, tức là trên bộ nhớ, nó sẽ đưa con trỏ pa trỏ đến địa chỉ của phần tử tiếp theo của mảng. *pa++ là phép toán trên giá trị, nó tăng giá trị hiện tại của phần tử mảng lên ộm t đơn vị. Ví dụ: int A[5] = {5, 10, 15, 20, 25}; int *pa = &A[2]; Thì pa++ là tương đương với pa = &A[3] và *pa = 20. Nhưng *pa++ lại tương đương với pa = &A[2] và *pa = 15+1 = 16, A[2] = 16. 8
11. int A[5] = {5, 10, 15, 20, 25}; int *pa = &A[2]; pa ++; Nhưng *pa ++; Trong trường hợp: int A[5] = {5, 10, 15, 20, 25}; int *pa = &A[4]; thì phép toán pa++ sẽ đưa con trỏ pa trỏ đến một địa chỉ không xác định. Lí do là A[4] là phần tử cuối của mảng A, nên pa++ sẽ trỏ đến địa chỉ ngay sau địa chỉ của A[4], địa chỉ này nằm ngoài vùng chỉ số của mảng A nên không xác định. Tương tự với trường hợp pa=&A[0], phép toán pa cũng đưa pa trỏ đến một địa chỉ không xác định int A[5] = {5, 10, 15, 20, 25}; int *pa = &A[4]; pa ++; pa = &A[0]; pa ; • Vì mảng A là con trỏ hằng, cho nên không thể thực hiện các phép toán trên A mà chỉ có thể thực hiện trên các con trỏ trỏ đến A: các phép toán pa++ hoặc pa là hợp lệ, nhưng các phép toán A++ hoặc A là không hợp lệ. 9
12. Chương trình 2.2a minh hoạ việc cài đặt một thủ tục sắp xếp các phần tử của một mảng theo cách thông thường. Chương trình 2.2a void SortArray(int A[], int n){ int temp; for(int i=0; i A[j]){ temp = A[i]; A[i] = A[j]; A[j] = temp; } } Chương trình 2.2b cài đặt một thủ tục tương tự bằng con trỏ. Hai thủ tục này có chức năng hoàn toàn giống nhau. Chương trình 2.2b void SortArray(int *A, int n){ int temp; for(int i=0; i *(A+j)){ temp = *(A+i); *(A+i) = *(A+j); *(A+j) = temp; } Trong chương trình 2.2b, thay vì dùng một mảng, ta dùng một con trỏ để trỏ đến mảng cần sắp xếp. Khi đó, ta có thể dùng các thao tác trên con trỏ thay vì các thao tác trên các phần tử mảng. 1.2.2 Con trỏ và mảng nhiều chiều Con trỏ và mảng nhiều chiều Một câu hỏi đặt ra là nếu ộm t ma trận một chiều thì tương đương với một con trỏ, vậy một mảng nhiều chiều thì tương đương với con trỏ như thế nào? Xét ví dụ: int A[3][3] = { 10
13. {5, 10, 15}, {20, 25, 30}, {35, 40, 45} }; Khi đó, địa chỉ của ma trận A chính là địa chỉ của hàng đầu tiên của ma trận A, và cũng là địa chỉ của phần tử đầu tiên của hàng đầu tiên của ma trận A: Địa chỉ của ma trận A: A = A[0] = *(A+0) = &A[0][0]; Địa chỉ của hàng thứ nhất: A[1] = *(A+1) = &A[1][0]; Địa chỉ của hàng thứ i: A[i] = *(A+i) = &A[i][0]; Địa chỉ phần tử &A[i][j] = (*(A+i)) + j; Giá trị phần tử A[i][j] = *((*(A+i)) + j); Như vậy, một mảng hai chiều có thể thay thế bằng một mảng một chiều các con trỏ cùng kiểu: int A[3][3]; có thể thay thế bằng: int (*A)[3]; Con trỏ trỏ tới con trỏ Vì một mảng hai chiều int A[3][3] có thể thay thế bằng một mảng các con trỏ int (*A)[3]. Hơn nữa, ộm t mảng int A[3] lại có thể thay thế bằng một con trỏ int *A. Do vậy, một mảng hai chiều có thể thay thế bằng một mảng các con trỏ, hoặc một con trỏ trỏ đến con trỏ. Nghĩa là các cách viết sau là tương đương: int A[3][3]; int (*A)[3]; int A; 1.3. CON TRỎ HÀM Mặc dù hàm không phải là một biến cụ thể nên không có một địa chỉ xác định. Nhưng trong khi chạy, mỗi một hàm trong C++ cũng có một vùng nhớ xác định, do vậy, C++ cho phép dùng con trỏ để trỏ đến hàm. Con trỏ hàm được dùng để truyền tham số có dạng hàm. Khai báo con trỏ hàm Con trỏ hàm được khai báo tương tự như khai báo nguyên mẫu hàm thông thường trong C++, ngoại trừ việc có thêm kí hiệu con trỏ “*” trước tên hàm. Cú pháp khai báo con trỏ hàm như sau: (* )([ ]); 11
14. Trong đó: Kiểu dữ liệu trả về: là các kiểu dữ liệu thông thường của C++ hoặc kiểu do người dùng tự định nghĩa. Tên hàm: tên do người dùng tự định nghĩa, tuân thủ theo quy tắc đặt tên biến trong C++ Các tham số: có thể có hoặc không (phần trong dấu “[]” là tuỳ chọn). Nếu có nhiều tham số, mỗi tham số được phân cách nhau bởi dấu phẩy. Ví dụ khai báo: int (*Calcul)(int a, int b); là khai báo một con trỏ hàm, tên là Calcul, có kiểu int và có hai tham số cũng là kiểu int. Lưu ý: Dấu “()” bao bọc tên hàm là cần thiết để chỉ ra rằng ta đang khai báo một con trỏ hàm. Nếu không có dấu ngoặc đơn này, trình biên dịch sẽ hiểu rằng ta đang khai báo một hàm thông thường và có giá trị trả về là một con trỏ. Ví dụ, hai khai báo sau là khác nhau hoàn toàn: // Khai báo một con trỏ hàm int (*Calcul)(int a, int b); // Khai báo một hàm trả về kiểu con trỏ int *Calcul(int a, int b); Sử dụng con trỏ hàm Con trỏ hàm được dùng khi cần gọi một hàm như là tham số của một hàm khác. Khi đó, một hàm được gọi phải có khuôn mẫu giống với con trỏ hàm đã được khai báo. Ví dụ, với khai báo : int (*Calcul)(int a, int b); thì có thể gọi các hàm có hai tham số kiểu int và trả về cũng kiểu int như sau: int add(int a, int b); int sub(int a, int b); nhưng không được gọi các hàm khác kiểu tham số hoặc kiểu trả về như sau: int add(float a, int b); int add(int a); char* sub(char* a, char* b): 12
15. Chương trình 2.3 #include #include // Hàm có sử dụng con trỏ hàm như tham số void Display(char[] str, int (*Xtype)(int c)){ int index = 0; while(str[index] != ‘\0’){ cout > input; char reply; cout > reply; if(reply == ‘l’) // Hiển thị theo dạng lowercase Display(str, tolower); else // Hiển thị theo dạng uppercase Display(str, toupper); return; } Chương trình 2.3 khai báo hàm Display() có sử dụng con trỏ hàm có khuôn mẫu int (*Xtype)(int c); Trong hàm main, con trỏ hàm này được gọi bởi hai thể hiện là các hàm tolower() và hàm toupper(). Hai hàm này được khai báo trong thư viện ctype.h với mẫu như sau: int tolower(int c); int toupper(int c); Hai khuôn mẫu này phù hợp với con trỏ hàm Xtype trong hàm Display() nên lời gọi hàm Display() trong hàm main là hợp lệ. 13
16. 1.4 CẤP PHÁT BỘ NHỚ ĐỘNG Xét hai trường hợp sau đây: Trường hợp 1, khai báo một con trỏ và gán giá trị cho nó: int *pa = 12; Trường hợp 2, khai báo con trỏ đến phần tử cuối cùng của mảng rồi tăng thêm một đơn vị cho nó: int A[5] = {5, 10, 15, 20, 25}; int *pa = &A[4]; pa++; Trong cả hai trường hợp, ta đều không biết thực sự con trỏ pa đang trỏ đến địa chỉ nào trong bộ nhớ: trường hợp 1 chỉ ra rằng con trỏ pa đang trỏ tới một địa chỉ không xác định, nhưng lại chứa giá trị là 12 do được gán vào. Trường hợp 2, con trỏ pa đã trỏ đến địa chỉ ngay sau địa chỉ phần tử cuối cùng của mảng A, đó cũng là một địa chỉ không xác định. Các địa chỉ không xác định này là các địa chỉ nằm ở vùng nhớ tự do còn thừa của bộ nhớ. Vùng nhớ này có thể bị chiếm dụng bởi bấtkìmột chương trình nào đang chạy. Do đó, rất có thể các chương trình khác sẽ chiếm mất các địa chỉ mà con trỏ pa đang trỏ tới. Khi đó, nếu các chương trình thay đổi giá trị của địa chỉ đó, giá trị pa cũng bị thay đổi theo mà ta không thể kiểm soát được. Để tránh các rủi ro có thể gặp phải, C++ yêu cầu phải cấp phát bộ nhớ ộm t cách tường minh cho con trỏ trước khi sử dụng chúng. 1.4.1 Cấp phát bộ nhớ động cho biến Cấp phát bộ nhớ động Thao tác cấp phát bộ nhớ cho con trỏ thực chất là gán cho con trỏ một địa chỉ xác định và đưa địa chỉ đó vào vùng đã bị chiếm dụng, các chương trình khác không thể sử dụng địa chỉ đó. Cú pháp cấp phát bộ nhớ cho con trỏ như sau: = new ; Ví dụ, khai báo: int *pa; pa = new int; sẽ cấp phát bộ nhớ hợp lệ cho con trỏ pa. Lưu ý: Ta có thể vừa cấp phát bộ nhớ, vừa khởi tạo giá trị cho con trỏ theo cú pháp sau: int *pa; pa = new int(12); sẽ cấp phát cho con trỏ pa một địa chỉ xác định, đồng thời gán giá trị của con trỏ 14
17. *pa = 12. Giải phóng ộb nhớ động Địa chỉ của con trỏ sau khi được cấp phát bởi thao tác new sẽ trở thành vùng nhớ đã bị chiếm dụng, các chương trình khác không thể sử dụng vùng nhớ đó ngay cả khi ta không dùng con trỏ nữa. Để tiết kiệm bộ nhớ, ta phải huỷ bỏ vùng nhớ của con trỏ ngay sau khi không dùng đến con trỏ nữa. Cú pháp huỷ bỏ vùng nhớ của con trỏ như sau: delete ; Ví dụ: int *pa= new int (12); delete(pa); Lưu ý: Một con trỏ, sau khi bị giải phóng địa chỉ, vẫn có thể được cấp phát một vùng nhớ mới hoặc trỏ đến một địa chỉ mới: int *pa = new int(12); // Khai báo con trỏ pa, cấp phát bộ nhớ // và gán giá trị ban đầu cho pa là 12. delete pa; // Giải phóng vùng nhớ vừa cấp cho pa. int A[5] = {5, 10, 15, 20, 25}; pa = A; // Cho pa trỏ đến địa chỉ của mảng A Nếu có nhiều con trỏ cùng trỏ vào một địa chỉ, thì chỉ cần giải phóng bộ nhớ của một con trỏ, tất cả các con trỏ còn lại cũng bị giải phóng bộ nhớ: int *pa = new int(12); // *pa = 12 int *pb = pa; // pb trỏ đến cùng địa chỉ pa. *pb += 5; // *pa = *pb = 17 delete pa; // Giải phóng cả pa lẫn pb Một con trỏ sau khi cấp phát bộ nhớ động bằng thao tác new, cần phải phóng bộ nhớ trước khi trỏ đếnộ m t địa chỉ mới hoặc cấp phát bộ nhớ mới: int*pa=newint(12); //pađượccấpbộnhớvà*pa=12 *pa = new int(15);// pa trỏ đến địa chỉ khác và *pa = 15. // địa chỉ cũ của pa vẫn bị coi là bận 1.4.2 Cấp phát bộ nhớ cho mảng động một chiều Cấp phát bộ nhớ cho mảng động một chiều Mảng một chiều được coi là tương ứng với một con trỏ cùng kiểu. Tuy nhiên, cú pháp cấp phát bộ nhớ cho mảng động một chiều là khác với cú pháp cấp phát bộ nhớ cho con trỏ thông thường: = new [ ]; 15
18. Trong đó: Tên con trỏ: tên do người dùng đặt, tuân thủ theo quy tắc đặt tên biến của C++. Kiểu con trỏ: Kiểu dữ liệu cơ bản của C++ hoặc là kiểu do người dùng tự định nghĩa Độ dài mảng: số lượng các phần tử cần cấp phát bộ nhớ của mảng. Ví dụ: int *A = new int[5]; sẽ khai báo một mảng A có 5 phần tử kiểu int được cấp phát bộ nhớ động. Lưu ý: Khi cấp phát bộ nhớ cho con trỏ có khởi tạo thông thường, ta dùng dấu “()”, khi cấp phát bộ nhớ cho mảng, ta dùng dấu “[]”. Hai lệnh cấp phát sau là hoàn toàn khác nhau: // Cấp phát bộ nhớ và khởi tạo cho một con trỏ int int *A = new int(5); // Cấp phát bộ nhớ cho ộm t mảng 5 phần tử kiểu int int *A = new int[5]; Giải phóng ộb nhớ của mảng động một chiều Để giải phóng vùng nhớ đã được cấp phát cho một mảng động, ta dùng cú pháp sau: delete [] ; Ví dụ: // Cấp phát bộ nhớ cho ộm t mảng có 5 phần tử kiểu int int *A = new int[5]; // Giải phóng vùng nhớ do mảng A đang chiếm giữ. delete [] A; Chương trình 2.4 void InitArray(int *A, int length){ A = new int[length]; for(int i=0; i<length; i++) A[i] = 0; Return } void DeleteArray(int *A){ delete [] A; return;} 16
19. 1.4.3 Cấp phát bộ nhớ cho mảng động nhiều chiều Cấp phát bộ nhớ cho mảng động nhiều chiều Một mảng hai chiều là ộm t con trỏ đến một con trỏ. Do vậy, ta phải cấp phát bộ nhớ theo từng chiều theo cú pháp cấp phát bộ nhớ cho mảng động một chiều. Ví dụ: int A; const int length = 10; A = new int*[length]; // Cấp phát bộ nhớ cho số dòng của ma trận A for(int i=0; i #include /* Khai báo nguyên mẫu hàm */ void InitArray(int A, int row, int colum); void AddArray(int A, int B, int row, int colum); void DisplayArray(int A, int row, int colum); void DeleteArray(int A, int row); 17
20. void InitArray(int A, int row, int colum){ A = new int*[row]; for(int i=0; i > A[i][j]; } return; } void AddArray(int A, int B, int row, int colum){ for(int i=0; i > row; cout > colum; /* Khởi tạo các ma trận */ cout << “Khoi tao mang A:” << endl; InitArray(A, row, colum); 18
21. cout << “Khoi tao mang B:” << endl; InitArray(B, row, colum); // Cộng hai ma trận AddArray(A, B, row, colum); // Hiển thị ma trận kết quả cout << “Tong hai mang A va mang B:” << endl; DisplayArray(A, row, colum); // Giải phóng bộ nhớ DeleteArray(A, row); DeleteArray(B, row); return; } TỔNG KẾT CHƯƠNG Nội dung chương 1 đã trình bày các vấn đề liên quan đến việc khai báo và sử dụng con trỏ và mảng trong ngôn ngữ C++: . Con trỏ là ộm t kiểu biến đặc biệt, nó trỏ đến địa chỉ củaộ m t biến khác. Có hai cách truy nhập đến con trỏ là truy nhập đến địa chỉ hoặc truy nhập đến giá trị của địa chỉ mà con trỏ trỏ đến. . Con trỏ có thể tham gia vào các phép toán như các biến thông thường bằng phép lấy giá trị. . Một con trỏ có sự tương ứng với một mảng một chiều có cùng kiểu. . Một ma trận hai chiều có thể thay thế bằng một mảng các con trỏ hoặc một con trỏ trỏ đến con trỏ. . Một con trỏ có thể trỏ đến một hàm, khi đó, nó được dùng để gọi một hàm như là một tham số cho hàm khác. . Một con trỏ cần phải trỏ vào một địa chỉ xác định hoặc phải được cấp phát bộ nhớ qua phép toán new và giải phóng bộ nhớ sau khi dùng bằng thao tác delete. 19
22. Bài tập chương 1 Câu hỏi về con trỏ 1. Toán tử gì được dùng để xác định địa chỉ của một biến? 2. Toán tử gì được dùng để xác định giá trị ở vị trí được trỏ bởi một con trỏ? địa chỉ của một biến? 3. Con trỏ là gì? 4. Truy cập gián tiếp là gì? 5. Mảng được lưu trữ trong bộ nhớ như thế nào? 6. Chỉ ra hai cách để nhận được địa chỉ phần tử đầu tiên của mảng data[]. 7. Nếu mảng được truyền đến một hàm, hai cách gì để nhận biết mảng kết thúc ở đâu? 8. Sáu toán tử gì có thể thực hiện với con trỏ? 9. Giả sử bạn có hai con trỏ. Nếu con trỏ đầu tiên trỏ đến phần tử thứ ba trong một mảng kiểu int, con trỏ thứ hai trỏ đến phần tử thứ tư. Việc trừ con trỏ thứ hai cho con trỏ đầu cho kết quả gì? 10. Giả sử cost là một tên biến. Làm thế nào để khai báo và khởi tạo một con trỏ có tên p_cost trỏ đến biến đó. Làm thế nào để gán giá trị 100 cho biến cost bằng cách dùng cả truy cập trực tiếp và gián tiếp. Làm thế nào để in giá trị của con trỏ p_cost và giá trị con trỏ p_cost trỏ đến. 11. Làm thế nào để gán địa chỉ của biến thực có tên là radius cho một viến con trỏ. 12. Hai cách để gán giá trị 100 cho phần tử thứ ba của mảng data[]. 13. Viết một hàm có tên là sumarrays() có đối số là hai mảng, tính tổng giá trị cả hai mảng và trả về tổng đó. Viết chương trình minh họa. 14. Viết lệnh khai báo biến con trỏ, khai báo và khởi gán con trỏ trỏ tới biến, khai báo và khởi gán con trỏ trỏ đến con trỏ. 15. Xét khai báo float x; float *px = &x; float ppx = &px; Để gán 100 cho biến x, ta có thể viết như sau hay không? *ppx = 100; 16. Viết một nguyên mẫu hàm với đối là một mảng con trỏ kiểu char và trả về void. 20
23. 17. Con trỏ trỏ đến hàm là gì? 18. Viết một khai báo con trỏ trỏ đến hàm trả về kiểu char và có đối là một mảng con trỏ kiểu char. 19. Khai báo sau có gì sai: char *ptr(char *x[]); 20. Giải thích các khai báo sau: a. int *var1; b. int var2; c. int var3; 21. Giải thích các khai báo sau: a. int a[3][12]; b. int (*b)[12]; c. int *c[12]; 22. Giải thích các khai báo sau: a. char *z[10]; b. char *y(int field); c. char (*x)(int field); 23. Viết một khai báo con trỏ trỏ đến hàm có đối kiểu nguyên và trả về biến kiểu float. 24 Viết một khai báo mảng con trỏ trỏ đến hàm có đối là chuỗi ký tự và trả về số nguyên. 25. Viết lệnh khai báo mảng 10 con trỏ kiểu char. 26. Có điểm gì sai trong đoạn mã sau: int x[3][12]; int *ptr[12]; ptr = x; 27. Hãy khai báo biến kí tự ch và con trỏ kiểu kí tự pc trỏ vào biến ch. Viết ra các cách gán giá trị ‘A’ cho biến ch. 28. Cho mảng nguyên cost. Viết ra các cách gán giá trị 100 cho phần tử thứ 3 của mảng. 29. Cho p, q là các con trỏ cùng trỏ đến kí tự c. Đặt *p = *q + 1. Có thể khẳng định: *q = *p - 1 ? 30. Cho p, q là các con trỏ trỏ đến biến nguyên x = 5. Đặt *p = *q + 1; Hỏi *q ? 31. Cho p, q, r, s là các con trỏ trỏ đến biến nguyên x = 10. Đặt *q = *p + 1; *r = *q + 1; *s = *r + 1. Hỏi giá trị của biến x ? 21
24. 32. Chọn câu đúng nhất trong các câu sau: A: Địa chỉ của một biến là số thứ tự của byte đầu tiên máy dành cho biến đó. B: Địa chỉ của một biến là một số nguyên. C: Số học địa chỉ là các phép toán làm việc trên các số nguyên biểu diễn địa chỉ của biến D: a và b đúng 33.Chọn câu sai trong các câu sau: A: Các con trỏ có thể phân biệt nhau bởi kiểu của biến mà nó trỏ đến. B: Hai con trỏ trỏ đến các kiểu khác nhau sẽ có kích thước khác nhau. C: Một con trỏ kiểu void có thể được gán bởi con trỏ có kiểu bất kỳ (cần ép kiểu). D: Hai con trỏ cùng trỏ đến kiểu cấu trúc có thể gán cho nhau. 34. Cho con trỏ p trỏ đến biến x kiểu float. Có thể khẳng định ? A: p là một biến và *p cũng là ộm t biến B: p là một biến và *p là một giá trị hằng C: Để sử dụng được p cần phải khai báo float *p; và gán *p = x; D: Cũng có thể khai báo void *p; và gán (float)p = &x; 35. Cho khai báo float x, y, z, *px, *py; và các lệnh px = &x; py = &y; Có thể khẳng định ? A: Nếu x = *px thì y = *py B: Nếu x = y + z thì *px = y + z C: Nếu *px = y + z thì *px = *py + z D: a, b, c đúng 36. Cho khai báo float x, y, z, *px, *py; và các lệnh px = &x; py = &y; Có thể khẳng định ? A: Nếu *px = x thì *py = y B: Nếu *px = *py - z thì *px = y - z C: Nếu *px = y - z thì x = y - z D: a, b, c đúng 37. Không dùng mảng, hãy nhập một dãy số nguyên và in ngược dãy ra màn hình. 38. Không dùng mảng, hãy nhập một dãy số nguyên và chỉ ra vị trí của số bé nhất, lớn nhất. 39. Không dùng mảng, hãy nhập một dãy số nguyên và in ra dãy đã được sắp xếp. 40. Không dùng mảng, hãy nhập một dãy kí tự. Thay mỗi kí tự ‘a’ trong dãy thành kí tự ‘b’ và in kết quả ra màn hình. 22
25. CHƯƠNG 2: CÁC DÒNG NHẬP XUẤT VÀ TỆP TIN Nhập/xuất với cin/cout Định dạng In ra máy in Làm việc với File Nhập/xuất nhị phân Trong C++ có sẵn một số lớp chuẩn chứa dữ liệu và các phương thức phục vụ cho các thao tác nhập/xuất dữ liệu của NSD, thường được gọi chung là stream (dòng). Trong số các lớp này, lớp có tên ios là lớp cơ sở, chứa các thuộc tính để định dạng việc nhập/xuất và kiểm tra lỗi. Mở rộng (kế thừa) lớp này có các lớp istream, ostream cung cấp thêm các toán tử nhập/xuất như >>, >, << và các hàm kể trên khi làm việc với các đối tượng này sẽ cho phép NSD nhập dữ liệu thông qua bàn phím hoặc xuất kết quả thông qua màn hình. 23
26. Để nhập/xuất thông qua các thiết bị khác (như máy in, file trên đĩa ), C++ cung cấp thêm các lớp ifstream, ofstream, fstream cho phép NSD khai báo các đối tượng mới gắn với thiết bị và từ đó nhập/xuất thông qua các thiết bị này. Trong chương này, chúng ta sẽ xét các đối tượng chuẩn cin, cout và một số toán tử, hàm nhập xuất đặc trưng của lớp iostream cũng như cách tạo và sử dụng các đối tượng thuộc các lớp ifstream, ofstream, fstream để làm việc với các thiết bị như máy in và file trên đĩa. 2.1. NHẬP/XUẤT VỚI CIN/COUT Như đã nhắc ở trên, cin là dòng dữ liệu nhập (đối tượng) thuộc lớp istream. Các thao tác trên đối tượng này gồm có các toán tử và hàm phục vụ nhập dữ liệu vào cho biến từ bàn phím. 2.1.1. Toán tử nhập >> Toán tử này cho phép nhập dữ liệu từ một dòng Input_stream nào đó vào cho một danh sách các biến. Cú pháp chung như sau: Input_stream >> biến1 >> biến2 >> trong đó Input_stream là đối tượng thuộc lớp istream. Trường hợp Input_stream là cin, câu lệnh nhập sẽ được viết: cin >> biến1 >> biến2 >> câu lệnh này cho phép nhập dữ liệu từ bàn phím cho các biến. Các biến này có thể thuộc các kiểu chuẩn như : kiểu nguyên, thực, ký tự, xâu kí tự. Chú ý 2 đặc điểm quan trọng của câu lệnh trên. Lệnh sẽ bỏ qua không gán các dấu trắng (dấu cách > a >> b >> c; cũng có thể được viết thành cin >> a; cin >> b; cin >> c; 24
27. và chỉ cần nhập dữ liệu vào từ bàn phím một lần chung cho cả 3 lệnh (mỗi dữ liệu nhập cho mỗi biến phải cách nhau ít nhất một dấu trắng) Ví dụ 1 : Nhập dữ liệu cho các biến int a; float b; char c; char *s; cin >> a >> b >> c >> s; giả sử NSD nhập vào dãy dữ liệu : 12 12E 12E > s; thì s sẽ được tự động gán giá trị "12E" mà không cần NSD nhập thêm dữ liệu vào cho cin. Qua ví dụ trên một lần nữa ta nhắc lại đặc điểm của toán tử nhập >> là các biến chỉ lấy dữ liệu vừa đủ cho kiểu của biến (ví dụ biến c chỉ lấy một kí tự 'A', b lấy giá trị 34.517) hoặc cho đến khi gặp dấu trắng đầu tiên (ví dụ a lấy giá trị 12, s lấy giá trị "BC" dù trong cin vẫn còn dữ liệu). Từ đó ta thấy toán tử >> là không phù hợp khi nhập dữ liệu cho các xâu kí tự có chứa dấu cách. C++ giải quyết trường hợp này bằng một số hàm (phương thức) nhập khác thay cho toán tử >>. 2.1.2. Các hàm nhập kí tự và xâu kí tự a. Nhập kí tự cin.get() : Hàm trả lại một kí tự (kể cả dấu cách, dấu ) Ví dụ: char ch; ch = cin.get(); nếu nhập AB, ch nhận giá trị 'A', trong cin còn B. nếu nhập A, ch nhận giá trị 'A', trong cin còn . nếu nhập , ch nhận giá trị '', trong cin rỗng. 25
28. cin.get(ch) : Hàm nhập kí tự cho ch và trả lại một tham chiếu tới cin. Do hàm trả lại tham chiếu tới cin nên có thể viết các phương thức nhập này liên tiếp trên một đối tượng cin. Ví dụ: char c, d; cin.get(c).get(d); nếu nhập AB thì c nhận giá trị 'A' và d nhận giá trị 'B'. Trong cin còn 'C'. b. Nhập xâu kí tự cin.get(s, n, fchar) : Hàm nhập cho s dãy kí tự từ cin. Dãy được tính từ kí tự đầu tiên trong cin cho đến khi đã đủ n – 1 kí tự hoặc gặp kí tự kết thúc fchar. Kí tự kết thúc này được ngầm định là dấu xuống dòng nếu bị bỏ qua trong danh sách đối. Tức có thể viết câu lệnh trên dưới dạng cin.get(s, n) khi đó xâu s sẽ nhận dãy kí tự nhập cho đến khi đủ n-1 kí tự hoặc đến khi NSD kết thúc nhập (bằng dấu ). Chú ý : Lệnh sẽ tự động gán dấu kết thúc xâu ('\0') vào cho xâu s sau khi nhập xong. Các lệnh có thể viết nối nhau, ví dụ: cin.get(s1, n1).get(s2,n2); Kí tự kết thúc fchar (hoặc ) vẫn nằm lại trong cin. Điều này có thể làm trôi các lệnh get() tiếp theo. Ví dụ: struct Sinhvien { char *ht; // họ tên char *qq; // quê quán }; void main() { int i; for (i=1; i<=3; i++) { cout << "Nhap ho ten sv thu " << i; cin.get(sv[i].ht, 25); cout << "Nhap que quan sv thu "<< i; cin.get(sv[i].qq, 30); } } 26
29. Trong đoạn lệnh trên sau khi nhập họ tên của sinh viên thứ 1, do kí tự  vẫn nằm trong bộ đệm nên khi nhập quê quán chương trình sẽ lấy kí tự  này gán cho qq, do đó quê quán của sinh viên sẽ là xâu rỗng. Để khắc phục tình trạng này chúng ta có thể sử dụng một trong các câu lệnh nhập kí tự để "nhấc" dấu enter còn "rơi vãi" ra khỏi bộ đệm. Có thể sử dụng các câu lệnh sau : cin.get(); // đọc một kí tự trong bộ đệm cin.ignore(n); //đọc n kí tự trong bộ đệm (với n=1) như vậy để đoạn chương trình trên hoạt động tốt ta có thể tổ chức lại như sau: void main() { int i; for (i=1; i > cũng giống các phương thức nhập kí tự và xâu kí tự ở chỗ cũng để lại kí tự enter trong cin. Do vậy, chúng ta nên sử dụng các phương thức cin.get(), cin.ignore(n) để loại bỏ kí tự enter trước khi thực hiện lệnh nhập kí tự và xâu kí tự khác. Tương tự dòng nhập cin, cout là dòng dữ liệu xuất thuộc lớp ostream. Điều này có nghĩa dữ liệu làm việc với các thao tác xuất (in) sẽ đưa kết quả ra cout mà đã được mặc định là màn hình. Do đó ta có thể sử dụng toán tử xuất << và các phương thức xuất trong các lớp ios (lớp cơ sở) và ostream. 27
30. 2.1.3. Toán tử xuất <>345 28
31. b. Chỉ định kí tự chèn vào khoảng trống trước giá trị cần in cout.fill(ch) ; Kí tự độn ngầm định là dấu cách, có nghĩa khi độ rộng của giá trị cần in bé hơn độ rộng chỉ định thì máy sẽ độn các dấu cách vào trước giá trị cần in cho đủ với độ rộng chỉ định. Có thể yêu cầu độn một kí tự ch bất kỳ thay cho dấu cách bằng phương thức trên. Ví dụ trong dãy lệnh trên, nếu ta thêm dòng lệnh cout.fill('*') trước khi in b chẳng hạn thì kết quả in ra sẽ là: 12 345. Phương thức này có tác dụng với mọi câu lệnh in sau nó cho đến khi gặp một chỉ định mới. c. Chỉ định độ chính xác (số số lẻ thập phân) cần in cout.precision(n) ; Phương thức này yêu cầu các số thực in ra sau đó sẽ có n chữ số lẻ. Các số thực trước khi in ra sẽ được làm tròn đến chữ số lẻ thứ n. Chỉ định này có tác dụng cho đến khi gặp một chỉ định mới. Ví dụ: int a = 12.3; b = 345.678; // độ rộng thực của a là 4, của b là 7 cout <>345.68 2.2.2. Các cờ định dạng Một số các qui định về định dạng thường được gắn liền với các "cờ". Thông thường nếu định dạng này được sử dụng trong suốt quá trình chạy chương trình hoặc trong một khoảng thời gian dài trước khi gỡ bỏ thì ta "bật" các cờ tương ứng với nó. Các cờ được bật sẽ có tác dụng cho đến khi cờ với định dạng khác được bật. Các cờ được cho trong file tiêu đề iostream.h. Để bật/tắt các cờ ta sử dụng các phương thức sau: cout.setf(danh sách cờ); // Bật các cờ trong danh sách cout.unsetf(danh sách cờ); // Tắt các cờ trong danh sách Các cờ trong danh sách được viết cách nhau bởi phép toán hợp bit (|). Ví dụ lệnh cout.setf(ios::left | ios::scientific) sẽ bật các cờ ios::left và ios::scientific. Phương thức cout.unsetf(ios::right | ios::fixed) sẽ tắt các cờ ios::right | ios::fixed. Dưới đây là danh sách các cờ cho trong iostream.h. 29
32. d. Nhóm căn lề ios::left : nếu bật thì giá trị in nằm bên trái vùng in ra (kí tự độn nằm sau). ios::right : giá trị in nằm bên phái vùng in ra (kí tự độn nằm trước), đây là trường hợp ngầm định nếu ta không sử dụng cờ cụ thể. ios::internal : giống cờ ios::right tuy nhiên dấu của giá trị in ra sẽ được in đầu tiên, sau đó mới đến kí tự độn và giá trị số. Ví dụ: int a = 12.3; b = 345.678; // độ rộng thực của a là 4, của b là 8 cout << a; // chiếm 4 cột màn hình cout.width(10); // đặt độ rộng giá trị in tiếp theo là 10 cout.fill('*') ; // dấu * làm kí tự độn cout.precision(2); // đặt độ chính xác đến 2 số lẻ cout.setf(ios::left) ; // bật cờ ios::left cout << b; // kết qủa: 12.3 345.68 cout.setf(ios::right) ; // bật cờ ios::right cout << b; // kết qủa: 12.3 345.68 cout.setf(ios::internal) ; // bật cờ ios::internal cout << b; // kết qủa: 12.3 345.68 e. Nhóm định dạng số nguyên ios::dec : in số nguyên dưới dạng thập phân (ngầm định) ios::oct : in số nguyên dưới dạng cơ số 8 ios::hex : in số nguyên dưới dạng cơ số 16 f. Nhóm định dạng số thực ios::fixed : in số thực dạng dấu phảy tĩnh (ngầm định) ios::scientific : in số thực dạng dấu phảy động ios::showpoint : in đủ n chữ số lẻ của phần thập phân, nếu tắt (ngầm định) thì không in các số 0 cuối của phần thập phân. Ví dụ: giả sử độ chính xác được đặt với 3 số lẻ (bởi câu lệnh cout.precision(3)) nếu fixed bật + showpoint bật : 123.2500 được in thành 123.250 123.2599 được in thành 123.260 30
33. 123.2 được in thành 123.200 nếu fixed bật + showpoint tắt : 123.2500 được in thành 123.25 123.2599 được in thành 123.26 123.2 được in thành 123.2 nếu scientific bật + showpoint bật : 12.3 được in thành 1.230e+01 2.32599 được in thành 2.326e+00 324 được in thành 3.240e+02 nếu scientific bật + showpoint tắt : 12.3 được in thành 1.23e+01 2.32599 được in thành 2.326e+00 324 được in thành 3.24e+02 g. Nhóm định dạng hiển thị ios::showpos : nếu tắt (ngầm định) thì không in dấu cộng (+) trướcsố dương. Nếu bật trước mỗi số dương sẽ in thêm dấu cộng. ios::showbase : nếu bật sẽ in số 0 trước các số nguyên hệ 8 và in 0x trước số hệ 16. Nếu tắt (ngầm định) sẽ không in 0 và 0x. ios::uppercase : nếu bật thì các kí tự biểu diễn số trong hệ 16 (A F) sẽ viết hoa, nếu tắt (ngầm định) sẽ viết thường. 2.2.3. Các bộ và hàm định dạng iostream.h cũng cung cấp một số bộ và hàm định dạng cho phép sử dụng tiện lợi hơn so với các cờ và các phương thức vì nó có thể được viết liên tiếp trên dòng lệnh xuất. h. Các bộ định dạng dec // tương tự ios::dec oct // tương tự ios::dec hex // tương tự ios::hex endl // xuất kí tự xuống dòng ('\n') flush // đẩy toàn bộ dữ liệu ra dòng xuất Ví dụ : cout.setf(ios::showbase) ; // cho phép in các kí tự biểu thị cơ 31
34. số cout.setf(ios::uppercase) ; // dưới dạng chữ viết hoa int a = 171; int b = 32 ; cout ) setw(n) // tương tự cout.width(n) setprecision(n) // tương tự cout.precision(n) setfill(c) // tương tự cout.fill(c) setiosflags(l) // tương tự cout.setf(l) resetiosflags(l) // tương tự cout.unsetf(l) 2.3. IN RA MÁY IN Như trong phần đầu chương đã trình bày, để làm việc với các thiết bị khác với màn hình và đĩa chúng ta cần tạo ra các đối tượng (thuộc các lớp ifstream, ofstream và fstream) tức các dòng tin bằng các hàm tạo của lớp và gắn chúng với thiết bị bằng câu lệnh: ofstream Tên_dòng(thiết bị) ; Ví dụ để tạo một đối tượng mang tên Mayin và gắn với máy in, chúng ta dùng lệnh: ofstream Mayin(4) ; trong đó 4 là số hiệu của máy in. Khi đó mọi câu lệnh dùng toán tử xuất << và cho ra Mayin sẽ đưa dữ liệu cần in vào một bộ đệm mặc định trong bộ nhớ. Nếu bộ đệm đầy, một số thông tin đưa vào trước sẽ tự động chuyển ra máy in. Để chủ động đưa tất cả dữ liệu còn lại trong bộ đệm ra máy in chúng ta cần sử dụng bộ định dạng flush (Mayin << flush << ) hoặc phương thức flush (Mayin.flush(); ). Ví dụ: Sau khi đã khai báo một đối tượng mang tên Mayin bằng câu lệnh như trên Để in chu vi và diện tísch hình chữ nhật có cạnh cd và cr ta có thể viết: Mayin << "Diện tích HCN = " << cd * cr << endl; Mayin << "Chu vi HCN = " << 2*(cd + cr) << endl; Mayin.flush(); hoặc : Mayin << "Diện tích HCN = " << cd * cr << endl; Mayin << "Chu vi HCN = " << 2*(cd + cr) << endl << flush; 32
35. khi chương trình kết thúc mọi dữ liệu còn lại trong các đối tượng sẽ được tự động chuyển ra thiết bị gắn với nó. Ví dụ máy in sẽ in tất cả mọi dữ liệu còn sót lại trong Mayin khi chương trình kết thúc. 2.4. LÀM VIỆC VỚI FILE Làm việc với một file trên đĩa cũng được quan niệm như làm việc với các thiết bị khác của máy tính (ví dụ như làm việc với máy in với đối tượng Mayin trong phần trên hoặc làm việc với màn hình với đối tượng chuẩn cout). Các đối tượng này được khai báo thuộc lớp ifstream hay ofstream tùy thuộc ta muốn sử dụng file để đọc hay ghi. Như vậy, để sử dụng một file dữ liệu đầu tiên chúng ta cần tạo đối tượng và gắn cho file này. Để tạo đối tượng có thể sử dụng các hàm tạo có sẵn trong hai lớp ifstream và ofstream. Đối tượng sẽ được gắn với tên file cụ thể trên đĩa ngay trong quá trình tạo đối tượng (tạo đối tượng với tham số là tên file) hoặc cũng có thể được gắn với tên file sau này bằng câu lệnh mở file. Sau khi đã gắn một đối tượng với file trên đĩa, có thể sử dụng đối tượng như đối với Mayin hoặc cin, cout. Điều này có nghĩa trong các câu lệnh in ra màn hình chỉ cần thay từ khóa cout bởi tên đối tượng mọi dữ liệu cần in trong câu lệnh sẽ được ghi lên file mà đối tượng đại diện. Cũng tương tự nếu thay cin bởi tên đối tượng, dữ liệu sẽ được đọc vào từ file thay cho từ bàn phím. Để tạo đối tượng dùng cho việc ghi ta khai báo chúng với lớp ofstream còn để dùng cho việc đọc ta khai báo chúng với lớp ifstream. 2.4.1. Tạo đối tượng gắn với file Mỗi lớp ifstream và ofstream cung cấp 4 phương thức để tạo file. Ở đây chúng tôi chỉ trình bày 2 cách (2 phương thức) hay dùng. + Cách 1: đối_tượng; đối_tượng.open(tên_file, chế_độ); Lớp là một trong hai lớp ifstream và ofstream. Đối tượng là tên do NSD tự đặt. Chế độ là cách thức làm việc với file (xem dưới). Cách này cho phép tạo trước một đối tượng chưa gắn với file cụ thể nào. Sau đó dùng tiếp phương thức open để đồng thời mở file và gắn với đối tượng vừa tạo. Ví dụ: ifstream f; // tạo đối tượng có tên f để đọc hoặc ofstream f; // tạo đối tượng có tên f để ghi f.open("Baitap"); // mở file Baitap và gắn với f + Cách 2: đối_tượng(tên_file, chế_độ) 33
36. Cách này cho phép đồng thời mở file cụ thể và gắn file với tên đối tượng trong câu lệnh. Ví dụ: ifstream f("Baitap"); // mở file Baitap gắn với đối tượng f để ofstream f("Baitap); // đọc hoặc ghi. Sau khi mở file và gắn với đối tượng f, mọi thao tác trên f cũng chính là làm việc với file Baitap. Trong các câu lệnh trên có các chế độ để qui định cách thức làm việc của file. Các chế độ này gồm có: ios::binary : quan niệm file theo kiểu nhị phân. Ngầm định là kiểu văn bản. ios::in : file để đọc (ngầm định với đối tượng trong ifstream). ios::out : file để ghi (ngầm định với đối tượng trong ofstream), nếu file đã có trên đĩa thì nội dung của nó sẽ bị ghi đè (bị xóa). ios::app : bổ sung vào cuối file ios::trunc : xóa nội dung file đã có ios::ate : chuyển con trỏ đến cuối file ios::nocreate : không làm gì nếu file chưa có ios::replace : không làm gì nếu file đã có có thể chỉ định cùng lúc nhiều chế độ bằng cách ghi chúng liên tiếp nhau với toán tử hợp bit |. Ví dụ để mở file bài tập như một file nhị phân và ghi tiếp theo vào cuối file ta dùng câu lệnh: ofstream f("Baitap", ios::binary | ios::app); 2.4.2 Đóng file và giải phóng đối tượng Để đóng file được đại diện bởi f, sử dụng phương thức close như sau: đối_tượng.close(); Sau khi đóng file (và giải phóng mối liên kết giữa đối tượng và file) có thể dùng đối tượng để gắn và làm việc với file khác bằng phương thức open như trên. Ví dụ 2 : Đọc một dãy số từ bàn phím và ghi lên file. File được xem như file văn bản (ngầm định), các số được ghi cách nhau 1 dấu cách. #include #include #include 34
37. void main() { ofstream f; // khai báo (tạo) đối tượng f int x; f.open("DAYSO"); // mở file DAYSO và gắn với f for (int i = 1; i > x; f #include #include #include #include #include #include struct Sv { char *hoten; int tuoi; double diem; }; class Sinhvien { int sosv ; Sv *sv; public: Sinhvien() { sosv = 0; sv = NULL; } 35
38. void nhap(); void sapxep(); void ghifile(char *fname); }; void Sinhvien::nhap() { cout > sosv; int n = sosv; sv = new Sinhvien[n+1]; // Bỏ phần tử thứ 0 for (int i = 1; i > sv[i].tuoi; cout > sv[i].diem; } } void Sinhvien::ghi(char fname) { ofstream f(fname) ; f > sosv; for (int i=1; i<=sosv; i++) { 36
39. f.getline(sv[i].hoten, 25); f >> sv[i].tuoi >> sv[i].diem; } f.close(); } void Sinhvien::sapxep() { int n = sosv; for (int i = 1; i sv[j].tuoi) { Sinhvien t = sv[i]; sv[i] = sv[j]; sv[j] = t; } } void main() { clrscr(); Sinhvien x ; x.nhap(); x.ghi("DSSV1"); x.doc("DSSV1"); x.sapxep(); x.ghi("DSSV2"); cout << "Đã xong"; getch(); } 2.4.3. Kiểm tra sự tồn tại của file, kiểm tra hết file Việc mở một file chưa có để đọc sẽ gây nên lỗi và làm dừng chương trình. Khi xảy ra lỗi mở file, giá trị trả lại của phương thức bad là một số khác 0. Do vậy có thể sử dụng phương thức này để kiểm tra một file đã có trên đĩa hay chưa. Ví dụ: ifstream f("Bai tap"); if (f.bad()) { cout << "file Baitap chưa có"; exit(1); } 37
40. Khi đọc hoặc ghi, con trỏ file sẽ chuyển dần về cuối file. Khi con trỏ ở cuối file, phương thức eof() sẽ trả lại giá trị khác không. Do đó có thể sử dụng phương thức này để kiểm tra đã hết file hay chưa. Chương trình sau cho phép tính độ dài của file Baitap. File cần được mở theo kiểu nhị phân. #include #include #include #include void main() { clrscr(); long dodai = 0; char ch; ifstream f("Baitap", ios::in | ios::binary) ; if (f.bad()) { cout << "File Baitap không có"; exit(1); } while (!f.eof()) { f.get(ch)); dodai++; } cout << "Độ dài của file = " << dodai; getch(); } 2.4.4. Đọc ghi đồng thời trên file Để đọc ghi đồng thời, file phải được gắn với đối tượng của lớp fstream là lớp thừa kế của 2 lớp ifstream và ofstream. Khi đó chế độ phải được bao gồm chỉ định ios::in | ios::out. Ví dụ: fstream f("Data", ios::in | ios::out) ; hoặc fstream f ; f.open("Data", ios::in | ios::out) ; 38
41. 2.4.5. Di chuyển con trỏ file Các phương thức sau cho phép làm việc trên đối tượng của dòng xuất (ofstream). đối_tượng.seekp(n) ; Di chuyển con trỏ đến byte thứ n (các byte được tính từ 0) đối_tượng.seekp(n, vị trí xuất phát) ; Di chuyển đi n byte (có thể âm hoặc dương) từ vị trí xuất phát. Vị trí xuất phát gồm: ios::beg : từ đầu file ios::end : từ cuối file ios::cur : từ vị trí hiện tại của con trỏ. đối_tượng.tellp(n) ; Cho biết vị trí hiện tại của con trỏ. Để làm việc với dòng nhập tên các phương thức trên được thay tương ứng bởi các tên : seekg và tellg. Đối với các dòng nhập lẫn xuất có thể sử dụng được cả 6 phương thức trên. Ví dụ sau tính độ dài tệp đơn giản hơn ví dụ ở trên. fstream f("Baitap"); f.seekg(0, ios::end); cout #include #include #include #include #include #include void main() { int stt ; char *hoten, *fname, traloi; int tuoi; float diem; fstream f; cout > fname; f.open(fname, ios::in | ios::out | ios::noreplace) ; if (f.bad()) { 39
42. cout > tuoi; cout > diem; f > tuoi >> diem; f.ignore(); cout << "\nSinh viên thứ " << stt ; cout << "\nHọ tên: " << hoten; cout << "\nTuổi: " << setw(4) << tuoi; cout << "\nĐiểm: " << setw(8) << diem; 40
43. } f.close(); getch(); } 2.5. NHẬP/XUẤT NHỊ PHÂN 2.5.1. Khái niệm về 2 loại file: văn bản và nhị phân j. File văn bản Trong file văn bản mỗi byte được xem là một kí tự. Tuy nhiên nếu 2 byte 10 (LF), 13 (CR) đi liền nhau thì được xem là một kí tự và nó là kí tự xuống dòng. Như vậy file văn bản là một tập hợp các dòng kí tự với kí tự xuống dòng có mã là 10. Kí tự có mã 26 được xem là kí tự kết thúc file. k. File nhị phân Thông tin lưu trong file được xem như dãy byte bình thường. Mã kết thúc file được chọn là -1, được định nghĩa là EOF trong stdio.h. Các thao tác trên file nhị phân thường đọc ghi từng byte một, không quan tâm ý nghĩa của byte. Một số các thao tác nhập/xuất sẽ có hiệu quả khác nhau khi mở file dưới các dạng khác nhau. Ví dụ 1 : giả sử ch = 10, khi đó f #include #include #include void main() 41
44. { clrscr(); fstream fnguon("DATA1", ios::in | ios::binary); fstream fdich("DATA2", ios::out | ios::binary); char ch; while (!fnguon.eof()) { fnguon.get(ch); fdich.put(ch); } fnguon.close(); fdich.close(); } 2.5.3. Đọc, ghi dãy kí tự write(char *buf, int n); // ghi n kí tự trong buf ra dòng xuất read(char *buf, int n); // nhập n kí tự từ buf vào dòng nhập gcount(); // cho biết số kí tự read đọc được Ví dụ 3 : Chương trình sao chép file ở trên có thể sử dụng các phương thức mới này như sau: #include #include #include #include void main() { clrscr(); fstream fnguon("DATA1", ios::in | ios::binary); fstream fdich("DATA2", ios::out | ios::binary); char buf[2000] ; int n = 2000; while (n) { fnguon.read(buf, 2000); n = fnguon.gcount(); fdich.write(buf, n); } fnguon.close(); 42
45. fdich.close(); } 2.5.4. Đọc ghi đồng thời #include #include #include #include #include #include #include #include struct Sv { char *hoten; int tuoi; double diem; }; class Sinhvien { int sosv; Sv x; char fname[30]; static int size; public: Sinhvien(char *fn); void tao(); void bosung(); void xemsua(); }; int Sinhvien::size = sizeof(Sv); Sinhvien::Sinhvien(char *fn) { strcpy(fname, fn) ; fstream f; f.open(fname, ios::in | ios::ate | ios::binary); 43
46. if (!f.good) sosv = 0; else { sosv = f.tellg() / size; } } void Sinhvien::tao() { fstream f; f.open(fname, ios::out | ios::noreplace | ios::binary); if (!f.good()) { cout > x.tuoi; cout > x.diem; f.write((char*)(&x), size); sosv++; } f.close(); } void Sinhvien::bosung() { fstream f; f.open(fname, ios::out | ios::app | ios::binary); if (!f.good()) { 44
47. cout > x.tuoi; cout > x.diem; f.write((char*)(&x), size); stt++; } sosv += stt; f.close(); } void Sinhvien::xemsua() { fstream f; int ch; f.open(fname, ios::out | ios::app | ios::binary); if (!f.good()) { cout > stt; 45
48. if (stt sosv) break; f.seekg((stt-1) * size, ios::beg); f.read((char*)(&x), size); cout > traloi; if (toupper(traloi) == 'C') { f.seekg(-size, ios::cur); cout > x.tuoi; cout > x.diem; f.write((char*)(&x), size); } } f.close(); } void main() { int chon; Sinhvien SV("DSSV") ; while (1) { clrscr(); cout << "\n1: Tạo danh sách sinh viên"; cout << "\n2: Bổ sung danh sách"; cout << "\n3: Xem – sửa danh sách"; cout << "\n0: Kết thúc"; chon = getch(); chon = chon – 48; clrscr(); if (chon == 1) SV.tao(); else if (chon == 2) SV.bosung(); else if (chon == 3) SV.xemsua(); else break; } } 46
49. BÀI TẬP 1. Viết chương trình đếm số dòng của một file văn bản. 2. Viết chương trình đọc in từng kí tự của file văn bản ra màn hình, mỗi màn hình 20 dòng. 3. Viết chương trình tìm xâu dài nhất trong một file văn bản. 4. Viết chương trình ghép một file văn bản thứ hai vào file văn bản thứnhất, trong đó tất cả chữ cái của file văn bản thứ nhất phải đổi thành chữ in hoa. 5. Viết chương trình in nội dung file ra màn hình và cho biết tổng số chữ cái, tổng số chữ số đã xuất hiện trong file. 6. Cho 2 file số thực (đã được sắp tăng dần). In ra màn hình dãy số xếp tăng dần của cả 2 file. (Cần tạo cả 2 file dữ liệu này bằng Editor của C++). 7. Viết hàm nhập 10 số thực từ bàn phím vào file INPUT.DAT. Viết hàm đọc các số thực từ file trên và in tổng bình phương của chúng ra màn hình. 8. Viết hàm nhập 10 số nguyên từ bàn phím vào file văn bản tên INPUT.DAT. Viết hàm đọc các số nguyên từ file trên và ghi những số chẵn vàofile EVEN.DAT còn các số lẻ vào file ODD.DAT. 9. Nhập bằng chương trình 2 ma trận số nguyên vào 2 file văn bản. Hãy tạo file văn bản thứ 3 chứa nội dung của ma trận tích của 2 ma trận trên. 10. Tổ chức quản lý file sinh viên (Họ tên, ngày sinh, giới tính, điểm) với các chức năng : Nhập, xem, xóa, sửa, tính điểm trung chung. 11. Thông tin về một nhân viên trong cơ quan bao gồm : họ và tên, nghề nghiệp, số điện thoại, địa chỉ nhà riêng. Viết hàm nhập từ bàn phím thông tin của 7 nhân viên và ghi vào file INPUT.DAT. Viết hàm tìm trong file INPUT.DAT và in ra thông tin của 1 nhân viên theo số điện thoại được nhập từ bàn phím. 47
50. CHƯƠNG 3 DỮ LIỆU KIỂU CẤU TRÚC VÀ HỢP Nội dung chính của chương này nhằm làm rõ các phương pháp, kỹ thuật biểu diễn, phép toán và ứng dụng của các cấu trúc dữ liệu trừu tượng. Cần đặc biệt lưu ý, ứng dụng các cấu trúc dữ liệu này không chỉ riêng cho lập trình ứng dụng mà còn ứng dụng trong biểu diễn bộ nhớ để giải quyết những vấn đề bên trong của các hệ điều hành. Các kỹ thuật lập trình trên cấu trúc dữ liệu trừu tượng được đề cập ở đây bao gồm: Kiểu cấu trúc Cấu trúc tự trỏ và danh sách liên kết Kiểu hợp Kiểu liệt kê Để lưu trữ các giá trị gồm nhiều thành phần dữ liệu giống nhau ta có kiểu biến mảng. Thực tế rất nhiều dữ liệu là tập các kiểu dữ liệu khác nhau tập hợp lại, để quản lý dữ liệu kiểu này C++ đưa ra kiểu dữ liệu cấu trúc. Một ví dụ của dữ liệu kiểu cấu trúc là một bảng lý lịch trong đó mỗi nhân sự được lưu trong một bảng gồm nhiều kiểu dữ liệu khác nhau như họ tên, tuổi, giới tính, mức lương 3.1. KIỂU CẤU TRÚC 3.1.1. Khai báo, khởi tạo Để tạo ra một kiểu cấu trúc NSD cần phải khai báo tên của kiểu (là một tên gọi do NSD tự đặt), tên cùng với các thành phần dữ liệu có trong kiểu cấu trúc này. Một kiểu cấu trúc được khai báo theo mẫu sau: struct { các thành phần ; } ; Mỗi thành phần giống như một biến riêng của kiểu, nó gồm kiểu và tên thành phần. Một thành phần cũng còn được gọi là trường. Phần tên của kiểu cấu trúc và phần danh sách biến có thể có hoặc không. Tuy nhiên trong khai báo kí tự kết thúc cuối cùng phải là dấu chấm phẩy 48
51. (;). Các kiểu cấu trúc được phép khai báo lồng nhau, nghĩa là một thành phần của kiểu cấu trúc có thể lại là một trường có kiểu cấu trúc. Một biến có kiểu cấu trúc sẽ được phân bố bộ nhớ sao cho các thực hiện của nó được sắp liên tục theo thứ tự xuất hiện trong khai báo. Khai báo biến kiểu cấu trúc cũng giống như khai báo các biến kiểu cơ sở dưới dạng: struct ; // kiểu cũ trong C hoặc ; // trong C++ Các biến được khai báo cũng có thể đi kèm khởi tạo: biến = { giá trị khởi tạo } ; Ví dụ: Khai báo kiểu cấu trúc chứa phân số gồm 2 thành phần nguyên chứa tử số và mẫu số. struct Phanso { int tu ; int mau ; } ; hoặc: struct Phanso { int tu, mau ; } Kiểu ngày tháng gồm 3 thành phần nguyên chứa ngày, tháng, năm. struct Ngaythang { int ng ; int th ; int nam ; } holiday = { 1,5,2000 } ; một biến holiday cũng được khai báo kèm cùng kiểu này và được khởi tạo bởi bộ số 1. 5. 2000. Các giá trị khởi tạo này lần lượt gán cho các thành phần theo đúng thứ tự trong khai báo, tức ng = 1, th = 5 và nam = 2000. Kiểu Lop dùng chứa thông tin về một lớp học gồm tên lớp và sĩ số sinh viên. Các biến kiểu Lop được khai báo là daihoc và caodang, trong đó daihoc được khởi tạo bởi bộ giá trị {"K41T", 60} với ý nghĩa tên lớp đại 49
52. học là K41T và sĩ số là 60 sinh viên. struct Lop { char tenlop[10], int soluong; } ; struct Lop daihoc = {"K41T", 60}, caodang ; hoặc: Lop daihoc = {"K41T", 60}, caodang ; Kiểu Sinhvien gồm có các trường hoten để lưu trữ họ và tên sinh viên, ns lưu trữ ngày sinh, gt lưu trữ giới tính dưới dạng số (qui ước 1: nam, 2: nữ) và cuối cùng trường diem lưu trữ điểm thi của sinh viên. Các trường trên đều có kiểu khác nhau. struct Sinhvien { char hoten[25] ; Ngaythang ns; int gt; float diem ; } x, *p, K41T[60]; Sinhvien y = {"NVA", {1,1,1980}, 1} ; Khai báo cùng với cấu trúc Sinhvien có các biến x, con trỏ p và mảng K41T với 60 phần tử kiểu Sinhvien. Một biến y được khai báo thêm và kèm theo khởi tạo giá trị {"NVA", {1,1,1980}, 1}, tức họ tên của sinh viên y là "NVA", ngày sinh là 1/1/1980, giới tính nam và điểm thi để trống. Đây là kiểu khởi tạo thiếu giá trị, giống như khởi tạo mảng, các giá trị để trống phải nằm ở cuối bộ giá trị khởi tạo (tức các thành phần bỏ khởi tạo không được nằm xen kẽ giữa những thành phần được khởi tạo).Ví dụ này còn minh hoạ cho các cấu trúc lồng nhau, cụ thể trong kiểu cấu trúc Sinhvien có một thành phần cũng kiểu cấu trúc là thành phần ns. 3.1.2.Truy nhập các thành phần kiểu cấu trúc Để truy nhập vào các thành phần kiểu cấu trúc ta sử dụng cú pháp: tên biến.tên thành phần hoặc tên biến tên thành phần đối với biến con trỏ cấu trúc. Cụ thể: Đối với biến thường: tên biến.tên thành phần Ví dụ: 50
53. struct Lop { char tenlop[10]; int siso; } ; Lop daihoc = "K41T", caodang ; caodang.tenlop = daihoc.tenlop ; // gán tên lớp cđẳng bởi tên lớp đhọc caodang.siso++; // tăng sĩ số lớp caodang lên 1 Đối với biến con trỏ: tên biến tên thành phần Ví dụ: struct Sinhvien { char hoten[25] ; Ngaythang ns; int gt; float diem ; } x, *p, K41T[60]; Sinhvien y = {"NVA", {1,1,1980}, 1} ; y.diem = 5.5 ; // gán điểm thi cho sinh viên y p = new Sinhvien ; // cấp bộ nhớ chứa 1 sinh viên strcpy(p hoten, y.hoten) ; // gán họ tên của y cho sv trỏ bởi p cout << p hoten << y.hoten; // in hoten của y và con trỏ p Đối với biến mảng: truy nhập thành phần mảng rồi đến thành phầncấu trúc. Ví dụ: strcpy(K41T[1].hoten, p hoten) ; // gán họ tên cho sv đầu tiên của lớp K41T[1].diem = 7.0 ; // gán điểm cho sv đầu tiên Đối với cấu trúc lồng nhau. Truy nhập thành phần ngoài rồi đến thành phần của cấu trúc bên trong, sử dụng các phép toán . hoặc (các phép toán lấy thành phần) một cách thích hợp. x.ngaysinh.ng = y.ngaysinh.ng ; // gán ngày, 51
54. x.ngaysinh.th = y.ngaysinh.th ; // tháng, x.ngaysinh.nam = y.ngaysinh.nam ; // năm sinh của y cho x. 3.1.3. Phép toán gán cấu trúc Cũng giống các biến mảng, để làm việc với một biến cấu trúc chúng ta phải thực hiện thao tác trên từng thành phần của chúng. Ví dụ vào/ra một biến cấu trúc phải viết câu lệnh vào/ra từng cho từng thành phần. Nhận xét này được minh họa trong ví dụ sau: struct Sinhvien { char hoten[25] ; Ngaythang ns; int gt; float diem ; } x, y; cout > x.ns.ng >> x.ns.th >> x.ns.nam; cin >> x.gt; cin >> x.diem cout << "Thông tin về sinh viên x là:" << endl ; cout << "Họ và tên: " << x.hoten << endl; cout << "Sinh ngày: " << x.ns.ng << "/" << x.ns.th << "/" << x.ns.nam ; cout << "Giới tính: " << (x.gt == 1) ? "Nam": "Nữ ; cout << x.diem Tuy nhiên, khác với biến mảng, đối với cấu trúc chúng ta có thể gán giá trị của 2 biến cho nhau. Phép gán này cũng tương đương với việc gán từng thành phần của cấu trúc. Ví dụ: struct Sinhvien { char hoten[25] ; Ngaythang ns; int gt; float diem ; } x, y, *p ; cout << " Nhập dữ liệu cho sinh viên x:" << endl ; cin.getline(x.hoten, 25); 52
55. cin >> x.ns.ng >> x.ns.th >> x.ns.nam; cin >> x.gt; cin >> x.diem y = x ; // Đối với biến mảng, phép gán này là không thực hiện được p = new Sinhvien[1] ; *p = x ; cout #include struct Phanso { int tu ; int mau ; } a, b, c ; void main() { clrscr(); cout << "Nhập phân số a:" << endl ; // nhập a 53
56. cout > a.tu; cout > a.mau; cout > b.tu; cout > b.mau; c.tu = a.tu*b.mau + a.mau*b.tu; // tính và in a+b c.mau = a.mau*b.mau; cout #include void main() { struct Sinhvien { char hoten[25] ; Ngaythang ns; int gt; float diem ; } x, K41T[60]; int i, n; 54
57. // nhập dữ liệu cout > n; for (i=1, i > x.ns.ng >> x.ns.th >>x.ns.nam ; cout > x.gt ; cout > x.diem ; cin.ignore(); K41T[i] = x ; } } // Tính điểm trung bình float tbnam = 0, tbnu = 0; int sonam = 0, sonu = 0 ; for (i=1; i<=n; i++) if (K41T[i].gt == 1) { sonam++ ; tbnam += K41T[1].diem ; } else { sonu++ ; tbnu += K41T[1].diem ; } cout << "Điểm trung bình của sinh viên nam là " << tbnam/sonam ; cout << "Điểm trung bình của sinh viên nữ là " << tbnu/sonu ; // In danh sách sinh viên có điểm cao nhất float diemmax = 0; for (i=1; i<=n; i++) // Tìm điểm cao nhất if (diemmax < K41T[i].diem) diemmax = K41T[i].diem ; for (i=1; i<=n; i++) // In danh sách { if (K41T[i].diem < diemmax) continue ; x = K41T[1] ; cout << x.hoten << '\t' ; cout << x.ns.ng << "/" << x.ns.th << "/" << x.ns.nam << '\t' ; 55
58. cout << (x.gt == 1) ? "Nam": "Nữ" << '\t' ; cout << x.diem << endl; } } 3.1.5.Hàm với cấu trúc l. Con trỏ và địa chỉ cấu trúc Một con trỏ cấu trúc cũng giống như con trỏ trỏ đến các kiểu dữ liệu khác, có nghĩa nó chứa địa chỉ của một biến cấu trúc hoặc một vùng nhớ có kiểu cấu trúc nào đó. Một con trỏ cấu trúc được khởi tạo bởi: Gán địa chỉ của một biến cấu trúc, một thành phần của mảng, tương tự nếu địa chỉ của mảng (cũng là địa chỉ của phần tử đầu tiên của mảng) gán cho con trỏ thì ta cũng gọi là con trỏ mảng cấu trúc. Ví dụ: struct Sinhvien { char hoten[25] ; Ngaythang ns; int gt; float diem ; } x, y, *p, lop[60]; p = &x ; // cho con trỏ p trỏ tới biến cấu trúc x p diem = 5.0; // gán giá trị 5.0 cho điểm của biến x p = &lop[10] ; // cho p trỏ tới sinh viên thứ 10 của lớp cout << p hoten; // hiện họ tên của sinh viên này *p = y ; // gán lại sinh viên thứ 10 là y (*p).gt = 2; // sửa lại giới tính của sinh viên thứ 10 là nữ Chú ý: thông qua ví dụ này ta còn thấy một cách khác nữa để truy nhập các thành phần của x được trỏ bởi con trỏ p. Khi đó *p là tương đương với x, do vậy ta dùng lại cú pháp sử dụng toán tử . sau *p để lấy thành phần như (*p).hoten, (*p).diem, Con trỏ được khởi tạo do xin cấp phát bộ nhớ. Ví dụ: 56
59. Sinhvien *p, *q ; p = new Sinhvien[1]; q = new Sinhvien[60]; trong ví dụ này *p có thể thay cho một biến kiểu sinh viên (tương đương biến x ở trên) còn q có thể được dùng để quản lý một danh sách có tối đa là 60 sinh viên (tương đương biến lop[60], ví dụ khi đó *(p+10) là sinh viên thứ 10 trong danh sách). Đối với con trỏ p trỏ đến mảng a, chúng ta có thể sử dụng một số cách sau để truy nhập đến các trường của các thành phần trong mảng, ví dụ để truy cập hoten của thành phần thứ i của mảng a ta có thể viết: p[i].hoten (p+i) hoten *(p+i).hoten Nói chung các cách viết trên đều dễ nhớ do suy từ kiểu mảng và con trỏ mảng. Cụ thể trong đó p[i] là thành phần thứ i của mảng a, tức a[i]. (p+i) là con trỏ trỏ đến thành phần thứ i và *(p+i) chính là a[i]. Ví dụ sau gán giá trị cho thành phần thứ 10 của mảng sinh viên lop, sau đó in ra màn hình các thông tin này. Ví dụ dùng để minh hoạ các cách truy nhập trường dữ liệu của thành phần trong mảng lop. Ví dụ 6 : struct Sinhvien { char hoten[25] ; Ngaythang ns; int gt; float diem ; } lop[60] ; strcpy(lop[10].hoten, "NVA"); lop[10].gt = 1; lop[10].diem = 9.0 ; Sinhvien *p ; // khai báo thêm biến con trỏ Sinh viên p = &lop ; // cho con trỏ p trỏ tới mảng lop cout << p[10].hoten ; // in họ tên sinh viên thứ 10 cout << (p+10) gt ; // in giới tính của sinh viên thứ 10 57
60. cout << (*(p+10)).diem ; // in điểm của sinh viên thứ 10 Chú ý: Độ ưu tiên của toán tử lấy thành phần (dấu chấm) là cao hơn các toán tử lấy địa chỉ (&) và lấy giá trị (*) nên cần phải viết các dấu ngoặc đúng cách. m. Địa chỉ của các thành phần của cấu trúc Các thành phần của một cấu trúc cũng giống như các biến, do vậy cách lấy địa chỉ của các thành phần này cũng tương tự như đối với biến bình thường. Chẳng hạn địa chỉ của thành phần giới tính của biến cấu trúc x là &x.gt (lưu ý độ ưu tiên của . cao hơn &, nên &x.gt là cũng tương đương với &(x.gt)), địa chỉ của trường hoten của thành phần thứ 10 trong mảng lớp là lop[10].hoten (hoten là xâu kí tự), tương tự địa chỉ của thành phần diem của biến được trỏ bởi p là &(p diem). Ví dụ: struct Sinhvien { char hoten[25] ; Ngaythang ns; int gt; float diem ; } lop[60], *p, x = { "NVA", {1,1,1980}, 1, 9.0) }; lop[10] = x; p = &lop[10] ; // p trỏ đến sinh viên thứ 10 trong lop char *ht; int *gt; float *d; // các con trỏ kiểu thành phần ht = x.ht ; // cho ht trỏ đến thành phần hoten của x gt = &(lop[10].gt) ; // gt trỏ đến gt của sinh viên thứ 10 d = &(p diem) ; // p trỏ đến diem của sv p đang trỏ cout << ht ; // in họ tên sinh viên x cout << *gt ; // in giới tính của sinh viên thứ 10 cout << *d ; // in điểm của sinh viên p đang trỏ. n. Đối của hàm là cấu trúc Một cấu trúc có thể được sử dụng để làm đối của hàm dưới các dạng sau đây: Là một biến cấu trúc, khi đó tham đối thực sự là một cấu trúc. Là một con trỏ cấu trúc, tham đối thực sự là địa chỉ của một cấu trúc. Là một tham chiếu cấu trúc, tham đối thực sự là một cấu trúc. Là một mảng cấu trúc hình thức hoặc con trỏ mảng, tham đối thực sự là tên mảng cấu trúc. 58
61. Ví dụ 7 : Ví dụ sau đây cho phép tính chính xác khoảng cách của 2 ngày tháng bất kỳ, từ đó có thể suy ra thứ của một ngày tháng bất kỳ. Đối của các hàm là một biến cấu trúc. Khai báo struct DATE { // Kiểu ngày tháng int ngay ; int thang; int nam ; }; // Số ngày của mỗi tháng int n[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; Hàm tính năm nhuận hay không nhuận, trả lại 1 nếu năm nhuận, ngược lại trả 0. int Nhuan(int nm) { return (nam%4==0 && nam%100!=0 || nam%400==0)? 1: 0; } Hàm trả lại số ngày của một tháng bất kỳ. Nếu năm nhuận và là tháng hai số ngày của tháng hai (28) được cộng thêm 1. int Ngayct(int thang, int nam) { return n[thang] + ((thang==2) ? Nhuan(nam): 0); } Hàm trả lại số ngày tính từ ngày 1 tháng 1 năm 1 bằng cách cộng dồn số ngày của từng năm từ năm 1 đến năm hiện tại, tiếp theo cộng dồn số ngày từng tháng của năm hiện tại cho đến tháng hiện tại và cuối cùng cộng thêm 59
62. số ngày hiện tại. long Tongngay(DATE d) { long i, kq = 0; for (i=1; i<d.nam; i++) kq += 365 + Nhuan(i); for (i=1; i<d.thang; i++) kq += Ngayct(i,d.nam); kq += d.ngay; return kq; } Hàm trả lại khoảng cách giữa 2 ngày bất kỳ. long Khoangcach(DATE d1, DATE d2) { return Tongngay(d1)-Tongngay(d2); } Hàm trả lại thứ của một ngày bất kỳ. Qui ước 1 là chủ nhật, 2 là thứ hai, Để tính thứ hàm dựa trên một ngày chuẩn nào đó (ở đây là ngày 1/1/2000, được biết là thứ bảy). Từ ngày chuẩn này nếu cộng hoặc trừ 7 sẽ cho ra ngày mới cũng là thứ bảy. Từ đó, tính khoảng cách giữa ngày cần tính thứ và ngày chuẩn. Tìm phần dư của phép chia khoảng cách này với 7, nếu phần dư là 0 thì thứ là bảy, phần dư là 1 thì thứ là chủ nhật int Thu(DATE d) { DATE curdate = {1,1,2000}; // ngày 1/1/2000 là thứ bảy long kc = Khoangcach(d, curdate); int du = kc % 7; if (du < 0) du += 7; return du; } Hàm dịch một số dư sang thứ char* Dich(int t) 60
63. { char* kq = new char[10]; switch (t) { case 0: strcpy(kq, "thứ bảy"); break; case 1: strcpy(kq, "chủ nhật"); break; case 2: strcpy(kq, "thứ hai"); break; case 3: strcpy(kq, "thứ ba"); break; case 4: strcpy(kq, "thứ tư"); break; case 5: strcpy(kq, "thứ năm"); break; case 6: strcpy(kq, "thứ sáu"); break; } return kq; } Hàm main() void main() { DATE d; cout > d.ngay >> d.thang >> d.nam ; cout << "Ngày " << d.ngay << "/" << d.thang << "/" << d.nam ; cout << " là " << Dich(Thu(d)); } Ví dụ 8 : Chương trình đơn giản về quản lý sinh viên. Khai báo. struct Sinhvien { // cấu trúc sinh viên char hoten[25] ; Ngaythang ns; int gt; float diem ; } ; Sinhvien lop[3]; // lớp chứa tối đa 3 sinh viên Hàm in thông tin về sinh viên sử dụng biến cấu trúc làm đối. Trong lời gọi sử dụng biến cấu trúc để truyền cho hàm. 61
64. void in(Sinhvien x) { cout > (p ns).ng >> (p ns).th >> (p ns).nam ; cout > (p gt) ; cout > (p diem) ; } Hàm sửa thông tin về sinh viên sử dụng tham chiếu cấu trúc làmđối. Trong lời gọi sử dụng biến cấu trúc để truyền cho hàm. void sua(Sinhvien &r) { int chon; do { cout > chon ; cin.ignore(); switch (chon) { case 1: cin.getline(r.hoten, 25) ; break; case 2: cin >> r.ns.ng >> r.ns.th >> r.ns.nam ; break; case 3: cin >> r.gt ; break; 62
65. case 4: cin >> r.diem ; break; } } while (chon) ; } Hàm nhapds nhập thông tin của mọi sinh viên trong mảng, sử dụng con trỏ mảng Sinhvien làm tham đối hình thức. Trong lời gọi sử dụng tên mảng để truyền cho hàm. void nhapds(Sinhvien *a) { int sosv = sizeof(lop) / sizeof(Sinhvien) -1; // bỏ phần tử 0 for (int i=1; i > chon ; cin.ignore(); sua(a[chon]) ; } Hàm inds hiện thông tin của mọi sinh viên trong mảng, sử dụng hằng con trỏ mảng Sinhvien làm tham đối hình thức. Trong lời gọi sử dụng tên mảng để truyền cho hàm. void hien(const Sinhvien *a) { int sosv = sizeof(lop) / sizeof(Sinhvien) -1; // bỏ phần tử 0 for (int i=1; i<=sosv; i++) in(a[i]) ; } Hàm main() gọi chạy các hàm trên để nhập, in, sửa danh sách sinh viên. void main() { nhapds(lop) ; 63
66. inds(lop); suads(lop); inds(lop); } o. Giá trị hàm là cấu trúc Cũng tương tự như các kiểu dữ liệu cơ bản, giá trị trả lại của một hàm cũng có thể là các cấu trúc dưới các dạng sau: là một biến cấu trúc. là một con trỏ cấu trúc. là một tham chiếu cấu trúc. Sau đây là các ví dụ minh hoạ giá trị cấu trúc của hàm. Ví dụ 9 : Đối và giá trị của hàm là cấu trúc: Cộng, trừ hai số phức. Khai báo kiểu số phức struct Sophuc // Khai báo kiểu số phức dùng chung { float thuc; float ao; }; Hàm cộng 2 số phức, trả lại một số phức Sophuc Cong(Sophuc x, Sophuc y) { Sophuc kq; kq.thuc = x.thuc + y.thuc ; kq.ao = x.ao + y.ao ; return kq; } Hàm trừ 2 số phức, trả lại một số phức Sophuc Tru(Sophuc x, Sophuc y) { Sophuc kq; kq.thuc = x.thuc + y.thuc ; kq.ao = x.ao + y.ao ; 64
67. return kq; } Hàm in một số phức dạng (r + im) void In(Sophuc x) { cout > x.thuc >> x.ao ; cout > y.thuc >> y.ao ; cout << "x + y = " ; In(Cong(x,y)) ; cout << "x - y = " ; In(Tru(x,y)) ; } Ví dụ 10 : Chương trình nhập và in thông tin về một lớp cùng sinh viên có điểm cao nhất lớp. Khai báo kiểu dữ liệu Sinh viên và biến mảng lop. struct Sinhvien { char *hoten ; float diem ; } lop[4] ; Hàm nhập sinh viên, giá trị trả lại là một con trỏ trỏ đến dữ liệu vừa nhập. Sinhvien* nhap() { Sinhvien* kq = new Sinhvien[1]; // nhớ cấp phát vùng nhớ 65
68. kq->hoten = new char[15]; // cho cả con trỏ hoten cout hoten,30); cout > kq->diem; cin.ignore(); return kq; // trả lại con trỏ kq } Hàm tìm sinh viên có điểm cao nhất, giá trị trả lại là một tham chiếu đến sinh viên tìm được. Sinhvien& svmax() { int sosv = sizeof(lop)/sizeof(Sinhvien)-1; // bỏ thành phần thứ 0 float maxdiem = 0; int kmax; // chỉ số sv có điểm max for (int i=1; i<sosv; i++) if (maxdiem < lop[i].diem) { maxdiem = lop[i].diem ; kmax = i; } return lop[kmax]; // trả lại sv có điểm max } Hàm in thông tin của một sinh viên x void in(Sinhvien x) { cout << x.hoten << "\t"; cout << x.diem << endl; } 66
69. Hàm chính void main() { clrscr(); int i; int sosv = sizeof(lop)/sizeof(Sinhvien)-1; // bỏ thành phần thứ 0 for (i=1; i<=sosv; i++) lop[i] = *nhap(); // nhập danh sách lớp for (i=1; i<=sosv; i++) in(lop[i]); // in danh sách lớp Sinhvien &b = svmax(); // khai báo tham chiếu b và cho // tham chiếu đến sv có điểm max in(b); // in sinh viên có điểm max getch(); } 3.1.6.Cấu trúc với thành phần kiểu bit p. Trường bit Thông thường các trường trong một cấu trúc thường sử dụng ít nhất là 2 byte tức 16 bit. Trong nhiều trường hợp một số trường có thể chỉ cần đến số bit ít hơn, ví dụ trường gioitinh thông thường chỉ cần đến 1 bit để lưu trữ. Những trường hợp như vậy ta có thể khai báo kiểu bit cho các trường này để tiết kiệm bộ nhớ. Tuy nhiên, cách khai báo này ít được sử dụng trừ khi cần thiết phải truy nhập đến mức bit của dữ liệu trong các chương trình liên quan đến hệ thống. Một trường bit là một khai báo trường int và thêm dấu: cùng số bit n theo sau, trong đó 0 n < 15. Ví dụ do độ lớn của ngày không vượt quá 31, tháng không vuợt quá 12 nên 2 trường này trong cấu trúc ngày tháng có thể khai báo tiết kiệm hơn bằng 5 và 4 bit như sau: struct Date { int ng: 5; int th: 4; int nam; } ; 67
70. q. Đặc điểm Cần chú ý các đặc điểm sau của một cấu trúc có chứa trường bit: Các bit được bố trí liên tục trên dãy các byte. Kiểu trường bit phải là int (signed hoặc unsigned). Độ dài mỗi trường bit không quá 16 bit. Có thể bỏ qua một số bit nếu bỏ trống tên trường, ví dụ: struct tu { int: 8; int x:8; } mỗi một biến cấu trúc theo khai báo trên gồm 2 byte, bỏ qua không sử dụng byte thấp và trường x chiếm byte (8 bit) cao. Không cho phép lấy địa chỉ của thành phần kiểu bit. Không thể xây dựng được mảng kiểu bit. Không được trả về từ hàm một thành phần kiểu bit. Ví dụ nếu b là một thành phần của biến cấu trúc x có kiểu bit thì câu lệnh sau là sai: return x.b ; // sai tuy nhiên có thể thông qua biến phụ như sau: int tam = x.b ; return tam ; Tiết kiệm bộ nhớ Dùng trong kiểu union để lấy các bit của một từ (xem ví dụ trong phần kiểu hợp). 3.1.7.Câu lệnh typedef Để thuận tiện trong sử dụng, thông thường các kiểu được NSD tạo mới sẽ được gán cho một tên kiểu bằng câu lệnh typedef như sau: typedef ; Ví dụ: Để tạo kiểu mới có tên Bool và chỉ chứa giá trị nguyên (thực chất chỉ cần 2 giá trị 0, 1), ta có thể khai báo: typedef int Bool; khai báo này cho phép xem Bool như kiểu số nguyên. hoặc có thể đặt tên cho kiểu ngày tháng là Date với khai báo sau: typedef struct Date { int ng; 68
71. int th; int nam; }; khi đó ta có thể sử dụng các tên kiểu này trong các khai báo (ví dụ tên kiểu của đối, của giá trị hàm trả lại ). 3.1.8.Hàm sizeof() Hàm trả lại kích thước của một biến hoặc kiểu. Ví dụ: Bool a, b; Date x, y, z[50]; cout << sizeof(a) << sizeof(b) << sizeof(Bool) ; // in 2 2 2 cout << "Số phần tử của z = " << sizeof(z) / sizeof(Date) // in 50 3.2. CẤU TRÚC TỰ TRỎ VÀ DANH SÁCH LIÊN KẾT Thông thường khi thiết kế chương trình chúng ta chưa biết được số lượng dữ liệu cần dùng là bao nhiêu để khai báo số biến cho phù hợp. Đặc biệt là biến dữ liệu kiểu mảng. Số lượng các thành phần của biến mảng cần phải khai báo trước và chương trình dịch sẽ bố trí vùng nhớ cố định cho các biến này. Do buộc phải khai báo trước số lượng thành phần nên kiểu mảng thường dẫn đến hoặc là lãng phí bộ nhớ (khi chương trình không dùng hết) hoặc là không đủ để chứa dữ liệu (khi chương trình cần chứa dữ liệu với số lượng thành phần lớn hơn). Để khắc phục tình trạng này C++ cho phép cấp phát bộ nhớ động, nghĩa là số lượng các thành phần không cần phải khai báo trước. Bằng toán tử new chúng ta có thể xin cấp phát vùng nhớ theo nhu cầu mỗi khi chạy chương trình. Tuy nhiên, cách làm này dẫn đến việc dữ liệu của một danh sách sẽ không còn nằm liên tục trong bộ nhớ như đối với biến mảng. Mỗi lần xin cấp phát bởi toán tử new, chương trình sẽ tìm một vùng nhớ đang rỗi bất kỳ để cấp phát cho biến và như vậy dữ liệu sẽ nằm rải rác trong bộ nhớ. Từ đó, để dễ dàng quản lý trật tự của một danh sách các dữ liệu, mỗi thành phần của danh sách cần phải chứa địa chỉ của thành phần tiếp theo hoặc trước nó (điều này là không cần thiết đối với biến mảng vì các thành phần của chúng sắp xếp liên tục, kề nhau). Từ đó, mỗi thành phần của danh sách sẽ là một cấu trúc, ngoài các thành phần chứa thông tin của bản thân, chúng còn phải có thêm một hoặc nhiều con trỏ để trỏ đến các thành phần tiếp theo hay đứng trước. Các cấu trúc như vậy được gọi là cấu trúc tự trỏ vì các thành phần con trỏ trong cấu trúc này sẽ trỏ đến các vùng dữ liệu có kiểu chính là kiểu của chúng. 69
72. 3.2.1.Cấu trúc tự trỏ Một cấu trúc có chứa ít nhất một thành phần con trỏ có kiểu của chính cấu trúc đang định nghĩa được gọi là cấu trúc tự trỏ. Có thể khai báo cấu trúc tự trỏ bởi một trong những cách sau: Cách 1: typedef struct ; // định nghĩa tên cấu trúc struct { các thành phần chứa thông tin ; *con trỏ ; } ; Ví dụ: typedef struct Sv Sinhvien ; // lưu ý phải có từ khoá struct struct Sv { char hoten[30] ; // thành phần chứa thông tin float diem ; // thành phần chứa thông tin Sinhvien *tiep ; // thành phần con trỏ chứa địa chỉ tiếp theo } ; Cách 2: struct { các thành phần chứa thông tin ; *con trỏ ; } ; typedef ; // định nghĩa tên cấu trúc tự trỏ Ví dụ: struct Sv { char hoten[30] ; // thành phần chứa thông tin 70
73. float diem ; // thành phần chứa thông tin Sv *tiep ; // thành phần con trỏ chứa địa chỉ tiếp theo } ; typedef Sv Sinhvien ; Cách 3: typedef struct // định nghĩa tên cấu trúc tự trỏ { các thành phần chứa thông tin ; *con trỏ ; } ; Ví dụ: typedef struct Sinhvien { char hoten[30] ; // thành phần chứa thông tin float diem ; // thành phần chứa thông tin Sinhvien *tiep ; // con trỏ chứa địa chỉ thành phần tiếp theo } ; Cách 4: struct { các thành phần chứa thông tin ; *con trỏ ; } ; Ví dụ: struct Sinhvien { char hoten[30] ; // thành phần chứa thông tin float diem ; // thành phần chứa thông tin Sinhvien *tiep ; // con trỏ chứa địa chỉ của phần tử tiếp. 71
74. } ; Trong các cách trên ta thấy 2 cách khai báo cuối cùng là đơn giản nhất. C++ quan niệm các tên gọi đứng sau các từ khoá struct, union, enum là các tên kiểu (dù không có từ khoá typedef), do vậy có thể sử dụng các tên này để khai báo. 3.2.2. Khái niệm danh sách liên kết Danh sách liên kết là một cấu trúc dữ liệu cho phép thể hiện và quản lý danh sách bằng các cấu trúc liên kết với nhau thông qua các con trỏ trong cấu trúc. Có nhiều dạng danh sách liên kết phụ thuộc vào các kết nối, ví dụ: Danh sách liên kết đơn, mỗi cấu trúc chứa một con trỏ trỏ đến cấu trúc tiếp theo hoặc trước đó. Đối với danh sách con trỏ trỏ về trước, cấu trúc đầu tiên của danh sách sẽ trỏ về hằng con trỏ NULL, cấu trúc cuối cùng được đánh dấu bởi con trỏ last là con trỏ trỏ vào cấu trúc này. Đối với danh sách con trỏ trỏ về cấu trúc tiếp theo, cấu trúc đầu sẽ được đánh dấu bằng con trỏ head và cấu trúc cuối cùng chưa con trỏ NULL. Danh sách liên kết kép gồm 2 con trỏ, một trỏ đến cấu trúc trước và một trỏ đến cấu trúc sau, 2 đầu của danh sách được đánh dấu bởi các con trỏ head, last. Danh sách liên kết vòng gồm 1 con trỏ trỏ về sau (hoặc trước), hai đầu của danh sách được nối với nhau tạo thành vòng tròn. Chỉ cần một con trỏ head để đánh dấu đầu danh sách. Do trong cấu trúc có chứa các con trỏ trỏ đến cấu trúc tiếp theo và/hoặc cấu trúc đứng trước nên từ một cấu trúc này chúng ta có thể truy cập đến một cấu trúc khác (trước và/hoặc sau nó). Kết hợp với các con trỏ đánh dấu 2 đầu danh sách (head, last) chúng ta sẽ dễ dàng làm việc với bất kỳ phần tử nào của danh sách. Có thể kể một số công việc thường thực hiện trên một danh sách như: bổ sung phần tử vào cuối danh sách, chèn thêm một phần tử mới, xoá một phần tử của danh sách, tìm kiếm, sắp xếp danh sách, in danh sách Hình vẽ bên dưới minh hoạ một danh sách liên kết đơn quản lý sinh viên, thông tin chứa trong mỗi phần tử của danh sách gồm có họ tên sinh viên, điểm. Ngoài ra mỗi phần tử còn chứa con trỏ tiep để nối với phần tử tiếp theo của nó. Phần tử cuối cùng nối với cấu trúc rỗng (NULL). 72
75. head NVA TTB PHT NULL 9.0 7.5 4.0 3.2.3. Các phép toán trên danh sách liên kết Dưới đây chúng ta mô tả tóm tắt cách thức thực hiện một số thao tác trên danh sách liên kết đơn. a. Tạo phần tử mới Để tạo phần tử mới thông thường chúng ta thực hiện theo các bước sau đây: dùng toán tử new xin cấp phát một vùng nhớ đủ chứa một phần tửcủa danh sách. nhập thông tin cần lưu trữ vào phần tử mới. Con trỏ tiep được đặt bằng NULL. gắn phần tử vừa tạo được vào danh sách. Có hai cách: hoặc gắn vào đầu danh sách, khi đó vị trí của con trỏ head (chỉ vào đầu danh sách) được điều chỉnh lại để chỉ vào phần tử mới. hoặc gắn vào cuối danh sách bằng cách cho con trỏ tiep của phần tử cuối danh sách (đang trỏ vào NULL) trỏ vào phần tử mới. Nếu danh sách có con trỏ last để chỉ vào cuối danh sách thì last được điều chỉnh để trỏ vào phần tử mới. Nếu danh sách không có con trỏ last thì để tìm được phần tử cuối chương trình phải duyệt từ đầu, bắt đầu từ con trỏ head cho đến khi gặp phần tử trỏ vào NULL, đó là phần tử cuối của danh sách. head MOI NVA TTB PHT NULL 0.0 9.0 7.5 4.0 Gắn phần tử mới vào đầu danh sách 73
76. b. Chèn phần tử mới vào giữa Giả sử phần tử mới được chèn vào giữa phần tử thứ i và i+1. Để chèn ta nối phần tử thứ i vào phần tử mới và phần tử mới nối vào phần tử thứ i+1. Thuật toán sẽ như sau: Cho con trỏ p chạy đến phần tử thứ i. Cho con trỏ tiep của phần tử mới trỏ vào phần tử thứ i+1 (tuc p->tiep). Cho con trỏ tiep của phần tử thứ i (hiện được trỏ bởi p) thay vì trỏ vào phần tử thứ i+1 bây giờ sẽ trỏ vào phần tử mới. MOI đầu i i+1 cuối NULL 0.0 9.0 7.5 4.0 Chèn phần tử mới vào giữa phần tử i và i+1 a. Xoá phần tử thứ i khỏi danh sách Việc xoá một phần tử ra khỏi danh sách rất đơn giản bởi chỉ việc thay đổi các con trỏ. Cụ thể giả sử cần xoá phần tử thứ i ta chỉ cần cho con trỏ tiep của phần tử thứ i- 1 trỏ ("vòng qua" phần tử thứ i) vào phần tử thứ i+1. Như vậy bây giờ khi chạy trên danh sách đến phần tử thứ i-1, phần tử tiếp theo là phần tử thứ i+1 chứ không còn là phần tử thư i. Nói cách khác phần tử thứ i không được nối bởi bất kỳ phần tử nào nên nó sẽ không thuộc danh sách. Có thể thực hiện các bước như sau: Cho con trỏ p chạy đến phần tử thứ i-1. Đặt phần tử thứ i vào biến x. Cho con trỏ tiep của phần tử thứ i-1 trỏ vào phần tử thứ i+1 bằng cách đặt tiep = x.tiep. Giải phóng bộ nhớ được trỏ bởi x bằng câu lệnh delete x. 74
77. i-1 i i+1 cuối NULL 0.0 9.0 7.5 4.0 Xóa phần tử thứ i c. Duyệt danh sách Duyệt là thao tác đi qua từng phần tử của danh sách, tại mỗi phần tử chương trình thực hiện một công việc gì đó trên phần tử mà ta gọi là thăm phần tử đó. Một phép thăm có thể đơn giản là hiện nội dung thông tin của phần tử đó ra màn hình chẳng hạn. Để duyệt danh sách ta chỉ cần cho một con trỏ p chạy từ đầu đến cuối danh sách đến khi phần tử cuối có con trỏ tiep = NULL thì dừng. Câu lệnh cho con trỏ p chuyển đến phần tử tiếp theo của nó là: p = p tiep ; d. Tìm kiếm Cho một danh sách trong đó mỗi phần tử của danh sách đều chứa một trường gọi là trường khoá, thường là các trường có kiểu cơ sở hoặc kết hợp của một số trường như vậy. Bài toán đặt ra là tìm trên danh sách phần tử có giá trị của trường khoá bằng với một giá trị cho trước. Tiến trình thực hiện nhiệm vụ thựcchất cũng là bài toán duyệt, trong đó thao tác "thăm" chính là so sánh trường khoá của phần tử với giá trị cho trước, nếu trùng nhau ta in kết quả và dừng, Nếu đã duyệt hết mà không có phần tử nào có trường khoá trùng với giá trị cho trước thì xem danh sách không chứa giá trị này. Ngoài các thao tác trên, nói chung còn nhiều các thao tác quen thuộc khác tuy nhiên chúng ta không trình bày ở đây vì nó không thuộc phạm vi của giáo trình này. Dưới đây là một ví dụ minh hoạ cho cấc cấu trúc tự trỏ, danh sách liên kết và một vài thao tác trên danh sách liên kết thông qua bài toán quản lý sinh viên. Khai báo struct DATE { int day, month, year; // ngày, tháng, năm }; struct Sinhvien { // cấu trúc tự 75
78. trỏ char hoten[31]; DATE ns; float diem; Sinhvien *tiep ; }; Sinhvien *dau = NULL, *cuoi = NULL; // Các con trỏ tới đầu và cuối ds Sinhvien *cur = NULL; // Con trỏ tới sv hiện tại int sosv = 0; // Số sv của danh sách Tạo sinh viên mới và nhập thông tin, trả lại con trỏ trỏ đến sinh viên mới. Sinhvien* Nhap1sv() // Tạo 1 khối dữ liệu cho sv mới { Sinhvien *kq = new Sinhvien[1] ; // Cấp phát bộ nhớ cho kq cout hoten); cout > kq->ns.day >> kq->ns.month >> kq- >ns.year; cout > kq->diem ; cin.ignore() ; kq->tiep = NULL; return kq ; } Bổ sung sinh viên mới vào cuối danh sách. void Bosung() // Bổ sung sv mới vào cuối ds { cur = Nhap1sv(); if (sosv == 0) {dau = cuoi = cur;} else { cuoi->tiep = cur; cuoi = cur; } sosv++; } 76
79. Chèn sv mới vào trước sinh viên thứ n. void Chentruoc(int n) // Chèn sv mới vào trước sv thứ n { cur = Nhap1sv(); if (sosv==0) { dau = cuoi = cur; sosv++; return; } if (sosv==1 || n==1) {cur->tiep = dau; dau = cur; sosv++; return;} Sinhvien *truoc, *sau; truoc = dau; sau = dau -> tiep; for (int i=1; i tiep; sau = truoc->tiep; truoc->tiep = cur; cur -> tiep = sau; sosv ++; } Chèn sv mới vào sau sinh viên thứ n. void Chensau(int n) // Chèn sv mới vào sau sv thứ n { cur = Nhap1sv(); if (sosv==0 || sosv tiep; for (int i=1; i tiep; sau = truoc->tiep; truoc->tiep = cur; cur -> tiep = sau; sosv ++; } Xoá sinh viên thứ n. void Xoa(int n) // Xoá sinh viên thứ n { 77
80. if (sosv==1&&n==1) { delete dau ; dau = cuoi = NULL; sosv ; return; } if (n==1) { cur = dau; dau = cur->tiep; delete cur; sosv ; return; } Sinhvien *truoc, *sau; truoc = dau; sau = dau -> tiep; for (int i=1; i tiep; cur = truoc->tiep; sau = cur->tiep; truoc->tiep = sau; delete cur ; sosv ; } Tạo danh sách sinh viên. void Taods() // Tạo danh sách { int tiep = 1; while (tiep) { Bosung(); cout > tiep ; } } In danh sách sinh viên. void Inds() // In danh sách { cur = dau; int i=1; while (cur != NULL) { cout hoten ; cout ns.day ns.month ns.year ; cout diem ; 78
81. cur = cur->tiep; i++; } } Hàm chính. void main() { clrscr(); Taods(); Inds(); getch(); } 3.3. KIỂU HỢP 3.3.1. Khai báo Giống như cấu trúc, kiểu hợp cũng có nhiều thành phần nhưng các thành phần của chúng sử dụng chung nhau một vùng nhớ. Do vậy kích thước của một kiểu hợp là độ dài của trường lớn nhất và việc thay đổi một thành phần sẽ ảnh hưởng đến tất cả các thành phần còn lại. union { Danh sách các thành phần; }; 3.3.2. Truy cập Cú pháp truy cập đến các thành phần của hợp cũng tương tự như kiểu cấu trúc, tức cũng ửs dụng toán tử lấy thành phần (dấu chấm . hoặc cho biến con trỏ kiểu hợp). Dưới đây là một ví dụ minh hoạ việc sử dụng khai báo kiểu hợp để tách byte thấp, byte cao của một số nguyên. Ví dụ 11 : void main() { union songuyen { int n; unsigned char c[2]; } x; cout > x.n ; cout << "Byte thấp của x = " << x.c[0] << endl ; 79
82. cout << "Byte cao của x = " << x.c[1] << endl; } Ví dụ 12 : Kết hợp cùng kiểu nhóm bit trong cấu trúc, chúng ta có thể tìm được các bit của một số như chương trình sau. Trong chương trình ta sử dụng một biến u có kiểu hợp. Trong kiểu hợp này có 2 thành phần là 2 cấu trúc lần lượt có tên s và f. union { struct { unsigned a, b ; } s; struct { unsigned n1: 1; unsigned: 15; unsigned n2: 1; unsigned: 7; unsigned n3: 8; } t ; } u; với khai báo trên đây khi nhập u.s thì nó cũng ảnh hưởng đến u.t, cụ thể u.t.n1 là bit đầu tiên (0) của thành phần u.s.a u.t.n2 là bit 0 của thành phần u.s.b u.t.n3 là byte cao của u.s.b 3.4. KIỂU LIỆT KÊ Có thể gán các giá trị nguyên liên tiếp (tính từ 0) cho các tên gọi cụ thể bằng kiểu liệt kê theo khai báo sau đây: enum tên_kiểu { d/s tên các giá trị }; Ví dụ: enum Bool {false, true}; khai báo kiểu mới đặt tên Bool chỉ nhận 1 trong 2 giá trị đặt tên false và true, trong đó false ứng với giá trị 0 và true ứng với giá trị 1. Cách khai báo kiểu enum trên cũng tương đương với dãy các macro sau: #define false 0 #define true 1 Với kiểu Bool ta có thể khai báo một số biến như sau: Bool Ok, found; hai biến Ok và found sẽ chỉ nhận 1 trong 2 giá trị false (thay cho 0) hoặc true (thay cho 1). Có nghĩa có thể gán: 80