Code:
/********************************************************************************
** CIS 15 BG
** Fall, 2006
***************
**
** Lab 8 Linked Lists 20 Points
**
*********************************************************************************
Write a program that builds a sorted linked list from a AGENDA.TXT and
then displays it on the monitor.
The data structure has three fileds:
name - a dynamically allocated string
date of birth - another structure with three integer fields:
month, day, and year
phone number - a string of 10 + 1 characters
The key field is the phone number and it is unique.
Then the program presents the user with a menu to:
. L - List
. S - Search
. I - Insert
. D - Delete
. M - Print Menu
. E - Exit
Test Cases: Run your program once choosing the following options:
S - search (found)
S - search (not found)
M - print menu
D - delete the first record in your list
D - delete any record in your list except the first one
D - delete a record that is not in your list (print an appropriate error message)
L - display the sorted list
I - insert at the end
I - insert in the middle
I - insert in the beginning
I - try to insert a duplicate (your program should reject it!)
L - display the sorted list
E - exit
Note: Do not forget to write a destroyList function.
Program documentation: For each function, in addition to Task, PRE, and POST,
write the name of the programmer too.
****************************************
**
** Written By:
** Student #1: Jon Paek
**
** Student #2:
** Date:
**
********************************************************************************/
#include<stdio.h>
#include<string.h>
#include<crtdbg.h>
#include<stdlib.h>
#include<ctype.h>
#define FLUSH while (getchar () != '\n')
#define FILE_NAME "agenda.txt"
// Type Definitions
typedef struct {
int month;
int day;
int year;
} BDATE;
typedef struct {
char *name;
BDATE bdate;
char number[11];
} 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);
// Our Declarations
void getKey (char target[]);
int main ( void )
{
// Local Definitions
NODE *pList = NULL;
// Statements
printf("\t\t LAB 8 - LINKED LISTS\n\n");
pList = buildList();
printMenu();
pList = processListManager(pList);
pList = destroyList (pList);
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**********************");
printf("\n\t\t* *");
printf("\n\t\t* L - List *");
printf("\n\t\t* S - Search *");
printf("\n\t\t* I - Insert *");
printf("\n\t\t* D - Delete *");
printf("\n\t\t* M - Print Menu *");
printf("\n\t\t* E - Exit *");
printf("\n\t\t* *");
printf("\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
/* ================================================================= */
/*
* Student#1: Jon Paek
*
* searchList, insertNode, insertManager, searchManager, buildList
*
/* ================================================================= */
NODE *buildList (void)
{
// Local Definitions
NODE *pList;
NODE *pPre;
NODE *pCur;
FILE *fpData;
char tempString[100];
int tempN[3];
char *pointer;
char tempName[100];
DATA item;
// Statements
printf("\nbuildList Function..\n");
pList = pPre = pCur = NULL;
fpData = fopen(FILE_NAME, "r");
if (!fpData)
{
printf("Error opening file %s\n", FILE_NAME);
exit(100);
}
pointer = fgets(tempString, sizeof(tempString), fpData);
while (pointer != NULL && strlen(pointer) > 1)
{
// Scans a line into the temporary string
sscanf(tempString, "%[^;]%*c %d-%d-%d (%3d) %3d-%4d",
tempName,
&item.bdate.month,
&item.bdate.day,
&item.bdate.year,
&tempN[0],
&tempN[1],
&tempN[2]
);
// Enters info for phone number
sprintf(item.number, "%d%d%d", tempN[0], tempN[1], tempN[2]);
item.name = tempName;
searchList (pList, &pPre, &pCur, item.number);
pointer = fgets(tempString, sizeof(tempString), fpData);
pList = insertNode(pList, pPre, item);
}
fclose(fpData);
return pList;
}
void searchManager (NODE *pList)
{
NODE *pCur;
NODE *pPre;
int found;
char target[11];
printf("searchManager...\n");
getKey(target);
found = searchList (pList, &pPre, &pCur, target);
printf("found = %d\n number = %s", found, target);
return ;
}
int searchList (NODE *pList, NODE **pPre, NODE **pCur, char target[])
{
// Local Definitions
int found = 0;
// Statements
*pPre = NULL;
*pCur = pList;
// Starts search from the beginning
while (*pCur != NULL && ( strncmp(target, (*pCur)->data.number, 10) > 0 ) )
{
*pPre = *pCur;
*pCur = (*pCur)->link;
}
if(*pCur && ( strncmp(target, (*pCur)->data.number, 10) == 0 ) )
found = 1;
return found;
} // end searchList
void getKey (char target[])
{
printf("Please enter the phone number, only numbers: ");
scanf("%s", target);
FLUSH;
while (strlen(target) != 10)
{
printf("Invalid input. Please try again: ");
scanf("%s", target);
FLUSH;
}
return ;
} // end getKey
NODE *insertManager (NODE *pList)
{
// Local Definitions
NODE *pCur;
NODE *pPre;
int found;
char target[11];
DATA item;
char name[100];
// Statements
printf("insertManager...\n");
getKey(target);
printf("You want to insert %s.\n", target);
found = searchList (pList, &pPre, &pCur, target);
if (found == 1)
printf("Cannot insert, number already exists!\n");
else
{
strcpy(item.number, target);
printf("Insert in progress.\nPlease enter the name: ");
gets(name);
item.name = name;
printf("Please enter the birthdate MM-DD-YY: ");
scanf("%d%*c%d%*c%d", &item.bdate.month, &item.bdate.day, &item.bdate.year);
FLUSH;
insertNode (pList, pPre, item);
}
return pList;
} // end insertManager
NODE *insertNode (NODE *pList, NODE *pPre, DATA item)
{
// Local Definitions
NODE* pNew;
// Statements
printf("Inserting...\n");
if (!(pNew = (NODE*)malloc(sizeof(NODE))))
{
printf("Memory overflow in insert\n");
exit(100);
}
pNew->data = item;
pNew->data.name = (char*)calloc(sizeof( strlen(item.name) ) + 1, sizeof(char));
strcpy(pNew->data.name, item.name);
printf("%s, %d-%d-%d, %s", pNew->data.name, pNew->data.bdate.month,
pNew->data.bdate.day,
pNew->data.bdate.year,
pNew->data.number);
if (pPre == NULL)
{
pNew->link = pList;
pList = pNew;
}
else
{
pNew->link = pPre->link;
pPre->link = pNew;
}
return pList;
} // end insertNode
/* ================================================================= */
/*
* Student#2:
*
* deleteList, printList, deleteManager, destroyList, buildList
*
/* ================================================================= */
NODE* deleteNode (NODE *pList, NODE *pPre, NODE *pCur)
{
// Local Definitions
// Statements
if (pPre == NULL)
// Deleting first node
pList = pCur->link;
else
// Deleting other nodes
pPre->link = pCur->link;
free (pCur);
return pList;
} // deleteNode
NODE* deleteManager (NODE *pList)
{
// Local Definitions
char target[11];
NODE *pCur;
NODE *pPre;
int found;
// Statements
pCur = pPre = NULL;
printf ("Please enter a phone number you would like to delete.\n");
getKey(target);
found = searchList (pList, &pPre, &pCur, target);
if (found == 1)
deleteNode (pList, pPre, pCur);
else
printf("Cannot delete, number doesn't exists!\n");
return pList;
}
NODE *destroyList (NODE *pList)
{
// Local Definitions
NODE *pCur;
NODE *pPre = NULL;
// Statements
pCur = pList;
while (pList != NULL)
{
pCur = pList;
pList = pList->link;
deleteNode (pList, pPre, pCur);
}
return pList;
}
void printList (NODE *pList)
{
// Local Definitions
NODE *pWalker;
int num1;
int num2;
int num3;
// Statements
pWalker = pList;
printf("List contains:\n");
while (pWalker)
{
printf("%-30s%02d-%02d-%02d\t", pWalker->data.name, pWalker->data.bdate.month,
pWalker->data.bdate.day, pWalker->data.bdate.year);
sscanf(pWalker->data.number, "%3d%3d%4d", &num1, &num2, &num3);
printf("(%d) %d-%d\n", num1, num2, num3);
pWalker = pWalker->link;
} // while
printf("\n");
return ;
} // printList