Question

This lab is to give you more experience with C++ Searching and Sorting Arrays

Given a file with data for names and marks you will read them into two arrays You will then display the data, do a linear search and report if found, sort the data, do a binary search. Be sure to test for found and not found in your main program.

1. Read Data

Write a function that reads in data from a file using the prototype below. The function can define and open the file, read the names and marks into the arrays and keep track of how many names there are in numElts, and then closes the file. The list of names and marks can be found at the end of the lab and copied into a text file.

void getNames(string names[], int marks[], int& numElts);

5. Display Data

Write a function to display the contents of names and marks using the prototype given below.

void displayData(const string names[], const int marks[], int numElts);

2. Linear Search

Write the searchList function given the prototype below so that it searches for a given name. The functions returns and int which is the index of the name found.

The main program will decide if -1 is returned then it will say name is not found otherwise it will write out the name and the mark for that name.

int linearSearch(const string list[], int numElts, string value);

3. Selection Sort

Write the selectionSort given the prototype below so that it sorts by name in ascending order. Be sure to accept both arrays name and mark for sorting purposes.

void selectionSort(string name[], int marks[], int numElts);

4. Binary Search

Write the binarySearch function given the prototype below so that it searches for a given name.The functions returns and int which is the index of the name found.

The main program will decide if -1 is returned then it will say name is not found otherwise it will write out the name and the mark for that name.

int binarySearch(const stringt array[], int numElts, string value);

5. Main Function

Write a main function that declares the names, marks, number of elements as well as the value to be searched for and the index of the returned function calls.

• Read and display the contents of names and marks.
• Ask the user for a name and using the linear search return the index to the user. If -1 is returned then the name is not in the file. Otherwise write out the name and mark for that student.
• Sort the arrays and write them out.
• Ask the user for a name to search for. This time use the binarySearch to return -1 or an index. Display the student’s name and mark if found.
• Test your program for found and not found for each type of search.

void getNames(string names[], int marks[], int& numElts);

int linearSearch(const string names[], int numElts,string who);

int binarySearch(const string names[], int numElts,string who);

void selectionSort(string names[], int marks[],int numElts);

void displayData(const string names[], const int marks[], int numElts);

const int NUM_Names = 20;

int main()

{

      string names[NUM_NAMES];

int marks[NUM_NAMES];

      int numElts;

int index;

      string searchWho;

// Function calls here

      return 0;

}

File for names and marks:

Collins,Bill 80

Smith,Bart 75

Allen,Jim 82

Griffin,Jim 55

Stamey,Marty 90

Rose,Geri 78

Taylor,Terri 56

Johnson,Jill 77

Allison,Jeff 45

Looney,Joe 89

Wolfe,Bill 63

James,Jean 72

Weaver,Jim 77

Pore,Bob 91

Rutherford,Greg 42

Javens,Renee 74

Harrison,Rose 58

Setzer,Cathy 93

Pike,Gordon 48

Holland,Beth 79

Answer 1

#include<sstream>

#include<string>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<fstream>

using namespace std;

//initializing this value to 20 as we have 20

int NUM_NAMES = 20;

void getNames(string names[], int marks[], int& numElts)

{

string temp[2],line="";

int t1=0;

ifstream myfile("file.txt");

if (myfile.is_open())

{

while(getline (myfile,line) )

{

;

for(int i=0;i<line.length();i++)

{

temp[t1]=temp[t1]+line.at(i);

if(line.at(i)==' ')

t1++;

}

names[numElts]=temp[0].substr(0,temp[0].length()-1);

marks[numElts++] = atoi(temp[1].c_str());

line="";

t1=0;

temp[0]="";

temp[1]="";

}

}

}

int linearSearch(string names[], int numElts, string value)

{

int val=-1;

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

if(value==names[i])

val=i;

return val;

}

int binarySearch(string names[], int numElts, string value)

{

//initializing three variables to get the student

int middle_val,

begin_val=0,

end_val=numElts;

//fetches the middle_val

while(begin_val<end_val)

{

middle_val=(begin_val+end_val)/2;

if( value.compare(names[middle_val])<0)

end_val=middle_val-1;

else if( value.compare(names[middle_val])>0)

begin_val=middle_val+1;

else if(value.compare(names[middle_val])==0)

return middle_val;

}

return -1;

}

void selectionSort(string names[], int marks[], int numElts)

{

int n = numElts;

int i,j,index;

int element1=0;

string element="";

for(i=n-1;i>0;i--)

{

index=0;

element=names[0];

element1=marks[0];

for(j=0;j<=i;j++)

{

if((element.compare(names[j]))<0)

{

element=names[j];

element1=marks[j];

index=j;

}

}

names[index]=names[i];

names[i]=element;

marks[index]=marks[i];

marks[i]=element1;

}

}

void displayData(string names[], const int marks[], int numElts)

{

//printing the details of student from 0 to end

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

{

cout<<"\nName: "<<names[i]<<" | "<<"Marks: "<<marks[i];//printing the details

}

cout<<"\n";

}

int main()

{

//declarations

string names[NUM_NAMES];

int marks[NUM_NAMES];

//initializing the elements

int numElts=0;

int index=0;

string searchWho="";

//this method is used to retrieve the data from list

getNames(names,marks,numElts);

cout<<"\nEnter the name of the person from the list to be searched:";

cin>>searchWho;

//this method is used to retrieve the searched info

index = linearSearch(names,numElts,searchWho);

if(index==-1)

cout<<"\nName not found";

else

//if the name is found below details are retrieved

cout<<"\nName: "<<names[index]<<" | "<<"Marks: "<<marks[index]<<"\n";

//Ascending order sort of the list

selectionSort(names,marks,numElts);

cout<<"\nEnter the name of the person from the list to be searched:";

cin>>searchWho;

//this method is used to retrieve the searched info

index = binarySearch(names,numElts,searchWho);

if(index==-1)

cout<<"\nElement not found";

else

cout<<"\nName: "<<names[index]<<" | "<<"Marks: "<<marks[index]<<"\n";

cout<<"\nBelow sorted Data after sorting:\n";

//this method is used to display info

displayData(names,marks,numElts);

return 1;

}