C++ please struct Node { } 1. Define a function called insert. As input paramete

Question

C++ please

struct Node {

}

1. Define a function called insert. As input parameters, insert takes a Node pointer that points to the end of an ordered list and another Node pointer that points to a new Node that will be added to the ordered list. The function insert returns no value. After insert is finished running, the new Node should be incorporated as part of the ordered list passed as a parameter. Assumptions: 1) the pointer to the first Node in the ordered list corresponds with the node that has the greatest value in the list and 2) the ordered list represented by the pointer pointing to the first Node in the list is already ordered.

2. Define a function called pop. As an input parameter, pop takes a Node pointer to a stack. It returns a Node pointer to the Node it is removing (hint: NOT deleting) from the stack. After pop has run, the stack pointed at by the input parameter no longer contains the Node that is being returned via a Node pointer.

Explanation / Answer

1.

#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node* next;
};

void sortedInsert(struct node** head_ref, struct node* new_node)
{
struct node* current;

if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
{
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{

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;
}
}

struct node *newNode(int new_data)
{

struct node* new_node =
(struct node*) malloc(sizeof(struct node));

new_node->data = new_data;
new_node->next = NULL;

return new_node;
}

void printList(struct node *head)
{
struct node *temp = head;
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}

int main()
{
/* Start with the empty list */
struct node* head = NULL;
struct node *new_node = newNode(5);
sortedInsert(&head, new_node);
new_node = newNode(10);
sortedInsert(&head, new_node);
new_node = newNode(7);
sortedInsert(&head, new_node);
new_node = newNode(3);
sortedInsert(&head, new_node);
new_node = newNode(1);
sortedInsert(&head, new_node);
new_node = newNode(9);
sortedInsert(&head, new_node);
printf(" Created Linked List ");
printList(head);

getchar();
return 0;
}

2.int Pop(struct node** headRef) {
struct node* head;
int result;
head = *headRef;
assert(head != NULL);
result = head->data;

*headRef = head->next;

free(head); // free the head node
return(result);

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.