Bài giảng Kỹ thuật lập trình - Tuần 11: Dữ liệu có cấu trúc - Hà Đại Dương

Nội dung text: Bài giảng Kỹ thuật lập trình - Tuần 11: Dữ liệu có cấu trúc - Hà Đại Dương

1. 10/25/2016 Kỹ thuật lập trình Tuần 11 - Dữ liệu có cấu trúc Giáo viên: Hà Đại Dương duonghd@mta.edu.vn 10/25/2016 1 Vấn đề • Các đối tượng phức tạp như: – Điểm trên mặt phẳng, Phân số, Ngày (tháng, năm) – Sinh viên Thì mô tả (dữ liệu) như thế nào? • Mô tả mỗi loại đối đó dưới dạng một kiểu dữ liệu có cấu trúc. • Mỗi thành phần của đối tượng, ví dụ toạ độ x, toạ độ y của 1 điểm gọi là trường (field). 10/25/2016 2 Nội dung • Kiểu có cấu trúc (structure) • Danh sách liên kết (linked list) • Hàng đợi (Queue) • Ngăn xếp (Stack) 10/25/2016 3 1
2. 10/25/2016 Kiểu có cấu trúc (structure) 10/25/2016 4 Khai báo kiểu cấu trúc • Cú pháp 1 struct Tên_cấu_trúc { Kiểu Tên_trường_1; Kiểu Tên_trường_2; Kiểu Tên_trường_n; }; 10/25/2016 5 Khai báo kiểu cấu trúc • Cú pháp 2 typedef struct { Kiểu Tên_trường_1; Kiểu Tên_trường_2; Kiểu Tên_trường_n; } Tên_cấu_trúc; 10/25/2016 6 2
3. 10/25/2016 Trong đó • struct, typedef struct: từ khoá • Tên_cấu_trúc: Tên cấu trúc cần định nghĩa • Kiểu: Kiểu dữ liệu đã có • Tên_trường_k: Tên trường (dữ liêu) 10/25/2016 7 Ví dụ 10/25/2016 8 Khai báo biến kiểu cấu trúc • Đối với cấu trúc khai báo theo cách 1: struct Tên_cấu_trúc Tên_biến, ; • Đối với các cấu khai báo theo cách 2: Tên_cấu_trúc Tên_biến, ; • Ví dụ: struct DiemPhang A, B, C; struct PhanSo P, Q; NgayThang NS; 10/25/2016 9 3
4. 10/25/2016 Truy cập các trường của biến • Với các biến thường (không phải con trỏ) cú pháp: Tên_biến.Tên_trường • Ví dụ với biến: NS (NgayThang) NS.ngay NS.thang NS.nam 10/25/2016 10 Ví dụ 1 • Viết chương trình cho phép nhập vào toạ độ 3 đỉnh của tam giác ABC, tính khoảng cách A, B. 10/25/2016 11 Khai báo biến cấu trúc Truy cập trường 10/25/2016 12 4
5. 10/25/2016 Ví dụ 2 • Viết chương trình cho phép nhập vào 2 phân số A, B; tính và in kết quả phép cộng 2 phân số đó. • Viết chương trình (15 phút) 10/25/2016 13 10/25/2016 14 Biến cấu trúc dạng con trỏ • Như các biến khác, các biến có cấu trúc cũng có thể khai báo dạng con trỏ. • Đối với cấu trúc khai báo theo cách 1: struct Tên_cấu_trúc *Tên_biến, ; • Đối với các cấu khai báo theo cách 2: Tên_cấu_trúc *Tên_biến, ; 10/25/2016 15 5
6. 10/25/2016 Thao tác với biến con trỏ • Phải cấp phát bộ nhớ trước khi sử dụng • Truy cập các trường: Tên_biến->Tên_trường (->: dấu - và >) Ví dụ với biến: A (DiemPhang) A->x A->y 10/25/2016 16 Ví dụ 3 • Viết chương trình cho phép nhập vào toạ độ 3 đỉnh của tam giác ABC, tính khoảng cách A, B (ví dụ 1). Khai báo biến dạng con trỏ 10/25/2016 17 Khai báo dạng con trỏ Cấp phát bộ nhớ Truy cập trường 10/25/2016 18 6
7. 10/25/2016 Danh sách liên kết 10/25/2016 19 Danh sách liên kết • Như đã biết, để tổ chức một danh sách có 2 cách: – Dùng mảng – Dùng con trỏ với việc cấp phát bộ nhớ động • Tuy nhiên với kiểu cấu trúc cùng khả năng “tự trỏ” người ta có thể tạo một dạng danh sách đặc biệt: Danh sách liên kết 10/25/2016 20 Cấu trúc tự trỏ • Trong tổ chức kiểu cấu trúc C/C++ cho phép định nghĩa 1 trường con trỏ để trỏ đến chính đối tượng có cùng kiểu cấu trúc với mình gọi là Cấu trúc tự trỏ. 10/25/2016 21 7
8. 10/25/2016 Cú pháp • Cú pháp 1 struct Tên_cấu_trúc { Kiểu Tên_trường_1; Kiểu Tên_trường_2; Kiểu Tên_trường_n; Tên_cấu_trúc con_trỏ_1 Tên_cấu_trúc con_trỏ_n }; 10/25/2016 22 Cú pháp • Cú pháp 2 typedef struct Tên_cấu_trúc { Kiểu Tên_trường_1; Kiểu Tên_trường_2; Kiểu Tên_trường_n; Tên_cấu_trúc con_trỏ_1; Tên_cấu_trúc con_trỏ_n; }; 10/25/2016 23 Ví dụ 4 • Sử dụng danh sách liên kết lưu các đỉnh kề nhau của 1 đa giác. • Khai báo cấu trúc tự trỏ 10/25/2016 24 8
9. 10/25/2016 Ví dụ 4 10/25/2016 25 Danh sách liên kết • Liên kết đơn: Tạo thành danh sách List Data Next Data Next Data Next Data Next Data Next Data Next NULL 10/25/2016 26 Danh sách liên kết • Liên kết đôi: Cây nhị phân, liên kết 2 chiều Tree Left Data Right Left Data Right Left Data Right Left Data Right Left Data Right 10/25/2016 27 9
10. 10/25/2016 Danh sách liên kết đơn • Quản lý danh sách (như là một mảng) List Data Next Data Next Data Next NULL Đầu danh sách: con trỏ List Cuối: Trỏ đến NULL để báo hiệu kết thúc danh sách 10/25/2016 28 Ví dụ 5 10/25/2016 29 Danh sách liên kết đơn • Thêm một mục List 3 Next 2 Next 1 Next NULL 4 Next 10/25/2016 30 10
11. 10/25/2016 Ví dụ 5 10/25/2016 31 Danh sách liên kết đơn • Xoá một mục List 3 Next 2 Next 1 Next NULL 10/25/2016 32 10/25/2016 33 11
12. 10/25/2016 Bài tập 10/25/2016 34 Bài tập 1. Viết chương trình cho phép nhập vào toạ độ 3 đỉnh của tam giác ABC, tính diện tích ABC. 2. Dùng danh sách liên kết lưu toạ độ các đỉnh kề của một đa giác, tính diện tích của đa giác đó. 3. Đọc dữ liệu điểm của sinh viên từ 1 file text vào 1 danh sách liên kết đơn theo thứ tự điểm giảm dần. 10/25/2016 35 Bài tập về nhà 1. Viết chương trình cho phép nhập vào 1 biểu thức bất kỳ, tách từng thành phần (toán hạng, toán tử) của biểu thức đó và lưu vào 1 danh sách liên kết đơn. 10/25/2016 36 12