Unknown memory leak with linked lists...
So my program is 99% towards completion. However, the program leaks memory. The deleteNode, deleteManager, and destroyList are the ones to blame, or so I think. When I delete a node other than the first one it works while leaking memory. However, when I try deleting the first node and then try to display the list again, the program crashes. Perhaps my deleteNode function needs some readjustment. In any case, here is the code and the input file.
Code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<crtdbg.h>
#define FLUSH while (getchar () != '\n')
#define FILE_IN "countries.txt"
// Type Definitions
typedef char KEY_TYPE;
typedef struct {
char *name;
char *capital;
long population;
} COUNTRY;
typedef struct {
KEY_TYPE key[3];
COUNTRY list;
} DATA;
typedef struct nodeTag {
DATA data;
struct nodeTag* link;
} NODE;
// Prototype Declarations
char getOption (void);
void printMenu (void);
int searchList (NODE *pList, NODE **pPre, NODE **pCur, char target[]);
NODE *insertNode (NODE *pList, NODE *pPre, DATA item);
NODE *deleteNode (NODE *pList, NODE *pPre, NODE *pCur);
void printList (NODE *pList);
NODE *destroyList (NODE *pList);
NODE *buildList (void);
NODE *processListManager (NODE *pList);
void searchManager (NODE *pList);
NODE *insertManager (NODE *pList);
NODE *deleteManager (NODE *pList);
int getData ( FILE *spIn, DATA *data );
void insertCommas ( NODE *pWalker, char *population );
void printCountry ( NODE *list, char populationInCommas[] );
int insertHandler ( DATA *data, char target[] );
int main ( void )
{
// Local Definitions
NODE *list = NULL;
// Statements
printf("\t\t LAB 8 - LINKED LISTS\n\n");
list = buildList();
printMenu();
processListManager ( list );
list = destroyList ( list );
printf("\n\t\tEnd of LAB 8 - LINKED LISTS"
"\n\t\tHave a great day!\n");
printf( _CrtDumpMemoryLeaks() ? "Memory Leak\n" : "No Leak\n");
return 0;
}// main
/* ================================================================= */
/*
* Instructor
*
/* ================================================================= */
/* ==================== getOption ====================
Gets and validates the user's option.
Pre : nothing
Post : valid option returned
Written by : Instructor
*/
char getOption (void)
{
// Local Definitions
char option;
// Statements
printf ("\n\nPlease enter the option: ");
scanf ("%c", &option);
FLUSH;
option = toupper (option);
while(strchr("LSIDME", option) == NULL)
{
printf("\..........* Invalid option! ***\n");
printf("Enter one of the following letters: L, S, I, D, M, E: " );
scanf ("%c", &option);
FLUSH;
option = toupper (option);
}
return option;
} // getOption
/* ============================== printMenu ==============================
Prints the menu to the screen.
PRE : nothing
POST : menu printed
Written by : Instructor
*/
void printMenu (void)
{
// Local Definitions
// Statements
printf("\n\t\t**********************"
"\n\t\t* *"
"\n\t\t* L - List *"
"\n\t\t* S - Search *"
"\n\t\t* I - Insert *"
"\n\t\t* D - Delete *"
"\n\t\t* M - Print Menu *"
"\n\t\t* E - Exit *"
"\n\t\t* *"
"\n\t\t**********************");
return;
} // printMenu
/* ============================== processListManager ====================
Process user's option by calling appropriate functions.
PRE : pList - a pointer to the first node of a linked list
POST : pList - might be changed after inserting or deleting
Written by : Instructor
*/
NODE *processListManager (NODE *pList)
{
// Local Definitions
char option;
// Statements
do
{
option = getOption();
switch(option)
{
case 'L' : printList (pList);
break;
case 'S' : searchManager (pList);
break;
case 'I' : pList = insertManager (pList);
break;
case 'D' : pList = deleteManager (pList);
break;
case 'M' : printMenu ();
break;
case 'E' : printf("End of processing!\n");
break;
default : break;
}
} while (option != 'E');
return pList;
} // processListManager
/* ================================================================= */
/*
* Me
*
/* ================================================================= */
/* =============================buildList=================================
Builds the list for the countries' data from the input file.
PRE : nothing
POST: pList - the complete list after reading from input file
*/
NODE *buildList (void)
{
// Local Declarations
NODE *pList;
NODE *pPre;
NODE *pCur;
DATA data;
FILE *spIn;
int result;
// Statements
if ( ! ( spIn = fopen ( FILE_IN, "r" ) ) ) {
printf("Error opening file %s\n", FILE_IN);
exit(100);
}
pList = NULL;
while ( getData ( spIn, &data ) ) {
result = searchList(pList, &pPre, &pCur, data.key);
if ( !result )
pList = insertNode(pList, pPre, data);
}
fclose ( spIn );
return pList;
} // buildList
/* ==============================getData==================================
Gathers the data from the input file and allocates memory for the
countries' names and capitals.
PRE : spIn - the input file containing country data
data - address of the data from buildList
POST: pList - the list after reading from input file
*/
int getData ( FILE *spIn, DATA *data )
{
// Local Declarations
int result;
// Statements
data->list.name = (char*)calloc(21, sizeof(char));
data->list.capital = (char*)calloc(16, sizeof(char));
result = fscanf ( spIn, "%2s %20[^;] %*c %15[^;] %*c %ld",
data->key, data->list.name,
data->list.capital, &(data->list.population) );
if ( result == 4 )
return 1;
else {
free ( data->list.name );
free ( data->list.capital );
return 0;
}
} // getData
/* ============================insertNode=================================
Inserts a node into the list.
PRE : pList - the current list before adding a new node
pPre - the predescessor of the new node
item - country data to be copied into the new node
POST: pList - the list with the new node added
*/
NODE *insertNode (NODE *pList, NODE *pPre, DATA item)
{
// Local Declarations
NODE *pNew;
// Statements
if ( ! ( pNew = (NODE*)malloc(sizeof(NODE))))
printf("Memory is unavailable.\n"),
exit(200);
pNew->data = item;
if ( pPre == NULL ) {
pNew->link = pList;
pList = pNew;
}
else {
pNew->link = pPre->link;
pPre->link = pNew;
}
return pList;
} // insertNode
/* ============================searchList=================================
Searches the list for the target key.
PRE : pList - the list with the countries' data
pPre - the predescessor of the walker node
pCur - walker node that walks through pList
target- the inputted key for the search
POST: found - returns 1 if target is found, otherwise returns 0
*/
int searchList (NODE *pList, NODE **pPre, NODE **pCur, char target[])
{
// Local Declarations
int found = 0;
// Statements
*pPre = NULL;
*pCur = pList;
while (*pCur != NULL) {
if (strcmp ( target, (*pCur)->data.key) == 0 ){
found = 1;
break;
}
*pPre = *pCur;
*pCur = (*pCur)->link;
}
return found;
} // searchList
/* =============================printList=================================
Prints the countries' IDs and names.
PRE : pList - the current country list
POST: list is printed
*/
void printList (NODE *pList)
{
// Local Declarations
NODE *pWalker;
// Statements
printf( "== ====================\n"
"ID NAME \n"
"== ====================\n");
pWalker = pList;
while ( pWalker ) {
printf("%s %-20s\n",
pWalker->data.key, pWalker->data.list.name);
pWalker = pWalker->link;
}
printf( "=======================" );
return;
} // printList
/* ============================insertCommas=================================
Inserts commas for the countries' populations when printed out.
PRE : pWalker - points to a node
POST: commas are inserted in countries' populations
*/
void insertCommas ( NODE *pWalker, char *population )
{
// Local Declarations
char printString[15];
char tempString[15];
char insertComma[] = ",";
int strLength;
int checkRmdr;
int i;
// Statements
*printString = '\0';
sprintf(tempString, "%ld", pWalker->data.list.population);
strLength = strlen ( tempString );
checkRmdr = strLength % 3;
if ( checkRmdr > 0 ) {
strncat ( printString, tempString, checkRmdr );
strcat ( printString, insertComma );
}
for ( i = checkRmdr; i < (int) strlen ( tempString ); ) {
strncat ( printString, tempString + i, 3 );
i += 3;
strcat ( printString, insertComma );
}
printString[strlen(printString) - 1] = '\0';
strcpy (population, printString);
return;
} // insertCommas
/* ============================searchManager==============================
Prompts user for a key and searches for it. If found, calls the
printCountry funtion that prints out the country's ID, name,
capital, and its population.
PRE : pList - the current country list
POST: nothing
*/
void searchManager (NODE *pList)
{
// Local Declarations
NODE *pPre;
NODE *pCur;
char target[3];
char populationInCommas[15];
// Statements
printf("Please enter a key: ");
scanf("%2s", target);
FLUSH;
if ( searchList ( pList, &pPre, &pCur, target ) ) {
insertCommas(pCur, populationInCommas);
printCountry(pCur, populationInCommas);
}
else
printf("Country could not be found. Please try again.");
return;
} // searchManager
/* ============================printCountry===============================
Prints country's ID, name, capital, and its population.
PRE : list - the current country list
populationInCommas - country's population with
inserted commas
POST: prints country data
*/
void printCountry ( NODE *list, char populationInCommas[] )
{
// Statements
printf( "\n ID: %s\n"
" Name: %s\n"
" Capital: %s\n"
"Population: %s\n", list->data.key,
list->data.list.name,
list->data.list.capital,
populationInCommas);
} // printCountry
/* ============================insertManager=================================
Inserts a node into the list by prompting the user to enter a key. It
will then call searchList to ensure that there are no duplicates. If not
found, it will proceed to gather more information from the user.
PRE : pList - the current list before adding a new node
POST: pList - the list with the new node added
*/
NODE *insertManager (NODE *pList)
{
// Local Declarations
NODE *pPre;
NODE *pCur;
DATA insertData;
int position;
char target[3];
int counter = 1;
// Statements
printf("Please enter a key: ");
scanf("%2s", target);
FLUSH;
if ( ! ( searchList ( pList, &pPre, &pCur, target ) ) ) {
position = insertHandler ( &insertData, target );
switch (position) {
case 1: pPre = NULL;
break;
case 2: pPre = pList;
while (pPre) {
pPre = pPre->link;
counter++;
}
counter /= 2;
pPre = pList;
while ( counter != 1 ) {
pPre = pPre->link;
counter--;
}
break;
case 3: pPre->link = NULL;
break;
}
pList = insertNode( pList, pPre, insertData );
}
else
printf("That country ID already exists. Please try again.");
return pList;
} // insertManager
/* ===========================insertHandler===============================
Inserts a node into the list.
PRE : pList - the current list before adding a new node
target - the new node's key
POST: position - integer that indicates the new node's position
*/
int insertHandler ( DATA *data, char target[] )
{
// Local Declarations
int position = 0;
// Statements
if ( ! ( data->list.name = (char*)calloc(21, sizeof(char)))) {
printf("Memory Unavailable.\n");
exit(300);
}
if ( ! ( data->list.capital = (char*)calloc(16, sizeof(char)))) {
printf("Memory Unavailable.\n");
exit(400);
}
strcpy ( data->key, target );
printf("Enter the country's name: ");
scanf("%s", data->list.name);
FLUSH;
printf("Enter the country's capital: ");
scanf("%s", data->list.capital);
FLUSH;
printf("Enter the country's population: ");
scanf("%ld", &(data->list.population));
FLUSH;
while ( position < 1 || position > 3 ) {
printf("Where would you like to place this new country?\n"
"Beginning(1), Middle(2), End(3): ");
scanf("%d", &position);
FLUSH;
if ( position < 1 || position > 3 )
printf("Incorrect option. Please try again.\n");
}
return position;
} // insertHandler
/* ============================deleteNode=================================
Deletes a node from the list.
PRE : pList - the current list before deleting a node
pPre - the predescessor of the node to be deleted
pCur - the node to be deleted
POST: pList - the list with the node removed
*/
NODE *deleteNode (NODE *pList, NODE *pPre, NODE *pCur)
{
// Statements
if ( pPre == NULL )
pList = pCur->link;
else
pPre->link = pCur->link;
free ( pCur );
return pList;
} // deleteNode
/* ============================deleteManager==============================
Prompts user for a key for the node they want to delete. searchList is
called and if not found, no nodes will be deleted.
PRE : pList - the current list before deleting a node
POST: pList - the list with or without the node to be deleted
*/
NODE *deleteManager (NODE *pList)
{
// Local Declarations
NODE *pPre = NULL;
NODE *pCur;
char target[3];
// Statements
printf("Please enter a key: ");
scanf("%2s", target);
FLUSH;
if ( searchList ( pList, &pPre, &pCur, target ) )
pList = deleteNode ( pList, pPre, pCur );
else
printf("Country could not be found. Please try again.");
return pList;
} // deleteManager
/* ============================destroyList=================================
Deletes all the nodes in the list.
PRE : pList - the current list before removing all data
POST: pList - an empty list
*/
NODE *destroyList (NODE *pList)
{
// Local Declarations
NODE *pPre = NULL;
NODE *pCur;
// Statements
while ( pList ) {
pCur = pList;
free ( pCur->data.list.name );
free ( pCur->data.list.capital );
pList = deleteNode ( pList, pPre, pCur );
}
return pList;
} // destroyList
The input file:
Code:
HU Hungary; Budapest; 10006835
MX Mexico; Mexico; 106202903
CN China; Beijing; 1306313812
NP Nepal; Kathmandu; 27676547
MU Mauritius; Port Louis; 1230602
FR France; Paris; 60656178
ES Spain; Madrid; 40341462
EG Egypt; Cairo; 77505756
TW Taiwan; Taipei; 22894384
GR Greece; Athens; 10668354
US United States; Washington, DC; 295734134
AU Australia; Canberra; 20090437
LI Liechtenstein; Vaduz; 33717
RU Russia; Moscow; 143420309
CA Canada; Ottawa; 32805041
MC Monaco; Monaco; 32409
BR Brazil; Brasilia; 186112794
IR Iran; Tehran; 68017860
FR France; Paris; 60656178
DO Dominican Republic; Santo Domingo; 8950034
FJ Figi; Suva; 893354
