hello everyone,
I wrote some code on binary search in algorithms using c but here is my problem:
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <ctype.h>
/*
TASK: Demo about static, linear data handling.
Four basic operations are exercised:
1) find
2) insert
3) modify
4) delete
5) show
6) quit
7) ? meaning help
QUESTIONS, :
Task of this year. Do firstly following:
1) Modifying is still missing. Program it now. Also find by name and ask how the ID shoudl
be changed!
2)later....
3) Add the third column in the students' description, the gender. It can be described as
char cGender[M] which can have values '? ' or '? ' for women and men or 1 and 0.
4) Change the full program to work with studend IDs, not with the names!
5) Add a new function (command like (r)everse) to sort the data in reverse order and
warn that after that it would no more work without sorting it back. After that show, sort it
back into ascending order.
6) Add a new filed into the program. It tells the students' age in years. Also int iYears[N];
It must become visible when showing or storing/retreaving the lists.
7) Disable same student ID's in the generation phase.
----------------------------------------------------------------------------------
*/
//GLOBAL CONSTANT
#define M 40 //max items
#define CMDS 7 //how many commands programmed
//PROTOTYPES
int GetAnsw( char []);
int ShuttleSortN(int [], char [][16], int);
int ShowTable(int [], char [][16], int);
int ShowCommands(char [][10], int);
int FindSequentially(char [], char [][16], int , int *);
int DoBinarySearch(char [], char [][16], int, int *);
int main()
{
int N= M - 10; //the rest 10 % of the table area is in reserve for insertions
int i, j;
time_t Start1, Finish1;
double dDuration1;
FILE *InputChannel;
FILE *OutputChannel;
char OutputFile[]= "C:/users/students.DAT";
char InputFile[]= "C:/users/students.DAT";
int InputSuccessful= 1;
int OutputSuccessful= 1;
char cFirstName[28][16]={
{"Adewale"},
{"Oluyemi"},
{"Emma"},
{"Okoyomo"},
{"Seyi"},
{"Rita"},
{"Lekan"},
{"Sandra"},
{"John"},
{"Kenny"},
{"Elijah"},
{"Olumide"},
{"oribogunje"},
{"Funsho"},
{"Temilehin"},
{"Olu-Osho"},
{"asha"},
{"Bimbo"},
{"Ade"},
{"Adeokin"},
{"Adeojo"},
{"Agboola"},
{"Iyabo"},
{"Yinka"},
{"Dayo"},
{"Toyin"},
{"Wande"},
{"Bimpe"}
};
char czCommand[80];
char czCmdHelp[CMDS][10]={
"(D)el",
"(F)ind",
"(I)ns",
"(M)od",
"(S)how",
"(Q)uit",
"? help"
};
char czCmds[CMDS][10]={
"Del",
"Find",
"Ins",
"Mod",
"Show",
"Quit",
"?"
};
char name[20], answ[20];
int iStudID[M];
char czStudentName[M][16];
int iNameL;
int iFound;
int iRetCode= 0;
//Is there anything in the input file
printf ("\nGive input file name if any (=CR): ");
GetAnsw(InputFile);
if (strcmp(InputFile, "")== 0)
InputChannel= NULL;
else{
InputChannel= fopen(InputFile,"tr");
}
if (InputChannel == NULL){
printf ("\nInput %s substituted by randomly generated records!", InputFile);
//fill the vectors with arbitrary values for names and ID-codes
for(i= 0; i< N; i++){
iStudID[i]= rand() % (N*100) + 10000; //for N= 10, rand. values => 10000.. 19999
//first name plus a acharacter for surname
strcpy(czStudentName[i], cFirstName[rand()% 28]);
iNameL= strlen(czStudentName[i]);
czStudentName[i][iNameL]= ' ';
czStudentName[i][iNameL + 1]= rand() % 24 + 'A';
czStudentName[i][iNameL + 2]= '.';
czStudentName[i][iNameL + 3]= 0; //the binary ending
}
}
else //reading the data from the input file without generating it
{
printf ("\nInput records will be taken from the file: %s!", InputFile);
i= 0;
iRetCode= fscanf(InputChannel, "%d %s", &iFound, name);
printf("\n%d. record: %d %s", i, iFound, name);
while ((iRetCode != EOF) && (i < N)){
iStudID[i]= iFound;
strcpy(czStudentName[i], name);
i++;
iRetCode= fscanf(InputChannel, "%d %s", &iFound, name);
printf("\n%d. record: %d %s", i, iFound, name);
}
N= i;
printf("\nRed %d. records!", N);
fclose(InputChannel);
}
//original data:
printf("\nTEST: Unsorted data:\n");
ShowTable(iStudID, czStudentName, N);
//Sort algorihtms used for >= 4 items:
printf("\n\nTEST: Sorted in ascending order according to name:\n");
iRetCode= ShuttleSortN(iStudID, czStudentName, N);
ShowTable(iStudID, czStudentName, N);
//Eternal loop to handle all operations:
while (1){
printf("\nGive command: ");
GetAnsw(czCommand);
//we also homogenize lowercases and uppercases
czCommand[0]= toupper(czCommand[0]);
//printf("\nTEST: Your command was: %s", czCommand);
if (strcmp(czCmds[0],czCommand)==0 ||
czCmds[0][0]==czCommand[0]){ //del
printf("\nDeleting: which name? ");
GetAnsw(name);
//It would be more "elegant" if this deletion would also use
//the newest FindSequentially-subroutine...
for (i=0; i< N; i++){
//printf("\nTEST: Comparing %s <> %s", name, cFirstName[i]);
if (strcmp(name, czStudentName[i])==0){
//lift the rest of the table higher to overlap the deleted
for (j= i; j<N-1; j++){
strcpy(czStudentName[j],czStudentName[j+1]);
iStudID[j]= iStudID[j+1];
};
N= N-1;
printf("\n%s deleted! Only %d records left!", name, N);
//ShowTable(iStudID, czStudentName, N);
break;
}
else if (i== N- 1) //at the end
printf("\nCould not delete an inexistent record!");
}
}
else if (strcmp(czCmds[1],czCommand)==0 || czCmds[1][0]==czCommand[0]) {
//find
printf("\nFinding: Give the name to find: ");
GetAnsw(name);
printf("\nDo you perform (s)equential or (b)inary search? ");
GetAnsw(answ);
answ[0]= toupper(answ[0]);
if (answ[0]=='B') //also binary search
DoBinarySearch(name, czStudentName, N, &iFound);
else
FindSequentially(name, czStudentName, N, &iFound);
if (iFound >= 0)
printf("\nFound %s with ID: %5d\n",
czStudentName[iFound], iStudID[iFound]);
else
printf("\nNot found!\n");
}
else if (strcmp(czCmds[2],czCommand)==0 ||
czCmds[2][0]==czCommand[0]) //insert
{
//printf("\nNot ready to insert...");
printf("\nInserting: Give the name: ");
GetAnsw(name);
//printf("... repeated: %s ", name);
FindSequentially(name, czStudentName, N, &iFound);
//printf("\nreturn code from finding: %d", iFound);
if (iFound > 0){ //old one exists, no insert
printf("\nAlready existing %s with ID: %5d\n",
czStudentName[iFound], iStudID[iFound]);
}
else if (iFound == -9999)
//no found, the proper place for it is at the end
{
//.... do your work here
strcpy(czStudentName[N], name);
printf("\nGive the ID: ");
GetAnsw(name);
iStudID[N]= atoi(name);
N= N +1;
printf ("\nInserted! There are now %d records!", N);
}
else if (iFound <= 0)
//no found, the next place is iFound
{
//move the ending part of the table forward
iFound= abs(iFound);
//printf("\n...start insertion from this old name on: %d %s...", iFound, czStudentName[iFound]);
for (i= N-1; i>= iFound; i--){
//printf("\nTest: should move: %d %s lower",iStudID[i],czStudentName[i]);
strcpy(czStudentName[i+1],czStudentName[i]);
iStudID[i+1]= iStudID[i];
}
//insert the new item
strcpy(czStudentName[iFound],name);
printf("\nGive the ID: ");
GetAnsw(name);
iStudID[iFound]= atoi(name);
N= N + 1;
}
}
else if (strcmp(czCmds[3],czCommand)==0 ||
czCmds[3][0]==czCommand[0]) //modify
{
printf("\nNot ready to modify...");
}
else if (strcmp(czCmds[4],czCommand)==0 ||
czCmds[4][0]==czCommand[0]) //show
{
printf("\nData set look like following:.\n");
ShowTable(iStudID, czStudentName, N);
}
else if (strcmp(czCmds[5],czCommand)==0 ||
czCmds[5][0]==czCommand[0]) {//quit
break;
}
else if (strcmp(czCmds[6],czCommand)==0 ||
czCmds[6][0]==czCommand[0]) //help
{
ShowCommands(czCmdHelp, CMDS);
}
else //error in command, help
{
printf("\nData set look like following:.\n");
ShowTable(iStudID, czStudentName, N);
printf("\nError in command.\n");
ShowCommands(czCmdHelp, CMDS);
}
}
//SAVING THE DATA INTO AN OUPUT FILE
OutputChannel= fopen(OutputFile,"w");
if (OutputChannel == NULL){
printf ("\nOutput file %s could not be opened (check the disk!)", OutputFile);
}
else{
printf ("\nSaving into the output file %s\n", OutputFile);
for(i=0; i< N; i++){
iRetCode= fprintf(OutputChannel,"%d %s\n", iStudID[i], czStudentName[i]);
if (iRetCode==0)
{
printf("\nOutput problem. Check the disk space ...!");
break;
}
}
fclose(OutputChannel);
}
//READY:
printf("\nPush any key to end ...");
getchar();
return 0;
}
//SUBROUTINES ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
int GetAnsw( char Answ[]){
/*TASK: scanf subsituted by characterwise input
FOR characters keyed
IF CR
end the output string
ELSE
insert the character into the input string
END
END
---------------------------------------------------------------
*/
char cCh;
int i;
i= 0;
while (1){
cCh= getchar();
if (cCh== 13 || cCh== 10) {//CR or LF
Answ[i]= 0; //binary ending
break;
}
else{
Answ[i]= cCh;
i++;
}
}
return 0;
}
int ShowCommands(char czCmdHelp[][10], int N){
/*PSEUDOCODE:
FOR all commands
show in the display
END
---------------------------------------------------
*/
int i;
printf("\nUse following commands (or one letter shortenings):\n");
for (i=0; i< CMDS; i++)
printf("\n%s", czCmdHelp[i]);
return 0;
}
int ShuttleSortN (int myVect[], char cNames[][16], int iNumb){
//This is a record sorting, also not only a key sort!
/*PSEUDOCODE:
For right hand r: 0 .. N-2
For left hand l: r + 1 … N-1
If l’th value < r’th value
Chance them (means swapping…)
TempPlace= left value
Left value = right value
Right value= TempPlace
End
End
End
*/
int r, l;
int k;
int swapInt;
char cTempName[16];
//l refers to left hand, r to right hand
for (r= 0;r <= iNumb-2; r++){
for(l= r+1; l <= iNumb-1; l++){
//if (myVect[r] < myVect[l]){ //ascending sorting order
if (strcmp(cNames[r],cNames[l])> 0){ //ascending sorting order
//printf("\nTest: changed %s %s", cNames[r],cNames[l]);
// swap the key values:
swapInt= myVect[l];
myVect[l]= myVect[r];
myVect[r]= swapInt;
//change also the other fields of the record
strcpy(cTempName, cNames[l]);
strcpy(cNames[l], cNames[r]);
strcpy(cNames[r], cTempName);
}
}
}
return 0;
}
int ShowTable(int iStudID[], char czStudentName[][16], int iNumb) {
/*
AUTHOR: T. Kallinen DATE: 2008-4-2
PSEUDOCODE:
IF items in the table
FOR all items
display
ELSE
display: no items
END
-----------------------------------------------------------------------------------------------
*/
int i;
printf("\nID Name:\n");
if (iNumb== 0)
printf("\nThe table is empty!");
else {
for(i= 0; i< iNumb; i++){
printf("%5d %-13s", iStudID[i], czStudentName[i]);
if (i % 4 == 3)
printf("\n");
}
}
return 0;
}
///////////////////////////////////////////////////////////////////////////////
/*‘BINARY SEARCH ALGORITHM DESCRIPTION:
‘
‘ 0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
‘ +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+->all pointers
‘ Vector: |17 | 18| 22| 22| 24| 25| 27| 31| 33| 36| 37| 41| 43| 46| 47| 51| 55|
‘ of +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
‘ N=12 items ^ ^ ^
‘ | | |
‘ LowerBound MiddlePoint UpperBound
‘ |
‘ FoundPointer
‘
‘PSEUDOCODE:
‘ BinarySearch(Vector, SearchValue, FoundPointer, N)
‘FoundPointer= -1
‘LowerBound=0
‘UpperBound= N-1
‘DO WHILE UpperBound >= LowerBound AND FoundPointer = -1
‘ MiddlePoint= INT((LowerBound + UpperBound)/2)
‘ IF SearchValue < Vector(MiddlePointer) ‘ … we’ll search from the left half
‘ UpperBound= MiddlePoint – 1 ‘…rejecting the right half
‘ ELSE …we’ll search from the right half
‘ IF SearchValue = Vector(MiddlePoint) ‘we did find it now!
‘ FoundPointer= MiddlePoint
‘ ELSE ‘reject the left part to move on to the right…
‘ LowerBound= MiddlePoint + 1
‘ END IF
‘ END IF
‘END DO
‘COMMENT: Also found or not?
‘IF FoundPointer= -1
‘ Not found…
‘ELSE
‘ Found successfully
` FoundPointer tells/returns the position
‘END IF
*/
int DoBinarySearch(char name[], char czStudentName[][16], int N, int *FoundPointer)
{
int Middlepoint,i=0;
int LowerB= 0;
int UpperB= N-1;
*FoundPointer= -1;
//here you shall fullfill the code
//printf ("\nBinary search not ready! Complete it\n");
while (UpperB > LowerB && *FoundPointer == -1)
{
Middlepoint=(LowerB + UpperB)/2;
if(strcmp(name, czStudentName[i])<0)
*FoundPointer=Middlepoint-1;
else{
if(strcmp(name, czStudentName[i])==0)
*FoundPointer=Middlepoint;
else
LowerB=Middlepoint + 1;
}
break;
}//COMMENT: Also found or not?
if(*FoundPointer= -1)
printf("Not Found\n");
else
printf("Found successfully!");
return *FoundPointer;
}
int FindSequentially(char name[], char czStudentName[][16], int iN, int *iFound){
int i;
for (i=0; i< iN; i++){
//printf("\ncomparing %s and %s\n", name, czStudentName[i]);
if (strcmp(name, czStudentName[i])==0){
//printf("\n%s has ID: %5d\n", czStudentName[i], iStudID[i]);
*iFound= i;
break;
}
else if (i== iN - 1) {//at the end
//printf("\nCould not find an inexistent record!");
*iFound= -9999;
break;
}
else if (strcmp(name, czStudentName[i])<0)
{
//printf("\nA bigger Key was found in the ascending order: %d %s", i,czStudentName[i]);
*iFound= - i;
break;
}
}
return 0;
}
my task is to write a code that modify the student name and that can search for name using binary search.
i will appreciate quick reply
Thanks