Kỹ thuật lập trình - Tuần 12: Ngăn xếp và hàng đợi

11/22/2016 1 Tuần 12 - Ngăn xếp & Hàng đợi Giáo viên: Hà Đại Dương duonghd@mta.edu.vn Kỹ thuật lập trình 11/22/2016 1 Bài trước 1. Kiểu có cấu trúc (structure) 2. Danh sách liên kết (linked list) 3. Ngăn xếp (Stack) 4. Hàng đợi (Queue) 11/22/2016 2 Ngăn xếp - Stack 11/22/2016 3 11/22/2016 2 Khái quát • Là một dạng danh sách “đặc biệt”: Việc thêm (phần tử) vào và lấy (phần tử) ra đều làm ở đỉnh ngăn xếp. • Để tạo ngăn xếp: – Có thể dùng Mảng (Sinh viên tự nghiên cứu, BTVN) – Có thể dùng danh sách liên kết 11/22/2016 4 Các thao tác với ngăn xếp • Khai báo • Khởi tạo (init) • Kiểm tra ngăn xếp rỗng (isEmpty) • Thêm phần tử vào (push) • Lấy phần tử ra (pop) • Lấy giá trị phần tử trên đỉnh (get) 11/22/2016 5 Khai báo • Cấu trúc dạng bản ghi tự trỏ • Khai báo biến 11/22/2016 6 11/22/2016 3 Vấn đề • Biến mô tả stack là một con trỏ • Chúng ta mới dùng tham số thực cho hàm dạng biến thường, và muốn trả về giá trị cho tham số này thì tham số hình thức cần khai báo dạng con trỏ hoặc tham chiếu • Cần truyền tham số thực dạng con trỏ cho hàm làm thế nào? -> Con trỏ (hoặc tham chiếu??) 11/22/2016 7 Ba cách khai báo tham số 11/22/2016 8 Tham trị Con trỏ Tham chiếu Gọi hàmHàm với các dạng tham số đầu vào a, b không đổi Khởi tạo • Khởi tạo giá trị cuối để biết điểm kết thúc của ngăn xếp ở đâu. Giá trị này thường được chọn là NULL. • Hàm init() 11/22/2016 9 11/22/2016 4 Kiểm tra ngăn xếp rỗng • Kiểm tra xem đã đến đáy ngăn xếp hay chưa • Hàm isEmpty() 11/22/2016 10 Thêm phần tử vào (push) • Thêm phần tử vào đỉnh ngăn xếp • Hàm push() 11/22/2016 11 Lấy phần tử ra (pop) • Lấy ra phần tử ở đỉnh ngăn xếp • Hàm pop() 11/22/2016 12 11/22/2016 5 Ví dụ 1 - Đảo ngược xâu • Đảo ngược 1 xâu ký tự, ví dụ đảo ngược HELLO là OLLEH • Cách làm: 1. Lấy từng ký tự của xâu vào theo thứ tự từ trái qua phải và đẩy (push) vào ngăn xếp. 2. Lần lượt lấy các ký tự ra khỏi ngăn xếp -> Được xâu đảo ngược. 11/22/2016 13 Ví dụ 1 11/22/2016 14 Ví dụ 2 - Tính giá trị BT hậu tố • Biểu thức trung tố: a+b a+b*c • Biểu thức hậu tố: ab+ abc*+ 11/22/2016 15 11/22/2016 6 Ví dụ 2 Có biểu thức: 253*+ (dạng trung tố: 2+5*3) • Tư tưởng: Tính giá trị biểu thức hậu tố: – Đọc từ trái sang phải • Nếu gặp toán hạng đưa vào stack • Nếu gặp toán tử (2 ngôi) lấy hai giá trị cuối cùng trên stack, thực hiện phép toán. Đưa giá trị tính được vào stack – Lặp đến hết chuỗi giá trị còn lại cuối cùng trong stack là giá trị của biểu thức 11/22/2016 16 Ví dụ 2 • Làm từng bước với biểu thức: 253*+ • Thế nào là 1 toán hạng? • Thế nào à 1 toán tử? • Viết chương trình (15 phút) 11/22/2016 17 11/22/2016 18 11/22/2016 7 11/22/2016 19 11/22/2016 20 Ví dụ 3 - BT trung tố -> hậu tốt • Đã tính được giá trị biểu thức hậu tố • Nếu chuyển được từ trung tố-> hậu tố ta tính được biểu thức viết theo cách thông thường (trung tố) bất kỳ 11/22/2016 21 11/22/2016 8 Ví dụ 3 • Có biểu thức: 2+5*3 và 2*5+3 • Ý tưởng thuật toán: – Duyệt từ trái sang nếu gặp: • Toán hạng: đưa và chuỗi (mảng) đầu ra • Toán tử: – Nếu “lớn” hơn toán tử trong stack thì đưa vào stack – Nếu “bé” hơn hoặc bằng thì lấy toán tử trong stack vào chuỗi đầu ra đến khi gặp toán tử lớn hơn; Đưa toán tử mới vào stack. – Hết chuỗi, lấy toàn bộ các toán tử đưa ra chuỗi đầu ra. 11/22/2016 22 Ví dụ 3 • So sánh các phép toán: (*,/) > (+,-) • Làm từng bước với 2+5*3 và 2*5+3 • Với stack trong bài toán này cần lấy giá trị (mà không xoá) của phần tử trên đỉnh stack để so sánh. Hàm get() 11/22/2016 23 Ví dụ 3 • Viết chương trình (15 phút) 11/22/2016 24 11/22/2016 9 Ví dụ 4 - Trong BT có dấu () • Biểu thức có cả dấu ( và ) • Làm như bình thường với 1 số sửa đổi: – Duyệt từ trái sang nếu gặp: • Toán hạng: đưa và chuỗi (mảng) đầu ra • Toán tử: – Nếu “lớn” hơn toán tử trong stack thì đưa vào stack – Nếu “bé” hơn hoặc bằng thì lấy toán tử trong stack vào chuỗi đầu ra đến khi gặp toán tử lớn hơn; Đưa toán tử mới vào stack. – Nếu là (: đẩy ( vào stack – Nếu là ): lấy toán tử trong stack vào chuỗi đầu ra cho đến khi gặp ( đầu tiên (Không đưa ( và ) vào chuỗi đầu ra) 11/22/2016 25 Ví dụ 4 • Làm từng bước với 2+(5+3)*4 Kết quả: 2,5,3,+,4,*,+ • Viết chương trình (15 phút) 11/22/2016 26 Ví dụ 5 - Tính giá trị biểu thức (Ngầm hiểu biểu thức là BT trung tố) • Chuyển BT trung tố -> Hậu tố (1 hàm) • Tính giá trị của BT hậu tố (1 hàm) • Tạm giả thiết rằng: Mỗi toán hạng (và mỗi toán tử) là 1 ký tự. • Viết chương trình (15 phút) 11/22/2016 27 11/22/2016 10 Ví dụ 6 - Tính giá trị biểu thức • Toán hạng có thể có nhiều hơn 1 chữ số • Ví dụ biểu thức: 123+(64-31)*32+1000 • Thực hiện: 1. Chuyển BT về dạng hậu tố BTHT (1 mảng) 2. Tính giá trị biểu thức hậu tố trên BTHT 11/22/2016 28 Hàng đợi - Queue 11/22/2016 29 Khái quát • Là một dạng danh sách “đặc biệt”: Thêm (phần tử) vào ở cuối và lấy (phần tử) ra ở đầu hàng đợi. • Để tạo hàng đợi: – Có thể dùng Mảng (Sinh viên tự nghiên cứu, BTVN) – Có thể dùng danh sách liên kết 11/22/2016 30 11/22/2016 11 Khái quát • Dùng 2 con trỏ: – Con trỏ head: lấy ra – Con trỏ tail: đẩy giá trị vào 11/22/2016 31 Các thao tác với hàng đợi • Khai báo • Khởi tạo (init) • Kiểm tra hàng đợi rỗng (isEmpty) • Thêm phần tử vào (put) • Lấy phần tử ra (get) 11/22/2016 32 Khai báo • Khai báo cấu trúc • Khai báo biến 11/22/2016 33 11/22/2016 12 Khởi tạo • Khởi tạo giá trị cuối để biết điểm kết thúc của hàng đợi ở đâu. Giá trị này thường được chọn là NULL. • Hàm init() 11/22/2016 34 Kiểm tra hàng đợi rỗng • Kiểm tra xem đã hết các phần tử trong hàng đợi hay chưa • Hàm isEmpty() 11/22/2016 35 Thêm phần tử vào (put) • Thêm phần tử vào đuôi hàng đợi • Hàm put() 11/22/2016 36 11/22/2016 13 11/22/2016 37 Lấy phần tử ra (get) • Lấy ra phần tử ở đầu hàng đợi • Hàm get() 11/22/2016 38 Ví dụ 7 - Duyệt xâu ký tự • Duyệt xâu ký tự • Cách làm: 1. Lấy từng ký tự của xâu vào theo thứ tự từ trái qua phải và đẩy (put) vào hàng đợi. 2. Lần lượt lấy các ký tự ra khỏi hàng đợi. 11/22/2016 39 11/22/2016 14 11/22/2016 40 Ứng dụng • Có thể dùng stack, queue để tránh đệ qui • Một số bài toán: – Duyệt đồ thị • Stack: Duyệt theo chiều sâu • Queue: Duyệt theo chiều rộng – Tô màu một vùng với biên xác định – 11/22/2016 41 Bài tập 11/22/2016 42 11/22/2016 15 Bài tập 1. Viết chương trình tách toán hạng, toán tử, dấu mở đóng ngoặc của một xâu biểu thức (trung tố). 2. Viết chương trình tính giá trị của biểu thức nhập từ bàn phím. Lưu ý các toán hạng có thể có nhiều hơn 1 chữ số. 3. Sử dụng queue giải quyết bài toán tô màu 4. Sử dụng stack giải quyết bài toán tô màu. 11/22/2016 43 Bài tập về nhà 1. Cài đặt các thao tác cho ngăn xếp sử dụng mảng 2. Cài đặt các thao tác cho hàng đợi sử dụng mảng 3. Đề xuất thuật toán, viết chương trình kiểm tra xem 1 xâu ký tự có được viết đúng cú pháp hay không? 11/22/2016 44