1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
|
Name.cpp
#include "stdafx.h"
#include "names.h"
FemaleNames::FemaleNames()
{
this->rank = 0;
this->name = "";
}
//accessor methods of class FemaleNames
int FemaleNames::getRank()
{
return this->rank;
}
string FemaleNames::getName()
{
return this->name;
}
//mutator methods of class FemaleNames
void FemaleNames::setRank(int rank)
{
this->rank = rank;
}
void FemaleNames::setName(string name)
{
this->name = name;
}
Name.h
#ifndef names_H
#define names_H
#include<iostream>
#include<string>
using namespace std;
class FemaleNames
{
private:
int rank;
string name;
public:
FemaleNames();
int getRank();
string getName();
void setRank(int rank);
void setName(string name);
};
#endif
Main.cpp
#include "stdafx.h"
#include "names.h"
#include<iostream>
#include <fstream>
#include <string>
#include <time.h>
#include<ctime>
using namespace std;
void sortNames(FemaleNames *fnames, int count);
int linearSearch(FemaleNames *fnames, string searchKey, int count);
int binarySearch(FemaleNames *fnames, string searchKey, int count);
string toUpper(string name);
int main()
{
FemaleNames fn[1000];
string name;
int value;
int count = 0;
string searchKey;
ifstream infile("CommonFemaleNames.txt");
if (infile)
{
infile >> value;
infile >> name;
fn[count].setName(name);
fn[count].setRank(value);
while (!infile.eof())
{
count++;
infile >> value;
infile >> name;
fn[count].setName(name);
fn[count].setRank(value);
}
}
infile.close();
sortNames(fn, count);
for (int i = 0; i <= count; i++)
cout << fn[i].getName() << "\t" << fn[i].getRank() << endl;
clock_t startClock, finishClock;
double timeCount;
cout << "Enter search key: " << endl;
cin >> searchKey;
searchKey = toUpper(searchKey);
cout << searchKey << endl;
startClock = clock() / 1000;
int pos1 = linearSearch(fn, searchKey, count);
finishClock = clock() / 1000;
timeCount = finishClock - startClock;
if (pos1 != -1)
cout << "The key is found at: " << pos1 << endl;
else
cout << "Element not found" << endl;
cout << "The time taken to find the key using linear search is: " << timeCount << " ns." << endl;
startClock = clock() / 1000;
int pos2 = binarySearch(fn, searchKey, count);
finishClock = clock() / 1000;
timeCount = finishClock - startClock;
if (pos2 != -1)
cout << "The key is found at: " << pos2 << endl;
else
cout << "Element not found" << endl;
cout << "The time taken to find the key using binary search is: " << timeCount << " ns." << endl;
system("pause");
return 0;
}
string toUpper(string name)
{
for (int i = 0; i<name.size(); i++)
{
name[i] = toupper(name[i]);
}
return name;
}
void sortNames(FemaleNames *fnames, int count)
{
FemaleNames temp;
for (int i = 0; i<count; i++)
{
for (int j = i + 1; j <= count; j++)
{
if (fnames[i].getName().compare(fnames[j].getName())>0)
{
temp = fnames[i];
fnames[i] = fnames[j];
fnames[j] = temp;
}
}
}
}
int linearSearch(FemaleNames *fnames, string searchKey, int count)
{
for (int i = 0; i <= count; ++i)
{
if (fnames[i].getName().compare(searchKey) == 0)
return i;
}
return -1;
}
int binarySearch(FemaleNames *fnames, string searchKey, int count)
{
int first = 0, last = count + 1, middle, position = -1;
bool found = false;
while (!found && first < last)
{
middle = (first + last) / 2;
if ((fnames[middle].getName().compare(searchKey)) == 0)
{
return middle;
}
else if ((fnames[middle].getName().compare(searchKey)) > 0)
last = middle - 1;
else
first = middle + 1;
}
return -1;
}
|