Xem mẫu
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật
Mục lục
Phần I: Mở đầu
I. Giới thiệu đề tài
Trong khoa học máy tính, cấu trúc dữ liệu là cách lưu dữ liệu trong máy
tính sao cho nó có thể được sử dụng một cách hiệu quả. Thông thường, một
cấu trúc dữ liệu được chọn cẩn thận sẽ cho phép thực hiện thuật toán hiệu quả
hơn. Việc chọn cấu trúc dữ liệu thường bắt đầu từ chọn một cấu trúc dữ liệu
trừu tượng. Một cấu trúc dữ liệu được thiết kế tốt cho phép thực hiện nhiều
phép toán, sử dụng càng ít tài nguyên, thời gian xử lý và không gian bộ nhớ càng
tốt. Các cấu trúc dữ liệu được triển khai bằng cách sử dụng các kiểu dữ liệu,
các tham chiếu và các phép toán trên đó được cung cấp bởi một ngôn ngữ
lập trình.
Trong đó nổi trội lên là hai cấu trúc dữ liệu đó là Stack (ngăn xếp) và
Queue (hàng đợi). Stack và Queue có ứng dụng rất nhiều kể cả trong thuật toán
lẫn trong thực tế. Hàng ngày chúng ta thường xuyên làm việc và tiếp xúc với
các biểu thức, toán hạng, toán tử… và máy tính cũng vậy. Tuy nhiên máy tính
không thể nào hiểu được ngôn ngữ và cách viết của con người, vì vậy để máy
tính hiểu được các biểu thức thì chúng ta phải chuyển chúng về một dạng mà
máy tính có thể thực hiện được. Vì vậy em xin chọn đề tài “Ứng dụng ngăn xếp
GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 1
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật
(Stack) và hàng đợi (Queue) để viết chương trình biến đổi biểu thức trung tố
thành tiền tố và hậu tố” để làm bài tiểu luận.
II. Mục đích yêu cầu của đề bài
1. Mục đích
Đề tài này giúp em củng cố, nâng cao kiến thức về môn học cấu trúc dữ
liệu và giải thuật. Từ đó hiểu sâu hơn và vận dụng vào trong các bài toán số
liệu thực tế đồng thời thông qua việc làm đề tài này giúp em biết được các
phương pháp nghiên cứu một vấn đề nhỏ nào đó.
2. Yêu cầu
Dùng ngôn ngữ lập trình C/C++ để cài đặt chương trình. Với dữ liệu
được nhập vào từ bàn phím.
III. Phương pháp nghiên cứu
+ Tham khảo tài liệu: cấu trúc dữ liệu và giải thuật, trên mạng…
+ Tìm hiểu thực tiễn, thực tế, quy cách, nhu cầu của bài toán.
+ Xin ý kiến, hướng dẫn của giáo viên hướng dẫn.
Phần II: Nội dung
I. Ngăn xếp (Stack)
Ngăn xếp (Stack) là một danh sách có thứ tự mà phép chèn và xóa được
thực hiện tại đầu cuối của danh sách và người ta gọi đầu cuối này là
đỉnh (top) của stack. Với nguyên tắc vào sau ra trước, danh sách kiểu
LIFO (last in first out).
Có 2 cách lưu trữ Stack:
GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 2
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật
+ Bằng mảng.
+ Bằng danh sách liên kết.
Các thao tác cơ bản trên Stack:
Push: Đưa một phần tử vào đỉnh của Stack.
Pop: Lấy từ đỉnh của Stack một phần tử.
Peek: Xem đỉnh của Stack chứa nội dung là gì?
Một số ứng dụng của Stack:
Ứng dụng trực tiếp:
Ứng dụng nổi bật của Stack là Stack cho chương trình sử dụng Stack để
gọi hàm.
Trong trình duyệt WEB, các trang đã xem được lưu trong
stack.
Trong trình soạn thảo văn bản, thao tác Undo được lưu
trong stack.
Ứng dụng gián tiếp:
Cấu trúc dữ liệu bổ trợ cho thuật toán khác.
Một thành phần của cấu trúc dữ liệu khác.
II. Hàng đợi (Queue)
Hàng đợi là kiểu danh sách tuyến tính mà phép bổ sung được thực hiện ở
1 đầu, gọi là lối sau (rear) và phép loại bỏ thực hiện ở 1 đầu khác gọi là
lối trước (front). Nguyên tắc vào trước ra trước, danh sách kiểu FIFO
(first in first out).
Có 2 cách lưu trữ tương tự như Stack:
+ Bằng mảng.
GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 3
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật
+ Bằng danh sách liên kết.
Ứng dụng của Queue
Ứng dụng trực tiếp
Danh sách hàng đợi.
Quản lý truy cập tới các tài nguyên dùng chung (ví dụ máy in).
Multiprogramming.
Ứng dụng gián tiếp
Cấu trúc dữ liệu phụ trợ cho các thuật toán.
Một phần của CTDL khác.
III. Ứng dụng của Stack và Queue trong ký pháp Ba Lan
1. Khái niệm:
Prefix: Biểu thức tiền tố được biểu diễn bằng cách đặt toán tử lên trước
các toán hạng. Cách biểu diễn này còn được biết đến với tên gọi “ký pháp Ba
Lan” do nhà toán học Ba Lan Jan Łukasiewicz phát minh năm 1920. Với cách
biểu diễn này, thay vì viết x + y như dạng trung tố, ta sẽ viết + x y. Tùy theo độ
ưu tiên của toán tử mà chúng sẽ được sắp xếp khác nhau, bạn có thể xem một
số ví dụ ở phía sau phần giới thiệu này.
Postfix: Ngược lại với cách Prefix, biểu thức hậu tố tức là các toán tử sẽ
được đặt sau các toán hạng. Cách biểu diễn này được gọi là “ký pháp nghịch
đảo Ba Lan” hoặc được viết tắt là RPN(Reverse Polish notation), được phát
minh vào khoảng giữa thập kỷ 1950 bởi một triết học gia và nhà khoa học máy
tính Charles Hamblin người Úc.
GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 4
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật
Ví dụ:
2. Chuyển đổi dạng Infix(trung tố) sang Postfix(hậu tố)
Thuật toán:
Bước 1: Đọc một thành phần của biểu thức E (dạng Infix biểu diễn
bằng xâu, đọc từ trái qua phải). Giả sử thành phần đọc được là x
Bước 1.1: Nếu x là toán hạng thì viết nó vào bên phải biểu thức E1
(xâu lưu
kết quả của Postfix)
Bước 1.2: Nếu x là dấu ‘(’ thì đẩy nó vào Stack.
Bước 1.3: Nếu x là một trong các phép toán +, , *, / thì
Bước 1.3.1: Xét phần tử y ở đỉnh Stack.
Bước 1.3.2: Nếu Pri(y) >= Pri(x) là một phép toán thì loại y ra
khỏi Stack và viết y vào bên phải của E1 và quay lại bước 1.3.1
Bước 1.3.3: Nếu Pri(y) < Pri(x) thì đẩy x vào Stack.
Bước 1.4: Nếu x là dấu ‘)’ thì
Bước 1.4.1: Xét phần tử y ở đầu của Stack.
Bước 1.4.2: y là phép toán thì loại y ra khỏi Stack, viết y vào bên
phải E1 và quay trở lại 1.4.1
...
- tailieumienphi.vn
nguon tai.lieu . vn