際際滷

際際滷Share a Scribd company logo

Ctdl C06

Download as PPT, PDF
giang
giang
1 of 38
C畉U TRC D畛 LI畛U V GI畉I THU畉T Ch動董ng 6: Danh s叩ch v chu畛i
Danh s叩ch tr畛u t動畛ng M畛t danh s叩ch (list) ki畛u T M畛t d達y h畛u h畉n ki畛u T M畛t s畛 t叩c v畛: 1. Kh畛i t畉o danh s叩ch r畛ng ( create ) 2. Ki畛m tra r畛ng ( empty ) 3. Ki畛m tra 畉y ( full ) 4. T鱈nh k鱈ch th動畛c ( size ) 5. X坦a r畛ng danh s叩ch ( clear ) 6. Th棚m m畛t gi叩 tr畛 vo danh s叩ch t畉i m畛t v鱈 tr鱈 c畛 th畛 ( insert ) 7. L畉y m畛t gi叩 tr畛 t畉i m畛t v畛 tr鱈 c畛 th畛 ra kh畛i danh s叩ch ( remove ) 8. Nh畉n v畛 gi叩 tr畛 t畉i m畛t v畛 tr鱈 c畛 th畛 ( retrieve ) 9. Thay th畉 m畛t gi叩 tr畛 t畉i m畛t v畛 tr鱈 c畛 th畛 ( replace ) 10. Duy畛t danh s叩ch v thi hnh m畛t t叩c v畛 t畉i m畛i v畛 tr鱈 ( traverse )
Thi畉t k畉 c叩c ph動董ng th畛c
Ch畛 s畛 c叩c ph畉n t畛 叩nh ch畛 s畛 m畛t danh s叩ch c坦 n ph畉n t畛: 叩nh ch畛 s畛 t畛 0, 1, c叩c ph畉n t畛 V鱈 d畛: a 0 , a 1 , a 2 , , a n-1 Ph畉n t畛 a idx 畛ng sau a idx-1 v tr動畛c a idx+1 (n畉u c坦) D湛ng ch畛 s畛: T狸m th畉y m畛t ph畉n t畛, tr畉 v畛 v畛 tr鱈 (ch畛 s畛) c畛a n坦. Th棚m vo m畛t ph畉n t畛 t畉i v畛 tr鱈 idx th狸 ch畛 s畛 c叩c ph畉n t畛 c滴 t畛 idx tr畛 v畛 sau 畛u tng l棚n 1. Ch畛 s畛 ny 動畛c d湛ng b畉t k畛 danh s叩ch 動畛c hi畛n th畛c th畉 no 畛 c畉p v畉t l箪.
Ph動董ng th畛c insert v remove
Ph動董ng th畛c retrieve v replace
Ph動董ng th畛c traverse v tham s畛 hm void print_int( int &x) { cout << x << ; } void increase_int( int &x) { x++; } void main() { List< int > alist; alist.traverse(print_int); alist.traverse(increase_int); } Khi g畛i tham s畛 hm, ch動董ng tr狸nh d畛ch ph畉i nh狸n th畉y hm 動畛c g畛i. T湛y theo m畛c 鱈ch m g畛i c叩c hm kh叩c nhau.
Hi畛n th畛c danh s叩ch li棚n t畛c template < class List_entry> class List { public: // methods of the List ADT List( ) ; int size( ) const; bool full( ) const; bool empty( ) const; void clear( ) ; void traverse( void (*visit)(List_entry &)) ; Error_code retrieve( int position , List_entry &x) const; Error_code replace( int position , const List_entry &x) ; Error_code remove( int position , List_entry &x) ; Error_code insert( int position , const List_entry &x) ; protected: // data members for a contiguous list implementation int count ; List_entry entry[max_list] ; } ;
Th棚m vo m畛t danh s叩ch li棚n t畛c insert(3, z) d e f g h d e f g h z count=8 count=9 a b c 0 1 2 3 4 5 6 7 8 9
Gi畉i thu畉t th棚m vo m畛t danh s叩ch li棚n t畛c Algorithm Insert Input : position l v畛 tr鱈 c畉n th棚m vo, x l gi叩 tr畛 c畉n th棚m vo Output : danh s叩ch 達 th棚m vo x 1. if list 畉y 1.1. return overflow 2. if position n畉m ngoi kho畉ng [0..count] 2.1. return range_error //D畛i t畉t c畉 c叩c ph畉n t畛 t畛 position v畛 sau 1 v畛 tr鱈 3. for index = count-1 down to position 3.1. entry[index+1] = entry[index] 4. entry[position] = x //G叩n x vo v畛 tr鱈 position 5. count++ //Tng s畛 ph畉n t畛 l棚n 1 6. return success; End Insert
M達 C++ th棚m vo m畛t danh s叩ch li棚n t畛c template < class List_entry> Error_code List<List_entry> :: insert( int position , const List_entry &x) { if (full( )) return overflow ; if (position < 0 || position > count) return range_error ; for ( int i = count 1 ; i >= position ; i) entry[i + 1] = entry[i] ; entry[position] = x ; count++; return success ; }
X坦a t畛 m畛t danh s叩ch li棚n t畛c x remove(3, x) d e f g h d e f g h count=8 count=7 a b c 0 1 2 3 4 5 6 7 8 9
Gi畉i thu畉t x坦a t畛 m畛t danh s叩ch li棚n t畛c Algorithm Remove Input : position l v畛 tr鱈 c畉n x坦a b畛, x l gi叩 tr畛 l畉y ra 動畛c Output : danh s叩ch 達 x坦a b畛 ph畉n t畛 t畉i position 1. if list r畛ng 1.1. return underflow 2. if position n畉m ngoi kho畉ng [0..count-1] 2.1. return range_error 3. x = entry[position] //L畉y x t畉i v畛 tr鱈 position ra 4. count-- //Gi畉m s畛 ph畉n t畛 i 1 //D畛i t畉t c畉 c叩c ph畉n t畛 t畛 position v畛 tr動畛c 1 v畛 tr鱈 5. for index = position to count-1 5.1. entry[index] = entry[index+1] 6. return success; End Remove
Gi畉i thu畉t duy畛t m畛t danh s叩ch li棚n t畛c Algorithm Traverse Input : hm visit d湛ng 畛 t叩c 畛ng vo t畛ng ph畉n t畛 Output : danh s叩ch 動畛c c畉p nh畉t b畉ng hm visit //Qu辿t qua t畉t c畉 c叩c ph畉n t畛 trong list 1. for index = 0 to count-1 1.1. Thi hnh hm visit 畛 duy畛t ph畉n t畛 entry[index] End Traverse
M達 C++ duy畛t m畛t danh s叩ch li棚n t畛c template < class List_entry> void List<List_entry> :: traverse( void (*visit)(List_entry &)) / * Post: T叩c v畛 cho b畛i hm visit s畉 動畛c thi hnh t畉i m畛i thnh ph畉n c畛a list b畉t 畉u t畛 v畛 tr鱈 0 tr畛 i. * / { for ( int i = 0 ; i < count ; i++) (*visit)(entry[i]) ; }
Danh s叩ch li棚n k畉t 董n (DSLK 董n)
Hi畛n th畛c DSLK 董n template < class List_entry> class List { public: // Specifications for the methods of the list ADT go here. // The following methods replace compiler-generated defaults. List( ) ; ~List( ); List( const List<List_entry> &copy) ; void operator = ( const List<List_entry> &copy) ; protected: // Data members for the linked list implementation now follow. int count ; Node<List_entry> * head ; // The following auxiliary function is used to locate list positions Node<List_entry> *set_position( int position) const; } ;
T狸m v畛 tr鱈 tr棚n DSLK 董n Nhu c畉u: Nh畉p vo ch畛 s畛 c畛a m畛t ph畉n t畛 Cho bi畉t 坦 l ph畉n t畛 no (con tr畛 ch畛 畉n ph畉n t畛) t動畛ng: B畉t 畉u t畛 ph畉n t畛 畉u ti棚n Di chuy畛n 炭ng position b動畛c th狸 畉n 動畛c ph畉n t畛 c畉n t狸m Ph畉i 畉m b畉o l position n畉m trong kho畉ng [0..count-1]
Gi畉i thu畉t t狸m v畛 tr鱈 tr棚n DSLK 董n Algorithm Set position Input : position l v畛 tr鱈 c畉n t狸m Output : con tr畛 ch畛 畉n ph畉n t畛 t畉i v畛 tr鱈 c畉n t狸m 1. set q to head 2. for index =0 to position //Thi hnh position b動畛c 2.1. advance q to the next element //Tr畛 q 畉n ph畉n t畛 k畉 ti畉p 3. return q End Set position index=0 set_position(2) index=1 index=2 q x y z head m
M達 C++ t狸m v畛 tr鱈 tr棚n DSLK 董n template < class List_entry> Node<List_entry> *List<List_entry> :: set_position( int position) const / * Pre: position l v畛 tr鱈 h畛p l畛 trong list, 0 < position < count. Post: Tr畉 v畛 m畛t con tr畛 ch畛 畉n Node ang 畛 v畛 tr鱈 position */ { Node<List_entry> *q = head ; for ( int i = 0 ; i < position ; i++) q = q->next ; return q ; }
Th棚m vo m畛t DSLK 董n new_node a y following_node ph畉n t畛 t畉i v畛 tr鱈 position x previous_node ph畉n t畛 t畉i v畛 tr鱈 position-1 b但y gi畛, ph畉n t畛 ny c坦 v畛 tr鱈 position b但y gi畛, ph畉n t畛 ny c坦 v畛 tr鱈 position+1
Gi畉i thu畉t th棚m vo m畛t DSLK 董n Algorithm Insert Input: position l v畛 tr鱈 th棚m vo, x l gi叩 tr畛 th棚m vo Output: danh s叩ch 達 th棚m vo x t畉i v畛 tr鱈 position 1. N畉u position > 0 1.1. Tr畛 previous 畉n ph畉n t畛 t畉i v畛 tr鱈 position-1 1.2. Tr畛 following 畉n ph畉n t畛 sau previous 2. Ng動畛c l畉i 2.1. Tr畛 following 畉n head 3. T畉o ra node m畛i l new_node v畛i gi叩 tr畛 x 4. Tr畛 next c畛a new_node 畉n following 5. N畉u position l 0 5.1. Tr畛 head 畉n new_node 6. Ng動畛c l畉i 6.1. Tr畛 next c畛a previous 畉n new_node 7. Tng s畛 l動畛ng c叩c ph畉n t畛 l棚n 1 End Insert
M達 C++ th棚m vo m畛t DSLK 董n template < class List_entry> Error_code List<List_entry> :: insert( int position , const List_entry &x) { if (position < 0 || position > count) return range_error ; Node<List_entry> *new_node , *previous , *following ; if (position > 0) { previous = set_position(position 1) ; following = previous->next ; } else following = head ; new_node = new Node<List_entry>(x , following) ; if (new_node == NULL) return overflow ; if (position == 0) head = new_node ; else previous->next = new_node ; count++ ; return success ; }
X坦a b畛 t畛 m畛t DSLK 董n b但y gi畛, ph畉n t畛 ny c坦 v畛 tr鱈 position ph畉n t畛 t畉i v畛 tr鱈 position ph畉n t畛 t畉i v畛 tr鱈 position+1 x z previous_node ph畉n t畛 t畉i v畛 tr鱈 position-1 y following_node
DSLK k辿p (Doubly linked list)
畛nh ngh挑a DSLK k辿p template < class List_entry> class List { public: // Add specications for methods of the list ADT. // Add methods to replace compiler generated defaults. protected: // Data members for the doubly-linked list implementation follow: int count ; mutable int current_position ; mutable Node<List_entry> *current ; // The auxiliary function to locate list positions follows: void set_position( int position) const; } ; C叩c hm h畉ng ( const ) c坦 th畛 thay 畛i gi叩 tr畛 c畛a c叩c bi畉n mutable ny
畛nh ngh挑a Node cho DSLK k辿p template < class Node_entry> struct Node { // data members Node_entry entry ; Node<Node_entry> *next ; Node<Node_entry> *back ; // constructors Node( ) ; Node(Node_entry , Node<Node_entry> *link_back = NULL , Node<Node_entry> *link_next = NULL) ; } ; z
T狸m v畛 tr鱈 trong DSLK k辿p set_position(6) set_position(8) x y z m current current_position position = 5 position = 6 position = 7 position = 8
Th棚m vo trong DSLK k辿p current previous following new_node x y z ph畉n t畛 t畉i v畛 tr鱈 position-1 ph畉n t畛 t畉i v畛 tr鱈 position ph畉n t畛 ny b但y gi畛 c坦 v畛 tr鱈 l position ph畉n t畛 ny b但y gi畛 c坦 v畛 tr鱈 l position+1
Th棚m vo trong DSLK k辿p Algorithm Insert Input: x l gi叩 tr畛 c畉n th棚m vo t畉i position (0<=position<=count) Output : danh s叩ch 達 th棚m gi叩 tr畛 x vo v畛 tr鱈 position 1. if position l 0 1.1. if s畛 ph畉n t畛 l 0 1.1.1. Tr畛 following 畉n NULL 1.2. Tr畛 preceding 畉n NULL 2. else 2.1. Tr畛 preceding 畉n v畛 tr鱈 position -1, following 畉n v畛 tr鱈 position 3. T畉o ra ph畉n t畛 m畛i new_node 4. Tr畛 next v back c畛a new_node 畉n following v preceding 5. if preceding kh叩c r畛ng 5.1. Tr畛 next c畛a preceding 畉n new_node 6. if following kh叩c r畛ng 6.1. Tr畛 back c畛a following 畉n new_node 7. Tng s畛 ph畉n t畛 l棚n 1 End Insert
M達 C++ th棚m vo trong DSLK k辿p template < class List_entry> Error_code List<List_entry> :: insert( int position , const List_entry &x) { Node<List_entry> *new node , *following , *preceding ; if (position < 0 || position > count) return range_error ; if (position == 0) { if (count == 0) following = NULL ; else { set_position(0) ; following = current ; } preceding = NULL ; } else { set_position(position 1) ; preceding = current ; following = preceding->next ; } new_node = new Node<List_entry>(x , preceding , following) ; if (new_node == NULL) return overflow ; if (preceding != NULL) preceding->next = new_node ; if (following != NULL) following->back = new_node ; current = new_node ; current_position = position ; count++ ; return success ; }
So s叩nh c叩ch hi畛n th畛c li棚n t畛c v c叩ch hi畛n th畛c li棚n k畉t DS li棚n t畛c th鱈ch h畛p khi: K鱈ch th動畛c t畛ng ph畉n t畛 l r畉t nh畛 K鱈ch th動畛c c畛a c畉 danh s叩ch (s畛 ph畉n t畛) 達 bi畉t khi l畉p tr狸nh C坦 鱈t s畛 th棚m vo hay lo畉i b畛 畛 gi畛a danh s叩ch H狸nh th畛c truy c畉p tr畛c ti畉p l quan tr畛ng DSLK th鱈ch h畛p khi: K鱈ch th動畛c t畛ng ph畉n t畛 l l畛n K鱈ch th動畛c c畛a danh s叩ch kh担ng bi畉t tr動畛c C坦 nhi畛u s畛 th棚m vo, lo畉i b畛, hay x畉p x畉p c叩c ph畉n t畛 trong danh s叩ch
Chu畛i (string) Chu畛i l m畛t d達y c叩c k箪 t畛 V鱈 d畛: This is a string l 1 chu畛i c坦 16 k箪 t畛 l m畛t chu畛i r畛ng (c坦 0 k箪 t畛) Chu畛i tr畛u t動畛ng: C坦 th畛 xem l danh s叩ch C坦 c叩c t叩c v畛 th動畛ng d湛ng: Sao ch辿p ( strcpy ) N畛i k畉t ( strcat ) T鱈nh chi畛u di ( strlen ) So s叩nh 2 chu畛i ( strcmp ) T狸m m畛t chu畛i trong chu畛i kh叩c ( strstr )
Chu畛i tr棚n C C坦 ki畛u l char * K畉t th炭c b畉ng k箪 t畛 (NULL) S畛 ph畉n t畛 trong b畛 nh畛 nhi畛u h董n chi畛u di chu畛i l 1 C畉n chu畉n b畛 b畛 nh畛 c畉n thi畉t khi thao t叩c V鱈 d畛: char *str1, *str2; delete str2; str2 = new char[strlen(str1) + 1]; strcpy(str2, str1);
Thi畉t k畉 l畉i ki畛u d畛 li畛u chu畛i class String { public: // methods of the string ADT String( ) ; ~String( ) ; String ( const String &copy) ; // copy constructor String ( const char * copy) ; // conversion from C-string String (List< char > &copy) ; // conversion from List void operator = ( const String &copy) ; const char *c_str( ) const; // conversion to C-style string protected: char *entries ; int length ; } ;
Thi畉t k畉 c叩c to叩n t畛 c畉n thi畉t bool operator == ( const String &first , const String &second) ; bool operator > ( const String &first , const String &second) ; bool operator < ( const String &first , const String &second) ; bool operator >= ( const String &first , const String &second) ; bool operator <= ( const String &first , const String &second) ; bool operator != ( const String &first , const String &second) ; bool operator == ( const String &first , const String &second) { return strcmp(first . c_str( ) , second . c_str( )) == 0 ; }
Kh畛i t畉o v畛i chu畛i C String :: String ( const char *in_string) / * Pre: The pointer in_string references a C-string. Post: The String is initialized by the C-string in_string. * / { length = strlen(in_string) ; entries = new char [length + 1] ; strcpy(entries , in_string) ; }
Kh畛i t畉o v畛i danh s叩ch k箪 t畛 String :: String (List< char > &in_list) / * Post: The String is initialized by the character List in_list. * / { length = in_list . size( ) ; entries = new char [length + 1] ; for ( int i = 0 ; i < length ; i++) in_list . retrieve(i , entries[i]) ; //G叩n 畛 k畉t th炭c chu畛i entries[length] = ; }

More Related Content

Ctdl C06

  • 1. C畉U TRC D畛 LI畛U V GI畉I THU畉T Ch動董ng 6: Danh s叩ch v chu畛i
  • 2. Danh s叩ch tr畛u t動畛ng M畛t danh s叩ch (list) ki畛u T M畛t d達y h畛u h畉n ki畛u T M畛t s畛 t叩c v畛: 1. Kh畛i t畉o danh s叩ch r畛ng ( create ) 2. Ki畛m tra r畛ng ( empty ) 3. Ki畛m tra 畉y ( full ) 4. T鱈nh k鱈ch th動畛c ( size ) 5. X坦a r畛ng danh s叩ch ( clear ) 6. Th棚m m畛t gi叩 tr畛 vo danh s叩ch t畉i m畛t v鱈 tr鱈 c畛 th畛 ( insert ) 7. L畉y m畛t gi叩 tr畛 t畉i m畛t v畛 tr鱈 c畛 th畛 ra kh畛i danh s叩ch ( remove ) 8. Nh畉n v畛 gi叩 tr畛 t畉i m畛t v畛 tr鱈 c畛 th畛 ( retrieve ) 9. Thay th畉 m畛t gi叩 tr畛 t畉i m畛t v畛 tr鱈 c畛 th畛 ( replace ) 10. Duy畛t danh s叩ch v thi hnh m畛t t叩c v畛 t畉i m畛i v畛 tr鱈 ( traverse )
  • 3. Thi畉t k畉 c叩c ph動董ng th畛c
  • 4. Ch畛 s畛 c叩c ph畉n t畛 叩nh ch畛 s畛 m畛t danh s叩ch c坦 n ph畉n t畛: 叩nh ch畛 s畛 t畛 0, 1, c叩c ph畉n t畛 V鱈 d畛: a 0 , a 1 , a 2 , , a n-1 Ph畉n t畛 a idx 畛ng sau a idx-1 v tr動畛c a idx+1 (n畉u c坦) D湛ng ch畛 s畛: T狸m th畉y m畛t ph畉n t畛, tr畉 v畛 v畛 tr鱈 (ch畛 s畛) c畛a n坦. Th棚m vo m畛t ph畉n t畛 t畉i v畛 tr鱈 idx th狸 ch畛 s畛 c叩c ph畉n t畛 c滴 t畛 idx tr畛 v畛 sau 畛u tng l棚n 1. Ch畛 s畛 ny 動畛c d湛ng b畉t k畛 danh s叩ch 動畛c hi畛n th畛c th畉 no 畛 c畉p v畉t l箪.
  • 7. Ph動董ng th畛c traverse v tham s畛 hm void print_int( int &x) { cout << x << ; } void increase_int( int &x) { x++; } void main() { List< int > alist; alist.traverse(print_int); alist.traverse(increase_int); } Khi g畛i tham s畛 hm, ch動董ng tr狸nh d畛ch ph畉i nh狸n th畉y hm 動畛c g畛i. T湛y theo m畛c 鱈ch m g畛i c叩c hm kh叩c nhau.
  • 8. Hi畛n th畛c danh s叩ch li棚n t畛c template < class List_entry> class List { public: // methods of the List ADT List( ) ; int size( ) const; bool full( ) const; bool empty( ) const; void clear( ) ; void traverse( void (*visit)(List_entry &)) ; Error_code retrieve( int position , List_entry &x) const; Error_code replace( int position , const List_entry &x) ; Error_code remove( int position , List_entry &x) ; Error_code insert( int position , const List_entry &x) ; protected: // data members for a contiguous list implementation int count ; List_entry entry[max_list] ; } ;
  • 9. Th棚m vo m畛t danh s叩ch li棚n t畛c insert(3, z) d e f g h d e f g h z count=8 count=9 a b c 0 1 2 3 4 5 6 7 8 9
  • 10. Gi畉i thu畉t th棚m vo m畛t danh s叩ch li棚n t畛c Algorithm Insert Input : position l v畛 tr鱈 c畉n th棚m vo, x l gi叩 tr畛 c畉n th棚m vo Output : danh s叩ch 達 th棚m vo x 1. if list 畉y 1.1. return overflow 2. if position n畉m ngoi kho畉ng [0..count] 2.1. return range_error //D畛i t畉t c畉 c叩c ph畉n t畛 t畛 position v畛 sau 1 v畛 tr鱈 3. for index = count-1 down to position 3.1. entry[index+1] = entry[index] 4. entry[position] = x //G叩n x vo v畛 tr鱈 position 5. count++ //Tng s畛 ph畉n t畛 l棚n 1 6. return success; End Insert
  • 11. M達 C++ th棚m vo m畛t danh s叩ch li棚n t畛c template < class List_entry> Error_code List<List_entry> :: insert( int position , const List_entry &x) { if (full( )) return overflow ; if (position < 0 || position > count) return range_error ; for ( int i = count 1 ; i >= position ; i) entry[i + 1] = entry[i] ; entry[position] = x ; count++; return success ; }
  • 12. X坦a t畛 m畛t danh s叩ch li棚n t畛c x remove(3, x) d e f g h d e f g h count=8 count=7 a b c 0 1 2 3 4 5 6 7 8 9
  • 13. Gi畉i thu畉t x坦a t畛 m畛t danh s叩ch li棚n t畛c Algorithm Remove Input : position l v畛 tr鱈 c畉n x坦a b畛, x l gi叩 tr畛 l畉y ra 動畛c Output : danh s叩ch 達 x坦a b畛 ph畉n t畛 t畉i position 1. if list r畛ng 1.1. return underflow 2. if position n畉m ngoi kho畉ng [0..count-1] 2.1. return range_error 3. x = entry[position] //L畉y x t畉i v畛 tr鱈 position ra 4. count-- //Gi畉m s畛 ph畉n t畛 i 1 //D畛i t畉t c畉 c叩c ph畉n t畛 t畛 position v畛 tr動畛c 1 v畛 tr鱈 5. for index = position to count-1 5.1. entry[index] = entry[index+1] 6. return success; End Remove
  • 14. Gi畉i thu畉t duy畛t m畛t danh s叩ch li棚n t畛c Algorithm Traverse Input : hm visit d湛ng 畛 t叩c 畛ng vo t畛ng ph畉n t畛 Output : danh s叩ch 動畛c c畉p nh畉t b畉ng hm visit //Qu辿t qua t畉t c畉 c叩c ph畉n t畛 trong list 1. for index = 0 to count-1 1.1. Thi hnh hm visit 畛 duy畛t ph畉n t畛 entry[index] End Traverse
  • 15. M達 C++ duy畛t m畛t danh s叩ch li棚n t畛c template < class List_entry> void List<List_entry> :: traverse( void (*visit)(List_entry &)) / * Post: T叩c v畛 cho b畛i hm visit s畉 動畛c thi hnh t畉i m畛i thnh ph畉n c畛a list b畉t 畉u t畛 v畛 tr鱈 0 tr畛 i. * / { for ( int i = 0 ; i < count ; i++) (*visit)(entry[i]) ; }
  • 16. Danh s叩ch li棚n k畉t 董n (DSLK 董n)
  • 17. Hi畛n th畛c DSLK 董n template < class List_entry> class List { public: // Specifications for the methods of the list ADT go here. // The following methods replace compiler-generated defaults. List( ) ; ~List( ); List( const List<List_entry> &copy) ; void operator = ( const List<List_entry> &copy) ; protected: // Data members for the linked list implementation now follow. int count ; Node<List_entry> * head ; // The following auxiliary function is used to locate list positions Node<List_entry> *set_position( int position) const; } ;
  • 18. T狸m v畛 tr鱈 tr棚n DSLK 董n Nhu c畉u: Nh畉p vo ch畛 s畛 c畛a m畛t ph畉n t畛 Cho bi畉t 坦 l ph畉n t畛 no (con tr畛 ch畛 畉n ph畉n t畛) t動畛ng: B畉t 畉u t畛 ph畉n t畛 畉u ti棚n Di chuy畛n 炭ng position b動畛c th狸 畉n 動畛c ph畉n t畛 c畉n t狸m Ph畉i 畉m b畉o l position n畉m trong kho畉ng [0..count-1]
  • 19. Gi畉i thu畉t t狸m v畛 tr鱈 tr棚n DSLK 董n Algorithm Set position Input : position l v畛 tr鱈 c畉n t狸m Output : con tr畛 ch畛 畉n ph畉n t畛 t畉i v畛 tr鱈 c畉n t狸m 1. set q to head 2. for index =0 to position //Thi hnh position b動畛c 2.1. advance q to the next element //Tr畛 q 畉n ph畉n t畛 k畉 ti畉p 3. return q End Set position index=0 set_position(2) index=1 index=2 q x y z head m
  • 20. M達 C++ t狸m v畛 tr鱈 tr棚n DSLK 董n template < class List_entry> Node<List_entry> *List<List_entry> :: set_position( int position) const / * Pre: position l v畛 tr鱈 h畛p l畛 trong list, 0 < position < count. Post: Tr畉 v畛 m畛t con tr畛 ch畛 畉n Node ang 畛 v畛 tr鱈 position */ { Node<List_entry> *q = head ; for ( int i = 0 ; i < position ; i++) q = q->next ; return q ; }
  • 21. Th棚m vo m畛t DSLK 董n new_node a y following_node ph畉n t畛 t畉i v畛 tr鱈 position x previous_node ph畉n t畛 t畉i v畛 tr鱈 position-1 b但y gi畛, ph畉n t畛 ny c坦 v畛 tr鱈 position b但y gi畛, ph畉n t畛 ny c坦 v畛 tr鱈 position+1
  • 22. Gi畉i thu畉t th棚m vo m畛t DSLK 董n Algorithm Insert Input: position l v畛 tr鱈 th棚m vo, x l gi叩 tr畛 th棚m vo Output: danh s叩ch 達 th棚m vo x t畉i v畛 tr鱈 position 1. N畉u position > 0 1.1. Tr畛 previous 畉n ph畉n t畛 t畉i v畛 tr鱈 position-1 1.2. Tr畛 following 畉n ph畉n t畛 sau previous 2. Ng動畛c l畉i 2.1. Tr畛 following 畉n head 3. T畉o ra node m畛i l new_node v畛i gi叩 tr畛 x 4. Tr畛 next c畛a new_node 畉n following 5. N畉u position l 0 5.1. Tr畛 head 畉n new_node 6. Ng動畛c l畉i 6.1. Tr畛 next c畛a previous 畉n new_node 7. Tng s畛 l動畛ng c叩c ph畉n t畛 l棚n 1 End Insert
  • 23. M達 C++ th棚m vo m畛t DSLK 董n template < class List_entry> Error_code List<List_entry> :: insert( int position , const List_entry &x) { if (position < 0 || position > count) return range_error ; Node<List_entry> *new_node , *previous , *following ; if (position > 0) { previous = set_position(position 1) ; following = previous->next ; } else following = head ; new_node = new Node<List_entry>(x , following) ; if (new_node == NULL) return overflow ; if (position == 0) head = new_node ; else previous->next = new_node ; count++ ; return success ; }
  • 24. X坦a b畛 t畛 m畛t DSLK 董n b但y gi畛, ph畉n t畛 ny c坦 v畛 tr鱈 position ph畉n t畛 t畉i v畛 tr鱈 position ph畉n t畛 t畉i v畛 tr鱈 position+1 x z previous_node ph畉n t畛 t畉i v畛 tr鱈 position-1 y following_node
  • 25. DSLK k辿p (Doubly linked list)
  • 26. 畛nh ngh挑a DSLK k辿p template < class List_entry> class List { public: // Add specications for methods of the list ADT. // Add methods to replace compiler generated defaults. protected: // Data members for the doubly-linked list implementation follow: int count ; mutable int current_position ; mutable Node<List_entry> *current ; // The auxiliary function to locate list positions follows: void set_position( int position) const; } ; C叩c hm h畉ng ( const ) c坦 th畛 thay 畛i gi叩 tr畛 c畛a c叩c bi畉n mutable ny
  • 27. 畛nh ngh挑a Node cho DSLK k辿p template < class Node_entry> struct Node { // data members Node_entry entry ; Node<Node_entry> *next ; Node<Node_entry> *back ; // constructors Node( ) ; Node(Node_entry , Node<Node_entry> *link_back = NULL , Node<Node_entry> *link_next = NULL) ; } ; z
  • 28. T狸m v畛 tr鱈 trong DSLK k辿p set_position(6) set_position(8) x y z m current current_position position = 5 position = 6 position = 7 position = 8
  • 29. Th棚m vo trong DSLK k辿p current previous following new_node x y z ph畉n t畛 t畉i v畛 tr鱈 position-1 ph畉n t畛 t畉i v畛 tr鱈 position ph畉n t畛 ny b但y gi畛 c坦 v畛 tr鱈 l position ph畉n t畛 ny b但y gi畛 c坦 v畛 tr鱈 l position+1
  • 30. Th棚m vo trong DSLK k辿p Algorithm Insert Input: x l gi叩 tr畛 c畉n th棚m vo t畉i position (0<=position<=count) Output : danh s叩ch 達 th棚m gi叩 tr畛 x vo v畛 tr鱈 position 1. if position l 0 1.1. if s畛 ph畉n t畛 l 0 1.1.1. Tr畛 following 畉n NULL 1.2. Tr畛 preceding 畉n NULL 2. else 2.1. Tr畛 preceding 畉n v畛 tr鱈 position -1, following 畉n v畛 tr鱈 position 3. T畉o ra ph畉n t畛 m畛i new_node 4. Tr畛 next v back c畛a new_node 畉n following v preceding 5. if preceding kh叩c r畛ng 5.1. Tr畛 next c畛a preceding 畉n new_node 6. if following kh叩c r畛ng 6.1. Tr畛 back c畛a following 畉n new_node 7. Tng s畛 ph畉n t畛 l棚n 1 End Insert
  • 31. M達 C++ th棚m vo trong DSLK k辿p template < class List_entry> Error_code List<List_entry> :: insert( int position , const List_entry &x) { Node<List_entry> *new node , *following , *preceding ; if (position < 0 || position > count) return range_error ; if (position == 0) { if (count == 0) following = NULL ; else { set_position(0) ; following = current ; } preceding = NULL ; } else { set_position(position 1) ; preceding = current ; following = preceding->next ; } new_node = new Node<List_entry>(x , preceding , following) ; if (new_node == NULL) return overflow ; if (preceding != NULL) preceding->next = new_node ; if (following != NULL) following->back = new_node ; current = new_node ; current_position = position ; count++ ; return success ; }
  • 32. So s叩nh c叩ch hi畛n th畛c li棚n t畛c v c叩ch hi畛n th畛c li棚n k畉t DS li棚n t畛c th鱈ch h畛p khi: K鱈ch th動畛c t畛ng ph畉n t畛 l r畉t nh畛 K鱈ch th動畛c c畛a c畉 danh s叩ch (s畛 ph畉n t畛) 達 bi畉t khi l畉p tr狸nh C坦 鱈t s畛 th棚m vo hay lo畉i b畛 畛 gi畛a danh s叩ch H狸nh th畛c truy c畉p tr畛c ti畉p l quan tr畛ng DSLK th鱈ch h畛p khi: K鱈ch th動畛c t畛ng ph畉n t畛 l l畛n K鱈ch th動畛c c畛a danh s叩ch kh担ng bi畉t tr動畛c C坦 nhi畛u s畛 th棚m vo, lo畉i b畛, hay x畉p x畉p c叩c ph畉n t畛 trong danh s叩ch
  • 33. Chu畛i (string) Chu畛i l m畛t d達y c叩c k箪 t畛 V鱈 d畛: This is a string l 1 chu畛i c坦 16 k箪 t畛 l m畛t chu畛i r畛ng (c坦 0 k箪 t畛) Chu畛i tr畛u t動畛ng: C坦 th畛 xem l danh s叩ch C坦 c叩c t叩c v畛 th動畛ng d湛ng: Sao ch辿p ( strcpy ) N畛i k畉t ( strcat ) T鱈nh chi畛u di ( strlen ) So s叩nh 2 chu畛i ( strcmp ) T狸m m畛t chu畛i trong chu畛i kh叩c ( strstr )
  • 34. Chu畛i tr棚n C C坦 ki畛u l char * K畉t th炭c b畉ng k箪 t畛 (NULL) S畛 ph畉n t畛 trong b畛 nh畛 nhi畛u h董n chi畛u di chu畛i l 1 C畉n chu畉n b畛 b畛 nh畛 c畉n thi畉t khi thao t叩c V鱈 d畛: char *str1, *str2; delete str2; str2 = new char[strlen(str1) + 1]; strcpy(str2, str1);
  • 35. Thi畉t k畉 l畉i ki畛u d畛 li畛u chu畛i class String { public: // methods of the string ADT String( ) ; ~String( ) ; String ( const String &copy) ; // copy constructor String ( const char * copy) ; // conversion from C-string String (List< char > &copy) ; // conversion from List void operator = ( const String &copy) ; const char *c_str( ) const; // conversion to C-style string protected: char *entries ; int length ; } ;
  • 36. Thi畉t k畉 c叩c to叩n t畛 c畉n thi畉t bool operator == ( const String &first , const String &second) ; bool operator > ( const String &first , const String &second) ; bool operator < ( const String &first , const String &second) ; bool operator >= ( const String &first , const String &second) ; bool operator <= ( const String &first , const String &second) ; bool operator != ( const String &first , const String &second) ; bool operator == ( const String &first , const String &second) { return strcmp(first . c_str( ) , second . c_str( )) == 0 ; }
  • 37. Kh畛i t畉o v畛i chu畛i C String :: String ( const char *in_string) / * Pre: The pointer in_string references a C-string. Post: The String is initialized by the C-string in_string. * / { length = strlen(in_string) ; entries = new char [length + 1] ; strcpy(entries , in_string) ; }
  • 38. Kh畛i t畉o v畛i danh s叩ch k箪 t畛 String :: String (List< char > &in_list) / * Post: The String is initialized by the character List in_list. * / { length = in_list . size( ) ; entries = new char [length + 1] ; for ( int i = 0 ; i < length ; i++) in_list . retrieve(i , entries[i]) ; //G叩n 畛 k畉t th炭c chu畛i entries[length] = ; }