Bài giảng Cấu trúc dữ liệu và giải thuật: Một số ứng dụng DSLK - Stack

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Một số ứng dụng DSLK: Stack Mô tả stack Một stack là một cấu trúc dữ liệu mà việc thêm vào và loại bỏ được thực hiện tại một đầu (gọi là đỉnh – top của stack). Là một dạng vào sau ra trước – LIFO (Last In First Out) Ví dụ về stack Stack rỗng: Đẩy (push) Q vào: Đẩy A vào: Lấy (pop) ra một => được A: Lấy ra một => được Q và stack rỗng: Q Q A Q A Q Cài đặt ngăn xếp bằng DSLK Phần nhiều giống như DSLK đơn ta đã nghiên cứu. typedef …. DataType; struct Node { DataType Data; Node *Next; }; typedef Node *StackType; Một số phép toán trên ngăn xếp void CreateEmpty(StackType &S): tạo ngăn xếp rỗng int EmptyStack(StackType S): Kiểm tra ngăn xếp có rỗng hay không? int FullStack(StackType S): Kiểm tra ngăn xếp S đầy hay không? (trường hợp ngăn xếp được tạo bằng mảng) void Push(StackType &S, DataType x): Đưa phần tử x vào ngăn xếp S. int Pop(StackType &S, DataType &x): Lấy phần tử đầu của ngăn xếp gán cho x nếu ngăn xếp không rỗng. int Top(StackType S, DataType &x): Lấy phần tử đầu của ngăn xếp gán cho x để xem nếu ngăn xếp không rỗng. Cài đặt ngăn xếp bằng DSLK void CreateEmpty(StackType &S) { S=NULL; } int EmptyStack(StackType S) { return (S==NULL); } Cài đặt ngăn xếp bằng DSLK void Push(StackType &S, DataType x) { StackType temp; temp=new Node; if(temp==NULL) { coutData,x);//Gán x cho vùng Data của Temp temp->Next=S; S=temp; } } Cài đặt ngăn xếp bằng DSLK int Pop(StackType &S, DataType &x) { if(EmptyStack(S)) return 0; else { StackType temp=S; S=S->Next; Gán(x,temp->Data); delete(temp); return 1; } } Cài đặt ngăn xếp bằng DSLK int Top(StackType &S, DataType &x) { if(EmptyStack(S)) return 0; else { Gán(x,S->Data); return 1; } } Ứng dụng Stack Dùng để khử đệ quy Lưu vết trong thuật toán quay lui, vắt cạn. Chuyển đổi, đánh giá các biểu thức toán học (như trong các chương trình Excel, Pascal, C, … như thế nào!?) … Ứng dụng Stack: Đánh gía biểu thức toán học Một biểu thức toán học thông thường được viết theo kí pháp trung tố (toán tử đặt giữa hai toán hạng). Kí pháp nghịch đảo Ba Lan (là biểu thức toán học được viết dưới dạng hậu tố RPN - toán tử đặt sau các toán hạng) Ta ứng dụng ngăn xếp để chuyển biểu thức từ trung tố sang hậu tố, sau đó đánh giá biểu thức hậu tố đó. Ví dụ: Ứng dụng Stack: Chuyển biểu thức từ trung tố sang hậu tố Thuật toán Khởi tạo ngăn xếp rỗng Lặp lại các việc sau cho đến khi dấu kết thúc được đọc Đọc phần tử tiếp theo trong biểu thức trung tố Nếu phần tử là: - Dấu ‘(‘ : đưa nó vào S. - Dấu ‘)’ : Hiển thị các phần tử của S cho đến khi gặp dấu ‘(‘ được đọc (dấu ‘(‘ không hiển thị). - Toán tử: - Nếu S rỗng: Đẩy toán tử vào S.(1) - Ngược lại: - Nếu toán tử có độ ưu tiên cao hơn toán tử ở đỉnh S thì đưa toán tử đó vào S. - Ngược lại: lấy ra và hiển thị toán tử ở đỉnh S quay lại (1). - Toán hạng: Hiển thị nó 3. Khi hết biểu thức thì lấy S ra hiển thị đến khi S rỗng (Độ ưu tiên toán tử ta xem ‘(‘ , ‘+’, ’-’ , ‘*’, ‘/’, ‘%’ : Từ trái sang phải) Ứng dụng Stack: Chuyển biểu thức từ trung tố sang hậu tố Ví dụ: Chuyển biểu thức 7*8-(2+3) sang hậu tố Biểu thức trung tố Stack S Biểu thức hậu tố 7*8-(2+3) *8-(2+3) 8-(2+3) 7 7 7 8 Ứng dụng Stack: Chuyển biểu thức từ trung tố sang hậu tố Ví dụ: Chuyển biểu thức 7*8-(2+3) sang hậu tố Biểu thức trung tố Stack S Biểu thức hậu tố -(2+3) (2+3) 2+3) 7 8 * 7 8 * 7 8 * 2 Ứng dụng Stack: Chuyển biểu thức từ trung tố sang hậu tố Ví dụ: Chuyển biểu thức 7*8-(2+3) sang hậu tố Biểu thức trung tố Stack S Biểu thức hậu tố +3) 3) 7 8 * 2 7 8 * 2 3 Ứng dụng Stack: Chuyển biểu thức từ trung tố sang hậu tố Ví dụ: Chuyển biểu thức 7*8-(2+3) sang hậu tố Biểu thức trung tố Stack S Biểu thức hậu tố ) 7 8 * 2 3 + 7 8 * 2 3 + 7 8 * 2 3 + - Ứng dụng Stack: Đánh giá biểu thức dạng hậu tố Thuật toán Khởi tạo ngăn xếp rỗng 2. Lặp lại công việc sau cho đến khi kết thúc biểu thức - Đọc phần tử tiếp theo trong biểu thức - Nếu phần tử là toán hạng: Đưa nó vào S - Ngược lại (là toán tử) - Lấy từ đỉnh S hai toán hạng - Thực hiện phép toán tử đó với 2 toán hạng theo thứ tự ngược lại. - Đưa kết quả vừa tính trở lại S 3. Kết thúc biểu thức thì giá trị biểu thức là giá trị nút ở đỉnh. Reverse Polish Calculator – Ví dụ Tính toán biểu thức: 3 5 + 2 * = 3 5 Toán tử + Lấy ra 5 và 3 Tính 3 + 5 => 8 3 5 8 Toán tử * Lấy ra 2 và 8 Tính 8 * 2 => 16 8 16 2 2 16