Can anyone tell me how (and provide syntax) to delete a node in a dynamic link list? I used new to create nodes, the nodes are structures with forward links (next) and back linking (link). I can create and view all nodes easily, but cannot seem to find the proper way to delete them. So if anyone could show me the syntax or point me to a site it would be GREATLY appreciated.
Tek-Tips is the largest IT community on the Internet today!
Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!
-
Congratulations strongm on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!
Dynamic Link Listing (deleting nodes question)
- Thread starter Chemakill
- Start date
- Thread starter
- #2
If it is of any use, what follows is a copy and paste of my entire program's code. It should copy and paste directly into the compiler as a .cpp.
//Ryan's Employee program, Dynamic Link List Version.
#include <stdio.h>
#include <stdlib.h>
//The structure
struct EmployeeRecord
{
long empnum;
char name[25];
short pc;
float sal;
//link is now a pointer that points to the last record
EmployeeRecord *link;
//next is now a pointer that always points to one record beyond the current.
EmployeeRecord *next;
};
typedef struct EmployeeRecord SER;
//These are the pointers which will create and traverse the link list.
//The ptr_add can never change outside of add or it will warp the list,
//the ptr_top must always show the last record,
//the root must always equal NULL and represent the beginning of the list.
SER *root, *ptr_add, *ptr_top, *ptr_temp;
void menu();
void add();
void listind();
void listall();
void delet();
void payroll();
void main()
{
//Set the initial values of all the pointers.
//Create the first record and equate it to NULL
root = new EmployeeRecord;
root->next=NULL;
//Set the first position to the beginning NULL record.
ptr_add=root;
//Set the top to equal NULL, ie, the last record, as it is also the first one, at this point.
ptr_top = NULL;
menu();
printf("This program written by Ryan McPherson.\n"
;
}
void menu()
{
short choice;
//The menu loop
do
{
printf("Menu\n\n"
printf("1. Add a record.\n2. List a record.\n3. List all records\n"
printf("4. Delete a record.\n5. Calculate total payroll.\n6. Exit\n"
printf("\nYour choice: "
scanf("%d", &choice);
switch(choice)
{
case 1: add();
break;
case 2: listind();
break;
case 3: listall();
break;
case 4: delet();
break;
case 5: payroll();
break;
case 6: break;
default: printf("Please select a valid option.\n"
menu();
break;
}
}
while(choice < 6);
}
void add()
{
short x, ct;
printf("How many records would you like to add?\n"
scanf("%d", &x);
//Loop the correct number of times
for(ct = 0; ct<x; ct++)
{
//Insert the values
//Create a new record.
ptr_add->next = new EmployeeRecord;
//Insert all values into the new next.
printf("Please enter the employee number.\n"
scanf("%d", &ptr_add->next->empnum);
printf("Please enter the employee's name.\n"
scanf("%s", ptr_add->next->name);
printf("Please enter the employee's pay code.\n"
scanf("%d", &ptr_add->next->pc);
printf("Please enter the employee's salary.\n"
scanf("%f", &ptr_add->next->sal);
//The linking process
//Set the link variable of the new record to the top. In the first record, set it to NULL.
ptr_add->next->link = ptr_top;
//Set the top to the record that was just entered.
ptr_top = ptr_add->next;
//Set the next record to NULL. This sets a boundary beyond which we will not loop until
//a new record is entered, as all that lies beyond here is infinite. And the infinite is scary.
ptr_add->next=NULL;
}
printf("\n\n\n"
}
void listind()
{
//This is a the choice variable and a flag.
short choice, x=0;
printf("Please enter the employee number of the the employee you wish to view.\n"
scanf("%d", &choice);
//Set the temp pointer to the top so that top won't have to change.
ptr_temp = ptr_top;
//Loop while the pointer isn't beyond our bounds (each set to NULL) and the record hasn't been found.
while(ptr_temp->next!=NULL && x!=-1)
{
//The 'if'
if(ptr_temp->empnum == choice)
{
printf("%d\t%s\t%d\t$%7.2f\n", ptr_temp->empnum,ptr_temp->name,ptr_temp->pc,ptr_temp->sal);
x = -1;
}
else
{
//Remember, link is equal to the previous record. Which we want, if the record has not
//been found
ptr_temp = ptr_temp->link;
}
}
printf("\n\n\n"
}
void listall()
{
//Set the temp pointer to the top.
ptr_temp = ptr_top;
//Loops and prints
do
{
//Print the current record, then...
printf("%d\t%s\t%d\t$%7.2f\n", ptr_temp->empnum,ptr_temp->name,ptr_temp->pc,ptr_temp->sal);
//Advance to the next record.
ptr_temp = ptr_temp->link;
}
while(ptr_temp != NULL);
printf("\n\n\n"
}
void delet()
{
short choice;
char confirm = 'y';
SER *ptr_saved;
printf("Please enter the employee number of the employee you would like to delete.\n"
scanf("%d", &choice);
ptr_temp = ptr_top;
//Is this the top record?
if(root->empnum == choice)
{
printf("%d\t%s\t%d\t$%7.2f\n", root->empnum,root->name,root->pc,root->sal);
printf("Are you sure you wish to delete this record? (y/n): "
getchar();
scanf("%c", &confirm);
//Confirmation
if(confirm == 'y')
{
//First, saved the next hop position
ptr_saved = root->next;
//Remove the record in question
delete root;
//Make this position equal to the previous next hop position
root = ptr_saved;
printf("Record deleted.\n"
//The next hop position must be saved first, otherwise the chain will be broken
//with no way to recover the link
}
}
//Otherwise...
else
{
//Looping to find the record
for(ptr_temp=ptr_top; ptr_temp->next!=NULL; ptr_temp=ptr_temp->next)
{
if(ptr_temp->next->empnum == choice)
{
printf("%d\t%s\t%d\t$%7.2f\n", ptr_temp->next->empnum,ptr_temp->next->name,ptr_temp->next->pc,ptr_temp->next->sal);
printf("Are you sure you wish to delete this record? (y/n): "
getchar();
scanf("%c", &confirm);
//Confirmation
if(confirm == 'y')
{
//Very similiar to before.
//Save the position of the next hop
ptr_saved = ptr_temp->next->next;
//Free the current position
delete ptr_temp;
//Revert the current position to the saved one
ptr_temp = ptr_saved;
printf("Record deleted.\n"
}
}
}
}
printf("\n\n\n"
/*
NOTE: The use of the command 'free' may or may not be correct. According to
the book from which I am teaching myself this, one would use the 'free' command.
*/
}
void payroll()
{
double tpay = 0;
short pc1=8*5*52, pc2=5*52;
//Set the temp pointer to the top
ptr_temp = ptr_top;
//loops, calculates a value.
do
{
switch(ptr_temp->pc)
{
case 1: tpay = tpay + ptr_temp->sal*pc1;
break;
case 2: tpay = tpay + ptr_temp->sal*pc2;
break;
case 3: tpay = tpay + ptr_temp->sal*52;
break;
case 4: tpay = tpay + ptr_temp->sal*26;
break;
default: break;
}
//Advance onward!
ptr_temp = ptr_temp->link;
}
//Until we hit the fence.
while(ptr_temp != NULL);
printf("The total payroll is: $%7.2f\n\n\n", tpay);
}
//Ryan's Employee program, Dynamic Link List Version.
#include <stdio.h>
#include <stdlib.h>
//The structure
struct EmployeeRecord
{
long empnum;
char name[25];
short pc;
float sal;
//link is now a pointer that points to the last record
EmployeeRecord *link;
//next is now a pointer that always points to one record beyond the current.
EmployeeRecord *next;
};
typedef struct EmployeeRecord SER;
//These are the pointers which will create and traverse the link list.
//The ptr_add can never change outside of add or it will warp the list,
//the ptr_top must always show the last record,
//the root must always equal NULL and represent the beginning of the list.
SER *root, *ptr_add, *ptr_top, *ptr_temp;
void menu();
void add();
void listind();
void listall();
void delet();
void payroll();
void main()
{
//Set the initial values of all the pointers.
//Create the first record and equate it to NULL
root = new EmployeeRecord;
root->next=NULL;
//Set the first position to the beginning NULL record.
ptr_add=root;
//Set the top to equal NULL, ie, the last record, as it is also the first one, at this point.
ptr_top = NULL;
menu();
printf("This program written by Ryan McPherson.\n"
;}
void menu()
{
short choice;
//The menu loop
do
{
printf("Menu\n\n"
;printf("1. Add a record.\n2. List a record.\n3. List all records\n"
;printf("4. Delete a record.\n5. Calculate total payroll.\n6. Exit\n"
;printf("\nYour choice: "
;scanf("%d", &choice);
switch(choice)
{
case 1: add();
break;
case 2: listind();
break;
case 3: listall();
break;
case 4: delet();
break;
case 5: payroll();
break;
case 6: break;
default: printf("Please select a valid option.\n"
;menu();
break;
}
}
while(choice < 6);
}
void add()
{
short x, ct;
printf("How many records would you like to add?\n"
;scanf("%d", &x);
//Loop the correct number of times
for(ct = 0; ct<x; ct++)
{
//Insert the values
//Create a new record.
ptr_add->next = new EmployeeRecord;
//Insert all values into the new next.
printf("Please enter the employee number.\n"
;scanf("%d", &ptr_add->next->empnum);
printf("Please enter the employee's name.\n"
;scanf("%s", ptr_add->next->name);
printf("Please enter the employee's pay code.\n"
;scanf("%d", &ptr_add->next->pc);
printf("Please enter the employee's salary.\n"
;scanf("%f", &ptr_add->next->sal);
//The linking process
//Set the link variable of the new record to the top. In the first record, set it to NULL.
ptr_add->next->link = ptr_top;
//Set the top to the record that was just entered.
ptr_top = ptr_add->next;
//Set the next record to NULL. This sets a boundary beyond which we will not loop until
//a new record is entered, as all that lies beyond here is infinite. And the infinite is scary.
ptr_add->next=NULL;
}
printf("\n\n\n"
;}
void listind()
{
//This is a the choice variable and a flag.
short choice, x=0;
printf("Please enter the employee number of the the employee you wish to view.\n"
;scanf("%d", &choice);
//Set the temp pointer to the top so that top won't have to change.
ptr_temp = ptr_top;
//Loop while the pointer isn't beyond our bounds (each set to NULL) and the record hasn't been found.
while(ptr_temp->next!=NULL && x!=-1)
{
//The 'if'
if(ptr_temp->empnum == choice)
{
printf("%d\t%s\t%d\t$%7.2f\n", ptr_temp->empnum,ptr_temp->name,ptr_temp->pc,ptr_temp->sal);
x = -1;
}
else
{
//Remember, link is equal to the previous record. Which we want, if the record has not
//been found
ptr_temp = ptr_temp->link;
}
}
printf("\n\n\n"
;}
void listall()
{
//Set the temp pointer to the top.
ptr_temp = ptr_top;
//Loops and prints
do
{
//Print the current record, then...
printf("%d\t%s\t%d\t$%7.2f\n", ptr_temp->empnum,ptr_temp->name,ptr_temp->pc,ptr_temp->sal);
//Advance to the next record.
ptr_temp = ptr_temp->link;
}
while(ptr_temp != NULL);
printf("\n\n\n"
;}
void delet()
{
short choice;
char confirm = 'y';
SER *ptr_saved;
printf("Please enter the employee number of the employee you would like to delete.\n"
;scanf("%d", &choice);
ptr_temp = ptr_top;
//Is this the top record?
if(root->empnum == choice)
{
printf("%d\t%s\t%d\t$%7.2f\n", root->empnum,root->name,root->pc,root->sal);
printf("Are you sure you wish to delete this record? (y/n): "
;getchar();
scanf("%c", &confirm);
//Confirmation
if(confirm == 'y')
{
//First, saved the next hop position
ptr_saved = root->next;
//Remove the record in question
delete root;
//Make this position equal to the previous next hop position
root = ptr_saved;
printf("Record deleted.\n"
;//The next hop position must be saved first, otherwise the chain will be broken
//with no way to recover the link
}
}
//Otherwise...
else
{
//Looping to find the record
for(ptr_temp=ptr_top; ptr_temp->next!=NULL; ptr_temp=ptr_temp->next)
{
if(ptr_temp->next->empnum == choice)
{
printf("%d\t%s\t%d\t$%7.2f\n", ptr_temp->next->empnum,ptr_temp->next->name,ptr_temp->next->pc,ptr_temp->next->sal);
printf("Are you sure you wish to delete this record? (y/n): "
;getchar();
scanf("%c", &confirm);
//Confirmation
if(confirm == 'y')
{
//Very similiar to before.
//Save the position of the next hop
ptr_saved = ptr_temp->next->next;
//Free the current position
delete ptr_temp;
//Revert the current position to the saved one
ptr_temp = ptr_saved;
printf("Record deleted.\n"
;}
}
}
}
printf("\n\n\n"
;/*
NOTE: The use of the command 'free' may or may not be correct. According to
the book from which I am teaching myself this, one would use the 'free' command.
*/
}
void payroll()
{
double tpay = 0;
short pc1=8*5*52, pc2=5*52;
//Set the temp pointer to the top
ptr_temp = ptr_top;
//loops, calculates a value.
do
{
switch(ptr_temp->pc)
{
case 1: tpay = tpay + ptr_temp->sal*pc1;
break;
case 2: tpay = tpay + ptr_temp->sal*pc2;
break;
case 3: tpay = tpay + ptr_temp->sal*52;
break;
case 4: tpay = tpay + ptr_temp->sal*26;
break;
default: break;
}
//Advance onward!
ptr_temp = ptr_temp->link;
}
//Until we hit the fence.
while(ptr_temp != NULL);
printf("The total payroll is: $%7.2f\n\n\n", tpay);
}
Chemakil, it appears to me that you are deleting the ptr_temp which is the current node you are at. You should be deleting the next node. In other words you are peeking one node ahead to see if there is a match for the employee number. If there is a match then you need to get the next node's next ptr. I would say something like this
For (pTemp = pHead; pTemp->next != "" pTemp = pTemp->next)
{
if (pTemp->next->empNum == choice)
{
pNodeToDelete = pTemp->next;
pTemp->next = pNodeToDelete->next;
delete pNodeToDelete;
}
}
HTH,
JC
PS I am doing this only after a cursory look at your code due to time contraints if this is incorrect let me know and i will adjust fire
For (pTemp = pHead; pTemp->next != "" pTemp = pTemp->next)
{
if (pTemp->next->empNum == choice)
{
pNodeToDelete = pTemp->next;
pTemp->next = pNodeToDelete->next;
delete pNodeToDelete;
}
}
HTH,
JC
PS I am doing this only after a cursory look at your code due to time contraints if this is incorrect let me know and i will adjust fire
- Thread starter
- #4
- Status