際際滷

際際滷Share a Scribd company logo

Bai6 stacks

H畛 L畛i
H畛 L畛i
1 of 11
Download to read offline
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畛 vo 畛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 vi rng 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 hm v畛i m畛i l畉n g畛i hm th畛c hi畛n Hm g畛i (O) c畉t c叩c tham s畛 vo stack. G畛i th畛c hi畛n hm 動畛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 <stdio.h> double power(int, int); int main(void) { int x = 2; double d; d = power(x, 5); printf("%lfn", 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 hm 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 hm 畛 qui!
畛 qui L c担ng ngh畛 r畉t h畛u 鱈ch 畛nh ngh挑a c叩c hm 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 hm 畛 qui! C叩c hm 畛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 Fibonacci, th畛i gian ch畉y t畛i!!!! Tuy nhi棚n, nhi畛u hm 畛 qui kh叩c, VD t狸m ki畉m nh畛 ph但n, r畉t 董n gi畉n, r探 rng v hi畛u qu畉!

More Related Content

Bai6 stacks

  • 1. C畉u tr炭c d畛 li畛u v thu畉t to叩n Stacks
  • 2. 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畛 vo 畛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 */
  • 3. 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 vi rng 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!
  • 4. 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)
  • 5. 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 hm v畛i m畛i l畉n g畛i hm th畛c hi畛n Hm g畛i (O) c畉t c叩c tham s畛 vo stack. G畛i th畛c hi畛n hm 動畛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畛
  • 6. #include <stdio.h> double power(int, int); int main(void) { int x = 2; double d; d = power(x, 5); printf("%lfn", 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
  • 7. 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
  • 8. 畛 qui L c担ng ngh畛 r畉t h畛u 鱈ch 畛nh ngh挑a c叩c hm 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 hm 畛 qui!
  • 9. 畛 qui L c担ng ngh畛 r畉t h畛u 鱈ch 畛nh ngh挑a c叩c hm 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 hm 畛 qui! C叩c hm 畛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)
  • 10. 畛 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!)
  • 11. 畛 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 Fibonacci, th畛i gian ch畉y t畛i!!!! Tuy nhi棚n, nhi畛u hm 畛 qui kh叩c, VD t狸m ki畉m nh畛 ph但n, r畉t 董n gi畉n, r探 rng v hi畛u qu畉!