prg3_1.cpp

数据结构c++语言描述stl版 威廉兄弟的好书,值得看,这是配书代码

// File: prg3_1.cpp
// the program compares the efficiency of the sequential
// and binary search by timing algorithm execution using the
// timer class. two integer arrays list1 and list2
// of size ARRAY_SIZE are initialized with the same random
// integers in the range 0 to 999,999. initialize the array
// targetList having TARGET_SIZE elements to contain other
// random numbers in the same range. time the selection sort
// as it sorts list2 and output the result. using the
// elements in array targetList as target values for the
// sequential and binary searches, time each algorithm and
// output the results

#include <iostream>

#include "d_search.h"	// generic sequential and binary searches
#include "d_sort.h"		// generic selection sort
#include "d_random.h"	// random number generation
#include "d_timer.h"		// time events

using namespace std;

int main()
{	const int ARRAY_SIZE = 100000, TARGET_SIZE = 50000;

	// arrays for the search
   int list1[ARRAY_SIZE], list2[ARRAY_SIZE], targetList[TARGET_SIZE];
	int i;

	// t used for timing the search algorithms
	timer t;
	// random number object
	randomNumber rnd;

	// initialize the arrays with random numbers in the
   // range 0 to 999,999 
   for (i = 0; i < ARRAY_SIZE; i++)
		list1[i] = list2[i] = rnd.random(1000000);

	// initialize targetList with random numbers in the
   // same range 0 to 999,999 
	for (i=0;i < TARGET_SIZE; i++)
		targetList[i] = rnd.random(1000000);

	// sort list2
   cout << "Timing the Selection Sort" << endl;
	t.start();		// start timer
	selectionSort(list2,ARRAY_SIZE);
	t.stop();		// stop timer
	cout << "Selection Sort takes " << t.time()
		  << " seconds." << endl;

   cout << endl << "Timing the Sequential Search" << endl;
	t.start();		// start timer
	// perform sequential search with elements from list2
 	for (i = 0; i < TARGET_SIZE; i++)
		seqSearch(list1,0,ARRAY_SIZE,targetList[i]);
	t.stop();		// stop timer
	cout << "Sequential Search takes " << t.time()
		  << " seconds." << endl;

	cout << endl << "Timing the Binary Search" << endl;
	t.start();		// start timer
	// perform binary search with elements from list1
 	for (i = 0; i < TARGET_SIZE; i++)
		binSearch(list2,0,ARRAY_SIZE,targetList[i]);
	t.stop();		// stop timer
	cout << "Binary Search takes " << t.time()
		  << " seconds." << endl;

	return 0;
}

/*
Run:

Timing the Selection Sort
Selection Sort takes 126.912 seconds.

Timing the Sequential Search
Sequential Search takes 132.889 seconds.

Timing the Binary Search
Binary Search takes 0.08 seconds.
*/