dynamic allocation..urgent help needed!!!

kashif · 04-20-2003, 03:50 PM

hi, I need some help....i have an assignment for which i have written the complete code, but the thing is that the assignment requires that we use dynamic allocation. The functions also have been provided. But i do not know how to use them in my code, which works flawlessly. The instructions for the assignment with the dynamic allocation functions are here http://kashif.pcplayground.com/phonebook.html ....i need urgent help bec this is due tomm.
thanks
I am posting the code in here:-

Code:

/***********************************************************************
Description:This is an interactive menu driven program. It is designed
to implement an automated telephone book. Each entry in this automated
telephone book will contain a name and a telephone number.
***********************************************************************/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define TEL_BOOK_SIZE 75
#define NAME_SIZE 22
#define TEL_NUM_SIZE 14

struct tel_book_element
{	char name[NAME_SIZE];
	char tel_num[TEL_NUM_SIZE];
};

typedef struct tel_book_element Tel_Book_Element;

struct tel_book
{	Tel_Book_Element entry[TEL_BOOK_SIZE];
	int n;
};

typedef struct tel_book Tel_Book;

int binarySearch(const Tel_Book *tbp, const char searchName[], int *ip);
int linearSearch(const Tel_Book *tbp, const char num[]);
void putTelBook(const char *fname,Tel_Book *tbp);
void getTelBook(const char *fname,Tel_Book *tbp);
void displayMenu(void);
char *strToUpper(char *s);
void lookUpName(Tel_Book *tbp);
void listName(Tel_Book *tbp);
void modify(Tel_Book *tbp);
void del(Tel_Book *tbp);
void inputNewBook(char *fname,Tel_Book *tbp);
void sortTelBook(Tel_Book *tbp);
void lookupnumber(Tel_Book *tbp);

int main()
{  Tel_Book tb;
	char save,keyHit,fname[NAME_SIZE]="a:tbfile.txt";

	getTelBook(fname,&tb);
	do
	{  displayMenu();
		printf("Enter Your Selection (a-f) ");
		keyHit=getchar();
		getchar();      /* get rid of the new line character */
		switch(keyHit)
		{	case '1': inputNewBook(fname,&tb); break;
		    case '2': lookUpName(&tb); break;
			case '4': modify(&tb); break;
			case '5': del(&tb); break;
			case '6': listName(&tb); break;
			case '3': lookupnumber(&tb);break;
			case '7':
				printf("Do you want to save it (y/n)? "); save=getchar();
				if(save=='y'||save=='Y')
					putTelBook(fname,&tb);
				break;
			default:
				printf("Option is not correct. Hit Enter to continue");
				getchar();
				break;
		}
	}while(keyHit!='7');

	return 0;
}

/***********************************************************************
The function inputNewBook close the current TelBook and read the new
TelBook from file, uppercase name, and sort in alphabetical order.
***********************************************************************/
void inputNewBook(char *fname,Tel_Book *tbp)
{  int m;
	char save;

	printf("Do you want to save the current one (y/n)? ");
	save=getchar(); getchar();
	if(save=='y'||save=='Y')
		putTelBook(fname,tbp);
	printf("Enter the filename: ");
	gets(fname);
	getTelBook(fname,tbp);
	for(m=0;m<tbp->n;m++)
		strToUpper(tbp->entry[m].name);
	sortTelBook(tbp);
	printf("New telephone book has been inputed.\n");
	printf("Press Enter to continue");         /* pause the output */
	getchar();
}

/***********************************************************************
The function sortTelBook sort all the name in alphabetical order.
***********************************************************************/
void sortTelBook(Tel_Book *tbp)
{  int pass,m;
	char hold[NAME_SIZE];

	for(pass=1;pass<tbp->n;pass++)
		for(m=0;m<(tbp->n)-pass;m++)
			if(strcmp(tbp->entry[m].name,tbp->entry[m+1].name)>0)
			{	/* swap 2 elements */
				strcpy(hold,tbp->entry[m].name);
				strcpy(tbp->entry[m].name,tbp->entry[m+1].name);
				strcpy(tbp->entry[m+1].name,hold);
				strcpy(hold,tbp->entry[m].tel_num);
				strcpy(tbp->entry[m].tel_num,tbp->entry[m+1].tel_num);
				strcpy(tbp->entry[m+1].tel_num,hold);
			}
}

/***********************************************************************
This function displays the options of the interactive-user program.
***********************************************************************/
void displayMenu(void)
{
  printf("Automated Telephone Book Menu\n");	
	printf("1) New telephone book-upper case and sort it\n");
	printf("2) Look up name to get number\n");
	printf("3) Look up number to get name\n");
	printf("4) Insert new/modified element\n");
	printf("5) Delete element\n");
	printf("6) List names starting with given letter\n");
	printf("7) Quit\n");
}

/***********************************************************************
This function changes a string to uppercase.
***********************************************************************/
char *strToUpper(char *s)
{	int i;

	for(i=0;s[i]!='\0';i++)
		s[i]=toupper(s[i]);
	return s;
}

/***********************************************************************
This function search a name, return 1 if found, 0 if not found, and ip
is the position found or should be inserted.
***********************************************************************/
int binarySearch(const Tel_Book *tbp, const char searchName[], int *ip)
{	int low,high,middle;

	low=0;high=tbp->n-1;
	while(low<=high)
	{	middle=(low+high)/2;
		if(strcmp(searchName,tbp->entry[middle].name)==0)
		{	*ip=middle;
			return 1;
		}
		else if(strcmp(searchName,tbp->entry[middle].name)<0)
			high=middle-1;
		else
			low=middle+1;
	}
	*ip=low;
	return 0;
}

/***********************************************************************
This function read information from a file, and store it to a struct
typed TelBook.
***********************************************************************/
void getTelBook(const char *fname,Tel_Book *tbp)
{  FILE *fp;
	int m=0;

	if ((fp=fopen(fname, "r"))==NULL)
	{	printf("File could not be opened to read\n");
		exit(1);   /* terminate the program  */
	}
	while(fgets(tbp->entry[m].name,NAME_SIZE,fp)!=NULL)
	/* read while not EOF */
		fgets(tbp->entry[m++].tel_num,TEL_NUM_SIZE,fp);
	tbp->n=m;      /* store the total of entries */
	fclose(fp);
}

/***********************************************************************
This function output information from a struct TelBook to a file.
***********************************************************************/
void putTelBook(const char *fname,Tel_Book *tbp)
{ 	int m;
	FILE *fp;

	if ((fp=fopen(fname, "w"))==NULL)
	{	printf("File could not be opened to write\n");  exit(1);
	}
	for(m=0;m<tbp->n;m++)
	{	fputs(tbp->entry[m].name,fp);
		fputs(tbp->entry[m].tel_num,fp);
	}
	fclose(fp);
}

/***********************************************************************
This function provides an option that user can look up an entry of the
telephone book.
***********************************************************************/
void lookUpName(Tel_Book *tbp)
{	char searchName[NAME_SIZE];
	int i;

	printf("Enter a name you want you look up: ");
	fgets(searchName,NAME_SIZE,stdin);
	strToUpper(searchName);
	if(binarySearch(tbp,searchName,&i))
	{	printf("Name found:\n");
		printf("%s",tbp->entry[i].name);
		printf("%s",tbp->entry[i].tel_num);
	}
	else
		printf("Name not Found\n");
	printf("Press Enter to continue");
	getchar();
}

/***********************************************************************
This function provides an option that user can list all the names which
begin with the first name inputted.
***********************************************************************/
void listName(Tel_Book *tbp)
{	char name[NAME_SIZE];
	int i,found=0;

	printf("Enter a name you want to list: ");
	gets(name);
	strToUpper(name);
	for(i=0;i<tbp->n;i++)
		if(tbp->entry[i].name==strstr(tbp->entry[i].name,name))
		{  found=1;
			printf("%s",tbp->entry[i].name);
			printf("%s",tbp->entry[i].tel_num);
		}
	if (!found)
		printf("Name not in the list\n");
	printf("Press Enter to continue");
	getchar();
}

/***********************************************************************
This function provides an option that user can input an entry, if found
then modify, if not found then insert as a new entry.
***********************************************************************/
void modify(Tel_Book *tbp)
{  int i,j;
	char name[NAME_SIZE],tel[TEL_NUM_SIZE];

	printf("Enter the name to modify or insert: ");
	fgets(name,NAME_SIZE,stdin);
	strToUpper(name);
	printf("Enter the telephone number: ");
	fgets(tel,TEL_NUM_SIZE,stdin);
	if(binarySearch(tbp,name,&i))             /* found entry */
	{	printf("Modified Entry Inserted\n");
		strcpy(tbp->entry[i].name,name);    /* i is position modified */
		strcpy(tbp->entry[i].tel_num,tel);
	}
	else           /* not found the entry, i is position inserted */
	{
		printf("New Entry Inserted\n");
/*		moving entries up by one position*/
		for(j=tbp->n;j>i;j--)
		{	strcpy(tbp->entry[j].name,tbp->entry[j-1].name);
			strcpy(tbp->entry[j].tel_num,tbp->entry[j-1].tel_num);
		}
		strcpy(tbp->entry[i].name,name);
		strcpy(tbp->entry[i].tel_num,tel);
		tbp->n++;
	}
	printf("Press Enter to continue");
	getchar();

}

/***********************************************************************
This function provides an option that user can delete one entry.
***********************************************************************/
void del(Tel_Book *tbp)
{  int i,j;
	char name[NAME_SIZE];

	printf("Enter the name to delete: ");
	fgets(name,NAME_SIZE,stdin);
	strToUpper(name);
	if(binarySearch(tbp,name,&i))
	{	printf("Entry Deleted\n");
		for(j=i;j<tbp->n-1;j++)   /*	moving entries down by one position*/
		{	strcpy(tbp->entry[j].name,tbp->entry[j+1].name);
			strcpy(tbp->entry[j].tel_num,tbp->entry[j+1].tel_num);
		}
		tbp->n--;
	}
	else
		printf("Name not Found\n");
	printf("Press Enter to continue");
	getchar();
}

/***********************************************************************
This function looks up the number
***********************************************************************/

void lookupnumber(Tel_Book *tbp)
{
	char num[TEL_NUM_SIZE];
	int i=0,k;

	printf("Enter a number to look up: ");
	fgets(num,TEL_NUM_SIZE,stdin);
	k=linearSearch(tbp,num);
	if(k!=-1)
	{
		printf("Name found:\n");
		printf("%s",tbp->entry[k].name);
		printf("%s",tbp->entry[k].tel_num);
	}
	else
	printf("Name not Found\n");
	printf("Press Enter to continue");
	getchar();
}

/***********************************************************************
performs linear search
***********************************************************************/

int linearSearch(const Tel_Book *tbp, const char num[])
{
	int i=0;

	for ( i = 0 ; i < tbp->n ; i++ ) {
  if ( strcmp( num, tbp->entry[i].tel_num ) == 0 ) return i;
}
return -1;

}

agh · 04-20-2003, 04:19 PM

I get 403 Forbidden when I go to that page...

kashif · 04-20-2003, 04:32 PM

here are the instructions

Code:

modify the phonebook program to look like this, and change to dynamic allocation       

 

You are to design and implement an automated personal telephone book. Each element in this automated telephone book will contain a name and a telephone number.  The program should be an interactive menu driven program.  The menu of possible operations should be

                     Automated Telephone Book Menu

                          1) New telephone book - upper case and sort it

                          2) Look-up name to get number

                          3) Look-up number to get name

                          4) Insert new/modified element

                          5) Delete element

                          6) List names starting with given letter

                          7) Quit

                     Enter Choice (1 - 7) :

 

The address book must be stored in the following structure.

 

#define TEL_BOOK_SIZE 50

#define MAX_STRING_SIZE 82

 

struct telBookElement 

{ char *name;      /*a pointer to a dynamically allocated string storing a name*/

  char *telNum;    /*a pointer to a dynamically allocated string storing a telephone number*/

};

typedef struct telBookElement  TelBookElement;

struct telBook

{ TelBookElement element[TEL_BOOK_SIZE];

  int n;   /*the number of elements that contain names and telephone numbers*/

};

typedef struct telBook  TelBook;

 

Then in the main function have the declarations

TelBook  tb;

TelBook *tbp = &tb;

 

The first thing the program should do is to input the information about the telephone book from the file "tbfile.txt" and store it in the telephone book, tb. Each name and telephone number will be on a separate line. If this file contains info about a new telephone book then the names may not be in alphabetical order and may not be in upper case (this makes it easier for the person who creates the file). If the file contains info about an old telephone book then the names will be in alphabetical order and in upper case (since the file was created by the last run of the program).

"tbfile.txt"   New                                           "tbfile.txt"  Old

Anders Jane                                                  AMBERSON FREDRICK JAMES III 

281-275-4196                                                668-4397

Amberson Fredrick james III                        ANDERS JANE

668-4397                                                       281-275-4196

...                                                                   ...

LAST PERSON'S NAME                            LAST PERSON'S NAME

LAST PERSON'S TEL NUM                      LAST PERSON'S TEL NUM

 

Here is a function that can be used to input a string that is then stored in dynamically allocated memory. 

/***************************************************************************************************

The function fgetString inputs one line of text from the file pointed to by fp. It discards the new-line character, if present, and stores the string in dynamically allocated storage. It returns a pointer to this dynamically allocated string or NULL if no string was inputted before reaching the end of file.

***************************************************************************************************/

char *fgetString(FILE *fp)

{ char s[MAX_STRING_SIZE];  

  char *inputStatus, *sp;  

  int n;

 

  inputStaus = fgets(s, MAX_STRING_SIZE, fp);     /*input string*/

  if (inputStatus == NULL)                        /*if end of file*/

     return NULL;                                 /*return NULL like fgets*/

  n = strlen(s);                                  /*compute string length*/

  if (s[n-1] == '\n') s[--n] = '\0';              /*if present, get rid of new-line char*/

  sp = malloc(n + 1);                             /*allocate dynamic memory*/

  if (sp == NULL)                                 /*if out of memory*/               

  {  printf("Out of storage for string\n");        /*print error message*/

     exit(1);                                     /*exit program, abnormal termination*/ 

  }                                               /*otherwise memory was allocated*/

  strcpy(sp, s);                                  /*copy string to allocated memory*/

  return sp;                                      /*return pointer to allocated string*/

}

The fgetString function is used during the input of the "tbfile.txt" and anywhere else where one wants to input a string and store it in dynamically allocated storage.

/***************************************************************************************************

The function fgetTelBook inputs the information about the telephone book from the file "tbfile.txt" into the telephone book structure pointed to by tbp. You need a complete path name for the file. ***************************************************************************************************/

void fgetTelBook(TelBook *tbp)

{ char *namep;   

  int i;  

  FILE *fp = fopen("tbfile.txt", "r");               /*change file name to complete path name*/

  if (fp == NULL)                                     /*check to see if file opened*/

  {  printf("The \"tbfile.txt\" cannot be opened\n"); /*if not print error message*/

     exit(1);                                        /*exit program, abnormal termination*/ 

  }                                                   /*otherwise file was opened*/

  i = 0;

  namep = fgetString(fp);                            /*input name*/

  while(namep != NULL)                               /*while not at end of file*/

  {  tbp->element[i].name = namep;                     /*put name in i_th element*/

     input a telephone number (using fgetString) and put it in the i_th element; 

     increment i;

     namep = fgetString(fp);                         /*input next name*/

  }

  set the n field of the telephone book to i;

  close file;

}

After inputting the info into the telephone book structure, repeatedly print the menu, get the user's response of 1-7 (input this as a character not a number) and then determine which operation it is and carryout the selected operation. Remember to get rid of the new-line character that follows the user’s response, i.e. do a getchar() to read it out of the input buffer. If the operation code is not 1-7 then print an error message and prompt the user again for a correct operation. Each operation should be done by a function. The program should also have functions for tasks such as outputting the telephone book, uppercasing strings, sorting, etc.  

 

The operations are as follows:

1) should first go through the telephone book and upper case all names and then sort the telephone book into alphabetical order of the names.  Names should be compared using strcmp.

 

2) should prompt the user and input a name (upper case it) and then look-up the name in the telephone book. If found then display the telephone number of the person. If not found then display the message "Name Not Found". This look-up must use binary search. Input the name into a regular char array using gets so dynamic storage is not used up unnecessarily.

 

3) should prompt the user for a telephone number and then look-up the telephone number in the telephone book. If found then display the name of the person. If not found then display the message "Number Not Found". This look-up uses linear search that searches linearly forward from the beginning of the telephone book until the number is found or until the end of the book. This operation is not used nearly as much as a). If it were used frequently we would store another version of the phone book sorted on telephone numbers so we could use the much more efficient binary search algorithm for looking up telephone numbers as well as names. Input the telephone number into a character array using gets (not fgetString).

 

4) should prompt the user and input a name (upper case it) and telephone number for a person. The name should then be looked-up in the telephone book using binary search. If found then replace the old telephone number with the new one. If not found then insert the new element into the correct place to maintain the telephone book in alphabetical order of names (this requires first moving all following elements down by one position to make room for the new element and setting n to 1 more than before). This operation should display either the message "New Element Inserted" or "Old Element Modified" depending on which was done. Note that you need to input the name and telephone number as dynamically allocated strings so use fgetString(stdin), e.g. 

char *newName;

newName = fgetString(stdin); strToUpper(newNname);

If the element is a modification of an old element then remember to de-allocate the name and telephone number of the old element before assigning the new ones.

 

5) should prompt the user and input a name (upper case it) and then look-up the name in the telephone book using binary search. If found then delete the element by copying all following elements up by one position (thus overwriting the deleted element and not leaving any holes in the element array) and setting n to 1 less than before. This operation should display either the message "Element Deleted" or "Name Not Found" depending on what happened. Before copying all the following elements up by one, be sure to de-allocate the dynamic storage that is used for the name and telephone number strings in the deleted elementusing the free function, e.g. 

free(tbp->element[i].name); free(tbp->element[i].telNum);. Recall that C allows one to assign one whole struct to another. Thus one can copy up one of the elements by tbp->element[i] = tbp->element[i+1].

 

6) should  prompt the user and input the first letter of the name (upper case it) and then output all the names in the telephone book that start with this letter. Remember to get rid of the new-line character that follows the user’s response, i.e. do a getchar() to read it out of the input buffer . This is unnecessary for the other operations because fgetString and gets both input the new-line character and thus do not leave it in the input buffer. This operation is useful if you are looking up a name and cannot find it because it may have been entered differently, e.g. as "SMITH JAMES" and you were trying "SMITH JIM". In this case you could ask the system to list all names starting with ‘S’ and find the desired name in the list. 

 

7) should result in terminating the program. Before terminating the program output the info in the telephone book to "tbfile.txt" so the program will have an updated version of this info the next time the program is used. The function that does the output can use fputs for outputting the strings, but remember that fputs does not output a new-line character after the string. It expects that a new-line character is part of the string as it would be if input were done with fgets. However the fgetString function discarded the new-line character. We would thus need to explicity output the new-line character using fputc. For example, to output one name to the file with file pointer fp, you might use:  fputs(tbp->element[i].name, fp); fputc('\n', fp); The function that does this output must open the file "tbfile.txt" (use a complete path name) for writing and close it at the end. Output is done to the same file as input was done from so that the next time the program is run the file will contain the changes done to the telephone book this time.

 

This program uses binary search to look-up elements during operations 2), 4), 5).  A version of binary search that is particularly useful for this program is the following:

/***************************************************************************************************

The function binarySearch assumes the telephone book pointed to by tbp has the names in alphabetical order. *tbp, searchName are in-parameters. *ip is an out-parameter. In order to avoid copying the telephone book structure, which is large, we choose to pass a pointer to it, even though it is an in-parameter. This function does the following: If searchName occurs in the telephone book then the function returns true (1) and *ip is set to the subscript of where the name occurs, i.e. tbp->element[*ip].name is the searchName. If searchName does not occur in the telephone book then the function returns false (0) and *ip is set to the subscript of where an element with this name should be inserted, i.e. tbp->element[*ip] is where an element with this name should be inserted.

***************************************************************************************************/

int binarySearch(TelBook *tbp, char searchName[], int *ip)

{ int middle, low = 0, high = tbp->n - 1;

   while (low <= high)

  {  middle = (low + high) / 2;

     if (strcmp(searchName, tbp->element[middle].name) == 0)

     {  *ip = middle;

        return 1;

 .    }

     else if (strcmp(searchName,  tbp->element[middle].name) < 0)

        high = middle - 1;

     else

        low = middle + 1;

  }

  *ip = low;

  return 0;

}

Note that since this function returns true or false it can be used in a test position such as 

if (binarySearch(tbp, searchName, &i))

  do what should be done when the searchName is already in tb. i is the subscript where  searchName occurs;

else

  do what should be done when the searchName is not in tb. i is the subscript where an element with searchName should be inserted;

agh · 04-20-2003, 04:59 PM

Well, I'm guessing what you want is to use the function fgetString from the instructions inside the function getTelBook from your code.

But that's already done in fgetTelBook in the instructions... so just use that function.

kashif · 04-21-2003, 08:50 AM

but would'nt i have to make drastic changes to the code if i have to do it that way????

all the functions and all???