Kỹ thuật lập trình - Tuần 11: Dữ liệu có cấu trúc

10/25/2016 1 Tuần 11 - Dữ liệu có cấu trúc Giáo viên: Hà Đại Dương duonghd@mta.edu.vn Kỹ thuật lập trình 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 10/25/2016 2 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 10/25/2016 5 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; }; Khai báo kiểu cấu trúc • Cú pháp 2 10/25/2016 6 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 3 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 10/25/2016 4 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 10/25/2016 12 Khai báo biến cấu trúc Truy cập trường 10/25/2016 5 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 10/25/2016 6 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 10/25/2016 18 Khai báo dạng con trỏ Cấp phát bộ nhớ Truy cập trường 10/25/2016 7 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 10/25/2016 8 Cú pháp • Cú pháp 1 10/25/2016 22 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 }; Cú pháp • Cú pháp 2 10/25/2016 23 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; }; 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 10/25/2016 9 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 10/25/2016 26 Data Next Data Next Data Next Data Next Data Next Data Next List NULL Danh sách liên kết • Liên kết đôi: Cây nhị phân, liên kết 2 chiều 10/25/2016 27 Data RightLeft Data RightLeft Data RightLeft Data RightLeft Data RightLeft Tree 10/25/2016 10 Danh sách liên kết đơn • Quản lý danh sách (như là một mảng) Đầ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 Data Next Data Next Data NextList NULL Ví dụ 5 10/25/2016 29 Danh sách liên kết đơn • Thêm một mục 10/25/2016 30 3 Next 2 Next 1 NextList NULL 4 Next 10/25/2016 11 Ví dụ 5 10/25/2016 31 Danh sách liên kết đơn • Xoá một mục 10/25/2016 32 3 Next 2 Next 1 NextList NULL 10/25/2016 33 10/25/2016 12 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