Have something to say? Contribute New Article Reply to this Article
Linked list problem
//Pg.288
#include <cassert>
#include <iostream>
using namespace std;
void deleteKthElement(int k, int& count);
int main()
{
struct nodeType {
int info;
nodeType *link;
};
nodeType *first, *newNode, *last, *traverse;
int num;
int count = 0;
cout << "Enter a list of integers ending with -999.\n";
cin >> num;
first = NULL;
while (num != -999)
{
newNode = new nodeType;
assert(newNode !=NULL);
newNode ->info = num;
newNode ->link = NULL;
if(first == NULL)
{
first = newNode;
last = newNode;
}
else
{
last -> link = newNode;
last = newNode;
}
cin >> num;
count++; //increment the counter to keep track of no. of elements
} // end while
//print the linked list prior to deleting the 5th element
cout << "The linked list before:" << endl;
traverse = new nodeType;
assert(traverse != NULL);
traverse = first;
while (traverse != NULL)
{
cout << traverse->info << endl;
traverse = traverse->link;
}
deleteKthElement(5,count);
//print the linked list after deleting the 5th element !!
cout << "The linked list after deleting the 5th element:" << endl;
traverse = new nodeType;
assert(traverse != NULL);
traverse = first;
while (traverse != NULL)
{
cout << traverse->info << endl;
traverse = traverse->link;
}
} // end main
void deleteKthElement(int k, int& count)
{
assert(k <= count);
nodeType *current, *trailCurrent;
int i;
if (first ==NULL)
cerr << "Cannot delete from an empty list!" << endl;
else
if (k == 1)
{
current = first;
first = first->link;
if (first == NULL)
last = NULL;
delete current;
}
else
{
trailCurrent = first;
current = first->link;
i = 2;
while(i < k)
{
trailCurrent = current;
current = current->link;
i++;
}
trailCurrent->link = current->link;
if (current == last)
last = trailCurrent;
}
}
I'm struggling to get the 5th element deleted in the list
Compiler giving me a lot of errors ; eg. nodeType undeclared, etc.
Please help ?
I did what you said and i'm still experiencing some problems.Could you please paste the code into your compiler and run it ?
Thanks once again for your previous reply !
Thanks ... i seem to have found help .
Here's the adapted code
//Pg.288
#include <cassert>
#include <iostream>
using namespace std;
struct nodeType
{
int info;
nodeType *link;
};
void deleteKthElement(nodeType *firstElement, int k, const int& count);
int main()
{
nodeType *first, *newNode, *last, *traverse;
int num;
int count = 0;
cout << "Enter a list of integers ending with -999.\n";
cin >> num;
first = NULL;
while (num != -999)
{
newNode = new nodeType;
assert(newNode !=NULL);
newNode ->info = num;
newNode ->link = NULL;
if(first == NULL)
{
first = newNode;
last = newNode;
}
else
{
last -> link = newNode;
last = newNode;
}
cin >> num;
count++; //increment the counter to keep track of no. of elements
} // end while
//print the linked list prior to deleting the 3rd element
cout << "The linked list before:" << endl;
//traverse = new nodeType;
//assert(traverse != NULL);
traverse = first;
while (traverse != NULL)
{
cout << traverse->info << endl;
traverse = traverse->link;
}
deleteKthElement(first->link,2,count);
//print the linked list after deleting the 3rd element
cout << "The linked list after deleting the 3rd element:" << endl;
//traverse = new nodeType;
//assert(traverse != NULL);
traverse = first;
while (traverse != NULL)
{
cout << traverse->info << endl;
traverse = traverse->link;
}
} // end main
void deleteKthElement( nodeType *firstElement,int k, const int& count)
{
assert(k <= count);
nodeType *first ,*last, *current, *trailCurrent;
int i;
first = firstElement;
if (firstElement == NULL)
cerr << "Cannot delete from an empty list!" << endl;
else
if (k == 1)
{
current = firstElement;
firstElement = firstElement->link;
if (firstElement == NULL)
last = NULL;
delete current;
}
else
{
trailCurrent = firstElement;
current = firstElement->link;
i = 2;
while(i < k)
{
trailCurrent = current;
current = current->link;
i++;
}
trailCurrent->link = current->link;
if (current == last)
last = trailCurrent;
}
} //end deleteKthElement//Pg.288
#include <cassert>
#include <iostream>
using namespace std;
struct nodeType
{
int info;
nodeType *link;
};
void deleteKthElement(nodeType *firstElement, int k, const int& count);
int main()
{
nodeType *first, *newNode, *last, *traverse;
int num;
int count = 1;
cout << "Enter a list of integers ending with -999.\n";
cin >> num;
first = NULL;
while (num != -999)
{
newNode = new nodeType;
assert(newNode !=NULL);
newNode ->info = num;
newNode ->link = NULL;
if(first == NULL)
{
first = newNode;
last = newNode;
}
else
{
last -> link = newNode;
last = newNode;
}
cin >> num;
count++; //increment the counter to keep track of no. of elements
} // end while
//print the linked list prior to deleting the 3rd element
cout << "The linked list before:" << endl;
//traverse = new nodeType;
//assert(traverse != NULL);
traverse = first;
while (traverse != NULL)
{
cout << traverse->info << endl;
traverse = traverse->link;
}
deleteKthElement(first,2,count);
//print the linked list after deleting the 2nd element
cout << "The linked list after deleting the 2nd element:" << endl;
//traverse = new nodeType;
//assert(traverse != NULL);
traverse = first;
while (traverse != NULL)
{
cout << traverse->info << endl;
traverse = traverse->link;
}
} // end main
void deleteKthElement( nodeType *firstElement,int k, const int& count)
{
assert(k <= count);
nodeType *first ,*last, *current, *trailCurrent;
int i = 1;
// first = firstElement;
if (firstElement == NULL)
cerr << "Cannot delete from an empty list!" << endl;
else
if (k == 1)
{
current = firstElement;
firstElement = firstElement->link;
if (firstElement == NULL)
last = NULL;
delete current;
}
else
{
trailCurrent = firstElement;
current = firstElement->link;
i = 2;
while(i < k)
{
trailCurrent = current;
current = current->link;
i++;
}
trailCurrent->link = current->link;
if (current == last)
last = trailCurrent;
}
} //end deleteKthElementI thought i had this problem solved but i've just one last issue:
Why is the program displaying a zero (0) after deleting the node with the smallest info ??
Note: The program seems to work fine if the node with the smallest info is not the first node in the linked list. Why is this ?
(Please refer to my attachments for the code as well as the input and output of the program)
I thought i had this problem solved but i've just one last issue: Why is the program displaying a zero (0) after deleting the node with the smallest info ?? Note: The program seems to work fine if the node with the smallest info is not the first node in the linked list. Why is this ? (Please refer to my attachments for the code as well as the input and output of the program)
#include <cassert>
#include <iostream>
using namespace std;
struct nodeType
{
int info;
nodeType *link;
};
void deleteKthElement(nodeType *firstElement, int k, const int& count);
void deletesmallestInfoNode(nodeType *firstType);
void deleteNode(nodeType *firstNode, const int& deleteItem);
void deletegivenInfoNode(nodeType *fNode, const int& deleteInfo);
/* ------------------------------------------------------------------------ */
int main()
{
nodeType *first, *newNode, *last, *traverse;
int num;
int count = 0;
cout << "Enter a list of integers ending with -999.\n";
cin >> num;
first = NULL;
while (num != -999)
{
newNode = new nodeType;
assert(newNode !=NULL);
newNode ->info = num;
newNode ->link = NULL;
if(first == NULL)
{
first = newNode;
last = newNode;
}
else
{
last -> link = newNode;
last = newNode;
}
cin >> num;
count++; //increment the counter to keep track of no. of elements
} // end while
//print the linked list prior to deleting the 2nd element
cout << "The linked list before:" << endl;
traverse = first;
while (traverse != NULL)
{
cout << traverse->info << endl;
traverse = traverse->link;
}
deleteKthElement(first,2,count);
//print the linked list after deleting the 2nd element
cout << "The linked list after deleting the 2nd element:" << endl;
traverse = first;
while (traverse != NULL)
{
cout << traverse->info << endl;
traverse = traverse->link;
}
deletesmallestInfoNode(first);
//print the linked list after deleting the node with the smallest info
cout << "The linked list after deleting the node with the smallest info:" << endl;
traverse = first;
while (traverse != NULL)
{
cout << traverse->info << endl;
traverse = traverse->link;
}
deletegivenInfoNode(first,15);
//print the linked list after removing all occurences of 15 in the list
cout << "The linked list after deleting all occurences of 15 in the list:" << endl;
traverse = first;
while (traverse != NULL)
{
cout << traverse->info << endl;
traverse = traverse->link;
}
} // end main
/* ------------------------------------------------------------------------ */
void deleteKthElement( nodeType *firstElement,int k, const int& count)
{
assert(k <= count);
nodeType *first ,*last, *current, *trailCurrent;
int i = 1;
// first = firstElement;
if (firstElement == NULL)
cerr << "Cannot delete from an empty list!" << endl;
else
if (k == 1)
{
current = firstElement;
firstElement = firstElement->link;
if (firstElement == NULL)
last = NULL;
delete current;
}
else
{
trailCurrent = firstElement;
current = firstElement->link;
i = 2;
while(i < k)
{
trailCurrent = current;
current = current->link;
i++;
}
trailCurrent->link = current->link;
if (current == last)
last = trailCurrent;
}
} //end deleteKthElement
void deletesmallestInfoNode(nodeType *firstType)
{
nodeType *first;
first = firstType;
if (first == NULL) // the list has only one node
cerr << "Cannot delete from an empty list!" << endl;
else
{
nodeType* newNode;
bool found = false;
newNode = first; // newNode points to the first node
while (newNode != NULL && !found)
{
if (newNode->link == NULL) //only 1 node in list or the last
{
deleteNode(first,newNode->info); //call function to delete node
found = true; //smallest info found !
}
else if (newNode->info <= newNode->link->info)
{
deleteNode(first,newNode->info); //call function to delete node
found = true; //smallest info found !
}
else
newNode = newNode->link; //advance newNode
} // end while
} // endif
}//end deletesmallestInfoNode
void deleteNode(nodeType *firstNode ,const int& deleteItem)
{
nodeType *first, *last;
nodeType *current; //pointer to traverse the list
nodeType *trailCurrent; //pointer just before current
bool found;
first = firstNode;
if(first == NULL) //Case 1; list is empty.
cerr<<"Cannot delete from an empty list.\n";
else
{
if(first->info == deleteItem) //Case 2
{
current = first;
first = first->link;
if(first == NULL) //list only had 1 node
last = NULL;
delete current;
}
else //search the list for the node with the given info
{
found = false;
trailCurrent = first; //set trailCurrent to point to
//the first node
current = first->link; //set current to point to the
//second node
while(current != NULL && !found)
{
if(current->info != deleteItem)
{
trailCurrent = current;
current = current->link;
}
else
found = true;
} // end while
if(found) //Case 3; if found, delete the node
{
trailCurrent->link = current->link;
//count--;
if(last == current) //node to be deleted was
//the last node
last = trailCurrent; //update the value of last
delete current; //delete the node from the list
}
else
cout<<"Item to be deleted is not in the list."<<endl;
} //end else
} //end else
} //end deleteNode
//function to delete all occurences of a given info in the list
void deletegivenInfoNode(nodeType *fNode, const int& deleteInfo)
{
nodeType *first;
first = fNode;
bool found = false;
if (first == NULL) // the list has only one node
cerr << "Cannot delete from an empty list!" << endl;
else
{
nodeType *traversePtr; //pointer to traverse the list
traversePtr = first; // traversePtr points to the first node
while (traversePtr != NULL)
{
if (traversePtr->info == deleteInfo)
{
deleteNode(first,deleteInfo);
found = true;
}
else
traversePtr = traversePtr->link; //advance traversePtr
} // end while
} // end if
if (!(found))
cout << "Item to be deleted is not in the list!" << endl;
} // end deletegivenInfoNodeThis article has been dead for over three months
You
© 2012 DaniWeb® LLC
