Question

You will be reading in 3 files in the program. One will contain a list of 1000 words in unsorted order. The second file will contain 1000 words in sorted order. The final file will contain 20 words to be searched for.

The main program has been written for you. You will be implementing three functions:

bool readWords(string array[], int size, string fileName);

int linearSearch(string wordToFind, const string words[], int size);

int binarySearch(string wordToFind, const string words[], int size);

The readWords function will read in from file “fileName” into the string array “array”. There will be “size” entries in the input file. If the file exists the function will read in the file and return true. If the file does not exist the function will return false.

The linearSearch function will use the linear search to see if “wordToFind” in in the array “words”. The size of the words array is “size”. As with the example in the text book your function will return -1 if the item is not found and the index in the array if it is found.

The binarySearch function will use a binary search to see If “wordToFind” exists in the array “words”. As with the example in the text book your function will return -1 if the item is not found and the index in the array if it is found.

The program should be named “homework1.cpp”.

A template for the assignment is on eLearning. The file of words to be found is named "findWords.txt", there are 20 words in this file. The file of unsorted words is "unsortedWords.txt" and the file of the sorted words is "sortedWords.txt". There are 1000 words in the "unsortedWords.txt" file and there are 1000 words in the "sortedWords.txt" file.

Note: The code in the text book for calculating the middle for the binary search is: middle = (first + last) / 2;

This will cause an overflow error some very big arrays (but not for the program you are writing).

Instead you should use: middle = first + (last - first) / 2;

Answer 1

If you have any doubts, please give me comment...

#include <iostream>

#include <string>

#include <fstream>

using namespace std;

bool readWords(string array[], int size, string fileName);

int linearSearch(string wordToFind, const string words[], int size);

int binarySearch(string wordToFind, const string words[], int size);

int main()

{

string words[20], sortedWords[1000], unsortedWords[1000];

if(!readWords(words, 20, "findWords.txt")){

cout<<"Unable to open file"<<endl;

}

if(!readWords(sortedWords, 1000, "unsortedWords.txt")){

cout<<"Unable to open unsortedWords.txt file"<<endl;

}

if(!readWords(unsortedWords, 1000, "sortedWords.txt")){

cout<<"Unable to open sortedWords.txt file"<<endl;

}

return 0;

}

bool readWords(string array[], int size, string fileName)

{

ifstream in;

in.open(fileName.c_str());

if (in.fail())

return false;

for (int i = 0; i < size; i++)

cin >> array[i];

return true;

}

int linearSearch(string wordToFind, const string words[], int size)

{

for (int i = 0; i < size; i++)

{

if (words[i] == wordToFind)

return i;

}

return -1;

}

int binarySearch(string wordToFind, const string words[], int size)

{

int first = 0, last = size - 1;

while (first <= last)

{

int middle = first + (last - first) / 2;

if (words[middle] == wordToFind)

return middle;

if (words[middle] < wordToFind)

first = middle + 1;

else

last = middle - 1;

}

return -1;

}