#include <iostream>
#include <ctime>
#include <iomanip>
#include <cstdlib>
using namespace std;
const int MAX_NUMBER_LIST = 511;
const int DEFAULT_SEED = 5000;
const int MAX_TEST_VALUE = 50;
const int SEED = 11013;
const int DEFAULT_FILL_IN_NUMBERS = 43;
enum techsType{linear, binary};
void PrintTestValues(const int list[],
const int test[],
int numberOfElements,
techsType method,
int& comparision);
void FillMainList(int list[]);
void PrintNameHeader(ostream& oss);
void FillTestArray(const int list[], int test[]);
void PrintArray(const int ary[], int size);
void SelectionSort(int list[], int size);
int LinearSearch(const int list[], int value, int& comps);
int BinarySearch(const int list[], int value, int& comps);
int SearchForExistingElement(const int list[], int value, int range);
void GenerateRandomNumber(int list[], int numElems);
void SwapTwoItems(int& left, int& right);
void FillMainList(int list[])
{
bool existed;
int scan;
int value;
int index = 0;
while(index < MAX_NUMBER_LIST)
{
value = rand()%5000;
existed = false;
for(scan = 0; scan < index; ++scan)
{
if(value == list[scan])
existed = true;
}
if(existed == false)
{
list[index] = value;
index++;
}
}
}
void PrintTestValues(const int list[],
const int test[],
int numberOfElements,
techsType method,
int& comps)
{
cout << "Test value" << setw
(16) << "Result" << setw(16)
<< "Number of Comparisons" << endl;
if(method == linear)
{
for(int x = 0; x < numberOfElements; ++x)
{
cout << test
[x
] << setw
(16); if(LinearSearch(list, test[x], comps) == -1)
else
cout << setw
(16) << comps
; comps = 0;
}
}
else
{
for(int x = 0; x < numberOfElements; ++x)
{
cout << test
[x
] << setw
(16);
if(BinarySearch(list, test[x], comps) == -1)
else
cout << setw
(16) << comps
; comps = 0;
}
}
}
int BinarySearch(const int list[], int value, int& comps)
{
int first = 0,
last = MAX_NUMBER_LIST - 1,
middle,
position = -1;
bool found = false;
while(!found && first <= last)
{
comps++; //increast the number times searching
middle = (first + last)/2;
if(list[middle] == value)
{
found = true;
position = middle;
}
else if(list[middle] > value)
last = middle - 1;
else
first = middle + 1;
}
return position;
}
void PrintArray(const int ary[], int size)
{
cout << setw
(6) << ary
[0]; for(int index = 1; index < size; index++)
{
if((index % 12) == 0)
cout << setw
(6) << ary
[index
]; }
}
void FillTestArray(const int list[], int test[])
{
int index;
int scan;
int value;
bool existed = false;
for(index = 0; index < DEFAULT_FILL_IN_NUMBERS; ++index)
{
test[index] = list[index * 12];
}
do
{
value = rand() % 5000;
for(scan = 0; scan < index; ++scan)
{
if(value == test[scan])
existed = true;
}
if(existed == false)
{
test[index] = value;
index++;
}
}while(index < MAX_TEST_VALUE);
}
int SearchForExistingElement(const int list[], int value, int range)
{
int index = 0;
int position = -1;
bool found = false;
while(index < range && !found)
{
if(list[index] == value)
{
found = true;
position = index;
}
index++;
}
return position;
}
int LinearSearch(const int list[], int value, int &comps)
{
int index = 0;
int position = -1;
bool found = false;
while(index < MAX_NUMBER_LIST && !found)
{
comps++; //increast the number times searching
if(list[index] == value)
{
found = true;
position = index;
}
index++;
}
return position;
}
void SelectionSort(int list[], int numElems)
{
int minIndex, minValue;
for(int start = 0; start < numElems - 1; ++start)
{
minIndex = start;
minValue = list[start];
for(int index = start + 1; index < numElems; ++index)
{
if(list[index] < minValue)
{
minValue = list[index];
minIndex = index;
}
}
list[minIndex] = list[start];
list[start] = minValue;
}
}
void SwapTwoItems(int& left, int& right)
{
int temp = left;
left = right;
right = temp;
}
int main()
{
int list[MAX_NUMBER_LIST];
int test[MAX_TEST_VALUE];
char answer;
int numberTest;
int comparision = 0;
cout << "Do you want to use random values (versus default values)? [y/n] ";
if(answer == 'Y' || answer == 'y')
{
srand(static_cast<unsigned>(time(0)));
}
else
{
srand(static_cast<unsigned>(SEED));
}
FillMainList(list);
cout << "How many values do you want to test ? [1-50] ";
FillTestArray(list, test);
cout << "\n\nOriginal array : " << endl
; PrintArray(list, MAX_NUMBER_LIST);
cout << "\n\nOriginal test-arry : " << endl
; PrintArray(test, numberTest);
//cout << "\n\nBefore sort linear search performance : " << endl;
//PrintTestValues(list, test, numberTest, linear, comparision);
cout << "\n\nBefore sort binary search performance : " << endl
; PrintTestValues(list, test, numberTest, binary, comparision);
/*
SelectionSort(list, MAX_NUMBER_LIST);
cout << "\n\nAfter sort linear search performance : " << endl;
PrintTestValues(list, test, numberTest, linear, comparision);
cout << "\n\nAfter sort binary search performance : " << endl;
PrintTestValues(list, test, numberTest, binary, comparision);
*/
return 0;
}
Trả lời cùng với trích dẫn
Power Member
Help !!!! ^_^
!
Quyền hạn của bạn
