際際滷

際際滷Share a Scribd company logo

Bai5 dsachlket

H畛 L畛i
H畛 L畛i
1 of 18
Download to read offline
C畉u tr炭c d畛 li畛u v Thu畉t to叩n Danh s叩ch li棚n k畉t Stacks
Gi畛i h畉n c畛a m畉ng M畉ng (Arrays) 董n gi畉n, Nhanh nh動ng Ph畉i ch畛 畛nh m畛t k鱈ch th動畛c c畛 th畛 t畉i th畛i i畛m x但y d畛ng m畉ng Tu但n th畛 Lu畉t 畉y (Murphy) X但y d畛ng m畛t m畉ng v畛i kh担ng gian cho n bi畉n n = 働畛c l動畛ng ch鱈nh ch畉n c畛a b畉n v畛 s畛 l動畛ng bi畉n s畉 s畛 d畛ng l畛n nh畉t Ngy mai, b畉n c坦 th畛 c畉n n+1 bi畉n Li畛u c坦 th畛 c坦 m畛t h畛 th畛ng m畛m d畉o h董n?
Danh s叩ch li棚n k畉t S畛 d畛ng kh担ng gian bi畉n m畛m d畉o C畉p ph叩t kh担ng gian 畛ng cho t畛ng ph畉n t畛 theo y棚u c畉u c畛a bi to叩n G畉n m畛t con tr畛 ch畛 t畛i gi叩 tr畛 ph畉n t畛 k畉 ti畉p Danh s叩ch li棚n k畉t M畛i n炭t (node) c畛a danh s叩ch bao g畛m Gi叩 tr畛 kh坦a c畛a ph畉n t畛 trong n炭t Con tr畛 ch畛 畉n node k畉 ti畉p Data Next object
Danh s叩ch li棚n k畉t C畉u tr炭c danh s叩ch li棚n k畉t ch畛a m畛t con tr畛 tai 畉u danh s叩ch: head N坦 動畛c kh畛i t畉o = NULL Head Danh s叩ch li棚n k畉t
Danh s叩ch li棚n k畉t C畉u tr炭c danh s叩ch li棚n k畉t ch畛a m畛t con tr畛 tai 畉u danh s叩ch: head N坦 動畛c kh畛i t畉o = NULL B畛 xung ph畉n t畛 畉u ti棚n C畉p ph叩t kh担ng gian v湛ng nh畛 cho node Thi畉t l畉p gi叩 tr畛 d畛 li畛u 畛ng v畛i 畛i t動畛ng c畉n m担 t畉 Thi畉t l畉p Next 畉n NULL Thi畉t l畉p Head 畛 tr畛 畉n node m畛i Data Next object Head Collection node
Danh s叩ch li棚n k畉t B畛 xung ph畉n t畛 th畛 hai C畉p ph叩t kh担ng gian v湛ng nh畛 cho node Thi畉t l畉p gi叩 tr畛 d畛 li畛u 畛ng v畛i 畛i t動畛ng c畉n m担 t畉 Thi畉t l畉p Next tr畛 畉n v畛 tr鱈 Head hi畛n t畉i tr畛 畉n Thi畉t l畉p Head tr畛 畉n node m畛i Data Next object Head Danh s叩ch li棚n k畉t node Data Next object2 node
Danh s叩ch li棚n k畉t - Th畛 t畛c b畛 xung Add Th畛 t畛c b畛 xung struct t_node { void *item; struct t_node *next; } node; typedef struct t_node *Node; struct collection { Node head; }; int AddToCollection( Collection c, void *item ) { Node new = malloc( sizeof( struct t_node ) ); new->item = item; new->next = c->head; c->head = new; return TRUE; }
Danh s叩ch li棚n k畉t - Th畛 t畛c b畛 xung Add Th畛 t畛c b畛 xung struct t_node { void *item; struct t_node *next; } node; typedef struct t_node *Node; struct collection { Node head; }; int AddToCollection( Collection c, void *item ) { Node new = malloc( sizeof( struct t_node ) ); new->item = item; new->next = c->head; c->head = new; return TRUE; } 畛nh ngh挑a ki畛u 畛 qui - C c畉p ph叩t v湛ng nh畛! Ki畛m tra l畛i, ch竪n th棚m m畛t d嘆ng l畛nh 畛 k tra!
Danh s叩ch li棚n k畉t Th畛i gian b畛 xung H畉ng s畛 - 畛c l畉p v畛i n Th畛i gian t狸m ki畉m Tr動畛ng h畛p t畛i nh畉t - n Data Next object Head Danh s叩ch li棚n k畉t node Data Next object2 node
Danh s叩ch li棚n k畉t Th畛 t畛c Find Th畛 t畛c void *FindinCollection( Collection c, void *key ) { Node n = c->head; while ( n != NULL ) { if ( KeyCmp( ItemKey( n->item ), key ) == 0 ) { return n->item; n = n->next; } return NULL; } M畛t th畛 t畛c 畛 qui c滴ng c坦 th畛 s畛 d畛ng!
Danh s叩ch li棚n k畉t Th畛 t畛c Delete Th畛 t畛c void *DeleteFromCollection( Collection c, void *key ) { Node n, prev; n = prev = c->head; while ( n != NULL ) { if ( KeyCmp( ItemKey( n->item ), key ) == 0 ) { prev->next = n->next; return n; } prev = n; n = n->next; } return NULL; } head
Danh s叩ch li棚n k畉t Th畛 t畛c Delete Th畛 t畛c void *DeleteFromCollection( Collection c, void *key ) { Node n, prev; n = prev = c->head; while ( n != NULL ) { if ( KeyCmp( ItemKey( n->item ), key ) == 0 ) { prev->next = n->next; return n; } prev = n; n = n->next; } return NULL; } head C畉n b畛 xung th棚m m畛t s畛 l畛nh 畛 x坦a ph畉n t畛! Bi t但p!
Danh s叩ch li棚n k畉t - LIFO v FIFO Th畛 t畛c B畛 xung t畉i 畉u danh s叩ch (head) Last-In-First-Out (LIFO) semantics Hi畛u ch畛nh First-In-First-Out (FIFO) Gi畛 con tr畛 u担i tail struct t_node { void *item; struct t_node *next; } node; typedef struct t_node *Node; struct collection { Node head, tail; }; tail 動畛c thi棚t l畉p trong AddToCollection N畉u head == NULL head tail
Danh s叩ch li棚n k畉t Li棚n k畉t k辿p Danh s叩ch li棚n k畉t k辿p C坦 th畛 tr畛 c畉 hai h動畛ng struct t_node { void *item; struct t_node *prev, *next; } node; typedef struct t_node *Node; struct collection { Node head, tail; }; head tail prev prev prev
Stacks Stacks l m畛t d畉ng danh s叩ch (m畉ng) 畉c bi畛t v畛i ng畛 c畉nh LIFO Hai ph動董ng ph叩p 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動董ng ph叩p 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動董ng ph叩p 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)
Stacks Th畛 t畛c struct t_node { void *item; struct t_node *prev, *next; } node; typedef struct t_node *Node; struct collection { Node head, tail; }; head tail prev prev prev prev kh担ng b畉t bu畛c!

More Related Content

Bai5 dsachlket

  • 1. C畉u tr炭c d畛 li畛u v Thu畉t to叩n Danh s叩ch li棚n k畉t Stacks
  • 2. Gi畛i h畉n c畛a m畉ng M畉ng (Arrays) 董n gi畉n, Nhanh nh動ng Ph畉i ch畛 畛nh m畛t k鱈ch th動畛c c畛 th畛 t畉i th畛i i畛m x但y d畛ng m畉ng Tu但n th畛 Lu畉t 畉y (Murphy) X但y d畛ng m畛t m畉ng v畛i kh担ng gian cho n bi畉n n = 働畛c l動畛ng ch鱈nh ch畉n c畛a b畉n v畛 s畛 l動畛ng bi畉n s畉 s畛 d畛ng l畛n nh畉t Ngy mai, b畉n c坦 th畛 c畉n n+1 bi畉n Li畛u c坦 th畛 c坦 m畛t h畛 th畛ng m畛m d畉o h董n?
  • 3. Danh s叩ch li棚n k畉t S畛 d畛ng kh担ng gian bi畉n m畛m d畉o C畉p ph叩t kh担ng gian 畛ng cho t畛ng ph畉n t畛 theo y棚u c畉u c畛a bi to叩n G畉n m畛t con tr畛 ch畛 t畛i gi叩 tr畛 ph畉n t畛 k畉 ti畉p Danh s叩ch li棚n k畉t M畛i n炭t (node) c畛a danh s叩ch bao g畛m Gi叩 tr畛 kh坦a c畛a ph畉n t畛 trong n炭t Con tr畛 ch畛 畉n node k畉 ti畉p Data Next object
  • 4. Danh s叩ch li棚n k畉t C畉u tr炭c danh s叩ch li棚n k畉t ch畛a m畛t con tr畛 tai 畉u danh s叩ch: head N坦 動畛c kh畛i t畉o = NULL Head Danh s叩ch li棚n k畉t
  • 5. Danh s叩ch li棚n k畉t C畉u tr炭c danh s叩ch li棚n k畉t ch畛a m畛t con tr畛 tai 畉u danh s叩ch: head N坦 動畛c kh畛i t畉o = NULL B畛 xung ph畉n t畛 畉u ti棚n C畉p ph叩t kh担ng gian v湛ng nh畛 cho node Thi畉t l畉p gi叩 tr畛 d畛 li畛u 畛ng v畛i 畛i t動畛ng c畉n m担 t畉 Thi畉t l畉p Next 畉n NULL Thi畉t l畉p Head 畛 tr畛 畉n node m畛i Data Next object Head Collection node
  • 6. Danh s叩ch li棚n k畉t B畛 xung ph畉n t畛 th畛 hai C畉p ph叩t kh担ng gian v湛ng nh畛 cho node Thi畉t l畉p gi叩 tr畛 d畛 li畛u 畛ng v畛i 畛i t動畛ng c畉n m担 t畉 Thi畉t l畉p Next tr畛 畉n v畛 tr鱈 Head hi畛n t畉i tr畛 畉n Thi畉t l畉p Head tr畛 畉n node m畛i Data Next object Head Danh s叩ch li棚n k畉t node Data Next object2 node
  • 7. Danh s叩ch li棚n k畉t - Th畛 t畛c b畛 xung Add Th畛 t畛c b畛 xung struct t_node { void *item; struct t_node *next; } node; typedef struct t_node *Node; struct collection { Node head; }; int AddToCollection( Collection c, void *item ) { Node new = malloc( sizeof( struct t_node ) ); new->item = item; new->next = c->head; c->head = new; return TRUE; }
  • 8. Danh s叩ch li棚n k畉t - Th畛 t畛c b畛 xung Add Th畛 t畛c b畛 xung struct t_node { void *item; struct t_node *next; } node; typedef struct t_node *Node; struct collection { Node head; }; int AddToCollection( Collection c, void *item ) { Node new = malloc( sizeof( struct t_node ) ); new->item = item; new->next = c->head; c->head = new; return TRUE; } 畛nh ngh挑a ki畛u 畛 qui - C c畉p ph叩t v湛ng nh畛! Ki畛m tra l畛i, ch竪n th棚m m畛t d嘆ng l畛nh 畛 k tra!
  • 9. Danh s叩ch li棚n k畉t Th畛i gian b畛 xung H畉ng s畛 - 畛c l畉p v畛i n Th畛i gian t狸m ki畉m Tr動畛ng h畛p t畛i nh畉t - n Data Next object Head Danh s叩ch li棚n k畉t node Data Next object2 node
  • 10. Danh s叩ch li棚n k畉t Th畛 t畛c Find Th畛 t畛c void *FindinCollection( Collection c, void *key ) { Node n = c->head; while ( n != NULL ) { if ( KeyCmp( ItemKey( n->item ), key ) == 0 ) { return n->item; n = n->next; } return NULL; } M畛t th畛 t畛c 畛 qui c滴ng c坦 th畛 s畛 d畛ng!
  • 11. Danh s叩ch li棚n k畉t Th畛 t畛c Delete Th畛 t畛c void *DeleteFromCollection( Collection c, void *key ) { Node n, prev; n = prev = c->head; while ( n != NULL ) { if ( KeyCmp( ItemKey( n->item ), key ) == 0 ) { prev->next = n->next; return n; } prev = n; n = n->next; } return NULL; } head
  • 12. Danh s叩ch li棚n k畉t Th畛 t畛c Delete Th畛 t畛c void *DeleteFromCollection( Collection c, void *key ) { Node n, prev; n = prev = c->head; while ( n != NULL ) { if ( KeyCmp( ItemKey( n->item ), key ) == 0 ) { prev->next = n->next; return n; } prev = n; n = n->next; } return NULL; } head C畉n b畛 xung th棚m m畛t s畛 l畛nh 畛 x坦a ph畉n t畛! Bi t但p!
  • 13. Danh s叩ch li棚n k畉t - LIFO v FIFO Th畛 t畛c B畛 xung t畉i 畉u danh s叩ch (head) Last-In-First-Out (LIFO) semantics Hi畛u ch畛nh First-In-First-Out (FIFO) Gi畛 con tr畛 u担i tail struct t_node { void *item; struct t_node *next; } node; typedef struct t_node *Node; struct collection { Node head, tail; }; tail 動畛c thi棚t l畉p trong AddToCollection N畉u head == NULL head tail
  • 14. Danh s叩ch li棚n k畉t Li棚n k畉t k辿p Danh s叩ch li棚n k畉t k辿p C坦 th畛 tr畛 c畉 hai h動畛ng struct t_node { void *item; struct t_node *prev, *next; } node; typedef struct t_node *Node; struct collection { Node head, tail; }; head tail prev prev prev
  • 15. Stacks Stacks l m畛t d畉ng danh s叩ch (m畉ng) 畉c bi畛t v畛i ng畛 c畉nh LIFO Hai ph動董ng ph叩p 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動董ng ph叩p kh叩c int IsEmpty( Stack s ); /* Return TRUE if empty */ void *Top( Stack s ); /* Return the item at the top, without deleting it */
  • 16. 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動董ng ph叩p 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!
  • 17. 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)
  • 18. Stacks Th畛 t畛c struct t_node { void *item; struct t_node *prev, *next; } node; typedef struct t_node *Node; struct collection { Node head, tail; }; head tail prev prev prev prev kh担ng b畉t bu畛c!