Bài giảng Cấu trúc dữ liệu và thuật toán: Stacks

Cấu trúc dữ liệu và thuật toán Stacks Stacks • Stacks là một dạng danh sách (mảng) đặc biệt với ngữ cảnh LIFO • Hai phép toán • int push( Stack s, void *item ); - Bổ xung một phần tử vào đỉnh của stack • void *pop( Stack s ); - Loại bỏ một phần tử từ đỉnh của stack • Tương tự như một máy xếp đĩa • Các phép toán khác int IsEmpty( Stack s ); /* Return TRUE if empty */ void *Top( Stack s ); /* Return the item at the top, without deleting it */ Stacks – Thủ tục • Mảng (Arrays) • Cung cấp một stack với sức chứa giới hạn • Hạn chế về độ mềm dẻo nhưng đáp ứng được nhiều ứng dụng thực tế • Giới hạn về sức chứa bởi một vài ràng buộc • Bộ nhớ trong máy tính của bạn • Kích cỡ của máy xếp đĩa, etc • Phép toán push, pop • Các biến của AddToC…, DeleteFromC… • Danh sách liên kết cũng được sử dụng • Stack: • Về cơ bản là một danh sách liên kết với ngữ nghĩa đặc biệt! Stacks – một số vấn đề liên quan • Stacks trong chương trình tin học • Là khóa để call / return trong functions & procedures • Khuôn dạng Stack cho phép các lời gọi đệ qui • Call: push stack frame • Return: pop stack frame • Khuôn dạng Stack • Các tham số của Function • Return địa chỉ • Các biến cục bộ (Local variables) Ví dụ: Phương thức trao đổi dữ liệu • C dùng 1 stack để lưu trữ các biến cục bộ và các chuyển các tham số cho hàm với mỗi lần gọi hàm thực hiện Hàm gọi (O) cất các tham số vào stack. Gọi thực hiện hàm được gọi (F). F nhận lấy các tham số từ stack F tạo các biến cục bộ ứng với các tham số trên stack Khi kết thúc, F cập nhật giá trị các tham số (ref) và trả điều khiển cho O O nhận lấy các giá trị mới của tham số cũng như giá trị trả về #include double power(int, int); int main(void) { int x = 2; double d; d = power(x, 5); printf("%lf\n", d); return 0; } double power(int n, int p) { double result = n; while(--p > 0) result *= n; return result; } main: x2 main: d? power: p5 power: n2 power: result32.0 Phương thức trao đổi dữ liệu 32.0 Stack Frames - Functions in HLL • Program function f( int x, int y) { int a; if ( term_cond ) return …; a = ….; return g( a ); } function g( int z ) { int p, q; p = …. ; q = …. ; return f(p,q); } Context for execution of f Đệ qui • Là công nghệ rất hữu ích • Định nghĩa các hàm toán học • Định nghĩa cấu trúc dữ liệu • Các cấu trúc đệ qui được sử lý tự nhiên bởi các hàm đệ qui! Đệ qui • Là công nghệ rất hữu ích • Định nghĩa các hàm toán học • Định nghĩa cấu trúc dữ liệu • Các cấu trúc đệ qui được sử lý tự nhiên bởi các hàm đệ qui! • Các hàm định nghĩa đệ qui • factorial • Fibonacci • GCD bởi thuật toán Euclid • Biến đổi Fourier • Trò chơi • Tháp Hanoi (Towers of Hanoi) • Cờ (Chess) Đệ qui – Ví dụ • Dãy số (Fibonacci) fib( n ) = if ( n = 0 ) then 1 else if ( n = 1 ) then 1 else fib(n-1) + fib(n-2) int fib( n ) { if ( n < 2 ) return 1; else return fib(n-1) + fib(n-2); } Mã giả (Pseudo-code) C Giải pháp đơn giản, dễ hiểu (Simple, elegant solution!) Đệ qui – Ví dụ • Dãy số Fibonacci int fib( n ) { if ( n < 2 ) return 1; else return fib(n-1) + fib(n-2); } C Nhưng , trong Fibona cci, th ời gian chạy t ồi!!!! Tuy nhiên, nhiều hàm đệ qui khác, VD tìm kiếm nhị phân, rất đơn giản, rõ ràng và hiệu quả!