Bài giảng Lập trình nâng cao - Bài 10+11+12: Kiểu cấu trúc (struct) và kiểu hợp nhất (union) - Trương Xuân Nam

Nội dung text: Bài giảng Lập trình nâng cao - Bài 10+11+12: Kiểu cấu trúc (struct) và kiểu hợp nhất (union) - Trương Xuân Nam

1. LẬP TRÌNH NÂNG CAO Bài 10+11+12: Kiểu cấu trúc (struct) và kiểu hợp nhất (union) TRƯƠNG XUÂN NAM 1
2. Nội dung chính 1. Các kiểu dữ liệu tự tạo 2. Cấu trúc (struct) 1. Khai báo 2. Phép toán 3. Trường bit 4. Kích cỡ của struct 3. Bài tập struct 4. Hợp nhất (union) 5. Liệt kê (enum) 6. Cấu trúc tự trỏ và danh sách 7. Bài tập Trương Xuân Nam - Khoa CNTT 2
3. Phần 1 Các kiểu dữ liệu tự tạo Trương Xuân Nam - Khoa CNTT 3
4. Các kiểu dữ liệu tự tạo ▪ Kiểu dữ liệu: quy định về loại dữ liệu được ghi trong biến ▪ Có tính quy ước, vì dữ liệu luôn được ghi ở dạng byte / bit ▪ Xác định cách thức xử lý giá trị khi tham gia tính toán ▪ Các ngôn ngữ lập trình cung cấp một số kiểu dữ liệu cơ bản (số nguyên, số thực, logic, ) ▪ Cũng là các kiểu dữ liệu thường dùng trong cuộc sống ▪ Cuộc sống có nhiều kiểu dữ liệu phức tạp hơn: ▪ Phân số: tử số (số thực) + mẫu số (số thực) ▪ Số phức: phần thực (số thực) + phần ảo (số thực x i) ▪ Ngày: ngày (số nguyên) + tháng (số nguyên) + năm (số nguyên) ▪ Giờ: giờ (số nguyên) + phút (số nguyên) + giây (số nguyên) + ▪ Thời gian: Ngày + Giờ Trương Xuân Nam - Khoa CNTT 4
5. Tự tạo kiểu dữ liệu mới ▪ Các kiểu dữ liệu phức tạp thường là tổ hợp từ các loại cơ bản và đôi khi từ những loại tổ hợp đơn giản hơn ▪ Không ngôn ngữ lập trình nào cung cấp được mọi loại dữ liệu cần thiết cho mọi nhu cầu thực tiễn ▪ C/C++ cung cấp các cơ chế cho phép lập trình viên tự tạo các kiểu dữ liệu mới ▪ Cấu trúc (struct) ▪ Hợp nhất (union) ▪ Liệt kê (enum) ▪ Lớp (class) ▪ Chúng ta thực tế đã sử dụng rất nhiều các kiểu dữ liệu tự tạo (string, vector, ) Trương Xuân Nam - Khoa CNTT 5
6. Phần 2 Cấu trúc (struct) Trương Xuân Nam - Khoa CNTT 6
7. Đặt vấn đề: xét một bài toán cụ thể ▪ Quản lý dữ liệu thời gian (ngày tháng năm) ▪ Cách làm thông thường: bộ 3 biến lưu ngày, tháng, năm ▪ Mỗi khi có dữ liệu ngày tháng thì cần khai báo thêm cả 3 ▪ Truyền thông tin vào hàm? Dùng 3 tham số ▪ Trả về kết quả từ hàm? Không làm được ▪ Nhận xét ▪ Đặt tên biến nhập nhằng, khó quản lý, phải có quy tắc riêng ▪ Truyền tham số cho hàm dài dòng ▪ Tìm kiếm, sắp xếp, sao chép, khó khăn ▪ Giải pháp của C/C++: Gom những thông tin này tạo thành một kiểu dữ liệu mới Dữ liệu kiểu cấu trúc
8. Khai báo struct ▪ Cú pháp sử dụng struct: struct { }; ▪ Sau khi khao báo struct, ta có một kiểu dữ liệu mới, trùng tên với struct ▪ Ví dụ: struct ThoiGian { // kiểu dữ liệu ThoiGian int ngay, thang, nam; // các thành phần con }; ThoiGian homnay; // biến kiểu ThoiGian homnay.ngay = 3; // thành phần ngày = 3 homnay.thang = 4; // thành phần tháng = 4 homnay.nam = 2021; // thành phần năm = 2021 TRƯƠNG XUÂN NAM 8
9. Khai báo struct // khai báo kiểu ĐIỂM và 2 biến struct DIEM { int x; int y; } diem1, diem2; // khai báo biến riêng rẽ struct DIEM diem3, diem4; // khai báo biến trong C++ được bỏ struct DIEM diem5, diem6; TRƯƠNG XUÂN NAM 9
10. Khai báo struct // khai báo kiểu gián tiếp bằng typedef typedef struct { int x; int y; } POINT; // khai báo biến với định kiểu typedef struct POINT p1, p2; // khai báo và khởi trị struct POINT { int x; int y; } p3 = { 123, 456 }, p4; TRƯƠNG XUÂN NAM 10
11. Phép toán với struct ▪ Một kiểu struct được xem là một kiểu dữ liệu mới ▪ Phép gán hai biến struct cho nhau: sao chép nguyên văn dữ liệu từ nguồn tới đích ▪ Phép truy cập thành phần: ▪ Mỗi thành phần của struct là một biến độc lập ▪ Truy cập vào từng thành phần thông qua toán tử thành phần (.) struct Top10 { double top[10]; int len; }; Top10 abc; // biến kiểu Top10 abc.top[0] = 9.9; // gán thành phần abc.len = 1; // gán thành phần Top10 xyz = abc; // gán 2 struct TRƯƠNG XUÂN NAM 11
12. Phép toán với struct ▪ Truy cập struct lồng nhau struct A { int x, y; }; struct B { A p, q; }; B b; b.p.x = 1, b.p.y = 2; ▪ Toán tử thành phần sử dụng với con trỏ: struct Top10 { double top[10]; int len; int *end; }; Top10 * t1 = new Top10; t1->top[0] = 9.5; (*t1).len = 1; t1->end = nullptr; TRƯƠNG XUÂN NAM 12
13. Trường bit ▪ C/C++ cho phép chỉ định kích cỡ của một thành phần tới số bit struct bit_fields { unsigned int b0 : 1; unsigned int b1 : 4; unsigned int b2 : 1; unsigned int b3 : 10; }; ▪ Trong ví dụ trên thì b0 chỉ dùng 1 bit, b1 dùng 4 bit, b2 dùng 1 bit và b3 dùng 10 bit ▪ Tất cả 4 trường trên có thể được “nén” vào trong một vùng 16 bit (2 byte) TRƯƠNG XUÂN NAM 13
14. Trường bit ▪ Trường bit là cách sử dụng tinh tế các dữ liệu tới đơn vị nhỏ nhất của máy tính, cách làm này rất thông dụng trong việc lập trình điều kiển hoặc giao tiếp cấp thấp ▪ Quy tắc: 1. Số bit không được vượt quá số bit thực sự của kiểu khai báo 2. Không thể thực hiện phép lấy địa chỉ (&) của trường bit 3. Có thể ép trình dịch chuyển trường tiếp theo ra đầu byte bằng cách thêm một trường không tên cỡ 0 bit 4. Biến nguyên luôn có một bit dấu, vì vậy rất thận trọng với trường bit dạng nguyên nhưng cỡ 1 bit 5. Trường bit không thể khai báo dạng static 6. Trường bit không thể khai báo dạng mảng TRƯƠNG XUÂN NAM 14
15. Trường bit struct date { int d : 5; // int hay unsigned int? int m : 4; // int hay unsigned int? int y; }; struct align { unsigned int x : 5; unsigned int : 0; // cái gì đây? unsigned int y : 8; }; TRƯƠNG XUÂN NAM 15
16. Kích cỡ của struct struct A { int a; double b; }; struct B { int a; int b; double c; }; struct C { int a; double c; int b; }; TRƯƠNG XUÂN NAM 16
17. Kích cỡ của struct ▪ Cơ chế canh biên: ▪ Các biến thuộc struct sẽ được đẩy dịch theo từng bước, không nhất thiết phải đặt liên tiếp nhau trong bộ nhớ ▪ Lợi: tăng tốc độ xử lý ▪ Hại: kích cỡ của struct có thể tăng do xuất hiện nhiều ô nhớ thừa không được sử dụng ▪ Nguy hiểm: không có sự nhất quán về mã máy ▪ Chỉ thị: #pragma pack(n) ▪ N có thể là 1, 2, 4, 8, 16 ▪ Visual C++ mặc định là 8 ▪ Borland C++ mặc định là 1 TRƯƠNG XUÂN NAM 17
18. Phần 3 Bài tập struct TRƯƠNG XUÂN NAM 18
19. Hãy tự tạo vài kiểu dữ liệu mới TRƯƠNG XUÂN NAM 19
20. Bài tập ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ Dữ liệu kiểu cấu trúc
21. Bài tập ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ Dữ liệu kiểu cấu trúc
22. Phần 4 Hợp nhất (union) TRƯƠNG XUÂN NAM 22
23. Hợp nhất (union) ▪ Hợp nhất là một kiểu đóng gói dữ liệu thú vị trong C/C++ ▪ Nhắc lại về cấu trúc (struct): ▪ Nhóm các mảnh dữ liệu liên quan với nhau thành một khối ▪ Các dữ liệu con là các biến độc lập nhau, nằm trong khối nhớ cấp cho struct theo thứ tự khai báo ▪ Thay đổi dữ liệu con này không ảnh hưởng đến dữ liệu con khác ▪ Hợp nhất (union): ▪ Khai báo và mọi thứ (phép toán, cú pháp) giống hệt struct ▪ Khác biệt duy nhất: các dữ liệu con nằm chồng lên nhau trong cùng một khối nhớ ▪ Thay đổi dữ liệu con này có thể ảnh hưởng đến dữ liệu con khác TRƯƠNG XUÂN NAM 23
24. Hợp nhất (union) #include using namespace std; struct A { Sơ đồ bộ nhớ của struct A int x; x x x x y y z z short y; short z; }; union B { Sơ đồ bộ nhớ của union B int x; short y; x,y,z x,y,z x x short z; }; int main() { cout << sizeof(A) << endl; // 8 cout << sizeof(B) << endl; // 4 } TRƯƠNG XUÂN NAM 24
25. Hợp nhất (union) ▪ Cú pháp khai báo của union: giống struct union { }; ▪ Mọi thành phần của union đều nằm chồng lên nhau (chung địa chỉ là phần đầu của union) ▪ Kích cỡ của union = kích cỡ của thành phần lớn nhất ▪ Vấn đề chia sẻ khối nhớ: cập nhật thành phần này ảnh hưởng đến thành phần khác ▪ Vậy union dùng vào việc gì? ▪ Cung cấp nhiều kiểu nhìn cho một khối dữ liệu ▪ Sử dụng cùng một khối dữ liệu theo các cách uyển chuyển hơn TRƯƠNG XUÂN NAM 25
26. Hợp nhất (union) #include using namespace std; union ABC { int *diachi; // một con trỏ int giatri; // nhìn con trỏ như là một số nguyên }; int main() { int k = 100; ABC n; n.diachi = &k; cout << n.diachi << endl; // góc nhìn là con trỏ cout << n.giatri << endl; // góc nhìn là số nguyên cout << &k << endl; // địa chỉ của k để so sánh cout << (int) &k << endl; // đia chỉ của k ở số nguyên } TRƯƠNG XUÂN NAM 26
27. Struct trong union union Date { char str[11]; struct { char day[2]; char separator1; char month[2]; char separator2; char year[4]; } parts; } ngaynghi = {"30/04/2021"}; Sơ đồ bộ nhớ của union Date 3 0 / 0 4 / 2 0 2 1 \0 TRƯƠNG XUÂN NAM 27
28. Union trong struct #include using namespace std; struct Domain { string name; union { unsigned char p[4]; unsigned int v; } ip; } mydomain = {"txnam.net", { 150, 95, 105, 231 } }; int main() { cout << "Ten mien: " << mydomain.name << endl;; cout << "IP: " << mydomain.ip.v; } TRƯƠNG XUÂN NAM 28
29. Phần 5 Liệt kê (enum) TRƯƠNG XUÂN NAM 29
30. Liệt kê (enum) ▪ Kiểu liệt kê là tập hợp các hằng số nguyên được đặt tên ▪ Cú pháp: enum { }; ▪ Ví dụ: // kiểu Ngày, liệt kê các ngày trong tuần // giá trị các hằng số do trình dịch tự chọn enum Ngay { chunhat, thu2, thu3, thu4, thu5, thu6, thu7 }; // kiểu Giới tính, liệt kê các giới tính được khai báo // xác định luôn vài giá trị của hằng // hằng số KhongKhaiBao được tự động chọn là 3 enum GioiTinh { Nam = 1, Nu = 2, KhongKhaiBao }; // kiểu Bài tập, liệt kê các loại bài tập được giao enum BaiTap { mot_tiet, giua_ky, cuoi_ky, do_an }; TRƯƠNG XUÂN NAM 30
31. Liệt kê (enum) ▪ Thay vì dùng kiểu liệt kê, lập trình viên có thể tự định nghĩa các hằng số ▪ Nhưng kiểu liệt kê gom các hằng số có cùng mối quan hệ thành một nhóm, giúp viết mã trong sáng, dễ hiểu hơn, ▪ Ví dụ: GioiTinh abc = Nam; switch (abc) { case Nam: cout << "Gioi tinh Nam"; break; case Nu: cout << "Gioi tinh Nu"; break; case KhongKhaiBao: cout << "Khong khai gioi tinh"; break; default: cout << "Loi"; } TRƯƠNG XUÂN NAM 31
32. Phần 6 Cấu trúc tự trỏ và danh sách TRƯƠNG XUÂN NAM 32
33. Cấu trúc tự trỏ: khái niệm ▪ Cấu trúc tự trỏ là dạng struct mà trong bản thân struct chứa (các) con trỏ đến chính cấu trúc đó ▪ Cấu trúc bình thường vs Cấu trúc tự trỏ // một cấu trúc thông thường struct Info { string name; // tên int * data; // con trỏ đến dữ liệu string *sub; // một con trỏ khác }; // nếu struct Node chứa một (vài) con trỏ đến Node // thì đó là cấu trúc tự trỏ struct Node { string student; // trường tên sinh viên Node * next; // con trỏ đến một Node }; TRƯƠNG XUÂN NAM 33
34. Cấu trúc tự trỏ: có nhiều loại // cấu trúc tự trỏ dùng cho danh sách liên kết struct ListNode { int data; // dữ liệu ListNode *next; // nút tiếp theo }; // cấu trúc tự trỏ dùng cho cây nhị phân struct BinaryTreeNode { int data; // dữ liệu BinaryTreeNode *left, *right; // nút trái và nút phải }; // cấu trúc tự trỏ dùng cho cây tổng quát struct TreeNode { int data; // dữ liệu int childNo; // số nút con TreeNode child; // các nút con }; TRƯƠNG XUÂN NAM 34
35. Cấu trúc tự trỏ: ứng dụng vào danh sách (list) ▪ Danh sách: là cấu trúc dữ liệu thông dụng trong máy tính ▪ Lấy cảm hứng từ cuộc sống ▪ Các dữ liệu móc nối với nhau thành một chuỗi ▪ Có thể dễ dàng xóa một mục ▪ Có thể dễ dàng chèn thêm một mục ▪ Duyệt theo thứ từ từ mục đầu tiên đến hết TRƯƠNG XUÂN NAM 35
36. Cấu trúc tự trỏ: ứng dụng vào danh sách (list) ▪ Có nhiều cách cài đặt danh sách, sử dụng cấu trúc tự trỏ trong bài này chỉ là một trong những cách cài đặt, thường gọi là danh sách liên kết đơn (single linked list) ▪ Một nút trên danh sách: dùng cấu trúc tự trỏ struct Node { string data; // trường dữ liệu Node * next; // con trỏ đến nút tiếp theo }; ▪ Khai báo danh sách: một con trỏ trỏ tới đầu danh sách Node * head; // con trỏ đến nút đầu tiên A B C D E head TRƯƠNG XUÂN NAM 36
37. Cấu trúc tự trỏ: ứng dụng vào danh sách (list) // kiểm tra xem danh sách có rỗng không? bool isEmpty(Node * head) { return nullptr == head; } // tạo một nút mới với dữ liệu value, con trỏ tiếp là next Node * createNode(string value, Node * next = nullptr) { return new Node { value, next }; } // tạo một danh sách chứa n giá trị lấy từ mảng value Node * createList(string value[], int n) { Node * p = nullptr; for (int i = n-1; i >= 0; i ) p = createNode(value[i], p); return p; } TRƯƠNG XUÂN NAM 37
38. Cấu trúc tự trỏ: ứng dụng vào danh sách (list) // tạo một danh sách rỗng Node * createList() { return nullptr; } // hủy một danh sách void deleteList(Node * & head) { Node *ptr = head; while (nullptr != ptr) { Node * c = ptr; ptr = ptr->next; delete c; } head = nullptr; } TRƯƠNG XUÂN NAM 38
39. Cấu trúc tự trỏ: ứng dụng vào danh sách (list) // đếm số nút trên danh sách int lengthList(Node * head) { int len = 0; while (nullptr != head) { len++; head = head->next; } return len; } // in ra các phần tử trong danh sách void printList(Node * head) { while (nullptr != head) { cout data next; } } TRƯƠNG XUÂN NAM 39
40. Cấu trúc tự trỏ: ứng dụng vào danh sách (list) // chèn giá trị value thành vị trí thứ n trong danh sách // chèn vào cuối nếu n > số phần tử trong danh sách void insertNode(Node * & head, string value, int n) { Node ptr = &head; while (n > 0) { if (nullptr == *ptr) break; ptr = &((*ptr)->next); n ; } *ptr = createNode(value, *ptr); } TRƯƠNG XUÂN NAM 40
41. Cấu trúc tự trỏ: ứng dụng vào danh sách (list) // xóa giá trị thứ n trong danh sách // không làm gì nếu n > số phần tử trong danh sách void deleteNode(Node * & head, int n) { if (nullptr == head) return; Node ptr = &head; for (int i = 0; i next); if (nullptr == *ptr) return; } Node * c = *ptr; *ptr = c->next; delete c; } TRƯƠNG XUÂN NAM 41
42. Phần 7 Bài tập TRƯƠNG XUÂN NAM 42
43. Bài tập phần struct và union TRƯƠNG XUÂN NAM 43
44. Bài tập phần danh sách liên kết: viết các hàm TRƯƠNG XUÂN NAM 44