test.cpp

来自「数据结构与程序设计教材源码 数据结构与程序设计教材源码」· C++ 代码 · 共 112 行

 
void print_out(char *comment, float t, int comp_ct, int searches)
{
   float average;
   cout << comment << " Search Statistics: " << endl;
   cout << " Time for " << searches << " comparisons was " << t << endl;
   average = (( float ) comp_ct) / (( float ) searches);
   cout << " Average number of comparisons per search was " << average << endl;
}
 
void test_search(int searches, Ordered_list &the_list)
/* 
 
Pre:   None.
Post: The number of key comparisons and CPU time for a searching method
      have been calculated.
Uses: Methods of the classes Ordered_list, Random, Timer,
and an output function print_out.
 
*/
{
   int list_size = the_list.size();
   if (searches <= 0 || list_size < 0) {
      cout << " Exiting test: " << endl
           << " The number of searches must be positive." << endl
           << " The number of list entries must exceed 0." << endl;
      return;
 
   }

   int i, target, found_at;
   Random number;
   Timer clock;

   cout << "\n\nRecursive Binary Search 1" << endl;
   Key::comparisons = 0;
   for (i = 0; i < searches; i++) {
      target = 2 * number.random_integer(0, list_size - 1) + 1;
      if (run_recursive_binary_1(the_list, target, found_at) == not_present)
         cout << "Error: Failed to find expected target " << target << endl;
   }
   print_out("Successful", clock.elapsed_time(), Key::comparisons, searches);

   Key::comparisons = 0;
   clock.reset();
   for (i = 0; i < searches; i++) {
      target = 2 * number.random_integer(0, list_size);
      if (run_recursive_binary_1(the_list, target, found_at) == success)
         cout << "Error: Found unexpected target " << target
              << " at " << found_at << endl;
   }
   print_out("Unsuccessful", clock.elapsed_time(), Key::comparisons, searches);

   cout << "\n\nNon-recursive Binary Search 1" << endl;
   Key::comparisons = 0;
   for (i = 0; i < searches; i++) {
      target = 2 * number.random_integer(0, list_size - 1) + 1;
      if (binary_search_1(the_list, target, found_at) == not_present)
         cout << "Error: Failed to find expected target " << target << endl;
   }
   print_out("Successful", clock.elapsed_time(), Key::comparisons, searches);

   Key::comparisons = 0;
   clock.reset();
   for (i = 0; i < searches; i++) {
      target = 2 * number.random_integer(0, list_size);
      if (binary_search_1(the_list, target, found_at) == success)
         cout << "Error: Found unexpected target " << target
              << " at " << found_at << endl;
   }
   print_out("Unsuccessful", clock.elapsed_time(), Key::comparisons, searches);

   cout << "\n\nRecursive Binary Search 2" << endl;
   Key::comparisons = 0;
   for (i = 0; i < searches; i++) {
      target = 2 * number.random_integer(0, list_size - 1) + 1;
      if (run_recursive_binary_2(the_list, target, found_at) == not_present)
         cout << "Error: Failed to find expected target " << target << endl;
   }
   print_out("Successful", clock.elapsed_time(), Key::comparisons, searches);

   Key::comparisons = 0;
   clock.reset();
   for (i = 0; i < searches; i++) {
      target = 2 * number.random_integer(0, list_size);
      if (run_recursive_binary_2(the_list, target, found_at) == success)
         cout << "Error: Found unexpected target " << target
              << " at " << found_at << endl;
   }
   print_out("Unsuccessful", clock.elapsed_time(), Key::comparisons, searches);

   cout << "\n\nNon-recursive Binary Search 2" << endl;
   Key::comparisons = 0;
   for (i = 0; i < searches; i++) {
      target = 2 * number.random_integer(0, list_size - 1) + 1;
      if (binary_search_2(the_list, target, found_at) == not_present)
         cout << "Error: Failed to find expected target " << target << endl;
   }
   print_out("Successful", clock.elapsed_time(), Key::comparisons, searches);

   Key::comparisons = 0;
   clock.reset();
   for (i = 0; i < searches; i++) {
      target = 2 * number.random_integer(0, list_size);
      if (binary_search_2(the_list, target, found_at) == success)
         cout << "Error: Found unexpected target " << target
              << " at " << found_at << endl;
   }
   print_out("Unsuccessful", clock.elapsed_time(), Key::comparisons, searches);

}