Coding the sorted linked list functions
The Code
<![CDATA[
/*************************************************\
* Filename: sortedll.c *
* Author: Sue Bogar *
* Date Written: 4/30/98 *
* Date Modified: 11/22/98 *
* Section: 101 *
* EMail: bogar@cs.umbc.edu *
* *
* Description: This file contains the functions *
* necessary to work with the sorted linked list. *
* This set of functions provide the operations *
* needed including creation of a node, insertion, *
* deletion, determining if a list is empty and *
* the printing of the list. *
\*************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sortedll.h"
/******************
* CreateNode mallocs the space needed to
* hold a struct of type node, initializes
* the members, and returns a pointer to
* the new node.
******************/
NODEPTR CreateNode (void)
{
NODEPTR newNode;
/* Get the space needed for the node */
newNode = (NODEPTR) malloc (sizeof(NODE));
if (newNode == NULL)
{
fprintf (stderr, "Out of Memory - CreateNode\n");
exit (-1);
}
/* Initialize the members */
strcpy(newNode -> data.tagNo,"");
strcpy(newNode -> data.owner,"");
strcpy(newNode -> data.make,"");
strcpy(newNode -> data.model,"");
newNode -> data.lot = 0;
newNode -> next = NULL;
return newNode;
}
/******************
* SetData puts the data from the user, passed
* in as the info struct, temp, into the node
* pointed to by the NODEPTR it receives as an
* argument.
******************/
void SetData (NODEPTR temp, INFO new)
{
temp -> data = new;
temp -> next = NULL;
}
/******************
* Insert takes a pointer to a NODEPTR, the
* address of head, and a NODEPTR, temp as
* arguments. temp is a pointer to the
* node to be inserted. The node is then
* inserted into the list at the appropriate
* place to maintain the list as a sorted list.
******************/
void Insert (NODEPTR* headPtr, NODEPTR temp)
{
NODEPTR prev, curr;
if ( IsEmpty (*headPtr))
{
*headPtr = temp;
}
else
{
prev = NULL;
curr = *headPtr;
/* traverse the list until the spot
for insertion is found */
while (curr != NULL &&
(strcmp(temp -> data.tagNo,
curr -> data.tagNo) > 0))
{
prev = curr;
curr = curr -> next;
}
/* insert the node, temp */
if(prev == NULL)
{
temp -> next = *headPtr;
*headPtr = temp;
}
else
{
prev -> next = temp;
temp -> next = curr;
}
}
}
/******************
* Delete takes a pointer to a NODEPTR as its
* first argument, which is the address of
* head. Its second argument is a string that
* contains the value of data to be removed. This
* function traverses the list until the node
* containing the same tagNo as the target is found.
* That node is then deleted from the list and a 1
* returned, indicating success. If the target value
* is not in the list an error message is printed and
* -1 is returned.
******************/
int Delete (NODEPTR* headPtr, char* target)
{
NODEPTR temp, prev, curr;
if (IsEmpty (*headPtr))
{
fprintf(stderr, "Can't delete from an empty list\n");
return (-1);
}
/* if the target value is the first in the list, */
/* move head */
else if (strcmp((*headPtr) -> data.tagNo, target)
== 0)
{
temp = *headPtr;
*headPtr = (*headPtr) -> next;
free (temp);
printf("Deleteing %s\n", target);
return (1);
}
/* traverse the list until the target value is found */
else
{
prev = *headPtr;
curr = (*headPtr) -> next;
while (curr != NULL &&
strcmp(curr -> data.tagNo, target))
{
prev = curr;
curr = curr -> next;
}
if(curr != NULL)
{
/* delete the node that contains the target */
/* value */
temp = curr;
prev -> next = curr -> next;
free(temp);
printf("Deleteing %s\n", target);
return (1);
}
else
{
printf("Not in the list\n");
return (-1);
}
}
}
/******************
* IsEmpty takes a NODEPTR as its first
* argument, which is a pointer to the list,
* known as head. It determines whether the
* list is empty or not and returns 1 (true)
* if the list is empty and 0 (false) if it
* is not empty.
******************/
int IsEmpty (NODEPTR head)
{
/* If the pointer to the list is
NULL then there is no list. The
list is empty, so we return true.
*/
if(head == NULL)
{
return 1;
}
else
{
return 0;
}
}
/******************
* PrintList takes a NODEPTR as an argument
* which is a pointer to the list, known as
* head. The list is traversed and the values
* held in the data member of each node is printed.
******************/
void PrintList (NODEPTR head)
{
NODEPTR curr;
if (IsEmpty (head))
{
printf ("The list is empty\n");
}
else
{
/* set the current pointer to the first
node of the list */
curr = head;
/*Until the end of the list*/
while (curr != NULL)
{
/* print the current data item */
printf("tag : %s\n", curr -> data.tagNo);
printf("owner : %s\n", curr -> data.owner);
printf("make : %s\n", curr -> data.make);
printf("model : %s\n", curr -> data.model);
printf("lot : %d\n\n", curr -> data.lot);
/* move to the next node */
curr = curr -> next;
}
}
}
]]>
The Driver
<![CDATA[
/***********************************************
* File: sortedlldriver.c
* Author: Sue Bogar
* Date: 11/22/98
* Section: 101
* Email: bogar@cs.umbc.edu
*
* Description: a driver for testing sorted linked
* list code
************************************************/
#include <stdio.h>
#include "sortedll.h"
int main ()
{
NODEPTR head, temp;
INFO new;
char target[8];
int flag;
head = NULL;
temp = CreateNode();
printf ("\nEnter the tag number of the vehicle : ");
scanf ("%s", new.tagNo);
printf ("\nEnter the owner's last name : ");
scanf ("%s", new.owner);
printf ("\nEnter the make of the vehicle : ");
scanf ("%s", new.make);
printf ("\nEnter the model of the vehicle : ");
scanf ("%s", new.model);
printf ("\nEnter the assigned parking lot : ");
scanf ("%d", &new.lot);
SetData (temp, new);
Insert (&head, temp);
PrintList (head);
printf("-------------------------------------\n");
temp = CreateNode();
printf ("\nEnter the tag number of the vehicle : ");
scanf ("%s", new.tagNo);
printf ("\nEnter the owner's last name : ");
scanf ("%s", new.owner);
printf ("\nEnter the make of the vehicle : ");
scanf ("%s", new.make);
printf ("\nEnter the model of the vehicle : ");
scanf ("%s", new.model);
printf ("\nEnter the assigned parking lot : ");
scanf ("%d", &new.lot);
SetData (temp, new);
Insert (&head, temp);
PrintList (head);
printf("-------------------------------------\n");
temp = CreateNode();
printf ("\nEnter the tag number of the vehicle : ");
scanf ("%s", new.tagNo);
printf ("\nEnter the owner's last name : ");
scanf ("%s", new.owner);
printf ("\nEnter the make of the vehicle : ");
scanf ("%s", new.make);
printf ("\nEnter the model of the vehicle : ");
scanf ("%s", new.model);
printf ("\nEnter the assigned parking lot : ");
scanf ("%d", &new.lot);
SetData (temp, new);
Insert (&head, temp);
PrintList (head);
printf("-------------------------------------\n");
printf("\nEnter the tag number to be deleted : ");
scanf("%s", target);
flag = Delete(&head, target);
printf("The value %d was returned\n", flag);
PrintList (head);
printf("-------------------------------------\n");
printf("\nEnter the tag number to be deleted : ");
scanf("%s", target);
flag = Delete(&head, target);
printf("The value %d was returned\n", flag);
PrintList (head);
printf("-------------------------------------\n");
printf("\nEnter the tag number to be deleted : ");
scanf("%s", target);
flag = Delete(&head, target);
printf("The value %d was returned\n", flag);
PrintList (head);
printf("-------------------------------------\n");
printf("\nEnter the tag number to be deleted : ");
scanf("%s", target);
flag = Delete(&head, target);
printf("The value %d was returned\n", flag);
PrintList (head);
printf("-------------------------------------\n");
printf("\nEnter the tag number to be deleted : ");
scanf("%s", target);
flag = Delete(&head, target);
printf("The value %d was returned\n", flag);
PrintList (head);
printf("-------------------------------------\n");
return 0;
}
]]>
The Output
<![CDATA[
linux1[102] a.out
Enter the tag number of the vehicle : WMT123
Enter the owner's last name : Brown
Enter the make of the vehicle : Honda
Enter the model of the vehicle : Accord
Enter the assigned parking lot : 1
tag : WMT123
owner : Brown
make : Honda
model : Accord
lot : 1
-------------------------------------
Enter the tag number of the vehicle : ASG179
Enter the owner's last name : Smith
Enter the make of the vehicle : Olds
Enter the model of the vehicle : Calais
Enter the assigned parking lot : 14
tag : ASG179
owner : Smith
make : Olds
model : Calais
lot : 14
tag : WMT123
owner : Brown
make : Honda
model : Accord
lot : 1
-------------------------------------
Enter the tag number of the vehicle : ESD987
Enter the owner's last name : Jones
Enter the make of the vehicle : Ford
Enter the model of the vehicle : Tempo
Enter the assigned parking lot : 1
tag : ASG179
owner : Smith
make : Olds
model : Calais
lot : 14
tag : ESD987
owner : Jones
make : Ford
model : Tempo
lot : 1
tag : WMT123
owner : Brown
make : Honda
model : Accord
lot : 1
-------------------------------------
Enter the tag number to be deleted : ESD987
Deleteing ESD987
The value 1 was returned
tag : ASG179
owner : Smith
make : Olds
model : Calais
lot : 14
tag : WMT123
owner : Brown
make : Honda
model : Accord
lot : 1
-------------------------------------
Enter the tag number to be deleted : Wme345
Not in the list
The value -1 was returned
tag : ASG179
owner : Smith
make : Olds
model : Calais
lot : 14
tag : WMT123
owner : Brown
make : Honda
model : Accord
lot : 1
-------------------------------------
Enter the tag number to be deleted : WMT123
Deleteing WMT123
The value 1 was returned
tag : ASG179
owner : Smith
make : Olds
model : Calais
lot : 14
-------------------------------------
Enter the tag number to be deleted : ASG179
Deleteing ASG179
The value 1 was returned
The list is empty
-------------------------------------
Enter the tag number to be deleted : WMT123
Can't delete from an empty list
The value -1 was returned
The list is empty
-------------------------------------
linux1[103]
]]>