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 complicated2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 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<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