Objectives: • Having more practice working with and understanding linked lists.
ID: 3703458 • Letter: O
Question
Objectives:
• Having more practice working with and understanding linked lists.
• Implementing a function to search and insert nodes throughout a singly linked list.
• Implementing a function to delete a node at the and of a singly linked list.
• Implementing functions to sort items and count occurrences of items in a singly linked list.
Question: A incomplete C++ code was provided. Your test is to complete this code. Remember only fill out the missing part noted in comments and don't change other existing code. An input text file is also provided on which is used to populate the linked list with its original values. Much of the structure is given for a menu-driven C++ program to implement and perform operations on a singly linked list.
1. Read and understand the given code.
2. Understand each function’s purpose. Take note of the parameter types and return types.
3. Implement the following functions:
a. bool isEmpty(node *current_head)
b. void insertPos(node *current, int val, int toSearch)
c. void printList(node *current)
d. void deleteLast(node *current, node *trailCurrent)
e. void deleteAll(node *current)
f. int frequency(node *current, int toSearch)
g. void sort(node *head)
4. Test your implementation. Ensure each menu choice works correctly. Handling invalid input is not required.
5. Submit a single completed .cpp file.
Incomplete Linklist code:
Content in Input.txt:
Sample Output:
C:Users jlatelSource ReposLab22Debug>Lab22 1. Insert a number at a particular position. 2. Delete the last element. 3. Count a particular value 4. Sort the numbers. 5. Print list. 6. Quit Please enter a choice: 5 10 20 30 40 50 15 25 35 45 55 1. Insert a number at a particular position. 2. Delete the last element. 3. Count a particular value 4. Sort the numbers. 5. Print list. 6. Quit Please enter a choice: 1 Please enter a value to insert: 5 Please enter a current list value after which the new value will be inserted: 20 Number inserted. 1. Insert a number at a particular position. 2. Delete the last element. 3. Count a particular value 4. Sort the numbers. 5. Print list.Explanation / Answer
Please find the below code will all the functons implemented.
#include<iostream>
#include<fstream>
using namespace std;
struct node
{
int data;
node *next;
};
node* initializeList(node*, int);
void showMenu();
void insertPos(node*, int, int);
void deleteLast(node*, node*);
void deleteAll(node*);
int frequency(node*, int);
void sort(node*);
void printList(node*);
bool isEmpty(node*);
// Read and understand the main function. No coding is
// required in main, but please write your functions to
// conform to the function calls originating in main.
int main()
{
int input;
int val;
int toSearch;
ifstream inData;
inData.open("input.txt");
node *head = NULL;
while (inData >> val)
head = initializeList(head, val);
inData.close();
while (true)
{
showMenu();
cin >> input;
switch (input)
{
case 1:
if (!isEmpty(head))
{
cout << "Please enter a value to insert: ";
cin >> val;
cout << "Please enter a current list value after which the new value will be inserted: ";
cin >> toSearch;
insertPos(head, val, toSearch);
}
else
cout << "First add some initial values in the input file. ";
break;
case 2:
if (!isEmpty(head))
deleteLast(head, head);
else
cout << "Nothing to delete. List is empty. ";
break;
case 3:
if (!isEmpty(head))
{
cout << "Enter a number to search: ";
cin >> toSearch;
cout << "frequency = " << frequency(head, toSearch) << endl;
}
else
cout << "Cannot count. List is empty. ";
break;
case 4:
if (!isEmpty(head))
sort(head);
else
cout << "Nothing to sort. List is empty. ";
break;
case 5:
if (!isEmpty(head))
{
printList(head);
cout << endl;
}
else
cout << "Nothing to print. List is empty. ";
break;
case 6:
if (!isEmpty(head))
deleteAll(head);
return 0;
default:
cout << "Please make a valid selection. " << endl;
}
cout << endl;
}
}
// Read and understand the initializeList function. This function
// populates the linked list with numbers read from a text file.
// Ensure the input file is in the same folder as your executable.
// No coding is required here.
node* initializeList(node *current, int val)
{
node* head = current;
node* newNode = new node;
newNode->data = val;
newNode->next = NULL;
if (current == NULL)
{
current = newNode;
return current;
}
while (current->next != NULL)
current = current->next;
current->next = newNode;
return head;
}
// The showMenu function is also complete. No coding is required here.
void showMenu() {
cout << "1. Insert a number at a particular position. ";
cout << "2. Delete the last element. ";
cout << "3. Count a particular value. ";
cout << "4. Sort the numbers. ";
cout << "5. Print list. ";
cout << "6. Quit ";
cout << "Please enter a choice: ";
}
// The isEmpty function takes a node-type pointer to the list head
// POSTCONDITION: TRUE returned if the list is empty. Else false.
bool isEmpty(node *current_head)
{
// TODO: Implement the isEmpty function.
if(current_head==NULL)
return true;
else
return false;
}
// The insertPos function takes a node-type pointer, and
// two integers as arguments. The pointer initially points
// to the list's head, but advances with subsequent
// recursive calls. The variable val contains the
// content that the new inserted node will hold. The variable
// toSearch traverses the list to find that specified value.
// If the value is found at a particular node, the new node
// is inserted directly after the node containing the found value.
void insertPos(node *current, int val, int toSearch)
{
// TODO: Implement the insertPos function.
// NOTE: Here's some pseudo-code if you want it. But feel free
// to implement your own algorithm (as long as it works).
// If the current node is NULL, state that nothing was found and
// nothing was inserted.
if(current == NULL)
cout<<"Nothing is found and no node is inserted.";
// Else if the content at the current node matches the number
// we're searching for, dynamically allocate a newNode.
// Set the new node's content to the parameter val.
else {
node* newNode = new node;
if(current->data == toSearch) {
newNode->data = val;
// If the node after the current node is NULL, (meaning
// we're at the final node), set newNode's next pointer to NULL.
// Set the current node's next pointer to point to newNode.
if(current->next == NULL) {
newNode->next = NULL;
current->next =
newNode;
} else {
// Else, set the new node's next pointer to point to
// where the current node points.
// Then set the current node's next pointer to point to the
// newly inserted node.
newNode->next = current->next;
current->next = newNode;
}
} else {
// Else recursively call insertPos, passing in the subsequent node
// as the current node. The val and toSearch parameters are
// unchanged.
insertPos(current->next,val, toSearch);
}
}
}
// The printList function takes a node-type pointer.
// The pointer initially points to the list's head,
// but advances with subsequent recursive calls.
// POSTCONDITION: The entire list is output.
void printList(node *current)
{
// TODO: Implement the printList function.
if(current->next==NULL)
cout<<current->data<<"->X";
else {
cout<<current->data<<"->";
printList(current->next);
}
}
// The deleteLast function takes two node-type pointers.
// Note their names: current and trailCurrent. One
// pointer is intended to point to the current node. And
// the other is intended to remain one node behind.
// Remember, this is a singly linked list. We cannot traverse
// backwards as we could with a doubly linked list.
// Once the last node is deleted, the trailCurrent pointer can
// be used to set the next-pointer of the new last-node
// (formerly the second to last node) to NULL.
//
// There isn't a lot of code to write here, but spend some time
// analyzing and designing. For your reference, my implementation
// is six lines.
void deleteLast(node *current, node *trailCurrent)
{
// TODO: Implement the deleteLast function.
while (current->next != NULL) {
trailCurrent = current;
current = current->next;
}
trailCurrent->next = NULL;
delete current;
}
// The deleteAll function takes a node-type pointer.
// The pointer initially points to the list's head,
// but advances with subsequent recursive calls.
// POSTCONDITION: All dynamically allocated nodes
// are deleted.
void deleteAll(node *current)
{
node* prev;
while (current->next != NULL) {
prev = current;
current = current->next;
delete prev;
}
delete current;
}
// The frequency function takes a node-type pointer and an int.
// The function counts and returns the number of times toSearch
// occurs in the list.
// POSTCONDITION: The total count of found occurrences is returned.
int frequency(node *current, int toSearch)
{
// TODO: Implement the frequency function.
int freq = 0;
while (current != NULL) {
if(current->data == toSearch) {
freq++;
current = current->next;
}
return freq; }
}
// The sort function takes a node-type pointer.
// POSTCONDITION: The linked list is sorted in ascending order.
void sort(node *head)
{
// HINT: You don't have to rearrange the nodes themselves.
// It is sufficient to rearrange the ->data.
// Consider these temporary pointers for traversal.
node *temp1 = new node;
node *temp2 = new node;
// TODO: Complete this sort function here using any sort
// algorithm.
int data;
temp1=head;
while(temp1!=NULL)
{
temp2=temp1->next;
while(temp2!=NULL)
{
if(temp1->data > temp2->data)
{
data=temp1->data;
temp1->data=temp2->data;
temp2->data=data;
}
temp2=temp2->next;
}
temp1=temp1->next;
}
// And don't forget to delete dynamically allocated nodes.
delete temp1;
delete temp2;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.