I need create a binary search that computes and prints the average search cost.
This is what I have so far..the last part is my sortList. If it is incorrect please help :P
Thanks
Code:
#include <stdio.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define MAXNAMESIZE 32
#define MAXLISTSIZE 1000
#define TEST TRUE
int readList(char[][MAXNAMESIZE]);
void printList(char[][MAXNAMESIZE], int);
void testSequentialSearch(char[][MAXNAMESIZE], int);
void writeList(char[][MAXNAMESIZE], int);
int sequentialSearch(char[][MAXNAMESIZE], int, char[]);
int main() {
int listSize;
char nameList[MAXLISTSIZE][MAXNAMESIZE];
listSize = readList(nameList);
if (TEST) printList(nameList, listSize);
testSequentialSearch(nameList, listSize);
if (TEST) printList(nameList, listSize);
writeList(nameList, listSize);
return 0;
}
int readList(char nameList[][MAXNAMESIZE]) {
FILE *fp;
int length, listSize = 0;
char name[MAXNAMESIZE];
fp = fopen("names.txt", "r");
while (fgets(name, MAXNAMESIZE, fp) != NULL) {
length = strlen(name);
if (name[length-1]=='\n') name[length-1] = '\0';
if (strlen(name)>0) {
strcpy(nameList[listSize],name);
listSize = listSize + 1;
}
}
fclose(fp);
return listSize;
}
void printList(char nameList[][MAXNAMESIZE], int listSize) {
int i;
if (listSize == 0) {
printf("Empty list\n");
return;
} else {
for (i=0; i<listSize; i++) {
printf("%s\n",nameList[i]);
}
}
return;
}
void testSequentialSearch(char nameList[][MAXNAMESIZE], int listSize) {
int i, searchCost = 0;
float aveSearchCost;
for (i=0; i<listSize; i++) {
searchCost = searchCost + sequentialSearch(nameList, listSize, nameList[i]);
}
if (searchCost == 0) aveSearchCost = 0;
else aveSearchCost = (float) searchCost/ (float) listSize;
printf("Average cost of sequential search = %f\n",aveSearchCost);
return;
}
int sequentialSearch(char nameList[][MAXNAMESIZE], int listSize, char targetValue[]) {
int i, cost = 0;
if (listSize == 0) {
printf("Search failed.\n");
} else {
for (i=0; i<listSize; i++) {
cost = cost + 1;
if (strcmp(nameList[i], targetValue)==0) {
return cost;
}
}
printf("Search failed.\n");
}
return cost;
}
void writeList(char nameList[][MAXNAMESIZE], int listSize) {
FILE *fp;
int i = 0;
fp = fopen("sortedNames.txt","w");
for (i=0; i<listSize; i++) {
fprintf(fp,"%s\n",nameList[i]);
}
fclose(fp);
return;
}
void insertionSort(int numbers[], int array_size)
{
int i, j, index;
for (i=1; i < array_size; i++)
{
index = numbers[i];
j = i;
while ((j > 0) && (numbers[j-1] > index))
{
numbers[j] = numbers[j-1];
j = j - 1;
}
numbers[j] = index;
}
}