Question

C++

Assume that you have a structure Node as follows: struct Node { int value; Node* next; Node(int v, Node* n = nullptr) { // constructor value = v; next = n; } }; Question 1 (20 points) Write a function "count" that counts the number of elements in a given linked list. The prototype of this function is as follows: int count_elements(Node*); Question 2 (20 points) Write a function “average" that calculates the average of all the elements in a given linked list. The prototype of this function is as follows: double average(Node*); Question 3 (20 points) Write a function "insert_sorted" that inserts a value into the correct position in the linked list to keep it sorted at all times. The prototype of this function is as follows: void insert_sorted(Node*&); Question 4 (20 points) Write a function "delete_even" that deletes all even numbers from a given linked list. The prototype of this function is as follows: void delete_all_even(Node*&); Question 5 (20 points) Write a main function to test all the previous functions with arbitrary values of your choice.

Answer 1

A-1)

int count_elements(Node* head, int search_for) 
{ 
    Node* current = head; 
    int count = 0; 
    while (current != NULL) { 
        if (current->data == search_for) 
            count++; 
        current = current->next; 
    } 
    return count; 
} 

A-2)

double average(struct Node* head) 
{ 
    // if head = NULL 
    if (!head) 
        return -1; 
  
    int count = 0; // Initialize count 
    int sum = 0; 
    float avg = 0.0; 
  
    struct Node* current = head; // Initialize current 
    while (current != NULL) { 
        count++; 
        sum += current->data; 
        current = current->next; 
    } 
  
    // calculate average 
    avg = (double)sum / count; 
  
    return avg; 
} 

A-3)

void insert_sorted(struct Node** head_ref, struct Node* new_node) 
{ 
    struct Node* current; 
    /* Special case for the head end */
    if (*head_ref == NULL || (*head_ref)->data >= new_node->data) 
    { 
        new_node->next = *head_ref; 
        *head_ref = new_node; 
    } 
    else
    { 
        /* Locate the node before the point of insertion */
        current = *head_ref; 
        while (current->next!=NULL && 
               current->next->data < new_node->data) 
        { 
            current = current->next; 
        } 
        new_node->next = current->next; 
        current->next = new_node; 
    } 
} 

A-4)

void delete_all_even(Node** head_ref)
{
    Node* ptr = *head_ref;
    // Node* next;
 
    while (ptr != NULL) {
        // next = ptr->next;
        // If true, delete node 'ptr'
        if (ptr->data % 2 == 0)
            deleteNode(head_ref,
                       ptr->data);
        ptr = ptr->next;
    }
}

A-5)

int main() 
{ 
    struct Node* head = NULL; 
  
    // create linked list 7->6->8->4->1 
    push(&head, 7); 
    push(&head, 6); 
    push(&head, 8); 
    push(&head, 4); 
    push(&head, 1); 

    cout << "Count No. of nodes = " << count_elements(head);
    cout << "Average of nodes = " << avgerage(head);
    cout << "Sorting of nodes = " << insert_sorted(head);
    cout << "Delete Number of nodes = " << delete_all_even(head); 
  
    return 0; 
}