西安建筑科技大学：《数据结构与算法》课程教学资源（PPT电子教案）第三部分 线性表_线性表 Chapter 6 LISTS AND STRINGS（英文）

Chapter 6 LISTS AND STRINGS I1 List Specifications 2. List Implementations a). Class Templates (b). Contiguous c). Simply Linked d). Simply Linked with Position Pointer e). Doubly Linked

Chapter 6 LISTS AND STRINGS 1. List Specifications 2. List Implementations (a). Class Templates (b). Contiguous (c). Simply Linked (d). Simply Linked with Position Pointer (e). Doubly Linked

Chapter 6 LISTS AND STRINGS L3. Strings 4. Application: Text Editor 5. Linked Lists in Arrays 6. Application Generating Permutations 7. Pointers and pitfalls

Chapter 6 LISTS AND STRINGS 3. Strings 4. Application: Text Editor 5. Linked Lists in Arrays 6. Application: Generating Permutations 7. Pointers and Pitfalls

6.1 List Definition DEFINITION a list of elements of type T is a finite sequence of elements of T together with the following operations 1. Construct the list, leaving it empty 2. Determine whether the list is empty or not 3. Determine whether the list is full or not 4. Find the size of the list 5. Clear the list to make it empty 6. Insert an entry at a specified position of the list 7. Remove an entry from a specified position in the list 8. Retrieve the entry from a specified position in the list 9. Replace the entry at a specified position in the list 10. Traverse the list, performing a given operation on each entry

DEFINITION A list of elements of type T is a finite sequence of elements of T together with the following operations: 1. Construct the list, leaving it empty. 2. Determine whether the list is empty or not. 3. Determine whether the list is full or not. 4. Find the size of the list. 5. Clear the list to make it empty. 6. Insert an entry at a specified position of the list. 7. Remove an entry from a specified position in the list. 8. Retrieve the entry from a specified position in the list. 9. Replace the entry at a specified position in the list. 10. Traverse the list, performing a given operation on each entry. 6.1 List Definition

Comparison with Standard Template Library: 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

Comparison with Standard Template Library: ◆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

Method Specifications List: ListO; Post: The list has been created and is initialized to be empty. void List clear(; Post: All List entries have been removed the list is empty

List :: List( ); Post: The List has been created and is initialized to be empty. Method Specifications void List :: clear(); Post: All List entries have been removed; the List is empty

bool List empty const Post: The function returns true or false according to whether the List is empty or not. bool List: fullo const Post: The function returns true or false according to whether the list is full or not int List size const; Post: The function returns the number of entries in the list

bool List :: empty() const; Post: The function returns true or false according to whether the List is empty or not. bool List :: full() const; Post: The function returns true or false according to whether the List is full or not. int List :: size() const; Post: The function returns the number of entries in the List

Position Number in a list 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 soon。 Locating an entry of a list by its position is superficially ike 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

Position Number in a List ◆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

◆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); Post: If the List is not full and o position n, where n is the number of entries in the List, the function succeeds: Any entry formerly at position and all later entries have their position numbers increased by 1, and x is inserted at position in the list Else: The function fails with a diagnostic error code

Error_code List::insert(int position, const List_entry &x); Post: If the List is not full and 0 position n, where n is the number of entries in the List, the function succeeds:Any entry formerly at position and all later entries have their position numbers increased by 1, and x is inserted at position in the List. Else: The function fails with a diagnostic error code

Error_code List: remove( int position, List entry &x Post: If 0 s position <n where n is the number of entries in the list, the function succeeds: the entry at position is removed from the list, and all later entries have their position numbers decreased by 1. The parameter x records a copy of the entry formerly at position Else: The function fails with a diagnostic error code

Error_code List :: remove ( int position, List_entry &x ); Post: If 0 ≤ position<n, where n is the number of entries in the List, the function succeeds: The entry at position is removed from the List, and all later entries have their position numbers decreased by 1. The parameter x records a copy of the entry formerly at position. Else: The function fails with a diagnostic error code