11/22/2016

Kỹ thuật lập trình

Tuần 12 - Ngăn xếp & Hàng đợi

Giáo viên: Hà Đại Dương duonghd@mta.edu.vn

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

1

11/22/2016

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

2

11/22/2016

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??)

Hàm với các dạng tham số đầu vào

Gọi hàm

11/22/2016 7

Ba cách khai báo tham số

Tham trị

a, b không đổi

Con trỏ

Tham chiếu

11/22/2016 8

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

3

11/22/2016

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

4

11/22/2016

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

5

11/22/2016

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

6

11/22/2016

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

7

11/22/2016

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

8

11/22/2016

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

9

11/22/2016

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

10

11/22/2016

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

11/22/2016

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

12

11/22/2016

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

13

11/22/2016

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

14

11/22/2016

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

15