面向对象的C++程序设计 第六版 课后习题答案 第十七章.doc

SavitchInstructors Resource GuideProblem Solving w/ C+, 6eChapter 17Chapter 17Templates for More Abstraction1. Solutions to and Remarks on Selected Programming ProjectsWith earlier compilers, when the operator new is unable to allocate the amount of memory requested, then new returned a null pointer. The current ANSI/ISO C+ Standard provides that when operator new is unable to allocate the amount of memory requested, then new should throw an exception, bad_alloc. Standard compliant compilers can be instructed to exhibit the earlier behavior of returning a null pointer. It is also easy to overload operator new to catch the exception locally and return a null pointer in the event that such an exception is thrown. For these reasons, and because we have not yet treated exceptions in the text, I have not attempted to handle exceptions thrown by new in the code for these problems, preferring to test for a returned null pointer.1. Template SearchNo matter how clearly is stated, to understand it, I find I have to make the problem my own by paraphrasing the problem statement. I encourage the students to make there own paraphrases. This problem asks for a function template. The template should have parameters for a partially filled array and for a value of the base type of the array. If the value is in the partially filled array, then the function returns the index of the first occurrence of that value, otherwise the function returns -1. The base type of the array is a type parameter. Observation: you need two arguments for the partially filled array: one for the array and one for the number of entries in the array actually used.Then test, and test some more. I tested for an array of class objects and an array of int objects.#include /Precondition: if T, the array base type must have/operator= defined, & number_used = declared size of /the array argument./Postcondition: Function return index of the first / occurrence of target in array. if target is not in the / array, the function returns -1templateint search( T array, int number_used, T target) for ( int i = 0; i number_used; i+ ) if (arrayi = target) return i; return -1;class SingleIntpublic: SingleInt():d(0) SingleInt(int n):d(n) friend bool operator=(SingleInt left, SingleInt right);private: int d;bool operator=( SingleInt left, SingleInt right) return left.d = right.d;int main() using namespace std; SingleInt a14 = 1, 4, 3, 5, 3, 6, 8, 9, 10, 7; int b14 = 1, 4, 3, 5, 3, 6, 8, 9, 10, 7; /The constructor SingleInt(int) will be called to /initialize this array cout search( a, 10, SingleInt(5) index of array a of SingleInt objects endl; cout search( b, 10, 5) index of array a of SingleInt objects endl;The output from the trial run is as expected:3 index of object with data member 5 in array a of type SingleInt3 index of 5 in array a of int objects2. Template ListMy paraphrase of the problem statement is:Rewrite class template List from Display 17.4 and 17.6 so that it is more general. This more general version adds features that allow stepping through items on the list in order. allow asking for the current item advance the current item by one back up the current item by one make the first item be the current item ask for the nth item where n has appropriate value.The problem suggests the following members be added: a data member to record current positionMember functions: A function that returns the current item as a value - ITEM 2 A void function that makes the next item the current item. ITEM 3 A void function that makes the previous item the current item. ITEM 4 A void function that makes the first item the current item ITEM 5 A function that takes n as argument and returns item n as a value ITEM 6These functions together will make ITEM 1 possible.Numbering notes: The first item is indexed 0, as in arrays. Empty list has no first item There is no item after the last item in a list.Testing: Test for empty and handle this case appropriately Test for beginning and end and handle these cases appropriately. Test the class template.#include /This is the HEADER FILE list.h. /This is the INTERFACE for the class List. /Objects of type List can be list of items of any type for /which the operators and = are defined. All the items on /any one list must be of the same type. A list that can hold /up to max items all of type /Type_Name is declared as follows:/ List the_object(max);#ifndef LIST_H#define LIST_Htemplateclass Listpublic: List(int max); /Initializes the object to an empty list that can hold up /to max items of type T. bool is_empty() const; / returns true if the list is empty, specifically: / if 0 = current_length, / returns true (= 1) / else false (= 0) bool is_full() const; / returns true if the list is full, specifically: / if max_length = current_length, / returns true (= 1) / else false (= 0) bool at_front() const; / returns true if the list is at front, specifically: / if 0 = position / returns true ( = 1) / else false ( = 0) bool at_end() const; / returns true if list position is the last item, /specifically: / if position = current_length - 1 / returns true (= 1) / else returns false (= 0) T current() const; / returns the current item from the list void next_position(); /Make next item current position /Prerequisite: not end_of_list() /Postcondition: makes successor of current the new /current item. / if end_of_list, function does nothing void previous_position(); /Make previous item current position /Prerequisite: not at_front() /Postcondition: / makes predecessor of current the new current item / if at_front(), this function does nothing void reset(); /precondition: list is not empty /action: makes the first item the current item. T item_n( int n ) const; /Precondition: list is not empty and /0 = n = current_length /Postcondition: returns item indexed by n. List( ); /Returns all the dynamic memory used by the object /to the heap. int length( ) const; /Returns the number of items on the list. void add(T new_item); /Precondition: The list is not full /Postcondition: The new_item has been added to the list. void erase( ); /Removes all items from the list, i.e., makes list empty. friend std:ostream& operator (std:ostream& outs, const List& the_list); /Overloads the operator so it can be used to output the /contents of the list. The items are output one per line. /Precondition: If outs is a file output stream, then /outs has already been connected to a file.private: T *item; /pointer to the dynamic array holding the list. int max_length; /max number of items allowed on the list. int current_length; /number of items currently on list. int position; /index of current item;#include list.cc #endif /LIST_H/ file: list.cc/(Your system may require some suffix other than .cc)./This is the IMPLEMENTATION of the class template named /List. /The interface for the class template List is in the /header file list.h.#include #include /We are protected from multiple inclusion /by the #ifndef, #define and #endif preprocessor /directives, both the list.h and list.cc files /With C+ there is a maximum depth that inclusions /can go, but protection is nevertheless desirable.#include list.h#ifndef LIST_CC#define LIST_CC/Uses cstdlib and iostreamtemplateList:List(int max) using namespace std; position = 0; max_length = max; current_length = 0; item = new Tmax; if (item = NULL) cout Error: Insufficient memory.n; exit(1); templateList:List( ) delete item;templatebool List:is_empty() const if ( 0 = current_length) return 1; return 0;templatebool List:is_full() const return max_length = current_length);templatebool List:at_front() const if ( 0 = position ) return 1; return 0;templatebool List:at_end() const if ( position = current_length - 1 ) return 1; return 0;templateT List:current() const return itemposition;templatevoid List:next_position() if (!at_end() position+; / else this function does nothingtemplatevoid List:previous_position() if (!at_front() position-; / else this function does nothingtemplatevoid List:reset() position = 0;templateT List:item_n( int n ) const if ( is_empty() ) cout item_n called on empty list. Aborting endl; exit(1); else if ( !(0 = n) & !(n = current_length) ) cout call to item_n with bad index n aborting endl; exit(1); return itemn;templateint List:length( ) const return (current_length);/Uses iostream and cstdlib:templatevoid List:add(T new_item) using namespace std; if ( is_full( ) ) cout Error: adding to a full list.n; exit(1); else itemcurrent_length = new_item; position = current_length; current_length = current_length + 1; templatevoid List:erase( ) current_length = 0; position = 0;/Uses iostream:templatestd:ostream& operator (std:ostream& outs, const List& the_list) using namespace std; for (int i = 0; i the_list.current_length; i+) cout the_list.itemi endl; return outs;#endif/File: list-test.cc/Program to demonstrate use of the class template List./I have tested all the class members thoroughly only for /the int instantiation. The student should test just as /thoroughly for the char instantiation.#include #include list.hint main( ) using namespace std; List first_list(5); if ( first_list.is_empty() cout first_list is empty just after construction endl; for ( int i = 0; i 5; i+ ) first_list.add(20 - 2*i); if ( first_list.is_full() cout first_list (declared to be size 5) is full after adding 5 integers endl endl; cout first_list, using operator is n first_list endl; if ( first_list.at_front() cout first_list is at front endl; if ( first_list.at_end() cout first_list is at end endl; cout endl; cout first_list from end to front endl; cout extra first_list.item_n(0) s on the end signal that previous_position does endl nothing after front is reached endl; for ( i = 0; i 10; i+) cout first_list.current() ; first_list.previous_position(); cout endl endl; if ( first_list.at_front() cout first_list is at front endl; if ( first_list.at_end() cout first_list is at end endl; cout endl; cout first_list from front to end endl; cout extra first_list.item_n(4) s on the end signal thatn next_position does nothing after end is reached endl; for ( i = 0; i 10; i+) cout first_list.current() ; first_list.next_position(); cout endl endl; cout first_list from item 0 to item 4 endl; for ( i = 0; i 5; i+) cout first_list.item_n(i) ; cout endl endl; cout first_list from item 4 to item 0 = 0; i-) cout first_list.item_n(i) ; cout endl endl; if ( first_list.at_front() cout first_list is at front endl; if ( first_list.at_end() cout first_list is at end endl; cout endl; cout resetting first_list endl; first_list.reset(); if ( first_list.at_front() cout first_list is at front endl; if ( first_list.at_end() cout first_list is at end endl; cout endl; cout length of first_list first_list.length() endl endl; List second_list(5); for ( char ch = A; ch A + 5; ch+ ) second_list.add( ch ); cout second_list = n second_list endl; if ( second_list.at_front() cout second_list is at front endl; for ( ch = 0; ch 5; ch+) cout second_list.current() ; second_list.previous_position(); cout endl; second_list.erase(); second_list.add(A); second_list.add(B); second_list.add(C); cout second_list = n second_list; return 0;A typical run follows:first_list is empty just after constructionfirst_list (declared to be size 5) is full after adding 5 integersfirst_list, using operator is 2018161412first_list is at endfirst_list from end to front extra 20s on the end signal that previous_position does nothing after front is reached12 14 16 18 20 20 20 20 20 20 first_list is at frontfirst_list from front to end extra 12s on the end signal that next_position does nothing after end is reached20 18 16 14 12 12 12 12 12 12 first_list from item 0 to item 4 20 18 16 14 12 first_list from item 4 to item 0 12 14 16 18 20 first_list is at endresetting first_listfirst_list is at frontlength of first_list 5second_list = ABCDEE D C B A second_list = ABC3. No Solution is provided.4. Redo Project 3 Chapter 7 (delete_repeats) as template function.No solution is provided.5. Redo Project 6 Chapter 7 (Insertion sort) as template functionNotes only are provided for this problem.Insertion sort and Selection sort are related. Both maintain two subarrays of the array to be sorted. One subarray contains already sorted items, the other contains not-yet-sorted items. The not-yet-sorted subarray is initially the array to be sorted. The sorted subarray is initially empty. Insertion Sort takes an element from the unsorted subarray then decides where in the already sorted array this item should be inserted. Selection sort selects the item from the unsorted subarray that should be placed at the end of the already-sorted subarray.The insertion sort needs a search routine to find where in the sorted array to insert the next item. The selection sort needs a find_max (or perhaps find_min) routine to select the item in the unsorted subarray that should be place at the end of the sorted subarray.Consequently, the problem of writing either of these template sort routines becomes writing template functions, namely, a sort function, a find_max or search function, and a template swap utility routine. We already have a template swap in the text. Once the sort function is written, the find_max or search function is easy to write. 6. Template Iterative binary SearchWrite a template version of the iterative binary search from Display 13.8. Specify and discuss requirements on the template parameter type. Problems 6 and 7 are very closely related. I have done both in one code file. These are listed with the solution for Programming Problem 7.7. Template Recursive Binary SearchWrite a template version of the iterative binary search from Display 13.6. Specify and discuss requirements on the template parameter type. NOTE - I discovered an annoying non-standard issue in VC+ templates. VC+6.0 requires that identifiers for function parameter in a template must be present in the template declaration, and the identifiers must be the same as the identifiers in the actual template definition. Otherwise, any identifiers in the template implementation are treated as either undefined or redefined. This apparently should not be required, and is not required by Borland 5.5 compiler, nor is it required by the GNU g+ compiler, versions 2.9.5 and 3.0.Discussion of requirements for the template parameter type are embedded in the code as comments./#6 Template Iterative and /#7 Recursive Binary Search Template /Write a template version of the iterative recursive /binary search from Display 13.6. Discuss requirements on /the template parameter types. #include using std:cin;using std:cout;using std:endl;const int ARRAY_SIZE = 10;templatevoid recBinSrch(const T a, int first, int last, int key, bool& found, int& location);/Precondition: Type T must support = = and /afirst through alast are sorted in increasing order./Postcondition: /if key is not one of the values afirst through alast, /