Bài giảng Kỹ thuật lập trình: Ngăn xếp & Hàng đợi - GV. Hà Đại Dương

11/22/2016<br /> <br /> Kỹ thuật lập trình<br /> <br /> Tuần 12 - Ngăn xếp & Hàng đợi<br /> Giáo viên: Hà Đại Dương<br /> duonghd@mta.edu.vn<br /> <br /> 11/22/2016<br /> <br /> 1<br /> <br /> Bài trước<br /> 1.<br /> 2.<br /> 3.<br /> 4.<br /> <br /> Kiểu có cấu trúc (structure)<br /> Danh sách liên kết (linked list)<br /> Ngăn xếp (Stack)<br /> Hàng đợi (Queue)<br /> <br /> 11/22/2016<br /> <br /> 2<br /> <br /> Ngăn xếp - Stack<br /> <br /> 11/22/2016<br /> <br /> 3<br /> <br /> 1<br /> <br /> 11/22/2016<br /> <br /> Khái quát<br /> • Là một dạng danh sách “đặc biệt”: Việc thêm<br /> (phần tử) vào và lấy (phần tử) ra đều làm ở<br /> đỉnh ngăn xếp.<br /> • Để tạo ngăn xếp:<br /> – Có thể dùng Mảng (Sinh viên<br /> tự nghiên cứu, BTVN)<br /> – Có thể dùng danh sách<br /> liên kết<br /> 11/22/2016<br /> <br /> 4<br /> <br /> Các thao tác với ngăn xếp<br /> •<br /> •<br /> •<br /> •<br /> •<br /> •<br /> <br /> Khai báo<br /> Khởi tạo (init)<br /> Kiểm tra ngăn xếp rỗng (isEmpty)<br /> Thêm phần tử vào (push)<br /> Lấy phần tử ra (pop)<br /> Lấy giá trị phần tử trên đỉnh (get)<br /> <br /> 11/22/2016<br /> <br /> 5<br /> <br /> Khai báo<br /> • Cấu trúc dạng bản ghi tự trỏ<br /> <br /> • Khai báo biến<br /> <br /> 11/22/2016<br /> <br /> 6<br /> <br /> 2<br /> <br /> 11/22/2016<br /> <br /> Vấn đề<br /> • Biến mô tả stack là một con trỏ<br /> • Chúng ta mới dùng tham số thực cho hàm<br /> dạng biến thường, và muốn trả về giá trị cho<br /> tham số này thì tham số hình thức cần khai<br /> báo dạng con trỏ hoặc tham chiếu<br /> • Cần truyền tham số thực dạng con trỏ cho<br /> hàm làm thế nào? -> Con trỏ (hoặc tham<br /> chiếu??)<br /> 11/22/2016<br /> <br /> 7<br /> <br /> Hàm với các dạng tham số đầu vào<br /> <br /> Gọi hàm<br /> <br /> Ba cách khai báo tham số<br /> Tham trị<br /> <br /> a, b không đổi<br /> <br /> Con trỏ<br /> <br /> 11/22/2016<br /> <br /> Tham chiếu<br /> <br /> 8<br /> <br /> Khởi tạo<br /> • Khởi tạo giá trị cuối để biết điểm kết thúc của<br /> ngăn xếp ở đâu. Giá trị này thường được chọn<br /> là NULL.<br /> <br /> • Hàm init()<br /> <br /> 11/22/2016<br /> <br /> 9<br /> <br /> 3<br /> <br /> 11/22/2016<br /> <br /> Kiểm tra ngăn xếp rỗng<br /> • Kiểm tra xem đã đến đáy ngăn xếp hay chưa<br /> • Hàm isEmpty()<br /> <br /> 11/22/2016<br /> <br /> 10<br /> <br /> Thêm phần tử vào (push)<br /> • Thêm phần tử vào đỉnh ngăn xếp<br /> • Hàm push()<br /> <br /> 11/22/2016<br /> <br /> 11<br /> <br /> Lấy phần tử ra (pop)<br /> • Lấy ra phần tử ở đỉnh ngăn xếp<br /> • Hàm pop()<br /> <br /> 11/22/2016<br /> <br /> 12<br /> <br /> 4<br /> <br /> 11/22/2016<br /> <br /> Ví dụ 1 - Đảo ngược xâu<br /> • Đảo ngược 1 xâu ký tự, ví dụ đảo ngược<br /> HELLO là OLLEH<br /> • Cách làm:<br /> 1. Lấy từng ký tự của xâu vào theo thứ tự từ trái<br /> qua phải và đẩy (push) vào ngăn xếp.<br /> 2. Lần lượt lấy các ký tự ra khỏi ngăn xếp -> Được<br /> xâu đảo ngược.<br /> <br /> 11/22/2016<br /> <br /> 13<br /> <br /> Ví dụ 1 …<br /> <br /> 11/22/2016<br /> <br /> 14<br /> <br /> Ví dụ 2 - Tính giá trị BT hậu tố<br /> • Biểu thức trung tố:<br /> a+b<br /> a+b*c<br /> • Biểu thức hậu tố:<br /> ab+<br /> abc*+<br /> <br /> 11/22/2016<br /> <br /> 15<br /> <br /> 5<br /> <br />