Any help would be awesome. Beyond stuck. Ill post the question down below: Write

Question

Any help would be awesome. Beyond stuck. Ill post the question down below:

Write recursive functions that perform insertion and retrieval operations on a pointer-based sorted linked list of integers. The insertion function should be void, taking a head pointer and the item to be inserted as parameters. The retrieval function should take a head pointer and the item to be retrieved as parameters, and should return the item's position, or -1 if the item is not found in the list. Use these procedures to write a program that inputs a series of integers, inserting them into a list until 0 is entered. Then a second series of integers is input, until 0 is entered, and the position of each integer in the list is displayed.

Example:

Enter numbers to be inserted (0 to end): 34 23 1 45 7 0

The list is: 1 7 23 34 45

Enter numbers to be retrieved (0 to end): 23 8 45 0

23 is at position 3

8 is not in the list

45 is at position 5

Note that the program should be able to handle requests to retrieve items that are not in the list.

Explanation / Answer

/* Program to insert in a sorted list */
#include<stdio.h>
#include<stdlib.h>

/* Link list node */
struct node
{
int data;
struct node* next;
};

/* function to insert a new_node in a list. Note that this
function expects a pointer to head_ref as this can modify the
head of the input linked list (similar to push())*/
void sortedInsert(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;
}
}

/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */

/* A utility function to create a new node */
struct node *newNode(int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;
new_node->next = NULL;

return new_node;
}

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

int retrieve(struct node *head, int num, int loc){
if(head == NULL)
return -1;
if(head->data > num){
return -1;
}
if(head->data == num)
return loc;
return retrieve(head->next, num, loc+1);
}

/* Drier program to test count function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;
struct node *new_node;
int num;
int flag;
printf("Enter numbers to be inserted (0 to end) : ");

do{
scanf("%d", &num);
if(num != 0){
new_node = newNode(num);
sortedInsert(&head, new_node);
}
}while(num != 0);

printf("The list is : ");
printList(head);
printf(" ");

printf("Enter numbers to be retrieved (0 to end) : ");
do{
scanf("%d",&num);
if(num != 0){
flag = retrieve(head, num, 1);

if(flag == -1){
printf("%d is not in the list ",num);
}else{
printf("%d is at position %d ", num, flag);
}
}
}while(num != 0);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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