2008级计算机专业数据结构 内部资料,仅供课堂教学使用 Chapter 6 LISTs P212 1. List Specifications 2. List Implementations (a) Class Template (d) Simply Linked with Position Pointer (b)C (e)Doubly Linked (c)Simply Linked 3. Linked Lists in Arrays 4. Application: Generating Permutations 16. 1] List Specifications List definition p213 Comparison with Standard Template library P.213 The Stl list provides only those operations that can be implemented efficiently in a List implementation known as doubly linked, which we shall study shortly The Stl list does not allow random access to an arbitrary list position The STl vector, does provide some random access to a sequence of data values, but not all the other capabilities we shall develop for a List. In this way, our study of the list Adt provides an introduction to both the Stl classes list and vector 1. I Method Specifications P214 List void list clear( bool list pty( )const bool List : full() const int list ize()const Position number in a list P.215-216 To find an entry in a list, we use an integer that gives its position within the list We shall num ber the positions in a list so that the first entry in the list has position O, the second position 1. and so on Locating an entry of a list by its position is superficially like indexing an array, but there are important differences. If we insert an entry at a particular position, then the position numbers of all later entries increase by 1. If we remove an entry, then the positions of all following entries decrease by 1 The position number for a list is defined without regard to the implementation. For a contiguous \ill also use the position to find an entry within linked implementations of a list, where no indices or arrays are used at al Error code List : insert(int position, const List entry &x)i Error code List : remove(int position, List entry &x)i Error code List:: retrieve (int position, List entry &x)consti Error code List : replace(int position, const List entry &x)i d list traverse(void (*visit)(List entry &))i 16.2 List Implementations 6.2. 1 Class Templates P218 0 AC++ template construction allows us to write code, usually code to implement a class, that uses objects of an arbitrary, generic type In template code we utilize a parameter enclosed in angle brackets< to denote the generic type Later, when a client uses our code, the client can substitute an actual type for the template parameter The client can thus obtain several actual pieces of code from our template, using different actual types in place of the template parameter Example: We shall implement a template class List that depends on one generic type parameter. A client can then use our template to declare several lists with different types of entries with declarations of the following for List<int first list: list<char second list Templates provide a new mechanism for creating generic data structures, one that allows many different specializations of a given data structure template in a single application The added generality that we get by using templates comes at the price of slightly more complicated
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Chapter 6 LISTS P.212 ----------------------------------------------------------------------------------------------------------------------------------------------- 1. List Specifications 2. List Implementations (a) Class Templates (b) Contiguous (c) Simply Linked (d) Simply Linked with Position Pointer (e) Doubly Linked 3. Linked Lists in Arrays 4. Application: Generating Permutations [6.1] List Specifications List Definition P.213 Comparison with Standard Template Library: P.213 ⚫ The STL list provides only those operations that can be implemented efficiently in a List implementation known as doubly linked, which we shall study shortly. ⚫ The STL list does not allow random access to an arbitrary list position. ⚫ The STL vector, does provide some random access to a sequence of data values, but not all the other capabilities we shall develop for a List. ⚫ In this way, our study of the List ADT provides an introduction to both the STL classes list and vector. 6.1.1 Method Specifications P. 214 List : : List( ); void List : : clear( ); bool List :: empty( ) const; bool List :: full( ) const; int List : : size( ) const; Position Number in a List P. 215-216 ⚫ To find an entry in a list, we use an integer that gives its position within the list. ⚫ We shall number the positions in a list so that the first entry in the list has position 0, the second position 1, and so on. ⚫ Locating an entry of a list by its position is superficially like indexing an array, but there are important differences. If we insert an entry at a particular position, then the position numbers of all later entries increase by 1. If we remove an entry, then the positions of all following entries decrease by 1. ⚫ The position number for a list is defined without regard to the implementation. For a contiguous list, implemented in an array, the position will indeed be the index of the entry within the array. But we will also use the position to find an entry within linked implementations of a list, where no indices or arrays are used at all. Error_code List :: insert(int position, const List_entry &x); Error_code List :: remove(int position, List_entry &x); Error_code List :: retrieve(int position, List_entry &x) const; Error_code List :: replace(int position, const List_entry &x); void List :: traverse(void (*visit)(List_entry &)); [6.2] List Implementations 6.2.1 Class Templates P. 218 ⚫ A C++ template construction allows us to write code, usually code to implement a class, that uses objects of an arbitrary, generic type. ⚫ In template code we utilize a parameter enclosed in angle brackets to denote the generic type. ⚫ Later, when a client uses our code, the client can substitute an actual type for the template parameter. The client can thus obtain several actual pieces of code from our template, using different actual types in place of the template parameter. ⚫ Example: We shall implement a template class List that depends on one generic type parameter. A client can then use our template to declare several lists with different types of entries with declarations of the following form: List first_list; List second_list; ⚫ Templates provide a new mechanism for creating generic data structures, one that allows many different specializations of a given data structure template in a single application. ⚫ The added generality that we get by using templates comes at the price of slightly more complicated
2008级计算机 数据结构课堂教学笔记 内部资料,仅供课堂教学使用 class specifications and implementations 6.2.2 Contiguous Implementation P 219 List size p 219 Insertion P 220 Traversal P 221 Performance of methods: P 220 In processing a contiguous list with n entries insert and remove operate in time approximately proportional to n List, clear, empty, full, size, replace, and retrieve operate in constant time 6.2. 3 Simply linked Implementation Node declaration: P 221 List declaration P.221 Actions on a Linked list P. 222 Finding a list position P. 223 Insertion method P 224 Insertion into a linked list p 224 In processing a linked List with n entries: P. 225 clear, insert, remove, retrieve, and replace require time approximately prop nal to n List, empty, full, and size operate in constant time 6.2. 4 Variation Keeping the current position P 225-227 Suppose an application processes list entries in order or refers to the same entry several times before processing another entry Remem ber the last-used position in the list and, if the next operation refers to the same or a later position, start tracing through the list from this last-used position Note that this will not speed up every application using lists The method retrieve is defined as const, but its implementation will need to alter the last-used position of a List. To enable this, we use the mutable qualifier. Mutable data members of a class can be changed, even by constant methods Class list p 226 e All the new class members have protected visibility, so, from the perspective of a client, the class looks exactly like the earlier implementation e The current position is now a member of the class List, so there is no longer a need for set position to return a pointer; instead, the function simply resets the pointer current directly within the List template : set position(int position) const P 226 e For repeated references to the same position, neither the body of the if statement nor the body of the for statement will be executed. and hence the function will take almost no time. If we move forward only one position, the body of the for statement will be executed only once, so again the function will be very fast posi e If it is necessary to move backwards through the List, then the function operates in almost the same way as the version of set position used in the previous implementation 6.2.5 Doubly Linked lists Node definition: P 227 List definition: P 228 Insertion into a doubly linked list P.229-230 6.2.6 Comparison of Implementations Contiguous storage is generally preferable P231 Linked storage proves superior P231 16.3 Linked Lists in Arrays P251 on shows how to implement linked lists using only integer variables and arrays Begin with a large wor kspace array and regard the array as our allocation of unused space
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 class specifications and implementations. 6.2.2 Contiguous Implementation P. 219 List Size P. 219 Insertion P. 220 Traversal P. 221 Performance of Methods: P. 220 In processing a contiguous list with n entries: ⚫ insert and remove operate in time approximately proportional to n. ⚫ List, clear, empty, full, size, replace, and retrieve operate in constant time. 6.2.3 Simply Linked Implementation Node declaration: P. 221 List declaration: P. 221 Actions on a Linked List P. 222 Finding a List Position P. 223 Insertion Method P. 224 Insertion into a Linked List P. 224 In processing a linked List with n entries: P. 225 ⚫ clear, insert, remove, retrieve, and replace require time approximately proportional to n. ⚫ List, empty, full, and size operate in constant time. 6.2.4 Variation: Keeping the Current Position P. 225-227 ⚫ Suppose an application processes list entries in order or refers to the same entry several times before processing another entry. ⚫ Remember the last-used position in the list and, if the next operation refers to the same or a later position, start tracing through the list from this last-used position. ⚫ Note that this will not speed up every application using lists. ⚫ The method retrieve is defined as const, but its implementation will need to alter the last-used position of a List. To enable this, we use the mutable qualifier. Mutable data members of a class can be changed, even by constant methods. Class List P. 226 ⚫ All the new class members have protected visibility, so, from the perspective of a client, the class looks exactly like the earlier implementation. ⚫ The current position is now a member of the class List, so there is no longer a need for set position to return a pointer; instead, the function simply resets the pointer current directly within the List. template void List :: set_position(int position) const P. 226 ⚫ For repeated references to the same position, neither the body of the if statement nor the body of the for statement will be executed, and hence the function will take almost no time. ⚫ If we move forward only one position, the body of the for statement will be executed only once, so again the function will be very fast. ⚫ If it is necessary to move backwards through the List, then the function operates in almost the same way as the version of set position used in the previous implementation. 6.2.5 Doubly Linked Lists Node definition: P. 227 List definition: P. 228 Insertion into a Doubly Linked List P. 229-230 6.2.6 Comparison of Implementations Contiguous storage is generally preferable P. 231 Linked storage proves superior P. 231 [6.3] Linked Lists in Arrays P. 251 ⚫ This section shows how to implement linked lists using only integer variables and arrays. ⚫ Begin with a large workspace array and regard the array as our allocation of unused space
2008级计算机 数据结构课堂教学笔记 内部资料,仅供课堂教 e Set up our own functions to keep track of which parts of the array are unused and to link entries of the array together in the desired order e The one feature of linked lists that we must invariably lose in this implementation method is the dynamic allocation of storage Applications where linked lists in arrays may prove preferable are those where the num ber of entries in a list is known in advance the links are frequently rearranged, but relatively few additions or deletions are made, or the same data are sometimes best treated as a linked list and other times as a contiguous list Storage management P252-254 Class Declaration, Linked Lists in Arrays P255 New and delete P Other Operations P Insertion P. 257-255 16. 4 Application: Generating Permutations P260 Generating Permutations P261 The general pi ocedure Optimized permute Function P. 264 Main program P.264 Processing a permutation Pointers and pitfalls 12 items p265-266 Errata p. 215, line I of first specification should not be indented p. 246, last line: Change" s(ubstitue)"to"s(ubstitute) p. 260, bottom of diagram: Change"L: to"head: " (3 times)
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ Set up our own functions to keep track of which parts of the array are unused and to link entries of the array together in the desired order. ⚫ The one feature of linked lists that we must invariably lose in this implementation method is the dynamic allocation of storage. ⚫ Applications where linked lists in arrays may prove preferable are those where ◼ the number of entries in a list is known in advance, ◼ the links are frequently rearranged, but relatively few additions or deletions are made, or ◼ the same data are sometimes best treated as a linked list and other times as a contiguous list. Storage Management P. 252-254 Class Declaration, Linked Lists in Arrays P. 255 New and Delete P. 256 Other Operations P. 257 Insertion P. 257-258 [6.4] Application: Generating Permutations P. 260 Generating Permutations P. 261 The General Procedure P. 262 Optimized Permute Function P. 264 Main program: P. 264 Processing a permutation: P. 265 Pointers and Pitfalls 12 items P.265-266 ------------------------------------------------------------------------------------------------------------------------------- Errata p. 215, line 1 of first specification should not be indented. p. 246, last line: Change "s(ubstitue)" to "s(ubstitute)". p. 260, bottom of diagram: Change "L:" to "head:" (3 times). -------------------------------------------------------------------------------------------------------------------------------